Paper 2024/722
Ultrametric integral cryptanalysis
Abstract
A systematic method to analyze divisibility properties is proposed. In integral cryptanalysis, divisibility properties interpolate between bits that sum to zero (divisibility by two) and saturated bits (divisibility by $2^{n - 1}$ for $2^n$ inputs). From a theoretical point of view, we construct a new cryptanalytic technique that is a non-Archimedean multiplicative analogue of linear cryptanalysis. It lifts integral cryptanalysis to characteristic zero in the sense that, if all quantities are reduced modulo two, then one recovers the algebraic theory of integral cryptanalysis. The new technique leads to a theory of trails. We develop a tool based on off-the-shelf solvers that automates the analysis of these trails and use it to show that many integral distinguishers on PRESENT and SIMON are stronger than expected.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2024
- Keywords
- Geometric approachIntegral cryptanalysisDivision property
- Contact author(s)
-
tim beyne @ esat kuleuven be
michiel verbauwhede @ esat kuleuven be - History
- 2024-09-10: revised
- 2024-05-10: received
- See all versions
- Short URL
- https://ia.cr/2024/722
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/722,
author = {Tim Beyne and Michiel Verbauwhede},
title = {Ultrametric integral cryptanalysis},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/722},
year = {2024},
url = {https://eprint.iacr.org/2024/722}
}