Wild McEliece Incognito

Daniel J. Bernstein, Tanja Lange, Christiane Peters

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    Abstract

    The wild McEliece cryptosystem uses wild Goppa codes over nite elds to achieve smaller public key sizes compared to the original McEliece cryptosystem at the same level of security against all attacks known. However, the cryptosystem drops one of the condence-inspiring shields built into the original McEliece cryptosystem, namely a large pool of Goppa polynomials to choose from. This paper shows how to achieve almost all of the same reduction in key size while preserving this shield. Even if support splitting could be (1) generalized to handle an unknown support set and (2) sped up by a square-root factor, polynomial-searching attacks in the new system will still be at least as hard as information-set decoding. Furthermore, this paper presents a set of concrete cryptanalytic chal- lenges to encourage the cryptographic community to study the security of code-based cryptography. The challenges range through codes over F2;F3; : : : ;F32, and cover two dierent levels of how much the wildness is hidden.
    Original languageEnglish
    Title of host publicationLecture Notes in Computer Science
    Volume7071
    PublisherSpringer
    Publication date2011
    Pages244-254
    DOIs
    Publication statusPublished - 2011
    EventFourth International Conference on Post-Quantum Cryptography - Taipei, Taiwan
    Duration: 1 Jan 2011 → …

    Conference

    ConferenceFourth International Conference on Post-Quantum Cryptography
    CityTaipei, Taiwan
    Period01/01/2011 → …

    Keywords

    • List decoding
    • McEliece cryptosystem
    • Goppa codes
    • Wild Goppa codes
    • Niederreiter cryptosystem

    Fingerprint Dive into the research topics of 'Wild McEliece Incognito'. Together they form a unique fingerprint.

    Cite this