Paper 2010/585

Smaller decoding exponents: ball-collision decoding

Daniel J. Bernstein, Tanja Lange, and Christiane Peters

Abstract

Very few public-key cryptosystems are known that can encrypt and decrypt in time b^(2+o(1)) with conjectured security level 2^b against conventional computers and quantum computers. The oldest of these systems is the classic McEliece code-based cryptosystem. The best attacks known against this system are generic decoding attacks that treat McEliece’s hidden binary Goppa codes as random linear codes. A standard conjecture is that the best possible w-error-decoding attacks against random linear codes of dimension k and length n take time 2^((alpha(R,W)+o(1))n) if k/n goes to R and w/n goes to W as n goes to infinity. Before this paper, the best upper bound known on the exponent alpha(R, W) was the exponent of an attack introduced by Stern in 1989. This paper introduces “ball-collision decoding” and shows that it has a smaller exponent for each (R, W): the speedup from Stern’s algorithm to ball-collision decoding is exponential in n.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
McEliece cryptosystemNiederreiter cryptosystempost-quantum cryptographyattacksinformation-set decodingcollision decoding
Contact author(s)
c p peters @ tue nl
History
2011-03-07: last of 2 revisions
2010-11-18: received
See all versions
Short URL
https://ia.cr/2010/585
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/585,
      author = {Daniel J.  Bernstein and Tanja Lange and Christiane Peters},
      title = {Smaller decoding exponents:  ball-collision decoding},
      howpublished = {Cryptology ePrint Archive, Paper 2010/585},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/585}},
      url = {https://eprint.iacr.org/2010/585}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.