Conference paper
Smaller Decoding Exponents: Ball-Collision Decoding
Very few public-key cryptosystems are known that can encrypt and decrypt in time b2 + o(1) with conjectured security level 2b 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(α(R,W) + o(1))n if k/n → R and w/n → W as n → ∞. Before this paper, the best upper bound known on the exponent α(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.
Language: | English |
---|---|
Publisher: | Springer Berlin Heidelberg |
Year: | 2011 |
Pages: | 743-760 |
Proceedings: | Annual Cryptology Conference |
ISBN: | 3642227910 , 3642227929 , 9783642227912 and 9783642227929 |
Types: | Conference paper |
DOI: | 10.1007/978-3-642-22792-9_42 |