McEliece cryptosystem

The McEliece cryptosystem is an asymmetric encryption algorithm . It was introduced in 1978 by the cryptographer Robert J. McEliece . The method is rarely used in practice because the keys are large matrices; the description of a key with a security level of 128 bits requires on the order of 1 MB, over a thousand times more than comparable RSA keys. However, even using quantum computers, no efficient algorithm is known that can break the McEliece cryptosystem, making it a promising candidate for post-quantum cryptography .

Procedure

Generation of the public and private key

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

• You choose a - Goppa code with generator matrix . ${\displaystyle (n,k,t)}$ ${\displaystyle G}$
• An invertible matrix and a permutation matrix are also chosen . ${\displaystyle S\in \{0,1\}^{k\times k}}$ ${\displaystyle P\in \{0,1\}^{n\times n}}$
• One defines . ${\displaystyle {\hat {G}}=SGP}$

The public key consists of , the private one . ${\displaystyle {\hat {G}}}$ ${\displaystyle (S,G,P)}$

Encrypt messages

To encrypt a message , proceed as follows: ${\displaystyle m\in \{0,1\}^{k}}$

• One randomly chooses with Hamming weight , i. i.e., the exact coordinates of are 1 and all others are 0. ${\displaystyle z\in \{0,1\}^{n}}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle z}$
• The key text is calculated as . ${\displaystyle c=m{\hat {G}}+z}$

Decrypt messages

To decipher a ciphertext, proceed as follows: ${\displaystyle c}$

• One calculates . ${\displaystyle c'=cP^{-1}}$
• The error-correcting properties of the Goppa code used are used to further calculate the closest code word and the closest message word . ${\displaystyle c'}$ ${\displaystyle c''}$ ${\displaystyle c'''}$
• Ultimately, the message is calculated as . ${\displaystyle m}$ ${\displaystyle m=c'''S^{-1}}$

Cryptographic properties

correctness

It's easy to see that messages are always being decrypted correctly. After the first decryption step you have

${\displaystyle c'=cP^{-1}=(m{\hat {G}}+z)P^{-1}=mSG+zP^{-1}}$.

Since is a permutation, still has Hamming weight , and therefore after the second decryption step one gets: ${\displaystyle P}$ ${\displaystyle zP^{-1}}$ ${\displaystyle t}$

${\displaystyle c''=mSG}$, as well as , ${\displaystyle c'''=mS}$

because the Goppa code used can correct up to errors. Since is invertible, we now get: ${\displaystyle t}$ ${\displaystyle S}$

${\displaystyle c'''S^{-1}=m}$

as correct decryption back.

safety

Under the learning parity with noise assumption and the assumption that is indistinguishable from random matrices, the method has the one- way property . ${\displaystyle {\hat {G}}}$ ${\displaystyle k\times n}$

Variants of the procedure

Achieving IND-CPA security

In 2008 it was shown that a small change in the procedure leads to an IND-CPA -secure encryption procedure. Instead of encrypting a message of length during encryption, only messages of length for a positive , e.g. B. used. These are then messages the length randomly extended . In the end, these positions are simply ignored during decryption. ${\displaystyle k}$ ${\displaystyle \beta k}$ ${\displaystyle \beta <1}$ ${\displaystyle \beta ={\frac {9}{10}}}$ ${\displaystyle k}$

Reduction in key size

In the original description of the method, the memory requirement is about kB. For the recommended parameters, this results in key sizes between 253 kB and 701 kB, which in practice is often viewed as too large. Alternatively, one can the matrix by Gaussian elimination in the form bring, wherein the unit matrix of dimension referred to. The storage requirement for the public key is then reduced to , or for the given parameters to 72 kB to 189 kB. ${\displaystyle {\hat {G}}}$ ${\displaystyle {\frac {kn}{8\cdot 1024}}}$ ${\displaystyle {\hat {G}}}$ ${\displaystyle {\tilde {G}}=(E_{k}|{\hat {G}}')}$ ${\displaystyle E_{k}}$ ${\displaystyle k}$ ${\displaystyle {\frac {k(n-k)}{8\cdot 1024}}}$

For encryption is now simply used. For decryption using the mitberechnete parallel to the normalization matrix with , and multiplied with even right before the output of the message . ${\displaystyle {\tilde {G}}}$ ${\displaystyle N}$ ${\displaystyle {\hat {G}}=N{\tilde {G}}}$ ${\displaystyle N}$

swell

1. ^ Robert J. McEliece : A Public-Key Cryptosystem Based on Algebraic Coding Theory . In: Deep Space Network Progress Report . tape 42 , no. 44 , 1978, pp. 114–116 ( pdf, 246kB ).
2. ↑ Ryo Nojima, Hideki Imai, Kazukuni Kobara, Kirill Morozov: Semantic Security for the McEliece Cryptosystem without Random Oracles . In: Designs, Codes and Cryptography . tape 49 , no. 1-3 . Springer, 2008, p. 289–305 , doi : 10.1007 / s10623-008-9175-9 ( pdf, 236kB ).