×

The strict avalanche criterion randomness test. (English) Zbl 1096.62005

Summary: A new statistical test for randomness, the strict avalanche criterion (SAC) test, is presented, together with its results over some well-known generators in the literature. These results are analyzed and some possible applications of the test, as for measuring the strength of cryptographic primitives including block ciphers, stream ciphers and pseudorandom number generators, especially during the design and analysis phase, are detailed. Finally, the source code for a basic version of the SAC test is provided, which proves some of its other advantages: it is easy to implement, and very fast and well-suited for practical applications.

MSC:

62B10 Statistical aspects of information-theoretic topics
65C10 Random number generation in numerical analysis
62G10 Nonparametric hypothesis testing

Software:

Diehard
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A.L. Rukhin, Testing randomness: a suite of statistical procedures. SIAM J. Theory Probability Appl. (45) 2000.; A.L. Rukhin, Testing randomness: a suite of statistical procedures. SIAM J. Theory Probability Appl. (45) 2000. · Zbl 1171.62329
[2] Maurer, U. M., A universal statistical test for random bit generators, (Menezes, A. J.; Vanstone, S. A., Advances in Cryptology-Crypto’90 (1991), Springer-Verlag: Springer-Verlag New York), pp. 409-420 · Zbl 0789.62005
[3] Knuth, D. E., The Art of Computer Programming, 2 (1997), Prentice Hall PTR · Zbl 0191.17903
[4] G, Marsaglia. Diehard: a battery of tests for randomness. http://stat.fsu.edu/ geo/diehard.html, 1996.; G, Marsaglia. Diehard: a battery of tests for randomness. http://stat.fsu.edu/ geo/diehard.html, 1996.
[5] J. Soto. Statistical testing of random number generators, in: Proceedings of the 22nd National Information Systems Security Conference, 1999.; J. Soto. Statistical testing of random number generators, in: Proceedings of the 22nd National Information Systems Security Conference, 1999.
[6] G. Marsaglia, T. Wai Wan, Some difficult-to-pass tests of randomness, J Sta. Software, 7(3) (2002).; G. Marsaglia, T. Wai Wan, Some difficult-to-pass tests of randomness, J Sta. Software, 7(3) (2002).
[7] Center for Information Security and Cryptography (CISC), Library of Tests for Random Number Generators at http://www.csis.hku.hk/cisc/download/idetect/.; Center for Information Security and Cryptography (CISC), Library of Tests for Random Number Generators at http://www.csis.hku.hk/cisc/download/idetect/.
[8] J.S. Coron, D. Naccache, An accurate evaluation of Maurer’s universal test, in: Proceedings of SAC’98 (Lecture Notes in Computer Science), Springer-Verlag, 1998.; J.S. Coron, D. Naccache, An accurate evaluation of Maurer’s universal test, in: Proceedings of SAC’98 (Lecture Notes in Computer Science), Springer-Verlag, 1998. · Zbl 0929.94006
[9] Forre, R., The strict avalanche criterion: spectral properties of booleans functions and an extended definition. Advances in cryptology, (Goldwasser, S., Crypto’88, Lecture Notes in Computer Science, vol. 403 (1990), Springer-Verlag), pp. 450-468
[10] A. Webster, S. Tavares, On the Design of S-Boxes. Advances in Cryptology, Crypto’85, 198, p. 5.; A. Webster, S. Tavares, On the Design of S-Boxes. Advances in Cryptology, Crypto’85, 198, p. 5.
[11] Feistel, H., Cryptography and computer privacy, Scientific Am., 228, 5, 15-23 (1973)
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.