Reliability of two-level testing approach in the NIST SP 800-22 test suite
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 σN = 1kk - 1 N , where σ = 1k( 1 - 1k )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. , number=1, journal=Journal of the Belarusian State University. Mathematics and Informatics, author=Serov, Aleksandr A., year=2026, month=Jun., pages=22–35