ETH Zürich » Computer Science » Theory » Cryptography

Statistical Randomness Testing

A new statistical test for random bit generators has been developed that is universal in the sense that any significant deviation of the output statistics from the statistics of a unbiased random bit source is detected with high probability when the defective generator can be modeled as an ergodic stationary source with finite memory. This is in contrast to most presently used statistical tests which can detect only one type of non-randomness, for example, a bias in the distribution of 0's and 1's or a correlation between consecutive bits. Moreover, the new test, whose formulation was motivated by considering the universal data compression algorithms of Elias and of Willems, measures the entropy per output bit of a generator. This is shown to be the correct quality measure for a random bit generator in cryptographic applications. A generator is thus rejected with high probability if and only if the cryptographic significance of a statistical defect is above a specified threshold. The test is easy to implement and very efficient.

Research Highlights

  • Universal statistical test. A new statistical randomness test was proposed in [Mau92a] which measures the entropy of a given bit source, universally for the large classes of stationary ergodic sources. The test is now widely used in cryptographic and other applications.

Publication Concerning This Topic

Ueli Maurer
A Universal Statistical Test for Random Bit Generators
Journal of Cryptology, vol. 5, no. 2, pp. 89–105, 1992, Preliminary version: [Mau90b].
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer
A Universal Statistical Test for Random Bit Generators
Advances in Cryptology — CRYPTO '90, Lecture Notes in Computer Science, Springer-Verlag, vol. 537, pp. 409–420, Aug 1990, Final version: [Mau92a].
Available files: [ Abstract ] [ BibTeX ]

© IACR | Springer | ACM | IEEE

Main Research Page