Welcome to the resource topic for
**2002/030**

**Title:**

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

**Authors:**
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.

**ePrint:**
https://eprint.iacr.org/2002/030

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .