Paper 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2013
Keywords
statistical cryptanalysisblock cipherkey-alternating block ciphermultiple differential attacktruncated differentialmultidimen- sional linear attackzero-correlationimpossible differential
Contact author(s)
celine blondeau @ aalto fi
History
2015-03-04: received
Short URL
https://ia.cr/2015/183
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/183,
      author = {Céline Blondeau and Kaisa Nyberg},
      title = {New Links Between Differential and Linear Cryptanalysis},
      howpublished = {Cryptology ePrint Archive, Paper 2015/183},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/183}},
      url = {https://eprint.iacr.org/2015/183}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.