Algebraic Attacks Against Poseidon2

A recent paper improved on existing algebraic attacks against Poseidon2. It received a bounty from the Ethereum Foundation under the Poseidon Initiative https://www.poseidon-initiative.info/

The paper specifically mentions Quantus as a chain that uses Poseidon2. It claims a 2^106 speedup against the best existing algebraic attacks against binary-Poseidon2 (does not apply to us, we use Goldilocks field) but even with this speedup the paper clarifies that Poseidon2 maintains the claimed 128-bit security level.

The authors’ GitHub repo for one of the bounty claims contains SageMath code that solved a specific CICO (constrained input / output) bounty instance in under 11 hours on 64 cores using round-skipping. This repo targets a reduced/small-field setup (M31 prime), not full-round Goldilocks parameters.

In the paper, they analyzed parameter sets that include our width (12) and degree (7) but not our capacity, which is 8, not 4. This gives us additional headroom in the security analysis. We also use 22 internal rounds and 8 external rounds whereas the paper analyzes the 15 internal round case. Additionally we pad to 189 felts, which gives further security buffer.

Based on my (limited) understanding, I think this does not warrant any change to our implementation, but we should invite review by people with more domain expertise.

One of the authors of the paper responded confirming we do not need to update the parameters.

We mention @QuantusNetwork as an example of a deployment. However, in our paper we focus on instances 128-bit classic secure, while your implementation is 128-bit quantum secure, 256-bit classical. There is no impact for your concrete parameter set.

https://x.com/AlexRdgzG/status/2024381450817032520?s=20