Attacking and defending the McEliece cryptosystem

Daniel J. Bernstein; Tanja Lange; Christiane Peters

doi:10.1007/978-3-540-88403-3_3

Attacking and defending the McEliece cryptosystem

Daniel J. Bernstein
, Tanja Lange
, Christiane Peters

University of Illinois at Chicago
Eindhoven University of Technology

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

This paper presents several improvements to Stern's attack on the McEliece cryptosystem and achieves results considerably better than Canteaut et al. This paper shows that the system with the originally proposed parameters can be broken in just 1400 days by a single 2.4GHz Core 2 Quad CPU, or 7 days by a cluster of 200 CPUs. This attack has been implemented and is now in progress. This paper proposes new parameters for the McEliece and Niederreiter cryptosystems achieving standard levels of security against all known attacks. The new parameters take account of the improved attack; the recent introduction of list decoding for binary Goppa codes; and the possibility of choosing code lengths that are not a power of 2. The resulting public-key sizes are considerably smaller than previous parameter choices for the same level of security. © 2008 Springer Berlin Heidelberg.
Keyword: list decoding binary Goppa code,Stern attack,minimal weight code word,MATHEMATICS,Quantum cryptography,Decoding,McEliece cryptosystem,security analysis,Codes (symbols),ALGORITHM,Cryptography,Technical presentations,COMPUTER,CODES

Original language	English
Title of host publication	PROCEEDINGS OF POST-QUANTUM CRYPTOGRAPHY
Volume	Volume 5299
Publisher	Springer Verlag
Publication date	2008
Pages	31-46
ISBN (Print)	978-35-40-88402-6
DOIs	https://doi.org/10.1007/978-3-540-88403-3_3
Publication status	Published - 2008
Externally published	Yes
Event	2nd International Workshop on Post-Quantum Cryptography - , United States Duration: 17 Oct 2008 → 19 Oct 2008 Conference number: 2

Workshop

Workshop	2nd International Workshop on Post-Quantum Cryptography
Number	2
Country/Territory	United States
Period	17/10/2008 → 19/10/2008

Series	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	Volume 5299 LNCS

Access to Document

10.1007/978-3-540-88403-3_3

OpenUrl availability

Check availability in DTU Findit

Cite this

@inproceedings{a476e516a9134c3cbbc23e25af7e4a06,

title = "Attacking and defending the McEliece cryptosystem",

abstract = "This paper presents several improvements to Stern's attack on the McEliece cryptosystem and achieves results considerably better than Canteaut et al. This paper shows that the system with the originally proposed parameters can be broken in just 1400 days by a single 2.4GHz Core 2 Quad CPU, or 7 days by a cluster of 200 CPUs. This attack has been implemented and is now in progress. This paper proposes new parameters for the McEliece and Niederreiter cryptosystems achieving standard levels of security against all known attacks. The new parameters take account of the improved attack; the recent introduction of list decoding for binary Goppa codes; and the possibility of choosing code lengths that are not a power of 2. The resulting public-key sizes are considerably smaller than previous parameter choices for the same level of security. {\textcopyright} 2008 Springer Berlin Heidelberg. Keyword: list decoding binary Goppa code,Stern attack,minimal weight code word,MATHEMATICS,Quantum cryptography,Decoding,McEliece cryptosystem,security analysis,Codes (symbols),ALGORITHM,Cryptography,Technical presentations,COMPUTER,CODES",

author = "Bernstein, \{Daniel J.\} and Tanja Lange and Christiane Peters",

year = "2008",

doi = "10.1007/978-3-540-88403-3\_3",

language = "English",

isbn = "978-35-40-88402-6",

volume = "Volume 5299",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

number = "Volume 5299 LNCS",

pages = "31--46",

booktitle = "PROCEEDINGS OF POST-QUANTUM CRYPTOGRAPHY",

address = "Germany",

note = "2nd International Workshop on Post-Quantum Cryptography, PQCrypto ; Conference date: 17-10-2008 Through 19-10-2008",

}

Bernstein, DJ, Lange, T & Peters, C 2008, Attacking and defending the McEliece cryptosystem. in PROCEEDINGS OF POST-QUANTUM CRYPTOGRAPHY. vol. Volume 5299, Springer Verlag, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. Volume 5299 LNCS, pp. 31-46, 2nd International Workshop on Post-Quantum Cryptography, Ohio, United States, 17/10/2008. https://doi.org/10.1007/978-3-540-88403-3_3

Attacking and defending the McEliece cryptosystem. / Bernstein, Daniel J.; Lange, Tanja; Peters, Christiane.
PROCEEDINGS OF POST-QUANTUM CRYPTOGRAPHY. Vol. Volume 5299 Springer Verlag, 2008. p. 31-46 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); No. Volume 5299 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Attacking and defending the McEliece cryptosystem

AU - Bernstein, Daniel J.

AU - Lange, Tanja

AU - Peters, Christiane

N1 - Conference code: 2

PY - 2008

Y1 - 2008

N2 - This paper presents several improvements to Stern's attack on the McEliece cryptosystem and achieves results considerably better than Canteaut et al. This paper shows that the system with the originally proposed parameters can be broken in just 1400 days by a single 2.4GHz Core 2 Quad CPU, or 7 days by a cluster of 200 CPUs. This attack has been implemented and is now in progress. This paper proposes new parameters for the McEliece and Niederreiter cryptosystems achieving standard levels of security against all known attacks. The new parameters take account of the improved attack; the recent introduction of list decoding for binary Goppa codes; and the possibility of choosing code lengths that are not a power of 2. The resulting public-key sizes are considerably smaller than previous parameter choices for the same level of security. © 2008 Springer Berlin Heidelberg. Keyword: list decoding binary Goppa code,Stern attack,minimal weight code word,MATHEMATICS,Quantum cryptography,Decoding,McEliece cryptosystem,security analysis,Codes (symbols),ALGORITHM,Cryptography,Technical presentations,COMPUTER,CODES

AB - This paper presents several improvements to Stern's attack on the McEliece cryptosystem and achieves results considerably better than Canteaut et al. This paper shows that the system with the originally proposed parameters can be broken in just 1400 days by a single 2.4GHz Core 2 Quad CPU, or 7 days by a cluster of 200 CPUs. This attack has been implemented and is now in progress. This paper proposes new parameters for the McEliece and Niederreiter cryptosystems achieving standard levels of security against all known attacks. The new parameters take account of the improved attack; the recent introduction of list decoding for binary Goppa codes; and the possibility of choosing code lengths that are not a power of 2. The resulting public-key sizes are considerably smaller than previous parameter choices for the same level of security. © 2008 Springer Berlin Heidelberg. Keyword: list decoding binary Goppa code,Stern attack,minimal weight code word,MATHEMATICS,Quantum cryptography,Decoding,McEliece cryptosystem,security analysis,Codes (symbols),ALGORITHM,Cryptography,Technical presentations,COMPUTER,CODES

U2 - 10.1007/978-3-540-88403-3_3

DO - 10.1007/978-3-540-88403-3_3

M3 - Article in proceedings

SN - 978-35-40-88402-6

VL - Volume 5299

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 31

EP - 46

BT - PROCEEDINGS OF POST-QUANTUM CRYPTOGRAPHY

PB - Springer Verlag

T2 - 2nd International Workshop on Post-Quantum Cryptography

Y2 - 17 October 2008 through 19 October 2008

ER -

Bernstein DJ, Lange T, Peters C. Attacking and defending the McEliece cryptosystem. In PROCEEDINGS OF POST-QUANTUM CRYPTOGRAPHY. Vol. Volume 5299. Springer Verlag. 2008. p. 31-46. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); No. Volume 5299 LNCS). doi: 10.1007/978-3-540-88403-3_3

Attacking and defending the McEliece cryptosystem

Abstract

Workshop

Access to Document

OpenUrl availability

Fingerprint

Cite this