Welcome to the resource topic for 2023/247
Title:
A New Sieving-Style Information-Set Decoding Algorithm
Authors: Qian Guo, Thomas Johansson, Vu Nguyen
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 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 .