Poseidon Cryptanalysis Initiative 2024-2026

Ethereum Foundation

Scrutinizing Poseidon for Good

Introduction

Poseidon and Poseidon2 are hash functions designed  for the use in verifiable computation protocols. They have been optimized for the smallest circuit size over prime fields.

Poseidon  hash function has been used in numerous Ethereum applications that deal with verifiable computation. It is among the top performers at recent STARK benchmarks by StarkNet, which makes it a promising candidate for the use at Ethereum L1 for various protocols that employ ZK proofs. 

This project aims to boost the security investigation of various Poseidon instances and eventually decide whether there is sufficient evidence that is secure for high-value applications and foundations of Ethereum. Below we present the details of the Phase 1 of this project, which ends in December 2025. Phase 2 will be planned in mid-2025, and shall conclude in December 2026.


 

Running Team

The project is run by the Ethereum Foundation Poseidon Group (EFPG: poseidon@ethereum.org ):

The Advisory Board oversees key decisions and announcements made by EFPG, with members serving in an unpaid capacity:

 

Documentation on Poseidon

Original papers:

Reference code:

Follow-up research:

 

Bounty Program

Bounty program runs till December 1st, 2025. The idea of the bounty program is twofold:


These ideas are implemented as follows: we take original instances of Poseidon and Poseidon2, which claim 128-bit preimage security, and reduce the number of rounds such that the interpolation attack becomes feasible. The expected complexity of the attack 2^T is then used to claim “T-bit estimated security”. If either of our assumptions is violated then a better attack should be found.

Hash function instances in the program: 

The task is to find a preimage of 0, or, more precisely:

where Perm is the inner sponge permutation (bijective mapping) of the hash function the challenge list.

We encourage cryptanalysts to find an improved attack variant (such as “skipping first rounds” trick)  rather than to find a solution with a brute force. New attack ideas might qualify for a bonus.

Common terms:

Concrete bounties (details here): 

We expect that the best attack that solves these bounties is an interpolation attack. A Groebner basis attack that breaks any of these instances may qualify for an additional bonus.

Attack Reward Program

A research paper, which describes an attack on a reduced-round Poseidon, may qualify for a prize. It has to conform to the following rules:

Groebner Basis Exploratory

Existing Groebner basis research papers on Poseidon have very imprecise complexity estimates. We would like to launch a more detailed investigation of attack complexity so that the complexity of a full attack can be extrapolated from the ones on small instances.

We provide  research grants to derive a formula for Groebner basis preimage attacks arising from round equations. Concretely, we ask the following:

The complexity of these steps should be counted separately, both in terms of memory requirements and CPU operations. From the table of practical complexities, a formula for the full instance should be extrapolated.

The investigation is supposed to be done in close collaboration with the EF Poseidon Group. Questions should be sent to poseidon@ethereum.org 


Applications should be made at Ethereum Foundation website by January 1st, 2025. They will be processed in the order of receiving.

Workshops and Retreats

We plan to support workshops, retreats, and schools that are devoted to the cryptanalysis of Poseidon and related designs. Among those are

Short Term Grants

We have compiled a list of research problems which appear necessary to understand the security of Poseidon instances further. The grant amount ranges from $20000 to $40000, depending on the deliverables that are suggested by the applicants.


Applications should be made at Ethereum Foundation website by January 1st, 2025. They will be processed in the order of receiving.

Constructing an explicit Groebner basis

We invite a research in constructing explicit Groebner basis using some non-common ordering, follow the recent preprint. Such a construction should be accompanied by a trial application of the FGLM or a related algorithm to get a LEX-order basis. 

Analysis of small field versions 

We invite research on instances of Poseidon that use a very small field size, as long as MDS matrices can be constructed there. 

Security over extension fields

Currently Poseidon is defined over prime fields of various size. Parameters for extension fields are unknown as most attacks are not evaluated over such fields. Still some applications are looking for such instances in order to get higher performance or security.


We are looking for the analysis of Poseidon  variants where the underlying field is an extension of some prime field, for example M31.

Attack with resultants  

With the emergence of AOHs, Gröbner basis attacks have gained significant attention. However, alternative system-solving approaches, such as resultants, have also recently proven useful in the cryptanalysis of primitives like Anemoi, Jarvis, and Rescue-Prime. Expanding the application of resultants could enhance and diversify the quality of security evaluations of Poseidon-like constructions too.

Reducing constants 

Currently the round constants for all Poseidon versions are generated in the pseudo-random manner. We are interested in the research whether one can use low-weight constants and use them less frequently.

Security of partial rounds w.r.t. statistical attacks

We invite research on non-algebraic attacks that cover partial rounds. We are particularly interested in attacks that might exploit non-MDS matrices in Poseidon2.

Clustering differential trails 

Many algebraic hash functions argue the statistical security from the fact that any differential trail would pass a certain number of nonlinear components and thus has low ``probability''. However, little is known about possible clustering of such differential trails into truncated differentials, or linear relations into linear hulls for such designs.


We are looking for

Provable security

While many arithmetic hash functions come with a built-in provable protection against statistical attacks, rather little is known about resistance to algebraic attacks. The arguments supporting the algebraic security are, in the nutshell, the evidence of the high-degree of the transformation and an argument that equations for the Groebner attacks are numerous and have high degree and/or many variables. We would like to see some more universal evidence of such security, for example Security bounds for a transformation modelled as an iteration of random low-degree operations, in the style of Luby-Rackoff proofs. 


It would also be interesting to derive provable security for designs which are not necessarily efficient when compared to modern (unproven) approaches. For example, one such idea would be to specifically start with a unique representation of an algebraic structure for which strong arguments about its solving complexity can be made. This structure may then be transformed into a symmetric primitive mimicking the same behavior, but not necessarily being efficient.

Attacks on Fiat-Shamir usage

We are looking into attacks on (reduced-round) instances of Poseidon which would break the security of non-interactive cryptographic protocols obtained via the Fiat-Shamir heuristic, where Poseidon would be used to generate public coins. Applicants are free to choose protocols at their own.


Eligibility

The standard EF rules for small grants apply. Poseidon authors can not be applicants to the grants nor to the award program.

Disclaimer

Ethereum Foundation Poseidon Group includes Dmitry Khovratovich, one of the designers of Poseidon. Dmitry and the Poseidon team contributed to defining the bounty parameters and structuring the research grant program. Decisions on awarding grants and distributing bounties will be made by the members of the Ethereum Foundation Poseidon Group in consultation with the Advisory Board.



ChangeLog

29 Nov 2024 -- 24-bit bounty claimed for Poseidon-31

29 Nov 2024 -- a typo in the Koala Bear prime definition was fixed (2^32 -> 2^31 )


 poseidon@ethereum.org         2024