[Resource Topic] 2023/247: A New Sieving-Style Information-Set Decoding Algorithm

Welcome to the resource topic for 2023/247

A New Sieving-Style Information-Set Decoding Algorithm

Authors: Qian Guo, Thomas Johansson, Vu Nguyen


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 for solving the syndrome decoding problem. The essential idea is to keep a list of weight-2p solution vectors to a partial syndrome decoding problem and then create new vectors by finding pairs of vectors that collide in p positions.
By increasing the parity-check condition by one position and then iteratively repeating this process, we find the final solution(s). We show that while being competitive in terms of performance, our novel algorithm requires significantly less memory compared to other ISD variants. Also, in the case of problems with very low relative weight, it seems to outperform all previous algorithms. In particular, for code-based candidates BIKE and HQC, the algorithm has lower bit complexity than the previous best results.

ePrint: https://eprint.iacr.org/2023/247

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .