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