Paper 2002/030
Adaptive chisquare 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 chisquare test because the sample size must be greater than k. We suggest the adaptive chisquare 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 chisquare 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 chisquare test.
Metadata
 Available format(s)
 PDF PS
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 adaptive testingrandom number testingblock cipher testing
 Contact author(s)
 ryabko @ neic nsk su
 History
 20020308: received
 Short URL
 https://ia.cr/2002/030
 License

CC BY
BibTeX
@misc{cryptoeprint:2002/030, author = {Boris Ryabko}, title = {Adaptive chisquare test and its application to some cryptographic problems.}, howpublished = {Cryptology ePrint Archive, Paper 2002/030}, year = {2002}, note = {\url{https://eprint.iacr.org/2002/030}}, url = {https://eprint.iacr.org/2002/030} }