EIP-5988 - Add Poseidon hash function precompile

Hello everyone,

Léo Perrin here, I am a symmetric cryptographer and I had a look at several arithmetization-oriented hash functions. The need to support a vast number of distinct sets of parameters for a primitive is something that is completely new in this field, and which we are only started to learn how to handle from a security standpoint. Until now, when doing cryptanalysis, we look at a single (or a few) well specified primitive, say the three AESs (128, 192 and 256). Here, there is a lot more variety for any given primitive (field size, number of inputs), and this of course impacts the security analysis. For example, it is well known that some choices of the MDS matrix can lead to significant security issues with Poseidon [1,2]. However, the matrix suggested above is, as far as I can tell, completely safe, provided that the round constants are chosen pseudo randomly.

This brings me to another point: it is in my opinion crucial that the MDS matrix and the round constants be provided as a “bundle”, i.e. implementers must not have the freedom to combine an MDS matrix from some set with round constants from another set. While not published yet, some colleagues and I found that some specific patterns in the combination of an MDS matrix and some round constants could be a security problem for some arithmetization-oriented permutation (not Poseidon at this stage, but still). It is nothing to worry about in practice provided that, again, matrix and constants are not allowed to be picked independently.

Feel free to ask any question you may have regarding the symmetric crypto aspects, with one obvious caveat: while I know the state-of-the-art in this area pretty well, it is a brand new area where there has been too little work on cryptanalysis in my opinion. Thus, much remains to be investigated!

[1] Out of Oddity – New Cryptanalytic Techniques Against Symmetric Primitives Optimized for Integrity Proof Systems. Beyne et al. CRYPTO’20 (also available on eprint).
[2] Mind the Middle Layer: The HADES Design Strategy Revisited. Keller and Rosemarin. EUROCRYPT’21 (also available on eprint).