Appendix D: Solutions for Chapter 21

This page collects solutions and editorial notes for the exercises in Chapter 21: HQC, a pedagogical implementation. Compute and derivation exercises have worked solutions; open-ended exercises have an editorial note describing what a strong answer addresses.

The fuller versions of these routines are in the hqc package under solutions/ch21-hqc. From a clone of the companion repository, pytest tests/ch21 runs its suite. Appendix C has the setup.

Exercise 1

$k = \lfloor 97/17 \rfloor = 5$, so each seed runs $2^5 = 32$ messages and the full sweep is $20 \cdot 32 = 640$ trials. Running the chapter’s multi-seed harness with $N$ changed to 97 gives:

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]
        message.append(1 if sum(block) > r // 2 else 0)
    return message

N, W, W_R, W_E, R = 97, 3, 3, 3, 17
K = N // R
successes = 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))
        total += 1
        if rep_decode(noisy, R, N) == m:
            successes += 1

print(f"k = {K}")
print(f"{successes}/{total} round-trips succeeded")
print(f"failures: {total - successes}")
# ==> k = 5
# ==> 638/640 round-trips succeeded
# ==> failures: 2

Two failures in 640, or 0.31%, against the chapter’s 2 in 320 at $n = 83$, or 0.63%. The rate halves. Both are deterministic smoke-test observations against one fixed seed schedule rather than cryptographic DFR estimates, and 2 failures is far too few to estimate a rate from. What the comparison shows is direction, not magnitude. Widening the ring from 83 to 97 while holding all four weights and $r$ fixed spreads the same noise budget over more positions, so each 17-bit block collects fewer errors on average.

Real HQC-1 targets DFR $< 2^{-128}$ at $n = 17{,}669$. The toys exist to show that the structural mechanism, repetition decoding on top of a quasi-cyclic syndrome, works at all.

97 is a prime, but not the kind HQC uses

The chapter’s ring section requires $n$ to be a primitive prime, so that $x^n - 1$ has only two irreducible factors over $\text{GF}(2)$. 2 has order 48 modulo 97 rather than 96, so $x^{97} - 1$ factors into three irreducibles and 97 fails that test; 83 passes it. Nothing in this exercise depends on the difference, because the arithmetic only needs $n$ odd, and the exercise is about the noise budget rather than the ring. It is worth noticing anyway: real HQC would not choose 97. The primitive primes just above 83 are 101, 107, 131 and 139.

Exercise 2

Worst case: $2 \cdot 75 \cdot 66 + 75 = 9{,}975$ errors in $n = 17{,}669$ positions. Spread uniformly, that is an error density, not a per-block count:

$$\frac{9{,}975}{17{,}669} \approx 0.565$$

so a length-$r$ block collects about $0.565\,r$ errors whatever $r$ is: roughly 10 in a 17-bit block, 78 in a 138-bit block, 322 in a 570-bit block. Exercise 4 uses that scaling. Note that real HQC-1 decodes a concatenated Reed-Solomon and duplicated Reed-Muller code rather than repetition blocks, so this is a thought experiment about the noise, not a description of the decoder.

This calculation overestimates the actual failure rate of real HQC for three reasons.

First, $\text{GF}(2)$ products cancel. The bound $w_r w$ on the weight of $r_2 \cdot x$ assumes all $w_r w$ cross-terms land on distinct exponents. Whenever two land on the same one they XOR to zero, and at these weights that happens constantly. The specification’s own simulation of the error vector $x \cdot r_2 - r_1 \cdot y + e$ at HQC-1 parameters concentrates its weight between roughly 5,800 and 6,200 (Gaborit et al., 2025, sec. 6.1.1), against the worst case of 9,975. The realistic density is nearer $0.34$ than $0.565$, and that gap is what makes the scheme possible at all.

Second, the per-block error count concentrates. It is a sum of $r$ nearly independent indicator variables, so it clusters around its mean, and the probability of exceeding a capacity set above that mean falls exponentially in the gap. A bound on the mean says nothing about the tail. The tail is the DFR, and it is where all the design margin lives.

Third, HQC does not decode pure repetition blocks. Its concatenated decoder corrects far more errors at the same rate than majority vote does, so a repetition-block figure is a loose upper bound rather than the real failure model. The published $2^{-128}$ target comes from analysis of that concatenated decoder (Gaborit et al., 2025, sec. 6.1), not from the worst-case noise bound.

Exercise 3

Published sizes (bytes) at NIST levels 1, 3, 5:

Level	McEliece pk + ct	HQC pk + ct	ML-KEM pk + ct
1	261120 + 96 = 261216	2241 + 4433 = 6674	800 + 768 = 1568
3	524160 + 156 = 524316	4514 + 8978 = 13492	1184 + 1088 = 2272
5	1357824 + 208 = 1358032	7237 + 14421 = 21658	1568 + 1568 = 3136

At every level, ML-KEM has the smallest pk + ct, then HQC, then McEliece by a large margin. HQC never beats ML-KEM in this comparison. The McEliece-to-HQC key-compression ratio is largest at Level 5: $1{,}357{,}824 / 7{,}237 \approx 188\times$, since McEliece scales as $k(n-k)$ while HQC scales linearly in $n$.

mceliece = [(261120, 96), (524160, 156), (1357824, 208)]
hqc = [(2241, 4433), (4514, 8978), (7237, 14421)]
mlkem = [(800, 768), (1184, 1088), (1568, 1568)]
for lvl, m, h, k in zip([1, 3, 5], mceliece, hqc, mlkem):
    print(lvl, sum(m), sum(h), sum(k), round(m[0] / h[0], 1))
# ==> 1 261216 6674 1568 116.5
# ==> 3 524316 13492 2272 116.1
# ==> 5 1358032 21658 3136 187.6

Exercise 4

For $r = 3, 5, 7, 11, 17$:

$r$	correction $\lfloor(r-1)/2\rfloor$	rate $1/r$
3	1	0.333
5	2	0.200
7	3	0.143
11	5	0.091
17	8	0.059

Now push $r$ up against HQC-1’s noise. Exercise 2 turned the worst-case bound into a density of about $0.565$, and a length-$r$ block collects $0.565\,r$ errors against a capacity of $\lfloor (r-1)/2 \rfloor \approx 0.5\,r$. Both scale with $r$, and the errors scale faster. Raising the repetition factor buys nothing: at the worst-case bound, majority vote fails in the average block at every $r$, and the failure probability climbs from 0.71 at $r = 17$ toward 1 as $r$ grows. Repetition needs an error density below one half, and the worst-case bound is above it.

The realistic density is what saves the scheme. Taking $p \approx 0.34$ from the specification’s simulated error weight, majority vote does work, but it converges slowly:

from math import comb, log2

def block_failure_log2(r, num, den):
    """log2 P(more than floor((r-1)/2) errors in an r-bit block), p = num/den."""
    cap = (r - 1) // 2
    q = den - num
    total = sum(comb(r, i) * num**i * q ** (r - i) for i in range(cap + 1, r + 1))
    if total == 0:
        return float("-inf")
    scale = den**r
    a, b = total.bit_length(), scale.bit_length()
    shift_a, shift_b = max(0, a - 60), max(0, b - 60)
    return log2((total >> shift_a) / (scale >> shift_b)) + shift_a - shift_b

for r in (17, 138, 801, 1667):
    print(f"r = {r:5d}  log2 P(block fails) = {block_failure_log2(r, 34, 100):7.1f}")
# ==> r =    17  log2 P(block fails) =    -3.6
# ==> r =   138  log2 P(block fails) =   -13.7
# ==> r =   801  log2 P(block fails) =   -67.0
# ==> r =  1667  log2 P(block fails) =  -135.0

A 128-bit message needs 128 blocks, so a union bound wants each block below $2^{-135}$ to reach an overall $2^{-128}$. That lands at $r = 1{,}667$: a codeword of $128 \cdot 1{,}667 = 213{,}376$ bits, twelve times the 17,669-bit ring HQC actually works in. HQC’s concatenated code carries the same 128 bits in $n_1 n_2 = 46 \cdot 384 = 17{,}664$ bits, a rate of $1/138$, and hits the same target. That factor of twelve is what the concatenation buys.

It gets there by dividing the labor. The outer code is a shortened Reed-Solomon code over $\text{GF}(2^8)$; the inner code is the duplicated first-order Reed-Muller code $\text{RM}(1, 7) = [128, 8, 64]$, with each bit repeated 3 times at level 1 and 5 times at levels 3 and 5. Each duplicated Reed-Muller block is maximum-likelihood decoded to one symbol, and the Reed-Solomon layer then corrects the symbols the inner decoder got wrong. The inner code drives the per-symbol error rate down at a modest rate cost; the outer code mops up the rare symbols that survive. Pure repetition has no second layer to fall back on, which is why its only lever is $r$ and why that lever runs out.

References

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