Public key and key exchange methods which use Diffie-Hellman, Elliptic Curve, RSA and El Gamal will be cracked by quantum computers. In order to overcome this we need new methods which are quantum robust. One of these methods is Learning With Errors (LWE). With RLWE we use the learning with errors (LWE) method but add polynomial rings over finite fields. If you want to understand LWE, click [here]. Let's say that Bob and Alice want to create a shared encryption key. In this case, Bob and Alice agree on shared values of \(A\), \(n\) and \(q\), and each of them generate error values (\(e\)) and secret values (\(s\)). They then calculate \(b\) based on \(A\), and their own values of \(e\) and \(s\). After this they exchange their values of \(b\) and calculate new values with the \(b\) values they have received and their own secret values. After this they will generate the same shared key.
Ring Learning With Errors for Key Exchange (RLWE-KEX) |
Outline
In this method we perform a similar method to the Diffie Hellman method, but use Ring Learning With Errors (RLWE). With RLWE we use the coefficients of polynomials and which can be added and multiplied within a finite field (\(\textbf{F}_q\)) [theory] and where all the coefficients will be less than \(q\). Initially Alice and Bob agree on a complexity value of \(n\), and which is the highest co-efficient power to be used. They then generate \(q\) which is \(2^n-1\). All the polynomial operations will then be conducted with a modulus of \(q\) and where the largest coefficient value will be \(q-1\). She then creates \(a_i(x)\) which is a set of polynomial values:
\(\textbf{A} = a_{n-1} x^{n-1} + ... + a_1 x + a_1 x^2 + a_0 \)
Next Alice will divide by \(\Phi (x)\), which is \(x^n+1\):
\(\textbf{A} = (a_{n-1} x^{n-1} + ... + a_1 x + a_1 x^2 + a_0) \div (x^n+1) \)
In Python this is achieved with:
xN_1 = [1] + [0] * (n-1) + [1] A = np.floor(p.polydiv(A,xN_1)[1])
Alice now generates an error polynomial (\(\textbf{e}\)) and a secret polynomial (\(\textbf{s}\)):
\(\textbf{e_A}= e_{n-1} x^{n-1} + ... e_2 x^2 + e_1 x + e_0\)
\(\textbf{s_A}= s_{n-1} x^{n-1} + ... s_2 x^2 + s_1 x + s_0\)
Alice now creates \(b_A\) which is a polynomial created from \(A\), \(\textbf{e_A}\) and \(\textbf{s_A}\):
\(\textbf{b_A} = A \times s_A + e_A\)
In coding this is defined as:
bA = p.polymul(A,sA)%q bA = np.floor(p.polydiv(sA,xN_1)[1]) bA = p.polyadd(bA,eA)%q
Bob now generates his own error polynomial \(e^{'}\) and a secret polynomial \(s^{'}\):
\(\textbf{e_B}= e^{'}_{n-1} x^{n-1} + ... e^{'}_2 x^2 + e^{'}_1 x + e^{'}_0\)
\(\textbf{s_B}= s^{'}_{n-1} x^{n-1} + ... s^{'}_2 x^2 + s^{'}_1 x + s^{'}_0\)
Alice shares \(\textbf{A}\) with Bob, and Bob now creates \(\textbf{b_B}\) which is a polynomial created from \(\textbf{A}\), \(\textbf{e_B}\) and \(\textbf{s_B}\):
\(\textbf{b_B} = \textbf{A} \times \textbf{s_B} + \textbf{e_B}\)
The code for this is:
sB = gen_poly(n,q) eB = gen_poly(n,q) bB = p.polymul(A,sB)%q bB = np.floor(p.polydiv(sB,xN_1)[1]) bB = p.polyadd(bB,eB)%q
Alice then takes Bob's value (\(\textbf{b_B}\)) and multiplies by \(\textbf{s_A}\) and divides by \(x^n + 1\):
\(\textbf{shared_A} = \textbf{b_B} \times \textbf{s_A} \div (x^n + 1)\)
Bob then takes Alice's value (\(\textbf{b_A}\)) and multiplies by \(\textbf{s_B}\) and divides by \(x^n + 1\):
\(\textbf{shared_B} = \textbf{b_A} \times \textbf{s_B} \div (x^n + 1)\)
In code this is:
sharedAlice = np.floor(p.polymul(sA,bB)%q) sharedAlice = np.floor(p.polydiv(sharedAlice,xN_1)[1])%q sharedBob = np.floor(p.polymul(sB,bA)%q) sharedBob = np.floor(p.polydiv(sharedBob,xN_1)[1])%q
We now extract the noise from the received values and create an array (\(u\)) with:
\(\text{if shared_A}_i < \frac{q}{4} \text{ then } u_i=0\)
\(\text{else if shared_A}_i< \frac{q}{2} \text{ then } u_i=1\)
\(\text{else if shared_A}_i< \frac{3q}{4} \text{ then } u_i=0\)
\(\text{else if shared_A}_i < q \text{ then } u_i=1\)
At the end of this, Bob and Alice will have the same shared value (and thus can create a shared key based on it).
For 128 bits of equivalent security, we use n = 512, q = 25,601, and \(\Phi (x)=x^{512} + 1\)
For 256 bits of equivalent security, we use n = 512, q = 40,961, and \(\Phi (x)=x^{1024} + 1\)
A sample run with \(n=10\), and \(q=2^{10}+1\) shows that Alice and Bob have the same shared secret (1110110111):
q value: 1023 (2^ 10 +1) n value: 10 (number of bits in polynomials) A: 10 | [339. 105. 145. 686. 331. 768. 292. 180. 340. 471.] -Alice--- s: 10 | [ 1. 0. 1. -1. -1. -2. 1. -1. 0. -2.] e: 10 | [ 1. 0. -1. -1. -1. 0. -2. 0. 1. -1.] b: 10 | [2.000e+00 0.000e+00 0.000e+00 1.021e+03 1.021e+03 1.021e+03 1.022e+03 1.022e+03 1.000e+00 1.020e+03] -Bob--- s': 10 | [-2. 0. 2. -2. -1. -2. 0. -1. -2. 0.] e': 10 | [ 0. 0. 0. -1. 1. -1. -2. -1. 0. 1.] b': 10 | [1.021e+03 0.000e+00 2.000e+00 1.020e+03 0.000e+00 1.020e+03 1.021e+03 1.021e+03 1.021e+03 1.000e+00] Before noise extraction: Shared Secret Alice: 10 | [1010. 1021. 1011. 1019. 0. 1012. 1017. 1015. 9. 3.] Before noise extraction: Shared Secret Bob: 10 | [1.008e+03 1.022e+03 1.014e+03 1.017e+03 1.016e+03 1.018e+03 1.000e+00 1.019e+03 2.000e+00 1.200e+01] u : 10 | [1 0 0 1 0 1 1 1 1 0] Shared Secret Alice: 10 | [1. 0. 0. 1. 0. 1. 1. 1. 1. 0.] Shared Secret Bob: 10 | [1. 0. 0. 1. 0. 1. 1. 1. 1. 0.]
Coding
The following is an outline (based on code [here]):
import numpy as np import sys from numpy.polynomial import polynomial as p n = 1024 qval = 32 q = 2**qval-1 xN_1 = [1] + [0] * (n-1) + [1] # (x^n + 1) def gen_poly(n,q): global xN_1 l = 0 #Gamma Distribution Location (Mean "center" of dist.) poly = np.floor(np.random.normal(l,size=(n))) while (len(poly) != n): poly = np.floor(np.random.normal(l,size=(n))) poly = np.floor(p.polydiv(poly,xN_1)[1]%q) return poly #Generate A A = np.floor(np.random.random(size=(n))*q)%q A = np.floor(p.polydiv(A,xN_1)[1]) #Alice (Secret & Error) sA = gen_poly(n,q) eA = gen_poly(n,q) bA = p.polymul(A,sA)%q bA = np.floor(p.polydiv(sA,xN_1)[1]) bA = p.polyadd(bA,eA)%q #Bob sB = gen_poly(n,q) eB = gen_poly(n,q) bB = p.polymul(A,sB)%q bB = np.floor(p.polydiv(sB,xN_1)[1]) bB = p.polyadd(bB,eB)%q #Shared Secret #Alice sharedAlice = np.floor(p.polymul(sA,bB)%q) sharedAlice = np.floor(p.polydiv(sharedAlice,xN_1)[1])%q #TODO FIX THIS HAS TO BE DIVED BY HELPER sharedBob = np.floor(p.polymul(sB,bA)%q) sharedBob = np.floor(p.polydiv(sharedBob,xN_1)[1])%q #Error Rounding #--Bob u = np.asarray([0] * n) i = 0 while (i < len(u)): if (len(bB) <= i): break; if (int(bB[i]/(q/4)) == 0): u[i] = 0 elif (int(bB[i]/(q/2)) == 0): u[i] = 1 elif (int(bB[i]/(3*q/4)) == 0): u[i] = 0 elif (int(bB[i]/(q)) == 0): u[i] = 1 else: print("error! (1)") i+=1 i = 0 while (i < len(u)): #Region 0 (0 --- q/4 and q/2 --- 3q/4) if (u[i] == 0): if (sharedBob[i] >= q*0.125 and sharedBob[i] < q*0.625): sharedBob[i] = 1 else: sharedBob[i] = 0 #Region 1 (q/4 --- q/2 and 3q/4 --- q) elif (u[i] == 1): if (sharedBob[i] >= q*0.875 and sharedBob[i] < q*0.375): sharedBob[i] = 0 else: sharedBob[i] = 1 else: print("error! (2)") i += 1 #--Alice i = 0 while (i < len(u)): #Region 0 (0 --- q/4 and q/2 --- 3q/4) if (u[i] == 0): if (sharedAlice[i] >= q*0.125 and sharedAlice[i] < q*0.625): sharedAlice[i] = 1 else: sharedAlice[i] = 0 #Region 1 (q/4 --- q/2 and 3q/4 --- q) elif (u[i] == 1): if (sharedAlice[i] >= q*0.875 and sharedAlice[i] < q*0.375): sharedAlice[i] = 0 else: sharedAlice[i] = 1 else: print("error! (3)") i += 1 # print("A:",len(A),"|",A) print("\n-Alice---") print(" s:",len(sA),"|",sA) print(" e:",len(eA),"|",eA) print(" b:",len(bA),"|",bA) print("\n-Bob---") print(" s':",len(sB),"|",sB) print(" e':",len(eB),"|",eB) print(" b':",len(bB),"|",bB) print(" u :",len(u),"|",u) print("\n") print("Shared Secret Alice:",len(sharedAlice),"|",sharedAlice) print("Shared Secret Bob:",len(sharedBob),"|",sharedBob) print("\n\n--Verification--") i = 0 while (i < len(sharedBob)): if (sharedAlice[i] != sharedBob[i]): print("Error at index",i) i+=1
A fun article on this is [here]