Cryptology ePrint Archive: Report 2019/1426

On asymptotically optimal tests for random number generators

Boris Ryabko

Abstract: The problem of constructing effective statistical tests for random number generators (RNG) is considered. Currently, statistical tests for RNGs are a mandatory part of cryptographic information protection systems, but their effectiveness is mainly estimated based on experiments with various RNGs. We find an asymptotic estimate for the p-value of an optimal test in the case where the alternative hypothesis is a known stationary ergodic source, and then describe a family of tests each of which has the same asymptotic estimate of the p-value for any (unknown) stationary ergodic source.

Category / Keywords: foundations / randomness testing, statistical test for cryptographic applications, random number generators, Information Theory, Shannon entropy.

Date: received 8 Dec 2019, last revised 9 Dec 2019

Contact author: boris at ryabko net

Available format(s): PDF | BibTeX Citation

Version: 20191210:080339 (All versions of this report)

Short URL: ia.cr/2019/1426


[ Cryptology ePrint archive ]