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 reduces to syndrome decoding of a random-looking binary code. 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.