Paper 2026/967

Revisiting Linear Subspace Trails in Poseidon

Abstract

Algebraic attacks are an important class of cryptanalytic techniques for Poseidon/Poseidon2 and Neptune. These designs use partial S-box activation in internal rounds to reduce arithmetization cost, and this structure makes linear subspace trails an important technique in their algebraic analysis. If the state at some internal round is restricted to a suitable linear subspace, then several subsequent internal rounds can be linearized and therefore do not increase the degree of the polynomial system used to model the attack. Recent studies have explored such linearization and round-skipping techniques for algebraic attacks on Poseidon/Poseidon2 and Neptune. These techniques reduce the complexity of attacks by lowering the degree of the polynomial systems that model the attacked rounds. Consequently, a precise bound on the length of linear subspace trails is needed for a more accurate assessment of the algebraic security of these designs. We revisit infinite and finite linear subspace trails in Poseidon-like designs. First, motivated by previous work that relates infinitely long linear subspace trails to invariant subspaces of the linear layer, we revisit this phenomenon for the Cauchy MDS matrices used in Poseidon. We further give a quantitative heuristic estimate for the probability that such invariant subspace conditions occur under random parameter choices. Second, we analyze finite linear subspace trails for partial rounds in a general setting, where the state width is $t$ and each round activates $s$ S-box coordinates. Under the rank growth condition stated in this paper, when no such invariant subspace exists, a finite trail has length at most $\lceil t/s \rceil - 1$. For Poseidon, $s = 1$, this gives at most $t - 1$ consecutive linearized internal partial rounds. For the internal linear layers of Poseidon2 and Neptune, a similar conclusion applies. More precisely, if repeated diagonal entries in the lower-right block do not give rise to infinitely long linear subspace trails, then the maximum length of a finite linear subspace trail is exactly $t - 1$. Third, for preimage attacks in sponge mode with rate $r$, capacity $c$, and digest size $d$, the available extra constraint budget is $Ec = r - \min(c,d)$. For Poseidon/Poseidon2 and Neptune, the finite trail bound and this constraint budget together determine how many internal partial rounds can be linearized in the corresponding attack model.