Learning With Errors (LWE) is a quantum robust method of cryptography. Initially we create a secret key value (s) and another value (e). Next we select a number of values (A[]) and calculate B[] = A[] x s + e. The values of A[] and B[] become our public key. If s is a single value, A and B are one dimensional matrices. If we select s to be a one-dimensional matrix, A will be a two-dimensional matrix, and B will be a one-dimensional matrix.
Learning With Errors (LWE) and Ring LWEOutlineLearning with errors is a method defined by Oded Regev in 2005 [here] and is known as LWE (Learning With Errors). It involves the difficulty of finding the values which solve: \(\textbf{B} = \textbf{A} \times \textbf{s} + \textbf{e}\) where you know \(\textbf{A}\) and \(\textbf{B}\). The value of \(\textbf{s}\) becomes the secret values (or the secret key), and \(\textbf{A}\) and \(\textbf{B}\) can become the public key. Slides: [here] Basics for LWEIn this presentation we will use the examples defined here. The following code implements a basic LWE method: import numpy as np import sys q=13 A=np.array([[4 ,1, 11, 10],[5, 5 ,9 ,5],[3, 9 ,0 ,10],[1, 3 ,3 ,2],[12, 7 ,3 ,4],[6, 5 ,11 ,4],[3, 3, 5, 0]]) sA = np.array([[6],[9],[11],[11]]) eA = np.array([[0],[-1],[1],[1],[1],[0],[-1]]) bA = np.matmul(A,sA)%q print (bA) bA = np.add(bA,eA)%q print print ("Print output\n",bA) \(b_A = \begin{bmatrix} 4 & 1 & 11 & 10 \\ 5 & 5 & 9 & 5 \\ 3 & 9 & 0 & 10 \\ 1 & 3 & 3 & 2 \\ 12 & 7 & 3 & 4 \\ 6 & 5 & 11 & 4 \\ 3 & 3 & 5 & 0 \end{bmatrix} \times \begin{bmatrix} 6 \\ 9 \\ 11 \\ 11 \end{bmatrix} + \begin{bmatrix} 0 \\ -1 \\ 1 \\ 1 \\ 1 \\ 0 \\ -1 \end{bmatrix} \pmod{13} = \begin{bmatrix} 4 \\ 7 \\ 2 \\ 11 \\ 5 \\ 12 \\ 8 \end{bmatrix} \) Ring LWEIn this presentation we will use the examples defined here. The following code implements a basic Ring LWE method: import numpy as np A = [4,1,11,10] sA = [6,9,11,11] eA =[0,-1,1,1] n=len(A) q=13 print (A,sA,eA) xN_1 = [1] + [0] * (n-1) + [1] print (xN_1) A = np.floor(np.polydiv(A,xN_1)[1]) bA = np.polymul(A,sA)%q bA = np.floor(np.polydiv(bA,xN_1)[1]) bA = np.polyadd(bA,eA)%q bA = np.floor(np.polydiv(bA,xN_1)[1]) print ("Print output\n",bA) 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 \pmod q\) \(\textbf{s_A}= s_{n-1} x^{n-1} + ... s_2 x^2 + s_1 x + s_0 \pmod q\) 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 \pmod q\) \(\textbf{s_B}= s^{'}_{n-1} x^{n-1} + ... s^{'}_2 x^2 + s^{'}_1 x + s^{'}_0 \pmod q\) 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)\) At the end of this, Bob and Alice will have the same shared value (and thus can create a shared key based on it). 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 |