I consider the McEliece cryptosystem to be the oldest surviving code-based public-key encryption scheme, and one of the very few classical cryptosystems from the 1970s that has never been broken at its recommended parameters, even after decades of dedicated cryptanalysis. I find it particularly relevant today because it is one of the leading candidates (as “Classic McEliece”) in the NIST post-quantum cryptography standardization process. What draws me to it is how different its security foundation is from RSA or ECC — instead of relying on number theory, McEliece hides an efficiently-decodable error-correcting code behind random linear transformations, turning decoding into a problem that looks intractable to anyone without the secret structure.
History and Background
I trace the McEliece cryptosystem back to Robert McEliece’s 1978 paper, published as a JPL technical report rather than a traditional peer-reviewed venue, which is part of why it took a while to gain mainstream cryptographic attention. It predates RSA-based schemes’ dominance and was originally proposed using binary Goppa codes. Despite being largely overlooked for practical deployment for many years — mainly because of its large public key size — it has aged remarkably well from a security standpoint. Unlike many contemporaries, its core security assumption (the hardness of decoding a general linear code) has not been meaningfully weakened by advances in classical algorithms, and no efficient quantum algorithm is known for it either, which is precisely why it re-emerged as a leading post-quantum candidate decades later.
Problem Statement
I want a public-key encryption scheme that remains secure even against an adversary equipped with a large-scale quantum computer. RSA and ECC both fall to Shor’s algorithm, so I need a different hard mathematical problem. I choose the problem of decoding a random linear code — given a generator matrix and a received (possibly corrupted) codeword, finding the original message — which is proven NP-hard in general, and for which no known efficient classical or quantum algorithm exists when using well-chosen code families.
Core Concepts
- Generator matrix $G$ — a $k \times n$ matrix that maps a $k$-bit message $m$ to an $n$-bit codeword via $c = mG$.
- Error-correcting code — a scheme that can recover the original message even if some bits of the transmitted codeword are flipped, up to a maximum number $t$ of errors.
- Binary Goppa code — the specific algebraic code family McEliece uses, chosen because it has an efficient decoding algorithm capable of correcting up to $t$ errors.
- Scrambler matrix $S$ — a random invertible $k \times k$ matrix used to disguise the structure of $G$.
- Permutation matrix $P$ — a random $n \times n$ permutation matrix used to further scramble the code’s column order.
- Public/private key split — the public key is a disguised generator matrix; the private key is the original Goppa code plus $S$ and $P$, enabling efficient decoding.
How It Works
I walk through the three main phases:
- Key generation: Select a binary Goppa code with parameters $[n, k, 2t+1]$, giving a $k \times n$ generator matrix $G$ that can correct up to $t$ errors using an efficient decoding algorithm.
- Choose a random invertible $k \times k$ matrix $S$ and a random $n \times n$ permutation matrix $P$.
- Compute the public generator matrix as $\hat{G} = S \cdot G \cdot P$.
- Publish $(\hat{G}, t)$ as the public key; keep $(S, G, P)$ and the Goppa decoding algorithm as the private key.
- Encryption: To send a $k$-bit message $m$, compute $c = m\hat{G}$, then deliberately add a random error vector $e$ of weight exactly $t$: the ciphertext is $y = c \oplus e = m\hat{G} \oplus e$.
- Decryption: Compute $y P^{-1} = m S G \oplus e P^{-1}$. Since $eP^{-1}$ still has weight $t$ (permutation preserves Hamming weight), apply the Goppa decoding algorithm to correct these $t$ errors and recover $mS \cdot G$’s underlying message $mS$.
- Recover the original message as $m = (mS) S^{-1}$.
Working Principle
I understand this scheme as deliberately injecting noise into a message that only the legitimate receiver can remove, because only they know the specific error-correcting code hiding underneath the disguised public matrix. To an outside attacker, $\hat G$ looks like the generator matrix of some arbitrary linear code, so recovering $m$ from $y$ appears to require solving general syndrome/message decoding — a problem with no known efficient algorithm for well-parameterized random-looking codes. The legitimate receiver, however, can undo the permutation and scrambling to reveal the underlying Goppa code structure, where fast algebraic decoding algorithms (like Patterson’s algorithm) make error correction efficient.
Mathematical Foundation
I define the public key as:
$$ \hat{G} = S \cdot G \cdot P $$
Encryption computes:
$$ y = m\hat{G} \oplus e, \qquad \text{wt}(e) = t $$
Decryption first undoes the permutation:
$$ yP^{-1} = mSG \oplus eP^{-1} $$
Since $mSG$ is itself a valid Goppa codeword (because $mS$ is just another $k$-bit vector being encoded by $G$), and $eP^{-1}$ still has weight $t$, the Goppa decoder recovers $mSG$ exactly, provided:
$$ t \leq \left\lfloor \frac{d-1}{2} \right\rfloor $$
where $d = 2t+1$ is the code’s minimum distance. From the recovered codeword $mSG$, I extract $mS$ (since $G$ is systematic or invertible on a known information set), then compute:
$$ m = (mS)S^{-1} $$
The overall security reduces to the assumed hardness of the general decoding problem:
$$ \text{Given } \hat G, y: \text{ find } m \text{ such that wt}(y \oplus m\hat G) \leq t $$
which is NP-hard for general linear codes and has no known efficient solving algorithm for the disguised Goppa code case.
Diagrams
flowchart TD
K1[Select Goppa code: generator matrix G, corrects t errors] --> K2[Choose random S and permutation P]
K2 --> K3[Public key: G_hat = S * G * P]
K3 --> E1[Message m encoded: c = m * G_hat]
E1 --> E2[Add random weight-t error: y = c XOR e]
E2 --> D1[Receiver computes y * P^-1]
D1 --> D2[Goppa decoder removes t errors, recovers m*S*G]
D2 --> D3[Extract mS, then compute m = mS * S^-1]sequenceDiagram
participant S as Sender
participant R as Receiver
R->>S: Public key G_hat, error weight t
S->>S: Compute c = m * G_hat
S->>S: Add random error e (weight t)
S->>R: Send ciphertext y = c XOR e
R->>R: Compute y * P^-1
R->>R: Apply Goppa decoding to remove errors
R->>R: Undo scrambler S to recover message mPseudocode
Function McElieceKeyGen(n, k, t):
(G, decoder) = GenerateGoppaCode(n, k, t) // k x n generator matrix
S = RandomInvertibleMatrix(k, k)
P = RandomPermutationMatrix(n)
G_hat = S * G * P
publicKey = (G_hat, t)
privateKey = (S, G, P, decoder)
return (publicKey, privateKey)
Function McElieceEncrypt(m, G_hat, t):
c = m * G_hat
e = RandomWeightTVector(n, t)
y = c XOR e
return y
Function McElieceDecrypt(y, privateKey):
(S, G, P, decoder) = privateKey
y_prime = y * inverse(P)
codeword = decoder(G, y_prime) // corrects up to t errors
mS = ExtractMessage(codeword, G)
m = mS * inverse(S)
return m
Step-by-Step Example
I illustrate with a small conceptual example, again using a simplified Hamming-style stand-in for a true Goppa code, since real Goppa codes are algebraically heavier to hand-compute. Suppose $k=4$, $n=7$, $t=1$, and:
$$ G = \begin{pmatrix} 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 \end{pmatrix} $$
Suppose I choose a random invertible $S$ and a permutation $P$ of the 7 columns to obtain the public $\hat G = SGP$. To send message $m = 1011$, I compute $c = m\hat G$, a 7-bit codeword, then flip exactly one bit at random (say, position 3) to get ciphertext $y = c \oplus e$ where $e = 0010000$. The receiver undoes $P$ first, then runs the Hamming decoder (standing in for a true Goppa decoder) to identify and correct the single flipped bit, recovering the codeword $mSG$, and finally undoes $S$ to recover $m = 1011$ exactly.
Time Complexity
I separate this into the three phases. Key generation, dominated by generating the Goppa code and computing $G_{hat} = SGP$, takes roughly $O(n^2 k)$ for the matrix multiplications involved. Encryption is a vector-matrix multiplication plus adding a sparse error vector:
$$ T_{\text{encrypt}} = O(nk) $$
Decryption is dominated by the Goppa decoding step, typically:
$$ T_{\text{decrypt}} = O(n t) \text{ to } O(t^2 \log n) $$
depending on the specific decoding algorithm (Patterson’s algorithm is commonly cited around $O(nt)$ for practical parameter ranges), plus $O(nk)$ for the matrix operations to undo $S$ and $P$.
Space Complexity
The public key $\hat G$ is a dense $k \times n$ binary matrix requiring:
$$ S_{\text{public}} = O(nk) $$
bits, which for real-world secure parameters (e.g., $n=6960$, $k=5413$, $t=119$ in Classic McEliece) results in public keys on the order of a megabyte — notably larger than RSA or ECC keys. The private key needs $S$ ($O(k^2)$), $G$ ($O(nk)$), and $P$ ($O(n)$), giving overall private key space also around $O(nk)$.
Correctness Analysis
I consider the scheme correct because permutation matrices preserve Hamming weight, so the injected error $e$ of weight $t$ remains weight $t$ after multiplying by $P^{-1}$. Since the underlying Goppa code is guaranteed to correctly decode any error pattern of weight $t \leq \lfloor (d-1)/2 \rfloor$, and the scheme is parameterized so this bound is always respected, decryption always succeeds in recovering the exact original codeword, and hence the exact original message, given the correct private key and no implementation bugs.
Advantages
- One of the longest-standing unbroken public-key cryptosystems, with over four decades of cryptanalysis at recommended parameters.
- Believed resistant to quantum attacks, unlike RSA and ECC, since general syndrome/message decoding has no known efficient quantum algorithm.
- Very fast encryption and decryption relative to RSA, since operations are simple linear algebra over $\mathbb{F}_2$.
- A NIST-selected finalist (“Classic McEliece”) for post-quantum key encapsulation standardization.
Disadvantages
- Extremely large public key sizes (hundreds of kilobytes to over a megabyte), which is impractical for some bandwidth- or storage-constrained systems.
- Ciphertext expansion — the encrypted message is larger than the plaintext due to the added error bits.
- Choosing insecure code families (structured codes with too much algebraic symmetry) can be catastrophically broken, as has happened with some non-Goppa variants.
- Key generation is relatively expensive and requires careful, correct construction of a valid Goppa code.
Applications
- Post-quantum secure key encapsulation mechanisms, particularly Classic McEliece, being considered for long-term data protection.
- Government and military communication systems requiring high-assurance, quantum-resistant encryption.
- Long-term archival encryption where data must remain confidential decades into the future, even against future quantum decryption capability.
- Research baseline for comparing new code-based cryptosystem proposals against a well-studied, trusted historical scheme.
Implementation in C
I implement a simplified demonstration using a toy Hamming-style generator matrix, mirroring the structure of the Niederreiter example but applied to the McEliece encoding-then-corrupt-then-decode flow.
#include <stdio.h>
#include <string.h>
#define K 4 /* message length */
#define N 7 /* codeword length */
/* Toy (7,4) generator matrix (stand-in for a real Goppa-code generator matrix) */
int G[K][N] = {
{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}
};
/* Toy parity-check matrix matching G, used for simple syndrome-based decoding */
int H[N-K][N] = {
{1,1,0,1,1,0,0},
{1,0,1,1,0,1,0},
{0,1,1,1,0,0,1}
};
void encode(int m[K], int c[N]) {
for (int j = 0; j < N; j++) {
c[j] = 0;
for (int i = 0; i < K; i++) {
c[j] ^= (m[i] & G[i][j]);
}
}
}
void add_error(int c[N], int errorPos, int y[N]) {
memcpy(y, c, sizeof(int) * N);
y[errorPos] ^= 1; /* flip exactly one bit: weight-1 error, t = 1 */
}
int find_error_position(int y[N]) {
int syndrome[N-K];
for (int i = 0; i < N-K; i++) {
syndrome[i] = 0;
for (int j = 0; j < N; j++) {
syndrome[i] ^= (H[i][j] & y[j]);
}
}
/* match syndrome against each column of H to find the error position */
for (int col = 0; col < N; col++) {
int match = 1;
for (int row = 0; row < N-K; row++) {
if (H[row][col] != syndrome[row]) { match = 0; break; }
}
if (match) return col;
}
return -1; /* no single-bit error detected */
}
int main() {
int m[K] = {1, 0, 1, 1}; /* the message to send */
int c[N], y[N];
encode(m, c);
printf("Encoded codeword: ");
for (int i = 0; i < N; i++) printf("%d", c[i]);
printf("\n");
add_error(c, 3, y); /* inject one error at position 3 */
printf("Ciphertext (with error): ");
for (int i = 0; i < N; i++) printf("%d", y[i]);
printf("\n");
int errPos = find_error_position(y);
printf("Detected error position: %d\n", errPos);
if (errPos != -1) y[errPos] ^= 1; /* correct the error */
printf("Corrected codeword: ");
for (int i = 0; i < N; i++) printf("%d", y[i]);
printf("\n");
return 0;
}
Sample Input and Output
Encoded codeword: 1011010
Ciphertext (with error): 1010010
Detected error position: 3
Corrected codeword: 1011010
Optimization Techniques
- Using structured code variants like quasi-cyclic or quasi-dyadic Goppa codes to significantly shrink public key sizes, while carefully verifying they do not reintroduce exploitable algebraic structure.
- Applying efficient bitsliced or SIMD-vectorized matrix-vector multiplication to speed up encryption on modern CPUs.
- Using the Patterson decoding algorithm rather than brute-force syndrome tables for practical values of $n$ and $t$.
- Caching the precomputed decoding data structures (like the code’s parity-check matrix in systematic form) to speed up repeated decryption operations.
Common Mistakes
- Using structured codes (like some quasi-cyclic variants) without rigorous security analysis, since added structure sometimes introduces new algebraic attacks.
- Choosing error weight $t$ or code parameters $(n,k)$ too small for genuine security, especially against information-set decoding attacks.
- Failing to use a proper cryptographically secure random source when generating the error vector $e$, which can leak exploitable patterns.
- Implementing without side-channel protections, since decoding time or memory access patterns can sometimes leak information about the private Goppa code structure.
Further Reading
- McEliece, R. J., “A Public-Key Cryptosystem Based on Algebraic Coding Theory,” DSN Progress Report 42-44, JPL, 1978. https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF
- Bernstein, D. J., Lange, T., Peters, C., “Attacking and Defending the McEliece Cryptosystem,” PQCrypto 2008. https://eprint.iacr.org/2008/318
- Classic McEliece NIST PQC Submission. https://classic.mceliece.org/
- Overbeck, R., Sendrier, N., “Code-based Cryptography,” in Post-Quantum Cryptography, Springer, 2009. https://link.springer.com/chapter/10.1007/978-3-540-88702-7_4
- NIST Post-Quantum Cryptography Standardization Project. https://csrc.nist.gov/projects/post-quantum-cryptography
