Paper 2022/1328

Revisiting Nearest-Neighbor-Based Information Set Decoding

Andre Esser, Technology Innovation Institute
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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
representation techniquesyndrome decodingnearest neighbor searchcode-based cryptography
Contact author(s)
andre r esser @ gmail com
History
2023-02-17: revised
2022-10-06: received
See all versions
Short URL
https://ia.cr/2022/1328
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1328,
      author = {Andre Esser},
      title = {Revisiting Nearest-Neighbor-Based Information Set Decoding},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1328},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1328}},
      url = {https://eprint.iacr.org/2022/1328}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.