Maurer, Ueli M. A universal statistical test for random bit generators. (English) Zbl 0790.94014 J. Cryptology 5, No. 2, 89-105 (1992). Summary: A new statistical test for random bit generators is presented which, in contrast to presently used statistical tests, is universal in the sense that it can detect any significant deviation of a device’s output statistics from the statistics of a truly random bit source when the device can be modeled as an ergodic stationary source with finite memory but arbitrary (unknown) state transition probabilities. The test parameter is closely related to the device’s per-bit entropy which is shown to be the correct quality measure for a secret-key source in a cryptographic application. The test hence measures the cryptographic badness of a device’s possible defect. The test is easy to implement and very fast and thus well suited for practical applications. A simple program listing is provided. Cited in 4 ReviewsCited in 23 Documents MSC: 94A60 Cryptography 62P99 Applications of statistics Keywords:entropy; exhaustive key search; statistical test for random bit generators; ergodic stationary source; cryptographic application PDFBibTeX XMLCite \textit{U. M. Maurer}, J. Cryptology 5, No. 2, 89--105 (1992; Zbl 0790.94014) Full Text: DOI References: [1] Beker, H.; Piper, F., Cipher Systems (1982), London: Northwood Books, London · Zbl 0502.94001 [2] Blahut, R. E., Principles and Practice of Information Theory (1987), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0681.94001 [3] Dudewicz, E. J.; van der Meulen, E. C., Entropy-based tests of uniformity, Journal of the American Statistical Association, 76, 376, 967-974 (1981) · Zbl 0484.62035 [4] Elias, P., Interval and recency rank source coding: Two on-line adaptive variable-length schemes, IEEE Transactions on Information Theory, 33, 3-10 (1987) · Zbl 0628.94010 [5] Feller, W., An Introduction to Probability Theory and Its Applications (1968), New York: Wiley, New York · Zbl 0155.23101 [6] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0426.68001 [7] Knuth, D. E., The Art of Computer Programming, vol. 2 (1981), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0477.65002 [8] Kolmogorov, A. N., Three approaches to the quantitative definition of information, Problemy Peredachi Informatsii, 1, 1, 3-11 (1965) · Zbl 0271.94018 [9] Martin-Löf, P., The definition of random sequences, Information and Control, 9, 602-619 (1966) · Zbl 0244.62008 [10] Massey, J. L., An introduction to contemporary cryptology, Proceedings of the IEEE, 76, 5, 533-549 (1988) [11] Shannon, C. E., A mathematical theory of communication, Bell System Technical Journal, 27, 379-423 (1948) · Zbl 1154.94303 [12] Willems, F. M. J., Universal data compression and repetition times, IEEE Transactions on Information Theory, 35, 54-58 (1989) · Zbl 0671.94005 [13] Wozencraft, J. M.; Reiften, B., Sequential Decoding (1960), Cambridge, MA: Technical Press of the M.I.T., Cambridge, MA [14] Ziv, J.; Capocelli, R. M., Compression tests for randomness and estimating the statistical model of an individual sequence, Sequences, 366-373 (1990), Berlin: Springer-Verlag, Berlin · Zbl 0691.94002 [15] Ziv, J.; Lempel, A., A universal algorithm for sequential data compression, IEEE Transactions on Information Theory, 23, 337-343 (1977) · Zbl 0379.94010 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.