International Association
for Cryptologic Research

POSEIDON is a hash function proposed by Grassi et al. in the USENIX Security ’21 conference. Due to its impressive efficiency and low arithmetic complexity it has garnered the attention of designers of integrity-proof systems such as SNARKS, STARKS, and Bulletproofs. In this work, we show some caveats in Poseidon’s security argument. Most notably, we extend on previous work by Sauer and quantify the rate at which the degree of regularity increases as a function of full and partial rounds. We observe that this degree grows slower than originally assumed, suggesting that there are cases where the recommended number of rounds is insufficient to meet claimed security. The findings presented in this paper are asymptotic in nature and do not affect all parameter sets equally. As a proof of concept, we present a full attack for an instance at the 1024-bit security level. We present two more parameter sets at the 512- and 384-bit security levels where the original security argument does not hold, but for which we were not able to demonstrate a full attack due to other aspects of the design. We were not able to find parameter sets in the 128- and 256-bit levels that are vulnerable