Paper 2025/2040

The Algebraic CheapLunch: Extending FreeLunch Attacks on Arithmetization-Oriented Primitives Beyond CICO-1

Abstract

The security of many arithmetization-oriented (AO) hash functions depends of the hardness of Constrained-input constrained-output (CICO) problems. These problems have received significant attention from the cryptographic community in recent years, with notable advances in Gröbner basis and resultant-based attacks, yet progress has mainly been limited to CICO problems restricted to a single output. In this work, we build on the "FreeLunch method" of Bariant et al. (Crypto 2024) that constructs Gröbner bases "for free" in this particular case, and extend it to CICO problems with multiple outputs. More precisely, we consider tools for solving weighted polynomial systems, and show how to apply them in the AO setting. This results in new polynomial modelings, more efficient methods for computing the initial Gröbner basis under certain assumptions, and improved complexity estimates for the change of ordering step, derived from tighter upper bounds on the ideal degree. We apply our framework to Poseidon, Neptune and XHash8, where our assumptions are experimentally verified, and theory matches practice. For Griffin and ArionHash our assumptions are not verified, leaving us with improved, yet loose, upper bounds on the ideal degree. While our results do not threaten the security of any full-round hash function, they provide new insights into the security of these primitives under more general CICO problems.