Paper 2023/537

Algebraic Cryptanalysis of HADES Design Strategy: Application to POSEIDON and Poseidon2

Tomer Ashur, Polygon Research, Cryptomeria
Thomas Buschman, Eindhoven University of Technology
Mohammad Mahzoun, Eindhoven University of Technology

Arithmetization-Oriented primitives are the building block of advanced cryptographic protocols such as Zero-Knowledge proof systems. One approach to designing such primitives is the HADES design strategy which aims to provide an efficient way to instantiate generalizing substitution-permutation networks to include partial S-box rounds. A notable instance of HADES, introduced by Grassi \emph{et al.} at USENIX Security '21, is Poseidon. Because of its impressive efficiency and low arithmetic complexity, Poseidon is a popular choice among the designers of integrity-proof systems. An updated version of Poseidon, namely, Poseidon2 was published at AfricaCrypt '23 aiming to improve the efficiency of Poseidon by optimizing its linear operations. In this work, we show some caveats in the security argument of HADES against algebraic attacks and quantify the complexity of Gr\"{o}bner basis attacks. We show that the complexity of the attack is lower than claimed with the direct implication that there are cases where the recommended number of rounds is insufficient for meeting the claimed security. Concretely, the complexity of a Gr\"{o}bner basis attack for an instance of Poseidon with 1024 bits of security is 731.77 bits and the original security argument starts failing already at the 384-bit security level. Since the security of Poseidon2 is derived from the security of Poseidon, the same analysis applies to the instances of Poseidon2. The results were shared with the designers and the security arguments were updated accordingly.

Available format(s)
Attacks and cryptanalysis
Publication info
POSEIDONHash functionsZero-Knowledge proof systemsGroebner Basis attacks
Contact author(s)
tomer @ cryptomeria tech
t buschman @ student tue nl
m mahzoun @ tue nl
2023-11-21: last of 2 revisions
2023-04-14: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-NoDerivs


      author = {Tomer Ashur and Thomas Buschman and Mohammad Mahzoun},
      title = {Algebraic Cryptanalysis of HADES Design Strategy: Application to POSEIDON and Poseidon2},
      howpublished = {Cryptology ePrint Archive, Paper 2023/537},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.