[protocol spec] Document infeasibility of an attack on Poseidon

[daira]

[Bariant, Bouvier, Leurent, and Perrin 2022, section 4.3] describe an algebraic attack on some instantiations of Poseidon (including the version we use, Poseidon 1.1) that claims to improve on the attack cost estimates given in the Poseidon paper.

Closer examination shows that the costs of this attack are stated only for $\alpha = 3$. The instantiation of Poseidon used in Orchard has $\alpha = 5$. Since the attack cost has an $\alpha^{r-2}$ multiplicative term where $r$ is the total number of (full or partial) rounds, it is infeasible (well over $2^{128}$ work) for our instantiation. This should be documented in the protocol specification, with the discussion of Poseidon's security in section 5.4.1.10.

This came to my attention via Least Authority's audit report on Mina, where Least Authority claim Mina's Poseidon instantiation would be subject to the above attack with ~ $2^{116}$ work. This is incorrect for a similar reason: Mina uses a Poseidon instantiation with $\alpha = 7$ (the Kimchi constants here), against which the attack is infeasible.

[daira]

This did not make it into 2023.4.0.