Reliability of two-level testing approach in the NIST SP 800-22 test suite

Authors

  • Aleksandr A. Serov Steklov Mathematical Institute, Russian Academy of Sciences, 8 Gubkina Street, Moscow 119333, Russia

Keywords:

random sequence, pseudorandom sequence, statistical testing, reliability of statistical test, binomial distribution, two-sided estimate

Abstract

The two-level approach for testing random number generators involving the well-known NIST SP 800-22 test suite, i. e. counting the sequences passing a basic test and checking the p-values distribution with a chi-square test, was considered. Such an approach may increase the reliability of the test. However, it is sensitive to the approximation error introduced by the computing of p-values. In this paper it is shown that for AES-based sequences two-level testing approach is not reliable too. Systematic error in the computing of the p-values is dependent only on the accuracy of approximation of the exact distribution of statistic by its theoretical counterpart and the number of bits in the analysed sequences n. For a reliable second-level test, this error should be smaller, or at least, approximately equal to $\frac{\sigma}{N} = \frac{1}{k}\sqrt {\frac{{k\; - \;1}}{N}}$, where $\sigma = \sqrt {\frac{1}{k}\left( {1\; - \;\frac{1}{k}} \right)N}$ is the standard deviation from the mean number of particles in a bin for equiprobable scheme of allocation N particles in k bins. Such heuristic assumptions and carried out experiments suggest that for example in the second-level test of the Frequency test of NIST SP 800-22 test suite with n = 220 the number of tested sequences N should not exceed 26 000. To completely eliminate the systematic error appearing in the Frequency test when determining the number of bin from k bins (disjoint subintervals of the interval [0, 1]), to which the p-value belongs the two-sided estimates of the quantiles of the binomial law are proposed.

Author Biography

  • Aleksandr A. Serov, Steklov Mathematical Institute, Russian Academy of Sciences, 8 Gubkina Street, Moscow 119333, Russia

    PhD (physics and mathematics); researcher at the department of discrete mathematics

References

  1. Menezes AJ, van Oorschot PC, Vanstone SA. Handbook of applied cryptography. Boca Raton: CRC Press; 1996. XXVIII, 780 p. (Discrete mathematics and its applications).
  2. Rukhin A, Soto J, Nechvatal J, Smid M, Barker E, Leigh S, et al. A statistical test suite for random and pseudorandom number generators for cryptographic applications. Gaithersburg: National Institute of Standards and Technology; 2010. [131] p. (NIST special publications; SP 800-22 revision 1a).
  3. L’Ecuyer P, Simard R. TestU01: a software library in ANSI C for empirical testing of random number generators [Internet]. Montreal: Université de Montréal; 2013 [cited 2025 June 21]. IV, 214 p. Available from: https://scispace.com/pdf/a-software-library-in-ansi-c-for-empirical-testing-of-random-hk10yxs2w3.pdf.
  4. Pareschi F, Rovatti R, Setti G. Second-level NIST randomness tests for improving test reliability. In: Institute of Electrical and Electronics Engineers. 2007 IEEE International symposium on circuits and systems (ISCAS); 2007 May 27–30; New Orleans, USA. [S. l.]: Institute of Electrical and Electronics Engineers; 2007. p. 1437–1440. DOI: 10.1109/ISCAS.2007.378572.
  5. Kim S-J, Umeno K, Hasegawa A. Corrections of the NIST statistical test suite for randomness. arXiv:nlin/0401040v1 [Preprint]. 2004 [cited 2025 June 21]: [14 p.]. Available from: https://arxiv.org/abs/nlin/0401040v1.
  6. Hamano K. The distribution of the spectrum for the Discrete Fourier transform test included in SP 800-22. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 2005;E88-A(1):67–73.
  7. Hamano K, Kaneko T. Correction of overlapping template matching test included in NIST randomness test suite. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 2007;E90-A(9):1788–1792.
  8. Sulak F, Doğanaksoy A, Ege B, Koçak O. Evaluation of randomness test results for short sequences. In: Carlet C, Pott A, editors. Sequences and their applications – SETA 2010. Proceedings of the 6th International conference; 2010 September 13–17; Paris, France. Berlin: Springer; 2010. p. 309–319 (Lecture notes in computer science; volume 6338). DOI: 10.1007/978-3-642-15874-2_27.
  9. Pareschi F, Rovatti R, Setti G. On statistical tests for randomness included in the NIST SP 800-22 test suite and based on the binomial distribution. IEEE Transactions on Information Forensics and Security. 2012;7(2):491–505. DOI: 10.1109/TIFS.2012.2185227.
  10. Kharin YuS, Zubkov AM. On statistical testing of composite hypotheses on s-dimensional uniform probability distribution of binary sequences. Diskretnaya matematika. 2024;36(1):116–135. Russian. DOI: 10.4213/dm1806.
  11. Rose GG. KISS: a bit too simple. Cryptography and Communications. 2018;10(1):123–137. DOI: 10.1007/s12095-017-0225-x.
  12. Blum L, Blum M, Shub M. A simple unpredictable pseudo-random number generator. SIAM Journal on Computing. 1986;15(2):364–383. DOI: 10.1137/0215025.
  13. Zubkov AM, Serov AA. Testing the NIST statistical test suite on artificial pseudorandom sequences. Matematicheskie voprosy kriptografii. 2019;10(2):89–96. DOI: 10.4213/mvk286.
  14. Zubkov AM, Serov AA. A natural approach to the experimental study of dependence between statistical tests. Matematicheskie voprosy kriptografii. 2021;12(1):131–142. DOI: 10.4213/mvk352.
  15. Shiryaev AN. Probability. 2nd edition. Boas RP, translator. Berlin: Springer-Verlag; 1996. XVI, 623 p. (Graduate texts in mathematics; volume 95).
  16. Korolev V, Shevtsova I. An improvement of the Berry – Esseen inequality with applications to Poisson and mixed Poisson random sums. Scandinavian Actuarial Journal. 2012;2012(2):81–105. DOI: 10.1080/03461238.2010.485370.
  17. Zubkov AM, Serov AA. A complete proof of universal inequalities for distribution function of binomial law. Theory of Probability and its Applications. 2013;57(3):539–544. DOI: 10.1137/S0040585X97986138.
  18. Serov AA. Two-sided estimates of the binomial law quantiles. Theory of Probability and its Applications. Forthcoming 2026.

Downloads

Additional Files

Published

2026-06-01

Issue

No. 1 (2026): Journal of the Belarusian State University. Mathematics and Informatics

Section

Computer Data Analysis

License

Copyright (c) 2026 Journal of the Belarusian State University. Mathematics and Informatics

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)

How to Cite

[1]
Serov, A.A. 2026. Reliability of two-level testing approach in the NIST SP 800-22 test suite. Journal of the Belarusian State University. Mathematics and Informatics. 1 (Jun. 2026), 22–35.