Smaller decoding exponents : ball-collision decoding

D.J. Bernstein, T. Lange, C.P. Peters

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

106 Citaties (SciVal)


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¿¿¿R and w/n¿¿¿W as n¿¿¿8. Before this paper, the best upper bound known on the exponent a(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.
Originele taal-2Engels
TitelAdvances in Cryptology - CRYPTO 2011 (31st Annual International Cryptology Conference, Santa Barbara CA, USA, August 14-18, 2011. Proceedings)
RedacteurenP. Rogaway
Plaats van productieBerlin
ISBN van geprinte versie978-3-642-22791-2
StatusGepubliceerd - 2011

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Duik in de onderzoeksthema's van 'Smaller decoding exponents : ball-collision decoding'. Samen vormen ze een unieke vingerafdruk.

Citeer dit