Paper 2003/127

Using Information Theory Approach to Randomness Testing

B. Ya. Ryabko and V. A. Monarev

Abstract

We address the problem of detecting deviations of binary sequence from randomness,which is very important for random number (RNG) and pseudorandom number generators (PRNG). Namely, we consider a null hypothesis $H_0$ that a given bit sequence is generated by Bernoulli source with equal probabilities of 0 and 1 and the alternative hypothesis $H_1$ that the sequence is generated by a stationary and ergodic source which differs from the source under $H_0$. We show that data compression methods can be used as a basis for such testing and describe two new tests for randomness, which are based on ideas of universal coding. Known statistical tests and suggested ones are applied for testing PRNGs, which are practically used. Those experiments show that the power of the new tests is greater than of many known algorithms.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
pseudo-randomness
Contact author(s)
ryabko @ adm ict nsc ru
History
2003-06-23: received
Short URL
https://ia.cr/2003/127
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/127,
      author = {B.  Ya.  Ryabko and V. A.  Monarev},
      title = {Using Information Theory Approach to  Randomness Testing},
      howpublished = {Cryptology ePrint Archive, Paper 2003/127},
      year = {2003},
      note = {\url{https://eprint.iacr.org/2003/127}},
      url = {https://eprint.iacr.org/2003/127}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.