Robert J. McEliece, RIP: Who Laid Down The Foundations Of A Quantum Robust Future

We live in a world that is dominated by large (and faceless) corporation, but it is individuals who have really build our information…

Robert J. McEliece, RIP: Who Laid Down The Foundations Of A Quantum Robust Future

We live in a world that is dominated by large (and faceless) corporations, but it is individuals who have often built our information world. One of those was Robert J. McEliece, and who passed away in May 2019 at the age of 76. While working on a range of space-related projects, he contributed in many areas including with information transmission and storage. Robert eventually was awarded the Claude E. Shannon Award for his work, and gave many memorable talks:

and:

His best know work is around error-correcting codes, including within convolution codes, and now his work is causing great attention in creating an encryption system that would be robust against a quantum computer.

His work

Many of our public key methods are based on discrete logarithms and which build on the theories created by John Napier. Bitcoin, Tor, smart cards, Wif-fi, and many other applications use discrete logarithms. But these methods, and other public-key methods, are at risk from quantum computers. One contender is the McEliece Cryptography method.

In a lesson for any modern researcher, in just two pages, Robert McEliece, in 1978, outlined a public key encryption method based on Algebraic Coding — now known as the McEliece Cryptography method [paper]. It is an asymmetric encryption method (with a public key and a private key), and, at the time, looked to be a serious contender for a trapdoor method. Unfortunately, RSA became the King of the Hill, and the McEliece method was pushed to the end of the queue for designers.

It has basically drifted for nearly 40 years. But, as an era of quantum computers is dawning, it is now being reconsidered, as it is seen to be immune to attacks using Shor’s algorithm [here].

NIST has now started to move on quantum robust methods with a paper outlining the requirement for new cryptography methods, as a large-scale quantum computer will break most of the currently available public-key systems, including RSA and discrete logarithm methods. Overall public key encryption is most often used to protect secret keys used in symmetric encryption, and to prove identity. A large-scale breach of a public key would lead to a complete lack of trust on the Internet for the hacked entity.

The main contenders for quantum robust methods are:

  • Lattice-based cryptography — This classification shows great potential and is leading to new cryptography, such as for fully homomorphic encryption [here] and code obfuscation. An example is given in the following section.
  • Code-based cryptography — This method was created in 1978 with the McEliece cryptosystem but has barely been using in real applications. The McEliece method uses linear codes that are used in error correcting codes, and involves matrix-vector multiplication. An example of a linear code is Hamming code [here]
  • Multivariate polynomial cryptography — These focus on the difficulty of solving systems of multivariate polynomials over finite fields. Unfortunately, many of the methods that have been proposed have already been broken.
  • Hash-based signatures — This would involve creating digital signatures using hashing methods. The drawback is that a signer needs to keep a track of all of the messages that have been signed and that there is a limit to the number of signatures that can be produced.

The McEliece method

The McEliece method uses code-based cryptography. Its foundation is based on the difficulty in decoding a general linear code and is generally faster than RSA for encryption and decryption. Within it, we have a probabilistic key generation method, which is then used to produce the public and the private key. The keys are generated with the parameters of n, k and T.

The keys are generated with the parameters of n, k and t. With this, we create an [n,k] matrix of codes, and which is able to correct t errors. In his paper, McEliece defines defines n=1024, k=524, t=50, and which gives a public key size of 524x(1024–524) = 262,000 bits. In the example above we use k=1608, N=2048 and T=40, which gives a public key size of 1608x(2048–40) — 3,228,864 bits. For quantum robustness it is recommended that N is 6960, k is 5,412 and t is 119 (giving a large key size of 8,373,911 bits.

Here is a demo of the encryption [here].

Example

This page provides a simple explanation of how the key is created for McEliece crypto. It uses a (7,4) Hamming code with one-bit error correction. The following is an outline [here]:

import numpy
import sys
g =numpy.array([[1,0,0,0,1,1,0],[0,1,0,0,1,0,1],[0,0,1,0,0,1,1 ],[0,0,0,1,1,1,1]])
s =numpy.array([[1,1,0,1],[1,0,0,1],[0,1,1,1],[1,1,0,0]])
p=numpy.array([[0,1,0,0,0,0,0],[0,0,0,1,0,0,0],[0,0,0,0,0,0,1],[1,0,0,0,0,0,0],[0,0,1,0,0,0,0],[0,0,0,0,0,1,0],[0,0,0,0,1,0,0]])
print 'G:\n',g
print 'S:\n',s
print 'P:\n',p
matrix = numpy.dot(s,g)%2
G_1 = numpy.dot(matrix,p)%2
print 'Result:\n',G_1
message = ([1,1,0,1])
e = ([0,0,0,0,1,0,0])
res=numpy.dot(message,G_1)%2
cipher = numpy.add(res,e)%2
print '\nCipher:',cipher
p_1=numpy.linalg.inv(p)%2
print '\nP^{-1}:\n',p_1
y_1 = numpy.dot(cipher,p_1)%2
print "\ny\':",y_1

This is based on the example [here]. We illustrate the process with a (7,4) Hamming code which corrects one error. The generator matrix is then:

1  0  0  0  1  1  0
         G = 0  1  0  0  1  0  1
             0  0  1  0  0  1  1
             0  0  0  1  1  1  1

Bob then selects a scrambler matrix (S):

1  1  0  1
          S = 1  0  0  1
              0  1  1  1
              1  1  0  0

And also a permutation matrix:

0  1  0  0  0  0  0 
              0  0  0  1  0  0  0
              0  0  0  0  0  0  1
         P =  1  0  0  0  0  0  0
              0  0  1  0  0  0  0
              0  0  0  0  0  1  0
              0  0  0  0  1  0  0

Bob public key then becomes the dot product of these matrices

1  1  1  1  0  0  0
     G' = SGP   = 1  1  0  0  1  0  0
                  1  0  0  1  1  0  1
                  0  1  0  1  1  1  0

Bob will use G’ as a public key, but S, G and P are secret. Next, for Alice to send a ciphered message to Bob, she converts the message into binary vectors of length k.

For a message of m Alice will create randomly a binary n-vector of weight t, and randomly places t 1’s in a zero vector of length n).

This is then sent to Bob:

y = mG’ + e

Bob then decrypts with:

yP−1=(mG′+e)P−1=mSG+eP−1=mSG+e′

A sample run is:

Message: [ 1.  1.  0.  1.]
G:
[[1 0 0 0 1 1 0]
 [0 1 0 0 1 0 1]
 [0 0 1 0 0 1 1]
 [0 0 0 1 1 1 1]]
S:
[[1 1 0 1]
 [1 0 0 1]
 [0 1 1 1]
 [1 1 0 0]]
P:
[[0 1 0 0 0 0 0]
 [0 0 0 1 0 0 0]
 [0 0 0 0 0 0 1]
 [1 0 0 0 0 0 0]
 [0 0 1 0 0 0 0]
 [0 0 0 0 0 1 0]
 [0 0 0 0 1 0 0]]
Result:
[[1 1 1 1 0 0 0]
 [1 1 0 0 1 0 0]
 [1 0 0 1 1 0 1]
 [0 1 0 1 1 1 0]]
Cipher: [ 0.  1.  1.  0.  1.  1.  0.]
P^{-1}:
[[ 0.  0.  0.  1.  0.  0.  0.]
 [ 1.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  1.  0.  0.]
 [ 0.  1.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  1.]
 [ 0.  0.  0.  0.  0.  1.  0.]
 [ 0.  0.  1.  0.  0.  0.  0.]]
y': [ 1.  0.  0.  0.  1.  1.  1.]
S^{-1}:
[[ 1.  1.  0.  1.]
 [ 1.  1.  0.  0.]
 [-0.  1.  1.  1.]
 [ 1.  0.  0.  1.]]
Decipher: [ 1.  1.  0.  1.]

Conclusions

We need to consider new ways of defining hard problems in an era of quantum computers. Using algebraic codes to create quantum robust crypto is now a serious contender to replace some of your public key methods.

So it could be goodbye John Napier — and discrete logarithms — and goodbye to Robert McEliece. Both have left a long legacy in building a more trusted world.