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

Vietnamese

Các mục tiêu phân giải hội chứng tham số thông thường (RSD) là một biến thể có cấu trúc của hội chứng cổ điển và là nền tảng của một số lượng ngày càng tăng của các cấu trúc mã hóa hiệu quả, bao gồm các giao thức kiến thức không, máy phát điện tương quan pseudorandom và MPC trong các chữ ký cụ thể đầu. Mặc dù RSD thường được cho là khó khăn về mặt tính toán, các công trình gần đây đã chỉ ra rằng các cuộc tấn công algebraic có thể vượt trội hơn các cuộc tấn công thông tin trên các chế độ tham số an ninh RSD quan trọng. Xây dựng trên dòng công việc này, chúng tôi xem xét lại độ cứng cụ thể của RSD và cho thấy rằng nhiều tập hợp tham số được sử dụng rộng rãi là dễ dàng hơn để giải quyết so với trước đây ước tính. Sự cải thiện này bắt nguồn từ một cuộc tấn công algebraic

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