Paper 2023/247

A New Sieving-Style Information-Set Decoding Algorithm

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

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 problems with very low relative weight, it seems to significantly outperform all previous algorithms. In particular, for code-based candidates BIKE and HQC, the algorithm has lower bit complexity than the previous best results.

Note: - Revise results tables. - Fix Section 4.2 (duplicate vectors). - Trimming various sections for readability. - New figures about time-memory tradeoffs. - Discussion on our attack regarding DOOM. -Adding appendix. - Fixed typos/references/citations.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
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
History
2023-05-26: revised
2023-02-21: received
See all versions
Short URL
https://ia.cr/2023/247
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/247,
      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{https://eprint.iacr.org/2023/247}},
      url = {https://eprint.iacr.org/2023/247}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.