Smaller decoding exponents: Ball-collision decoding

Publication: Research - peer-reviewConference article – Annual report year: 2011

Without internal affiliation

  • Author: Bernstein, Daniel J.

    University of Illinois at Chicago, Department of Computer Science

  • Author: Lange, Tanja

    Technische Universiteit Eindhoven, Netherlands

  • Author: Peters, Christiane

    Unknown

View graph of relations

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
Original languageEnglish
JournalLecture Notes in Computer Science
Publication date2011
Volume6841 LNCS
Pages743-760
ISSN0302-9743
DOIs
StatePublished

Conference

ConferenceAnnual International Cryptology Conference
Number31
Period01/01/11 → …
CitationsWeb of Science® Times Cited: No match on DOI
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 6461959