Paper 2022/1328

Revisiting Nearest-Neighbor-Based Information Set Decoding

Abstract

The syndrome decoding problem lies at the heart of code-based cryptographic constructions. Information Set Decoding (ISD) algorithms are commonly used to assess the security of these systems. The most efficient ISD algorithms rely heavily on nearest neighbor search techniques. However, the runtime result of the fastest known ISD algorithm by Both-May (PQCrypto '17) was recently challenged by Carrier et al. (Asiacrypt '22), which introduce themselves a new technique called RLPN decoding which yields improvements over ISD for codes with small rates $\frac{k}{n}\leq 0.3$. In this work we first revisit the Both-May algorithm, by giving a clean exposition and a corrected analysis. We confirm the claim by Carrier et al. that the initial analysis is flawed. However, we find that the algorithm still (slightly) improves on time complexity and significantly improves on memory complexity over previous algorithms. Our first main contribution is therefore to set the correct baseline for further improvements. As a second main contribution we then show how to improve on the Both-May algorithm, lowering the worst case running time in the full distance decoding setting to $2^{0.0948n}$. We obtain even higher time complexity gains for small rates, shifting the break even point with RLPN decoding to rate $\frac{k}{n}=0.25$. Moreover, we significantly improve on memory for all rates $\frac{k}{n}<0.5$. We obtain our improvement by introducing a novel technique to combine the list construction step and the list filtering step commonly applied by ISD algorithms. Therefore we treat the nearest neighbor routine in a non-blackbox fashion which allows us to embed the filtering into the nearest neighbor search. In this context we introduce the fixed-weight nearest neighbor problem, and propose a first algorithm to solve this problem. Besides resulting in an improved decoding algorithm this opens the direction for further improvements, since any faster algorithm for solving this fixed-weight nearest neighbor variant is likely to lead to further improvements of our ISD algorithm.