A New Sieving-Style Information-Set Decoding Algorithm

ePrint Report: A New Sieving-Style Information-Set Decoding Algorithm

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 …

algorithm code cryptography decoding eprint report information nguyen nist novel partial post-quantum problem process quantum random report solution standardization syndrome thomas