Links among impossible differential, integral and zero correlation linear cryptanalysis

Bing Sun, Zhiqiang Liu, Vincent Rijmen, Ruilin Li, Lei Cheng, Qingju Wang, Hoda A. Alkhzaimi, Chao Li

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


As two important cryptanalytic methods, impossible differential and integral cryptanalysis have attracted much attention in recent years. Although relations among other cryptanalytic approaches have been investigated, the link between these two methods has been missing. The motivation in this paper is to fix this gap and establish links between impossible differential cryptanalysis and integral cryptanalysis. Firstly, by introducing the concept of structure and dual structure, we prove that a → b is an impossible differential of a structure E if and only if it is a zero correlation linear hull of the dual structure E⊥. Meanwhile, our proof shows that the automatic search tool presented by Wu and Wang could find all impossible differentials of both Feistel structures with SP-type round functions and SPN structures. Secondly, by establishing some boolean equations, we show that a zero correlation linear hull always indicates the existence of an integral distinguisher. With this observation we improve the number of rounds of integral distinguishers of Feistel structures, CAST-256, SMS4 and Camellia. Finally, we conclude that an r-round impossible differential of E always leads to an r-round integral distinguisher of the dual structure ɛ⊥. In the case that ɛ and ɛ⊥ are linearly equivalent, we derive a direct link between impossible differentials and integral distinguishers of ɛ. Our results could help to classify different cryptanalytic tools and facilitate the task of evaluating security of block ciphers against various cryptanalytic approaches.
Original languageEnglish
Title of host publicationCRYPTO 2015 : Proceedings of the 35th Annual Cryptology Conference
Publication date2015
ISBN (Print)9783662479889
Publication statusPublished - 2015
SeriesLecture Notes in Computer Science


  • Computer Science (all)
  • Theoretical Computer Science
  • ARIA
  • Camellia
  • CAST-256
  • Feistel
  • Impossible differential
  • Integral
  • SMS4
  • SPN
  • Zero correlation linear
  • Boolean algebra
  • Gears
  • Lyapunov methods
  • Zero correlation
  • Cryptography

Cite this

Sun, B., Liu, Z., Rijmen, V., Li, R., Cheng, L., Wang, Q., Alkhzaimi, H. A., & Li, C. (2015). Links among impossible differential, integral and zero correlation linear cryptanalysis. In CRYPTO 2015: Proceedings of the 35th Annual Cryptology Conference (Vol. 9215, pp. 95-115). Springer. Lecture Notes in Computer Science, Vol.. 9215