RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Probl. Peredachi Inf.: Year: Volume: Issue: Page: Find

 Probl. Peredachi Inf., 2003, Volume 39, Issue 2, Pages 53–62 (Mi ppi301)

Methods of Signal Processing

Adaptive $\chi^2$ Criterion for Discrimination of Near Hypotheses with a Large Number of Classes and Its Application to Some Cryptography Problems

B. Ya. Ryabko, V. S. Stognienko, Yu. I. Shokin

Abstract: The main problem considered consists in testing the hypothesis $H_0$ that letters of an alphabet $A=\{a_1,a_2,…,a_k\}$ are generated with equal probabilities $\frac{1}{k}$ against the alternative complex hypothesis $H_1$, the negation of $H_0$. In many applications, in particular, those connected with cryptography, $k$ is large, but possible deviations from the uniform distribution are small. Therefore, application of Pearson's $\chi_2$ test, which is one of the most wide-spread and efficient tests, requires samples of a very large size, certainly exceeding $k$. We propose a so-called adaptive $\chi_2$ test, whose power can be considerably higher than that of the traditional method in the case described. This conclusion is based on the theoretical analysis of the proposed criterion for some classes of alternatives as well as on experimental results related to discriminating between enciphered Russian texts and random sequences.

Full text: PDF file (1040 kB)
References: PDF file   HTML file

English version:
Problems of Information Transmission, 2003, 39:2, 207–215

Bibliographic databases:

UDC: 621.391.1:519.27

Citation: B. Ya. Ryabko, V. S. Stognienko, Yu. I. Shokin, “Adaptive $\chi^2$ Criterion for Discrimination of Near Hypotheses with a Large Number of Classes and Its Application to Some Cryptography Problems”, Probl. Peredachi Inf., 39:2 (2003), 53–62; Problems Inform. Transmission, 39:2 (2003), 207–215

Citation in format AMSBIB
\Bibitem{RyaStoSho03} \by B.~Ya.~Ryabko, V.~S.~Stognienko, Yu.~I.~Shokin \paper Adaptive $\chi^2$ Criterion for Discrimination of Near Hypotheses with a Large Number of Classes and Its Application to Some Cryptography Problems \jour Probl. Peredachi Inf. \yr 2003 \vol 39 \issue 2 \pages 53--62 \mathnet{http://mi.mathnet.ru/ppi301} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2105861} \zmath{https://zbmath.org/?q=an:1130.62331} \transl \jour Problems Inform. Transmission \yr 2003 \vol 39 \issue 2 \pages 207--215 \crossref{https://doi.org/10.1023/A:1025104406075} 

• http://mi.mathnet.ru/eng/ppi301
• http://mi.mathnet.ru/eng/ppi/v39/i2/p53

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. B. Ya. Ryabko, A. I. Pestunov, ““Book Stack” as a New Statistical Test for Random Numbers”, Problems Inform. Transmission, 40:1 (2004), 66–71
2. B. Ya. Ryabko, V. A. Monarev, Yu. I. Shokin, “A New Type of Attacks on Block Ciphers”, Problems Inform. Transmission, 41:4 (2005), 385–394
•  Number of views: This page: 419 Full text: 141 References: 42 First page: 2