Paper 2023/247

A New Sieving-Style Information-Set Decoding Algorithm

Qian Guo, Lund University
Thomas Johansson, Lund University
Vu Nguyen, Lund University

The problem of decoding random codes is a fundamental problem for code-based cryptography, including recent code-based candidates in the NIST post-quantum standardization process. In this paper, we present a novel sieving-style information-set decoding (ISD) algorithm, addressing the task of solving the syndrome decoding problem. Our approach involves maintaining a list of weight-$2p$ solution vectors to a partial syndrome decoding problem and then creating new vectors by identifying pairs of vectors that collide in $p$ positions. By gradually increasing the parity-check condition by one and repeating this process iteratively, we find the final solution(s). We show that our novel algorithm performs better than other ISDs in the memory-restricted scenario when applied to McEliece. Notably, in the case of problem instances with very low relative weight, it seems to significantly outperform all previous algorithms. In particular, for code-based candidate BIKE, the algorithm has lower bit complexity than the previous best results.

Note: - Fixed typos/references/citations. - Improved readability - Remove results for BIKE msg-recovery and HQC key-recovery.

Available format(s)
Attacks and cryptanalysis
Publication info
Code-based cryptographyNIST post-quantum standardizationInformation-Set DecodingClassic-McElieceBIKEHQC
Contact author(s)
qian guo @ eit lth se
thomas johansson @ eit lth se
vu nguyen @ eit lth se
2023-10-09: last of 2 revisions
2023-02-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Qian Guo and Thomas Johansson and Vu Nguyen},
      title = {A New Sieving-Style Information-Set Decoding Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2023/247},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.