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}$. In the submission’s table for mceliece348864, Stern’s algorithm costs 22.0 bits less than Prange and Becker-Joux-May-Meurer’s 31.5 bits less when memory access is free, and 15.5 and 16.1 bits less when memory access is charged at square-root cost (Albrecht et al., 2022, sec. 3.5 of the guide for security reviewers).

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. The quasi-cyclic structure brings HQC’s public key into the same order of magnitude as those of lattice-based KEMs.

That compactness is part of NIST’s case for HQC in March 2025, not the whole of it. NIST selected HQC for standardization as “a good complement to ML-KEM, since it is based on a different underlying security problem and still retains reasonable performance characteristics for general applications”. It preferred HQC to BIKE, the other quasi-cyclic candidate, for “HQC’s stable DFR analysis”, the analysis of HQC’s decryption failure rate (National Institute of Standards and Technology, 2025, p. 11). It did not find the case for standardizing Classic McEliece compelling, “due to skepticism that it will see widespread use”. NIST found that Classic McEliece’s large public keys make it “an unattractive choice for most common applications”, though it offers “an excellent performance profile for applications that are sensitive to ciphertext size, where public keys are rarely transmitted” (National Institute of Standards and Technology, 2025, p. 16).

HQC is a different construction, not a compressed McEliece. Its code hides no trapdoor, and the only coding-theory assumptions its security proof needs are decisional quasi-cyclic syndrome decoding problems (National Institute of Standards and Technology, 2025, p. 10), which Chapter 21 states. Classic McEliece hides a Goppa trapdoor, and its security rests on the one-wayness of decoding for its own Goppa-derived public keys (Albrecht et al., 2022, sec. 3 of the guide for security reviewers), whose resistance to structural attacks is assessed separately (Chapter 20). The size comparison does not rank those assumptions by confidence.

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.

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

National Institute of Standards and Technology. (2025). 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