×

zbMATH — the first resource for mathematics

On testing pseudorandom generators via statistical tests based on the arcsine law. (English) Zbl 1441.62043
Summary: Testing the quality of pseudorandom number generators is an important issue. Security requirements become more and more demanding, weaknesses in this matter are simply not acceptable. There is a need for an in-depth analysis of statistical tests – one has to be sure that rejecting/accepting a generator as good is not a result of errors in computations or approximations. In this paper we propose a second level statistical test based on the arcsine law for random walks. We provide upper bounds for the approximation of the arcsine distribution, what allows us to perform a detailed error analysis of the proposed test.
MSC:
62B15 Theory of statistical experiments
62F03 Parametric hypothesis testing
60G50 Sums of independent random variables; random walks
65C10 Random number generation in numerical analysis
11K45 Pseudo-random numbers; Monte Carlo methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Marsaglia, G., The structure of linear congruential sequences, (Zaremba, S., Applications of Number Theory to Numerical Analysis (1972), Academic Press), 249-285
[2] Knuth, D. E., The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 784 (1997), Addison-Wesley Pub. Co
[3] L’Ecuyer, P., Testing random number generators, (Proceedings of the 24th Conference on Winter Simulation. Proceedings of the 24th Conference on Winter Simulation, WSC ’92 (1992), ACM: ACM New York, NY, USA), 305-313
[4] Pareschi, F.; Rovatti, R.; Setti, G., Second-level NIST randomness tests for improving test reliability, (2007 IEEE International Symposium on Circuits and Systems (2007)), 1437-1440
[5] Brown, R. G.; Eddelbuettel, D.; Bauer, D., Dieharder: A random number test suite (2019), (Accessed 3 July 2019)
[6] 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
[7] L’Ecuyer, P.; Simard, R., TestU01: A software library in ANSI C for empirical testing of random number generators. Software user’s guide, version of May 16, 2013 (2013)
[8] NIST.gov - Computer Security Division - Computer Security Resource Center, P., NIST test suite (2019), (Accessed 3 July 2019)
[9] Rukhin, A.; Soto, J.; Nechvatal, J.; Smid, M.; Barker, E.; Leigh, S.; Levenson, M.; Vangel, M.; Banks, D.; Heckert, A.; Dray, J.; Vo, S., A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic ApplicationsTech. Rep. Rev. 1a (2010), NIST, NIST Special Publication 800-22
[10] Pareschi, F.; Rovatti, R.; Setti, G., Second-level testing revisited and applications to NIST SP800-22, (2007 18th European Conference on Circuit Theory and Design (2007), IEEE), 627-630
[11] 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
[12] Matsumoto, M.; Nishimura, T., A nonempirical test on the weight of pseudorandom number generators, (Fang, K.-T.; Niederreiter, H.; Hickernell, F. J., Monte Carlo and Quasi-Monte Carlo Methods 2000 (2002), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 381-395 · Zbl 1002.65010
[13] Leopardi, P. C., Testing the tests: Using random number generators to improve empirical tests, (L’ Ecuyer, P.; Owen, A. B., Monte Carlo and Quasi-Monte Carlo Methods 2008 (2009), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 501-512 · Zbl 1183.62071
[14] Kim, C.; Choe, G. H.; Kim, D. H., Tests of randomness by the Gambler’s ruin algorithm, Appl. Math. Comput., 199, 1, 195-210 (2008) · Zbl 1142.65003
[15] Ekkehard, H.; Grønvik, A., Re-seeding invalidates tests of random number generators, Appl. Math. Comput., 217, 1, 339-346 (2010) · Zbl 1206.65017
[16] Lorek, P.; Słowik, M.; Zagórski, F., Statistical testing of PRNG: generalized Gambler’s ruin problem, (Blömer, J.; Kotsireas, I. S.; Kutsia, T.; Simos, D. E., Mathematical Aspects of Computer and Information Sciences - 7th International Conference, MACIS 2017, Vienna, Austria, November 15-17, 2017, Proceedings. Mathematical Aspects of Computer and Information Sciences - 7th International Conference, MACIS 2017, Vienna, Austria, November 15-17, 2017, Proceedings, Lecture Notes in Computer Science, vol. 10693 (2017), Springer), 425-437 · Zbl 07036072
[17] Feller, W., An Introduction to Probability Theory and Its Applications, Vol. 1 (1968), John Wiley & Sons · Zbl 0155.23101
[18] Wang, Y.; Nicol, T., On statistical distance based testing of pseudo random sequences and experiments with PHP and Debian OpenSSL, Comput. Secur., 53, 44-64 (2015)
[19] Lorek, P.; Łoś, G.; Gotfryd, K.; Zagórski, F., PRNG_Arcsine_test: Empirical tests for PRNGs based on the arcsine law. GitHub repository (2019), GitHub
[20] Asmussen, S.; Glynn, P. W., (Stochastic Simulation: Algorithms and Analysis. Stochastic Simulation: Algorithms and Analysis, Stochastic Modelling and Applied Probability, vol. 57 (2007), Springer-Verlag New York) · Zbl 1126.65001
[21] Kroese, D. P.; Taimre, T.; Botev, Z. I., (Handbook of Monte Carlo Methods. Handbook of Monte Carlo Methods, Wiley Series in Probability and Statistics (2011), John Wiley & Sons: John Wiley & Sons Hoboken, NJ, USA), 1-752 · Zbl 1213.65001
[22] L’Ecuyer, P., History of uniform random number generation, (2017 Winter Simulation Conference. 2017 Winter Simulation Conference, WSC (2017), IEEE), 202-230
[23] Niederreiter, H., Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc., 84, 6, 957-1041 (1978) · Zbl 0404.65003
[24] Denker, M.; Woyczynski, W. A., Introductory Statistics and Random Phenomena. Uncertainty, Complexity, and Chaotic Behavior in Engineering and Science, 509 (1998), Birkhäuser Boston · Zbl 0912.62001
[25] Katz, J.; Lindell, Y., Introduction to Modern Cryptography (2014)
[26] Golic, J., Linear statistical weakness of alleged RC4 keystream generator, (Fumy, W., Advances in Cryptology — EUROCRYPT ’97. Advances in Cryptology — EUROCRYPT ’97, Lecture Notes in Computer Science, vol. 1233 (1997), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), URL http://link.springer.com/10.1007/3-540-69053-0
[27] Fluhrer, S. R.; McGrew, D. A., Statistical analysis of the alleged RC4 keystream generator, (Fast Software Encryption, 7th International Workshop (2000)), 19-30 · Zbl 0994.68639
[28] AlFardan, N.; Bernstein, D. J.; Paterson, K. G.; Poettering, B.; Schuldt, J. C.N., On the security of RC4 in TLS, (Presented As Part of the 22nd USENIX Security Symposium. Presented As Part of the 22nd USENIX Security Symposium, USENIX Security 13 (2013), USENIX: USENIX Washington, D.C.), 305-320, URL https://www.usenix.org/conference/usenixsecurity13/technical-sessions/paper/alFardan
[29] M. Vanhoef, F. Piessens, All Your Biases Belong to Us: Breaking RC4 in WPA-TKIP and TLS, in: USENIX Security Symposium, 2015.
[30] Rescorla, E., The Transport Layer Security (TLS) Protocol Version 1.3, No. 8446 (2018), RFC Editor, August
[31] Gut, A., Probability: A Graduate Course, Springer Texts in Statistics, 608 (2005), Springer-Verlag New York · Zbl 1076.60001
[32] Khintchine, A., Über einen Satz der Wahrscheinlichkeitsrechnung, Fund. Math., 6, 1, 9-20 (1924) · JFM 50.0344.02
[33] Devroye, L., The equivalence of weak, strong and complete convergence in \(L_1\) for kernel density estimates, Ann. Statist., 11, 3, 896-904 (1983) · Zbl 0521.62033
[34] Berend, D.; Kontorovich, A., On the convergence of the empirical distribution (2012), ArXiv e-prints, https://arxiv.org/abs/1205.6711v2
[35] Haramoto, H., Automation of statistical tests on randomness to obtain clearer conclusion, (L’ Ecuyer, P.; Owen, A. B., Monte Carlo and Quasi-Monte Carlo Methods 2008 (2009), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 411-421 · Zbl 1190.62213
[36] Feller, W., An Introduction to Probability Theory and Its Applications, Vol. 2 (1971), John Wiley & Sons · Zbl 0219.60003
[37] Dvoretzky, A.; Motzkin, T., A problem of arrangements, Duke Math. J., 14, 2, 305-313 (1947) · Zbl 0030.16701
[38] L’Ecuyer, P., Combined multiple recursive random number generators, Oper. Res., 44, 5, 816-822 (1996) · Zbl 0904.65004
[39] Harase, S., Conversion of Mersenne Twister to double-precision floating-point numbers, Math. Comput. Simulation, 161, 76-83 (2019)
[40] Haahr, M., RANDOM.ORG: True random number service (2019), (Accessed 3 July 2019)
[41] Takashima, K., Sojourn time test for maximum-length linearly recurring sequences with characteristic primitive trinomials, J. Japanese Soc. Comput. Statist., 7, 77-87 (1994) · Zbl 0830.65003
[42] Takashima, K., Sojourn time test of \(m\)-Sequences with characteristic pentanomials, J. Japanese Soc. Comput. Statist., 8, 37-46 (1995) · Zbl 1330.65010
[43] Takashima, K., Last visit time tests for pseudorandom numbers, J. Japanese Soc. Comput. Statist., 9, 1-14 (1996) · Zbl 1330.65011
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.