Bounty program for Poseidon Hash Initiative

Bounties for generic security level

Poseidon-256 based on Poseidon:

To produce an instance with $\kappa$-bit security, we plugged $\kappa$ into the round number script with parameter $R_F=6$. We have also calculated the complexity of the interpolation and the Groebner basis attack in the table below.
24-bit security level: 256-bit field, $d=5$, $t=3$, $R_F=6$, $R_P=8$. 256-bit (1 field element) preimage of 0.
28-bit security level: 256-bit field, $d=5$, $t=3$, $R_F=6$, $R_P=9$. 256-bit (1 field element) preimage of 0.
32-bit security level: 256-bit field, $d=5$, $t=3$, $R_F=6$, $R_P=11$. 256-bit (1 field element) preimage of 0.
40-bit security level: 256-bit field, $d=5$, $t=3$, $R_F=6$, $R_P=16$. 256-bit (1 field element) preimage of 0.

Poseidon-64 based on Poseidon2:

To produce an instance with $\kappa$-bit security, we plugged $\kappa$ into the round number script with parameter $R_F=6$. We have also calculated the complexity of the interpolation and the Groebner basis attack in the table below.
24-bit security level: 64-bit field, $d=7$, $t=8$, $R_F=6$, $R_P=7$. 64-bit preimage (1 field element). $4000
28-bit security level: 64-bit field, $d=7$, $t=8$, $R_F=6$, $R_P=8$. 64-bit preimage (1 field element). $6000
32-bit security level: 64-bit field, $d=7$, $t=8$, $R_F=6$, $R_P=10$. 64-bit preimage (1 field element). $10000
40-bit security level: 64-bit field, $d=7$, $t=8$, $R_F=6$, $R_P=13$. 64-bit preimage (1 field element). $15000

Poseidon-31 based on Poseidon2:

To produce an instance with $\kappa$-bit security, we proceeded differently: the approach as for Poseidon-256 and Poseidon-64 would give too large round numbers which would become impossible to break. Instead, for small security levels we set $R_F=4$ and then set $R_P$ so that the resulting complexity of the interpolation attack (solve univariate equation for one output word $2^{31}$ times) is slightly bigger then that of the complexity of the interpolation attack on the same security level of Poseidon-256 and Poseidon-64. We have also calculated the complexity of the Groebner basis attack in the table below.
24-bit security level:
- 31-bit field M31, $d=5$, $t=16$, $R_F=4$, $R_P=0$. 62-bit preimage (2 field elements).
- 31-bit field KoalaBear, $d=3$, $t=16$, $R_F=4$, $R_P=1$. 62-bit preimage (2 field elements).
28-bit security level:
- 31-bit field M31, $d=5$, $t=16$, $R_F=4$, $R_P=1$. 62-bit preimage.
- 31-bit field KoalaBear, $d=3$, $t=16$, $R_F=4$, $R_P=3$. 62-bit preimage.
32-bit security level:
- 31-bit field M31, $d=5$, $t=16$, $R_F=6$, $R_P=1$. 62-bit preimage.
- 31-bit field KoalaBear, $d=3$, $t=16$, $R_F=6$, $R_P=4$. 62-bit preimage.
40-bit security level: 31-bit field M31, $d=5$, $t=16$, $R_F=6$, $R_P=4$. 62-bit preimage.

Our estimate of algebraic attack complexity on these instances (in $\log_2$):