Regular Syndrome Decoding Is Easier Than Previously Estimated

What it is

A preprint by Jiseung Kim, Minkyu Kim, Changmin Lee and Hochang Lee, received 20 October 2026 and approved 21 October 2026 on the IACR ePrint archive (2026/2564). It has no peer-review venue listed. It lowers the estimated attack cost for the Regular Syndrome Decoding (RSD) problem, which the abstract says underlies zero-knowledge protocols, pseudorandom correlation generators (PCGs) and MPC-in-the-Head signatures.

How it works

The attack is a hybrid-algebraic method with three stages: guess zero coordinates, eliminate variables using the syndrome equations, then solve by linearization. Earlier work treated the guessing and the elimination as largely separate choices. This paper places both across all regular blocks together, so the guessing penalty is balanced while enough equations remain for linearization. The abstract calls this a block-balancing principle for the whole guess–reduce–solve pipeline. The abstract gives no algorithm details or cost formulas.

Preconditions / Affected

The abstract names these applications, each with at least one parameter set estimated below its 128-bit target:

• Ferret (CCS 2020)
• Wolverine (IEEE S&P 2021)
• Committed VOLE (CCS 2025)

The largest loss is close to 67 bits. On PCG benchmarks, previous best attack costs improve by up to 29.77 bits over non-binary fields and up to 25.91 bits over binary fields. All revised 128-bit PCG parameter sets of Liu et al. (EUROCRYPT 2024) that the authors evaluated have estimated attack costs below 2^111 field operations.

Caveats

These are cost estimates, not demonstrated key or secret recovery. The abstract does not say which parameter sets fall short, and it gives no mitigation or replacement parameters. Check the full paper for the per-set figures before judging any deployment.