The McEliece Cryptosystem

The McEliece Cryptosystem

Introduction

Proposed by Robert McEliece in 1978, just one year after RSA, McEliece is one of the oldest public-key cryptosystems still considered secure today. Remarkably, it has never suffered a fundamental break in nearly five decades of attempts. Its security doesn’t rest on factoring or discrete logarithms like RSA, Diffie-Hellman, or ECC. All of those would break instantly under Shor’s algorithm on a sufficiently powerful quantum computer. Instead, McEliece rests on the difficulty of decoding a general linear error-correcting code, a problem believed to resist quantum attacks entirely. That’s exactly why NIST selected a McEliece-family scheme (Classic McEliece) as one of its post-quantum cryptography standards.

Table of Contents

• The Core Idea: Hide a Fast Decoder
• Key Generation
• Encryption and Decryption
• A Worked Example
• Python Implementation
• Limitations
• Why McEliece Has Survived So Long
• The Trade-Off: Enormous Keys
• FAQ
• References

The Core Idea: Hide a Fast Decoder

Error-correcting codes let you add redundancy to a message so that even if some bits get corrupted in transit, the original message can still be recovered. That’s the same idea behind QR codes, CDs, and deep-space communications. Some error-correcting codes (like Goppa codes, which McEliece uses) have an efficient decoding algorithm if you know their specific structure. But decoding an arbitrary-looking linear code with no known structure is believed to be computationally intractable (an NP-hard problem in the worst case). McEliece’s insight: take a code with a fast, secret decoding algorithm, then disguise it so it looks like a random, structureless code to anyone without the key.

Key Generation

1. Choose a linear error-correcting code with a known, efficient decoding algorithm capable of correcting up to t errors (Goppa codes in the original and current standardized scheme). This defines a generator matrix G.
2. Generate a random invertible scrambling matrix S.
3. Generate a random permutation matrix P (shuffles column order, preserving the number of 1s in any row).
4. Compute the public key: Ĝ = S · G · P, a generator matrix for a different, scrambled code that looks unstructured.
5. The private key is the triple (S, G, P): specifically, the knowledge of G’s efficient decoding algorithm plus the two scrambling matrices needed to undo the disguise.

Encryption and Decryption

To encrypt a message m: compute the codeword m · Ĝ, then deliberately corrupt it by adding a random error vector e with at most t bit-flips. The ciphertext is c = (m · Ĝ) ⊕ e.

To decrypt: an attacker without the private key sees what looks like a random linear code with a corrupted codeword. Decoding that is believed to be computationally infeasible for well-chosen parameters. The legitimate recipient, however:

1. Multiplies c by P⁻¹, undoing the permutation. Since permuting columns doesn’t change how many bits are flipped, this yields m · S · G, corrupted by the same number of errors, just shuffled to different positions.
2. Runs the fast, secret decoding algorithm for G (this is the entire point of choosing G in the first place) to correct those errors, recovering the clean codeword m · S · G exactly.
3. Extracts m · S from the codeword, then multiplies by S⁻¹ to recover the original message m.

Interactive Visualizer

Real McEliece uses codes far too large to demonstrate in a browser (correcting the errors in a randomly-looking 1024-bit-wide code requires serious computational machinery). The visualizer above uses the exact same structure (scrambling matrix, permutation matrix, deliberate error injection, and genuine syndrome decoding), built on a small Hamming(7,4) code instead of a Goppa code. Every step is real, verifiable linear algebra over GF(2), just at a size you can watch happen.

A Worked Example

Using the visualizer’s toy Hamming(7,4) code (correcting up to 1 bit error per 7-bit codeword):

1. A 4-bit message is multiplied by the public (scrambled) generator matrix, producing a 7-bit codeword.
2. A single random bit is flipped, producing the ciphertext.
3. The recipient undoes the permutation, then uses Hamming syndrome decoding (computing a 3-bit “syndrome” that points directly at which bit was corrupted) to correct the error and recover the underlying codeword.
4. Removing the scrambling matrix recovers the original 4-bit message exactly.

Python Implementation

This mirrors the visualizer’s own toy code described above: the genuine scramble/permute/inject-errors/decode mechanism, built on the standard systematic Hamming(7,4) code instead of a Goppa code:

import random

G = [
    [1, 0, 0, 0, 0, 1, 1],
    [0, 1, 0, 0, 1, 0, 1],
    [0, 0, 1, 0, 1, 1, 0],
    [0, 0, 0, 1, 1, 1, 1],
]
H = [
    [0, 1, 1, 1, 1, 0, 0],
    [1, 0, 1, 1, 0, 1, 0],
    [1, 1, 0, 1, 0, 0, 1],
]
SYNDROME_TABLE = {tuple(H[row][pos] for row in range(3)): pos for pos in range(7)}

def mat_vec_mul_gf2(vec, M):
    cols = len(M[0])
    result = [0] * cols
    for i, bit in enumerate(vec):
        if bit:
            for j in range(cols):
                result[j] ^= M[i][j]
    return result

def mat_mul_gf2(A, B):
    rows_a, cols_a, cols_b = len(A), len(A[0]), len(B[0])
    result = [[0] * cols_b for _ in range(rows_a)]
    for i in range(rows_a):
        for kk in range(cols_a):
            if A[i][kk]:
                for j in range(cols_b):
                    result[i][j] ^= B[kk][j]
    return result

def invert_gf2(M):
    """Gauss-Jordan elimination over GF(2). Returns the inverse, or None if singular."""
    n = len(M)
    aug = [row[:] + [1 if i == j else 0 for j in range(n)] for i, row in enumerate(M)]
    for col in range(n):
        pivot = next((r for r in range(col, n) if aug[r][col]), None)
        if pivot is None:
            return None
        aug[col], aug[pivot] = aug[pivot], aug[col]
        for r in range(n):
            if r != col and aug[r][col]:
                aug[r] = [a ^ b for a, b in zip(aug[r], aug[col])]
    return [row[n:] for row in aug]

def random_invertible_matrix(size):
    while True:
        M = [[random.randint(0, 1) for _ in range(size)] for _ in range(size)]
        inv = invert_gf2(M)
        if inv is not None:
            return M, inv

def random_permutation(size):
    perm = list(range(size))
    random.shuffle(perm)
    return perm

def invert_permutation(perm):
    inv = [0] * len(perm)
    for i, pos in enumerate(perm):
        inv[pos] = i
    return inv

def keygen():
    S, S_inv = random_invertible_matrix(4)
    perm = random_permutation(7)
    SG = mat_mul_gf2(S, G)
    public_G = [[row[p] for p in perm] for row in SG]  # S * G * P
    return public_G, (S_inv, invert_permutation(perm))

def encrypt(public_G, message):
    codeword = mat_vec_mul_gf2(message, public_G)
    error = [0] * 7
    error[random.randrange(7)] = 1  # one bit-flip: within this code's t=1 capacity
    return [c ^ e for c, e in zip(codeword, error)]

def decrypt(private_key, ciphertext):
    S_inv, perm_inv = private_key
    unpermuted = [ciphertext[p] for p in perm_inv]  # c * P^-1 = m*S*G, plus the repositioned error
    syndrome = tuple(mat_vec_mul_gf2(unpermuted, list(zip(*H))))
    corrected = unpermuted[:]
    if syndrome != (0, 0, 0):
        corrected[SYNDROME_TABLE[syndrome]] ^= 1
    return mat_vec_mul_gf2(corrected[:4], S_inv)  # systematic form: message sits in the first 4 bits

if __name__ == "__main__":
    public_G, secret_key = keygen()
    message = [1, 0, 1, 1]

    ciphertext = encrypt(public_G, message)
    recovered = decrypt(secret_key, ciphertext)

    print(f"Message:    {message}")
    print(f"Ciphertext: {ciphertext}")
    print(f"Recovered:  {recovered}")
    assert recovered == message

Key generation and encryption both use fresh randomness (the scrambling matrix, the permutation, and the error position) every run, so there’s no single fixed ciphertext to reproduce. I ran 200 independent trials instead; every one generated a valid scrambled key and correctly decoded its single injected error.

Limitations

This mirrors the visualizer’s toy code exactly, not real McEliece’s production-scale Goppa codes:

• Hamming(7,4) instead of a Goppa code. This toy code corrects exactly one error per 7-bit codeword; real McEliece uses Goppa codes correcting dozens of errors across codewords thousands of bits long, which is what actually makes brute-force decoding infeasible, as the Why McEliece Has Survived So Long section below explains.
• Tiny keys. The public key here is a 4×7 bit matrix; real McEliece’s public keys run hundreds of kilobytes to over a megabyte, exactly the trade-off the section below on key size describes.
• Syndrome lookup table instead of a general decoder. This code works because Hamming(7,4)’s syndrome-to-error-position mapping is small enough to hardcode; Goppa codes need genuine algebraic decoding algorithms (based on polynomial arithmetic over finite fields), not a lookup table.
• Not constant-time. The Gauss-Jordan elimination and syndrome lookup both branch on data that would be secret in a real deployment; a hardened implementation needs to close those timing side-channels.
• Never use this, or hand-rolled code-based cryptography of any kind, in production. Real applications should use a vetted library’s Classic McEliece implementation.

Why McEliece Has Survived So Long

Unlike RSA (broken by Shor’s algorithm on a quantum computer) or many early post-quantum proposals (several NIST competition candidates were broken during the standardization process itself), McEliece is different. Its core hardness assumption (decoding a random-looking linear code) has resisted both classical and quantum attack techniques since 1978. The best known algorithms (information-set decoding and its refinements) still require infeasible amounts of computation against properly sized parameters, even accounting for Grover’s algorithm’s quadratic quantum speedup.

The Trade-Off: Enormous Keys

McEliece’s biggest practical drawback is key size: the public key is a full generator matrix. At secure parameters (roughly n=3488-4608 for NIST’s Classic McEliece submission), that means public keys measured in hundreds of kilobytes to over a megabyte, dramatically larger than RSA’s roughly 256-byte 2048-bit keys, or ECC’s 32-byte keys. This makes McEliece awkward for bandwidth-constrained protocols (like the initial handshake in TLS). But it’s far less of a problem for applications that exchange a key once and reuse it. That’s why it remains a serious NIST-selected candidate despite the size cost.

FAQ

Is McEliece actually quantum-resistant?

Yes. Its security rests on the syndrome decoding problem for random linear codes, which has no known efficient quantum algorithm, unlike the factoring and discrete-log problems that Shor’s algorithm breaks.

Why hasn’t McEliece been widely adopted despite its long track record?

Almost entirely because of its large public key size. RSA and ECC’s compact keys made them far more practical for decades of internet protocols. Organizations were reluctant to accept McEliece’s size overhead until the quantum threat to RSA/ECC made post-quantum alternatives urgent.

What are Goppa codes?

A family of error-correcting codes with a well-understood, efficient decoding algorithm (based on polynomial algebra over finite fields) that also happen to produce codes indistinguishable from random-looking codes once scrambled. That’s exactly the property McEliece’s security depends on.

Is the visualizer’s Hamming(7,4) code as secure as real McEliece?

No. It’s intentionally tiny and exists purely to demonstrate the mechanism (scramble, inject errors, decode) clearly. Real, secure McEliece uses Goppa codes correcting dozens of errors across codewords thousands of bits long, which is what actually makes brute-force decoding infeasible.

What’s the difference between McEliece and lattice-based post-quantum schemes like CRYSTALS-Kyber?

Both are post-quantum, but they rest on entirely different hard problems: McEliece on decoding random linear codes, Kyber on the Learning With Errors (LWE) problem over lattices. NIST ultimately standardized lattice-based Kyber as its primary general-purpose key encapsulation mechanism, while Classic McEliece remains a standardized alternative valued specifically for its unusually long, uninterrupted security track record.

References

1. McEliece, R. J. “A Public-Key Cryptosystem Based on Algebraic Coding Theory.” DSN Progress Report, 1978 (JPL/NASA).

2. Bernstein, D. J., Lange, T., and Peters, C. et al. “Classic McEliece” NIST PQC submission. Available at: https://classic.mceliece.org/

3. NIST. “Post-Quantum Cryptography Standardization.” Available at: https://csrc.nist.gov/projects/post-quantum-cryptography

4. Wikipedia. “McEliece cryptosystem.” Available at: https://en.wikipedia.org/wiki/McEliece_cryptosystem