Chapter 19: Coding theory for cryptographers
A code adds redundancy to a message so that small errors can be detected and corrected. Hamming’s 1950 paper starts from why detection alone was not enough. Bell Labs’ Model 5 relay computers checked themselves, but they ran unattended over nights and weekends, so “the errors meant that frequently the computations came to a halt” (Hamming, 1950). The idea of adding redundancy 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 generic algorithms, which decode as if the code were a random linear code, take time exponential in the number of errors (Prange, 1962), though an adversary may also attack the hidden structure itself. 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 McEliece’s cryptosystem.
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. Chapter 20’s status notes report the structural analyses of 2026, which call for a fresh assessment of the submitted Classic McEliece parameters.
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. Quasi-cyclic codes are the exception: in this chapter’s quasi-cyclic section and in Chapter 21, is the length of one circulant block, and the codes have length or . An code encodes -bit messages into -bit codewords with minimum distance . This notation follows MacWilliams and Sloane (Sections 2 and 3 of Chapter 1 in 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 (Section 5 of Chapter 1 in 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 (Section 2 of Chapter 1 in 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 (Section 2 of Chapter 1 in 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 (Sections 1 and 2 of Chapter 1 in 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 (Theorem 1 of Chapter 1 in 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: (Theorems 6 and 8 of Chapter 1 in 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 (Section 3 of Chapter 12 in 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, and generic syndrome decoding, which is exponential, gives the attack baseline. An adversary may also exploit the hidden Goppa structure. 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 recover the low-weight error from the public decoding instance. It may use generic decoding or exploit the hidden Goppa structure. Chapter 20 discusses both and 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-neighbor 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. For a Goppa code with and , that makes their attack about times cheaper than the best attack then known (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-neighbor 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). Maximizing the exponent of Prange’s cost formula over rates at half the Gilbert-Varshamov distance gives , the table’s . The quoted is the same maximum rounded up, as the BJMM paper rounds its worst-case coefficients (Becker et al., 2012, sec. 1).
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 at half distance, 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., 2026, 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 analyzes 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 analyzes (Gaborit et al., 2026, sec. 6.3). The parameter sets target the submissions’ claimed NIST categories under their stated attack-cost models (Albrecht et al., 2022, sec. 3.5 of the guide for security reviewers; Gaborit et al., 2026, sec. 6.3). Generic quantum-ISD estimates address one attack family; they do not settle the overall assessment.
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 October 2026 specification (Table 9 in Gaborit et al., 2026). The August 2025 specification renamed the parameter sets (Gaborit et al., 2025): 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). HQC’s origin is the 2016 paper that introduced the scheme and its decisional assumption (Definition 13 and Theorem 1 in Aguilar et al., 2016). The bracketed date is for the search problem: a 2007 identification scheme already relied on decoding random double-circulant codes, which are quasi-cyclic (§IV-B in Gaborit & Girault, 2007). The variants the current specification’s proof uses came later, adding a parity condition against a distinguisher that Chapter 21 describes (p. 4 in Gaborit et al., 2026).
| 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 | 2016 (search form: by 2007) |
| 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 fixes each circulant block by its first row, so HQC’s key takes kilobytes where an explicit parity-check matrix of its code would take megabytes, 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 with a 2,241-byte key, against mceliece348864’s 261,120 bytes. The code-based family is undominated because of mceliece348864, not HQC-1, which is dominated. 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: no practical attack has broken it at suitable parameters since 1978. Even so, the structural analyses of 2026, which Chapter 20’s status notes report, call for a fresh assessment of the submitted parameters. 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 parameterized 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: