CLASSIC McELIECE

Part 1 of 3 · plain-language model + the real spec underneath it
SRC: ETSI TR 103 823 ↗
01 · Origins

A scheme from 1978

Classic McEliece is based on a public-key cryptosystem developed by Robert J. McEliece in 1978. First published in a short paper titled "A Public-Key Cryptosystem Based on Algebraic Coding Theory" for NASA's Jet Propulsion Laboratory, it is one of the oldest known public-key encryption schemes. Unlike RSA (published around the same time), McEliece's scheme has never been broken by quantum algorithms, making it a leading candidate for post-quantum cryptography today.

02 · Core definitions

Key concepts

Some of the advanced cryptographic jargon you'll encounter throughout this walkthrough, simplified:

Security Models
  • OW-CPA Secure: "One-Way Chosen Plaintext Attack". An attacker can encrypt messages but can't reverse the math to decrypt them. However, they might be able to tamper with the ciphertext in transit. (The inner layer).
  • CCA Secure: "Chosen Ciphertext Attack". The gold standard. An attacker can't decrypt, and if they try to tamper with the ciphertext, the receiver will instantly detect it and reject the message. (The outer layer).
The FO Transform
  • Fujisaki-Okamoto Transform: A clever mathematical wrapper. It takes a scheme that is only OW-CPA secure (weak against tampering) and upgrades it to be fully CCA secure. It does this by forcing the receiver to re-encrypt the decrypted message and check if it matches the original ciphertext.
The Math Foundation
  • Binary Goppa Code: A type of error-correcting code used in telecommunications to fix static or noise in transmissions. McEliece cleverly turns this into cryptography by adding "noise" (errors) on purpose, which only the private key holder can correct.

The formal entities

Before diving into analogies, here are the formal mathematical entities that power the McEliece scheme. These exact terms will appear in the Step-by-Step Demo (Part 3).

Private Elements
  • g(X): A random irreducible polynomial (degree t). This is the core secret trapdoor.
  • α (Alpha): A sequence of n distinct elements from a finite field. These act as "secret addresses".
  • Together, g(X) and α form the private key, allowing efficient error correction.
Public Matrix
  • H: The public parity-check matrix. It's a scrambled version of a private matrix.
  • The sender uses H to encrypt their message. Without the private key, H looks completely random and is computationally useless for decoding.
Vectors & Ciphertext
  • c: A valid plaintext codeword. Appears in Part 3 · Step 4 · Stage A as c = [3, 6, 1, 0].
  • e: An error vector containing exactly t errors. Appears in Part 3 · Step 4 · Stage B as e = [1, 0, 1, 0].
  • y = c + e (mod 7): The corrupted ciphertext. Called y = c ⊕ e in binary schemes — same idea, just addition mod 7 in the demo. Appears in Part 3 · Step 4 · Stage B as the transmitted vector.
  • s = H·yᵀ: The syndrome. Used by the receiver to locate the errors. Appears in Part 3 · Step 4 · Stage C and is the C₀ input to PKE.Dec in Step 6.
03 · The idea, in one story

🎂 The glitter-and-vacuum trick

🧁

You want to mail a secret recipe. So you sprinkle it with a very specific, deliberate pattern of glitter enough to make it unreadable to anyone who intercepts it.

Before you ever mailed anything, you secretly gave your friend a custom vacuum built for exactly that glitter pattern. They run it once and the recipe reappears instantly.

A snoop with no vacuum has to guess, speck by speck, which parts are glitter and at real-world scale, that guess is computationally hopeless.

04 · Story terms → spec terms

How the analogy maps to the real notation

StorySpec objectRole
Your secret glitter recipeg(X), αIrreducible polynomial + n distinct field elements (the private key)
The scrambled public mailbox specH (or H′)Public parity-check matrix, published openly
The custom vacuumGoppa decoding algorithmOnly works because it knows g(X), α
The glitter itselfe (weight t)Random error vector added on purpose
The glittery card that gets mailedc = H·eᵀCiphertext the syndrome, not the message directly
Snoop's impossible guessing gameInformation Set DecodingBest known generic attack
05 · Inner layer

McEliece.PKE : the trapdoor itself

PK = Public Key — shared openly, anyone can encrypt
SK = Secret Key — kept private, only the owner can decrypt

This layer is the raw mathematical trapdoor — the "glitter trick" from Section 03. It has three operations: making the keys, locking data, and unlocking data.

① KeyGen() — Making the keys

The owner runs this once, in private, to create their key pair.

  1. Pick the secret recipe — choose a random irreducible polynomial g(X) and a list of secret positions α₁…αₙ. Together these form the SK (Secret Key).
  2. Build a private cheat-sheet — use g(X) and α to construct a private error-correcting matrix.
  3. Scramble it — mathematically shuffle the matrix until it looks random to anyone who doesn't know the recipe. The result is the PK (Public Key) H′.
  4. Publish H′ — anyone can now use it to send a locked message. (If the scrambling step fails, just restart — this is a known quirk of the scheme.)
② Enc(pk, e) — Locking

The sender runs this using only the public key. No secret needed.

  1. Load the public cheat-sheet — read the published PK H′ and reconstruct the full matrix H.
  2. Choose the glitter — pick a random error vector e: a pattern of deliberate "mistakes" to add to the data.
  3. Lock it — compute c = H · eᵀ. This mixes the glitter pattern with the public cheat-sheet in a way that's easy to do but nearly impossible to undo without the secret recipe.
  4. Send c — the locked output (ciphertext) is transmitted. The glitter pattern e stays secret.
③ Dec(sk, c) — Unlocking

Only the owner can run this, because only they have the SK.

  1. Expand the ciphertext — pad c into the full n-bit format the decoder expects.
  2. Run the vacuum — use the secret recipe (g(X), α) to run the Goppa error-correcting algorithm. It finds and removes the hidden glitter pattern.
  3. Recover e — the exact error vector the sender chose is revealed.
  4. If no match, signal failure (⊥) — if the data is too corrupted or was tampered with, no valid pattern exists and decryption cleanly fails rather than producing garbage.
💡

Why does this encrypt a glitter pattern (e) instead of the actual message? Because the math only supports hiding short error vectors — not arbitrary messages. The outer layer (Section 07) solves this: it uses e as a shared secret to derive a full encryption key, which is then used to encrypt any message you like.

06 · What the spec actually builds

Two layers, wrapped around each other in a "Russian Doll" Design

Classic McEliece doesn't just use the math trapdoor directly. It wraps the trapdoor inside a strict security checkpoint. Think of it like a vault inside a highly secure room.

OUTER LAYER: THE KEM CHECKPOINT (CCA Secure)

This layer doesn't do the encryption itself. Instead, it carefully checks if the person sending the message actually followed the rules, preventing attackers from tricking the system with corrupted data.

INNER LAYER: THE PKE TRAPDOOR (OW-CPA Secure)

This is the raw McEliece math (the glitter trick). It's incredibly hard to break by guessing, but on its own, it's vulnerable to tampering.

The Secret Key (g(X), α)
The Goppa-code math at the very center
07 · Outer layer

How the Security Checkpoint works

The outer layer uses the Fujisaki-Okamoto Transform. Its entire job is to agree on a shared Session Key without an attacker manipulating the process.

📤

Sender's Job

  • Pick a secret: Choose a random error vector (the glitter).
  • Lock it up: Encrypt the secret using the Inner PKE layer.
  • Take a fingerprint: Create a digital fingerprint (Hash) of the secret.
  • Send them both: Transmit the locked secret and the fingerprint to the receiver.
📥

Receiver's Checkpoint

  • Unlock it: Use the private key to decode and reveal the secret.
  • Check the lock: Re-encrypt the secret. Does it perfectly match the locked version sent by the sender?
  • Check the fingerprint: Hash the secret. Does it perfectly match the sender's fingerprint?
  • Derive the key: If everything matches, generate a shared Session Key. If a check fails, quietly generate a fake key instead of returning an error.
🛡️

The Genius Move: By generating a fake key instead of returning a "Decryption Failed" error, the system gives the attacker zero feedback. The attacker cannot tell if they guessed wrong or if the system rejected their tampered message, making chosen-ciphertext attacks impossible.

08 · Table 3

Standardized parameter sets

SetExtension Degree (m)Code Length (n)Error Weight (t)Claimed security
mceliece348864123,48864Category 1
mceliece460896134,60896Category 3
mceliece6960119136,960119Category 5
mceliece6688128136,688128Category 5
mceliece8192128138,192128Category 5
09 · Table 4

Key & ciphertext sizes

SetPublic keyPrivate keyCiphertext
mceliece348864261,120 B6,452 B128 B
mceliece460896524,160 B13,568 B188 B
mceliece69601191,044,992 B13,892 B240 B
mceliece66881281,047,319 B13,908 B226 B
mceliece81921281,357,824 B14,080 B240 B
Public key
1,044,992 B
Private key
13,892 B
Ciphertext
240 B
bars scaled by log₁₀(bytes) — mceliece6960119 · linearly, the ciphertext bar would be invisible next to the public key
10 · Table 5

Estimated classical security (message recovery)

SetBits of security
mceliece348864140
mceliece460896181
mceliece6688128257
mceliece6960119258
mceliece8192128294

Estimated against information-set-decoding attacks (the formal name for the snoop's brute-force guessing game). Key-recovery attacks aren't costed separately, since they're believed to be strictly harder than message recovery.

11 · Table 6

Performance

Figures for mceliece348864 (systematic), single core, 3.5 GHz Xeon E3-1275 v3.

KeyGen
58.0M cyc
Enc
44.3K cyc
Dec
134.7K cyc
bars scaled by log₁₀(cycles), KeyGen is ~3 orders of magnitude slower than Enc/Dec, matching "hard to build the trapdoor, cheap to use it"