Chapter 20: McEliece: the original PQC

McEliece’s 1978 idea is to take a code you can decode efficiently, disguise it as a random code, and publish the disguised version (McEliece, 1978). Syndrome decoding of a general linear code is NP-hard in the worst case (Berlekamp et al., 1978). McEliece’s security rests on the concrete average-case hardness of decoding random-looking binary codes at the chosen parameters (Chapter 19). If the disguise holds, an attacker sees a random-looking generator matrix and faces that decoding problem at exponential cost. The key holder knows the hidden structure and decodes in polynomial time.

The disguise is simple. Start with the generator matrix $G$ of a binary Goppa code (Chapter 19). Multiply on the left by a random invertible $k \times k$ matrix $S$: this changes the generator basis without changing the code. Multiply on the right by an $n \times n$ permutation matrix $P$ to permute the coordinates, producing a permutation-equivalent code. Publish $G_{\text{pub}} = S \cdot G \cdot P$. The result looks like a random $k \times n$ binary matrix. It still corrects the same number of errors, but the decoding-friendly representation Patterson’s algorithm needs is gone. Only the holder of the decoder, the Goppa polynomial $g(x)$, the support, and the disguise $(S, P)$, can undo it and decode.

McEliece proposed this construction the same year Rivest, Shamir, and Adleman published RSA (both 1978). Shor’s 1994 algorithm showed that a sufficiently large quantum computer could break RSA. McEliece has survived 48 years without a demonstrated structural break under classical or quantum cryptanalysis.

A toy McEliece round-trip

Start with the Goppa code from Chapter 19: $\mathrm{GF}(8)$, $g(x) = x + 3$, support $L = \{0, 1, 2, 4, 5, 6, 7\}$, giving an $[n{=}7, k{=}4, d{\geq}3]$ code that corrects $t = 1$ error. Chapter 19 built the parity-check matrix $H$ and derived the generator matrix $G$. Now wrap them in a McEliece cryptosystem.

Key generation picks a random invertible $S$ and a random column permutation $P$, then publishes $G_{\text{pub}} = S \cdot G \cdot P$:

# Generator matrix G for the [7,4] Goppa code (systematic form [B^T | I_4]).
G = [[0,1,1,1,0,0,0],[1,1,0,0,1,0,0],[1,1,1,0,0,1,0],[1,0,1,0,0,0,1]]

# Scrambling matrix S (invertible 4x4 over GF(2)) and its inverse.
S = [[1,0,0,0],[1,1,0,0],[0,1,1,0],[0,0,1,1]]
S_inv = [[1,0,0,0],[1,1,0,0],[1,1,1,0],[1,1,1,1]]

# Column permutation.
perm = [2, 0, 4, 1, 6, 3, 5]

def mat_mul(A, B):
    Bt = [list(col) for col in zip(*B)]
    return [[sum(a*b for a,b in zip(ra,cb))%2 for cb in Bt] for ra in A]

# G_pub = S * G * P.
SG = mat_mul(S, G)
perm_inv = [0]*7
for i, j in enumerate(perm):
    perm_inv[j] = i
G_pub = [[SG[r][perm_inv[c]] for c in range(7)] for r in range(4)]

print("G_pub:")
for row in G_pub:
    print(" ", row)
# ==> G_pub:
# ==>   [1, 1, 0, 0, 1, 0, 0]
# ==>   [0, 1, 1, 0, 1, 0, 1]
# ==>   [0, 0, 0, 1, 1, 0, 1]
# ==>   [1, 0, 0, 1, 0, 1, 0]

Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch20/, one file per block. Appendix C covers the clone and the environment they run on.

The public key $G_{\text{pub}}$ is a $4 \times 7$ binary matrix that no longer reveals the Goppa code’s structure. Encryption adds a weight-$t$ error to the encoded message:

G_pub = [[1,1,0,0,1,0,0],[0,1,1,0,1,0,1],[0,0,0,1,1,0,1],[1,0,0,1,0,1,0]]

msg = [1, 0, 1, 1]
c = [0] * 7
for i, mi in enumerate(msg):
    if mi:
        c = [x ^ y for x, y in zip(c, G_pub[i])]

e = [0, 0, 0, 0, 1, 0, 0]  # weight-1 error at position 4
ct = [x ^ y for x, y in zip(c, e)]
print("m * G_pub =", c)
print("ciphertext =", ct)
# ==> m * G_pub = [0, 1, 0, 0, 0, 1, 1]
# ==> ciphertext = [0, 1, 0, 0, 1, 1, 1]

Decryption inverts $P$, decodes the Goppa code, then inverts $S$. For $t = 1$, decoding reduces to syndrome lookup (Chapter 19). The receiver applies the inverse permutation, looks up the syndrome, and flips the indicated bit. The scrambled message sits in the last $k$ positions (because $G = [B^T \mid I_k]$). Multiplying by $S^{-1}$ recovers the original:

ct = [0, 1, 0, 0, 1, 1, 1]

# Parity-check matrix H for the [7,4] Goppa code.
H = [[0,1,1,0,1,0,1],[1,0,0,0,1,1,1],[1,1,0,1,0,0,1]]

def mat_vec(A, v):
    return [sum(a*x for a,x in zip(row, v))%2 for row in A]

# Step 1: undo permutation P.
perm = [2, 0, 4, 1, 6, 3, 5]
perm_inv = [0]*7
for i, j in enumerate(perm):
    perm_inv[j] = i
c_unperm = [0]*7
for i in range(7):
    c_unperm[perm_inv[i]] = ct[i]

# Step 2: syndrome decode.
s = mat_vec(H, c_unperm)
error_pos = None
for j in range(7):
    if [H[r][j] for r in range(3)] == s:
        error_pos = j
        break
c_unperm[error_pos] ^= 1

# Step 3: extract scrambled message (last k=4 bits).
m_scrambled = c_unperm[3:]

# Step 4: undo S.  m = m_scrambled * S^{-1}.
S_inv = [[1,0,0,0],[1,1,0,0],[1,1,1,0],[1,1,1,1]]
recovered = [sum(m_scrambled[i]*S_inv[i][j] for i in range(4))%2 for j in range(4)]

print("m * S =", m_scrambled)
print("recovered:", recovered)
# ==> m * S = [1, 1, 0, 1]
# ==> recovered: [1, 0, 1, 1]

The original message $(1, 0, 1, 1)$ is recovered. The sender needs only $G_{\text{pub}}$; the receiver needs the decoder: $g(x)$, the support, and $(S, P)$. The security rests on the hardness of decoding a random-looking $[7, 4]$ code without knowing the hidden Goppa structure.

This toy example uses $n = 7$, where brute force over all weight-1 errors costs $\binom{7}{1} = 7$ operations. At real parameters the same structure scales to $n = 3{,}488$. There the cheapest attack the Classic McEliece submission prices costs $2^{140.8}$ operations, and even that figure assumes a memory model the submission itself calls physically implausible (Albrecht et al., 2022, sec. 3.5 of the guide for security reviewers). Before building the full-size construction, we need the general decoding algorithm.

Patterson’s decoding algorithm

Chapter 19 introduced syndrome decoding: compute $s = H \cdot r^T$, look up the syndrome in a table, flip the indicated bit. That approach works for $t = 1$ (the table has $n + 1$ entries). For $t = 2$ the table grows to $1 + n + \binom{n}{2} = O(n^2)$ entries, about 6.1 million at $n = 3{,}488$: storable in principle. But the table size is $\binom{n}{t}$, exponential in $t$. At the real Classic McEliece value $t = 64$ it is infeasibly large. Patterson’s 1975 algorithm sidesteps the table: it decodes binary Goppa codes in time polynomial in $n$ and $t$ for any $t$ (Patterson, 1975).

The algorithm works on the polynomial ring $\mathrm{GF}(2^m)[x] / g(x)$, where $g(x)$ is the secret Goppa polynomial of degree $t$. Given a received word $r$, the steps are:

1. Syndrome polynomial. Compute $S(x) = \sum_{i : r_i = 1} \frac{1}{x - \alpha_i} \bmod g(x)$, where $\alpha_i$ is the $i$-th support element. If $S(x) = 0$, there are no errors.

2. Key transform. Compute $T(x) = S(x)^{-1} + x \bmod g(x)$.

3. Square root. Compute $\tau(x) = \sqrt{T(x)} \bmod g(x)$. In $\mathrm{GF}(2^m)$, the square root of a field element $a$ is $a^{2^{m-1}}$. The quotient ring $\mathrm{GF}(2^m)[x]/(g(x))$ is isomorphic to $\mathrm{GF}(2^{mt})$ when $g$ is irreducible, so the polynomial square root is $T(x)^{2^{mt-1}} \bmod g(x)$, computed by $mt - 1$ successive squarings in the quotient ring.

4. Partial GCD. Run the extended Euclidean algorithm on $g(x)$ and $\tau(x)$, stopping when the remainder has degree $\leq \lfloor t/2 \rfloor$. At that point the partial results $a(x)$ (the remainder) and $b(x)$ (the corresponding cofactor) give the error locator polynomial $\sigma(x) = a(x)^2 + x \cdot b(x)^2$.

5. Root-finding. Evaluate $\sigma(x)$ at every support element. The roots are the error positions. Flip those bits to recover the codeword.

The trapdoor gap: Patterson runs in polynomial time given $g(x)$ and the support. At mceliece348864 the five steps are dominated by root-finding, which evaluates a degree-$t$ polynomial at all $n$ support elements, so the whole decode is on the order of $nt = 3{,}488 \times 64 \approx 2^{17.8}$ field operations. Without $g(x)$ the best known attack is information-set decoding (ISD), which at the error weights Classic McEliece actually uses costs $2^{\Theta(n/\log_2 n)}$ operations, and $2^{140.8}$ concretely at this parameter set. The figure below draws the two paths as two lanes, one above the other.

Figure 20.1. The same original-McEliece ciphertext, decoded two ways, at the $(n, t)$ parameters of mceliece348864. The ciphertext drawn is this chapter's codeword-plus-error form, not Classic McEliece's shorter Niederreiter syndrome, and the next section separates the two. The receiver holds the Goppa polynomial and the support, so Patterson's five steps run in sequence and cost about $nt = 2^{17.8}$ field operations, dominated by evaluating the degree-$t$ error locator at all $n$ support elements. The attacker holds only $G_{\text{pub}}$, cannot form the syndrome polynomial the first step needs, and is left with information-set decoding at $2^{140.8}$ operations under the free-memory model, or $2^{158.6}$ once memory access is charged (Albrecht et al., 2022, sec. 3.5 of the guide for security reviewers). The units differ: field operations on one side, the estimator's own operation count on the other, which the guide says already stands for more than $2^{143}$ bit operations. The gap is therefore not the difference of the exponents, but charging a few hundred bit operations for each field operation still leaves it above 110 bits.

The three algorithms: original McEliece-style PKE

The toy round-trip above used the warm-up parameters ($\mathrm{GF}(8)$, $t = 1$). This chapter builds the original McEliece public-key encryption: a message multiplied by a disguised generator matrix, plus a weight-$t$ error. The NIST submission, Classic McEliece, instead uses the Niederreiter dual form (a disguised parity-check matrix and a syndrome ciphertext) wrapped in a KEM transform. Exercise 4 builds the Niederreiter variant, and the cryptanalysis section returns to it. Now build the full construction over $\mathrm{GF}(2^4)$ with $t = 2$, the smallest parameter set where Patterson’s algorithm is non-trivial ($t = 1$ reduces to a single inversion; $t = 2$ requires the square-root and partial-GCD steps).

Key generation. Choose a random irreducible Goppa polynomial $g(x)$ of degree $t$ over $\mathrm{GF}(2^m)$. Construct the $[n, k]$ Goppa code’s generator matrix $G$. Sample a random invertible $k \times k$ matrix $S$ and a random $n \times n$ permutation matrix $P$. Publish $G_{\text{pub}} = S \cdot G \cdot P$.

Encryption. Given a $k$-bit message $m$, compute $c = m \cdot G_{\text{pub}} \oplus e$ where $e$ is a random weight-$t$ binary vector of length $n$.

Decryption. Given ciphertext $c$: (1) undo the column permutation, $c' = c \cdot P^{-1}$; (2) decode $c'$ with Patterson’s algorithm using the secret $g(x)$; (3) extract the scrambled message from the systematic positions; (4) multiply by $S^{-1}$ to recover $m$.

The security assumption is one-wayness of decoding for the codes Classic McEliece actually publishes: given a public key drawn from its key-generation distribution and the syndrome of a weight-$t$ error, recovering the error is hard. Hardness of decoding a uniformly random binary linear code is the generic benchmark information-set decoding prices, and the scheme’s analysis does not assume its keys are indistinguishable from random matrices, as the cryptanalysis section below explains. The best known attack is information-set decoding, which the submission’s estimator prices at $2^{140.8}$ operations for mceliece348864 under free memory access and $2^{158.6}$ once memory access is charged at square-root cost (Albrecht et al., 2022, sec. 3.5 of the guide for security reviewers).

Classic McEliece replaces this PKE interface with the Niederreiter-form KEM: encapsulation samples a weight-$t$ error vector, sends its syndrome, and derives the shared secret from the error vector the receiver decodes (Exercise 4).

Building McEliece in Python

Parameters. $\mathrm{GF}(2^4)$ with irreducible polynomial $x^4 + x + 1$. The field has 16 elements (integers 0 through 15, representing polynomials by their bit pattern). $t = 2$, so $g(x)$ has degree 2. If $g(x)$ is irreducible over $\mathrm{GF}(16)$ it has no roots in the field, giving full support $n = 16$. The code parameters are $[16, 8, \geq 5]$: 8 message bits, 16-bit codewords, corrects 2 errors.

Field arithmetic

def gf16_mul(a, b):
    """Multiply in GF(2^4) = GF(2)[x]/(x^4 + x + 1)."""
    result = 0
    for _ in range(4):
        if b & 1:
            result ^= a
        b >>= 1
        a <<= 1
        if a & 16:
            a ^= 0b10011  # x^4 + x + 1 = 19
    return result

def gf16_inv(a):
    """Brute-force inverse in GF(16)."""
    for x in range(1, 16):
        if gf16_mul(a, x) == 1:
            return x

print(f"3 * 5 = {gf16_mul(3, 5)}")
print(f"inv(7) = {gf16_inv(7)}")
print(f"7 * inv(7) = {gf16_mul(7, gf16_inv(7))}")
# ==> 3 * 5 = 15
# ==> inv(7) = 6
# ==> 7 * inv(7) = 1

Goppa code construction

Find a degree-2 irreducible polynomial $g(x)$ over $\mathrm{GF}(16)$ and build the binary parity-check matrix $H$. The matrix has $m \cdot t = 4 \cdot 2 = 8$ rows and $n = 16$ columns:

import random

def gf16_mul(a, b):
    result = 0
    for _ in range(4):
        if b & 1: result ^= a
        b >>= 1; a <<= 1
        if a & 16: a ^= 0b10011
    return result

def gf16_inv(a):
    for x in range(1, 16):
        if gf16_mul(a, x) == 1: return x

def poly_eval_gf16(coeffs, x):
    result = 0
    for c in reversed(coeffs):
        result = gf16_mul(result, x) ^ c
    return result

# Find an irreducible degree-2 polynomial over GF(16).
rng = random.Random(42)
while True:
    c0, c1 = rng.randint(0, 15), rng.randint(0, 15)
    g = [c0, c1, 1]  # monic: x^2 + c1*x + c0
    if all(poly_eval_gf16(g, a) != 0 for a in range(16)):
        break  # no roots in GF(16) => irreducible for degree 2

print(f"g(x) = {g}")

# Build the 8x16 binary parity-check matrix.
support = list(range(16))
t = 2
h = [gf16_inv(poly_eval_gf16(g, a)) for a in support]

V = []
for i in range(t):
    row = []
    for j in range(16):
        lj_pow = 1
        for _ in range(i):
            lj_pow = gf16_mul(lj_pow, support[j])
        row.append(gf16_mul(lj_pow, h[j]))
    V.append(row)

H = []
for row in V:
    for bit in range(4):
        H.append([(entry >> bit) & 1 for entry in row])

print(f"H shape: {len(H)} x {len(H[0])}")
# ==> g(x) = [8, 7, 1]
# ==> H shape: 8 x 16

Generator matrix and verification

Row-reduce $H$ to systematic form $[I_8 \mid B]$ via Gaussian elimination with column pivoting. The generator matrix is $G = [B^T \mid I_8]$. Every codeword $c = m \cdot G$ satisfies $G \cdot H^T = 0$ over $\mathrm{GF}(2)$:

import random

def gf16_mul(a, b):
    result = 0
    for _ in range(4):
        if b & 1: result ^= a
        b >>= 1; a <<= 1
        if a & 16: a ^= 0b10011
    return result

def gf16_inv(a):
    for x in range(1, 16):
        if gf16_mul(a, x) == 1: return x

def poly_eval_gf16(coeffs, x):
    result = 0
    for c in reversed(coeffs):
        result = gf16_mul(result, x) ^ c
    return result

# Reproduce the Goppa code from the previous block.
rng = random.Random(42)
while True:
    c0, c1 = rng.randint(0, 15), rng.randint(0, 15)
    g = [c0, c1, 1]
    if all(poly_eval_gf16(g, a) != 0 for a in range(16)):
        break
support = list(range(16))
t, n = 2, 16
h = [gf16_inv(poly_eval_gf16(g, a)) for a in support]
V = []
for i in range(t):
    row = []
    for j in range(n):
        lj_pow = 1
        for _ in range(i): lj_pow = gf16_mul(lj_pow, support[j])
        row.append(gf16_mul(lj_pow, h[j]))
    V.append(row)
H = []
for row in V:
    for bit in range(4):
        H.append([(entry >> bit) & 1 for entry in row])

# Gaussian elimination with column pivoting.
def gauss_systematic(H):
    rows, cols = len(H), len(H[0])
    M = [list(row) for row in H]
    col_perm = list(range(cols))
    for i in range(rows):
        pivot = None
        for j in range(i, cols):
            for r in range(i, rows):
                if M[r][j] == 1:
                    if r != i: M[i], M[r] = M[r], M[i]
                    pivot = j; break
            if pivot is not None: break
        # Column swap: bring the pivot into column i so the left n-k
        # columns can form the identity block of [I_{n-k} | B].
        if pivot != i:
            for r in range(rows):
                M[r][i], M[r][pivot] = M[r][pivot], M[r][i]
            col_perm[i], col_perm[pivot] = col_perm[pivot], col_perm[i]
        for r in range(rows):
            if r != i and M[r][i] == 1:
                for c in range(cols): M[r][c] ^= M[i][c]
    return M, col_perm

H_sys, col_perm = gauss_systematic(H)
nk = len(H_sys)
k = n - nk

# G = [B^T | I_k] from H_sys = [I_{n-k} | B].
B = [[H_sys[r][nk+c] for c in range(k)] for r in range(nk)]
Bt = [list(col) for col in zip(*B)]
Ik = [[1 if i==j else 0 for j in range(k)] for i in range(k)]
G = [Bt[r] + Ik[r] for r in range(k)]

# Verify G * H^T = 0 in permuted column ordering.
H_perm = [[H[r][col_perm[c]] for c in range(n)] for r in range(nk)]
Ht = [list(col) for col in zip(*H_perm)]
GHt = [[sum(G[r][i]*Ht[i][c] for i in range(n))%2 for c in range(nk)]
       for r in range(k)]
print(f"G shape: {k} x {n}")
print(f"G * H^T = 0: {all(all(x==0 for x in row) for row in GHt)}")
# ==> G shape: 8 x 16
# ==> G * H^T = 0: True

Patterson decoding

Inject a weight-2 error and decode using Patterson’s algorithm. The full implementation is patterson_decode in the ch20-mceliece package under solutions/. For $t = 2$, the error locator polynomial $\sigma(x)$ has degree at most 2, so root-finding is exhaustive evaluation over 16 field elements:

import sys, pathlib, random
sys.path.insert(0, str(pathlib.Path("solutions/ch20-mceliece/src")))

from mceliece.gf2m import poly_eval
from mceliece.goppa import goppa_parity_check, find_irreducible_goppa_poly, full_support
from mceliece.gf2 import generator_from_parity, vec_add
from mceliece.patterson import patterson_decode

m, irred = 4, 0b10011
rng = random.Random(42)
g_coeffs = find_irreducible_goppa_poly(m, irred, 2, rng)
support = [a for a in full_support(m) if poly_eval(g_coeffs, a, m, irred) != 0]
H = goppa_parity_check(m, irred, g_coeffs, support)
G, col_perm = generator_from_parity(H)
support_sys = [support[col_perm[i]] for i in range(len(support))]

msg = [1, 0, 1, 1, 0, 0, 1, 0]
codeword = [0] * 16
for i, mi in enumerate(msg):
    if mi:
        codeword = vec_add(codeword, G[i])

received = list(codeword)
received[3] ^= 1
received[11] ^= 1

decoded = patterson_decode(received, g_coeffs, support_sys, m, irred)
print(f"errors corrected: {sum(a^b for a,b in zip(received, decoded))}")
print(f"codeword recovered: {decoded == codeword}")
# ==> errors corrected: 2
# ==> codeword recovered: True

Full McEliece keygen, encrypt, decrypt

The standalone package at solutions/ch20-mceliece/ implements the complete scheme. Key generation chooses a random Goppa polynomial, constructs $G$, samples $S$ and $P$, and publishes $G_{\text{pub}} = S \cdot G \cdot P$:

import sys, pathlib, random
sys.path.insert(0, str(pathlib.Path("solutions/ch20-mceliece/src")))
from mceliece import keygen, encrypt, decrypt

pub, sec = keygen(m=4, t=2, irred=0b10011, rng=random.Random(42))
print(f"public key: {pub['k']}x{pub['n']} matrix ({pub['k']*pub['n']} bits = {pub['k']*pub['n']//8} bytes)")

msg = [1, 0, 1, 1, 0, 0, 1, 0]
ct = encrypt(pub, msg, rng=random.Random(99))
recovered = decrypt(sec, ct)
print(f"message:   {msg}")
print(f"recovered: {recovered}")
print(f"match: {msg == recovered}")
# ==> public key: 8x16 matrix (128 bits = 16 bytes)
# ==> message:   [1, 0, 1, 1, 0, 0, 1, 0]
# ==> recovered: [1, 0, 1, 1, 0, 0, 1, 0]
# ==> match: True

Round-trip across 50 key seeds

import sys, pathlib, random
sys.path.insert(0, str(pathlib.Path("solutions/ch20-mceliece/src")))
from mceliece import keygen, encrypt, decrypt

failures = 0
for seed in range(50):
    r = random.Random(seed)
    p, s = keygen(m=4, t=2, irred=0b10011, rng=r)
    trial_msg = [r.randint(0, 1) for _ in range(p['k'])]
    c = encrypt(p, trial_msg, rng=random.Random(seed + 1000))
    if decrypt(s, c) != trial_msg:
        failures += 1
print(f"50 seeds, random messages: {failures} failures")
# ==> 50 seeds, random messages: 0 failures

What this package is not

solutions/ch20-mceliece is a didactic McEliece-style public-key encryption scheme: original generator-matrix encryption, not constant-time, and not IND-CCA2 secure. It is not Classic McEliece. Classic McEliece uses the Niederreiter dual form (Exercise 4) wrapped in a CCA-secure KEM transform with ciphertext verification and implicit rejection. Earlier variants also included plaintext confirmation.

Cryptanalysis and ISD resistance

The public key $G_{\text{pub}} = S \cdot G \cdot P$ is a $k \times n$ binary matrix. An attacker who wants to decrypt a ciphertext must either recover the hidden Goppa code (structural attack) or decode a random-looking linear code directly (generic attack).

Structural attacks. Attempts to recover $g(x)$ or the support from the public key have a long history. No efficient structural key-recovery attack is known against the submitted binary-Goppa Classic McEliece parameter sets. A polynomial-time distinguisher does exist for high-rate binary Goppa and alternant codes (Faugère et al., 2013), but it stops working far below the error counts the submitted parameters use, so it does not apply to them.

Algebraic attacks and distinguishers targeting Goppa-code structure remain an active research area, and three claims from the last two years show what “active” means and what it does not. A 2024 syzygy distinguisher was priced at $2^{529}$ operations against mceliece348864. A 2026 paper titled “A heuristic subexponential attack on the McEliece cryptosystem” claimed key recovery at $2^{610}$. The Classic McEliece team responded to both of those by assuming the claims correct and then measuring them (Classic McEliece Team, 2025, 2026). Both costs sit far above $2^{256}$. That is the cost of recovering a private key by searching every 256-bit seed, an attack the submission had documented years earlier. The 2026 paper’s largest actual demonstration is a toy $(n, t) = (482, 7)$, which ISD software from 2008 breaks in a fraction of a second on one core. Its own page 7 concedes that the work “does not, for the time being, constitute a threat to Classic McEliece”.

The third claim is different in kind. In August 2026 Ghoshal, Ishai, Jain, and Sun posted a preprint presenting a classical distinguisher that separates a Goppa-McEliece public key from a uniformly random $k \times n$ binary matrix, in the asymptotic regime Classic McEliece’s parameters follow (Ghoshal et al., 2026). Its guarantee is proved rather than conjectured, by linear algebra and interpolation: $n^{O(\log n)}$ time, advantage $1 - o(1)$. It applies to all five submitted parameter sets, where the concrete instantiation is cheaper but weaker. One execution against mceliece348864 is estimated at $2^{114}$ binary operations, against the paper’s own $2^{151}$ information-set-decoding reference in the same circuit model, and it achieves a proved advantage above $0.42$ rather than $1 - o(1)$. The authors say the asymptotic theorem’s constants are not made concrete, that amplifying the concrete advantage would need the attack reparameterized, and that the estimates are improved but not yet practical.

A number in an abstract is not a break, and neither is a distinguisher. The syzygy result and the 2026 distinguisher both target indistinguishability of public keys from random matrices, a property the Classic McEliece security analysis explicitly declines to rely on. The scheme rests on the weaker assumption that decoding is one-way, and the 2026 authors put their own result the same way: distinguishing the public key from random “only suggests a structural weakness”. Its 27 August revision adds a heuristic $n^{O(\log n)}$ key-recovery extension that outputs an equivalent decryption key, priced by the authors at $2^{130}$ to $2^{149}$ binary operations across the parameter sets under the same optimistic operation count. What the paper now lists as open is proving or refuting the heuristics. Both extensions are heuristic rather than proved: decryption on the rejection side, key recovery under conjectures supported by small-instance experiments, and neither has been demonstrated against any submitted parameter set. None of the three moves the 48 years. What the third one moves is the margin, on an estimate that charges nothing for the $2^{66}$ bits of storage it needs.

Status, September 2026

The third claim is a preprint (ePrint 2026/1630, posted 7 August 2026, revised 27 August 2026) under community review at the time of writing. The concrete figures, $2^{114}$ time and $2^{66}$ bits of storage against mceliece348864 at proved advantage above $0.42$, are the authors’ own Table 1 and Table 2 estimates, with no independent verification yet. The revision’s Table 3 prices its heuristic key recovery at $2^{130.4}$ to $2^{149}$ binary operations across the parameter sets. Its Remark 5.1 and Remark 7.3 report further optimizations, roughly 20 bits, not incorporated into those figures, with preliminary estimates that would put key recovery below $2^{128}$ on every set. The Classic McEliece team posted a statement to the NIST pqc-forum on 21 August 2026, before the 27 August revision: its preliminary analysis finds the attack slower than standard attacks for every parameter set, and it separates distinguishing public keys from recovering keys or breaking one-wayness (Classic McEliece Team, 2026b). A 24 August costing by Saarinen, revised 15 September, now prices the heuristic key recovery on every Classic McEliece parameter set, from about $2^{126.77}$ bit operations for mceliece348864 to about $2^{145.22}$ for mceliece460896, with working memory from $2^{51.33}$ to $2^{59.10}$ bits. Its abstract states that all five arithmetic estimates lie below the NIST classical-gate reference level for the category each set claims. That is a conditional arithmetic estimate in a model that charges nothing for address generation or memory traffic, uses budget estimates for some stages, assumes the public tests recover enough compatible locator values, and recovers no key (Saarinen, 2026). Check the current paper version and the responses before using these numbers for a parameter decision.

ISD as the best generic attack. Chapter 19 covered the ISD timeline from Prange (1962) to May-Ozerov (2015). Chapter 19’s bounded-distance regime is half-distance decoding of random binary codes, each exponent the worst case over code rates, which falls near rate $0.45$ to $0.47$. There BJMM reached $\approx 0.0494n$ time with $\approx 0.0286n$ memory, and May-Ozerov lowered the time to $\approx 0.0473n$ with exponential nearest-neighbour lists, the smallest half-distance exponent in the 2015 comparison and, as Chapter 19 records, still the figure the Classic McEliece submission quotes (Becker et al., 2012; May & Ozerov, 2015). Concrete schemes still set parameters from finite-$n$ cost models, not from this asymptotic exponent. For the NIST Classic McEliece parameters:

from math import comb, log2

def prange_exponent(n, k, w):
    return log2(comb(n, w)) - log2(comb(n - k, w))

print(f"toy (n=16, k=8, t=2):  2^{prange_exponent(16, 8, 2):.1f}")
print(f"mceliece348864:        2^{prange_exponent(3488, 2720, 64):.1f}")
print(f"brute-force C(16,2) = {comb(16, 2)}")
# ==> toy (n=16, k=8, t=2):  2^2.1
# ==> mceliece348864:        2^142.8
# ==> brute-force C(16,2) = 120

The toy parameters give $2^{2.1} \approx 4.3$ expected Prange iterations (versus brute-force $\binom{16}{2} = 120$), and mceliece348864 gives $2^{142.8}$. Those are iteration counts, not operation counts. Each iteration pays for a Gaussian elimination, worth roughly another $2^{31}$ bit operations at these dimensions, which is why the submission’s own table prices full Prange at $2^{173.4}$.

That table is Esser-Bellini estimator output for every selected parameter set, under three different assumptions about what memory access costs (Albrecht et al., 2022, sec. 3.5 of the guide for security reviewers). Four of its columns, for mceliece348864:

Memory model	Prange	Stern	BJMM	May-Ozerov
Free access	$2^{173.4}$	$2^{151.4}$	$2^{141.9}$	$2^{140.8}$
Cube-root cost	$2^{176.7}$	$2^{159.3}$	$2^{159.1}$	$2^{156.4}$
Square-root cost	$2^{178.3}$	$2^{162.8}$	$2^{162.2}$	$2^{158.6}$

Read down the first row and the modern algorithms look decisive, buying 32.6 bits over Prange. Read down the third and the same algorithms buy 19.7 bits, and May-Ozerov’s margin over Stern collapses from 10.6 bits to 4.2. Most of the advertised speedup is a charge the free-memory model declines to make.

One caution about the last column, and it sharpens the point rather than softening it. The estimator does not run May-Ozerov’s nearest-neighbour search. Esser and Bellini set that routine aside because it “inherits a huge polynomial overhead limiting its practicality”, and priced the May-Ozerov ISD structure with a simpler substitute instead (Esser & Bellini, 2022). A 2025 analysis measured what was set aside. The original nearest-neighbour algorithm first beats the simpler method at $n > 533{,}500$ for rate-$1/2$ codes, and at $n > 1{,}874{,}400$ in a McEliece-like regime (Bouillaguet et al., 2025). At that length the decoding itself costs more than $2^{63{,}000}$ operations. The $0.0473n$ exponent is real and it is asymptotic. At $n = 3{,}488$ the column above prices a structure, not that exponent.

The cheapest entry in the whole table, $2^{140.8}$, sits below the $2^{143}$ NIST estimates for brute-force AES-128 key search. The guide meets that rather than rounding it away. Its estimator scores an operation on an entire vector as one operation, so $2^{140.8}$ already stands for more than $2^{143}$ bit operations, and the attack it prices needs $2^{86.6}$ memory. Charging for that memory is what puts every known attack on mceliece348864 above AES-128 key search, and it is the submission’s stated basis for assigning the set to category 1.

NIST Classic McEliece parameter sets. Classic McEliece was one of the fourth-round NIST KEM candidates (Albrecht et al., 2022). In March 2025 NIST selected HQC as the code-based KEM to standardize alongside the already-finalized ML-KEM (FIPS 203) (National Institute of Standards and Technology, 2025). The fourth-round status report states that Classic McEliece “is no longer under consideration for standardization as part of the current NIST PQC Standardization Process” (National Institute of Standards and Technology, 2025a).

NIST added that it might develop a standard later, based on the ISO standardization of Classic McEliece that was then still running (National Institute of Standards and Technology, 2025a). That process has since closed: ISO/IEC 18033-2:2006/Amd 2, published in June 2026, adds Classic McEliece and FrodoKEM to the asymmetric-cipher standard (ISO/IEC JTC 1/SC 27, 2026). It did not take mceliece348864, the set this chapter uses. The transcription of the ISO text lists only the larger code lengths 6688128, 6960119, and 8192128 (Josefsson, 2026). NIST has published no Classic McEliece standard of its own. The five submitted parameter sets:

Name	$n$	$k$	$t$	$m$	PK (bytes)	Level
mceliece348864	3,488	2,720	64	12	261,120	1
mceliece460896	4,608	3,360	96	13	524,160	3
mceliece6688128	6,688	5,024	128	13	1,044,992	5
mceliece6960119	6,960	5,413	119	13	1,047,319	5
mceliece8192128	8,192	6,528	128	13	1,357,824	5

Why keys are huge. Classic McEliece publishes $T$, the non-identity block of the parity-check matrix reduced to systematic form $(I_{mt} \mid T)$, which makes it an $mt \times k$ matrix over $\mathrm{GF}(2)$ (Albrecht et al., 2022, sec. 4.2 of the cryptosystem specification). It is stored one row at a time, each row padded out to a whole number of bytes, so the size is $mt \lceil k/8 \rceil$ (Albrecht et al., 2022, sec. 6.2 of the cryptosystem specification). For mceliece348864 that is $768 \times 340 = 261{,}120$ bytes (255 KiB), and the padding costs nothing because $k = 2{,}720$ is already a multiple of 8. For mceliece6960119 it does cost something: $k = 5{,}413$ rounds up to 677 bytes a row, so the key is $1{,}547 \times 677 = 1{,}047{,}319$ bytes, carrying three wasted bits on every row. The matrix has no exploitable structure for compression, because the whole point is to look random.

Ciphertexts run the other way. Classic McEliece uses the Niederreiter dual form (Exercise 4), where the ciphertext is just the $mt$-bit syndrome. For mceliece348864 that is $mt = 12 \times 64 = 768$ bits $= 96$ bytes, against the $n/8 = 436$ bytes a raw McEliece ciphertext would require. Fourth-round Classic McEliece appends nothing to it: encapsulation sends the syndrome alone and derives the session key as $H(1, e, C)$, and decapsulation falls back on implicit rejection rather than checking a plaintext-confirmation hash (Albrecht et al., 2022, sec. 5.5 and 5.6 of the cryptosystem specification). An earlier variant did append a 32-byte confirmation hash, which is where the 128-byte figure sometimes still quoted comes from.

Quantum attacks. Grover’s algorithm provides a quadratic speedup on the brute-force search component of ISD, and the guide states the consequence in one line: known quantum attacks replace the asymptotic base with its square root (Albrecht et al., 2022, sec. 3.4). Chapter 19 works the arithmetic. At rate $1/2$ and the full Gilbert-Varshamov distance the classical Prange exponent is $\approx 0.1199n$, and halving takes it to $\approx 0.0599n$. The $0.1207n$ usually quoted for this setting is not the rate-$1/2$ value: it is the maximum of the same exponent over all rates, attained near rate $0.454$. The regime matters more than the digits, because the same section rules that regime out for this scheme. Its $\Theta(n)$ error weights “do not appear in the McEliece system”, and Classic McEliece prices $t \in o(n)$, which gives $2^{\Theta(n/\log_2 n)}$ instead.

NIST’s security categories account for the quantum speedup, and Classic McEliece’s parameters are chosen so that even quantum ISD exceeds the target security level.

No comparable structural break. Chapter 19 covers the ISD-exponent track record from 1962 to 2012 across all code-based candidates (Becker et al., 2012; Prange, 1962). SIDH was proposed in 2011 and broken in 2022 by Castryck and Decru with an attack that exploits the torsion-point images SIDH publishes, not the isogeny graph itself (Castryck & Decru, 2023) (Chapter 22 covers this). McEliece has had no comparable structural break.

Tradeoffs: keys, ciphertexts, and assumptions

Property	Classic McEliece (348864)	HQC-1 (formerly HQC-128)	ML-KEM-512
Public key	261,120 B	2,241 B	800 B
Ciphertext	96 B	4,433 B	768 B
Assumption	Goppa-code SDP (+ structural resistance)	QCSD (decisional variants)	Module-LWE
NIST status	Not selected	Selected (March 2025)	Standard (FIPS 203)

HQC’s sizes here follow the latest HQC specification (HQC-1). Older NIST-round and implementation references call this parameter set HQC-128. McEliece has the largest public keys by far (255 KiB vs 2,241 B for HQC, 800 B for ML-KEM) but the smallest ciphertexts (96 B). The key size is the practical bottleneck: key exchange requires transmitting the public key, and 255 KiB is expensive for constrained devices and for protocols that negotiate keys frequently. ML-KEM has the smallest public key (800 B) at NIST level 1. Chapter 21 develops the quasi-cyclic compression that lets HQC reach a 2,241-byte public key from the same code-based foundation.

For applications where public keys are transmitted once and stored (certificate infrastructure), 255 KiB is manageable. For protocols that negotiate keys per-session (TLS handshakes on constrained hardware), the key size is prohibitive. Chapter 21 builds HQC, the code-based alternative that trades one-wayness of decoding over a Goppa-derived key for a decisional quasi-cyclic assumption and much smaller keys.

Exercises

Exercise 1. All 16 messages. Using the warm-up parameters ($\mathrm{GF}(8)$, $t = 1$, $n = 7$, $k = 4$) and a fixed key seed, encrypt and decrypt all 16 possible 4-bit messages. Verify that every round-trip succeeds.

Exercise 2. ISD iteration count vs brute force. For the toy $\mathrm{GF}(16)$ parameters ($n = 16$, $k = 8$, $t = 2$), compute the expected number of Prange ISD iterations, $\binom{n}{w} / \binom{n-k}{w}$. Compare it against the $\binom{16}{2} = 120$ weight-2 vectors a brute-force search enumerates. Then explain why this iteration count alone overstates Prange’s advantage: one Prange iteration costs a Gaussian elimination, whereas one brute-force trial is a single syndrome check. Estimate the per-iteration cost and discuss how it changes the comparison.

Exercise 3. Key-size arithmetic. Classic McEliece uses systematic-form public keys: the non-identity block $T$ of the parity-check matrix in systematic form, which has $n - k$ rows and $k$ columns. For mceliece348864 ($n = 3{,}488$, $k = 2{,}720$), compute the public key size in bytes. Compute the ratio of public key size to the raw McEliece ciphertext size ($n$ bits). Explain in one sentence why key size, not ciphertext bandwidth, is the practical bottleneck.

Exercise 4. Niederreiter’s dual. In the Niederreiter variant (Niederreiter, 1986), the public key is a disguised parity-check matrix $H_{\text{pub}} = M \cdot H \cdot P$ and the message is encoded as a weight-$t$ error vector $e$. The ciphertext is the syndrome $s = H_{\text{pub}} \cdot e^T$. Decryption inverts $P$, inverts $M$, and uses Patterson’s algorithm to recover $e$ from the syndrome. Implement the Niederreiter variant for the toy $\mathrm{GF}(16)$ parameters and verify that the syndrome uniquely determines $e$ for all $\binom{16}{2} = 120$ weight-2 error patterns.

Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 20. A separate track, for rebuilding rather than reading: the package exercises/ch20-mceliece has every function the chapter teaches replaced by a stub. Run PQC_IMPL=exercises pytest tests/ch20 to grade your version against the suite that proves the reference one.

References

Albrecht, M. R., Bernstein, D. J., Chou, T., Cid, C., Gilcher, J., Lange, T., Maram, V., von Maurich, I., Misoczki, R., Niederhagen, R., Paterson, K. G., Persichetti, E., Peters, C., Schwabe, P., Sendrier, N., Szefer, J., Tjhai, C. J., Tomlinson, M., & Wang, W. (2022). Classic McEliece: conservative code-based cryptography. NIST Post-Quantum Cryptography Round 4 submission. https://classic.mceliece.org/nist.html

Becker, A., Joux, A., May, A., & Meurer, A. (2012). Decoding Random Binary Linear Codes in 2^n/20: How 1+1=0 Improves Information Set Decoding. Advances in Cryptology – EUROCRYPT 2012, 7237, 520–536. https://doi.org/10.1007/978-3-642-29011-4_31

Berlekamp, E. R., McEliece, R. J., & van Tilborg, H. C. A. (1978). On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory, 24(3), 384–386. https://doi.org/10.1109/TIT.1978.1055873

Bouillaguet, C., Delaplace, C., & Hamdad, M. (2025). The May-Ozerov Algorithm for Syndrome Decoding is “Galactic.” IACR Communications in Cryptology, 2(1). https://doi.org/10.62056/akjbksuc2

Castryck, W., & Decru, T. (2023). An efficient key recovery attack on SIDH. Advances in Cryptology – EUROCRYPT 2023, Part V, 14008, 423–447. https://doi.org/10.1007/978-3-031-30589-4_15

Classic McEliece Team. (2025). Notes on a recent claim that a mceliece348864 distinguisher uses only 2⁵²⁹ operations. Classic McEliece team report, 17 April 2025. https://classic.mceliece.org/mceliece-529-20250417.pdf

Classic McEliece Team. (2026a). Notes on recent speculation that a mceliece348864 key-recovery attack uses only 2⁶¹⁰ operations. Classic McEliece team report, 23 June 2026. https://classic.mceliece.org/mceliece-610-20260623.pdf

Classic McEliece Team. (2026b). Statement on eprint 2026/1630, posted by D. J. Bernstein to the NIST pqc-forum. NIST pqc-forum, thread “eprint 2026/1630”, 21 August 2026. https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/2kfyUnLObWQ

Esser, A., & Bellini, E. (2022). Syndrome Decoding Estimator. Public-Key Cryptography – PKC 2022, 13177, 112–141. https://doi.org/10.1007/978-3-030-97121-2_5

Faugère, J.-C., Gauthier-Umaña, V., Otmani, A., Perret, L., & Tillich, J.-P. (2013). A Distinguisher for High-Rate McEliece Cryptosystems. IEEE Transactions on Information Theory, 59(10), 6830–6844. https://doi.org/10.1109/TIT.2013.2272036

Ghoshal, A., Ishai, Y., Jain, A., & Sun, N. (2026). Quasipolynomial Cryptanalysis of the McEliece Cryptosystem (or: PIR Meets McEliece). IACR Cryptology ePrint Archive, Paper 2026/1630. https://eprint.iacr.org/2026/1630

ISO/IEC JTC 1/SC 27. (2026). Information technology — Security techniques — Encryption algorithms — Part 2: Asymmetric ciphers — Amendment 2. ISO/IEC 18033-2:2006/Amd 2:2026. https://www.iso.org/standard/86890.html

Josefsson, S. (2026). Classic McEliece. IETF Internet-Draft draft-josefsson-mceliece-05. https://datatracker.ietf.org/doc/draft-josefsson-mceliece/

May, A., & Ozerov, I. (2015). On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes. Advances in Cryptology – EUROCRYPT 2015, 9056, 203–228. https://doi.org/10.1007/978-3-662-46800-5_9

McEliece, R. J. (1978). A public-key cryptosystem based on algebraic coding theory. DSN Progress Report, 42–44, 114–116. https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF

National Institute of Standards and Technology. (2025a). Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process (Internal Report NIST IR 8545). National Institute of Standards and Technology. https://doi.org/10.6028/NIST.IR.8545

National Institute of Standards and Technology. (2025b). NIST Selects HQC as Fifth Algorithm for Post-Quantum Encryption. NIST news release. https://www.nist.gov/news-events/news/2025/03/nist-selects-hqc-fifth-algorithm-post-quantum-encryption

Niederreiter, H. (1986). Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory, 15(2), 159–166. https://cir.nii.ac.jp/crid/1571980076566605568?lang=en

Patterson, N. J. (1975). The algebraic decoding of Goppa codes. IEEE Transactions on Information Theory, 21(2), 203–207. https://doi.org/10.1109/TIT.1975.1055350

Prange, E. (1962). The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory, 8(5), S5–S9. https://doi.org/10.1109/TIT.1962.1057777

Saarinen, M.-J. O. (2026). Bit Operation Cost of “Holdout” Key-Recovery Attacks Against Classic McEliece. IACR Cryptology ePrint Archive, Paper 2026/1786. https://eprint.iacr.org/2026/1786