# McEliece public-key encryption

The McEliece public-key encryption scheme is based on error-correcting codes. The idea behind this scheme is to first select a particular code for which an efficient decoding algorithm is known, and then to disguise the code as a general linear code (see Note 12.36). Since the problem of decoding an arbitrary linear code is NP-hard (Definition 2.73), a description of the original code can serve as the private key, while a description of the transformed code serves as the public key.

The McEliece encryption scheme (when used with Goppa codes) has resisted cryptanalysis to date. It is also notable as being the first public-key encryption scheme to use randomization in the encryption process. Although very efficient, the McEliece encryption scheme has received little attention in practice because of the very large public keys (see Remark 8.33).

8.29 Algorithm Key generation for McEliece public-key encryption

8.30 Algorithm McEliece public-key encryption

SUMMARY: В encrypts a message m for A, which A decrypts.

• 1. Encryption. В should do the following:
• (a) Obtain A’s authentic public key (G, t).
• (b) Represent the message as a binary string m of length k.
• (c) Choose a random binary error vector 2 of length n having at most t 1 ’s.
• (d) Compute the binary vector c = mG + z.
• (e) Send the ciphertext c to A.
• 2. Decryption. To recover plaintext m from c, A should do the following:
• (a) Compute c = cP~*  , where P  is the inverse of the matrix P.
• (b) Use the decoding algorithm for the code generated by G to decode c to m.
• (c) Compute m = mS~
• 3

•  Proof that decryption works. Since and zP~2 is a vector with at most t l’s, the decoding algorithm for the code generated byG corrects c to m = mS. Finally, mS~l = m, and, hence, decryption works. A special type of error-correcting code, called a Goppa code, may be used in step 3 ofthe key generation. For each irreducible polynomial g(x) of degree t over F2„,, there existsa binary Goppa code of length n = 2m and dimension к >n — mt capable of correctingany pattern of t or fewer errors. Furthermore, efficient decoding algorithms are known forsuch codes. 8.31 Note (security ofMcEliece encryption) There are two basic kinds of attacks known.
•  From the public information, an adversary may try to compute the key G or a key G'for a Goppa code equivalent to the one with generator matrix G. There is no efficientmethod known for accomplishing this. (ii) An adversary may try to recover the plaintext m directly given some ciphertext c. Theadversary picks к columns at random from G. If Gfc, c*. and zk denote the restrictionof G, c and г, respectively, to these к columns, then {ck + zk) = mGk. If zr = 0 andif Gk is non-singular, then m can be recovered by solving the system of equationscfc = mGk• Since the probability that zk = 0, i.e., the selected к bits were not inerror, is only ("J*) /(£), the probability of this attack succeeding is negligibly small. 8.32 Note (recommended parameter sizes) The original parameters suggested by McEliecewere n = 1024, t = 50, and к > 524. Based on the security analysis (Note 8.31), anoptimum choice of parameters for the Goppa code which maximizes the adversary’s workfactor appears to be n = 1024, t = 38, and к > 644. 8.33 Remark (McEliece encryption in practice) Although the encryption and decryption operations are relatively fast, the McEliece scheme suffers from the drawback that the publickey is very large. A (less significant) drawback is that there is message expansion by a factor of 11/k. For the recommended parameters n = 1024, t = 38, к > 644, the public key isabout 219 bits in size, while the message expansion factor is about 1.6. For these reasons,the scheme receives little attention in practice.
•  From the public information, an adversary may try to compute the key G or a key G'for a Goppa code equivalent to the one with generator matrix G. There is no efficientmethod known for accomplishing this. (ii) An adversary may try to recover the plaintext m directly given some ciphertext c. Theadversary picks к columns at random from G. If Gfc, c*. and zk denote the restrictionof G, c and г, respectively, to these к columns, then {ck + zk) = mGk. If zr = 0 andif Gk is non-singular, then m can be recovered by solving the system of equationscfc = mGk• Since the probability that zk = 0, i.e., the selected к bits were not inerror, is only ("J*) /(£), the probability of this attack succeeding is negligibly small. 8.32 Note (recommended parameter sizes) The original parameters suggested by McEliecewere n = 1024, t = 50, and к > 524. Based on the security analysis (Note 8.31), anoptimum choice of parameters for the Goppa code which maximizes the adversary’s workfactor appears to be n = 1024, t = 38, and к > 644. 8.33 Remark (McEliece encryption in practice) Although the encryption and decryption operations are relatively fast, the McEliece scheme suffers from the drawback that the publickey is very large. A (less significant) drawback is that there is message expansion by a factor of 11/k. For the recommended parameters n = 1024, t = 38, к > 644, the public key isabout 219 bits in size, while the message expansion factor is about 1.6. For these reasons,the scheme receives little attention in practice.
•  From the public information, an adversary may try to compute the key G or a key G'for a Goppa code equivalent to the one with generator matrix G. There is no efficientmethod known for accomplishing this. (ii) An adversary may try to recover the plaintext m directly given some ciphertext c. Theadversary picks к columns at random from G. If Gfc, c*. and zk denote the restrictionof G, c and г, respectively, to these к columns, then {ck + zk) = mGk. If zr = 0 andif Gk is non-singular, then m can be recovered by solving the system of equationscfc = mGk• Since the probability that zk = 0, i.e., the selected к bits were not inerror, is only ("J*) /(£), the probability of this attack succeeding is negligibly small. 8.32 Note (recommended parameter sizes) The original parameters suggested by McEliecewere n = 1024, t = 50, and к > 524. Based on the security analysis (Note 8.31), anoptimum choice of parameters for the Goppa code which maximizes the adversary’s workfactor appears to be n = 1024, t = 38, and к > 644. 8.33 Remark (McEliece encryption in practice) Although the encryption and decryption operations are relatively fast, the McEliece scheme suffers from the drawback that the publickey is very large. A (less significant) drawback is that there is message expansion by a factor of 11/k. For the recommended parameters n = 1024, t = 38, к > 644, the public key isabout 219 bits in size, while the message expansion factor is about 1.6. For these reasons,the scheme receives little attention in practice.