×

Testing randomness via aperiodic words. (English) Zbl 1169.62097

Summary: The properties of statistical procedures based on occurrences of aperiodic patterns in a random text are summarized. Accurate asymptotic formulas for the expected value of the number of aperiodic words occurring a given number of times and for the covariance matrix are given. The form of the optimal linear test based on these statistics is established. These procedures are applied to testing for the randomness of a string of binary digits originating from block ciphers, US government-approved random number generators or classical transcendental numbers.

MSC:

62P99 Applications of statistics
62E20 Asymptotic distribution theory in statistics
62F03 Parametric hypothesis testing
60F99 Limit theorems in probability theory

Software:

Monobit Test
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Knuth D. E., The Art of Computer Programming 2, 3. ed. (1997) · Zbl 0883.68015
[2] Marsaglia, G. A current view of random number generation. Computer Science and Statistics: Proceedings of the Sixteenth Symposium on the Interface. New York. pp.3–10. Elsevier Science Publishers. · Zbl 0212.18204
[3] DOI: 10.1239/jap/1014842270 · Zbl 1095.65500 · doi:10.1239/jap/1014842270
[4] Barbour A. D., Poisson Approximation (1992) · Zbl 0746.60002
[5] DOI: 10.1089/10665270050081360 · doi:10.1089/10665270050081360
[6] Szpankowski W., Average Case Analysis of Algorithms on Sequences (2001) · Zbl 0968.68205 · doi:10.1002/9781118032770
[7] DOI: 10.1016/0898-1221(93)90001-C · Zbl 0788.65007 · doi:10.1016/0898-1221(93)90001-C
[8] DOI: 10.1239/aap/1037990953 · Zbl 1026.60014 · doi:10.1239/aap/1037990953
[9] Kolchin V. F., Random Allocations (1978) · Zbl 0376.60003
[10] Guibas L. J., Journal of Combinatorial Theory 30 pp 19– (1981) · Zbl 0464.68070 · doi:10.1016/0097-3165(81)90038-8
[11] DOI: 10.1515/dma.1991.1.3.335 · Zbl 0728.62022 · doi:10.1515/dma.1991.1.3.335
[12] Soto, J. and Bassham, L. Randomness testing of the advanced encryption standard finalist candidates. Proceedings of AES Conference. Available online at:http://csrc.nist.gov/publications/nistir/ir6483.pdf
[13] DOI: 10.1063/1.1809295 · doi:10.1063/1.1809295
[14] Jakobsson, M., Shriver, E., Hillyer, B. K. and Juels, A. A practical secure physical random bit generator. Proceedings of the Fifth ACM Conference on Computer and Communications Security. San Francisco.
[15] American Bankers Association, 1998, Public key cryptography for the financial services industry: the elliptic curve digital signature algorithm (ECDSA), Annex A.4. ANSI X9.62
[16] National Institute of Standards and Technology, 2000, Digital signature standard (DSS), Appendices 3.1 and 3.2, Federal Information Processing Standards Publication 186-2. Available online at:http://csrc.nist.gov/publications/fips/fips186-2/fips186-2-changel.pdf
[17] National Institute of Standards and Technology, 2005, Using the 3-key triple DES and AES algorithms, NIST-Recommended Random Number Generator Based on ANSI X9.31, Appendix A.2.4. Available online at:http://csrc.nist.gov/cryptval/rng/931rngext.pdf
[18] Pincus, S. and Kalman, R. E. Not all (possibly) ’random’ sequences are created equal. Proceedings of the National Academy of Sciences of the United States of America. Vol. 94, pp.3513–3518. · Zbl 0873.11047
[19] Good I. J., Journal of Royal Statistical Society 130 pp 102– (1967) · doi:10.2307/2344040
[20] Rukhin A. L., NIST Special Publication 800-22 (2000)
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.