Nearly Forgotten About For Four Decades, But Has It’s Time Has Come To Move Us Into A Trusted Quantum Etra?
When I was a student studying communication engineering, I was completely enchanted with the magic of error-correcting codes (ECCs). With Reed-Solomon, we could build a coding system where we could have errors in our data and then not only know there are errors (“error detection”) but actually find and correct them. A variation of this became the classic Shamir secure split method.
Mceliece’s public key encryption method was published in 1978, but RSA had a much smaller public key, and so it has been dismissed for over four decades. It’s time has now come, and whereas RSA is non-quantum robust, Mceliece’s method is.
So, let’s look at a simple example of the McEliece method using Hamming codes (and which I learnt about as an undergraduate student).
McEliece with Hamming codes
With (7,4) Hamming code we take 4 bits of data and add 3 Hamming bits to give 7 bits for each 4-bit value. We create a code generator matrix G and the parity-check matrix H. The input data is multiplied by G, and then to check the result is multiplied by H:
If we have a data input of [1 0 1 0] then to create the message to send we get:
The bits transmitted will thus be “1 0 1 1 0 1 0”.
which identifies there are no errors. For a data input of “1010”, we get the following:
Input Coded (1 error) Error Position
[1 0 1 0] [1 0 1 1 0 1 0] [0 0 0]
----------------------
Single Errors:
Input Coded (1 error) Error Position
[1 0 1 0] [0 0 1 1 0 1 0] [1 0 0]
[1 0 1 0] [1 1 1 1 0 1 0] [0 1 0]
[1 0 1 0] [1 0 0 1 0 1 0] [0 0 1]
[1 0 1 0] [1 0 1 0 0 1 0] [0 1 1]
[1 0 1 0] [1 0 1 1 1 1 0] [1 0 1]
[1 0 1 0] [1 0 1 1 0 0 0] [1 1 0]
[1 0 1 0] [1 0 1 1 0 1 1] [1 1 1]It can be seen that the data is “1010” and after the Hamming bits are added the result is “1011010”. If there are no errors the result is “000”, which means there are no errors.
If we add an error of the first coded bit we get a received value of “0 0 1 1 0 1 0”. The result is then “100” which identifies that Bit 0 is in error. If we look at an error in the next bit, we get a value of “010” which identifies that position is in error, and so each result correctly identifies the error, and we can thus correct it (for single-bit errors). And now we will use this method to perform our encryption.
McEliece with Hamming codes
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 1
G = 0 1 0 0 0 1 1
0 0 1 0 1 0 1
0 0 0 1 1 1 0Bob then selected a scrambler matrix (S):
1 1 0 1
S = 1 0 0 1
0 1 1 1
1 1 0 0And 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 0Bob public key then becomes the dot product of these matrices
1 1 0 1 0 1 0
G' = SGP = 1 1 0 0 1 0 0
1 0 0 1 0 0 1
0 1 1 1 0 0 0Bob 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 ones 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′
At this stage, we will use our H matrix to determine the syndrome, and identify where the error is. As the position of the error would have changed because of the permutation matrix, we need to remap the position of the error.
A sample run is [here]:
Message:
[1. 0. 1. 1.]
G:
[[1 0 0 0 1 1 1]
[0 1 0 0 0 1 1]
[0 0 1 0 1 0 1]
[0 0 0 1 1 1 0]]
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 (GSP):
[[1 1 0 1 0 1 0]
[1 1 0 0 1 0 0]
[1 0 0 1 0 0 1]
[0 1 1 1 0 0 0]]
Cipher: [0. 0. 1. 1. 1. 1. 1.]
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.]]
syndrome': [1. 1. 0.] 3.0
Error position: 5
y': [0. 1. 1. 0. 1. 1. 1.]
y' (corrected): [0. 1. 1. 0. 0. 1. 1.]
S^{-1}:
[[1. 1. 0. 1.]
[1. 1. 0. 0.]
[0. 1. 1. 1.]
[1. 0. 0. 1.]]
Decipher: [1. 0. 1. 1.]Coding
The following is an outline [here]:
import numpy
import sys
import io
g =numpy.array([[1,0,0,0,1,1,1],[0,1,0,0,0,1,1],[0,0,1,0,1,0,1],[0,0,0,1,1,1,0]])
h=numpy.array([[1,0,0,0,1,1,1],[0,1,0,1,0,1,1],[0,0,1,1,1,0,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]])
mapping=([4,1,5,2,7,6,3])
matrix = numpy.dot(s,g)%2
G_1 = numpy.dot(matrix,p)%2
message = ([1,1,0,0])
e = ([0,0,0,0,1,0,0])
if (len(sys.argv)>1):
message=numpy.genfromtxt(io.StringIO(sys.argv[1]),delimiter=',')
print('Message:\n',message)
print('G:\n',g)
print('S:\n',s)
print('P:\n',p)
print('Result (GSP):\n',G_1)
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
syndrome = numpy.dot(h,numpy.transpose(cipher))%2
error = syndrome[0]+2*syndrome[1]+4*syndrome[2]
print("\nsyndrome\':",syndrome,error)
error=mapping[int(error-1)]
print ("Error position: ",error)
print ("y': ",y_1)
y_1[error-1]=(y_1[error-1]+1)%2
print ("y' (corrected): ",y_1)
s_1=numpy.linalg.inv(s)%2
print ('\nS^{-1}:\n',s_1)
# syn = ([1,0,0,0])
decipher = numpy.dot(y_1[0:4],s_1)%2
print ('\nDecipher:',decipher)Conclusions
It’s goodbye to RSA and ECC, and hello (possibly) to public key methods based on coding theory.
