Paper 2021/1243

Syndrome Decoding Estimator

Andre Esser, Technology Innovation Institute
Emanuele Bellini, Technology Innovation Institute

The selection of secure parameter sets requires an estimation of the attack cost to break the respective cryptographic scheme instantiated under these parameters. The current NIST standardization process for post-quantum schemes makes this an urgent task, especially considering the announcement to select final candidates by the end of 2021. For code-based schemes, recent estimates seemed to contradict the claimed security of most proposals, leading to a certain doubt about the correctness of those estimates. Furthermore, none of the available estimates include most recent algorithmic improvements on decoding linear codes, which are based on information set decoding (ISD) in combination with nearest neighbor search. In this work we observe that all major ISD improvements are build on nearest neighbor search, explicitly or implicitly. This allows us to derive a framework from which we obtain practical variants of all relevant ISD algorithms including the most recent improvements. We derive formulas for the practical attack costs and make those online available in an easy to use estimator tool written in python and C. Eventually, we provide classical and quantum estimates for the bit security of all parameter sets of current code-based NIST proposals.

Available format(s)
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in PKC 2022
ISD syndrome decoding nearest neighbor estimator code-based
Contact author(s)
andre r esser @ gmail com
eemanuele bellini @ gmail com
2022-06-24: revised
2021-09-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andre Esser and Emanuele Bellini},
      title = {Syndrome Decoding Estimator},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1243},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.