### Abstract

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. © 2011 International Association for Cryptologic Research.

Keyword: Quantum computers,post-quantum cryptography,information-set decoding,Quantum cryptography,Decoding,Public key cryptography,McEliece cryptosystem,collision decoding,Quantum optics,Niederreiter cryptosystem,attacks,Post quantum cryptography

Keyword: Quantum computers,post-quantum cryptography,information-set decoding,Quantum cryptography,Decoding,Public key cryptography,McEliece cryptosystem,collision decoding,Quantum optics,Niederreiter cryptosystem,attacks,Post quantum cryptography

Original language | English |
---|---|

Book series | Lecture Notes in Computer Science |

Volume | 6841 LNCS |

Pages (from-to) | 743-760 |

ISSN | 0302-9743 |

DOIs | |

Publication status | Published - 2011 |

Externally published | Yes |

Event | Annual International Cryptology Conference - Duration: 1 Jan 2011 → … Conference number: 31 |

### Conference

Conference | Annual International Cryptology Conference |
---|---|

Number | 31 |

Period | 01/01/2011 → … |

## Cite this

Bernstein, D. J., Lange, T., & Peters, C. (2011). Smaller decoding exponents: Ball-collision decoding.

*Lecture Notes in Computer Science*,*6841 LNCS*, 743-760. https://doi.org/10.1007/978-3-642-22792-9_42