Why Decoding a Random Linear Code Is Hard Enough to Sign With

The oldest public-key encryption scheme still unbroken is not RSA. McEliece proposed a code-based cryptosystem in 1978, a year after Rivest, Shamir and Adleman, and it has survived four decades of cryptanalysis while RSA’s original 512-bit parameters fell to factoring progress and elliptic curve variants were undermined by side-channel and invalid-curve attacks. What has kept McEliece alive is a hardness assumption from a different branch of mathematics: decoding a random linear code is hard, and the cost of the best known decoders is exponential in the code length.

The decoding problem stated as a matrix

A linear code of length $n$ and dimension $k$ over $\mathbb{F}_2$ is the set of vectors $c$ satisfying $Hc = 0$ for an $(n-k) \times n$ parity-check matrix $H$ of rank $n-k$. Equivalently, it is the row space of a generator matrix $G$ of size $k \times n$. The code has $2^k$ codewords out of $2^n$ possible vectors, so a random vector is a codeword with probability $2^{k-n}$.

The central hard problem is \emph{syndrome decoding}. Given $H$ and a syndrome $s \in \mathbb{F}_2^{n-k}$, find an error vector $e$ of Hamming weight at most $w$ such that $He = s$. When $w$ is below the covering radius, a solution exists with positive probability, and finding one is believed to require exponential time in $n/k$ for random $H$. The decision form asks whether such an $e$ exists, and the search form asks for it.

The connection to encryption is direct. In the McEliece construction the public key is a generator matrix $G’ = SGP$, where $G$ is the generator matrix of a code with an efficient decoder, $S$ is a random invertible scrambling matrix, and $P$ is a random permutation. The plaintext $m$ is encoded as $c = mG’ + e$ with $e$ a random error vector of weight $t$. The recipient, who knows the structure, strips $P$, decodes with the efficient algorithm, and strips $S$. An attacker who sees only $G’$ faces a decoding problem on a code whose structure is hidden.

Niederreiter’s transposition and what it buys

Niederreiter’s variant states the same problem in the parity-check form. The public key is a parity-check matrix $H’ = SHP$, the ciphertext is the syndrome $s = H’e^T$ of a low-weight error vector, and decryption recovers $e$ using the secret code structure. The security is the same problem viewed from the dual code, and the two schemes are equivalent under suitable parameters.

The practical difference is message length and ciphertext size. McEliece’s ciphertext is a codeword of length $n$; Niederreiter’s is a syndrome of length $n-k$, which is much shorter for the same security. For the same public key size, Niederreiter also admits a smaller public matrix because the parity check matrix has fewer rows than the generator matrix has columns. These are the reasons the modern code-based signature proposals build on the Niederreiter form, and why the public keys still measure in the hundreds of kilobytes or megabytes depending on the parameter set.

The price of the Niederreiter form is that the plaintext space is the set of weight-$t$ error patterns, not the space of arbitrary messages. Converting a hash digest into such a pattern requires an encoding step. The common construction uses a restricted-weight encoding: a digest of $\ell$ bits is mapped to a weight-$t$ binary string by a combinatorial unranking procedure that treats a set of positions as a number in the range $\binom{n}{t}$. Decoding the same string requires inverting that combinatorial numbering. A signature scheme needs the encoding to be a bijection onto a set of fixed weight vectors, and the efficiency of the unrank-and-rank routines determines whether signing is dominated by hashing or by the decoder.

The algorithms that set the security level

Prange’s information-set decoding, described in 1962, is the baseline. Choose $k$ columns of $H$ that form an invertible submatrix, bring the matrix into systematic form by row operations, and solve for $e$ by testing whether the resulting syndrome’s nonzero entries fall outside the chosen columns. If they do, the result is a valid low-weight solution; if not, try another information set. The probability of success per trial is approximately $\binom{n-k}{t} / \binom{n}{t}$ for the parameters of interest, which is astronomically small, so the algorithm’s cost is the number of trials times the cost of one Gaussian elimination.

Stern’s algorithm improves the constant by exploiting collisions. It splits the information set into two halves, lists candidate partial solutions in each half, and looks for pairs whose sums produce the desired syndrome. The collision search is a meet-in-the-middle, and the algorithm’s complexity is roughly $2^{c n/\log n}$ for a constant $c$ that depends on the rate. The modern improvements by Minder and Peters, and later by Becker, Joux, May and Meurer at the Asiacrypt “decoding challenge”, reduced the exponent through a mixture of Stern’s algorithm with Wagner’s generalised birthday technique and with careful bit-manipulation tuning. Every redesign of the code-based parameter sets since 2008 can be read as a response to a tightening in that exponent.

The consequence for anyone choosing parameters: the security level is not a property of $n$ alone. A long code with a high rate has a smaller information set and is easier to attack than a shorter code with a low rate. The security claims in the Classic McEliece submission are stated against a specific decoder model, and the parameter sets were re-evaluated after each improvement, which is why the candidate settled on parameters that look large next to early McEliece proposals. For a scheme whose ciphertext is already hundreds of bytes, the growth in public key size was accepted rather than traded away.

The code must be random, and why that is an operational burden

McEliece’s original proposal used binary Goppa codes, which have an efficient algebraic decoder and a distinguishing property that allows the recipient to find the close codeword. The decoder is the Patterson algorithm, which corrects up to $t$ errors for a Goppa polynomial of degree $t$ and runs in $O(t n^2)$ bit operations. That is cheap enough that decryption is not the bottleneck, which is unusual among post-quantum schemes.

A code with too much structure is a liability: if the public key can be recognised as a structured code, the attacker can recover the structural trapdoor instead of decoding. The pattern of a structure-detection attack is a linear-algebra test that the legitimately random-looking matrix fails. The simplest form is a rank check: a quasi-cyclic code of block size $b$ has a parity-check matrix whose blocks are circulant, so the matrix has a low-rank decomposition that a rank computation over a small extension field reveals. A quasi-dyadic code has an even more severe structure, with each block a dyadic matrix determined by $O(\log b)$ bits, and the corresponding attack recovers the trapdoor from a rank computation on a few blocks.

The history of code-based cryptography includes several schemes that failed exactly this way, and the lesson is that a hidden structure has to be tested for, not assumed away. The checking procedure is mechanical: compute invariants of the public matrix, such as its rank over extensions, its weight distribution, the dimension of its automorphism group, and its generator polynomial’s factorisation, and compare against the invariants of a random matrix of the same size. A parameter set that can be distinguished from random in polynomial time is not a parameter set; the Classic McEliece design incorporates the outcome of that test by keeping the Goppa structure and accepting the key size.

This is the opposite of the lattice situation, where the public key is statistically indistinguishable from uniform by construction and the reduction argument covers the average case. A code-based public key is a large unstructured object whose security rests on the belief that distinguishing random from hidden-Goppa codes is hard; that belief has held since 1978, but the surrounding ecosystem is thinner than for lattices. The operational cost is also higher, since the public key is a dense binary matrix of several hundred kilobytes and the key generation step requires generating a random invertible matrix and checking its rank over $\mathbb{F}_2$. The per-session trade-off against the compact keys from FIPS 203 is one of the more interesting decisions in hybrid key exchange deployment.