Integral cryptanalysis in characteristic $p$

Tim Beyne; Michiel Verbauwhede

Paper 2025/932

Integral cryptanalysis in characteristic $p$

Tim Beyne

, KU Leuven

Michiel Verbauwhede

, KU Leuven

Abstract

Integral and ultrametric integral cryptanalysis are generalized to finite rings of prime characteristic $p$ that are isomorphic to a product of fields. This extends, for instance, the complete state of the art in integral cryptanalysis from $\mathbf{F}_2^n$ to $\mathbf{F}_q^n$, for all prime powers $q$. A compact representation of transition matrices, based on convex polyhedra, is introduced to ensure that the proposed methods are computationally efficient even for large $p$. Automated tools are developed and applied to a few generic and several concrete primitives. The analysis shows that previous degree estimates for Feistel-GMiMC, HadesMiMC, AES-Prime, small-pSquare and mid-pSquare are overly optimistic. Furthermore, except for AES-Prime, these primitives do not meet their design criteria unless their number of rounds is substantially increased.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: A minor revision of an IACR publication in ASIACRYPT 2025
Keywords: Geometric approach Integral cryptanalysis Ultrametric integral cryptanalysis Arithmetization-oriented primitives
Contact author(s): tim beyne @ esat kuleuven be
michiel verbauwhede @ esat kuleuven be
History: 2025-08-26: revised; 2025-05-22: received; See all versions
Short URL: https://ia.cr/2025/932
License: CC BY

BibTeX

@misc{cryptoeprint:2025/932,
      author = {Tim Beyne and Michiel Verbauwhede},
      title = {Integral cryptanalysis in characteristic $p$},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/932},
      year = {2025},
      url = {https://eprint.iacr.org/2025/932}
}