Classic McEliece

Classic McEliece is a code-based NIST standardization candidate still being considered, and may become a standard after the currently ongoing ISO standardization process is concluded.

The McEliece cryptosystem¹ (textbook)

Let \(\Gamma\) be an \(\lbrack n,k,2t+1\rbrack _2\) binary Goppa code with an efficient \(t\)-error decoding algorithm, where \(t\approx (n − k)/ \log2(n)\).

Public parameters are:

• \(n\), the code length;
• \(k\), the code dimension;
• \(t\), and hence the minimum distance \(2t+1\).

The private key is:

• \(\Gamma\) and a \(k\times n\) generator matrix \(G\);
• an \(n\times n\) permutation matrix \(P\);
• a non-singular \(k\times k\) matrix \(S\).

The public key is:

• \(G'=SGP\)

Encrypt(\(m,G'\)):

\[c=mG'+e\]

Decrypt\((c,P,S,\Gamma)\):

\[ \begin{align*} cP^{-1} &= mG'P^{-1} + eP^{-1} \\ &= (mS)G + eP^{-1} \end{align*} \]

The decoding algorithm will return \(mS\), and hence recover \(m\).

The Niederreiter cryptosystem² (textbook)

The Niederreiter proposal is a version of the McEliece proposal based on syndrome decoding, with the following differences:

• substitute the \(k\times n\) generator matrix \(G\) for a \((n-k)\times (n-k)\) parity check matrix \(H\);
• adjust the size of \(S\) accordingly, from \(k\times k\) to \((n-k)\times (n-k)\);
• the public key is a version of the parity check matrix, \(H'=SHP\);
• for plaintexts \(m\) of weight \(t\) and length \(n\), akin to errors, ciphertexts are syndromes \(c=H'm;\)
• decryption is to find \(m\) such that \(w(m)=t\) and \(c=H'm\).

References