Appendix D: Solutions for Chapter 20

This page collects solutions and editorial notes for the exercises in Chapter 20: McEliece: the original PQC. 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 mceliece package under solutions/ch20-mceliece. From a clone of the companion repository, pytest tests/ch20 runs its suite. Appendix C has the setup.

Exercise 1

The exercise is a roundtrip sanity check. With $t = 1$ the encrypter adds a single error, and the chapter’s warm-up recovers it by syndrome lookup rather than by Patterson. The table has only $n + 1 = 8$ entries at these parameters, and every nonzero syndrome equals exactly one column of $H$. The underlying $[7, 4]$ code has minimum distance $\ge 3$ and corrects 1 error, so every weight-1 error is correctable and every roundtrip succeeds. The expected output is 16/16 successful roundtrips with no decryption failures. If a roundtrip fails, the cause is almost always a bug in the GF(8) arithmetic or the key randomization, not a structural decoding problem.

Running it over all 16 messages and all 7 error positions, rather than one error position per message, is the stronger check and costs nothing:

G = [[0,1,1,1,0,0,0],[1,1,0,0,1,0,0],[1,1,1,0,0,1,0],[1,0,1,0,0,0,1]]
S = [[1,0,0,0],[1,1,0,0],[0,1,1,0],[0,0,1,1]]
S_inv = [[1,0,0,0],[1,1,0,0],[1,1,1,0],[1,1,1,1]]
H = [[0,1,1,0,1,0,1],[1,0,0,0,1,1,1],[1,1,0,1,0,0,1]]
perm = [2, 0, 4, 1, 6, 3, 5]

perm_inv = [0] * 7
for i, j in enumerate(perm):
    perm_inv[j] = i

# G_pub = S * G * P.
SG = [[sum(S[r][i] * G[i][c] for i in range(4)) % 2 for c in range(7)] for r in range(4)]
G_pub = [[SG[r][perm_inv[c]] for c in range(7)] for r in range(4)]

ok = 0
for code in range(16):
    msg = [(code >> b) & 1 for b in range(4)]
    for pos in range(7):
        c = [0] * 7
        for i, mi in enumerate(msg):
            if mi:
                c = [x ^ y for x, y in zip(c, G_pub[i])]
        ct = list(c)
        ct[pos] ^= 1
        unperm = [0] * 7
        for i in range(7):
            unperm[perm_inv[i]] = ct[i]
        s = [sum(a * x for a, x in zip(row, unperm)) % 2 for row in H]
        for j in range(7):
            if [H[r][j] for r in range(3)] == s:
                unperm[j] ^= 1
                break
        scrambled = unperm[3:]
        rec = [sum(scrambled[i] * S_inv[i][j] for i in range(4)) % 2 for j in range(4)]
        ok += (rec == msg)

print(f"{ok} of {16 * 7} roundtrips recovered the message")
# ==> 112 of 112 roundtrips recovered the message

Exercise 2

Expected Prange iterations: $E_{\text{prange}} = \binom{16}{8} / \binom{14}{8} = 12870 / 3003 \approx 4.29$ (equivalently $\binom{n}{w} / \binom{n-k}{w}$, the form the chapter’s prange_exponent uses), far below the $\binom{16}{2} = 120$ vectors a brute-force search enumerates. On iteration count alone Prange essentially always wins: $\binom{n}{w} / \binom{n-k}{w} \le \binom{n}{w}$, so the expected iteration count never exceeds the brute-force count.

That comparison is misleading because the two units of work differ. One brute-force trial is a single weight-$w$ syndrome check, $O(n)$ bit operations. One Prange iteration is a Gaussian elimination on an $(n-k) \times n$ matrix to test one information set, on the order of $(n-k)^2 n$ bit operations (here $8^2 \cdot 16 \approx 10^3$ against the $O(16)$ of a brute-force check). The honest comparison multiplies the iteration count by the per-iteration cost. ISD’s real advantage is asymptotic, the iteration-count term shrinking exponentially faster than the per-iteration polynomial grows, not “fewer iterations” on a 16-bit toy. At the mceliece348864 regime ($n = 3{,}488$, $k = 2{,}720$, $w = 64$) the iteration term is the $2^{142.8}$ the chapter computes, with the Gaussian-elimination cost a polynomial factor on top.

import math
print(round(math.comb(16, 8) / math.comb(14, 8), 2))
print(math.comb(16, 2))
# ==> 4.29
# ==> 120

Exercise 3

Systematic-form key: $k \cdot (n - k)$ bits. For mceliece348864: $2720 \cdot 768 = 2{,}088{,}960$ bits $= 261{,}120$ bytes (255 KiB). Raw ciphertext: $n = 3488$ bits $= 436$ bytes. Ratio: $261120 / 436 \approx 599$.

Key size dominates because public keys are transmitted once per protocol session (TLS, IKEv2), and 255 KiB does not merely strain that transport. It exceeds what a single TLS extension can carry: an extension’s extension_data is length-prefixed with two bytes, capping it at 65,535. A raw McEliece ciphertext is ~436 bytes, and Classic McEliece’s Niederreiter syndrome is 96, either of which fits any modern protocol with room to spare. The bottleneck is the one-time key transport, not per-message bandwidth.

n, k = 3488, 2720
pk = k * (n - k) // 8
ct = n // 8
print(pk, ct, round(pk / ct, 1))
# ==> 261120 436 598.9

Exercise 4

For the toy parameters $(n, k, t) = (16, 8, 2)$, the parity-check matrix has $n - k = 8$ rows. There are $\binom{16}{2} = 120$ distinct weight-2 error vectors and $2^8 = 256$ syndromes, so counting alone leaves injectivity possible without establishing it. The minimum distance establishes it. Two distinct weight-2 vectors differ by a nonzero vector of weight at most 4, the code has $d \ge 2t + 1 = 5$, so that difference is not a codeword and the two syndromes cannot coincide. The same argument covers weight $\le 2$ in general, which is what makes the syndrome a faithful ciphertext for a weight-2 message.

Enumerate to confirm it:

import sys, pathlib, random, itertools
sys.path.insert(0, str(pathlib.Path("solutions/ch20-mceliece/src")))
from mceliece.gf2m import poly_eval
from mceliece.goppa import goppa_parity_check, find_irreducible_goppa_poly, full_support
from mceliece.gf2 import random_invertible_matrix, random_permutation_matrix, mat_mul

m, irred, t, n = 4, 0b10011, 2, 16
rng = random.Random(42)
g = find_irreducible_goppa_poly(m, irred, t, rng)
support = [a for a in full_support(m) if poly_eval(g, a, m, irred) != 0]
H = goppa_parity_check(m, irred, g, support)

# H_pub = M * H * P, the Niederreiter public key.
M = random_invertible_matrix(len(H), rng)
P, _perm = random_permutation_matrix(n, rng)
H_pub = mat_mul(mat_mul(M, H), P)

seen = {}
for combo in itertools.chain.from_iterable(
        itertools.combinations(range(n), w) for w in range(t + 1)):
    e = [0] * n
    for c in combo:
        e[c] = 1
    s = tuple(sum(H_pub[r][c] * e[c] for c in range(n)) % 2 for r in range(len(H_pub)))
    seen.setdefault(s, []).append(combo)

weight2 = sum(1 for v in seen.values() for c in v if len(c) == 2)
print(f"weight-2 patterns: {weight2}")
print(f"patterns of weight <= {t}: {sum(len(v) for v in seen.values())}")
print(f"distinct syndromes: {len(seen)}")
print(f"injective: {all(len(v) == 1 for v in seen.values())}")
# ==> weight-2 patterns: 120
# ==> patterns of weight <= 2: 137
# ==> distinct syndromes: 137
# ==> injective: True

Niederreiter security is identical to McEliece’s: the disguising matrix $M$ and permutation $P$ hide the algebraic structure of the underlying Goppa code, and recovering $e$ from $s$ without the secret key is syndrome decoding for the public matrix $H_{\text{pub}}$. An attacker can decode generically, as if the code were random, or exploit the hidden Goppa structure, and the chapter’s cryptanalysis section takes up both routes. The advantage of Niederreiter is smaller ciphertexts: the message is a weight-$t$ error vector of length $n$, carrying $\log_2 \binom{n}{t}$ bits, far less than the $n$-bit codewords McEliece transmits. This is why the NIST submission, Classic McEliece, uses the Niederreiter syndrome form (with a CCA-secure KEM transform: ciphertext verification and implicit rejection), giving the 96-byte mceliece348864 ciphertext. The original generator-matrix McEliece form is the one this chapter’s toy implements.