Paper 2021/1243

Syndrome Decoding Estimator

Andre Esser and Emanuele Bellini

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Preprint. Minor revision.
Keywords
ISDsyndrome decodingnearest neighborestimatorcode-based
Contact author(s)
andre r esser @ gmail com
eemanuele bellini @ gmail com
History
2021-09-20: received
Short URL
https://ia.cr/2021/1243
License
Creative Commons Attribution
CC BY

BibTeX

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