Tomorrow Roozbeh Sarenche (COSIC) will be giving a
COSIC Seminar on "Towards Decentralized Searcher Competition in MEV Markets". Free to attend live! www.esat.kuleuven.be/cosic/?post_...
esat.kuleuven.be
Events Archive - COSIC
COSIC
@cosic.bsky.social
354 followers 45 following 1.1K posts
COSIC provides a broad expertise in digital security and strives for innovative security solutions. COSIC is headed by Bart Preneel. www.esat.kuleuven.be/cosic
![Abstract. Poseidon [Grassi, Khovratovich, Rechberger, Roy, and Schofnegger; USENIX’21] is an arithmetization-oriented (AO) hash function designed to be efficient in real-world zero-knowledge (ZK) applications. We present GSR, a generalized S-box skipping gadget that absorbs a single initial full round and t − 2k partial rounds without increasing the polynomial degree of the Poseidon polynomial system with state size t and input-output constraints 2k. By restricting the subspace of the total constraints satisfying solutions, independent of the rounds constants and MDS matrix selection, the distinguisher expends input degrees of freedom to linearize the internal state transitions where the dense algebraic mixing usually occurs. This maps a computationally infeasible polynomial system into a bounded, low-degree ideal parameterized by k free variables.
We show how to use the gadget to construct a probability 1 distinguisher over t − 2k + 1 rounds of Poseidon. We then show how this distinguisher can be used as a basis for interpolation-based attacks. We go on to present experimental solutions to the CICO-1 problem over 28 out of 31 rounds and CICO-2 problem over 25 out of 31 rounds in the setting set by the Ethereum Poseidon initiative (i.e., using the KoalaBear field with t = 24 and α = 3). Crucially, since the subspace restriction approach is tuned only by t and k, our results apply to the Poseidon structure regardless of the choice of round constants, MDS matrix, S-box exponent α, or field size p.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fwa55bujvdrwlwlwgqmmxmuf/bafkreibrfgfvxgmz2zfq6tul6wx4lgfrft5kd6hubigfg6zvf5vrmijpdq)
![Abstract. In this note, we show that some of the parameters of the Quotient-Ring transform proposed for VOX are vulnerable. More precisely, they were chosen to defeat an attack in the field extension 𝔽_(q^(l)) obtained by quotienting 𝔽_(q)[X] by an irreducible polynomial of degree l. We observe that we may use a smaller extension 𝔽_(q^(l′)) for any l′|l, in which case the attacks apply again. We also introduce a simple algebraic attack without the use of the MinRank problem to attack the scheme. These attacks concern a subset of the parameter sets proposed for VOX: I, Ic, III, IIIa, V, Vb. We estimate the cost of our attack on these parameter sets and find costs of at most 2⁶⁷ gates, and significantly lower in most cases. In practice, our attack requires 0.3s, 1.35s, 0.56s for parameter sets I,III,V for the initial VOX parameters, and 56.7s, 6.11s for parameter sets IIIa, Vb proposed after the rectangular MinRank attack.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fwa55bujvdrwlwlwgqmmxmuf/bafkreicbqbkfnth3y6v6d3wezhhnpddi5urwvjdloop5o5tislxiocgcvu)
