Appendix D: Solutions for Chapter 19

This page collects solutions and editorial notes for the exercises in Chapter 19: Coding theory for cryptographers. Compute and derivation exercises have worked solutions; open-ended exercises have an editorial note describing what a strong answer addresses.

Exercise 1

The relationship $G H^T = 0$ encodes that every row of $G$ lies in the kernel of $H$, so every codeword $c = m G$ has syndrome $H c^T = H (m G)^T = H G^T m^T = (G H^T)^T m^T = 0$. The matrix product is bookkeeping; the structural reason is just kernel containment.

Exercise 2

The syndrome of a weight-2 error is the XOR of the parity-check columns at the two flipped positions, because $H (c + e)^T = H e^T$ and $e$ selects those two columns. With the systematic $H = [A \mid I_3]$ that the chapter prints, column 2 is $(0,1,1)$ and column 5 is $(0,1,0)$, so the syndrome is $(0,0,1)$, which the table maps to position 6.

G = [[1, 0, 0, 0, 1, 1, 0], [0, 1, 0, 0, 1, 0, 1],
     [0, 0, 1, 0, 0, 1, 1], [0, 0, 0, 1, 1, 1, 1]]
H = [[1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 1, 0, 1, 0], [0, 1, 1, 1, 0, 0, 1]]

def encode(message):
    codeword = [0] * 7
    for i, bit in enumerate(message):
        if bit:
            codeword = [(c ^ g) for c, g in zip(codeword, G[i])]
    return codeword

def syndrome(word):
    return [sum(a * x for a, x in zip(row, word)) % 2 for row in H]

table = {tuple(H[r][j] for r in range(3)): j for j in range(7)}

sent = encode([1, 1, 0, 0])
received = list(sent)
received[2] ^= 1
received[5] ^= 1
s = syndrome(received)

corrected = list(received)
corrected[table[tuple(s)]] ^= 1
print("sent:     ", sent)
print("received: ", received)
print("syndrome: ", s, "-> position", table[tuple(s)])
print("corrected:", corrected, "valid codeword:", syndrome(corrected) == [0, 0, 0])
print("decoded message:", corrected[:4])
# ==> sent:      [1, 1, 0, 0, 0, 1, 1]
# ==> received:  [1, 1, 1, 0, 0, 0, 1]
# ==> syndrome:  [0, 0, 1] -> position 6
# ==> corrected: [1, 1, 1, 0, 0, 0, 0] valid codeword: True
# ==> decoded message: [1, 1, 1, 0]

The decoder flips bit 6 and returns a word that differs from the transmitted codeword in positions 2, 5 and 6. That result is itself a valid codeword, the encoding of $(1,1,1,0)$, so the syndrome check passes and the decoder reports success while returning the wrong message. Three positions is exactly the minimum distance $d = 3$: any weight-2 error either lands inside another codeword’s correction ball or, as here, is carried into one by the correction. The $[7,4,3]$ code corrects only $t = \lfloor (d-1)/2 \rfloor = 1$ error, and beyond that it mis-corrects silently rather than reporting failure. Detection alone is not what is missing here. A code of distance 3 already detects every weight-2 error, because no nonzero word of weight 2 is a codeword, so a receiver that only checks the syndrome and asks for a retransmission would catch this one. What the $[7,4,3]$ code cannot do is detect a double error while correcting single errors automatically: its weight-2 syndromes are exactly the weight-1 syndromes, so a decoder in correcting mode has no way to tell the two apart. Doing both at once is single-error correction with double-error detection, and it needs $d \geq 4$, which is what the extended $[8,4,4]$ Hamming code buys with its extra overall parity bit.

Exercise 3

import math
def prange_log2(n, k, w):
    return math.log2(math.comb(n, k) / math.comb(n - w, k))


print(round(prange_log2(7, 4, 1), 2))
print(round(prange_log2(3488, 2720, 64), 1))
# ==> 1.22
# ==> 142.8

(a) is $2^{1.22} \approx 2.3$ iterations and (b) is approximately $2^{143}$. Both are expected iteration counts, before any work is priced per iteration, so the mceliece348864 figure is the classical Prange iteration exponent at that parameter set rather than a security-strength figure. Chapter 20 prices the iterations and reaches the submission’s own full-Prange estimate of $2^{173.4}$. Tightened ISD variants (Stern, Becker-Joux-May-Meurer) reduce this by 10-30 bits depending on the parameter set.

Exercise 4

HQC-1 (called HQC-128 before the August 2025 specification) has circulant block size $n = 17{,}669$. The comparison worked here is against the single $n \times n$ non-identity circulant block, the one the chapter’s aside calls the honest dense comparison: a dense matrix of that shape costs $n^2$ bits, or $\lceil n^2/8 \rceil$ bytes, while the quasi-cyclic representation stores one row of it, $\lceil n/8 \rceil$ bytes. Comparing instead against the full $n \times 2n$ parity-check matrix of the $[2n, n]$ code, as the chapter body’s block does, doubles the dense side and therefore doubles the savings factor to roughly $2n$.

n = 17669
# Ceil division: a length-n row needs ceil(n/8) bytes (matches the chapter body).
random_bytes = -(-(n * n) // 8)
qc_bytes = -(-n // 8)
print(round(random_bytes / 1024 / 1024, 1), "MB random")
print(round(qc_bytes / 1024, 2), "KB QC")
print(random_bytes // qc_bytes, "x savings")
# ==> 37.2 MB random
# ==> 2.16 KB QC
# ==> 17666 x savings

The savings factor is approximately $n$, the order of the circulant. It differs slightly because rounding both the $n \times n$ matrix and the length-$n$ row up to whole bytes perturbs the ratio. This is the bandwidth reason HQC was selected in NIST’s Round 4 KEM selection (March 2025) for future standardization alongside ML-KEM, despite Classic McEliece’s longer unbroken track record. The QC structure brings public-key sizes back into the same order of magnitude as lattice-based KEMs, at the cost of relying on the average-case QC-syndrome-decoding assumption rather than the well-studied general SDP.

The fuller versions of these routines are in the coding_theory package under solutions/ch19-coding-theory. It carries the GF(2) linear algebra, the Hamming encode-syndrome-decode cycle, the GF(8) Goppa parity-check construction, and Prange ISD alongside its closed-form cost estimator, each as a function rather than as a script. From a clone of the companion repository, pytest tests/ch19 runs its suite. Appendix C has the setup.