Graph Theoretic Approach to Randomness Test Based on the Overlapping Blocks

Abstract

Cryptographic parameters such as secret keys, should be chosen randomly and at the same time it should not be so difficult to reproduced them when necessary. Because of this, pseudorandom bit (or number) generators take the role of true random generators. Outputs of pseudorandom generators, although they are produced through some deterministic process, should be random looking, that is not distinguishable from true random sequences. In other word they should not follow any pattern. In this paper we propose a new approach using graph theory, to determine when to expected a fixed pattern to appear in a random sequence for the fist time. Using these expected values and comparing them with the observed values a randomness test can be defined. In this work patters are traced through the sequence in an overlapping manner.

Keywords

• Cryptography
• Statistical Randomness Testing
• NIST Test Suite
• Recursion

References

1. [1]M. U˘guz, “Kirptografide rastgelelik,” in Siber G¨uvenlik ve Savunma: Blokzincir ve Kriptoloji, S¸ . Sa˘gıro˘glu and S. Akleylek, Eds. Nobel Akademik Yayıncılık E˘gitim Danıs¸manlık Tic. Ltd. S¸ ti, 2021, vol. 5, pp. 311–346.
2. [2] M. U˘guz, A. Do˘ganaksoy, F. Sulak, and O. Koc¸ak, “R-2 composition tests: a family of statistical randomness tests for a collection of binary sequences,” Cryptography and Communications, vol. 11, pp. 921–949, 2019.
3. [3] F. Sulak, “New statistical randomness tests: 4-bit template matching tests,” Turkish Journal of Mathematics, vol. 41, no. 1, pp. 80–95, 2017.
4. [4] P. M. Alcover, A. Guillam´on, and M. d. C. Ruiz, “A new randomness test for bit sequences,” Informatica, vol. 24, no. 3, pp. 339–356, 2013.
5. [5] K. Hamano and H. Yamamoto, “A randomness test based on tcodes,” in 2008 International Symposium on Information Theory and Its Applications. IEEE, 2008, pp. 1–6.
6. [6] K. Hamano, F. Sato, and H. Yamamoto, “A new randomness test based on linear complexity profile,” IEICE transactions on fundamentals of electronics, communications and computer sciences, vol. 92, no. 1, pp. 166–172, 2009.
7. [7] K. Hamano and H. Yamamoto, “A randomness test based on tcomplexity,” IEICE transactions on fundamentals of electronics, communications and computer sciences, vol. 93, no. 7, pp. 1346–1354, 2010.
8. [8] V. Katos, “A randomness test for block ciphers,” Applied mathematics and computation, vol. 162, no. 1, pp. 29–35, 2005.

9. [9] U. M. Maurer, “A universal statistical test for random bit generators,” Journal of cryptology, vol. 5, pp. 89–105, 1992.
10. [10] D. E. Knuth, The art of computer programming. Pearson Education, 1997, vol. 3.
11. [11] A. Ruhkin, “Testing randomness: A suite of statistical procedures,” Theory of Probability & Its Applications, vol. 45, no. 1, pp. 111–132, 2001.
12. [12] G. Marsaglia, “Random number cdrom including the diehard battery of tests of randomness,” Accessed June. 28, 2023, 1995.
13. [13] C. William, “Cryptx package documentation,” Accessed June. 28, 2023, 1992. [Online]. Available: https://metacpan.org/dist/ CryptX
14. [14] P. L’ecuyer and R. Simard, “Testu01: Ac library for empirical testing of random number generators,” ACM Transactions on Mathematical Software (TOMS), vol. 33, no. 4, pp. 1–40, 2007.
15. [15] L. Bassham, A. Rukhin, J. Soto, J. Nechvatal, M. Smid, S. Leigh, M. Levenson, M. Vangel, N. Heckert, and D. Banks, “A statistical test suite for random and pseudorandom number generators for cryptographic applications,” Accessed June. 28, 2023, 2010-09-16 2010. [Online]. Available: https://tsapps.nist.gov/publication/get pdf.cfm?pub id=906762
16. [16] J. Soto and L. Bassham, “Randomness testing of the advanced encryption standard finalist candidates,” Accessed June. 28, 2023, 2000. [Online]. Available: https://nvlpubs.nist. gov/nistpubs/Legacy/IR/nistir6483.pdf
17. [17] F. Sulak, A. Do˘ganaksoy, M. U˘guz, and O. Koc¸ak, “Periodic template tests: A family of statistical randomness tests for a collection of binary sequences,” Discrete Applied Mathematics, vol. 271, pp. 191–204, 2019.