Offensive Security Researcher & Quantum Cryptography Analyst

McEliece Algorithm: Working, Explanation, and Post-Quantum Cryptography

Abdul Wahab Junaid
McEliece algorithm and working of this algorithm

McEliece algorithm and working of this algorithm

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

How It Works

I walk through the three main phases:

  1. 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.
  2. Choose a random invertible $k \times k$ matrix $S$ and a random $n \times n$ permutation matrix $P$.
  3. Compute the public generator matrix as $\hat{G} = S \cdot G \cdot P$.
  4. Publish $(\hat{G}, t)$ as the public key; keep $(S, G, P)$ and the Goppa decoding algorithm as the private key.
  5. 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$.
  6. 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$.
  7. 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 m

Pseudocode

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

Disadvantages

Applications

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

Common Mistakes

Further Reading

Exit mobile version