# zbMATH — the first resource for mathematics

Smaller decoding exponents: ball-collision decoding. (English) Zbl 1287.94053
Rogaway, Phillip (ed.), Advances in cryptology – CRYPTO 2011. 31st annual cryptology conference, Santa Barbara, CA, USA, August 14–18, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22791-2/pbk). Lecture Notes in Computer Science 6841, 743-760 (2011).
Summary: 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 \rightarrow R$$ and $$w/n \rightarrow W$$ as $$n \rightarrow \infty$$.
Before this paper, the best upper bound known on the exponent $$\alpha (R,W)$$ was the exponent of an attack introduced by J. Stern in 1989 [Coding theory and applications, Proc. 3rd Int. Colloq., Toulon/France 1988, Lect. Notes Comput. Sci. 388, 106–113 (1989; Zbl 0678.94006)]. 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$$.
For the entire collection see [Zbl 1219.94002].

##### MSC:
 94A60 Cryptography
Full Text: