ZK Hash Function Cryptanalysis Bounties

Terms

Task: find $X1,X2,Y1,Y2$ such that $\displaystyle Perm(X1,X2,0)=(Y1,Y2,0)$

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

• Solutions should be sent to Dmitry Khovratovich before November 30th 2022.
• First come first win.
• Within 1 month after the submission the authors should provide a technical report with the attack description, which should be released to the public domain at latest December 1st 2022. The code should be also made public before this date.
• Total Bounty Budget: $200,000 USD.
• Parameters are fixed on November 23rd 2021.

Rescue Prime

Design spec.

• $p=18446744073709551557 \text{\textasciitilde} 2^{64}$
• $m=3$
• $alpha=3$
• Number of rounds: $N$
• Brute force attack complexity: $2^{64}$

We expect that a variant with $s$ bits of security to withstand attacks of complexity up to $2^{1.5s}$ time (function calls) and memory.

Reference implementation and bounty instances.

Feistel-MIMC

Design spec.

• $p=18446744073709551557 \text{\textasciitilde} 2^{64}$
• $alpha=3$
• Task: find $X,Y$ such that $Feistel\text{\textendash}MiMC(X,0)=(Y,0)$
• Number of rounds: $r$
• Brute force attack complexity: $2^{64}$

We expect that a variant with $s$ bits of security to withstand attacks of complexity up to $2^{2s}$ time (function calls) and memory.

The initial parameters were broken and were replaced.

Reference implementation and bounty instances.

Poseidon

Design spec.

• $p=18446744073709551557 \text{\textasciitilde} 2^{64}$
• $d=3$
• $t=3$
• Number of full rounds: $RF=8$
• Number of partial rounds $RP$ varies (see below)
• Brute force attack complexity: $2^{64}$

We expect that a variant with $s$ bits of security to withstand attacks of complexity up to $2^{s+37}$ time (function calls) and memory.

The initial parameters were broken and were replaced.

Reference implementation and bounty instances.

Reinforced Concrete

Design spec.

• Number of layers as in the original design
• Different prime field
• The best attack we have found for these variants is exhaustive search.
• Groebner basis challenges might be declared additionally.

We expect that a variant with $s$ bits of security to withstand attacks of complexity up to $2^{2s}$ time (function calls) and memory.

Decomposition and alpha/beta values.

Reference implementation and bounty instances.

Contact

dmitry.khovratovich@ethereum.org