Graph Theoretic Approach to Randomness Test Based on the Overlapping Blocks

Year 2023, Volume: 12 Issue: 2, 42 - 52, 28.06.2023

Muhiddin Uğuz

https://doi.org/10.55859/ijiss.1288854

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]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] 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] F. Sulak, “New statistical randomness tests: 4-bit template matching tests,” Turkish Journal of Mathematics, vol. 41, no. 1, pp. 80–95, 2017.
• [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] 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] 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] 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] V. Katos, “A randomness test for block ciphers,” Applied mathematics and computation, vol. 162, no. 1, pp. 29–35, 2005.
• [9] U. M. Maurer, “A universal statistical test for random bit generators,” Journal of cryptology, vol. 5, pp. 89–105, 1992.
• [10] D. E. Knuth, The art of computer programming. Pearson Education, 1997, vol. 3.
• [11] A. Ruhkin, “Testing randomness: A suite of statistical procedures,” Theory of Probability & Its Applications, vol. 45, no. 1, pp. 111–132, 2001.
• [12] G. Marsaglia, “Random number cdrom including the diehard battery of tests of randomness,” Accessed June. 28, 2023, 1995.
• [13] C. William, “Cryptx package documentation,” Accessed June. 28, 2023, 1992. [Online]. Available: https://metacpan.org/dist/ CryptX
• [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] 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] 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] 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.