McEliece cryptosystem

From Wikipedia, the free encyclopedia

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

The algorithm uses Goppa codes, which are a type of error-correcting code (see coding theory). The algorithm disguises a Goppa code made from the plaintext as a general linear code. Goppa codes are easy to decode, but distinguishing them from a general linear code is hard. This is McEliece's hard problem.

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, 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).

1 Scheme definition
2 References
3 External links

[edit] 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).

[edit] Key generation

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

[edit] Message encryption

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

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

[edit] Message decryption

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