Paper 2009/414

Security Bounds for the Design of Code-based Cryptosystems

Matthieu Finiasz and Nicolas Sendrier

Abstract

Code-based cryptography is often viewed as an interesting ``Post-Quantum'' alternative to the classical number theory cryptography. Unlike many other such alternatives, it has the convenient advantage of having only a few, well identified, attack algorithms. However, improvements to these algorithms have made their effective complexity quite complex to compute. We give here some lower bounds on the work factor of idealized versions of these algorithms, taking into account all possible tweaks which could improve their practical complexity. The aim of this article is to help designers select durably secure parameters.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. This is an extended version (with additional proofs included) of the article from Asiacrypt 2009.
Keywords
computational syndrome decodinginformation set decodinggeneralized birthday algorithm
Contact author(s)
finiasz @ gmail com
History
2009-09-01: received
Short URL
https://ia.cr/2009/414
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/414,
      author = {Matthieu Finiasz and Nicolas Sendrier},
      title = {Security Bounds for the Design of Code-based Cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2009/414},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/414}},
      url = {https://eprint.iacr.org/2009/414}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.