Welcome to the resource topic for 2023/537
Title:
Algebraic cryptanalysis of POSEIDON
Authors: Tomer Ashur, Thomas Buschman, Mohammad Mahzoun
Abstract: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
ePrint: https://eprint.iacr.org/2023/537
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .