Editing McEliece cryptosystem (section)

== Scheme definition ==
McEliece consists of three algorithms: a probabilistic key generation algorithm that 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: <math>n, k, t</math>.

=== Key generation ===

The principle is that Alice chooses a linear code <math>C</math> from some family of codes for which she knows an efficient decoding algorithm, and to make <math>C</math> public knowledge but keep the decoding algorithm secret. Such a decoding algorithm requires not just knowing <math>C</math>, in the sense of knowing an arbitrary generator matrix, but requires one to know the parameters used when specifying <math>C</math> in the chosen family of codes. For instance, for binary Goppa codes, this information would be the Goppa polynomial and the code locators. Therefore, Alice may publish a suitably obfuscated generator matrix of <math>C</math>.

More specifically, the steps are as follows:
# Alice selects a binary <math>(n, k)</math>-linear code <math>C</math> capable of (efficiently) correcting <math>t</math> errors from some large family of codes, e.g. binary Goppa codes. This choice should give rise to an efficient decoding algorithm <math>A</math>. Let also <math>G</math> be any generator matrix for <math>C</math>. Any linear code has many generator matrices, but often there is a natural choice for this family of codes. Knowing this would reveal <math>A</math> so it should be kept secret.
# Alice selects a random <math>k \times k</math> binary [[Invertible matrix|non-singular matrix]] <math>S</math>.
# Alice selects a random <math>n \times n</math> [[permutation matrix]] <math>P</math>.
# Alice computes the <math>k \times n</math> matrix <math>{\hat G} = SGP</math>.
# Alice's public key is <math>({\hat G}, t)</math>; her private key is <math>(S, P, A)</math>. Note that <math>A</math> could be encoded and stored as the parameters used for selecting <math>C</math>.

=== Message encryption ===

Suppose Bob wishes to send a message ''m'' to Alice whose public key is <math>({\hat G}, t)</math>:
# Bob encodes the message <math>m</math> as a binary string of length <math>k</math>.
# Bob computes the vector <math>c^{\prime} = m{\hat G}</math>.
# Bob generates a random <math>n</math>-bit vector <math>z</math> containing exactly <math>t</math> ones (a vector of length <math>n</math> and weight <math>t</math>)<ref name="McEliece"/>
# Bob sends Alice the ciphertext computed as <math>c = c^{\prime} + z</math>.

=== Message decryption ===
Upon receipt of <math>c</math>, Alice performs the following steps to decrypt the message:
# Alice computes the inverse of <math>P</math> (i.e. <math>P^{-1}</math>).
# Alice computes <math>{\hat c} = cP^{-1}</math>.
# Alice uses the decoding algorithm <math>A</math> to decode <math>{\hat c}</math> to <math>{\hat m}</math>.
# Alice computes <math>m = {\hat m}S^{-1}</math>.