Newest papers

Regular Syndrome Decoding Is Easier Than Previously Estimated

Jiseung Kim, Minkyu Kim, Changmin Lee, Hochang Lee · 2026 · arXiv

DOI: 10.48550/arXiv.2610.29175 · open-access PDF

Russian

Проблема регулярного расшифровки синдрома (RSD) является структурированным вариантом классического расшифровки синдрома и лежит в основе растущего числа эффективных криптографических конструкций, включая протоколы нулевых знаний, генераторы корреляции псевдорезультатов и MPC в подписях головки. Хотя RSD обычно считается вычислительно-трудным, последние работы показали, что алгебраические атаки могут превосходить расшифровку наборов информации на важных параметрических режимах RSD. Основываясь на этой линии работы, мы пересматриваем конкретную жесткость RSD и показываем, что многие широко используемые наборы параметров существенно отличаются

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 ea

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

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