CryptoDB
Improved Resultant Attack against Arithmetization-Oriented Primitives
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | In the last decade, the introduction of advanced crypto- graphic protocols operating on large finite fields F_q has raised the need for efficient cryptographic primitives in this setting, commonly referred to as Arithmetization-Oriented (AO). The cryptanalysis of AO hash functions is essentially done through the study of the CICO problem on the underlying permutation. Two recent works at Crypto 2024 and Asiacrypt 2024 managed to solve the CICO problem much more efficiently than traditional Gröbner basis methods, respectively using advanced Gröbner basis techniques and resultants. In this paper, we propose an attack framework based on resultants that applies to a wide range of AO permutations and improves significantly upon these two recent works. Our improvements mainly come from an efficient reduction procedure that we propose and rigorously analyze, taking advantage of fast multivariate multiplication. We present the most efficient attacks on Griffin, Arion, Anemoi, and Rescue. We show that most variants of Griffin, Arion and Anemoi fail to reach the claimed security level. For the first time, we successfully break a parameter set of Rescue, namely the 512-bit security in 2^{475}. The presented theory and complexity estimates are backed up with experimental attacks. Notably, we practically find CICO solutions for 8 out of 10 rounds of Griffin, and 11 out of 20 rounds of Anemoi, and 6 out of 18 rounds of Rescue, improving by respectively 1, 3 and 1 rounds on the previous best practical attacks. |
BibTeX
@inproceedings{crypto-2025-35716,
title={Improved Resultant Attack against Arithmetization-Oriented Primitives},
publisher={Springer-Verlag},
author={Augustin Bariant and Aurélien Boeuf and Pierre Briaud and Maël Hostettler and Morten Øygarden and Håvard Raddum},
year=2025
}