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].

94A60 Cryptography
Full Text: DOI