Demonstrates enhanced decoding efficiency in code-based cryptosystems, suggesting better security assessment methods.
The majority of code-based cryptosystems are designed based on the syndrome decoding (SD) problems. The most effective attacks against SD problems employ information set decoding (ISD) algorithms. On EUROCRYPT 2023, Esser and Zweydinger presented a significant time-memory trade-off for the ISD algorithm. In this paper, we propose an improved ISD algorithm by combining Esser-Zweydinger algorithm and the nearest neighbor technique. Then, we apply the improved algorithm to reduce the memory of the depth-2 Both-May algorithm (2017 WCC) from O (20.0282n ) O ( 2 0.0282 n ) to O (20.0249n ) O ( 2 0.0249 n ) while keeping its time complexity constant at O (20.0492n ) O ( 2 0.0492 n ) , where n denotes the length of a binary linear code. Furthermore, we consider the quantum version of the improved algorithm and derive an asymptotic time complexity of O (20.057866n ) O ( 2 0.057866 n ) , which is lower than that of O (20.058660n ) O ( 2 0.058660 n ) from the quantum BJMM algorithm if memory consumption is not limited. In addition, we use the improved algorithm to reestimate the security level of HQC, BIKE, and Classic McEliece, respectively. In particular, for the parameters of Classic McEliece, the security levels estimated by our algorithm are 3 ~ ∼ 6 bits lower than Esse-Zweydinger’s results.
No takes yet. Share an insight, caveat, or question.
Li et al. (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: