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

Abstract

The security of many arithmetization-oriented (AO) hash functions depends on 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.

Keywords: Gröbner basis · Hash function · Poseidon · XHash · ArionHash · Griffin

1. Introduction

The increasing deployment of practical zero-knowledge (ZK) proof protocols has created a need for hash functions that allow a preimage to be proven efficiently using the corresponding proof system. The construction of these hash functions depends a lot on the cost model of the target proof system. In general, a requirement is that the round functions of the permutation can be verified using a low-degree function, hence the name Arithmetization-Oriented (AO). This can be achieved by having the entire round function be of low degree, such as in Poseidon [GKR+21] and Neptune [GOPL22], or by including operations that have a low degree inverse, such as in Anemoi [BBP+23], XHash [ABK+23], Griffin [GHR+23], and ArionHash [RST23]. Due to their inherent algebraic structure, algebraic attacks (especially Gröbner basis attacks) are often the main attack vector against these hash functions.

AO hash functions are typically constructed by first designing a permutation F: \mathbb{F}_p^t \longrightarrow \mathbb{F}_p^t and then using it in a sponge construction [BDPA08]. By their very nature, the security of hash functions in sponge constructions is directly dependent on the difficulty of solving the Constrained-Input Constrained-Output (CICO) problem for the underlying permutation. The abovementioned algebraic attacks generally proceed by modeling this CICO problem as a multivariate polynomial system, and then find its solution(s).

Previous works. In the CICO-1 setting, several works have already been able to leverage the structure of the input modeling to obtain more efficient attacks, for instance, by choosing a custom ordering for which this modeling is already a Gröbner basis [BBO+24] and/or by using resultants for variable elimination [47, 8]. While these approaches have been very successful for CICO-k problems with k = 1, it is unclear whether they can be extended to larger values of k. The case of k > 1 has received much less attention from the cryptographic community.

Our results. In this work, the authors propose an extension of the FreeLunch approach of [BBO+24] to the k > 1 case, referred to as the “CheapLunch” approach. In particular, they give a general framework allowing them to model primitives in such a way that, under some genericity assumptions and for a custom monomial ordering, a Gröbner basis of the modeling can be computed efficiently (though not quite “for free”). This transfers the bottleneck for Gröbner basis attacks from the Gröbner basis computation step to the change-of-ordering step. The framework is applied to Poseidon, Neptune, XHash8, Griffin, and ArionHash, with results summarized in Table 1 of the paper.

2. Preliminaries

2.1 CICO Problem

The main focus of this work is the analysis of AO hash functions using the sponge construction [BDPA08]. These sponges are typically instantiated via AO permutations F: \mathbb{F}_q^t \to \mathbb{F}_q^t (where \mathbb{F}_q is a finite field). A crucial security requirement for these constructions is for the underlying permutation to be secure with respect to the CICO problem.

When \text{IN} = \text{OUT} = k, the notation CICO-k is used. The majority of recent algebraic cryptanalyses focuses on CICO-1, with the exception of [CR25] for Anemoi. This work tackles the general CICO-(IN,OUT) problem with \text{IN} \geq 2 and \text{OUT} \geq 2 for various permutations.

2.2 Polynomial System Solving via Gröbner Bases

Let \{P_1, \ldots, P_m\} \subset \mathbb{F}[x_1, \ldots, x_n] be a polynomial system over a field \mathbb{F} and let I = \langle P_1, \ldots, P_m \rangle be its associated ideal. A monomial ordering is a well-order on \mathbb{N}^n such that if \alpha \prec \beta, then \alpha + \gamma \prec \beta + \gamma. Three orderings are used: lexicographical (lex), weighted graded reverse lexicographical (wgrevlex), and graded reverse lexicographical (grevlex).

The main steps of solving a zero-dimensional ideal I are: (1) find a Gröbner basis for a suitable monomial order, (2) convert it into a lex-order Gröbner basis, and (3) solve the univariate polynomial G_n and recover the solutions.

2.3 Gröbner Bases for Weighted Homogeneous Systems

The approach makes use of a tailored wgrevlex ordering for the first Gröbner basis computation. For weighted homogeneous systems, the algorithms of [25, 26] have been adapted by observing that for any polynomial P that is homogeneous with respect to w, the polynomial \mathrm{hom}_w(P) := P(x_1^{w_1}, \ldots, x_n^{w_n}) is homogeneous in the usual sense.

The complexity of computing a wgrevlex Gröbner basis for a weighted homogeneous system \mathcal{P} of m polynomials in n variables is estimated by

where 2 \leq \omega \leq 3 is the linear algebra constant.

For a regular sequence, the weighted degree of regularity can be upper bounded by the weighted Macaulay bound:

2.4 Ideal Degree for Weighted Homogeneous Systems

For weighted homogeneous systems, the ideal degree can be upper bounded using the weighted Bézout bound:

3. The CheapLunch Framework for Solving CICO-k

The CICO modeling considered is akin to that of [7, Section 3]. The rationale behind the approach is to pick a certain weighted monomial order for which the first Gröbner basis computation can be precisely analyzed for several ciphers, and which allows tighter upper bounds on the ideal degree.

To find a first Gröbner basis, this order effectively splits the modeling into two parts: one part \mathcal{Q} for which a Gröbner basis G(\mathcal{Q}) will be computed, and one part \mathcal{P} whose leading monomials will be coprime to those of G(\mathcal{Q}), whenever \mathcal{Q}^{\text{top}} is regular.

3.1 Toy Example

The paper illustrates the approach with a toy example, solving the CICO-(IN,OUT) problem for an AO permutation F: \mathbb{F}^t \to \mathbb{F}^t of the form F = A_r \circ S \circ A_{r-1} \circ S \circ \cdots \circ S \circ A_0. The modeling symbolically evaluates the permutation round by round, introducing new y-variables and equations to circumvent the large degree caused by inverse power maps. The construction yields a system of k + r polynomials that can be divided into round polynomials \mathcal{P} and output constraints \mathcal{Q}.

The key idea from [BBO+24] is to choose a weighted order in which y_i^{\alpha} is the leading term of P_i. When k = 1, this corresponds to the FreeLunch setting. When k \geq 2, one can no longer directly apply the same reasoning, but the approach can be adapted whenever the system \mathcal{Q}^{\text{top}} is regular.

3.2 Gröbner Bases for Regular CheapLunch Systems

The proof works by showing that \mathrm{LM}(h) \in \langle \mathrm{LM}(\sum_{j=1}^{m} f_{ij} Q_j) \mid 1 \leq i \leq g \rangle for any element h \in I, distinguishing two cases based on whether the leading monomial of h matches that of its top-homogeneous part.

3.3 Gröbner Basis Computation Procedure

Lemma 1 and Proposition 1 suggest a natural computation procedure for a regular CheapLunch system \{\mathcal{P}, \mathcal{Q}\}: (1) compute a Gröbner basis for \mathcal{Q}^{\mathrm{top}} over the subring \mathbb{F}[x_1, \ldots, x_m], (2) lift it to a Gröbner basis for \mathcal{Q} by multiplying with the original polynomials, and (3) return G(\mathcal{Q}) \cup \mathcal{P}.

3.4 Complexity Estimates

Step 1 consists of computing a Gröbner basis of \mathcal{Q}^{\mathrm{top}}, a homogeneous system of m equations in m variables, with complexity:

Step 2 performs polynomial multiplications, using multivariate multiplication (Theorem 3) with complexity:

The cost of Step 1 does not depend on \prod_{j=1}^{n} \alpha_j, while Step 2 only grows linearly. This is in contrast to the change of ordering step, whose cost grows with (\prod_{j=1}^{n} \alpha_j)^{\omega}, transferring the bottleneck to that step.

3.5 Change of Ordering Step

The cost of the change of ordering is polynomial in D_I. Using the FGLM approach and under the stability and SNP assumptions, the computation of all multiplication matrices has complexity:

Using fast linear algebra [FGHR13], the complexity for CLS is:

The Hermite Normal Form (HNF) algorithm [BNS22] provides the characteristic polynomial in time:

A conservative estimate (from a designer’s point of view, with \omega = 2) yields a lower bound:

4. Primitives with Regular CheapLunch Systems

The framework of Section 3 is now applied to CheapLunch systems arising from AO hash functions whose \mathcal{Q}^{\mathrm{top}} part is assumed to be regular, as verified from Hilbert series experiments.

4.1 XHash8

XHash8 [ABK+23] is a permutation derived from Rescue-Prime Optimized (RPO) [AKM+22] defined over \mathbb{F}_p^{12}, where p is the Goldilocks prime 2^{64} - 2^{32} + 1. It is designed for a sponge construction with rate 8 and capacity 4. The particularity of XHash8 is that some of its nonlinear layers are partial: they only activate 8 out of 12 branches.

The full system is a CheapLunch system with ideal degree bound:

and weighted degree of regularity:

4.2 Poseidon and Neptune

Both primitives are defined as a composition of full rounds \mathcal{E}^{(i)} and partial rounds \mathcal{I}^{(j)}. A polynomial modeling of the CICO-(t-k, k) problem is defined using k + R_P variables and a weight vector:

The system has a CheapLunch structure. The weighted degree of regularity satisfies:

The ideal degree satisfies the weighted Bézout bound:

The section also includes detailed comparisons to previous cryptanalysis work [3, 36] and the designers’ analysis. The CheapLunch approach provides lower ideal degree bounds and transfers the bottleneck from Gröbner basis computation to the change-of-ordering step. No attacks are found on full Poseidon with its security margin for realistic security levels (80 \leq \lambda \leq 256).

4.3 Neptune in Compression Mode

Neptune in compression mode is defined as \mathbf{x} \mapsto \mathrm{Trunc}_k(\mathbf{x} + P(\mathbf{x})). The framework greatly improves on the results of [GKR25] by computing a Gröbner basis efficiently and providing precise bounds. The ideal degree for a preimage attack is:

where \ell = t - k is the length of the subspace trail. A new CheapLunch structure is identified where \mathcal{Q} has k - 1 equations of weight d \cdot 4^{R_{f,1}}, yielding:

5. Non-Regular Examples

The paper now considers CheapLunch systems that do not follow Definition 9. When \mathcal{Q}^{\mathrm{top}} is not regular, the arguments used to prove Lemma 1 no longer apply. The Gröbner basis computation may feature non-trivial cancellation (degree fall polynomials), preventing direct application of the Section 3 strategy.

5.1 Griffin

The Griffin hash function [GHR+23] has been broken for k = 1 in [BBO+24, BBO+25], but no cryptanalysis exists for k > 1. A new modeling for the CICO-k problem introduces intermediate variables y_i, z_i for each round. The weighted Bézout bound gives:

This bound is not tight. Based on experiments, the authors make the following conjecture:

5.2 ArionHash

ArionHash [RST23] is an AO hash function whose underlying permutation Arion-\pi uses inversion on one branch and low degree functions on other branches, following the Generalized Triangular Dynamical System (GTDS) formulation [RS24]. For the CICO-k problem, variables y_i are introduced on the last branch with equations P_i := y_i^{\alpha} - L_t^{(i-1)}(x_1, \ldots, x_k, y_1, \ldots, y_{i-1}).

The system is not regular because the highest degree terms of all output polynomials Q_j are constant multiples of the same state element. By canceling out the common higher degree terms through linear combinations, an improved upper bound is obtained:

where \deg(\bar{Q}_j) = (2^{t-1}(e+1) - e)^{(r-1)} \cdot (2^{t-j}(e+1) - e). Experimental results confirm the bound holds but show it is not tight.

Acknowledgements

This work has been facilitated through the COSINUS associate team between Inria and Simula. The authors would like to thank Vincent Neiger and Maël Hostettler for insightful discussions in the early stages of this work. The work of Antoine Bak and Aurélien Boeuf was supported by the European Research Council (ERC, grant agreement no. 101041545 “ReSCALE”). Aurélien Boeuf was also supported in part by the French Agence Nationale de la Recherche through the SWAP project under Contract ANR-21-CE39-0012. Antoine Bak was also supported by the French DGA. The work of Morten Øygarden and Atharva Phanse has been funded by a research grant from the Ethereum Foundation through the Poseidon Cryptanalysis Initiative.

References

• [Alf05] Alfonsín, J.L.R.: The Diophantine Frobenius Problem, vol. 30. Oxford University Press (2005).
• [ABK+23] Ashur, T., Bhati, A.S., Kindi, A., Mahzoun, M., Perrin, L.: XHash: Efficient STARK-friendly hash function. Cryptology ePrint Archive, Report 2023/1045 (2023). eprint.iacr.org/2023/1045.
• [ABM23] Ashur, T., Buschman, T., Mahzoun, M.: Algebraic cryptanalysis of HADES design strategy: Application to Poseidon and Poseidon2. Cryptology ePrint Archive, Paper 2023/537 (2023). eprint.iacr.org/2023/537.
• [AKM+22] Ashur, T., Kindi, A., Meier, W., Szepieniec, A., Threadbare, B.: Rescue-prime optimized. Cryptology ePrint Archive, Report 2022/1577 (2022). eprint.iacr.org/2022/1577. [page on this site]
• [BP25] Bak, A., Perrin, L.: On the security of Split-and-Lookup-based ZK-friendly primitives. IACR Transactions on Symmetric Cryptology 2025(2), 87–123 (2025).
• [BFS15] Bardet, M., Faugère, J.C., Salvy, B.: On the complexity of the F5 Gröbner basis algorithm. Journal of Symbolic Computation 70, 49–70 (2015).
• [BBO+24] Bariant, A., Boeuf, A., Lemoine, A., Manterola Ayala, I., Øygarden, M., Perrin, L., Raddum, H.: The Algebraic FreeLunch: Efficient Gröbner Basis Attacks Against Arithmetization-Oriented Primitives. In: Crypto 2024. pp. 139–173. Springer (2024).
• [BBO+25] Bariant, A., Boeuf, A., Briaud, P., Hostettler, M., Øygarden, M., Raddum, H.: Improved Resultant Attack against Arithmetization-Oriented Primitives. Cryptology ePrint Archive, Paper 2025/259 (2025). eprint.iacr.org/2025/259.
• [BBLP22] Bariant, A., Bouvier, C., Leurent, G., Perrin, L.: Algebraic attacks against some arithmetization-oriented primitives. IACR Transactions on Symmetric Cryptology 2022(3), 73–101 (Sep 2022).
• [BMMT94] Becker, E., Mora, T., Marinari, M.G., Traverso, C.: The shape of the shape lemma. In: Proceedings of the 1994 International Symposium on Symbolic and Algebraic Computation. pp. 129–133 (1994).
• [BGL20] Ben-Sasson, E., Goldberg, L., Levit, D.: STARK friendly hash – survey and recommendation. Cryptology ePrint Archive, Paper 2020/948 (2020). eprint.iacr.org/2020/948.
• [Ber75] Bernshtein, D.N.: The number of roots of a system of equations. Functional Analysis and Its Applications 9, 183–185 (1975).
• [BNS22] Berthomieu, J., Neiger, V., Safey El Din, M.: Faster change of order algorithm for Gröbner bases under shape and stability assumptions. In: ISSAC 2022. pp. 409–418 (2022).
• [BDPA08] Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: On the Indifferentiability of the Sponge Construction. In: EUROCRYPT 2008. pp. 181–197. Springer (2008).
• [BCD+20] Beyne, T., Canteaut, A., Dinur, I., et al.: Out of oddity – new cryptanalytic techniques against symmetric primitives optimized for integrity proof systems. In: CRYPTO 2020. pp. 299–328. Springer (2020). [page on this site]
• [BBP+23] Bouvier, C., Briaud, P., Chaidos, P., Perrin, L., Salen, R., Velichkov, V., Willems, D.: New design techniques for efficient arithmetization-oriented hash functions: Anemoi permutations and jive compression mode. In: CRYPTO 2023. pp. 507–539. Springer (2023). [page on this site]
• [CR25] Campa, L., Roy, A.: Groebner basis cryptanalysis of Anemoi. Cryptology ePrint Archive, Paper 2025/814 (2025). eprint.iacr.org/2025/814.
• [CLO15] Cox, D.A., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms. Springer, fourth edn. (2015).
• [Fau99] Faugère, J.C.: A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra 139(1), 61–88 (1999).
• [Fau02] Faugère, J.C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In: ISSAC ’02. pp. 75–83. ACM (2002).
• [FGHR14a] Faugère, J.C., Gaudry, P., Huot, L., Renault, G.: Sub-cubic change of ordering for Gröbner basis: a probabilistic approach. In: ISSAC 2014. pp. 170–177 (2014).
• [FGHR14b] Faugère, J.C., Gaudry, P., Huot, L., Renault, G.: Using symmetries in the index calculus for elliptic curves discrete logarithm. Journal of Cryptology 27(4), 595–635 (2014).
• [FGLM93] Faugère, J., Gianni, P.M., Lazard, D., Mora, T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. J. Symb. Comput. 16(4), 329–344 (1993).
• [FM17] Faugère, J.C., Mou, C.: Sparse FGLM algorithms. Journal of Symbolic Computation 80, 538–569 (2017).
• [FSV13] Faugère, J.C., Safey El Din, M., Verron, T.: On the Complexity of Computing Gröbner Bases for Quasi-homogeneous Systems. In: ISSAC ’13. pp. 189–196. ACM (2013).
• [FSV16] Faugère, J.C., Safey El Din, M., Verron, T.: On the complexity of computing Gröbner bases for weighted homogeneous systems. Journal of Symbolic Computation 76, 107–141 (2016).
• [FGHR13] Faugère, J.C., Gaudry, P., Huot, L., Renault, G.: Polynomial systems solving by fast linear algebra (2013). arxiv.org/abs/1304.6039.
• [FGLM93b] Faugère, J.C., Gianni, P., Lazard, D., Mora, T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. Journal of Symbolic Computation 16(4), 329–344 (1993).
• [FB09] Fusco, G., Bach, E.: Phase transition of multivariate polynomial systems. Mathematical Structures in Computer Science 19(1), 9–23 (2009).
• [GM87] Gianni, P., Mora, T.: Algebraic solution of systems of polynomial equations using Groebner bases. vol. 356, pp. 247–257 (1987).
• [GHR+23] Grassi, L., Hao, Y., Rechberger, C., Schofnegger, M., Walch, R., Wang, Q.: Horst meets fluid-SPN: Griffin for zero-knowledge applications. In: CRYPTO 2023. pp. 573–606. Springer (2023). [page on this site]
• [GKL+22] Grassi, L., Khovratovich, D., Lüftenegger, R., Rechberger, C., Schofnegger, M., Walch, R.: Reinforced concrete: A fast hash function for verifiable computation. CCS ’22. pp. 1323–1335. ACM (2022). [page on this site]
• [GKL+24] Grassi, L., Khovratovich, D., Lüftenegger, R., Rechberger, C., Schofnegger, M., Walch, R.: Monolith: Circuit-friendly hash functions with new nonlinear layers. IACR Transactions on Symmetric Cryptology 2024(3), 44–83 (Sep 2024).
• [GKR+21] Grassi, L., Khovratovich, D., Rechberger, C., Roy, A., Schofnegger, M.: Poseidon: A New Hash Function for Zero-Knowledge Proof Systems. In: 30th USENIX Security Symposium. pp. 519–535 (2021). [page on this site]
• [GKS23] Grassi, L., Khovratovich, D., Schofnegger, M.: Poseidon2: A faster version of the Poseidon hash function. In: AFRICACRYPT 2023. pp. 177–203. Springer (2023). [page on this site]
• [GKR25] Grassi, L., Koschatko, K., Rechberger, C.: Poseidon and Neptune: Gröbner basis cryptanalysis exploiting subspace trails. Cryptology ePrint Archive, Paper 2025/954 (2025). eprint.iacr.org/2025/954.
• [GOPL22] Grassi, L., Onofri, S., Pedicini, M., Sozzi, L.: Invertible quadratic non-linear layers for MPC-/FHE-/ZK-friendly schemes over \mathbb{F}_p^n: Application to Poseidon. IACR Transactions on Symmetric Cryptology 2022(3), 20–72 (Sep 2022).
• [Jea16] Jean, J.: TikZ for Cryptographers (2016).
• [Kho77] Khovanskii, A.: Newton polyhedra and toroidal varieties. Functional Analysis and Its Applications 11, 289–296 (1977).
• [KLR24] Koschatko, K., Lüftenegger, R., Rechberger, C.: Exploring the six worlds of Gröbner basis cryptanalysis: Application to Anemoi. IACR Transactions on Symmetric Cryptology 2024(4), 138–190 (Dec 2024).
• [Kus76] Kushnirenko, A.G.: Newton polytopes and the Bézout theorem. Functional Analysis and Its Applications 10(3), 233–235 (1976).
• [Laz83] Lazard, D.: Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations. In: Computer Algebra. pp. 146–156. Springer (1983).
• [RS24] Roy, A., Steiner, M.J.: Generalized triangular dynamical system: An algebraic system for constructing cryptographic permutations over finite fields. In: SAC 2024. pp. 139–165. Springer (2024).
• [RST23] Roy, A., Steiner, M.J., Trevisani, S.: Arion: Arithmetization-oriented permutation and hashing from generalized triangular dynamical systems. arXiv preprint arXiv:2303.04639 (2023).
• [SLS+23] Szepieniec, A., Lemmens, A., Sauer, J.F., Threadbare, B., Al-Kindi: The Tip5 hash function for recursive STARKs. Cryptology ePrint Archive, Paper 2023/107 (2023). eprint.iacr.org/2023/107. [page on this site]
• [HS13] Van Der Hoeven, J., Schost, E.: Multi-point evaluation in higher dimensions. Applicable Algebra in Engineering, Communication and Computing 24(1), 37–52 (2013).
• [YZY+24] Yang, H.S., Zheng, Q.X., Yang, J., Liu, Q.F., Tang, D.: A New Security Evaluation Method Based on Resultant for Arithmetic-Oriented Algorithms. In: AsiaCrypt 2024. pp. 457–489. Springer (2024).