Chapter 19: Coding theory for cryptographers
A code adds redundancy to a message so that small errors can be detected and corrected. Hamming invented his code in 1950 because the Bell Labs card reader kept rejecting his programs over single-bit errors (Hamming, 1950). The idea is old and well understood. Given a message of bits, produce a codeword of bits. Design the redundancy so that a receiver can recover the original message even when a few bits flip in transit.
The cryptographic twist is this: what if the code’s structure is a secret? If you know the structure, decoding is efficient. If you do not, the best known algorithms for decoding a random linear code take exponential time in the code length (Prange, 1962). The worst-case decision problem is NP-complete (Berlekamp et al., 1978). Those are two different statements, and the section on syndrome decoding below keeps them apart. That gap between “easy with the key” and “hard without it” is the security assumption behind the code-based systems in Part IV. McEliece proposed the first code-based public-key cryptosystem in 1978 (McEliece, 1978), the same year as RSA. The binary-Goppa-code line has resisted practical cryptanalysis at suitable parameters ever since, though many structured and reduced-parameter variants have fallen.
Notation. Throughout the coding chapters of Part IV, Chapters 19 to 21, denotes the code length (the number of bits in a codeword), denotes the dimension (the number of message bits), and denotes the minimum Hamming distance. An code encodes -bit messages into -bit codewords with minimum distance . This notation is standard in coding theory (MacWilliams & Sloane, 1977). It does not conflict with Part III’s use of for hash output length, which addressed a different cryptographic family, and Chapter 24 resets once more for the multivariate systems, where it counts variables rather than codeword bits.
The [7,4,3] Hamming code
Section titled “The [7,4,3] Hamming code”The smallest interesting example is the Hamming code. It takes a 4-bit message, appends 3 parity bits, and produces a 7-bit codeword. The redundancy lets a receiver correct any single-bit error.
Start with the parity-check matrix , a binary matrix in systematic form . The seven columns of are the seven nonzero vectors of . Every possible nonzero syndrome points to a unique column:
The generator matrix is a matrix in systematic form , where is the left block of :
The defining relationship is over . This says that every row of (and therefore every codeword, since codewords are linear combinations of rows of ) is in the null space of .
Encode the message by computing :
# Generator matrix G for the [7,4,3] Hamming code (systematic form).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],]
def gf2_encode(message, G): n = len(G[0]) codeword = [0] * n for i, bit in enumerate(message): if bit: codeword = [(c ^ g) for c, g in zip(codeword, G[i])] return codeword
m = [1, 0, 1, 1]c = gf2_encode(m, G)print("codeword:", c)# ==> codeword: [1, 0, 1, 1, 0, 1, 0]Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch19/, one file per block. Appendix C covers the clone and the environment they run on.
The first four bits of the codeword are the message itself (because is in systematic form), and the last three bits are the parity checks.
Now introduce a single-bit error at position 2 (0-indexed). The received word is where has a single 1 at position 2. Compute the syndrome :
H = [ [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 1, 0, 1, 0], [0, 1, 1, 1, 0, 0, 1],]
def gf2_mat_vec(A, v): return [sum(a * x for a, x in zip(row, v)) % 2 for row in A]
c = [1, 0, 1, 1, 0, 1, 0]r = list(c)r[2] ^= 1 # flip bit 2
s = gf2_mat_vec(H, r)print("received:", r)print("syndrome:", s)# ==> received: [1, 0, 0, 1, 0, 1, 0]# ==> syndrome: [0, 1, 1]The syndrome is column 2 of . That is not a coincidence. Since for any valid codeword, the syndrome depends only on the error pattern, not on which codeword was sent. When has a single 1 at position , the syndrome equals column of . The receiver looks up the syndrome in a table, flips the indicated bit, and recovers the original codeword.
This works because the seven columns of are all distinct. Each single-bit error produces a unique syndrome, and the zero vector (the all-zero syndrome) corresponds to no error. The code has possible syndromes, accounting for 7 single-bit error patterns plus the no-error case. The codewords and their 8-element radius-1 correction balls partition perfectly: . (Each ball holds the codeword itself plus its 7 single-bit neighbors: .) A code that achieves this exact packing with no wasted syndromes is called a perfect code (MacWilliams & Sloane, 1977). (A sphere-packing picture of would require seven dimensions; the arithmetic carries the intuition instead.)
Linear codes over GF(2)
Section titled “Linear codes over GF(2)”Linear code. A binary linear code of length and dimension is a -dimensional subspace of . It contains codewords. Being a subspace means that the sum of any two codewords is a codeword, and the zero vector is always a codeword (MacWilliams & Sloane, 1977).
Generator matrix. A matrix whose rows form a basis for . Every codeword is a unique linear combination of the rows: for some . A generator matrix in systematic form embeds the message in the first positions and appends parity bits (MacWilliams & Sloane, 1977).
Parity-check matrix. An matrix with the property . In systematic form , where . Since , the product is over , because in characteristic 2. The relationship is the defining constraint: every row of satisfies all parity checks (MacWilliams & Sloane, 1977).
Syndrome. For a received word (where is the transmitted codeword and is the error pattern), the syndrome is . The syndrome depends only on the error, not on which codeword was sent. Two received words with the same syndrome differ by a codeword.
Minimum distance. The minimum distance of a linear code is , where is the Hamming weight (number of nonzero coordinates). For a linear code, the minimum distance equals the minimum weight of a nonzero codeword, because and is itself a codeword (MacWilliams & Sloane, 1977).
Error-correcting capability. An code can correct up to errors. The decoder finds the codeword nearest to the received word. If at most bits were flipped, the nearest codeword is the one that was sent.
Hamming bound. The number of syndromes is , and each must account for a distinct error pattern of weight at most . The number of such patterns is . For the code to correct all weight- errors, the syndromes must be sufficient:
Equality defines a perfect code. The Hamming code is perfect: (MacWilliams & Sloane, 1977).
Syndrome decoding problem (SDP). Chapter 3 introduced this problem in its bounded-weight form and cited the NP-completeness result. Here it is stated precisely. The decision version: given an binary matrix , a target syndrome , and a weight bound , decide whether some has and . Berlekamp, McEliece, and van Tilborg proved this decision problem NP-complete in 1978 (Berlekamp et al., 1978). The associated search problem, finding such an when it exists, is NP-hard. Code-based cryptography rests on the stronger practical assumption that random-looking instances at the chosen parameters are hard on average. No polynomial-time algorithm is known for decoding a random code when the error weight is close to .
Building codes in Python
Section titled “Building codes in Python”The [7,4,3] Hamming code
Section titled “The [7,4,3] Hamming code”The generator and parity-check matrices for the Hamming code, with the check that confirms the two describe the same code. The syndrome table below is the decoder’s half, and the full encode, corrupt and decode cycle runs in the coding_theory package of solutions/ch19-coding-theory:
# GF(2) matrix product A * B^T where B_rows holds the rows of B.# Each row of B is a column of B^T, so the (i,j) entry of the product# is the dot product of A's row i with B's row j, reduced mod 2.def gf2_mul_by_transpose(A, B_rows): return [[sum(a * b for a, b in zip(row_a, row_b)) % 2 for row_b in B_rows] for row_a in A]
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],]
# Verify the defining relationship: G * H^T = 0.# Pass H directly: each row of H is a column of H^T.product = gf2_mul_by_transpose(G, H)print("G * H^T =", product)# ==> G * H^T = [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]Syndrome table decoding
Section titled “Syndrome table decoding”Build the full syndrome-to-error lookup table for the Hamming code. The table maps each of the 7 nonzero syndromes to the single-bit error it corrects:
H = [ [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 1, 0, 1, 0], [0, 1, 1, 1, 0, 0, 1],]
# Build syndrome table: syndrome -> error position.table = {}for j in range(7): syn = tuple(H[r][j] for r in range(3)) table[syn] = j
print("syndrome table:")for syn, pos in sorted(table.items()): print(f" {syn} -> position {pos}")# ==> syndrome table:# ==> (0, 0, 1) -> position 6# ==> (0, 1, 0) -> position 5# ==> (0, 1, 1) -> position 2# ==> (1, 0, 0) -> position 4# ==> (1, 0, 1) -> position 1# ==> (1, 1, 0) -> position 0# ==> (1, 1, 1) -> position 3A weight-2 error exceeds the code’s correction capability () and produces a syndrome that maps to the wrong position:
H = [ [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 1, 0, 1, 0], [0, 1, 1, 1, 0, 0, 1],]
def gf2_mat_vec(A, v): return [sum(a * x for a, x in zip(row, v)) % 2 for row in A]
# Encode the zero message, flip bits 0 and 1 (weight-2 error).c = [0, 0, 0, 0, 0, 0, 0]e = [1, 1, 0, 0, 0, 0, 0]r = [(ci ^ ei) for ci, ei in zip(c, e)]s = gf2_mat_vec(H, r)print("syndrome of weight-2 error:", s)# ==> syndrome of weight-2 error: [0, 1, 1]
# Syndrome (0,1,1) maps to position 2, not positions 0 and 1.# The decoder "corrects" to the wrong codeword.print("decoder thinks error is at position 2")# ==> decoder thinks error is at position 2The syndrome is the XOR of columns 0 and 1 of , which happens to equal column 2. The decoder cannot distinguish a weight-2 error at positions 0 and 1 from a weight-1 error at position 2. This is expected: the code corrects at most error.
Prange information-set decoding
Section titled “Prange information-set decoding”Given a parity-check matrix and a syndrome , the syndrome decoding problem asks for a low-weight error vector with . Prange’s algorithm (Prange, 1962) is the simplest attack:
- Pick random column indices as the “information set” .
- Let be the remaining indices.
- Extract the submatrix from the columns in .
- If is invertible over , solve .
- If (the target error weight), output with zeros at positions in and at positions in .
The algorithm succeeds when the randomly chosen information set avoids all error positions. The probability of this per iteration is , so the expected number of iterations is:
For the Hamming code with , this gives iterations. The formula conditions on the sampled set yielding an invertible , which holds with constant probability over . That constant shifts exact small-case counts but not the asymptotic exponent. For real parameters, the cost is exponential:
import math
def prange_exponent(n, k, w): """Log2 of expected Prange iterations: C(n,k) / C(n-w,k).""" log_cost = ( sum(math.log2(n - i) for i in range(k)) - sum(math.log2(n - w - i) for i in range(k)) ) return log_cost
# Hamming [7,4,3] with w=1.exp_hamming = prange_exponent(7, 4, 1)print(f"[7,4,3] w=1: 2^{exp_hamming:.1f} iterations")# ==> [7,4,3] w=1: 2^1.2 iterations
# Classic McEliece mceliece348864: n=3488, k=2720, w=64.exp_mce = prange_exponent(3488, 2720, 64)print(f"mceliece348864: 2^{exp_mce:.1f} iterations")# ==> mceliece348864: 2^142.8 iterations
# Classic McEliece mceliece6960119: n=6960, k=5413, w=119.exp_mce2 = prange_exponent(6960, 5413, 119)print(f"mceliece6960119: 2^{exp_mce2:.1f} iterations")# ==> mceliece6960119: 2^263.4 iterationsPrange’s iterations for mceliece348864 is the baseline. The information-set decoding section below surveys the improvements.
Goppa codes
Section titled “Goppa codes”A binary Goppa code is a family of codes with a hidden algebraic structure that makes efficient decoding possible for someone who knows the structure, while the parity-check matrix looks random to an outsider. This is the trapdoor behind McEliece’s 1978 cryptosystem (McEliece, 1978).
The construction uses extension fields. Fix and work in . Choose an irreducible polynomial of degree over and a support set of distinct elements of that are not roots of . The binary Goppa code is defined as:
The code has parameters and corrects up to errors (MacWilliams & Sloane, 1977). Patterson’s algorithm decodes in polynomial time given and (Patterson, 1975). Without and the support , the binary parity-check matrix is meant to look like a random binary matrix: the best known attack is then generic syndrome decoding, which is exponential. Security therefore rests on two legs, the average-case hardness of decoding random-looking codes and the absence of an efficient attack that recovers or exploits the hidden Goppa structure. Chapter 20 takes up the structural side for Classic McEliece.
The smallest concrete example uses (so ) and . The field has 8 elements (0 through 7). Take for some root and let be the 7 elements of excluding . With and , the support has elements and the code has parameters . The parity-check matrix is with entries expanded to binary:
def gf8_mul(a, b): """Multiply in GF(2^3) = GF(2)[x]/(x^3 + x + 1).""" p = 0 for _ in range(3): if b & 1: p ^= a b >>= 1 a <<= 1 if a & 0b1000: a ^= 0b1011 # reduce mod x^3 + x + 1 return p
def gf8_inv(a): """Brute-force inverse in GF(8). Crashes on zero input.""" assert a != 0, "zero has no inverse" for x in range(1, 8): if gf8_mul(a, x) == 1: return x
# Goppa code with g(x) = x - 3 over GF(8), support = GF(8) \ {3}.g_root = 3support = [i for i in range(8) if i != g_root]print("support:", support)# ==> support: [0, 1, 2, 4, 5, 6, 7]
# H_j = 1 / (L_j XOR g_root), expanded to 3 binary rows.H_goppa = [[0] * len(support) for _ in range(3)]for j, alpha in enumerate(support): val = gf8_inv(alpha ^ g_root) for bit in range(3): H_goppa[2 - bit][j] = (val >> bit) & 1
print("Goppa parity-check matrix:")for row in H_goppa: print(" ", row)# ==> Goppa parity-check matrix:# ==> [1, 1, 0, 1, 0, 0, 1]# ==> [1, 0, 0, 0, 1, 1, 1]# ==> [0, 1, 1, 0, 1, 0, 1]The binary parity-check matrix has no visible structure that reveals the Goppa polynomial or the support set. This toy instance is far too small to actually hide anything. It only shows the shape of the trapdoor. This is the trapdoor: the code owner knows and can decode efficiently with Patterson’s algorithm (Patterson, 1975); an eavesdropper sees a random-looking binary matrix and must solve SDP. Chapter 20 builds a full McEliece key generation, encryption, and decryption around this structure.
Quasi-cyclic codes
Section titled “Quasi-cyclic codes”A quasi-cyclic (QC) code is a code where a cyclic shift of any codeword by a fixed block length is also a codeword. The parity-check matrix is built from circulant blocks, where each block is fully determined by its first row. Circulant multiplication corresponds to polynomial multiplication modulo over .
HQC uses this structure. The name stands for “Hamming Quasi-Cyclic,” though the scheme’s inner code is not a Hamming code. Chapter 21 covers HQC’s actual construction. A double-circulant quasi-cyclic code is described by a single vector : the parity-check matrix has the form where is the circulant matrix whose rows are cyclic shifts of . HQC’s actual public key is not just ; it is a pair where is a noisy syndrome of secret sparse vectors (Chapter 21). What the quasi-cyclic structure buys is compactness: a circulant block is fixed by one row. Storing takes bits; storing the full parity-check matrix of a random code would take bits:
# Key-size savings from quasi-cyclic structure.# Random [2n, n] code: parity-check matrix has n * 2n bits.# QC code: store one row of the circulant block, n bits.
n_hqc1 = 17_669random_matrix_bits = n_hqc1 * (2 * n_hqc1)qc_bits = n_hqc1savings = random_matrix_bits / qc_bits
# Ceil division: 17,669 bits needs 2,209 bytes, not 2,208.random_matrix_bytes = -(-random_matrix_bits // 8)qc_bytes = -(-qc_bits // 8)
print(f"random matrix: {random_matrix_bits:,} bits = {random_matrix_bytes:,} bytes")print(f"QC representation: {qc_bits:,} bits = {qc_bytes:,} bytes")print(f"savings factor: {savings:,.0f}x")# ==> random matrix: 624,387,122 bits = 78,048,391 bytes# ==> QC representation: 17,669 bits = 2,209 bytes# ==> savings factor: 35,338xThe tradeoff is that quasi-cyclic structure introduces algebraic relations that might help an attacker. HQC’s security rests on the quasi-cyclic syndrome decoding (QCSD) problem, a structured variant of generic SDP rather than generic SDP itself. The structure is what compresses the key, and it is also why QCSD needs separate cryptanalysis: no known algorithm exploits the quasi-cyclic structure to break HQC’s chosen parameters. Chapter 21 states the IND-CPA reduction to the decisional QCSD variants the HQC specification uses (2-DQCSD-P and 3-DQCSD-PT) and builds the scheme’s IND-CPA core at toy parameters on this foundation.
Circulant multiplication is polynomial multiplication in the ring . The vector represents the polynomial . Multiplying two such polynomials and reducing modulo wraps high-degree terms back around, which is exactly what a cyclic shift does:
def poly_mul_mod(a, b, n): """Multiply polynomials a and b in GF(2)[x]/(x^n - 1).""" result = [0] * n for i, ai in enumerate(a): if ai == 0: continue for j, bj in enumerate(b): if bj: result[(i + j) % n] ^= 1 return result
# Small example: n=5, multiply (1 + x) by (1 + x^3) mod x^5 - 1.a = [1, 1, 0, 0, 0]b = [1, 0, 0, 1, 0]c = poly_mul_mod(a, b, 5)print("product mod x^5-1:", c)# ==> product mod x^5-1: [1, 1, 0, 1, 1]Information-set decoding
Section titled “Information-set decoding”Prange’s algorithm from 1962 is the baseline ISD (Prange, 1962). Every subsequent improvement refines the same framework: guess a structure-free subset of the codeword positions, solve the resulting system, and check whether the solution has the right weight.
The ISD exponent timeline below is for half-distance decoding of random binary codes: error weight at half the Gilbert-Varshamov distance, and each exponent the maximum of the algorithm’s rate-dependent cost over all code rates, which is the worst case each paper reports and which falls near rate to for every algorithm in the table. This bounded-distance regime is closer to the setting code-based KEMs use than full-distance decoding is. Each time exponent comes with the memory the algorithm’s lists occupy, which is where the later improvements pay for their speed. Concrete schemes still pick their own rates and weights and size parameters with finite- estimators, not with this asymptotic exponent. Each entry is the asymptotic cost :
| Year | Algorithm | Time exponent | Memory exponent | Reference |
|---|---|---|---|---|
| 1962 | Prange | polynomial | (Prange, 1962) | |
| 1989 | Stern | (Stern, 1989) | ||
| 2011 | MMT | (May et al., 2011) | ||
| 2012 | BJMM | (Becker et al., 2012) | ||
| 2015 | May-Ozerov | exponential, not tabulated | (May & Ozerov, 2015) |
The memory column is the space coefficient BJMM’s comparison table reports for each algorithm optimized for speed (Table 1 in Becker et al., 2012). May-Ozerov’s theorem states a time exponent and no memory coefficient. Its nearest-neighbour search keeps exponential lists, and its authors record a large polynomial overhead as an open problem.
Each improvement applies a refined search strategy within the information set. Lee-Brickell allows a small number of error positions inside the information set, a constant-factor gain over Prange (Lee & Brickell, 1988). Stern splits the information set in half and uses a birthday-style collision search to find partial matches (Stern, 1989). BJMM exploits the “representation technique”: in a target vector has exponentially many representations as a sum of two vectors. These extra representations speed up the collision search (Becker et al., 2012).
BJMM’s is the classical milestone most often cited for random binary codes in this regime. May-Ozerov’s nearest-neighbour search lowered it further to , the figure the Classic McEliece submission itself quotes against Prange’s (Albrecht et al., 2022, sec. 3.4 of the guide for security reviewers). Standards bodies set parameters from detailed finite- cost models, not from a single asymptotic exponent. For comparison, the lattice core-SVP model from Chapter 13 gives a cost of where is the BKZ block size. Both are exponential-time attacks. From Prange’s to May-Ozerov’s the exponent has fallen only modestly over fifty years, slow progress next to lattice algorithms, and the lattice sieving exponent has itself been stable since 2016.
Quantum ISD. Grover’s algorithm provides a quadratic speedup on the brute-force search component of ISD, and both submissions state the consequence in one line. The Classic McEliece guide for security reviewers has known quantum attacks replacing the asymptotic base with its square root (Albrecht et al., 2022, sec. 3.4). The HQC specification obtains its quantum-safe security “by dividing the security bits by two (taking the square root of the complexity)” (Gaborit et al., 2025, sec. 6.3). Both cite the same source, Bernstein’s analysis of Grover applied to information-set decoding (Bernstein, 2010).
Halving applies to whatever exponent the regime supplies, so the regime has to be named. Taking Prange at rate and the full Gilbert-Varshamov distance (, from ), the classical exponent evaluates to , and Grover takes it to . The frequently quoted for this setting is not the rate- value: it is the maximum of the same exponent over all rates, attained near rate . Note also that halving a Prange exponent is not the same as halving the best classical exponent, because the quantum variants of the improved algorithms rebalance their parameters rather than inheriting a clean square root (Albrecht et al., 2022, sec. 3.3 of the guide for security reviewers).
Neither submission actually prices its own parameters in a regime. Classic McEliece analyses error weight , which gives rather than , and says in as many words that the weights used in the coding-theory literature “do not appear in the McEliece system” (Albrecht et al., 2022, sec. 3.4 of the guide for security reviewers). HQC analyses (Gaborit et al., 2025, sec. 6.3). NIST’s security categories for code-based schemes account for the quantum speedup, and the parameters of both schemes are chosen so that even the quantum ISD cost exceeds the target security level.
Code-based vs lattice-based vs hash-based
Section titled “Code-based vs lattice-based vs hash-based”All sizes below use Category 1 parameter sets (128-bit classical security target). HQC sizes follow the August 2025 specification (Table 6 in Gaborit et al., 2025), which also renamed the parameter sets: what earlier rounds called HQC-128 is HQC-1 there, and this book uses the current names. The Classic McEliece ciphertext is the Niederreiter syndrome only, with the 32-byte session key a separate Encap output (Albrecht et al., 2022, sec. 6.2 of the cryptosystem specification).
| Property | ML-KEM-512 | SLH-DSA-128s | mceliece348864 | HQC-1 |
|---|---|---|---|---|
| Hardness assumption | Module-LWE | Hash/XOF properties | Goppa-code SDP (+ structural resistance) | QCSD (decisional variants) |
| Representative origin | 2012 (LWE: 2005) | 1979 | 1978 | 2017 |
| Public key | 800 B | 32 B | 261,120 B | 2,241 B |
| Ciphertext / signature | 768 B | 7,856 B | 96 B | 4,433 B |
| Reduction type | Worst-to-avg (GapSVP to LWE) | EUF-CMA from hash/XOF | No worst-case-to-avg reduction | Decisional QCSD to IND-CPA; KEM via transform |
McEliece’s public keys are large because the systematic-form matrix of a random Goppa code has no exploitable structure for compression. HQC’s quasi-cyclic structure compresses the key from megabytes to kilobytes, at the cost of a structured assumption. SLH-DSA has the smallest keys but the largest signatures.
No assumption family is dominated on size, but individual parameter sets are, and the distinction matters. Read the two size rows as coordinates. mceliece348864 has the largest key (261 KB) but the smallest ciphertext (96 B); SLH-DSA-128s has the smallest key (32 B) but the largest output (7,856 B); ML-KEM-512 sits between them on both axes. No other set in the table beats any of those three on key and output at once. HQC-1 is beaten on both by ML-KEM-512, at 2,241 against 800 bytes of key and 4,433 against 768 of ciphertext. What HQC buys is not size against ML-KEM but a code-based assumption at kilobyte rather than megabyte keys, which is why the code-based family as a whole is not dominated even though this one set is. The figure below plots all four.
Plotting those pairs on logarithmic axes shows the shape of the tradeoff directly. Both axes span orders of magnitude, so a linear plot would collapse three of the four points into the origin.
The binary Goppa McEliece line has the longest track record of any post-quantum candidate: 48 years unbroken at suitable parameters as of 2026. ISD exponent improvements from 1962 to 2015 lowered the constant only modestly (Prange’s to May-Ozerov’s in the bounded-distance regime), slow progress compared to lattice algorithm advances over the same period. The decoding-hardness foundation has held up under sustained cryptanalytic scrutiny across that window, though concrete schemes still depend on parameter choices and resistance to structural attacks.
Chapter 20 builds McEliece from Goppa codes in its original generator-matrix form, then connects it to the Niederreiter-form Classic McEliece KEM. Chapter 21 builds HQC from quasi-cyclic codes.
Exercises
Section titled “Exercises”Exercise 1. Verify by hand. Multiply the generator matrix and the transpose of the parity-check matrix from this chapter over . The product is a matrix. Confirm that every entry is zero. Then explain in one sentence why this relationship guarantees that every codeword has the zero syndrome.
Exercise 2. Decode a weight-2 error. Encode the message using the Hamming code from this chapter. Flip bits at positions 2 and 5 of the codeword. Compute the syndrome. Look up the syndrome in the table and report which position the decoder thinks the error is at. Explain why the decoder corrects to the wrong codeword, given that .
Exercise 3. Estimate Prange ISD cost. Using math.comb and the formula , compute the expected number of Prange iterations for (a) the Hamming code with , and (b) mceliece348864 with , , . Express both results as . Verify that (a) gives approximately iterations and (b) gives approximately .
Exercise 4. Quasi-cyclic key savings. Storing a dense binary matrix costs bits. A circulant block of the same size is fixed by its first row, so it costs bits. For HQC-1 with , compute both storages in bytes, rounding each up to a whole byte, and express the savings factor. The factor is close to but not equal to it. Say why. (This is the comparison against the non-identity block alone, the one the aside above calls the honest dense comparison. Comparing against the full parity-check matrix, as the chapter body’s block does, doubles both the dense side and the factor.)
Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 19. A separate track, for rebuilding rather than reading. The package exercises/ch19-coding-theory hands you the six routines this chapter prints in full. What it stubs is the four the chapter only describes: the general GF(2) matrix product, the zero-syndrome entry that turns a lookup table into a decoder, the parameterised Goppa parity-check construction, and Prange ISD with its cost estimator. Run PQC_IMPL=exercises pytest tests/ch19 to grade your version against the suite that proves the reference one.
References
Section titled “References”Last updated: