Chapter 21: HQC, a pedagogical implementation

Classic McEliece (Chapter 20) descends from McEliece’s binary-Goppa cryptosystem of 1978 (McEliece, 1978), and no practical attack has broken that line at suitable parameters since. Chapter 20’s cryptanalysis section, with its account as of October 2026 and its dated notes, reports the structural analyses of 2026, which call for a fresh assessment of the submitted parameters. Classic McEliece’s public keys are enormous: 261,120 bytes for mceliece348864, the set that claims NIST security level 1 (Albrecht et al., 2022). The key is the non-identity block of a parity-check matrix reduced to systematic form, with no public structure that would compress it (Chapter 20). Transmitting that matrix once per session is impractical for bandwidth-constrained protocols like TLS handshakes on embedded hardware.

HQC (Hamming Quasi-Cyclic) is a code-based KEM whose public key is two polynomials in $\text{GF}(2)[x]/(x^n - 1)$ (Gaborit et al., 2026). At NIST level 1, the HQC-1 public key is 2,241 bytes, roughly 116 times smaller than mceliece348864’s. The compactness comes from restricting HQC’s own code to a double-circulant quasi-cyclic structure: its large binary parity-check matrix is generated from a small number of length-$n$ ring elements rather than stored densely. Those 2,241 bytes are the reference encoding, which is smaller than the two polynomials themselves: one 2,209-byte ring element plus a 32-byte seed that regenerates the second, uniform ring element (Gaborit et al., 2026, sec. 4.2). Chapter 19 introduced circulant polynomial multiplication; this chapter uses it to build a complete cryptosystem.

The two schemes rest on different assumptions and expose different attack surfaces. Classic McEliece states its assumption directly over the Goppa-derived public key: recovering a weight-$t$ error is hard, the Goppa-code SDP with structural resistance folded in (Chapter 20). It does not route that through a claim that the key is indistinguishable from a random matrix. The literature uses that implication to motivate studying distinguishers, and the submission declines to rely on it (Albrecht et al., 2022, sec. 3.1 of the guide for security reviewers; Classic McEliece Team, 2026). An attacker can decode generically or exploit the hidden Goppa structure, and the 2026 analyses take the second route.

HQC hides no trapdoor in its code: the error-correcting code it decodes is public (National Institute of Standards and Technology, 2025a, p. 10), and its secret key is a pair of sparse vectors. There is no hidden code for an attacker to recover, and Germany’s Federal Office for Information Security (BSI) noted in September 2026 that the structural results on Goppa codes do not affect HQC (p. 2 in German Federal Office for Information Security, 2026).

HQC’s security reduces to a structured syndrome-decoding variant: the quasi-cyclic syndrome decoding problem (QCSD). That structure is not free: it hands an attacker a measurable speedup, which the cryptanalysis section below prices and which the published security levels already have deducted. The assumption is also newer than the Goppa-code assumption, which dates to McEliece’s scheme of 1978 (McEliece, 1978). Decoding random double-circulant codes, the two-block quasi-cyclic case, was a cryptographic assumption by 2007 (§IV-B in Gaborit & Girault, 2007). HQC’s decisional form of quasi-cyclic decoding dates to 2016 (Definition 13 in Aguilar et al., 2016). No proof or efficient attack separates QCSD from generic syndrome decoding at the HQC parameter sets.

A toy HQC round-trip

The following code runs a complete HQC key generation, encryption, and decryption at toy parameters. The ring degree is $n = 83$, the secret weight $w = 3$, the encryption weight $w_r = 3$, the error weight $w_e = 3$, and the repetition factor $r = 17$. The message length is $k = \lfloor 83/17 \rfloor = 4$ bits.

import random

def poly_add(a, b):
    return [ai ^ bi for ai, bi in zip(a, b)]

def poly_mul(a, b, n):
    c = [0] * n
    for i in range(n):
        if a[i] == 0:
            continue
        for j in range(n):
            if b[j]:
                c[(i + j) % n] ^= 1
    return c

def sample_sparse(n, w, rng):
    positions = rng.sample(range(n), w)
    vec = [0] * n
    for p in positions:
        vec[p] = 1
    return vec

def support(v):
    return [i for i, x in enumerate(v) if x]

def rep_encode(message, r, n):
    codeword = []
    for bit in message:
        codeword.extend([bit] * r)
    codeword.extend([0] * (n - len(codeword)))
    return codeword

def rep_decode(received, r, n):
    k = n // r
    message = []
    for i in range(k):
        block = received[i * r : (i + 1) * r]
        ones = sum(block)
        message.append(1 if ones > r // 2 else 0)
    return message

N, W, W_R, W_E, R = 83, 3, 3, 3, 17
K = N // R  # 4

# Key generation
rng = random.Random(0)
s = [rng.randint(0, 1) for _ in range(N)]
x = sample_sparse(N, W, rng)
y = sample_sparse(N, W, rng)
h = poly_add(x, poly_mul(s, y, N))

print("x support:", support(x))
print("y support:", support(y))
print("h weight: ", sum(h))
# ==> x support: [14, 41, 78]
# ==> y support: [62, 75, 80]
# ==> h weight:  46

Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch21/, one file per block, except the sketch of a reference-compliant HQC call shape, which is all comments. Appendix C covers the clone and the environment they run on.

The secret key is the pair $(x, y)$ of sparse binary vectors with weight 3. The public key is $(s, h)$ where $s$ is a uniform random polynomial and $h = x + s \cdot y$ in $\text{GF}(2)[x]/(x^{83} - 1)$. The public key consists of two length-83 binary vectors: 166 bits total.

This chapter swaps two of the specification’s symbol names

The toy names the uniform element $s$ and the derived element $h$. The HQC specification uses the opposite convention: $h$ uniform, $s = x + h \cdot y$, encryption $u = r_1 + h \cdot r_2$, and decryption $v - u \cdot y$. Over $\text{GF}(2)$ the quotient ring is commutative and subtraction equals addition, so the cancellation is identical. Only the symbol names differ from the reference. Chapter 19’s quasi-cyclic section uses the specification’s letters. Keep the swap in mind when reading this chapter against the HQC document or its known-answer test (KAT) files.

import random

def poly_add(a, b):
    return [ai ^ bi for ai, bi in zip(a, b)]

def poly_mul(a, b, n):
    c = [0] * n
    for i in range(n):
        if a[i] == 0:
            continue
        for j in range(n):
            if b[j]:
                c[(i + j) % n] ^= 1
    return c

def sample_sparse(n, w, rng):
    positions = rng.sample(range(n), w)
    vec = [0] * n
    for p in positions:
        vec[p] = 1
    return vec

def support(v):
    return [i for i, x in enumerate(v) if x]

def rep_encode(message, r, n):
    codeword = []
    for bit in message:
        codeword.extend([bit] * r)
    codeword.extend([0] * (n - len(codeword)))
    return codeword

def rep_decode(received, r, n):
    k = n // r
    message = []
    for i in range(k):
        block = received[i * r : (i + 1) * r]
        ones = sum(block)
        message.append(1 if ones > r // 2 else 0)
    return message

N, W, W_R, W_E, R = 83, 3, 3, 3, 17
K = N // R

# Reconstruct key from seed 0
rng = random.Random(0)
s = [rng.randint(0, 1) for _ in range(N)]
x = sample_sparse(N, W, rng)
y = sample_sparse(N, W, rng)
h = poly_add(x, poly_mul(s, y, N))

# Encryption
msg = [1, 0, 1, 1]
rng_enc = random.Random(1000)
r1 = sample_sparse(N, W_R, rng_enc)
r2 = sample_sparse(N, W_R, rng_enc)
e = sample_sparse(N, W_E, rng_enc)

u = poly_add(r1, poly_mul(r2, s, N))
codeword = rep_encode(msg, R, N)
v = poly_add(poly_add(poly_mul(r2, h, N), codeword), e)

print("r1 support:", support(r1))
print("r2 support:", support(r2))
print("e support: ", support(e))
print("u weight:", sum(u))
print("v weight:", sum(v))
# ==> r1 support: [12, 50, 54]
# ==> r2 support: [8, 45, 59]
# ==> e support:  [21, 55, 68]
# ==> u weight: 40
# ==> v weight: 42

Encryption samples three fresh sparse vectors $(r_1, r_2, e)$ and computes:

$$u = r_1 + r_2 \cdot s$$ $$v = r_2 \cdot h + \text{encode}(m) + e$$

The ciphertext $(u, v)$ consists of two length-83 binary vectors. The message $[1, 0, 1, 1]$ is encoded by repeating each bit 17 times before adding it to $v$.

import random

def poly_add(a, b):
    return [ai ^ bi for ai, bi in zip(a, b)]

def poly_mul(a, b, n):
    c = [0] * n
    for i in range(n):
        if a[i] == 0:
            continue
        for j in range(n):
            if b[j]:
                c[(i + j) % n] ^= 1
    return c

def sample_sparse(n, w, rng):
    positions = rng.sample(range(n), w)
    vec = [0] * n
    for p in positions:
        vec[p] = 1
    return vec

def rep_encode(message, r, n):
    codeword = []
    for bit in message:
        codeword.extend([bit] * r)
    codeword.extend([0] * (n - len(codeword)))
    return codeword

def rep_decode(received, r, n):
    k = n // r
    message = []
    for i in range(k):
        block = received[i * r : (i + 1) * r]
        ones = sum(block)
        message.append(1 if ones > r // 2 else 0)
    return message

N, W, W_R, W_E, R = 83, 3, 3, 3, 17
K = N // R

# Reconstruct everything from seeds
rng = random.Random(0)
s = [rng.randint(0, 1) for _ in range(N)]
x = sample_sparse(N, W, rng)
y = sample_sparse(N, W, rng)
h = poly_add(x, poly_mul(s, y, N))

msg = [1, 0, 1, 1]
rng_enc = random.Random(1000)
r1 = sample_sparse(N, W_R, rng_enc)
r2 = sample_sparse(N, W_R, rng_enc)
e = sample_sparse(N, W_E, rng_enc)

u = poly_add(r1, poly_mul(r2, s, N))
codeword = rep_encode(msg, R, N)
v = poly_add(poly_add(poly_mul(r2, h, N), codeword), e)

# Decryption
noisy_code = poly_add(v, poly_mul(u, y, N))
noise = poly_add(noisy_code, codeword)
recovered = rep_decode(noisy_code, R, N)

print("noise weight:", sum(noise))
for bi in range(K):
    block = noise[bi * R : (bi + 1) * R]
    print(f"  block {bi}: {sum(block)} errors (capacity 8)")
print("recovered:", recovered)
print("match:", recovered == msg)
# ==> noise weight: 19
# ==>   block 0: 2 errors (capacity 8)
# ==>   block 1: 5 errors (capacity 8)
# ==>   block 2: 5 errors (capacity 8)
# ==>   block 3: 4 errors (capacity 8)
# ==> recovered: [1, 0, 1, 1]
# ==> match: True

Decryption computes $v + u \cdot y$ (over $\text{GF}(2)$, addition equals subtraction). The result is $\text{encode}(m) + \text{noise}$, where the noise term is $r_2 \cdot x + r_1 \cdot y + e$. The noise has weight 19 across 83 positions. Sixteen of those bits land in the four 17-bit repetition blocks, unevenly at 2, 5, 5 and 4, and the remaining three fall in the 15 padding positions the blocks do not cover. Each block has at most 5 errors, well within the correction capacity of $\lfloor(17-1)/2\rfloor = 8$. Majority-vote decoding recovers the original message.

Ring, sparse vectors, and noise budget

The polynomial ring $\text{GF}(2)[x]/(x^n - 1)$

Chapter 19 introduced the ring $\text{GF}(2)[x]/(x^n - 1)$, where polynomials have binary coefficients and multiplication wraps at degree $n$. Two operations define the ring: addition is componentwise XOR, and multiplication is circulant convolution. A polynomial $a(x) = \sum_{i=0}^{n-1} a_i x^i$ is stored as a length-$n$ binary vector $[a_0, a_1, \ldots, a_{n-1}]$.

HQC chooses $n$ to be a primitive prime: prime, and with 2 a primitive root modulo $n$. Primality alone would give $\gcd(n, 2) = 1$ and so a semisimple ring, which is what makes the arithmetic well behaved. Primitivity buys something stronger. It forces $x^n - 1$ to factor into exactly two irreducibles over $\text{GF}(2)$, namely $x - 1$ and one factor of degree $n - 1$, so the ring splits into just two components, $\text{GF}(2) \times \text{GF}(2^{n-1})$. Those are its only proper quotients: the parity map onto $\text{GF}(2)$, whose single bit the parity restriction in the hardness assumption below accounts for, and the full-size $\text{GF}(2^{n-1})$. What primitivity removes is any quotient of intermediate degree, that is, any factor of $x^n - 1$ other than $x - 1$ and the one of degree $n - 1$. The specification names thwarting structural attacks as the reason (Gaborit et al., 2026, sec. 2.3). All three parameter sets satisfy it, and so does the toy’s $n = 83$.

The ring structure means that multiplying two polynomials and reducing modulo $x^n - 1$ is equivalent to multiplying a circulant matrix by a vector. The circulant structure means HQC stores two polynomials of degree less than $n$ rather than a dense matrix.

Sparse vector sampling

A weight-$w$ binary vector has exactly $w$ ones among $n$ positions. The number of such vectors is $\binom{n}{w}$. For the toy parameters ($n = 83$, $w = 3$), there are $\binom{83}{3} = 91{,}881$ possible secret vectors. For HQC-1 ($n = 17{,}669$, $w = 67$), one weight-$w$ vector has approximately $2^{631}$ possibilities. The secret is the pair $(x, y)$, so the naive support space is approximately $(2^{631})^2 \approx 2^{1262}$ (Gaborit et al., 2026). Security is not claimed from this counting argument. The relevant assumption is quasi-cyclic syndrome decoding (QCSD). The count only shows that direct enumeration of the sparse supports is out of reach.

Repetition code

The inner error-correcting code in the toy is a repetition code. Encoding repeats each message bit $r$ times. Decoding applies majority vote to each block of $r$ received bits: if more than $r/2$ bits are 1, decode to 1; otherwise decode to 0. The correction capacity is $\lfloor(r-1)/2\rfloor$ errors per block. With $r = 17$, the code corrects up to 8 errors per block.

The real HQC specification uses a concatenated code, not pure repetition: an outer shortened Reed-Solomon code over $\text{GF}(2^8)$ followed by an inner duplicated first-order Reed-Muller code $\text{RM}(1, 7) = [128, 8, 64]$ (Gaborit et al., 2026, sec. 3.5). Each Reed-Muller codeword bit is duplicated (3 times at level 1, 5 times at levels 3 and 5) and the duplicated block is maximum-likelihood decoded. The resulting symbols are then corrected by an algebraic Reed-Solomon decoder. This concatenation achieves a far better correction-to-rate tradeoff than pure repetition. The toy uses repetition alone because majority-vote decoding has no prerequisites. Reed-Solomon and Reed-Muller decoding would each require their own construction before the cryptosystem.

Noise budget

The correctness of HQC decryption depends on a noise budget. Decryption computes:

$$v + u \cdot y = r_2 \cdot h + \text{encode}(m) + e + (r_1 + r_2 \cdot s) \cdot y$$

Expanding $h = x + s \cdot y$ and simplifying over $\text{GF}(2)$:

$$v + u \cdot y = \text{encode}(m) + \underbrace{r_2 \cdot x + r_1 \cdot y + e}_{\text{noise}}$$

The noise term has three components. Two are products of sparse vectors ($r_2 \cdot x$ and $r_1 \cdot y$), and the third is the error vector $e$. The weight of each product is at most $w_r \cdot w$ (when all cross-terms land at distinct positions), so the total noise weight is at most $2 w_r w + w_e$. For the toy ($w_r = w = w_e = 3$), the worst case is $2 \cdot 3 \cdot 3 + 3 = 21$. In practice, $\text{GF}(2)$ cancellations reduce this. The motivating example above achieved noise weight 19.

Decryption succeeds when every 17-bit repetition block has at most 8 errors. The expected errors per block are approximately $\text{noise\_weight} \cdot r / n$. With noise weight 19 and $r/n = 17/83 \approx 0.20$, the expected per-block errors are about 3.9, well below the capacity of 8. At these toy parameters the multi-seed test below sees 2 failures in 320 deterministic trials (0.625%). That is a coarse smoke-test observation, not a statistically meaningful cryptographic decryption-failure-rate estimate. It only confirms the toy parameters are deliberately small enough for failures to appear at all.

Building HQC in Python

Polynomial arithmetic in $\text{GF}(2)[x]/(x^n - 1)$

Addition is componentwise XOR. Multiplication is the convolution

$$c_k = \sum_{i} a_i b_{(k-i) \bmod n} \bmod 2.$$

def poly_add(a, b):
    return [ai ^ bi for ai, bi in zip(a, b)]

def poly_mul(a, b, n):
    c = [0] * n
    for i in range(n):
        if a[i] == 0:
            continue
        for j in range(n):
            if b[j]:
                c[(i + j) % n] ^= 1
    return c

# Worked example: (1 + x^2 + x^5) * (1 + x + x^3) mod x^83 - 1
N = 83
a = [0] * N
b = [0] * N
a[0], a[2], a[5] = 1, 1, 1
b[0], b[1], b[3] = 1, 1, 1
c = poly_mul(a, b, N)
support = [i for i, v in enumerate(c) if v]
print("product support:", support)
# ==> product support: [0, 1, 2, 6, 8]

The product $(1 + x^2 + x^5)(1 + x + x^3)$ expands to nine terms. Over $\text{GF}(2)$, the $x^3$ and $x^5$ terms each appear twice and cancel, leaving $1 + x + x^2 + x^6 + x^8$. All degrees are below 83, so the modular reduction has no effect in this example.

Sparse vector sampling

import random

def sample_sparse(n, w, rng):
    positions = rng.sample(range(n), w)
    vec = [0] * n
    for p in positions:
        vec[p] = 1
    return vec

rng = random.Random(42)
v = sample_sparse(83, 3, rng)
support = [i for i, x in enumerate(v) if x]
print("support:", support)
print("weight: ", sum(v))
# ==> support: [3, 14, 81]
# ==> weight:  3

The function selects $w$ positions uniformly at random without replacement, then sets those positions to 1. Taking a random.Random instance makes sampling deterministic for a given seed.

The toy’s randomness is not cryptographic randomness

random.Random appears here only so the printed supports and weights reproduce on the reader’s machine. A real HQC implementation must draw every sparse vector from an approved cryptographic random-bit generator. A seeded Mersenne Twister leaks its internal state to anyone who sees enough output, which in this construction means the secret $(x, y)$.

Repetition code

Encoding repeats each bit $r$ times and pads to length $n$.

def rep_encode(message, r, n):
    codeword = []
    for bit in message:
        codeword.extend([bit] * r)
    codeword.extend([0] * (n - len(codeword)))
    return codeword

def rep_decode(received, r, n):
    k = n // r
    message = []
    for i in range(k):
        block = received[i * r : (i + 1) * r]
        ones = sum(block)
        message.append(1 if ones > r // 2 else 0)
    return message

msg = [1, 0, 1, 1]
R, N = 17, 83
cw = rep_encode(msg, R, N)
print("first block (17 bits):", cw[:17])
print("second block (17 bits):", cw[17:34])
# ==> first block (17 bits): [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
# ==> second block (17 bits): [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Message bit 1 becomes 17 ones; message bit 0 becomes 17 zeros. The codeword occupies $4 \times 17 = 68$ of the 83 positions. The remaining 15 are zero-padded.

Decoding tolerates errors up to the correction capacity.

def rep_encode(message, r, n):
    codeword = []
    for bit in message:
        codeword.extend([bit] * r)
    codeword.extend([0] * (n - len(codeword)))
    return codeword

def rep_decode(received, r, n):
    k = n // r
    message = []
    for i in range(k):
        block = received[i * r : (i + 1) * r]
        ones = sum(block)
        message.append(1 if ones > r // 2 else 0)
    return message

msg = [1, 0, 1, 1]
R, N = 17, 83
cw = rep_encode(msg, R, N)

# Inject 5 errors into the first block
corrupted = list(cw)
for i in [2, 5, 8, 11, 14]:
    corrupted[i] = 1 - corrupted[i]

block0 = corrupted[:R]
ones = sum(block0)
print(f"corrupted block 0: {ones} ones out of {R}")
print(f"majority vote: {'1' if ones > R // 2 else '0'}")
recovered = rep_decode(corrupted, R, N)
print("decoded message:", recovered)
# ==> corrupted block 0: 12 ones out of 17
# ==> majority vote: 1
# ==> decoded message: [1, 0, 1, 1]

Five of the 17 ones in block 0 were flipped to zeros, leaving 12 ones. Since $12 > 17/2 = 8.5$, majority vote still decodes to 1. The correction capacity is 8 errors per block, and 5 errors is well within that limit.

HQC key generation

Key generation samples a uniform random polynomial $s$, two sparse secret vectors $(x, y)$ with weight $w$, and computes $h = x + s \cdot y$.

import random

def poly_add(a, b):
    return [ai ^ bi for ai, bi in zip(a, b)]

def poly_mul(a, b, n):
    c = [0] * n
    for i in range(n):
        if a[i] == 0:
            continue
        for j in range(n):
            if b[j]:
                c[(i + j) % n] ^= 1
    return c

def sample_sparse(n, w, rng):
    positions = rng.sample(range(n), w)
    vec = [0] * n
    for p in positions:
        vec[p] = 1
    return vec

N, W = 83, 3
rng = random.Random(0)
s = [rng.randint(0, 1) for _ in range(N)]
x = sample_sparse(N, W, rng)
y = sample_sparse(N, W, rng)
h = poly_add(x, poly_mul(s, y, N))

x_pos = [i for i, v in enumerate(x) if v]
y_pos = [i for i, v in enumerate(y) if v]
print("x support:", x_pos)
print("y support:", y_pos)
print("h weight: ", sum(h))
print("public key size: 2 *", N, "=", 2 * N, "bits")
# ==> x support: [14, 41, 78]
# ==> y support: [62, 75, 80]
# ==> h weight:  46
# ==> public key size: 2 * 83 = 166 bits

The public key $(s, h)$ is $2n = 166$ bits. For comparison, an unstructured code of the same shape, length $2n$ and dimension $n$, publishes the $n \times n$ non-identity block of its parity-check matrix explicitly, $n^2 = 6{,}889$ bits, plus the 83-bit syndrome. The quasi-cyclic structure compresses that explicit form by a factor of $(n + 1)/2 = 42$ at these toy parameters. The factor widens with $n$, because the dense block grows as $n^2$ while two ring elements grow as $n$.

HQC encryption

Encryption samples three sparse vectors $(r_1, r_2, e)$ and computes the ciphertext $(u, v)$.

import random

def poly_add(a, b):
    return [ai ^ bi for ai, bi in zip(a, b)]

def poly_mul(a, b, n):
    c = [0] * n
    for i in range(n):
        if a[i] == 0:
            continue
        for j in range(n):
            if b[j]:
                c[(i + j) % n] ^= 1
    return c

def sample_sparse(n, w, rng):
    positions = rng.sample(range(n), w)
    vec = [0] * n
    for p in positions:
        vec[p] = 1
    return vec

def rep_encode(message, r, n):
    codeword = []
    for bit in message:
        codeword.extend([bit] * r)
    codeword.extend([0] * (n - len(codeword)))
    return codeword

N, W, W_R, W_E, R = 83, 3, 3, 3, 17

# Reconstruct public key from seed 0
rng = random.Random(0)
s = [rng.randint(0, 1) for _ in range(N)]
x = sample_sparse(N, W, rng)
y = sample_sparse(N, W, rng)
h = poly_add(x, poly_mul(s, y, N))

# Encrypt message [1, 0, 1, 1]
msg = [1, 0, 1, 1]
rng_enc = random.Random(1000)
r1 = sample_sparse(N, W_R, rng_enc)
r2 = sample_sparse(N, W_R, rng_enc)
e = sample_sparse(N, W_E, rng_enc)

u = poly_add(r1, poly_mul(r2, s, N))
codeword = rep_encode(msg, R, N)
v = poly_add(poly_add(poly_mul(r2, h, N), codeword), e)

r1_pos = [i for i, v in enumerate(r1) if v]
r2_pos = [i for i, v in enumerate(r2) if v]
e_pos = [i for i, v in enumerate(e) if v]
print("r1 support:", r1_pos)
print("r2 support:", r2_pos)
print("e support: ", e_pos)
print("ciphertext size: 2 *", N, "=", 2 * N, "bits")
# ==> r1 support: [12, 50, 54]
# ==> r2 support: [8, 45, 59]
# ==> e support:  [21, 55, 68]
# ==> ciphertext size: 2 * 83 = 166 bits

The ciphertext $(u, v)$ is also $2n$ bits.

HQC decryption and noise cancellation

Decryption computes $v + u \cdot y$ and decodes the repetition code.

import random

def poly_add(a, b):
    return [ai ^ bi for ai, bi in zip(a, b)]

def poly_mul(a, b, n):
    c = [0] * n
    for i in range(n):
        if a[i] == 0:
            continue
        for j in range(n):
            if b[j]:
                c[(i + j) % n] ^= 1
    return c

def sample_sparse(n, w, rng):
    positions = rng.sample(range(n), w)
    vec = [0] * n
    for p in positions:
        vec[p] = 1
    return vec

def rep_encode(message, r, n):
    codeword = []
    for bit in message:
        codeword.extend([bit] * r)
    codeword.extend([0] * (n - len(codeword)))
    return codeword

def rep_decode(received, r, n):
    k = n // r
    message = []
    for i in range(k):
        block = received[i * r : (i + 1) * r]
        ones = sum(block)
        message.append(1 if ones > r // 2 else 0)
    return message

N, W, W_R, W_E, R = 83, 3, 3, 3, 17
K = N // R

# Reconstruct everything from seeds
rng = random.Random(0)
s = [rng.randint(0, 1) for _ in range(N)]
x = sample_sparse(N, W, rng)
y = sample_sparse(N, W, rng)
h = poly_add(x, poly_mul(s, y, N))

msg = [1, 0, 1, 1]
rng_enc = random.Random(1000)
r1 = sample_sparse(N, W_R, rng_enc)
r2 = sample_sparse(N, W_R, rng_enc)
e = sample_sparse(N, W_E, rng_enc)

u = poly_add(r1, poly_mul(r2, s, N))
codeword = rep_encode(msg, R, N)
v = poly_add(poly_add(poly_mul(r2, h, N), codeword), e)

# Decryption
noisy_code = poly_add(v, poly_mul(u, y, N))
recovered = rep_decode(noisy_code, R, N)

# Verify the noise decomposition
noise = poly_add(noisy_code, codeword)
expected_noise = poly_add(
    poly_add(poly_mul(r2, x, N), poly_mul(r1, y, N)), e
)
print("noise matches r2*x + r1*y + e:", noise == expected_noise)
print("noise weight:", sum(noise))
print("recovered:", recovered)
print("correct:", recovered == msg)
# ==> noise matches r2*x + r1*y + e: True
# ==> noise weight: 19
# ==> recovered: [1, 0, 1, 1]
# ==> correct: True

The noise decomposes exactly as the derivation predicts: $r_2 \cdot x + r_1 \cdot y + e$. Of the 19 noise bits, 16 fall in the four active repetition blocks and 3 fall in the 15-position zero-padding zone (positions 68 through 82) that the decoder ignores. No active block receives more than 8 errors, so majority-vote decoding succeeds.

Figure 21.1 shows the IND-CPA PKE core inside HQC at the toy parameters of this chapter, not the full salted HHK KEM wrapper (the Fujisaki-Okamoto section covers that). The key observation is that decryption cancels the quasi-cyclic outer layer via the secret $y$, leaving a bounded-weight noise term that the inner code corrects.

Figure 21.1. The HQC IND-CPA PKE core at the toy parameters of this chapter, not the full salted HHK KEM wrapper (covered in the Fujisaki-Okamoto section). KeyGen samples a uniform s and sparse secret (x, y) and publishes (s, h) with h = x + s·y. Encrypt samples sparse randomness (r1, r2, e), repetition-encodes the message, and emits (u, v) = (r1 + s·r2, Enc(m) + h·r2 + e). Decrypt computes v - y·u, which equals Enc(m) plus a bounded noise term, and majority-vote decodes the inner code to recover m. Real HQC replaces the repetition code with a concatenated outer Reed-Solomon and inner duplicated Reed-Muller code per the reference specification.

The flow makes the double-layer structure visible. The outer layer is the quasi-cyclic structure: (s, h) and (u, v) live in R_n = GF(2)[x] / (x^n - 1), and encryption adds a mask h · r_2 that decryption cancels via the secret y. The inner layer is the error-correcting code: the residual ε = r_2 · x + r_1 · y + e has bounded weight, and the inner decoder cleans it up. The toy uses repetition for the inner layer; HQC uses a concatenated outer Reed-Solomon and inner duplicated Reed-Muller code with a far better correction-to-rate tradeoff.

Multi-seed round-trip

One trial with a fixed seed does not test whether the noise budget holds across the space of key pairs and messages. The following test runs all 16 possible 4-bit messages across 20 independent key pairs (320 trials total).

import random

def poly_add(a, b):
    return [ai ^ bi for ai, bi in zip(a, b)]

def poly_mul(a, b, n):
    c = [0] * n
    for i in range(n):
        if a[i] == 0:
            continue
        for j in range(n):
            if b[j]:
                c[(i + j) % n] ^= 1
    return c

def sample_sparse(n, w, rng):
    positions = rng.sample(range(n), w)
    vec = [0] * n
    for p in positions:
        vec[p] = 1
    return vec

def rep_encode(message, r, n):
    codeword = []
    for bit in message:
        codeword.extend([bit] * r)
    codeword.extend([0] * (n - len(codeword)))
    return codeword

def rep_decode(received, r, n):
    k = n // r
    message = []
    for i in range(k):
        block = received[i * r : (i + 1) * r]
        ones = sum(block)
        message.append(1 if ones > r // 2 else 0)
    return message

N, W, W_R, W_E, R = 83, 3, 3, 3, 17
K = N // R
successes = 0
total = 0

for seed in range(20):
    rng_k = random.Random(seed)
    s = [rng_k.randint(0, 1) for _ in range(N)]
    x = sample_sparse(N, W, rng_k)
    y = sample_sparse(N, W, rng_k)
    h = poly_add(x, poly_mul(s, y, N))

    for mi in range(2**K):
        m = [(mi >> b) & 1 for b in range(K)]
        rng_e = random.Random(seed * 1000 + mi + 5000)
        r1 = sample_sparse(N, W_R, rng_e)
        r2 = sample_sparse(N, W_R, rng_e)
        e = sample_sparse(N, W_E, rng_e)
        u = poly_add(r1, poly_mul(r2, s, N))
        cw = rep_encode(m, R, N)
        v = poly_add(poly_add(poly_mul(r2, h, N), cw), e)
        noisy = poly_add(v, poly_mul(u, y, N))
        rec = rep_decode(noisy, R, N)
        total += 1
        if rec == m:
            successes += 1

print(f"{successes}/{total} round-trips succeeded")
# ==> 318/320 round-trips succeeded

318 of 320 trials succeed. The two failures occur when the noise concentrates in one repetition block, exceeding the correction capacity of 8. This 2-in-320 figure is a deterministic smoke-test observation, not a cryptographic decryption-failure-rate estimate: the toy parameters are deliberately small enough for failures to appear at all. HQC is not perfectly correct. The decryption failure rate (DFR) is a design parameter, and the specification keeps HQC-1’s below $2^{-127}$ (Table 8 in Gaborit et al., 2026).

The Fujisaki-Okamoto wrapper

The scheme above is IND-CPA secure: it resists chosen-plaintext attacks. For KEM applications (key encapsulation), IND-CCA2 security is required. HQC’s specification builds its KEM from the public-key scheme with a salted Fujisaki-Okamoto transform with implicit rejection, and shows the result IND-CCA2-secure in the random-oracle model (Gaborit et al., 2026, sec. 6.2). The transform keeps the re-encryption check of Fujisaki and Okamoto’s 1999 construction (Fujisaki & Okamoto, 1999), the idea modern lattice KEMs such as ML-KEM also use (Chapter 11, section “The Fujisaki-Okamoto wrapper”), though the exact construction differs.

The construction below is the FO/HHK idea in simplified form. The reference HQC KEM uses a salted variant: HHK with implicit rejection, a 16-byte salt carried in the ciphertext, and the encapsulation key folded into the hash inputs. The exact byte-level derivation is specified in the HQC document (Gaborit et al., 2026, sec. 3.7). The simplified transform wraps the IND-CPA scheme into a KEM with three operations:

1. KeyGen: run IND-CPA key generation. Sample a rejection seed $z$. The encapsulation key is the IND-CPA public key. The decapsulation key bundles the IND-CPA secret key, the public key, and $z$.
2. Encaps(ek): sample a random message $m$. Derive encryption randomness $r = H(m \| \text{ek})$. Run IND-CPA encryption with randomness $r$ to produce ciphertext $c$. Compute shared secret $K = G(m \| c)$. Return $(K, c)$.
3. Decaps(dk, c): run IND-CPA decryption to recover $m'$. Recompute $r' = H(m' \| \text{ek})$ and $c' = \text{Encrypt}(\text{ek}, m'; r')$. If $c' = c$, return $K = G(m' \| c)$. Otherwise return $K_{\text{reject}} = J(z \| c)$, an implicit rejection that leaks no information about the secret key.

The re-encryption check is the core of IND-CCA2 security. An attacker who submits a modified ciphertext gets the rejection key $J(z \| c)$, which is indistinguishable from random. The formal reduction from IND-CPA to IND-CCA2 for the unsalted transform with implicit rejection, in the random-oracle model, appears in Hofheinz, Hövelmanns, and Kiltz (Hofheinz et al., 2017, sec. 3). The specification states its own bound for the salted variant (Theorem 6.4 in Gaborit et al., 2026).

The toy implementation in this chapter demonstrates the IND-CPA core. The FO wrapping is structural (hashing and re-encryption), not algebraic.

Reference KAT compliance

The book’s from-scratch builds of the three finalized standards, ML-KEM, ML-DSA and SLH-DSA, are each checked against NIST’s published ACVP vectors in their test suites. This chapter’s HQC does not meet that bar, and the divergence from the reference specification is deliberate rather than a shortfall. It runs on four fronts:

• Inner code: plain repetition here; a concatenated outer Reed-Solomon and inner duplicated Reed-Muller code in the reference.
• Wrapping: IND-CPA PKE here; FO-wrapped IND-CCA2 KEM in the reference.
• Ring degree: n = 83 for the per-page walkthrough; 17669 / 35851 / 57637 in the reference at security levels 1, 3, and 5.
• Randomness schedule: Python’s random.Random(seed) here; the NIST submission’s deterministic-random-bit-generator schedule in the reference.

The block below sketches the call shape a reference-compliant implementation would expose. The surrounding chapter exercises the toy. The block is an exception marker, not a working runtime. See tests/ch21/vectors/README.md for fetch instructions for the official KAT files and tests/ch21/test_vectors.py for the harness that activates when those files are vendored. On 19 October 2026 the reference repository’s only release was still that of 22 August 2025, so its KAT files follow the August 2025 specification. Their values will not match an implementation of the October 2026 one, and their decapsulation keys are the 2,321-byte expanded form, not the 32-byte seed the later revision makes the default (p. 2 in Gaborit et al., 2026).

# A reference-compliant HQC-1 KEM exposes the four NIST KAT fields.
# The toy in this chapter does not match this call shape; a reference
# build would live under solutions/ch21-hqc-reference/.
#
# from hqc_reference.hqc128 import keygen, encaps, decaps
# seed = bytes.fromhex("...")          # NIST KAT "seed" field, 48 bytes
# pk, sk = keygen(seed=seed)            # expected pk == 2241 bytes, sk == 32
# ct, ss = encaps(pk, seed=seed)        # expected ct == 4433, ss == 32 bytes
# ss_prime = decaps(ct, sk)             # expected ss_prime == ss

Cryptanalysis and known attacks

The quasi-cyclic syndrome decoding problem

HQC’s IND-CPA security rests on two decisional quasi-cyclic syndrome decoding assumptions, not one. The specification’s Theorem 6.3 bounds an adversary’s advantage against the PKE by the sum of the advantages against them (Gaborit et al., 2026, sec. 6.2.1):

$$\text{Adv}^{\text{IND-CPA}}_{\text{HQC-PKE}}(\mathcal{A}) \leq \text{Adv}^{\text{2-DQCSD-P}}(\mathcal{B}_1) + \text{Adv}^{\text{3-DQCSD-PT}}(\mathcal{B}_2)$$

The first assumption covers the public key, the second the ciphertext. 2-DQCSD-P asks an attacker to distinguish the syndrome of a fixed-weight vector under a two-block quasi-cyclic parity-check matrix from a uniform pair, with the parity of the matrix and of the syndrome fixed rather than free. 3-DQCSD-PT is the three-block version of the same question, with one further twist. The concatenated codeword has length $n_1 n_2'$, in the specification’s notation the outer code’s length times the duplicated Reed-Muller code’s. That length is not prime, so HQC works in the ring of the first primitive prime $n$ above it and drops the last $l = n - n_1 n_2'$ bits where they are not needed. At HQC-1 that is 5 bits of a 17,669-bit ring (Gaborit et al., 2026, sec. 2.3). The IND-CCA2 bound for the KEM reuses both advantages, doubled, and adds the terms the salted Fujisaki-Okamoto transform contributes (Gaborit et al., 2026, sec. 6.2.2).

At the toy’s scale, the first reduction target reads: distinguish pairs $(s, h = x + s \cdot y)$ with sparse $(x, y)$ from pairs with $h$ drawn uniformly among the ring elements of the right parity, for a known public $s$. The parity restriction is not optional: evaluating a polynomial at $1$ turns a product into a product of weight parities, so with the secrets of odd weight $w$ every honest $h$ satisfies $h(1) = 1 + s(1)$. A comparison against an unrestricted uniform $h$ would be won by that one bit half the time. That is the “P” in 2-DQCSD-P.

The search variant asks the attacker to recover sparse $(x, y)$ from a public instance. An efficient search solver would also yield a distinguisher, so search is at least as hard as the decisional problem. Both are structured variants of the generic syndrome decoding problem (SDP), the benchmark Chapter 20 keeps apart from McEliece’s own assumption. The quasi-cyclic structure gives the attacker additional algebraic information: the code is invariant under cyclic shifts.

ISD against HQC

The information-set decoding (ISD) algorithms from Chapter 19 (Prange, Lee-Brickell, Stern, BJMM) apply to HQC, and the quasi-cyclic structure does buy the attacker something. Every cyclic shift of a quasi-cyclic instance is another valid instance of the same problem, so an attacker who only needs to solve one of them gets $n$ targets for the price of one. That is the DOOM attack (decoding one out of many), and the specification prices its gain at $O(\sqrt{n})$ and subtracts it before setting parameters (Gaborit et al., 2026, sec. 6.3). At HQC-1’s $n = 17{,}669$ the factor is about 133, or roughly 7 bits. The published security levels already have it deducted, which is the point worth taking away: the structure is not free, it is paid for in the parameter sizes.

Structural attacks

Unlike SIDH (Chapter 22), where Castryck and Decru found an attack exploiting auxiliary torsion-point information that runs in heuristic polynomial time when the starting curve’s endomorphism ring is known (Castryck & Decru, 2023), no comparable break exists against QCSD. The structural attacks that have been studied against quasi-cyclic codes work on the factorization of $x^n - 1$, and they get sharper the more low-degree factors it has. This is where the ring choice earns its keep: with $n$ a primitive prime, $x^n - 1$ has exactly two irreducible factors over $\text{GF}(2)$ and that family of attacks becomes ineffective (Gaborit et al., 2026, sec. 6.3). The defense is a design constraint on $n$ rather than an absence of attempts, which is a weaker guarantee than it first sounds, since it holds only as long as no attack is found that the two-factor condition does not block.

Decryption failure rate

HQC is not perfectly correct. In the toy, decryption fails when too many errors of the noise vector $r_2 \cdot x + r_1 \cdot y + e$ land in one repetition block. In real HQC the corresponding event is a failure of the concatenated Reed-Solomon and duplicated Reed-Muller decoder under the sampled error distribution. The probability of decryption failure is the decryption failure rate (DFR). A high DFR enables reaction attacks: an adversary submits many ciphertexts and uses the pattern of decryption failures to extract the secret key.

The specification bounds HQC-1’s DFR by $2^{-127.9}$, under the refined failure model its October 2026 revision adopted (Table 16 in Gaborit et al., 2026). The concatenated Reed-Solomon and duplicated Reed-Muller inner code has far higher correction capacity than the pure repetition code used in the toy. The toy’s 2-in-320 smoke-test failures at $n = 83$ reflect the deliberately small parameters, not a weakness in the construction.

NIST parameter sets

In March 2025 NIST selected HQC for standardization as an additional code-based KEM and a backup to the already-finalized ML-KEM (National Institute of Standards and Technology, 2025a, 2025b). The HQC standard had not been published by 19 October 2026. The three parameter sets are, from the October 2026 specification (Tables 8 and 9 in Gaborit et al., 2026):

Set	$n$	$w$	$w_r{=}w_e$	DFR	PK (B)	CT (B)	Lvl
HQC-1	17,669	67	76	$< 2^{-127}$	2,241	4,433	1
HQC-3	35,851	101	114	$< 2^{-192}$	4,514	8,978	3
HQC-5	57,637	132	150	$< 2^{-256}$	7,237	14,421	5

The October 2026 revision raised $w$ by 1 in all three sets and $w_r = w_e$ by 1 in HQC-1 and HQC-5. The August 2025 specification had $w$ of 66, 100 and 131 and $w_r = w_e$ of 75, 114 and 149 (Gaborit et al., 2025). The revision’s refined analysis of the decryption failure rate made room for the extra noise, and HQC-1’s tabulated bound moved from below $2^{-128}$ to below $2^{-127}$. The specification gives the raise as compensation for a small improvement in information-set decoding (p. 2 in Gaborit et al., 2026). The key and ciphertext sizes did not change.

Two names for the same three sets

The August 2025 specification renamed these sets HQC-1, HQC-3 and HQC-5 (Gaborit et al., 2025), the October 2026 specification keeps those names, and this book follows them. Earlier NIST-round documents and most published benchmarks call them hqc-128, hqc-192 and hqc-256. A name does not fix a set’s parameters. The October 2026 revision raised the weights under the same names and kept the sizes, so a security estimate, failure rate or timing published before it is for the earlier sets, whichever name it uses.

Each concatenated code pairs an outer shortened Reed-Solomon code over $\text{GF}(2^8)$ with an inner duplicated $\text{RM}(1,7)$ code, written $[n, k, d]$ (length, dimension, minimum distance):

Lvl	Outer RS	Inner dup-RM	Duplication
1	$[46, 16, 31]$	$[384, 8, 192]$	3
3	$[56, 24, 33]$	$[640, 8, 320]$	5
5	$[90, 32, 59]$	$[640, 8, 320]$	5

Reed-Solomon codes are maximum-distance-separable, so the outer code has $d = n - k + 1$ (for level 1, $46 - 16 + 1 = 31$). The inner code repeats each bit of the $\text{RM}(1,7) = [128, 8, 64]$ codeword, so its length and its minimum distance both scale with the duplication multiplicity (Gaborit et al., 2026, sec. 3.5). At level 1 the multiplicity is 3, giving $128 \times 3 = 384$ and $64 \times 3 = 192$; at levels 3 and 5 it is 5, giving $128 \times 5 = 640$ and $64 \times 5 = 320$.

The public key and ciphertext sizes grow linearly with $n$. At level 1, HQC’s public key is roughly 116x smaller than that of mceliece348864, which claims the same level (2,241 B vs 261,120 B).

Tradeoffs: McEliece, HQC, and ML-KEM

Property	Classic McEliece (348864)	HQC-1	ML-KEM-512
Public key	261,120 B	2,241 B	800 B (National Institute of Standards and Technology, 2024)
Ciphertext	96 B	4,433 B	768 B (National Institute of Standards and Technology, 2024)
pk + ct	261,216 B	6,674 B	1,568 B
Assumption	Goppa-code SDP + structural resistance	QCSD	Module-LWE
Assumption introduced	1978	2016 (search form: by 2007)	2012
DFR	0	$< 2^{-127}$	Negligible ($< 2^{-139}$)
NIST status	Not selected (National Institute of Standards and Technology, 2025a)	Selected 2025; FIPS pending (National Institute of Standards and Technology, 2025b)	Standard (FIPS 203)

Key and ciphertext sizes are performance properties. McEliece has the smallest ciphertext (96 bytes) but the largest public key (261 KB). HQC-1 has a public key roughly 116x smaller than mceliece348864’s and a ciphertext about 46x larger. ML-KEM has the smallest combined size but rests on a lattice assumption rather than a code-based one.

HQC’s assumption date is that of the paper that introduced the scheme and its decisional assumption (Definition 13 and Theorem 1 in Aguilar et al., 2016), and the bracketed date is for the search problem (§IV-B in Gaborit & Girault, 2007). The current proof uses later versions with parity and truncation. The 2016 form compares against a uniform distribution with no parity restriction (Definition 13 in Aguilar et al., 2016), so the one-bit distinguisher described in the cryptanalysis section above breaks it, and the parity condition was added as a countermeasure (p. 4 in Gaborit et al., 2026).

The status row gives NIST’s decisions alone. ML-KEM was standardized as FIPS 203 in 2024. NIST selected HQC in March 2025 as a backup code-based KEM (National Institute of Standards and Technology, 2025a, 2025b). No draft of its standard had been published by 19 October 2026. ISO’s publication of Classic McEliece in June 2026, which left out mceliece348864, is a separate record (Classic McEliece, 2026; ISO/IEC JTC 1/SC 27, 2026). So is BSI’s note of September 2026, which Chapter 20’s update of October 2026 reports. The note advises against Classic McEliece in new applications, and names HQC, once its standard is published, among the schemes it advises for key agreement (p. 1 in German Federal Office for Information Security, 2026).

Chapter 22 leaves linear codes for a different mathematical object: isogenies between elliptic curves. It also carries forward the bargain the cryptanalysis section above named. HQC publishes algebraic structure, the quasi-cyclic relations, in order to shrink its key, and pays for the speedup that structure hands an attacker in its parameter sizes. SIDH published auxiliary torsion-point images in order to make its key exchange work, and in 2022 Castryck and Decru turned exactly those against it. Chapter 22 builds the broken scheme first and then explains the break, because on this question the failure teaches more than the survivor does.

Exercises

Exercise 1. Reimplement the toy HQC at $n = 97$, $w = 3$, $w_r = 3$, $w_e = 3$, $r = 17$. Compute the message length $k = \lfloor 97/17 \rfloor$. Run 20 key seeds with all $2^k$ messages per seed. Compare the decryption failure rate to the $n = 83$ toy.

Exercise 2. For HQC-1-like weights ($n = 17{,}669$, $w = 67$, $w_r = w_e = 76$), compute the worst-case noise weight bound $2 w_r w + w_e = 2 \cdot 76 \cdot 67 + 76 = 10{,}260$. As a toy repetition-code thought experiment, assume this noise were spread uniformly across length-$r$ repetition blocks and compute the expected errors per block. Why does this toy calculation overestimate the actual decryption failure rate of real HQC? (Hint: $\text{GF}(2)$ cancellations in polynomial products, the probabilistic distribution of errors, and the fact that real HQC uses a concatenated Reed-Solomon and duplicated Reed-Muller decoder rather than pure repetition.)

Exercise 3. Fill in a table of public key + ciphertext sizes for Classic McEliece, HQC, and ML-KEM, grouping their parameter sets by the NIST security level each claims: 1, 3, and 5. At which level does HQC have the smallest pk + ct sum among the three? At which level is the ratio of McEliece’s public key to HQC’s largest?

Exercise 4. For repetition factors $r = 3, 5, 7, 11, 17$, compute the correction capacity $\lfloor(r-1)/2\rfloor$ and the code rate $1/r$ (each message bit costs $r$ codeword bits). Why does pure repetition become impractical at the scale of HQC-1? What property of HQC’s concatenated Reed-Solomon and duplicated Reed-Muller code makes it more efficient?

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

References

Aguilar, C., Blazy, O., Deneuville, J.-C., Gaborit, P., & Zémor, G. (2016). Efficient Encryption from Random Quasi-Cyclic Codes. arXiv:1612.05572v1 [cs.CR]. https://arxiv.org/abs/1612.05572v1

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

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. (2026). 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

Fujisaki, E., & Okamoto, T. (1999). Secure integration of asymmetric and symmetric encryption schemes. Advances in Cryptology – CRYPTO 1999, 1666, 537–554. https://doi.org/10.1007/3-540-48405-1_34

Gaborit, P., Aguilar-Melchor, C., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.-C., Persichetti, E., Zémor, G., Bos, J., Dion, A., Lacan, J., Robert, J.-M., Véron, P., Barreto, P. S. L. M., Ghosh, S., Gueron, S., Güneysu, T., Misoczki, R., … Vasseur, V. (2025). HQC: Hamming Quasi-Cyclic. https://pqc-hqc.org/doc/hqc_specifications_2025_08_22.pdf

Gaborit, P., Aguilar-Melchor, C., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.-C., Persichetti, E., Zémor, G., Bos, J., Dion, A., Lacan, J., Robert, J.-M., Véron, P., Barreto, P. S. L. M., Ghosh, S., Gueron, S., Güneysu, T., Misoczki, R., … Vasseur, V. (2026). HQC: Hamming Quasi-Cyclic. https://pqc-hqc.org/doc/hqc_specifications_2026_10_12.pdf

Gaborit, P., & Girault, M. (2007). Lightweight code-based identification and signature. 2007 IEEE International Symposium on Information Theory (ISIT), 191–195. https://doi.org/10.1109/ISIT.2007.4557225

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

Hofheinz, D., Hövelmanns, K., & Kiltz, E. (2017). A modular analysis of the Fujisaki-Okamoto transformation. Theory of Cryptography – TCC 2017, Part I, 10677, 341–371. https://doi.org/10.1007/978-3-319-70500-2_12

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

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. (2024). FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.203

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