Paper 2026/1692 Original: eprint.iacr.org/2026/1692 ↗

How to Attack Poseidon via Smart Subspace Restriction

Abstract

Poseidon [Grassi, Khovratovich, Rechberger, Roy, and Schofnegger; USENIX'21] is an arithmetization-oriented (AO) hash function designed to be highly efficient in real-world zero-knowledge (ZK) applications. As a sponge-based construction, its algebraic security inherently relies on its underlying permutation, Poseidon-$\pi$, and the dense mixing of its layers: the initial full rounds ($R_{f_0}$), middle partial rounds ($R_p$), and final full rounds ($R_{f_1}$). One of the common approaches to argue security is to bound the effort of solving the $k$-Constrained-Input $k$-Constrained-Output (CICO-$k$) problem over this permutation of state size $t\geq2k$. Recent cryptanalysis has utilized subspace restriction to mitigate algebraic degree growth in Poseidon and used it to argue improvements in CICO-$k$ solving, though prior methods have faced strict limits on the number of rounds they can successfully bypass (more specifically, $<2$) and have targeted $k\leq2$. In this paper, we introduce a unified mathematical framework for advanced subspace restriction in Poseidon cryptanalysis. We first present a baseline gadget; Generalized S-Box Skipping via Subspace Restriction (GSR); that deterministically absorbs $2t-2k$ total S-boxes across: one initial full round ($t$ S-boxes) and $t-2k$ partial rounds (one S-box per round). This significantly reduces the polynomial degree of the Poseidon multivariate polynomial system. By restricting the subspace of the total constraints satisfying solutions, independent of the round constants and MDS matrix selection, the distinguisher expends input degrees of freedom (DoFs) to linearize the internal state transitions where the dense algebraic mixing usually occurs. We then explain and break the first theoretical barrier that confines such subspace restriction techniques to configurations with exactly $R_{f_0}=1$ initial full round. We formalize $(k+1)$-wise collapsing, a non-trivial DoF consumption framework. By parameterizing the system from an intermediate state and formulating constraints backwards, Round 1 is naturally skipped at zero cost. Building on this baseline, for $R_{f_0} \ge 2$ and under the CICO-$k$ setting, $(k+1)$-wise collapsing non-trivially expends a portion of the available DoFs to project state variables into the nullspace of targeted inverse MDS submatrices. This forces a perfect algebraic cancellation of non-linear inverse S-boxes, effectively absorbing the second full round entirely. We show how the residual DoFs, after applying $(k+1)$-wise collapsing, can be either used to combine GSR for partial round skipping or alternatively deployed for bidirectional collapsing, i.e., to skip almost one full round from the back (defeating prepended/appended linear layer defenses) or can be used to construct exactly determined zero-dimensional ideals of strict degree-$3^{1+R_{f_1}}$ for $R_{f_0}=3$ instances. Our framework drastically improves upon the state-of-the-art algebraic limits of Poseidon, most notably by identifying a critical gap in derived theoretical cryptanalysis bounds. We demonstrate that monolithic Macaulay matrix approximations heavily over-estimate true solving complexity. By utilizing residual DoFs to construct exactly determined zero-dimensional ideals of strict degree-3 for $R_{f_0}=3$ instances, we empirically validate our framework by tracking the step-wise intermediate peak of Faugère's $F_4$ algorithm in $\mathtt{msolve}$. Through this, we successfully extract the Gröbner basis for a mathematically intractable $(3,8,0)$ instance of Poseidon with KoalaBear ($t=24$) in under 5 minutes on a standard 96-thread server. Further, in terms of monolithic complexities, where baseline estimates shows a mathematically intractable $F_4$ and FGLM time complexities of $\approx 2^{560}$ and $\approx 2^{404}$ bit operations, respectively, for a $(3,10,3)$ CICO-1 configuration, our framework successfully isolates the system into a degree-$3^4$ ideal, reducing the theoretical time complexities to $\approx 2^{121}$ and $\approx 2^{71}$ bit operations, respectively. Similarly, for a $(3,5,3)$ CICO-2 instance, we achieve a reduction in $F_4$ and FGLM time complexities from $\approx 2^{540}$ and $\approx 2^{390}$, respectively, to $\approx 2^{100}$ and $\approx 2^{69}$ bit operations, respectively, thereby bringing heavily constrained Gröbner basis attacks significantly closer to practical feasibility. We then demonstrate how deploying $(k+1)$-wise collapsing combined with GSR significantly improves the reach of interpolation-based and resultant-based CICO attacks on configurations targeting $R_{f_0}=2$. For the industry standard KoalaBear instance where $(R_{f_0},R_p,R_{f_1})=(4,23,4)$, our results achieve penetrations up to (2,14,4), i.e., 20 rounds for CICO-1, and (2,9,4), i.e., 15 rounds for CICO-2. Finally, when applying our baseline GSR technique only to $R_{f_0}=1$ configurations, our results further extend the attack reach to larger round-reduced versions. We successfully attack up to (1,23,4), i.e., 28 out of 31 rounds for CICO-1, and (1,20,4), i.e., 25 out of 31 rounds for CICO-2, overall establishing new practical limits for subspace restriction against Poseidon.