A new test for randomness and its application to some cryptographic problems

✍ Scribed by B.Ya. Ryabko; V.S. Stognienko; Yu.I. Shokin

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 237 KB
• Volume: 123
• Category: Article
• ISSN: 0378-3758
• DOI: 10.1016/s0378-3758(03)00149-6

✦ Synopsis

We consider the problem of testing the hypothesis H0 that the letters from some alphabet A = {a1; a2; : : : ; a k } obey the uniform distribution, when k is large. The problem is of interest for random number testing and some cryptographic applications where k = 2 10 ∼ 2 30 and greater. In such a case it is di cult to use the well-known chi-square test since the sample size for it must be greater than k.

We suggest an adaptive chi-square test which can be successfully applied for testing some kinds of H1 even if the sample size is much smaller than k. This statement is proved theoretically and conÿrmed experimentally.