## Cryptology ePrint Archive: Report 2002/030

**Adaptive chi-square test and its application to some cryptographic problems.**

*Boris Ryabko*

**Abstract: **We address the problem of testing the hypothesis H_0 that the
letters from some alphabet A= {a_1,a_2,..., a_k }, are
distributed uniformly
against the alternative hypothesis H_1 that the true
distribution is not uniform, in case k is large. (It is typical
for random number testing and some cryptographic problems where
k= 2^{10} - 2^{30} and more). In such
a case it is difficult to use the chi-square test because the
sample size must be greater than k.

We suggest the adaptive chi-square test which can be
successfully applied for testing some kinds of H_1 even in case
when the sample size is much less than k. This statement is
confirmed theoretically and experimentally. The theoretical proof
is based on the consideration of one kind of the alternative
hypothesis H_1 where the suggested test rejects the null
hypothesis when the sample size is O( \sqrt{k} ) (instead of
const k for the usual chi-square test ).

For experimental
investigation of the suggested test we consider a problem of
testing ciphered Russian texts. It turns out that the suggested
test can distinguish the ciphered texts from random sequences
basing on a sample which is much smaller than that required for the
usual chi-square test.

**Category / Keywords: **secret-key cryptography / adaptive testing, random number testing, block cipher testing

**Date: **received 8 Mar 2002

**Contact author: **ryabko at neic nsk su

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Version: **20020308:201111 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]