zbMATH — the first resource for mathematics

Checking the quality of approximation of \(p\)-values in statistical tests for random number generators by using a three-level test. (English) Zbl 07316676
Summary: Statistical tests of pseudorandom number generators (PRNGs) are applicable to any type of random number generators and are indispensable for evaluation. While several practical packages for statistical tests of randomness exist, they may suffer from a lack of reliability: for some tests, the amount of approximation error can be deemed significant. Reducing this error by finding a better approximation is necessary, but it generally requires an enormous amount of effort. In this paper, we introduce an experimental method for revealing defects in statistical tests by using a three-level test proposed by Okutomi and Nakamura. In particular, we investigate the NIST test suite and the test batteries in TestU01, which are widely used statistical packages. Furthermore, we show the efficiency of several modifications for some tests.
65C Probabilistic methods, stochastic differential equations
62E Statistical distribution theory
62F Parametric inference
Full Text: DOI
[1] Bassham, L. E.; Rukhin, A. L.; Soto, J.; Nechvatal, J. R.; Smid, M. E.; Barker, E. B.; Leigh, S. D.; Levenson, M.; Vangel, M.; Banks, D. L.; Heckert, N. A.; Dray, J. F.; Vo, S., SP 800-22 Rev. 1a. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, Technical Report (2010), National Institute of Standards & Technology: National Institute of Standards & Technology Gaithersburg, MD, United States
[2] Coron, J. S., On the security of random sources, (Public Key Cryptography: Second International Workshop on Practice and Theory in Public Key Cryptography, PKC’99 Kamakura, Japan, March 1-3, 1999 Proceedings (1999), Springer: Springer Berlin, Heidelberg), 29-42 · Zbl 0964.94018
[3] Fishman, G. S., Principles of Discrete Event Simulation (1978), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York, NY, USA · Zbl 0537.68104
[4] Hamano, K.; Kaneko, T., Correction of overlapping template matching test included in NIST randomness test suite, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E90-A, 9, 1788-1792 (2007)
[5] Kim, S. J.; Umeno, K.; Hasegawa, A., Corrections of the NIST Statistical Test Suite for Randomness, IACR Cryptology EPrint Archive, 2004, 18 (2004)
[6] Knuth, D. E., (The Art of Computer Programming, vol. 2. The Art of Computer Programming, vol. 2, Seminumerical Algorithms (1997), Addison-Wesley) · Zbl 0883.68015
[7] L’Ecuyer, P., Testing random number generators, (Proceedings of the 1992 Winter Simulation Conference (1992), IEEE Press), 305-313
[8] L’Ecuyer, P., Uniform random number generation, Ann. Oper. Res., 53, 77-120 (1994), 1310607(95k:65007) · Zbl 0843.65004
[9] L’Ecuyer, P., Tests based on sum-functions of spacings for uniform random numbers, J. Stat. Comput. Simul., 59, 3, 251-269 (1997), https://doi.org/10.1080/00949659708811859 · Zbl 0901.65001
[10] L’Ecuyer, P.; Cordeau, J. F.; Simard, R., Close-point spatial tests and their application to random number generators, Oper. Res., 48, 2, 308-317 (2000), http://pubsonline.informs.org/doi/pdf/10.1287/opre.48.2.308.12385 · Zbl 1106.65301
[11] L’Ecuyer, P.; Simard, R., TestU01: A C library for empirical testing of random number generators, ACM Trans. Math. Software, 33, 4, 22:1-22:40 (2007) · Zbl 1365.65008
[13] L’Ecuyer, P.; Simard, R.; Wegenkittl, S., Sparse serial tests of uniformity for random number generators, SIAM J. Sci. Comput., 24, 2, 652-668 (2002) · Zbl 1037.62006
[14] Marsaglia, G., Note on a proposed test for random number generators, IEEE Trans. Comput., C-34, 8, 756-758 (1985) · Zbl 0572.65001
[15] Matsumoto, M.; Nishimura, T., Mersenne Ttister: A 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Trans. Model. Comput. Simul., 8, 1, 3-30 (1998) · Zbl 0917.65005
[16] Okutomi, H.; Nakamura, K., A study on rational judgement method of randomness property using NIST randomnes test (in Japanese), Trans. Inst. Electron. Inf. Commun. Eng. A, 93, 1, 11-22 (2010)
[17] Pareschi, F.; Rovatti, R.; Setti, G., On statistical tests for randomness included in the NIST SP800-22 test suite and based on the binomial distribution, IEEE Trans. Inf. Forensics Secur., 7, 2, 491-505 (2012)
[18] Simard, R.; L’Ecuyer, P., Computing the two-sided Kolmogorov-Smirnov distribution, J. Statist. Softw. Articles, 39, 11, 1-18 (2011)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.