Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Smaller Decoding Exponents: Ball-Collision Decoding
verfasst von : Daniel J. Bernstein, Tanja Lange, Christiane Peters
Erschienen in: Advances in Cryptology – CRYPTO 2011
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
(
α
(
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
.