Paper 2023/1907

Integral Cryptanalysis Using Algebraic Transition Matrices

Tim Beyne, KU Leuven
Michiel Verbauwhede, KU Leuven

In this work we introduce algebraic transition matrices as the basis for a new approach to integral cryptanalysis that unifies monomial trails (Hu et al., Asiacrypt 2020) and parity sets (Boura and Canteaut, Crypto 2016). Algebraic transition matrices allow for the computation of the algebraic normal form of a primitive based on the algebraic normal forms of its components by means of well-understood operations from linear algebra. The theory of algebraic transition matrices leads to better insight into the relation between integral properties of $F$ and $F^{−1}$. In addition, we show that the link between invariants and eigenvectors of correlation matrices (Beyne, Asiacrypt 2018) carries over to algebraic transition matrices. Finally, algebraic transition matrices suggest a generalized definition of integral properties that subsumes previous notions such as extended division properties (Lambin, Derbez and Fouque, DCC 2020). On the practical side, a new algorithm is described to search for these generalized properties and applied to Present, resulting in new properties. The algorithm can be instantiated with any existing automated search method for integral cryptanalysis.

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in TOSC 2023
Integral CryptanalysisDivision PropertyNonlinear InvariantsANFChange-of-BasisAlgebraic Transition Matrices
Contact author(s)
tim beyne @ esat kuleuven be
michiel verbauwhede @ esat kuleuven be
2023-12-15: approved
2023-12-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tim Beyne and Michiel Verbauwhede},
      title = {Integral Cryptanalysis Using Algebraic Transition Matrices},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1907},
      year = {2023},
      doi = {10.46586/tosc.v2023.i4.244-269},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.