Randomness tests: theory and practice. (English) Zbl 1535.68116
Blass, Andreas (ed.) et al., Fields of logic and computation III. Essays dedicated to Yuri Gurevich on the occasion of his 80th birthday. Cham: Springer. Lect. Notes Comput. Sci. 12180, 258-290 (2020).
Summary: The mathematical theory of probabilities does not refer to the notion of an individual random object. For example, when we toss a fair coin \(n\) times, all \(2^n\) bit strings of length \(n\) are equiprobable outcomes and none of them is more “random” than others. However, when testing a statistical model, e.g., the fair coin hypothesis, we necessarily have to distinguish between outcomes that contradict this model, i.e., the outcomes that convince us to reject this model with some level of certainty, and all other outcomes. The same question arises when we apply randomness tests to some hardware random bits generator.
A similar distinction between random and non-random objects appears in algorithmic information theory. Algorithmic information theory defines the notion of an individual random sequence and therefore splits all infinite bit sequences into random and non-random ones. For finite sequences there is no sharp boundary. Instead, the notion of randomness deficiency can be defined, and sequences with greater deficiency are considered as “less random” ones. This definition can be given in terms of randomness tests that are similar to the practical tests used for checking (pseudo)random bits generators. However, these two kinds of randomness tests are rarely compared and discussed together.
In this survey we try to discuss current methods of producing and testing random bits, having in mind algorithmic information theory as a reference point. We also suggest some approach to construct robust practical tests for random bits.
For the entire collection see [Zbl 1498.03010].
A similar distinction between random and non-random objects appears in algorithmic information theory. Algorithmic information theory defines the notion of an individual random sequence and therefore splits all infinite bit sequences into random and non-random ones. For finite sequences there is no sharp boundary. Instead, the notion of randomness deficiency can be defined, and sequences with greater deficiency are considered as “less random” ones. This definition can be given in terms of randomness tests that are similar to the practical tests used for checking (pseudo)random bits generators. However, these two kinds of randomness tests are rarely compared and discussed together.
In this survey we try to discuss current methods of producing and testing random bits, having in mind algorithmic information theory as a reference point. We also suggest some approach to construct robust practical tests for random bits.
For the entire collection see [Zbl 1498.03010].
MSC:
| 68Q30 | Algorithmic information theory (Kolmogorov complexity, etc.) |
References:
| [1] | Wasserstein, R.L., Lazar, N.A.: Editorial: the ASA’s statement on p-values: context, process, and purpose. Am. Stat. 70(2), 129-133 (2016). https://doi.org/10.1080/00031305.2016.1154108 · Zbl 07665862 · doi:10.1080/00031305.2016.1154108 |
| [2] | Benjamin, D.J., et al.: Redefine statistical significance. Nat. Hum. Behav. 2, 6-10 (2018) · doi:10.1038/s41562-017-0189-z |
| [3] | Bienvenu, L., Gáacs, P., Hoyrup, M., Rojas, C., Shen, A.: Algorithmic tests and randomness with respect to a class of measures. Proc. Steklov Inst. Math. 274, 34-89 (2011). http://arxiv.org/abs/1103.1529 · Zbl 1294.03032 · doi:10.1134/S0081543811060058 |
| [4] | Blum, M., Micali, S.: How to generate cryptographically strong sequences of random bits. SIAM J. Comput. 13(4), 850-864 (1984). https://doi.org/10.1137/0213053. (preliminary version was presented at FOCS 1982 conference) · Zbl 0547.68046 · doi:10.1137/0213053 |
| [5] | Borel, É.: Le Hasard. Librarire Félix Alcan (1920) |
| [6] | Brown, R.G.: Dieharder: a GNU public random generator, version 3.31.1. Technical report, Duke University Physics Department (2006-2018). http://www.phy.duke.edu/ rgb/General/dieharder.php |
| [7] | David, A.P., de Rooij, S., Shafer, G., Shen, A., Vereshchagin, N., Vovk, V.: Insuring against loss of evidence in game-theoretic probability. Stat. Probab. Lett. 81, 157-162 (2011). https://doi.org/10.1016/j.spl.2010.10.013 · Zbl 1206.62004 · doi:10.1016/j.spl.2010.10.013 |
| [8] | Davies, R.: Hardware random number generators. Technical report, Statistics Research Associates Limited (2000). http://robertnz.net/hwrng.htm. Presented at 15th Australian Statistics Conference, July 2000, and 51st Conference of New Zealand Statistical Association, September 2000 |
| [9] | Gurevich, Y., Passmore, G.O.: Impugning randomness, convincingly. Studia Logica 100(1-2), 193-222 (2012). https://link.springer.com/article/10.1007/s11225-012-9375-1. See also https://arxiv.org/pdf/1601.00665.pdf, https://www.cl.cam.ac.uk/ gp351/Gurevich-Passmore-IRC.pdf · Zbl 1262.68054 · doi:10.1007/s11225-012-9375-1 |
| [10] | Gurevich, Y., Vovk, V.: Test statistics and p-values. Technical report, arXiv (2017). Working paper #16, On-line compression modelling project (new series). http://www.alrw.net/articles/16.pdf. See also https://arxiv.org/pdf/1702.02590.pdf |
| [11] | Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364-1396 (1999). https://doi.org/10.1137/S0097539793244708 · Zbl 0940.68048 · doi:10.1137/S0097539793244708 |
| [12] | Kim, S.Y., Umeno, K., Hasegava, A.: Corrections of the NIST statistical test suite for randomness. Technical report (2004). https://eprint.iacr.org/2004/018.pdf |
| [13] | Kireev, A.: On the falsified results of the “referendum” in Sevastopol (in Russian). Technical report, LiveJournal, November 2014. https://kireev.livejournal.com/1095568.html |
| [14] | Knuth, D.: The Art of Computer Programming. Seminumerical Algorithms, vol. 2, 2nd edn. Addison-Wesley, Boston (1981). ISBN 0-201-03822-6 · Zbl 0477.65002 |
| [15] | Kupriyanov, A.: Gauss against Churov: preliminary conclusions. Technical report, Troitsky variant (Russian newspaper), May 2018. https://trv-science.ru/2018/05/08/gauss-protiv-churova-promezhutochnyj-itog |
| [16] | Marsaglia, G.: A current view of random number generators. In: Computer Science and Statistics, Sixteenth Symposium on the Interface, pp. 3-10. Elsevier, North-Holland (1985) |
| [17] | Marsaglia, G.: Random numbers CDROM including the Diehard battery of tests of randomness. Technical report, University of Florida (1995). http://stat.fsu.edu/pub/diehard/, was available at http://stat.fsu.edu/pub/diehard/; now (2019) still available as snapshots from https://web.archive.org. Contains the preprint version of [16, 19] |
| [18] | Marsaglia, G., Tsang, W.W.: Some difficult-to-pass tests of randomness. J. Stat. Softw. 7(3) (2002). https://www.jstatsoft.org/article/view/v007i03 |
| [19] | Marsaglia, G., Zaman, A.: Monkey tests for random number generators. Comput. Math. Appl. 26(9), 1-10 (1993) · Zbl 0788.65007 · doi:10.1016/0898-1221(93)90001-C |
| [20] | Maurer, U.M.: A universal statistical test for random bit generators. J. Cryptol. 5(2), 89-105 (1992). https://link.springer.com/article/10.1007/BF00193563 · Zbl 0790.94014 · doi:10.1007/BF00193563 |
| [21] | Rukhin, A., et al.: A statistical test suite for random and pseudorandom number generators for cryptographic applications, revision 1 by Lawrence E. Bassham III. Special Publication 800-22-1a, National Institute of Standards and Technology, Technology Administration, U.S. Department of Commerce (NIST), April 2010. https://www.nist.gov/publications/statistical-test-suite-random-and-pseudorandom-number-generators-cryptographic. Previous version seems to be unavailable at this site, but the review of Elaine B. Barker, ITL Bulletin (December 2000, 3 pp.), is available at https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=151231. The Lempel-Ziv test, criticised in [12], was there (#10) according to the review; it is missing in the updated version |
| [22] | Barker, E., Kelsey, J.: Recommendation for random number generation using deterministic random bit generators. Special Publication 800-90A, National Institute of Standards and Technology, Technology Administration, U.S. Department of Commerce (NIST), June 2015. https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/final. Previous Version: January 2012 |
| [23] | Turan, M.S., Barker, E., Kelsey, J., McKay, K., Baish, M., Boyle, M.: Recommendation for the entropy sources used for random bit generation. Special Publication 800-90B, National Institute of Standards and Technology, Technology Administration, U.S. Department of Commerce (NIST), January 2018. https://csrc.nist.gov/publications/detail/sp/800-90b/final |
| [24] | Barker, E., Kelsey, J.: Recommendation for random bit generator (RBG) constructions (second draft). Special Publication 800-90C, National Institute of Standards and Technology, Technology Administration, U.S. Department of Commerce (NIST), April 2016. https://csrc.nist.gov/CSRC/media/Publications/sp/800-90c/draft/documents/sp800_90c_second_draft.pdf |
| [25] | Dang, Q.: Recommendation for applications using approved hash algorithms, revision 1. Special Publication 800-107r1, National Institute of Standards and Technology, Technology Administration, U.S. Department of Commerce (NIST), August 2012. https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-107r1.pdf |
| [26] | Novikov, G.: Randomness deficiencies. In: Kari, J., Manea, F., Petre, I. (eds.) CiE 2017. LNCS, vol. 10307, pp. 338-350. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-58741-7_32 · Zbl 1496.03170 · doi:10.1007/978-3-319-58741-7_32 |
| [27] | RAND Corporation: A Million Random Digits with 100,000 Normal Deviates. Free Press (1955). Reissued in 2001 as ISBN 0-8330-3047-7 · Zbl 0068.12905 |
| [28] | Reingold, O., Vadhan, S., Wigderson, A.: A note on extracting randomness from Santha-Vazirani sources. Technical report, available from Reingold (2014). https://omereingold.files.wordpress.com/2014/10/svsources.pdf |
| [29] | Santha, M., Vazirani, U.V.: Generating quasi-random sequences from semi-random sources. J. Comput. Syst. Sci. 33, 75-87 (1986). https://doi.org/10.1016/0022-0000(86)90044-9 · Zbl 0612.94004 · doi:10.1016/0022-0000(86)90044-9 |
| [30] | Shen, A.: Around Kolmogorov complexity: basic notions and results. In: Vovk, V., Papadopoulos, H., Gammerman, A. (eds.) Measures of Complexity, pp. 75-115. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21852-6_7 · Zbl 1338.68130 · doi:10.1007/978-3-319-21852-6_7 |
| [31] | Shen, A.: Election and statistics: the case of “United Russia”, 2009-2018 (in Russian), preprint (2018). https://arxiv.org/abs/1204.0307 |
| [32] | Shen, A.: Making randomness tests more robust. Technical report, HAL, February 2018. https://hal.archives-ouvertes.fr/hal-01707610 |
| [33] | Shen, A., Uspensky, V.A., Vereshchagin, N.K.: Kolmogorov Complexity and Algorithmic Randomness. American Mathematical Society (2017). http://www.lirmm.fr/ ashen/kolmbook-eng-scan.pdf · Zbl 1435.68015 |
| [34] | Stoppard, T.: Rosencrantz and Guildenstern Are Dead, a Play (1966). Grove Press (1971). ISBN 978-0-8021-3275-8 |
| [35] | TrueRNG: TrueRNG documentation. Technical report, Ubld.it (2019). http://ubld.it/truerng_v3 |
| [36] | Vereshchagin, N., Shen, A.: Algorithmic statistics revisited. In: Vovk, V., Papadopoulos, H., Gammerman, A. (eds.) Measures of Complexity, pp. 235-252. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21852-6_17. https://arxiv.org/abs/1504.04950v2 · Zbl 1336.62036 · doi:10.1007/978-3-319-21852-6_17 |
| [37] | Vereshchagin, N., Shen, A.: Algorithmic statistics: forty years later. In: Day, A., Fellows, M., Greenberg, N., Khoussainov, B., Melnikov, A., Rosamond, F. (eds.) Computability and Complexity. LNCS, vol. 10010, pp. 669-737. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-50062-1_41. https://arxiv.org/abs/1607.08077 · Zbl 1365.68297 · doi:10.1007/978-3-319-50062-1_41 |
| [38] | Yao, A.C.: Theory and application of trapdoor functions. In: 23rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 80-91 (1982). http://ieeexplore.ieee.org/document/4568378/ |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
