Paper 2026/409

Cryptanalysis of Poseidon-Based Fiat-Shamir Protocols

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.