Comparative Analysis of Statistical Test based on Data Compression Methods and Standard Tests for Assessing Randomness of Random Number Generators
https://doi.org/10.25205/1818-7900-2025-23-1-33-45
Abstract
This paper presents a detailed comparative analysis of statistical tests utilizing both modern data compressors and standard statistical methods for assessing the randomness of Random number generators (RNG). Our study aims to thoroughly evaluate the efficiency and performance of these tests in determining the quality of RNG output sequences.
Data compression techniques have long been recognized as effective statistical tests, with some being asymptotically optimal. We compare the effectiveness of these data compressor-based tests with traditional statistical tests in assessing the randomness properties of RNG.
Our results demonstrate that the efficiency of data compressor tests and standard statistical tests is closely similar. Through rigorous experimentation and analysis, we show that both approaches yield comparable results in evaluating the randomness of RNG output sequences.
Keywords
Data compression statistical tests,
random number generator,
National Institute of Standards and Technology statistical test,
TESU01 test
Supporting agencies: I would like to express my sincere gratitude to my supervisor, Professor Ryabko Boris Yakovlevich, for his invaluable assistance with the critical review of the experiment and insightful comments on the manuscript.
About the Author
Y. G. Lulu
Novosibirsk State University
Russian Federation
Russian Federation
Yeshewas Getachew Lulu, PhD Student, Faculty of Information Technology
Novosibirsk
References
1. Ryabko, B. Y.; Monarev, V. A. Using information theory approach to randomness testing: Journal of Statistical Planning and Inference. 2005, vol. 133, no. 1, pp. 95–110.
2. Ryabko, B. Asymptotically most powerful tests for random number generators. J Stat. Planning Infer.2022, 217, 1–7.
3. L’ECUYER, P. History of uniform random number generation. In 2017 Winter Simulation Conference. 2017, pp. 202–230.
4. Mezenes, A.; Van Oorschot, P.; Vanstone, S. Handbook of Applied Cryptography. CRC Press, Boca Raton, FL. 1996.
5. Matsumoto, M.; Takuji, Nishimura. Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8. 1998, 3-30.
6. Rukhin, L. Testing randomness: a suite of statistical proce-dures. Theory of Probability & Its Applications. 2001, vol. 45, no. 1, pp.111–132.
7. 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 Applications. National Institute of Standards and Technology, 2010.
8. L’Ecuyer, P.; Simard, R. TestU01: A C library for empirical testing of random number generators. ACM Trans. Math. Softw. (TOMS) 2007, 33, 22.
9. Ryabko, B., Astola, J.; Malyutov, M. Compression-Based Methods of Statistical Analysis and Prediction of Time Series. Springer International Publishing Switzerland. 2016.
10. Marsaglia, G. The marsaglia random number CDROMincluding the diehard battery of tests of randomness.1995.
11. Caelli, W. Crypt x package documentation. Tech. Rep.,Infor-mation Security Research. 1992.
12. Katos, V. A randomness test for block ciphers. Applied Mathe-matics and Computation. 2005, vol. 162, no. 1, pp. 29–35.
13. Alcover, P. M., Guillam ́, A., Ruiz , M. D. A new randomness test for bit sequences. Informatics. 2013, vol. 24, no. 3, pp. 339–356.
14. Knuth, Donald. E. The Art of Computer Programming. Semi numerical Algorithms. 1997, Volume 2, Addison-Wesley.
15. Abdelfattah, M. S., Hagiescu, A., Singh, D. Gzip on a chip: High performance lossless data compression on fpgas using opencl. In Proceedings of the international workshop on openCL. 2013 & 2014, pp. 1–9.
16. Onuma, Y., Terashima, Y., Kiyohara, R. Compression method for ECU software updates. IEEE Tenth International Conference on Mobile Computing and Ubiquitous Network (ICMU). 2017 Oct 3, pp. 1-6.
17. Andrea, Rock. Pseudorandom Number Generators for Cryptographic Applications. Universitat Salzburg, Marz. 2005.
18. Alakuijala, J., Farruggia, A., Ferragina, P., Kliuchnikov, E., Obryk, R., Szabadka, Z., Vandevenne, L. Brotli: A general-purpose data compressor. ACM Transactions on Information Systems (TOIS).2018, 37, 1–30.
19. Collet, Y., Kucherawy, M. Zstandard Compression and the application/zstd Media Type. 2018, No. rfc8478.
20. Li, Mingyin., Yue, Liu., Na, Wang. A Novel ANS Coding with Low Computational ComplexityIEEE/CIC International Conference on Communications in China (ICCC Workshops). IEEE, 2023.
21. Ryabko, B. Ya., Stognienko, V. S., Shokin, Yu. I. A new test for randomness and its application to some cryptographic problems. J. Statist. Plann. Inference 123, 365–376.
22. Fontaine, C. LINEAR CONGRUENTIAL GENERATOR. van Tilborg, H.C.A. (eds) Encyclopedia of Cryptography and Security. Springer, Boston, MA.2005.
23. Markowsky, G. The Sad History of Random Bits. J. Cyber Secur. Mobil.2014, 31, 1–24.
24. Klein, A. Linear Feedback Shift Registers Stream Ciphers. Springer, London. 2013,17–58.
25. Kim, J., Chae, H. All-Digital True Random-Number Generator using Middle Square Method, IEEE Asian Solid-State Circuits Conference (A-SSCC), Taipei, Taiwan. 2022, pp. 1–3.
26. Matsumoto, M., Saito, M., Nishimura, T., Hatagi, M. Cryptographic Mersenne Twister and Fubuki stream/block cipher. Cryptographic ePrint Archive, June 2005.
27. O’Neill, Melissa E. PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation. ACM Transactions on Mathematical Software. 2014
28. Blum, L., Blum, M., Shub, M. A Simple Unpredictable Pseudo-Random Number Generator. SIAM Journal on Computing, Society for Industrial & Applied Mathematics (SIAM). 2021, 364–383.
Review
For citations:
Lulu Y.G. Comparative Analysis of Statistical Test based on Data Compression Methods and Standard Tests for Assessing Randomness of Random Number Generators. Vestnik NSU. Series: Information Technologies. 2025;23(1):33-45. https://doi.org/10.25205/1818-7900-2025-23-1-33-45
Views:
136
Email this article 