Paper 2015/916

Rigorous Upper Bounds on Data Complexities of Block Cipher Cryptanalysis

Subhabrata Samajder and Palash Sarkar

Abstract

Statistical analysis of symmetric key attacks aims to obtain an expression for the data complexity which is the number of plaintext-ciphertext pairs needed to achieve the parameters of the attack. Existing statistical analyses invariably use some kind of approximation, the most common being the approximation of the distribution of a sum of random variables by a normal distribution. Such an approach leads to expressions for data complexities which are {\em inherently approximate}. Prior works do not provide any analysis of the error involved in such approximations. In contrast, this paper takes a rigorous approach to analysing attacks on block ciphers. In particular, no approximations are used. Expressions for upper bounds on the data complexities of several basic and advanced attacks are obtained. The analysis is based on the hypothesis testing framework. Probabilities of Type-I and Type-II errors are upper bounded using standard tail inequalities. In the cases of single linear and differential cryptanalysis, we use the Chernoff bound. For the cases of multiple linear and multiple differential cryptanalysis, Hoeffding bounds are used. This allows bounding the error probabilities and obtaining expressions for data complexities. We believe that our method provides important results for the attacks considered here and more generally, the techniques that we develop should have much wider applicability.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
block cipherlinear cryptanalysisdifferential cryptanalysislog-likelihood ratio testhypothesis testingChernoff boundHoeffding's inequality.
Contact author(s)
subhabrata samajder @ gmail com
palash sarkar @ gmail com
History
2016-06-14: revised
2015-09-22: received
See all versions
Short URL
https://ia.cr/2015/916
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/916,
      author = {Subhabrata Samajder and Palash Sarkar},
      title = {Rigorous Upper Bounds on Data Complexities of Block Cipher Cryptanalysis},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/916},
      year = {2015},
      url = {https://eprint.iacr.org/2015/916}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.