Paper 2023/247
A New Sieving-Style Information-Set Decoding Algorithm
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
-
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}
}
