Integral Cryptanalysis Using Algebraic Transition Matrices

Tim Beyne; Michiel Verbauwhede

Paper 2023/1907

Integral Cryptanalysis Using Algebraic Transition Matrices

Tim Beyne

, KU Leuven

Michiel Verbauwhede

, KU Leuven

Abstract

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.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published by the IACR in TOSC 2023
DOI: 10.46586/tosc.v2023.i4.244-269
Keywords: Integral Cryptanalysis Division Property Nonlinear Invariants ANF Change-of-Basis Algebraic Transition Matrices
Contact author(s): tim beyne @ esat kuleuven be
michiel verbauwhede @ esat kuleuven be
History: 2023-12-15: approved; 2023-12-12: received; See all versions
Short URL: https://ia.cr/2023/1907
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1907,
      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{https://eprint.iacr.org/2023/1907}},
      url = {https://eprint.iacr.org/2023/1907}
}