Classic McEliece

Daniel J. Bernstein, Tung Chou, Tanja Lange, Ingo von Maurich, Rafael Misoczki, Ruben Niederhagen, Edoardo Persichetti, Christiane Peters, Peter Schwabe, Nicolas Sendrier, Jakub Szefer, Wen Wang

Research output: Other contributionAcademic

Abstract

The first code-based public-key cryptosystem was introduced in 1978 by McEliece. The public key specifies a random binary Goppa code. A ciphertext is a codeword plus random errors. The private key allows efficient decoding: extracting the codeword from the ciphertext, identifying and removing the errors.

The McEliece system was designed to be one-way (OW-CPA), meaning that an attacker cannot efficiently find the codeword from a ciphertext and public key, when the codeword is chosen randomly. The security level of the McEliece system has remained remarkably stable, despite dozens of attack papers over 40 years. The original McEliece parameters were designed for only 264 security, but the system easily scales up to "overkill" parameters that provide ample security margin against advances in computer technology, including quantum computers.

The McEliece system has prompted a tremendous amount of followup work. Some of this work improves efficiency while clearly preserving security: this includes a "dual" PKE proposed by Niederreiter, software speedups, and hardware speedups.

Furthermore, it is now well known how to efficiently convert an OW-CPA PKE into a KEM that is IND-CCA2 secure against all ROM attacks. This conversion is tight, preserving the security level, under two assumptions that are satisfied by the McEliece PKE: first, the PKE is deterministic (i.e., decryption recovers all randomness that was used); second, the PKE has no decryption failures for valid ciphertexts. Even better, very recent work suggests the possibility of achieving similar tightness for the broader class of QROM attacks. The risk that a hash-function-specific attack could be faster than a ROM or QROM attack is addressed by the standard practice of selecting a well-studied, high-security, "unstructured" hash function.
LanguageEnglish
TypeWebsite
StatePublished - 2017

Fingerprint

Hash functions
ROM
Quantum computers
Binary codes
Random errors
Cryptography
Decoding
Hardware

Cite this

Bernstein, D. J., Chou, T., Lange, T., von Maurich, I., Misoczki, R., Niederhagen, R., ... Wang, W. Classic McEliece
Bernstein, Daniel J. ; Chou, Tung ; Lange, Tanja ; von Maurich, Ingo ; Misoczki, Rafael ; Niederhagen, Ruben ; Persichetti, Edoardo ; Peters, Christiane ; Schwabe, Peter ; Sendrier, Nicolas ; Szefer, Jakub ; Wang, Wen. / Classic McEliece.
@misc{96ac923410c34ebd9d9a4f708ecd832a,
title = "Classic McEliece",
abstract = "The first code-based public-key cryptosystem was introduced in 1978 by McEliece. The public key specifies a random binary Goppa code. A ciphertext is a codeword plus random errors. The private key allows efficient decoding: extracting the codeword from the ciphertext, identifying and removing the errors.The McEliece system was designed to be one-way (OW-CPA), meaning that an attacker cannot efficiently find the codeword from a ciphertext and public key, when the codeword is chosen randomly. The security level of the McEliece system has remained remarkably stable, despite dozens of attack papers over 40 years. The original McEliece parameters were designed for only 264 security, but the system easily scales up to {"}overkill{"} parameters that provide ample security margin against advances in computer technology, including quantum computers.The McEliece system has prompted a tremendous amount of followup work. Some of this work improves efficiency while clearly preserving security: this includes a {"}dual{"} PKE proposed by Niederreiter, software speedups, and hardware speedups.Furthermore, it is now well known how to efficiently convert an OW-CPA PKE into a KEM that is IND-CCA2 secure against all ROM attacks. This conversion is tight, preserving the security level, under two assumptions that are satisfied by the McEliece PKE: first, the PKE is deterministic (i.e., decryption recovers all randomness that was used); second, the PKE has no decryption failures for valid ciphertexts. Even better, very recent work suggests the possibility of achieving similar tightness for the broader class of QROM attacks. The risk that a hash-function-specific attack could be faster than a ROM or QROM attack is addressed by the standard practice of selecting a well-studied, high-security, {"}unstructured{"} hash function.",
author = "Bernstein, {Daniel J.} and Tung Chou and Tanja Lange and {von Maurich}, Ingo and Rafael Misoczki and Ruben Niederhagen and Edoardo Persichetti and Christiane Peters and Peter Schwabe and Nicolas Sendrier and Jakub Szefer and Wen Wang",
year = "2017",
language = "English",
type = "Other",

}

Bernstein, DJ, Chou, T, Lange, T, von Maurich, I, Misoczki, R, Niederhagen, R, Persichetti, E, Peters, C, Schwabe, P, Sendrier, N, Szefer, J & Wang, W Classic McEliece.

Classic McEliece. / Bernstein, Daniel J.; Chou, Tung; Lange, Tanja; von Maurich, Ingo; Misoczki, Rafael; Niederhagen, Ruben; Persichetti, Edoardo; Peters, Christiane; Schwabe, Peter; Sendrier, Nicolas; Szefer, Jakub; Wang, Wen.

2017, Website.

Research output: Other contributionAcademic

TY - GEN

T1 - Classic McEliece

AU - Bernstein,Daniel J.

AU - Chou,Tung

AU - Lange,Tanja

AU - von Maurich,Ingo

AU - Misoczki,Rafael

AU - Niederhagen,Ruben

AU - Persichetti,Edoardo

AU - Peters,Christiane

AU - Schwabe,Peter

AU - Sendrier,Nicolas

AU - Szefer,Jakub

AU - Wang,Wen

PY - 2017

Y1 - 2017

N2 - The first code-based public-key cryptosystem was introduced in 1978 by McEliece. The public key specifies a random binary Goppa code. A ciphertext is a codeword plus random errors. The private key allows efficient decoding: extracting the codeword from the ciphertext, identifying and removing the errors.The McEliece system was designed to be one-way (OW-CPA), meaning that an attacker cannot efficiently find the codeword from a ciphertext and public key, when the codeword is chosen randomly. The security level of the McEliece system has remained remarkably stable, despite dozens of attack papers over 40 years. The original McEliece parameters were designed for only 264 security, but the system easily scales up to "overkill" parameters that provide ample security margin against advances in computer technology, including quantum computers.The McEliece system has prompted a tremendous amount of followup work. Some of this work improves efficiency while clearly preserving security: this includes a "dual" PKE proposed by Niederreiter, software speedups, and hardware speedups.Furthermore, it is now well known how to efficiently convert an OW-CPA PKE into a KEM that is IND-CCA2 secure against all ROM attacks. This conversion is tight, preserving the security level, under two assumptions that are satisfied by the McEliece PKE: first, the PKE is deterministic (i.e., decryption recovers all randomness that was used); second, the PKE has no decryption failures for valid ciphertexts. Even better, very recent work suggests the possibility of achieving similar tightness for the broader class of QROM attacks. The risk that a hash-function-specific attack could be faster than a ROM or QROM attack is addressed by the standard practice of selecting a well-studied, high-security, "unstructured" hash function.

AB - The first code-based public-key cryptosystem was introduced in 1978 by McEliece. The public key specifies a random binary Goppa code. A ciphertext is a codeword plus random errors. The private key allows efficient decoding: extracting the codeword from the ciphertext, identifying and removing the errors.The McEliece system was designed to be one-way (OW-CPA), meaning that an attacker cannot efficiently find the codeword from a ciphertext and public key, when the codeword is chosen randomly. The security level of the McEliece system has remained remarkably stable, despite dozens of attack papers over 40 years. The original McEliece parameters were designed for only 264 security, but the system easily scales up to "overkill" parameters that provide ample security margin against advances in computer technology, including quantum computers.The McEliece system has prompted a tremendous amount of followup work. Some of this work improves efficiency while clearly preserving security: this includes a "dual" PKE proposed by Niederreiter, software speedups, and hardware speedups.Furthermore, it is now well known how to efficiently convert an OW-CPA PKE into a KEM that is IND-CCA2 secure against all ROM attacks. This conversion is tight, preserving the security level, under two assumptions that are satisfied by the McEliece PKE: first, the PKE is deterministic (i.e., decryption recovers all randomness that was used); second, the PKE has no decryption failures for valid ciphertexts. Even better, very recent work suggests the possibility of achieving similar tightness for the broader class of QROM attacks. The risk that a hash-function-specific attack could be faster than a ROM or QROM attack is addressed by the standard practice of selecting a well-studied, high-security, "unstructured" hash function.

M3 - Other contribution

ER -

Bernstein DJ, Chou T, Lange T, von Maurich I, Misoczki R, Niederhagen R et al. Classic McEliece. 2017.