In this paper we review some statistical tests included in the NIST SP 800-22 suite, which is a collection of tests for the evaluation of both true-random (physical) and pseudorandom (algorithmic) number generators for cryptographic applications. The output of these tests is the so-called p-value which is a random variable whose distribution converges to the uniform distribution in the interval [0,1] when testing an increasing number of samples from an ideal generator. Here, we compute the exact non-asymptotic distribution of p-values produced by few of the tests in the suite, and propose some computation-friendly approximations. This allows us to explain why intensive testing produces false-positives with a probability much higher than the expected one when considering asymptotic distribution instead of the true one. We also propose a new approximation for the Spectral Test reference distribution, which is more coherent with experimental results.
F. Pareschi, R. Rovatti, G. Setti (2012). On Statistical Tests for Randomness Included in the NIST SP800-22 Test Suite and Based on the Binomial Distribution. IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, 7, 491-505 [10.1109/TIFS.2012.2185227].
On Statistical Tests for Randomness Included in the NIST SP800-22 Test Suite and Based on the Binomial Distribution
PARESCHI, FABIO;ROVATTI, RICCARDO;
2012
Abstract
In this paper we review some statistical tests included in the NIST SP 800-22 suite, which is a collection of tests for the evaluation of both true-random (physical) and pseudorandom (algorithmic) number generators for cryptographic applications. The output of these tests is the so-called p-value which is a random variable whose distribution converges to the uniform distribution in the interval [0,1] when testing an increasing number of samples from an ideal generator. Here, we compute the exact non-asymptotic distribution of p-values produced by few of the tests in the suite, and propose some computation-friendly approximations. This allows us to explain why intensive testing produces false-positives with a probability much higher than the expected one when considering asymptotic distribution instead of the true one. We also propose a new approximation for the Spectral Test reference distribution, which is more coherent with experimental results.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
