Classic McEliece: the oldest code-based encryption idea and where it stands

Short answer: Classic McEliece is a code-based public-key encryption system built on an idea from 1978. Its authors point to a security level that has stayed stable despite decades of attack papers. NIST reviewed it in the fourth round of its post-quantum process and did not select it. The report says interest was limited and that more standards add complexity to protocols and migration.

Where the idea comes from

According to the Classic McEliece submission document, the first code-based public-key encryption system was introduced in 1978. The public key specifies a random binary Goppa code. A ciphertext is a codeword plus random errors. The private key allows efficient decoding, which means extracting the codeword from the ciphertext and removing the errors. The system was designed to be one-way against an attacker who sees only the ciphertext and public key.

The authors' security argument

The submission says the security level of the McEliece system has remained remarkably stable despite dozens of attack papers over 45 years. It adds that the original parameters were designed for only 2^64 security, but that the system scales up to "overkill" parameters that provide ample margin against advances in computer technology, including quantum computers. These are the designers' claims, and we have not verified them. A long record without a practical break is encouraging, but it is not a proof.

What the project publishes

The Classic McEliece website says the official definition is the cryptosystem specification. It also publishes a design rationale, a separate definition of a variant with plaintext confirmation, and a statement of that variant's advantages and disadvantages. A computer-executable package is meant for testing implementations in many languages, including checksum tests for each of the selected parameter sets.

What NIST said

NIST IR 8545 reports that in the fourth round NIST studied four key-establishment candidates: BIKE, Classic McEliece, HQC and SIKE. On Classic McEliece, the report says responses to an earlier request for feedback noted it may perform better than BIKE or HQC where a public key can be transferred once and then used for several encapsulations, such as file encryption and virtual private networks, because of its small ciphertext size and fast encapsulation and decapsulation. Some people were also interested because they see it as a conservative choice. However, the report says the interest expressed was limited and that having more standards to implement adds complexity to protocols and post-quantum migration.

The report includes a table of Classic McEliece key and ciphertext sizes. We do not reproduce the figures here, so check the report directly.

What this does not tell you

Based on the sources used here, Classic McEliece was not selected by NIST for standardization in that round. Other bodies may treat it differently, and the project itself refers to an ISO document. This article describes no deployment and does not recommend any product.

FAQ

What is Classic McEliece?

A code-based public-key encryption system based on a 1978 idea. The public key specifies a random binary Goppa code, and a ciphertext is a codeword plus random errors.

Why do its designers trust it?

They say its security level has remained remarkably stable despite dozens of attack papers over 45 years. This is the designers' claim.

Did NIST select it?

NIST studied it in the fourth round alongside BIKE, HQC and SIKE, and its report says it was not selected. HQC was chosen.

What did NIST see as its strengths?

Respondents noted a small ciphertext size and fast encapsulation and decapsulation, which may suit cases where one public key is reused, such as file encryption and VPNs.

Why was interest limited?

NIST's report says interest was limited, and that more standards to implement add complexity to protocols and migration.