Eve The Magician Does A Quantum Robust Trick — Learning With Errors
Eve The Magician Does A Quantum Robust Trick — Learning With Errors
Eve takes to the stage for another cyber magic show.
“As we have seen, you can forget your prime number factorisation”,
she says,
“that’s not going to need any magic once quantum computers come along!”.
There’s great laughter in the audience, apart from Mallory who just doesn’t get it. As always he has a strange smirk on his face.
“Today, I’m going to show you a bit of magic that will make smoke come out of a quantum computer.”
The lights dim, and Eve looks to the audience and locates Bob.
“Now Bob please come to the stage”,
says Eve.
“Please give our hero — Bob — a huge round of applause”.
“Now Bob. Think of ten numbers, and two other special ones. Only tell me the first of the two special numbers”,
she says.
Bob selects, “5, 8, 12, 16, 2, 6, 10, 3, 8, 10”, and “5 and 12” for the other numbers. He announces “5” for the special number.
“Let’s call the first special number Trent, and the other one Alice”.
Trent nods with approval of his name being mentioned.
“Now”, says Eve, “Take each number and multiply it by Trent and then add Alice. But, don’t tell me the result!”.
So Bob calculates “37,52,72,92,22,42,62,27,62”.
“Now, Alice please come to the stage”,
says Eve.
“Can you select any five numbers from Bob, but don’t tell me them?”
says Eve.
Alice selects “37,92,42,62,27”.
“Now. Alice. I want you to select a colour, either “Black” or “White”. If you select “Black” take the total of your values, otherwise if it is “White” take the total and add 1",
says Eve.
So Alice picks her colour, and calculates the values. She then says that the result is “260”.
The lights dim, and quick as a flash Eve says,
“Is the colour …”.
She stops, and opens up her hand and a black dove flies out …
“Oooo-oo”, comes from the audience as the black dove flies over the heads.
“Alice” says Eve, “Is the colour of the dove, the colour you selected?”
“Yes!!”, screams Alice.
“Now that is quantum crypto!”,
Eve turns to the camera and winks. Six men dressed in black suits talk into the sleeves and touch their ears, and leave the building.
How did she do it?
This is a method defined by Oded Regev in 2005, and is known as LWE (Learning With Errors). It involves the difficulty of finding the values which solve:
t =g x s + e
where you know t and g. The value of s becomes the secret value (or the secret key), and t and g can become the public key.
For Eve all she had to do what divide by the special number, and if the remainder was positive the message was “0”, else if it was odd, the message was “1”. Within Ring-LWE, which is the new crypto method implemented by Google, we use a set of numbers, known as polynomials for our values of t, g, s and e.
Here is a simple calculator [here]:
C:\Python27> python lwe.py
Public key [37, 52, 72, 92, 22, 42, 67, 27, 47, 62]
Selected values [22, 72, 42, 37, 47]
Message to send: 0
Sum is: 220
Encrypted is: 220
Message is 0
C:\Python27>python lwe.py
Public key [37, 52, 72, 92, 22, 42, 67, 27, 47, 62]
Selected values [22, 62, 67, 52, 37]
Message to send: 0
Sum is: 240
Encrypted is: 240
Message is 0
C:\Python27>python lwe.py
Public key [37, 52, 72, 92, 22, 42, 67, 27, 47, 62]
Selected values [92, 62, 22, 72, 67]
Message to send: 1
Sum is: 315
Encrypted is: 316
Message received is 1
C:\Python27> python lwe.py
Public key [37, 52, 72, 92, 22, 42, 67, 27, 47, 62]
Selected values [42, 47, 37, 22, 62]
Message to send: 1
Sum is: 210
Encrypted is: 211
Message received is 1
The Python code is:
import sys
import numpy as np
import random
public_key=[]
vals = [5, 8, 12, 16, 2, 6, 11, 3, 7, 10]
s = 5
e = 12
message = 1
file='1111'
val=0
for x in range(0,len(vals)):
public_key.append(vals[x]*s+e)
res = random.sample(public_key, 5)
print "Public key",public_key
print "Selected values",res
sum = np.sum(res)
print "Message to send:",message
print 'Sum is:',sum
if (message==1):
sum=sum+1
print 'Encrypted is:',sum
rem = sum % s
if (rem%2==0):
print 'Message received is 0'
else:
print 'Message received is 1'