Cryptology ePrint Archive: Report 2015/916

Rigorous Upper Bounds on Data Complexities of Block Cipher Cryptanalysis

Subhabrata Samajder and Palash Sarkar

Abstract: All statistical analysis of symmetric key attacks use the central limit theorem to approximate the distribution of a sum of random variables using the normal distribution. Expressions for data complexity using such an approach are {\em inherently approximate}. 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 differetial cryptanalysis, the Chernoff bound is used. For the cases of multiple linear and multiple differential cryptanalysis, the theory of martingales is required. A Doob martingale satisfying the Lipschitz condition is set up so that the Azuma-Hoeffding inequality can be applied. 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 have much wider applicability.

Category / Keywords: secret-key cryptography / block cipher, linear cryptanalysis, differential cryptanalysis, log-likelihood test, order statistics, normal distribution, hypothesis testing, Chernoff bound, Martingales, Lipschitz condition, Azuma-Hoeffding inequality.

Date: received 21 Sep 2015

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

Available format(s): PDF | BibTeX Citation

Version: 20150922:205854 (All versions of this report)

Short URL: ia.cr/2015/916

Discussion forum: Show discussion | Start new discussion