Cryptology ePrint Archive: Report 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.

Category / Keywords: block cipher, linear cryptanalysis, differential cryptanalysis, log-likelihood ratio test, hypothesis testing, Chernoff bound, Hoeffding's inequality.

Date: received 21 Sep 2015, last revised 14 Jun 2016

Contact author: subhabrata samajder at gmail com; palash sarkar@gmail com;

Available format(s): PDF | BibTeX Citation

Version: 20160614:114625 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]