PIPELINE SCHEMATIC

Part 2 of 3 · 8-step pipeline — mirrors the worked demo in Part 3 step-for-step

Owner / private key

KEM layer (outer)

Attacker — fails

Receiver — succeeds

INNER · McELIECE.PKE.KEYGEN — offline, owner only

🔐 Sample the Goppa code

Sample a random monic irreducible g(X) of degree t, and n distinct field elements α₁,…,αₙ. This pair is the private key sk = (g(X), α).

↓

📐 Build & reduce the parity-check matrix

Construct the private parity-check matrix from g(X), α. Row-reduce it to systematic form to get the public key H′. (If reduction fails, restart from step 01 — a known quirk of the scheme.)

↓

📤 H′ is published — this is the public key anyone can use to encrypt to the owner

↓

OUTER · McELIECE.KEM.ENC — sender, using public key only

🎲 Sample the error vector

Sender samples a uniformly random weight-t vector e — this plays the role of the "glitter pattern," and it is what actually gets encrypted, not the message.

↓

🔒 Inner encryption — C₀ = PKE.Enc(pk, e)

Reconstruct H from H′ and compute C₀ = H·eᵀ. This single call is the entire inner PKE layer from Part 1.

↓

🧾 Bind & derive — C₁, session key K

C₁ = Hash(2 ∥ e) binds the error vector to a tamper-evident tag. K = KDF(1 ∥ e ∥ C₀ ∥ C₁) derives the shared session key. Sender transmits the ciphertext (C₀, C₁) — never K itself.

↓

📡 (C₀, C₁) travels across the open network — anyone can intercept it

🕵️ Attacker's path

Intercepts (C₀, C₁) — no sk

Only option: Information Set Decoding — brute-force search over possible weight-t vectors matching C₀ = H·eᵀ.

❌ For real parameters (e.g. n=6960, t=119) the search space is ~10²⁰⁰+ — intractable, even for a quantum computer.

🔑 Owner's path — KEM.Dec

⚙️ PKE.Dec(sk, C₀) → e

Owner uses private key sk = (g(X), α) and received syndrome C₀ = H·eᵀ to run the Extended Euclidean Algorithm on polynomials, find the Error Locator Polynomial σ(X), evaluate σ at each αⱼ, and recover the exact error vector e (or ⊥ if decoding fails). This is the full Goppa decoding step — steps 6 and 7 of the worked demo.

↓

🔁 Re-encrypt & verify → derive K

Recompute C₀′ = PKE.Enc(pk, e) and C₁′ = Hash(2 ∥ e). Check both match what was received. If checks pass, derive K = KDF(1 ∥ e ∥ C₀ ∥ C₁). If any check fails, K is derived from a fixed fallback — a malformed ciphertext produces a key that looks valid but reveals nothing. This Fujisaki–Okamoto step is KEM-only and is not in the toy demo.

✅ Matches confirm e is genuine — shared session key K established without ever transmitting it.

🏁 Shared session key established — 8 steps total

Sender and receiver now hold the same K — derived, never transmitted. The message itself was never touched by McEliece; K goes on to encrypt real data with a symmetric cipher, while the attacker is still stuck searching.

Steps 01–02 KeyGen · Steps 03–05 KEM.Enc · Step 06 Attacker · Steps 07–08 KEM.Dec — matches the 8-step worked demo in Part 3.

Where the toy demo (Part 3) simplifies things: the worked numeric example encrypts a message codeword directly and recovers it via a syndrome + Euclid's algorithm, which is easier to hand-calculate. The real KEM shown here instead encrypts a random error vector e and uses it to derive a session key — the underlying "guess the error pattern" hardness is identical, but the surrounding protocol (steps 03–09) is the part that makes it a standardized, CCA-secure scheme rather than just a textbook trapdoor.