Cryptology ePrint Archive: Report 2015/183

New Links Between Differential and Linear Cryptanalysis

Céline Blondeau and Kaisa Nyberg

Abstract: Recently, a number of relations have been established among previously known statistical attacks on block ciphers. Leander showed in 2011 that statistical saturation distinguishers are on average equivalent to multidimensional linear distinguishers. Further relations between these two types of distinguishers and the integral and zero-correlation distinguishers were established by Bogdanov et al.. Knowledge about such relations is useful for classification of statistical attacks in order to determine those that give essentially complementary information about the security of block ciphers. The purpose of the work presented in this paper is to explore relations between differential and linear attacks. The mathematical link between linear and differential attacks was discovered by Chabaud and Vaudenay already in 1994, but it has never been used in practice. We will show how to use it for computing accurate estimatesof truncated differential probabilities from accurate estimates of correlations of linear approximations. We demonstrate this method in practice and give the first instantiation of multiple differential cryptanalysis using the LLR statistical test on PRESENT. On a more theoretical side,we establish equivalence between a multidimensional linear distinguisher and a truncated differential distinguisher, and show that certain zero-correlation linear distinguishers exist if and only if certain impossible differentials exist.

Category / Keywords: secret-key cryptography / statistical cryptanalysis, block cipher, key-alternating block cipher, multiple differential attack, truncated differential, multidimen- sional linear attack, zero-correlation, impossible differential

Original Publication (in the same form): IACR-EUROCRYPT-2013

Date: received 2 Mar 2015

Contact author: celine blondeau at aalto fi

Available format(s): PDF | BibTeX Citation

Version: 20150304:163440 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]