Chapter 21: HQC, a pedagogical implementation

Classic McEliece (Chapter 20) rests on a 48-year-old assumption, but its public keys are enormous: 261,120 bytes at NIST security level 1 (Albrecht et al., 2022). The key is the non-identity block of a parity-check matrix reduced to systematic form, and it looks random (Chapter 20). Transmitting that matrix once per session is impractical for bandwidth-constrained protocols like TLS handshakes on embedded hardware.

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

The tradeoff is assumption strength. 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). 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 (2017 vs 1978) and less studied. 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. 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. 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., 2025, 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 = 66$), one weight-$w$ vector has approximately $2^{623}$ possibilities. The secret is the pair $(x, y)$, so the naive support space is approximately $(2^{623})^2 \approx 2^{1246}$ (Gaborit et al., 2025). 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., 2025, sec. 3.4). 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 at the same length publishes the $(n-k) \times k$ non-identity block of its parity-check matrix, which is $k(n-k)$ bits. With $k \approx n/2$, that is approximately $83^2 / 4 \approx 1{,}722$ bits. The quasi-cyclic structure compresses the key by a factor of roughly 10 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 real HQC parameters target $\text{DFR} < 2^{-128}$ at security level 1 (Gaborit et al., 2025).

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 achieves this with a Fujisaki-Okamoto-style transform (Fujisaki & Okamoto, 1999), the same re-encryption-check idea used by modern lattice KEMs such as ML-KEM (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., 2025, sec. 3.6). 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 security reduction from IND-CPA to IND-CCA2 via the FO transform with implicit rejection, in the random-oracle model, appears in Hofheinz, Hovelmanns, and Kiltz (Hofheinz et al., 2017, sec. 3).

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.

# 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 == 2321
# 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.2 bounds an adversary’s advantage against the PKE by the sum of the advantages against them (Gaborit et al., 2025, 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$, which 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., 2025, 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., 2025, 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) that McEliece relies on. 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., 2025, 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., 2025, sec. 6.3). The defence 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 HQC parameter selection targets $\text{DFR} < 2^{-128}$ at security level 1. 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, but the HQC standard is not yet published (National Institute of Standards and Technology, 2025a, 2025b). The three parameter sets are, with sizes from the August 2025 specification (Gaborit et al., 2025):

Set	$n$	$w$	$w_r{=}w_e$	DFR	PK (B)	CT (B)	Lvl
HQC-1	17,669	66	75	$< 2^{-128}$	2,241	4,433	1
HQC-3	35,851	100	114	$< 2^{-192}$	4,514	8,978	3
HQC-5	57,637	131	149	$< 2^{-256}$	7,237	14,421	5

Two names for the same three sets

The August 2025 specification names these sets HQC-1, HQC-3 and HQC-5 throughout, and this book follows it. Earlier NIST-round documents, the reference implementation’s build targets, and most published benchmarks call them hqc-128, hqc-192 and hqc-256. The parameters are the same; only the labels changed.

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., 2025, sec. 3.4). 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 Classic McEliece (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	2017	2012
DFR	0	$< 2^{-128}$	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)

McEliece has the smallest ciphertext (96 bytes) but the largest public key (261 KB). HQC compresses the public key by roughly 116x at the cost of a ciphertext about 46x larger. ML-KEM has the smallest combined size but rests on a lattice assumption rather than a code-based one. ML-KEM was standardized as FIPS 203 in 2024. NIST selected HQC in March 2025 as a backup code-based KEM, with its standard not yet finalized (National Institute of Standards and Technology, 2025a, 2025b).

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 = 66$, $w_r = w_e = 75$), compute the worst-case noise weight bound $2 w_r w + w_e = 2 \cdot 75 \cdot 66 + 75 = 9{,}975$. 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 at NIST security levels 1, 3, and 5. At which level does HQC have the smallest pk + ct sum among the three? At which level is the McEliece-to-HQC key compression ratio 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

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 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

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

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