McEliece cryptosystem

In cryptography, the McEliece cryptosystem is an asymmetric key algorithm developed in 1978 by Robert McEliece. The algorithm has never gained much acceptance in practice.

The private and public keys are large matrices, which is one of the main disadvantages of the algorithm. The public key is very large: 2¹⁹ bits long.

Attempts have been made to cryptanalyze McEliece (when using Goppa codes as the underlying error-correcting code), but none have been successful. However, the algorithm is rarely used in practice because of the massive keys. One exceptional case that uses McEliece for encryption is the Freenet-like application Entropy (anonymous data store).

Scheme definition

McEliece consists of three algorithms: a probabilistic key generation algorithm which produces a public and a private key, a probabilistic encryption algorithm, and a deterministic decryption algorithm.

All users in a McEliece deployment share a set of common security parameters: $n,t,k$. Recommended values for these parameters are $n=1024,t=38,k=644$ (source: Handbook of Applied Cryptography).

Key generation

1. Users select a binary $(n,k)$-linear code $C$ capable of correcting $t$ errors. This code must possess an efficient decoding algorithm.
2. Alice generates a $k\times n$ generator matrix $G$ for the code $C$.
3. Select a random $k\times k$ binary non-singular matrix $S$.
4. Select a random $n\times n$ permutation matrix P.
5. Compute the $k\times n$ matrix ${\hat {G}}=SGP$.
6. Alice’s public key is $({\hat {G}},t)$; her private key is $(S,G,P)$.

Message encryption

Suppose Bob wishes to send a message m to Alice whose public key is $({\hat {G}},t)$:

1. Encode the message as a binary string of length $k$.
2. Compute the vector $c^{\prime }=m{\hat {G}}$.
3. Generate a random $n$-bit vector $z$ containing at most $t$ ones.
4. Compute the ciphertext as $c=c^{\prime }+z$.

Message decryption

1. Compute the inverse of $P$, $P^{-1}$.
2. Compute ${\hat {c}}=cP^{-1}$.
3. Use the decoding algorithm for the code $C$ to decode ${\hat {c}}$ to ${\hat {m}}$.
4. Compute $m={\hat {m}}S^{-1}$.

References

• Alfred J. Menezes, Scott A. Vanstone, A. J. Menezes and Paul C. van Oorschot, Handbook of Applied Cryptography.