On the randomness test and its incompleteness
Gao Jinping · Journal of Tsinghua University(Science and Technology) · 2011
Randomness test specifications do not demonstrate the relationship between statistical tests and the nature of randomness,thus providing little guidance for practical security evaluations.The indistinguishability definition of randomness states that randomness tests ideally have to investigate all probabilistic polynomial algorithms,hence testing randomness with completeness is theoretically impossible.Pseudorandomness can be tested by verifying the probabilistic distribution of the seed and the correctness of the claimed indistinguishability proofs for short random seeds.Further,pseudorandom generators with long seeds and non-deterministic random generators require statistical tests,while the quantitative relationship between sample size and significant level in statistical tests is also proved by applying Chebyshev's multivariate inequality and statistical techniques.An example is given to demonstrate that the statistical tests in specification NIST SP800-22 may not detect the obvious non-randomness of some contrived sequences.These results show that practical testing approaches can only detect non-randomness to some degree,but cannot be used to certify randomness.