Regular Syndrome Decoding easier than prior estimates, paper finds
Original title: Regular Syndrome Decoding Is Easier Than Previously Estimated
Authors say widely used RSD parameters miss 128-bit targets, with losses approaching 67 bits.
A paper revisits Regular Syndrome Decoding, used in zero-knowledge protocols, pseudorandom correlation generators, and MPC-in-the-Head signatures. A hybrid algebraic attack coordinates zero-coordinate guesses with syndrome-based eliminations across regular blocks. For Ferret, Wolverine, and committed VOLE, at least one parameter set per application falls below a 128-bit target, with losses approaching 67 bits. Estimated PCG attack costs improve by up to 29.77 and 25.91 bits, and revised Liu et al. sets sit below 2^111 field operations.
Unconfirmed: Attack costs are the authors' estimates, not demonstrated breaks of deployed systems.
- The method balances guessing cost while keeping equations for linearization.
- Non-binary PCG attack costs improve by up to 29.77 bits.
- Binary-field PCG improvements reach 25.91 bits over prior best attacks.
- Revised Liu et al. 128-bit PCG sets are estimated below 2^111 operations.
From the original article
1 min read at arxiv.orgThe Regular Syndrome Decoding (RSD) problem is a structured variant of classical Syndrome Decoding and underlies a growing number of efficient cryptographic constructions, including zero knowledge protocols, pseudorandom correlation generators, and MPC in the Head signatures.
By Jiseung Kim · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.