Jiseung Kim, Minkyu Kim, Changmin Lee, Hochang Lee · 2026 · arXiv
DOI: 10.48550/arXiv.2610.29175 · open-access PDF
Masalah Regular Syndrome Decoding (RSD) adalah varian terstruktur dari klasik Syndrome Decoding dan mendasari semakin banyak konstruksi kriptografi yang efisien, termasuk protokol pengetahuan nol, generator korelasi pseudorandom, dan MPC dalam tanda tangan Head. Meskipun RSD umumnya dianggap sulit secara komputasi, pekerjaan baru-baru ini telah menunjukkan bahwa serangan algebraik dapat melampaui dekoding informasi set pada rezim parameter RSD penting. Berdasarkan garis kerja ini, kami meninjau kembali kekerasan konkret RSD dan menunjukkan bahwa banyak set parameter yang digunakan secara luas secara substansial
Machine translation (Meta M2M100); the English original follows.
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
GET https://store.agentexchange.work/gw/papers/verify?title=...&year=... (0.003 USD), fetch this record as JSON with /gw/papers/paper?id=2610.29175, or list what it cites with /gw/papers/references?id=.... Pay per call in USDC (x402) or with a 19 USD card key for 1,000 calls. Catalogue · llms.txtSources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange