A novel improved information set decoding algorithm via nearest neighbor search

Abstract The majority of code-based cryptosystems are designed based on the syndrome decoding (SD) problems. The most effective attacks against SD problems employ information set decoding (ISD) algorithms. On EUROCRYPT 2023, Esser and Zweydinger presented a significant time-memory trade-off for the ISD algorithm. In this paper, we propose an improved ISD algorithm by combining Esser-Zweydinger algorithm and the nearest neighbor technique. Then, we apply the improved algorithm to reduce the memory of the depth-2 Both-May algorithm (2017 WCC) from $$O\big (2^{0.0282n}\big )$$ O ( 2 0.0282 n )