Paper 2026/409

Cryptanalysis of Poseidon-Based Fiat-Shamir Protocols

Nerses Asaturyan, Yerevan State Univeristy, Layerswap Labs

Gohar Hovhannisyan, Yerevan State University

Abstract

Poseidon[GKR+19 ] and its successor Poseidon2[GKS23] are arithmetization-oriented permutations proposed for hashing inside algebraic proof systems. While there is extensive prior work on cryptanalysis of reduced-round Poseidon/Poseidon2 and theoretical and practical weaknesses of the Fiat-Shamir transform, these two attacks are typically studied in isolation. This work asks whether combining them i.e., instantiating Fiat-Shamir with Poseidon can enable new attacks. We design and implement multiple candidate attacks that encode verifier checks together with reduced-round Poseidon-based challenge derivation as explicit polynomial systems, targeting settings such as Sigma protocols and FRI-like degree enforcement. We evaluate these approaches using Gr¨obner bases. We use this model to derive Gr¨obner-basis attack formulations aimed at constructing verifier-accepting transcripts that violate the intended low-degree bound, and we report the computational bottlenecks encountered in representative parameter regimes. We also document additional explored directions, including retry-style challenge biasing and reduced-round investigations, in order to clarify which attacks appear more or less promising. Across our implementations, we do not obtain meaningful forgeries: even with heavily reduced Poseidon parameters, Gr¨obner-basis computations do not find solutions for random instances of the constructed systems. Our results provide negative evidence for several natural algebraic attack routes on Poseidon-based Fiat-Shamir instantiations, and help clarify which known Fiat-Shamir weaknesses do and do not transfer to well-structured, fully transcript-bound deployments.

@misc{cryptoeprint:2026/409,
      author = {Hayk Hovhannisyan and Nerses Asaturyan and Gohar Hovhannisyan},
      title = {Cryptanalysis of Poseidon-Based Fiat-Shamir Protocols},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/409},
      year = {2026},
      url = {https://eprint.iacr.org/2026/409}
}