What is this Project About?

Arithmetization-oriented (AO) hash functions have proliferated rapidly over the past few years, driven by the demands of proof systems such as SNARKs and STARKs. Designing a hash function that is simultaneously efficient over a prime field and resistant to algebraic attacks is hard. Unfortunately, assessing whether a proposed design has actually achieved this isn’t any easier: our understanding of this topic remains limited.

The Athena consortium is a group of cryptographers coming together to rigorously examine the state of the art in the cryptanalysis of AO hash functions, with a particular focus on a regime of parameters that has received considerably less attention in the literature: small characteristic primes, meaning fields of size much smaller than the security parameter, such as KoalaBear (p=231−224+1p = 2^{31} - 2^{24} + 1) and Goldilocks (p=264−232+1p = 2^{64} - 2^{32} + 1).

The State of Our Understanding: An Honest Assessment

As mentioned above, the current state-of-the-art of the understanding of the security of such hash functions is limited. Below, we quickly go over what we understand well (“the good”), what we do not (“the bad”), and what we only partially understand, to an extent that remains to be estimated (“the ugly”).

The Good: CICO-1 and Ideal

The Constrained-Input Constrained-Output (CICO) problem is the natural security notion for permutation-based constructions, and has been used a lot in the AO setting. In particular, its simplest form (namely, CICO-1, where a single input and output coordinates are constrained) is reasonably well understood, and is enough when the field size is very large.

In this context, we can write convincing security arguments based on the ideal degree of the output polynomial. To make a long story short, in the case of CICO-1, we can be sure that a polynomial of a specific degree will appear during the polynomial solving step, and that this polynomial will be so big that it cannot be generated using less computing power than the intended security level. This is not a proof of security, but it is a meaningful and quantifiable heuristic, and one that the community has developed reasonable tools to reason about.

For CICO-1, this approach allows us to make security arguments that can be trusted. Unfortunately, its applicability beyond CICO-1 is less clear.

The Bad: CICO-k and the Limits of Degree Arguments

The situation deteriorates when we move to CICO-k for k≥2k \geq 2, and it deteriorates faster than one might hope.

The difficulty is structural. When k>2k > 2 it becomes feasible for an adversary to guess a single prime field element at one of the inputs and thereby over-define the resulting system. A single guess is enough to ensure that the ideal degree of the overdetermined system drops to zero. This does not imply that the system becomes much easier to solve, but it does mean that a plain ideal degree computation cannot meaningfully bound the attack complexity.

This is not a flaw in any particular hash function design: it is a structural limitation of the degree-based security argument as currently formulated. We do not yet have a satisfying replacement.

The Ugly: Round Skips

Another method to make attacks more efficient consists in skipping rounds. This informal term encompasses techniques that boil down to using the degrees of freedom inherent to our systems of equations to add cleverly chosen artificial constraints that decrease the ideal degree. We are not talking about a drastic drop all the way down to zero like in the previous section, but its impact on the overall complexity remains significant. Basically, it is as though several rounds of the primitive did not contribute to increasing the attack complexity: they are effectively “skipped”.

An honest assessment of the state-of-the-art regarding these could be written as follows: we do not currently know how to argue the absence of round-skip vulnerabilities in a general, convincing way. Existing analyses would check specific structural conditions that may not cover all attack avenues, relying on types of tricks that are well known to symmetric cryptographers, but may be too restricted to convincingly cover all possibilities. This is an open problem, and a serious one, especially for Poseidon (and its variants, like Poseidon2): if the first 4 rounds were to be skipped, the situation would become dire. There is, at this stage, no reason to believe that this will happen—but it would be much better to be sure that it won’t.

Where to go from here

The task of the Athena consortium is to make a proper assessment of the security level offered by already published ZK-friendly hash functions when instantiated over smaller fields with a size corresponding to 32- or 64-bit prime. Many have been broken, but others seem to have remained unscathed: we will figure this out.

To do this, we have gathered a team of a dozen scientists. Some of us are ZK-friendly hash function designers, some of us are ZK-friendly hash functions breakers (and some of us are both!), some of us are symmetric cryptanalysis specialists, and some of us are computer algebra experts. The team is lead by

and is composed of

Based on our expertise, we will issue concrete guidelines for AO hash functions targeting small-prime fields.