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}\le 0.3$. In this work we first revisit the Both-May algorithm, by giving a clean exposition and a corrected analysis. In this context we confirm the result by Carrier et al. that the initial analysis is flawed and conclude with the same runtime exponent. Our work aims at fully substantiating the corrected runtime exponent by a detailed analysis. Furthermore, we show that the Both-May algorithm significantly improves on memory complexity over previous algorithms. Our first main contribution is therefore to give the correct perspective on the significance of the Both-May algorithm and to clarify any remaining doubts on the corrected baseline. As a second main contribution we detail a possible strategy for future improvements of the Both-May algorithm. This strategy is based on 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. Even though, our current analysis does not yet yield a gain in complexity over the Both-May algorithm, we point out different ways to further improve the proposed technique.

Note: In the previous version, the fixed-weight nearest-neighbor problem solved within the improved Both-May+ algorithm was using non-uniform input distributions. This did not allow for a direct application of the outlined algorithm to solve the fixed-weight variant. The current revision fixes this issue.