McEliece cryptosystem

The McEliece encryption system is an asymmetric encryption algorithm. It was introduced in 1978 by cryptographers Robert J. McEliece.

  • 2.1 correctness
  • 2.2 Safety
  • 3.1 achieving IND - CPA security
  • 3.2 Reduction of the key size

Method

Generation of public and private key

The generation of the public and the private key works as follows.

  • One chooses a Goppa - code with generator matrix.
  • Furthermore, choose an invertible matrix and a permutation matrix.
  • One defines.

The public key is made, from the private.

The currently recommended parameter values ​​are for 2013, and for safety by the year 2050.

Encrypting messages

To encrypt a message, the procedure is as follows:

  • One chooses randomly with Hamming weight, ie. , Exactly coordinates of 1 and all others are 0
  • One calculates the ciphertext as.

Decrypt messages

To decrypt a ciphertext, the procedure is reasonably successor:

  • Man charged.
  • By means of the error-correcting properties of Goppa codes used to calculate further to the nearest codeword and the closest news word.
  • Ultimately, we can calculate the message.

Cryptographic Properties

Correctness

It is easy to see that messages are always correctly decrypted. After the first decoding step one has

Since a permutation is, still has Hamming weight, and therefore is obtained after the second decoding step:

Because the used Goppa code can accurately correct errors. Since is invertible, we get now:

As a correct decryption back.

Security

Learning of the parity with noise assumption and the assumption that is indistinguishable from random matrices, the method has the one-way property.

Variants of the method

Achieve IND - CPA security

2008, showed that a small change of the process leads to a IND - CPA secure encryption process. Instead of encrypting a message of length for the encryption to be only messages of length for a positive, eg be used. These are then extended with random messages to the length. When decrypting at the end of these positions are simply ignored.

Reduction of key size

In the original description of the method, the memory requirement is for about kB. For the recommended parameters, this results in key sizes between 253KB and 701KB, which is often considered in practice to be too large. Alternatively, one can bring the matrix by Gaussian elimination in the form, wherein the unit matrix of dimension indicated. The memory requirement for the public key drops to then, or for the given parameter to 72kB to 189KB.

For encryption is now used simply. For decryption, we used the parallel mitberechnete for normalization matrix, and multiplied before outputting the message yet from the right.

Swell

  • Asymmetric encryption algorithm
Hamming distance Ciphertext Indistinguishability Identity matrix Digital Object Identifier
560097
de