×

An accurate evaluation of Maurer’s universal test. (English) Zbl 0929.94006

Tavares, Stafford (ed.) et al., Selected areas in cryptography. 5th annual international workshop, SAC ’98. Kingston, Ontario, Canada, August 17–18, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1556, 57-71 (1999).
Summary: U. Maurer’s universal test [J. Cryptology 5, 89-105 (1992; Zbl 0790.94014)] is a very common randomness test, capable of detecting a wide gammut of statistical defects. The algorithm is simple (a few Java code lines), flexible (a variety of parameter combinations can be chosen by the tester) and fast. Although the test is based on sound probabilistic grounds, one of its crucical parts uses the heuristic approximation: \[ c(L,K) \cong 0.7-{0.8\over L}+\left(1.6+{12.8 \over L}\right) K^{-4/L}. \] In this work the authors compute the precise value of \(c(L,K)\) and show that the inaccuracy due to the heuristic estimate can make the test 2.67 times more permissive than what is theoretically admitted. Moreover, theye establish a new asymptotic relation between the test parameter and the source’s entropy.
For the entire collection see [Zbl 0912.00037].

MSC:

94A60 Cryptography
62P99 Applications of statistics
65C10 Random number generation in numerical analysis

Citations:

Zbl 0790.94014
PDFBibTeX XMLCite