Comment about the security section and Poseidon

[mschof]

In the security section of the repository, a comment is made about the Poseidon hash function based on an analysis in BBLP22, saying that it only offers 95 bits of security in Plonky2. However, the corresponding analysis in this paper discusses a slightly different case. In particular, Section 4.3 describes a root-finding approach which was relevant in the case of the original challenges, where t=3 and finding the solution to a univariate equation was thus sufficient in order to find a preimage. However, the Poseidon instance in Plonky2 uses a 64-bit prime field, and in a univariate approach this technique would allow to find a 64-bit part of a preimage with around 95 bits of work. In other words, even exhaustive search would be more efficient.
To summarize, the approach discussed in BBLP22, while correct, does not apply to the Poseidon instance used in Plonky2 (and does not break any full-round Poseidon instance in general). As far as we know, the Poseidon instance used in Plonky2 retains the full 128 bits of the claimed security level.

[dlubarov]

Sorry I missed this earlier. Thanks Markus for clarifying this for us! I was wondering why the 95 bit figure didn't seem consistent with the scripts mentioned in and based on the paper. (If those estimates had been broken, I imagine that would have been made very clear.) Good to know.