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

Portuguese

O campo de revisão de parâmetros de parâmetro de campo revisão (RSD) problema é uma variante estruturada da síndrome clássica de decodificação e subjacente a um número crescente de estruturas criptográficas de ataque eficazes, incluindo protocolos de conhecimento zero, geradores de correlação pseudorandom e MPC nas assinaturas de parâmetro de cabeçalho. Embora RSD é geralmente acreditado para ser computacionalmente difícil, trabalhos recentes mostraram que ataques algébricos refinados podem ultrapassar a decodificação de conjuntos de informações em regimes de parâmetro de segurança importantes. Construindo nesta linha de trabalho, revisamos a dureza concreta de RSD e mostramos que muitos conjuntos de parâmetros amplamente usados são substancialmente mais

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