×

A universal statistical test for random bit generators. (English) Zbl 0790.94014

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.

MSC:

94A60 Cryptography
62P99 Applications of statistics
PDFBibTeX XMLCite
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.