Newest papers

Regular Syndrome Decoding Is Easier Than Previously Estimated

Jiseung Kim, Minkyu Kim, Changmin Lee, Hochang Lee · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.29175 · cited by 0 works (OpenAlex) · open-access PDF

French

Le problème du paramètre paramétrique régulier d'évaluation du champ (RSD) est une variante structurée du décodage du syndrome classique et sous-tend un nombre croissant de structures cryptographiques d'attaque efficaces, y compris les protocoles de connaissances zéro, les générateurs de corrélation pseudorandom et le MPC dans les signatures concrètes de la tête. Bien que RSD soit généralement considéré comme étant difficile à calculer, les travaux récents ont montré que les attaques algébriques ont dépassé le nombre d'attaques d'information sur des régimes de paramètre de sécurité importants. Construisant sur cette ligne de travail, nous revoyons la dureté concrète de la RSD et montrons que de nombreux ensembles de paramètres largement utilis

Machine translation (Meta M2M100); the English original follows.

Abstract

The 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. Although RSD is generally believed to be computationally hard, recent works have shown that algebraic attacks can outperform information set decoding on important RSD parameter regimes. Building on this line of work, we revisit the concrete hardness of RSD and show that many widely used parameter sets are substantially easier to solve than previously estimated. This improvement stems from a refined hybrid algebraic attack that exposes and removes a previously overlooked source of concrete complexity: the joint blockwise placement of zero coordinate guesses and syndrome based variable eliminations. Rather than treating the two guessing stages and linear elimination as largely separate choices, our method coordinates them across all regular blocks so that the guessing penalty is balanced while sufficient equations are retained for linearization. This gives a systematic block balancing principle for the entire guess reduce solve pipeline. We reassess several RSD based applications, including Ferret, Wolverine, and committed VOLE. Our estimates place at least one parameter set per application below its 128 bit target, with losses approaching 67 bits. On PCG benchmarks, we improve previous best attack costs by up to 29.77 and 25.91 bits over non binary and binary fields, respectively. Moreover, for the revised 128 bit PCG parameter sets of Liu et al. evaluated here, estimated attack costs are all below $2^{111}$ field operations. These results substantially revise the concrete security landscape of RSD and indicate that several existing parameter choices overestimate the hardness of their underlying RSD instances.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Decoding methods, Binary number, Algebraic number, Algorithm, Set (abstract data type), Cryptography

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange