LS-14 test suite for long sequences

Abstract

Random number sequences are used in many branches of science. Because of many techni- cal reasons and their practicality, pseudo random sequences are usually employed in place of true number sequences. Whether a sequence generated through a deterministic process is a pseudo random, in other words, random-looking sequence or it contains certain pat- terns, can be determined with the help of statistics and mathematics. Although, in the literature there are many statistical randomness tests for this purpose, there is no much work on test suites specialized for long sequences, that is sequences of length 1,000,000 bits or more. Most of the randomness tests for long sequences use some mathematical approximations to compute expected values of the random variables and hence their results contain some errors. Another approach to evaluate randomness criteria of long sequences is to partition the long sequence into a collection short sequences and evaluate the collection for the ran- domness using statistical goodness of fit tests. The main advantage of this approach is, as the individual sequences are short, there is no need to use mathematical approximations. On the other hand when the second approach is preferred, partition the long sequence into a collection of fixed length subsequences and this approach causes a loss of information in some cases. Hence the idea of dynamic partition should be included to perform a more reliable test suite. In this paper, we propose three new tests, namely the entire R2 run, dynamic saturation point, and dynamic run tests. Moreover, we introduce a new test suite, called LS-14, consisting of 14 tests to evaluate randomness of long sequences. As LS-14 employs all three approaches: testing the entire long sequence, testing the collection of fixed length partitions of it, and finally, testing the collection obtained by the dynamic partitions of it, the proposed LS-14 test suit differs from all existing suites. Mutual comparisons of all 14 tests in the LS-14 suite, with each other are computed. Moreover, results obtained from the proposed test suite and NIST SP800-22 suite are compared. Examples of sequences with certain patterns which are not observed by NIST SP800-22 suite but detected by the proposed test suite are given.

Keywords

• Randomness
• random number
• statistical tests
• cryptography
• NIST SP800-22
• dynamic partitioning

References

1. [1] A.A. Abd EL-Latif, B. Abd-El-Atty and S.E. Venegas-Andraca, Controlled alternate quantum walk-based pseudo-random number generator and its application to quantum color image encryption, Phys. A: Stat. Mech. 547, 2020.
2. [2] Z. Akcengiz, M. Aslan, Ö. Karabayır, A. Doğanaksoy, M. Uğuz and F. Sulak, Statistical randomness tests of long sequences by dynamic partitioning, 2020 International Conference on Information Security and Cryptology, Ankara, Turkey, 2020.
3. [3] R.G. Brown, Dieharder: A random number test suite, 2013.
4. [4] M.B. Demirköz, B. Kocaoğlu, Glitter Lamps: A Cryptographically- Secure, Physical, Non-Deterministic Random Bit Generator, In Preparation.
5. [5] A. Doğanaksoy and F. Göloğlu, On lempel-ziv complexity of sequences, Sequences and Their Applications-SETA, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 4086, 180-189, 2006.
6. [6] A. Doğanaksoy, F. Sulak, M. Uğuz, O. Şeker and Z. Akcengiz, Mutual correlation of NIST statistical randomness tests and comparison of their sensitivities on transformed sequences, Turk. J. Electr. Eng. 25, 655-665, 2017.
7. [7] A. Doğanaksoy, F. Sulak, M. Uğuz, O. Şeker and Z. Akcengiz, New statistical randomness tests based on length of runs, Mathematical Problems in Engineering, Hindawi Publishing Corporation, 2015.
8. [8] C. Fan, Q. Ding and C.K. Tse, Evaluating the randomness of chaotic binary sequences via a novel period detection algorithm, Int J Bifurcat Chaos 32 (5), 2022.

9. [9] C. Georgescu, E. Simion, A. Petrescu-Nita and A. Toma, A view on nist randomness tests (in)dependence, 9th International Conference on Electronics, Computers and Artificial Intelligence (ECAI), 14, 2017.
10. [10] M. Gil, G. Gonnet and W. Petersen, A repetition test for pseudorandom number generators, Monte Carlo Methods Appl 12, 385-393, 2006.
11. [11] W. Golomb, Shift Register Sequences, Aegean Park Press, 1982.
12. [12] K. Hamano and T. Kaneko, Correction of overlapping template matching test included in nist randomness test suite, IEICE Transactions 90, 1788-1792, 2007.
13. [13] K. Hamano, F. Sato and H. Yamamoto, A new randomness test based on linear complexity profile, IEICE Transactions 92, 166-172, 2009.
14. [14] K. Hamano and H. Yamamoto, A randomness test based on t-complexity, IEICE Transactions 93, 1346-1354, 2010.
15. [15] J. Hernandez-Castro and D.F. Barrero, Evolutionary generation and degeneration of randomness to assess the independence of the ent test battery, IEEE Congress on Evolutionary Computation (CEC), 1420-1427, 2017.
16. [16] J. Hernandez-Castro, J. Sierra and A. Seznec, The sac test: A new randomness test, with some applications to prng analysis, Computational Science and Its Applications (ICCSA), International Conference, Assisi, Italy, 2004.
17. [17] J.A. Karell-Albo, C.M. Legón-Pérez, E.J. Madarro-Capó, O. Rojas and G. Sosa- Gómez, Measuring independence between statistical randomness tests by mutual information, Entropy 22, 2020.
18. [18] M.G. Kendall and B.B. Smith, Randomness and random sampling numbers, J. R. Stat. Soc. 101 (1), 147-166, 1938.
19. [19] O. Koçak, A unified evaluation of statistical randomness tests and experimental analysis of their relations, Ankara: METU, 2016.
20. [20] D.E. Knuth, The Art of Computer Programming, Volume 2 (3rd Ed.): Semi numerical Algorithms, Addison-Wesley Longman Publishing, 1997.
21. [21] P. LEcuyer, Testing random number generators, Theory Probab. its Appl. 35, 305- 313, 1992.
22. [22] P. LEcuyer and R. Simard, Testu01: A C library for empirical testing of random number generators, ACM Trans Math Softw 33 (4), 1-40, 2007.
23. [23] H. Li, Y. Liu, M. Su and G. Wang, Jump and hop randomness tests for binary sequences, Cryptogr Commun 14, 483-502, 2022.
24. [24] G. Marsaglia, The marsaglia random number cdrom including the diehard battery of tests of randomness, 1996.
25. [25] G. Marsaglia and A. Zaman, Monkey tests for random number generators, Comput. Math. with Appl. 26, 1-10, 1993.
26. [26] U.M. Maurer, A universal statistical test for random bit generators, J. Cryptol. 5, 89-105, 1992.
27. [27] K. Pearson, Notes on regression and inheritance in the case of two parents, Proc. R. Soc. Lond. 58, 1895.
28. [28] A. Rukhin, Testing randomness: A suite of statistical procedures, Theory Probab. its Appl. 45, 2000.
29. [29] A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, M.L. Stefan Leigh, M. Vangel, D. Banks, A. Heckert, J. Dray and S. Vo, A statistical test suite for random and pseudo random number generators for cryptographic applications, NIST SP, 2001.
30. [30] B. Ryabko, V. Stognienko and Y. Shokin, A new test for randomness and its application to some cryptographic problems, J. Stat. Plan. Inference 123, 365-376, 2004.
31. [31] J. Soto, Randomness testing of the advanced encryption standard candidate algorithms, 2001.
32. [32] J. Soto, Statistical testing of random number generators, 1999.
33. [33] A. Srinivasan, M. Mascagni and D. Ceperley, Testing parallel random number generators, Parallel Comput. 29, 69-94, 2003.
34. [34] F. Sulak, New statistical randomness tests: 4-bit template matching tests, Turk. J. Math. 41, 80-95, 2017.
35. [35] F. Sulak, A new statistical randomness test: Saturation point test, Int. J. Inf. Secur. 2, 81-85, 2013.
36. [36] F. Sulak, Statistical analysis of block ciphers and hash functions, METU, 2012.
37. [37] F. Sulak, M. Uğuz, O. Koçak and A. Doğanaksoy, On the independence of statistical randomness tests included in the nist test suite, Turk. J. Electr. Eng. 25, 3673-3683, 2017.
38. [38] F. Sulak, A. Doğanaksoy, M. Uğuz, O. Kocak, Periodic template tests: A family of statistical randomness tests for a collection of binary sequences, Discret. Appl. Math. 271, 191-204, 2019.
39. [39] M.S. Turan, E. Barker, J. Kelsey, K.A. McKay, M.L. Baish and M. Boyle, Recommendation for the entropy sources used for random bit generation, NIST, 2018.
40. [40] M. Turan, A. Doğanaksoy and S. Boztaş, On independence and sensitivity of statistical randomness tests, Sequences and Their Applications-SETA, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, volume 5203, 1829, 2008.
41. [41] A.V. Tutueva, E.G. Nepomuceno, A.I. Karimov, V.S. Andreev and D.N. Butusov, Adaptive chaotic maps and their application to pseudo-random numbers generation, Chaos Solitons Fractals 133, 2020.
42. [42] M. Uğuz, A.Doğanaksoy, F. Sulak, and O. Koçak, R-2 composition tests: a family of statistical randomness tests for a collection of binary sequences, Cryptogr Commun 11, 921-949, 2019.
43. [43] J. Walker, Ent. a pseudorandom number sequence test program, Software anddocumentation, 2008.
44. [44] C. Zhu, S. Li and Q. Lu, Pseudo-random number sequence generator based on chaoticlogistic-tent system, 2019 IEEE 2nd International Conference on Automation, Electronics and Electrical Engineering (AUTEEE), Shenyang, China, 2019.
45. [45] https:www.idquantique.com/random-number-generation/products/quantis-randomnumber- generator/
46. [46] https://users.metu.edu.tr/muhid/netcoreapp3.1.rar