Paper 2023/247 Original: eprint.iacr.org/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 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.
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2023-10-09: last updated
- 2023-02-21: published
- Short URL
- https://ia.cr/2023/247
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2023/247}
}