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$, a random generator matrix for a permuted copy of the code. 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. No quantum algorithm is known to break McEliece that way, and no practical attack, classical or quantum, has broken it at suitable parameters since 1978. The cryptanalysis section reports the structural analyses of 2026, which call for a fresh assessment of the submitted Classic McEliece parameters.

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$. The generator matrix $G$ below spans the same code, in systematic form. 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 from $G_{\text{pub}}$, a random generator matrix for a permuted copy of the $[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 generic 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 generic attack is information-set decoding (ISD), which at the error weights Classic McEliece actually uses costs $2^{\Theta(n/\log_2 n)}$ operations (Albrecht et al., 2022, sec. 3.4 of the guide for security reviewers). The estimate the submission’s guide reports is $2^{140.8}$ operations at this parameter set, under free memory access (Albrecht et al., 2022, sec. 3.5 of the guide for security reviewers). The cryptanalysis section gives the 2026 estimates for structural attacks, which rest on their own cost models and, for key recovery, on heuristics. The figure below draws Patterson’s decode and ISD 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}}$ and cannot form the syndrome polynomial the first step needs. For an attacker using information-set decoding, the best generic attack, the Esser-Bellini estimator, whose output the submission's guide reports, gives $2^{140.8}$ operations under the free-memory model, or $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). 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 generic attack is information-set decoding. The submission’s guide reports Esser and Bellini’s estimator pricing it 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). Structural attacks are the other route, and the cryptanalysis section gives their 2026 estimates, which rest on their own cost models and, for key recovery, on heuristics.

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 property at stake is the assumption the construction section stated: one-wayness of decoding for Classic McEliece’s own keys. Given a public key drawn from the scheme’s key-generation distribution and a ciphertext, recovering the weight-$t$ error must be hard (Albrecht et al., 2022, sec. 3 of the guide for security reviewers). The submission cites a tight proof, in the quantum random oracle model, that the KEM’s IND-CCA2 security follows from it (National Institute of Standards and Technology, 2025a, p. 14).

The guide also names a pair of assumptions that would imply one-wayness: that decoding is hard for a uniformly random matrix, and that the public key cannot be told apart from one. It adds that “This is not a two-way implication”, since distinguishers may exist even if one-wayness holds, but that the implication makes distinguishers worth studying as “a minimum bar for structural attacks” (Albrecht et al., 2022, sec. 3.1 of the guide for security reviewers). The Classic McEliece security analysis declines to rely on indistinguishability (Classic McEliece Team, 2025) and rests on one-wayness (Classic McEliece Team, 2026a).

The public key $G_{\text{pub}} = S \cdot G \cdot P$ is a $k \times n$ binary matrix. A generic attack treats the code it generates as a general linear code and decodes the ciphertext directly. A structural attack exploits the hidden Goppa structure, whether to recover the secret key or an equivalent decryption key, or to decrypt directly.

Structural attacks. Results on this route differ in what they achieve. A distinguisher tells a public key apart from a random matrix, and on its own recovers neither a plaintext nor a key. A decryption attack uses the structure to recover a plaintext. A key recovery outputs the secret key or an equivalent decryption key, either of which decrypts every ciphertext sent to that public key. Results also differ in how they are established. An attack may be proved to work, or rest on heuristics, assumptions stated and tested on small instances. A costing prices an attack in a stated cost model without running it, and an experiment runs one on an instance small enough to finish.

As of 19 October 2026, no structural key-recovery attack on Classic McEliece is known that is efficient in either usual sense. None runs in polynomial time, and none is practical at the submitted parameter sets. No key of a submitted set has been recovered (Saarinen, 2026), and Weis, whose estimates in the dated notes below are the lowest this chapter reports, writes that “None of this is close to practical” (Weis, 2026b). The parameter sets claim more than impracticality, though. Each claims that any attack needs computational resources comparable to or greater than those of its category’s reference attack, brute-force key search on AES-128, AES-192 or AES-256 (National Institute of Standards and Technology, 2016).

Against that claim, heuristic estimates published by then price key recovery below the reference for every set. Ghoshal, Ishai, Jain, and Sun price their heuristic key recovery at $2^{130.4}$ binary operations for mceliece348864, against $2^{143}$ gates for AES-128. For the other four sets the estimates reach at most $2^{149}$, against $2^{207}$ or $2^{272}$, in what the paper calls “an optimistic operation count” (Ghoshal et al., 2026; National Institute of Standards and Technology, 2016). The later costings in the dated notes below go lower, and Weis’s stays below every set’s reference with memory charged. The initial assessment of these results by Germany’s Federal Office for Information Security (BSI), in September 2026, advises against Classic McEliece in new applications (German Federal Office for Information Security, 2026, p. 1), as the update of October 2026 below reports.

The individual results follow, each with what it establishes. Attempts to recover $g(x)$ or the support from the public key have a long history. A polynomial-time distinguisher exists 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. A 2024 syzygy distinguisher was first priced at about $2^{529}$ operations against mceliece348864, and the paper’s October 2025 revision lowers that to $2^{401}$ (Randriambololona, 2025). A 2026 paper by Briaud, Lemoine, Randriambololona, and Tillich prices its distinguisher there at $2^{454}$ to $2^{610}$ operations, depending on how the linear algebra is costed. The paper conjectures that its heuristic key recovery is subexponential, like the distinguisher, and its revision of 17 September puts the key recovery “at best of complexity of order $2^{454}$” against mceliece348864 (Briaud et al., 2026).

The Classic McEliece team answered both papers by assuming their claims correct, in April 2025 and June 2026, before those revisions, and for Briaud et al.’s it took $2^{610}$ as the key-recovery cost (Classic McEliece Team, 2025, 2026a). Every one of these costs sits 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. Among Briaud et al.’s experiments, the June version of their paper broke the Technology Innovation Institute (TII) challenge instance claiming 248 bits of security, a toy $(n, t) = (482, 7)$, in 64,000 seconds (Briaud et al., 2026). At that size ISD software from 2008 recovers plaintexts in a fraction of a second on one core (Classic McEliece Team, 2026a). The paper itself says the work “does not, for the time being, constitute a threat to Classic McEliece” (Briaud et al., 2026).

The distinguisher of Ghoshal et al. is different in kind. Their preprint of August 2026 presents 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. Each distinguisher above targets indistinguishability of public keys from random matrices, which the scheme does not assume, and Ghoshal et al. put their own result the same way: distinguishing the public key from random “only suggests a structural weakness” (Ghoshal et al., 2026).

Ghoshal et al.’s first version already had a heuristic decryption algorithm, and their 27 August revision adds a heuristic $n^{O(\log n)}$ key-recovery extension that outputs an equivalent decryption key, the one priced above (Ghoshal et al., 2026). Both are heuristic rather than proved. The decryption is proved to keep every error-free coordinate of a ciphertext but only conjectured to discard every erroneous one, and the key recovery rests on conjectures supported by small-instance experiments. Neither has been demonstrated against any submitted parameter set. Among what the paper now lists as open is proving or refuting the heuristics.

Status, September 2026

Ghoshal et al.’s paper is a preprint (ePrint 2026/1630, received 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. Weis’s reimplementation of the paper’s cost analysis reproduces its Table 2 to the two decimals given (Weis, 2026a, sec. 3). That checks the arithmetic rather than the attack, and no run of the attack at a submitted size has been reported.

The revision’s Table 3 prices its heuristic key recovery, before optimization, at $2^{130.4}$ to $2^{149}$ binary operations across the parameter sets. Its Remark 5.1 reports two further optimizations, pointed out by Weis and not reflected in Tables 1 and 2, that cut the distinguisher’s estimated time exponent by roughly 20 bits. Its Remark 7.3 reports preliminary estimates with further optimizations Weis proposed that would put key recovery below $2^{128}$ on every set (Ghoshal et al., 2026).

The Classic McEliece team posted a statement to the NIST pqc-forum on 21 August 2026, before the 27 August revision. Its preliminary analysis indicates that the paper’s attack, which conjecturally recovers plaintexts, is slower than standard attacks for every parameter set. The distinguisher, it says, is not an attack: it “merely detects whether a bit string of the right length is a public key”, a different problem from recovering keys or breaking one-wayness (Classic McEliece Team, 2026b).

Saarinen’s costing, first posted on 24 August for a route of its own, has priced the direct locator-recovery route of Ghoshal et al.’s revision on every Classic McEliece parameter set since 30 August. Its current revision, of 15 September, comes to about $2^{126.77}$ bit operations for mceliece348864 and up 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, and assumes the public tests uniquely recover enough compatible locator values. The abstract adds that “no Classic McEliece target key has been recovered” (Saarinen, 2026).

Weis has since posted the optimizations Ghoshal et al.’s remarks credit to him as a paper, received on 11 September and revised on 18 and 25 September 2026 (Weis, 2026a). It extends Ghoshal et al.’s key recovery so that one run of the distinguisher’s linear algebra yields the whole secret support. It prices that run at $2^{94.3}$ bit operations for mceliece348864 and $2^{99.3}$ to $2^{102.4}$ for the other four sets, plus a few tenths of a bit (Table 4 in Weis, 2026a). The model is Ghoshal et al.’s, which charges nothing for memory, and about three quarters of the operations fetch a bit from a vector of $2^{48}$ to $2^{52}$ bits. Charging for memory as the Classic McEliece security guide does gives $2^{110}$ to $2^{128}$, which the paper says leaves every set “below ISD and below the claimed levels, but by less” (Weis, 2026a).

Several of its ingredients are heuristic, each stated as an assumption and tested on small keys, and the paper says none of it is close to practical. Its demonstration recovered the secret key of TII challenge instance 253, a toy code with $(n, t) = (214, 9)$ that no one had solved, in two sparse kernel computations of about 700 core-hours each (Weis, 2026a, sec. 7).

Saarinen’s costing claims no optimality among routes. Its Section 6 tabulates the figures of Weis’s first version beside its own, and notes that the single-run estimates rest on assumptions still untested at Classic McEliece size (Saarinen, 2026). No further statement labelled as the team’s had appeared by 29 September, in the pqc-forum thread of its 21 August statement or on the team’s NIST web page (Classic McEliece Team, 2026b). Bernstein, a submission author posting in a personal capacity on 26 September, said that Weis’s paper does not explain how it reaches $2^{94}$ bit operations and $2^{48}$ bits of memory at once. The same message argues that communication, not bit operations, is the bottleneck of these algorithms (Bernstein, 2026). Check the current version of each paper, and any response from the team, before using these numbers for a parameter decision.

Update, October 2026

Since the September note, Germany’s Federal Office for Information Security (BSI) has advised against using Classic McEliece in new applications, and Weis has withdrawn the resource pairing that note reports. Both sources were read on 11 October 2026.

BSI’s note is dated 29 September 2026 and was published on 1 October. It says that Classic McEliece “should currently no longer be used in new developments or when planning new cryptographic applications”. For key agreement, BSI advises the lattice-based FrodoKEM or ML-KEM, or HQC (Chapter 21) once its standard is published, in accordance with its Technical Guideline TR-02102-1. BSI recommends combining each post-quantum scheme with a further scheme. TR-02102-1 recommends Classic McEliece only in a hybrid with a classical scheme, built so that both must be broken. At present such a hybrid therefore still provides at least the security of the classical scheme (pp. 1 and 2 in German Federal Office for Information Security, 2026).

The next version of TR-02102-1, expected in early 2027, will revise the Classic McEliece recommendation (German Federal Office for Information Security, 2026, p. 1). BSI finds that the results so far “do not enable a practical attack” on the parameter sets TR-02102-1 recommends, and it observes “a significant improvement in structural attacks” over the last few months (p. 3 in German Federal Office for Information Security, 2026).

Weis’s version 0.5, posted on 6 October 2026, withdraws a statement made by versions 0.1 to 0.3, those of 11, 18 and 25 September. They said that a run which recomputes its large matrix in every product, instead of storing it, needs only $2^{47.8}$ to $2^{52.1}$ bits, and that the smaller memory costs no additional operations. In the September note, that statement is what paired $2^{94.3}$ bit operations with a vector of $2^{48}$ to $2^{52}$ bits, the combination Bernstein questioned. The September figures of $2^{110}$ to $2^{128}$ with memory charged “used both numbers”, so they fall with it. Costed by Ghoshal et al.’s formulas, as the September operation counts were, Weis’s run takes $2^{94}$ to $2^{102}$ operations and stores $2^{57}$ to $2^{62}$ bits (App. H in Weis, 2026b).

Version 0.5 counts one computation of its own instead, with a different solver: a fixed circuit of $2^{92.3}$ to $2^{101.3}$ gates with $2^{49.7}$ to $2^{53.6}$ bits of memory. Multiplied by $M^{1/3}$ or $M^{1/2}$ for $M$ bits of memory, the charge behind the Classic McEliece security guide, that comes to $2^{108.9}$ to $2^{128.1}$. The range is close to September’s, but every figure in it now belongs to the one computation (Tables 4 and 5 in Weis, 2026b).

Every figure its Table 5 gives for the run stays below the NIST reference level for the category each set claims, and below classical ISD against a single target. ISD against many ciphertexts, and Grover’s algorithm applied to ISD, narrow the gap. Against Grover’s count in quantum gates, the mceliece348864 run costs 6 to 16 bits more once memory is charged at a square root (§6 and Table 5 in Weis, 2026b). The paper says that none of this is close to practical. Its costs rest on four heuristic assumptions tested on small keys, one of them that the solver terminates and returns the kernel vectors (Weis, 2026b).

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-neighbor 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-neighbor 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 bounded what was set aside. It set a lower bound on the original routine’s cost against an upper bound on the simpler one’s (Bouillaguet et al., 2025). The original can win only at lengths above $n = 533{,}500$ for random codes of rate $1/2$, or above $n = 1{,}874{,}400$ for binary Goppa codes as in McEliece, taken at rate $0.8$ and relative distance $0.03$. At that second 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 attack the guide prices 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, 2025b). 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 once the ISO standardization of Classic McEliece, then still running, was complete, it might consider developing a standard based on the ISO standard (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, FrodoKEM and ML-KEM to the asymmetric-cipher standard (ISO/IEC JTC 1/SC 27, 2026). It did not take mceliece348864, the set this chapter uses: the Classic McEliece website lists the parameter sets the standard includes as mceliece460896, mceliece6688128, mceliece6960119 and mceliece8192128, each also in its f, pc and pcf forms (Classic McEliece, 2026). The draft the Classic McEliece team prepared for ISO in April 2023, which Josefsson’s Internet-Draft transcribes, had only the last three (Josefsson, 2026). NIST has published no Classic McEliece standard of its own. The five submitted parameter sets:

Name	$n$	$k$	$t$	$m$	PK (bytes)	Claimed category
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

The last column is the category the submission claims for each set. It assigns them “on the basis of counting realistic costs for memory”, and says that with free memory access the assignments would be 1, 2, 4, 4 and 5 instead (Albrecht et al., 2022, sec. 3.5 of the guide for security reviewers). NIST’s report of March 2025 adds a caveat in a footnote. Independent estimates of the cost of information-set decoding, it says, “have long suggested” that mceliece460896 and mceliece460896f, the sets “that claim Category 3 security”, “fall short of their security target”. “However, NIST remains confident that these parameter sets at least meet the criteria for Category 2 security” (National Institute of Standards and Technology, 2025a, p. 16).

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 public structure that would compress it. The structure it has is the hidden Goppa code, and a description in those terms is the private key.

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 of the guide for security reviewers). 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.

The parameter sets target the submission’s claimed NIST categories under its stated attack-cost models (Albrecht et al., 2022, sec. 3.5 of the guide for security reviewers). Generic quantum-ISD estimates address one attack family; they do not settle the overall assessment.

No comparable structural break. Chapter 19 covers the ISD-exponent track record from 1962 to 2015 across all code-based candidates (Becker et al., 2012; May & Ozerov, 2015; 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, in that no practical attack is known at its submitted parameter sets.

Longevity does not show that the margins are unchanged, though. NIST’s report of March 2025 recorded “significant progress” during the fourth round in techniques for key recovery and for distinguishing a Goppa code from a random one. Those techniques were “still far from concretely affecting the security of the submitted parameter sets”, NIST wrote, but they “somewhat weaken the argument that the long-term security of Classic McEliece is guaranteed by its long history of cryptanalysis” (National Institute of Standards and Technology, 2025a, p. 15). Its overall assessment reads: “NIST remains confident in the security of Classic McEliece, although recent progress in cryptanalysis somewhat undermines the case for treating it as an especially conservative choice” (National Institute of Standards and Technology, 2025a, p. 16). The structural results of 2026 reported above call for a fresh assessment of the submitted parameters.

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. The status row gives NIST’s decisions alone. ISO’s publication of Classic McEliece in June 2026, which left out mceliece348864, and BSI’s advice of September 2026 are separate records, and the cryptanalysis section gives each. 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). ML-KEM has the smallest public key (800 B) at NIST level 1.

Key and ciphertext sizes are performance properties, and the key size is the practical bottleneck, since key exchange requires transmitting the public key. 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. Whether to deploy Classic McEliece at all is a separate question: BSI has since advised against it for new applications, as the update of October 2026 in the cryptanalysis section reports.

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. Its code hides no trapdoor (National Institute of Standards and Technology, 2025a, p. 10), so the structural results this chapter reports do not affect it (p. 2 in German Federal Office for Information Security, 2026). What HQC exposes instead is its quasi-cyclic structure, which speeds up generic decoding by a factor its parameters pay for, and which Chapter 21’s cryptanalysis section examines.

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

Bernstein, D. J. (2026). Re: Quasipolynomial attack on Classic McEliece. NIST pqc-forum, 26 September 2026. https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/2kfyUnLObWQ/m/aullZkWKBAAJ

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

Briaud, P., Lemoine, A., Randriambololona, H., & Tillich, J.-P. (2026). A Heuristic Subexponential Attack on the McEliece Cryptosystem. IACR Cryptology ePrint Archive, Paper 2026/1232. https://eprint.iacr.org/2026/1232

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. (2026). Classic McEliece: ISO. Classic McEliece website, version 2026.06.15 of the “ISO” web page. https://classic.mceliece.org/iso.html

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 “Re: Quasipolynomial attack on Classic McEliece”, 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

German Federal Office for Information Security. (2026). Notes on Recent Developments Concerning Classic McEliece. Bundesamt für Sicherheit in der Informationstechnik (BSI), dated 29 September 2026, published 1 October 2026. https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Crypto/Notes_Classic_McEliece.pdf?__blob=publicationFile&v=2

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. (2016). Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process. Call for Proposals, Section 4.A.5 (Security Strength Categories). https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.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

Randriambololona, H. (2025). The syzygy distinguisher. IACR Cryptology ePrint Archive, Paper 2024/1193, revised 16 October 2025. https://eprint.iacr.org/2024/1193

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

Weis, S. A. (2026a). Improving GIJS Key Recovery for Classic McEliece. IACR Cryptology ePrint Archive, Paper 2026/1984. https://eprint.iacr.org/2026/1984

Weis, S. A. (2026b). Improving GIJS Key Recovery for Classic McEliece. IACR Cryptology ePrint Archive, Paper 2026/1984, version 0.5. https://eprint.iacr.org/2026/1984