We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Another look at normal approximations in cryptanalysis.
- Authors
Samajder, Subhabrata; Sarkar, Palash
- Abstract
Statistical analysis of attacks on symmetric ciphers often requires assuming the normal behaviour of a test statistic. Typically such an assumption is made in an asymptotic sense. In this work, we consider concrete versions of some important normal approximations that have been made in the literature. To do this, we use the Berry-Esséen theorem to derive explicit bounds on the approximation errors. A basic mathematical requirement is that such approximation errors should be within reasonable bounds, a point which appears to have been overlooked in many of the earlier works on statistical aspects of cryptanalysis. Interpreting the error bounds in the cryptanalytic context yields several surprising results. One important implication is that this puts in doubt the applicability of the order statistics based approach for analysing key recovery attacks on block ciphers. This approach has been earlier used to obtain several results on the data complexities of (multiple) linear and differential cryptanalysis. The non-applicability of the order statistics based approach puts a question mark on the data complexities obtained using this approach. Fortunately, we are able to recover all of these results by utilising the hypothesis testing framework. This, however, necessitates using normal approximations for the χ² and the LLR test statistics considered in earlier works. These approximations themselves have issues which seem to be difficult to resolve satisfactorily. More generally, the message of our work is that all cryptanalytic attacks should properly derive and interpret the error bounds for any (normal) approximation that is made.
- Subjects
CIPHERS; CRYPTOGRAPHY research; GAUSSIAN distribution; MATHEMATICS theorems; ORDER statistics
- Publication
Journal of Mathematical Cryptology, 2016, Vol 10, Issue 2, p69
- ISSN
1862-2976
- Publication type
Article
- DOI
10.1515/jmc-2016-0006