PDF Run this chapter's code LaTeX source Comments
Appendix ABinary Goppa Codes
Classic McEliece (Chapter 22) hides its trapdoor inside a binary Goppa code: a family of algebraic codes that come with a fast \(t\)-error decoder yet, after four decades of scrutiny, still cannot be distinguished from random linear codes by any efficient test — a qualifier that has been narrowing since 2023, and that Section A.8 takes up in full. The main text used only two facts about them – that they correct \(t\) errors and that they have an efficient decoder. This appendix supplies the construction behind those facts: how a Goppa code is defined, why the binary case corrects the full \(t\) errors rather than \(t/2\), and how Patterson’s algorithm decodes it [1, 2]. Throughout we assume the finite fields of Chapter 4.
A.1Setup: the field, the support, and the Goppa polynomial#
Fix an extension field \(\mathbb{F}_{2^m}\) of the binary field. A binary Goppa code is built from two ingredients.
A support \(L = (\alpha_1,\dots,\alpha_n)\) of \(n\) distinct elements of \(\mathbb{F}_{2^m}\). Since the field has \(2^m\) elements, \(n \le 2^m\).
A Goppa polynomial \(g(x) \in \mathbb{F}_{2^m}[x]\) of degree \(t\), subject to \(g(\alpha_j) \neq 0\) for every \(j\) – so that each \(x-\alpha_j\) is invertible modulo \(g\). For the Patterson decoder below, assume in addition that \(g\) is monic and irreducible, as in Classic McEliece.
The codewords will be binary vectors of length \(n\); the field \(\mathbb{F}_{2^m}\) is the scaffolding in which the defining constraints live. The number \(t\) is the design parameter: it will be the number of errors the code corrects.
A.2Definition#
Definition A.1 (Binary Goppa code). The binary Goppa code \(\Gamma(L,g)\) is the set of binary vectors whose coordinates, weighted by the poles \(x-\alpha_j\), sum to zero modulo \(g\): \[\Gamma(L,g) \;=\; \Big\{\, c=(c_1,\dots,c_n)\in\mathbb{F}_2^{\,n} \;:\; \sum_{j=1}^{n} \frac{c_j}{x-\alpha_j} \equiv 0 \pmod{g(x)} \,\Big\},\] where each \(\dfrac{1}{x-\alpha_j}\) denotes the inverse of \(x-\alpha_j\) in the ring \(\mathbb{F}_{2^m}[x]/(g)\), which exists because \(g(\alpha_j)\neq 0\).
The syndrome map is linear over \(\mathbb{F}_{2^m}\); restricting its kernel to \(\mathbb{F}_2^n\) gives an \(\mathbb{F}_2\)-linear code. This binary restriction is exactly what makes the binary case special, as Section A.4 shows.
A.3The parity-check matrix#
To turn the congruence into a matrix, expand each pole. Because \(g(\alpha_j)\neq 0\), one has the identity \[\frac{1}{x-\alpha_j} \;\equiv\; -\,g(\alpha_j)^{-1}\,\frac{g(x)-g(\alpha_j)}{x-\alpha_j} \pmod{g(x)},\] in which \(\big(g(x)-g(\alpha_j)\big)/(x-\alpha_j)\) is an honest polynomial of degree \(t-1\). Collecting the coefficients of \(1,x,\dots,x^{t-1}\) in the defining sum and setting each to zero yields a parity-check matrix over \(\mathbb{F}_{2^m}\) of the Vandermonde-times-diagonal form \[H \;=\; \underbrace{\begin{pmatrix} 1 & 1 & \cdots & 1\\ \alpha_1 & \alpha_2 & \cdots & \alpha_n\\ \vdots & & & \vdots\\ \alpha_1^{\,t-1} & \alpha_2^{\,t-1} & \cdots & \alpha_n^{\,t-1} \end{pmatrix}}_{\text{Vandermonde}} \underbrace{\begin{pmatrix} g(\alpha_1)^{-1} & & \\ & \ddots & \\ & & g(\alpha_n)^{-1} \end{pmatrix}}_{\text{diagonal}} \;\in\; \mathbb{F}_{2^m}^{\,t\times n}.\] A vector \(c\) lies in \(\Gamma(L,g)\) exactly when \(H c^{\top}=0\). This is the parity check of an alternant code, of which Goppa codes are the important special case.
To obtain a binary parity-check matrix, replace each entry of \(H\) by the column of \(m\) bits giving its coordinates in a fixed \(\mathbb{F}_2\)-basis of \(\mathbb{F}_{2^m}\). This expands the \(t\times n\) matrix over \(\mathbb{F}_{2^m}\) into an \((mt)\times n\) matrix over \(\mathbb{F}_2\). Its rows may be dependent, so the dimension satisfies \[k \;=\; \dim \Gamma(L,g) \;\ge\; n - m t .\] In Classic McEliece’s regime – \(m\) around \(12\)–\(13\), \(n\) a few thousand, \(t\) around \(60\)–\(130\) – this bound is met with near equality.
A.4Minimum distance: why the binary code corrects \(t\) errors#
A general alternant code with a degree-\(t\) polynomial guarantees only \(d \ge t+1\), hence correction of \(\lfloor t/2\rfloor\) errors. The binary Goppa code does twice as well, provided \(g\) is squarefree.
Proposition A.2 (Doubled distance for binary Goppa codes). If \(g\) is squarefree (equivalently separable: it has no repeated roots in the algebraic closure), then \[\Gamma(L,g) \;=\; \Gamma(L,g^2),\] and consequently its minimum distance obeys \(d \ge 2t+1\). The code therefore corrects up to \(t\) errors.
Proof sketch. For a binary \(c\), let \(\sigma_c(x)=\prod_{j:\,c_j=1}(x-\alpha_j)\) be the locator of its support. A short computation gives \[\sum_{j:\,c_j=1}\frac{1}{x-\alpha_j} \;=\; \frac{\sigma_c'(x)}{\sigma_c(x)},\] where \(\sigma_c'\) is the formal derivative. Since \(\gcd(\sigma_c,g)=1\) (no \(\alpha_j\) is a root of \(g\)), the defining condition \(c\in\Gamma(L,g)\) is equivalent to \(g \mid \sigma_c'\). Now over characteristic \(2\) the derivative kills every even-degree term, so \(\sigma_c'(x)\) contains only even powers of \(x\); because squaring is the Frobenius map on \(\mathbb{F}_{2^m}\), such a polynomial is a perfect square, \(\sigma_c'=B^2\) for some \(B\in\mathbb{F}_{2^m}[x]\). As \(g\) is squarefree, \[g \mid B^2 \iff g \mid B \iff g^2 \mid B^2=\sigma_c',\] so \(g\mid\sigma_c' \Leftrightarrow g^2\mid\sigma_c'\), i.e. \(\Gamma(L,g)=\Gamma(L,g^2)\). The right-hand code is alternant with polynomial of degree \(2t\), giving \(d\ge 2t+1\). ◻
The whole point of using binary codewords is this free doubling: a Goppa polynomial of degree \(t\) buys the error-correction of a designed distance \(2t+1\).
A.5Patterson’s decoding algorithm#
Decoding is the trapdoor. Given a received word \(y=c+e\) with \(c\in\Gamma(L,g)\) and \(\mathrm{wt}(e)\le t\), Patterson’s algorithm [2] recovers \(e\) using \(g\) and \(L\) as the secret. It exploits the same characteristic-\(2\) square structure used in Proposition A.2.
Write \(E=\{\,j: e_j=1\,\}\) for the (unknown) set of error positions and let the error-locator polynomial be \(\sigma(x)=\prod_{j\in E}(x-\alpha_j)\); its roots among \(L\) are exactly the errors. The algorithm reconstructs \(\sigma\) from the syndrome.
The two non-obvious lines are the split and the key equation, and both come from characteristic \(2\).
The split \(\sigma=a^2+x\,b^2\). Any polynomial over \(\mathbb{F}_{2^m}\) separates into even-degree and odd-degree parts; the even part is a perfect square \(a^2\), and the odd part is \(x\) times a perfect square \(x\,b^2\). Differentiating, \((a^2)'=0\) and \((x b^2)'=b^2\), so \(\sigma'=b^2\).
The key equation. Because \(S=\sigma'/\sigma \bmod g\), we have \(\sigma'\equiv \sigma S\), i.e. \(b^2\equiv(a^2+xb^2)S \pmod g\). Multiplying by \(T=S^{-1}\) and rearranging gives \(a^2\equiv b^2\,(T+x)\pmod g\). Taking the square root \(R=\sqrt{T+x}\) turns this into the linear-looking congruence \(a\equiv R\,b\pmod g\), which the extended Euclidean algorithm solves for a pair of the required small degrees.
Once \(\sigma\) is known, evaluating it at every \(\alpha_j\) (a Chien search) locates the errors, and over \(\mathbb{F}_2\) correcting them is a bit flip. The cost is dominated by the extended Euclidean step and the root search, both quasi-linear in \(n\) with fast arithmetic; this is the “efficient decoder \(\mathcal{D}_g\)” the main text invoked.
A.6A construction in SageMath#
The whole object is short to build. Take \(m=4\), so \(\mathbb{F}_{16}\), and a squarefree Goppa polynomial of degree \(t=2\).
F.<a> = GF(2^4)
PR.<x> = F[]
g = x^2 + x + a
while not g.is_irreducible():
g = x^2 + F.random_element()*x + F.random_element()
assert g.is_irreducible()
L = [b for b in F if g(b) != 0] # support: exclude any roots of g
n = len(L)
from sage.coding.goppa_code import GoppaCode
C = GoppaCode(g, L)
print(C) # a binary [n, k] Goppa code
print(C.dimension(), n - g.degree() * F.degree()) # k vs n - m tHere \(mt = 4\cdot 2 = 8\), so the dimension satisfies \(k\ge n-8\), and by Proposition A.2 the minimum distance is at least \(2t+1=5\), so the code corrects \(t=2\) errors. This demonstrates the algebraic core only. Engineering-grade Classic McEliece additionally fixes parameter sets, support ordering, systematic-matrix reduction, encoding, KEM behavior, failure handling, and constant-time requirements.
A.7Why Goppa codes, and not others#
Three properties, taken together, are what make binary Goppa codes the enduring choice for McEliece.
An efficient decoder. Patterson’s algorithm corrects the full \(t\) errors in near-linear time – the trapdoor the legitimate key holder uses.
A vast family. There are enormously many choices of support \(L\) and polynomial \(g\), so keys cannot be enumerated, and a random secret code is overwhelmingly unlikely to coincide with any particular target.
Indistinguishability. No efficient algorithm distinguishes a scrambled binary Goppa code from a random linear code of the same parameters. This is the security-critical property, and it is where less conservative families failed: the generalized Reed–Solomon codes of the original Niederreiter proposal were broken by the Sidelnikov–Shestakov structural attack [3], and several Reed–Muller and algebraic-geometry variants fell the same way.
Read the third bullet carefully: it says efficient, and that word has been doing more work each year since 2023. Section A.8 is about what has happened to it.
This is the concrete content behind the “decodable code in disguise” of Chapter 22: the disguise is the scrambled generator matrix, and the code being disguised is \(\Gamma(L,g)\).
A.8The distinguishers, and what they cost#
A distinguisher is not a break. It does not read a message and it does not recover a key; it answers one bit — is this public key a Goppa code or a random matrix? McEliece can survive with that bit leaked, because recovering the plaintext still means decoding, and decoding a random-looking code is the assumption that has never fallen.
But the bit matters, for two reasons. It is the difference between the conservative security claim (the public key is pseudorandom, so LPN applies) and the minimal one (recovering the message is hard). And historically, distinguishers have been the first step: Sidelnikov–Shestakov began as a structural observation about generalized Reed–Solomon codes and ended as a polynomial-time key recovery.
A.8.1The square-code barrier#
The classical tool is the Schur product: for \(a,b \in \mathbb{F}_q^n\) write \(a \star b := (a_1b_1,\dots,a_nb_n)\), and let \(\mathcal{C}^{\star 2} := \operatorname{span}\{a\star b\}\) be the square code. For a random code of dimension \(k\) the square has dimension \(\min\{n,\binom{k+1}{2}\}\) — essentially everything. For a code that lives inside a GRS code of dimension \(K\), products of evaluations of degree-\(<K\) polynomials have degree \(<2K-1\), so \[\dim \mathcal{C}^{\star 2} \;\le\; \min\{n,\; 2K-1\}.\] The structure shows up as a dimension defect — and only when \(2K-1 < n\), essentially when the ambient rate is below \(1/2\). This is the distinguisher of Faugère, Gauthier-Umaña, Otmani, Perret and Tillich [4], and it is polynomial-time, which is why Classic McEliece’s parameters were chosen to sit well outside its reach. Dualizing is the standard escape — the dual of a GRS code is again GRS, of dimension \(n-K\) — but it fails here, because the published code is only a subcode of the ambient GRS code and the dual of a subcode is a supercode of the dual, with no reason to have a small square.
A.8.2Crossing it with multiplicities#
Ghoshal, Ishai, Jain and Sun [5] cross that barrier with an idea that is more general than this setting. Replace evaluations by Hasse jets — the value of a polynomial together with all its Hasse derivatives of order below \(s\). Each coordinate then supplies \(s\) Hermite-interpolation constraints instead of one, and the condition for the structure to be forced weakens from \[n > dD \qquad\text{to}\qquad s(n-1) > dD ,\] where \(D\) is the ambient GRS degree and \(d\) the test degree. The number of coordinates needed falls from about \(dD\) to about \(dD/s\), which is exactly what lets the test keep working in the regime where the square code has already saturated.
The resulting algorithm is short enough to state in full. Fix \(s\) and \(d = s+1\), take the public matrix \(Y = [\,y_1|\cdots|y_n\,] \in \mathbb{F}_2^{k\times n}\), and:
hold out one column, say \(y_n\);
compute the space of multilinear homogeneous degree-\(d\) polynomials over \(\mathbb{F}_2\) that vanish on the Hamming ball of radius \(s-1\) around every other column (for multilinear \(F\) over \(\mathbb{F}_2\), vanishing on that ball is the order-\(<s\) Hasse jet vanishing);
take any nonzero \(h\) from that space and evaluate it at \(y_n\).
If \(h(y_n) \ne 0\), answer random; otherwise answer Goppa.
On a Goppa key the answer is always Goppa, with no probability attached. Restricting \(h\) to homogeneous polynomials makes the vanishing conditions blind to the unknown GRS multipliers; composing \(h\) with the hidden low-degree curve gives a univariate \(\varphi\) of degree at most \(dD\) with a zero of multiplicity \(s\) at each of \(n-1\) distinct points, and \(s(n-1) > dD\) forces \(\varphi \equiv 0\) by Hermite interpolation. On a random matrix a nonzero \(h\) exists whenever \(\binom{k}{d}\) exceeds the constraint count, and the held-out column is still uniform, so the minimum-distance bound for binary Reed–Muller codes bounds the false accept away from 1.
A.8.3Where the doubled distance reappears#
Proposition A.2 returns here, and not in the reader’s favour. Because \(\Gamma(L,g) = \Gamma(L,g^2)\) for squarefree \(g\), the code sits inside an ambient GRS code of dimension \(n-2t\) rather than \(n-t\) — so \(D = n-2t-1\), and the reconstruction condition \(s(n-1) > dD\) is easier to satisfy. The identity that buys the free doubling of the minimum distance is the same identity that sharpens the distinguisher. Abandoning it is no defence: the attack still runs in quasipolynomial time with \(D = n-t-1\), and one would have given up the error-correction for a worse constant.
A.8.4What it costs, and what it does not touch#
In the asymptotic regime Classic McEliece is actually parameterized for — extension degree \(m = \Theta(\log n)\), Goppa degree \(t = \Theta(n/\log n)\), dimension \(k = \Theta(n)\) — the two conditions are met by \(s,d = \Theta(\log n)\), and the polynomial space has dimension \(\binom{k}{d} \le k^d = n^{O(\log n)}\). Quasipolynomial: superpolynomial, but far below the \(2^{\Theta(t)}\) of generic decoding.
That \(\Theta(\log n)\) is forced rather than chosen. Substituting \(D = n-2t-1\) and \(d = s+1\) turns the reconstruction condition into \(2(s+1)t > n-1\) — the multiplicity and the Goppa degree must multiply to about \(n/2\). With \(t = \Theta(n/\log n)\) fixed by the scheme, \(s = \Theta(\log n)\) is the smallest that works, and the running time follows from it.
Concretely, after shortening (which lowers both length and dimension before the test), the estimates are:
| Parameter set | Distinguisher | Best previous | Generic decoding |
|---|---|---|---|
mceliece348864 |
\(2^{114}\) | \(2^{298}\) | \(2^{151}\) |
mceliece460896 |
\(2^{120}\) | \(2^{595}\) | \(2^{191}\) |
mceliece6688128 |
\(2^{124}\) | \(2^{691}\) | \(2^{257}\) |
mceliece8192128 |
\(2^{124}\) | \(2^{551}\) | \(2^{287}\) |
Read the table in two passes. The distinguisher is now cheaper than generic decoding on every parameter set, and below the claimed security level of the smallest — so the conservative assumption no longer holds anywhere in the standardized range. But the minimal assumption is untouched: there is no key recovery, and the decryption attack the same paper describes is heuristic and, by its authors’ own assessment, far beyond practical reach.
Two properties of this result set it apart from the subexponential distinguishers that preceded it [6, 7]. Its soundness analysis is unconditional — linear algebra and the Reed–Muller distance bound, with no heuristic about how some algebraic invariant behaves on random codes. And it came from somewhere unexpected: a failed attempt to build doubly-efficient private information retrieval from algebraic locally decodable codes. A McEliece public key has exactly the shape of a permuted PIR query matrix; the Reed–Muller construction reproduces the square-code attack, and the multiplicity-code construction gives this one.
A.8.5The consequence for parameters#
The last observation is the one most likely to outlive the attack. Generic decoding costs \(2^{\tilde{O}(t)}\) and this distinguisher costs \(2^{\tilde{O}(n/t)}\), so resisting both is governed by \[\min\{t,\; n/t\} \;\le\; \sqrt{n},\] and demanding \(\kappa\)-bit security against both forces \(n = \tilde{\Omega}(\kappa^2)\). Classic McEliece’s distinctive offer was \(\kappa\)-bit security with \(\tilde{O}(\kappa)\)-length ciphertexts — 96 bytes at the smallest parameter set, the smallest of any NIST candidate. Under this attack it falls onto the same quadratic curve as the LPN-based schemes it was meant to improve on. The enormous public key was always the acknowledged price; the tiny ciphertext was the compensation, and it is the compensation that this result puts in question.
Further reading#
Goppa introduced the codes in 1970 [1]; Patterson gave the binary decoder in 1975 [2]; McEliece turned them into a cryptosystem in 1978 [8]; and the current parameters and constant-time engineering are specified by the Classic McEliece submission [9].
Comments