We often see \( R=\mathbb{Z}[X]/ (X^{n}+1) \) within Ring LWE, but what is it? Well, it's a bit like using the \( \pmod p \) within crypto operations. Within lattice cryptography, we deal with polynomial values (such as \(3x^3+5x^2+2x+4\)). The magic operator is then the division of our polynomials by (\(X^N+1\)), and which will be \(x^4+1\) for the example where the order of the polynomial is three.
\( R=\mathbb{Z}[X]/ ( X^{N}+1 ) \) |
Theory
The magical operation in finite fields is \(\pmod p\), and where \(p\) is a prime number (\( \mathbb{Z}_p\)). For this we can have \((a \pmod p \times b \pmod p) \pmod p\) and which will equal \(ab \pmod p\).
In this way we can perform normal arithmetic operations, within a finite field (between 0 and \(p\)-1).
But how do we do this with polynomial operations, as we see in lattice cryptography?
With this we create a polynomial for values, such as for \(3x^3 + 5x^2 + 2x +4\) and which can be represented by the Python list of [3,5,2,4]. We can then use polynomial multiply and divide operations to perform our lattice methods.
For example, if A=[4,1,11,10]:
\(A=4x^3+x^2+11x+10\)
and B=[3,5,2,4]:\(B=3x^3+5x^2+2x+4\)
For \(A\) multiplied by \(B\), we get [ 12 ,23 ,46,103 ,76 ,64 ,40]:
\(12x^6+23x^5+46x^4+103x^3+76x^2+64x+40\)
Next we perform a \(\pmod q\) operation. If \(q=13\) we get:
\(12x^6+10x^5+7x^4+12x^3+11x^2+12x+1 \)
The magic operator is then the division of these polynomials by (\(X^N+1\)). With this, the arithmatic operations will still work, and where we will reduce the size of the polynomial.
For example is N=3, we have \(x^3+1\). Now we have divide by \(x^3+1\) at any point in the calculation, and end up with the same result. In the following code, we will take \(A\) and \(B\), and then perform:
\( \frac{A}{(X^N+1)} \times \frac{B}{(X^N+1)} \pmod q\)
and find out it gives the same result as:
\( \frac{AB}{(X^N+1)} \pmod q\)
A sample run is:
== X^N+1 4 1 x + 1 == A 3 2 4 x + 1 x + 11 x + 10 == B 3 2 3 x + 5 x + 2 x + 4 === A.B 6 5 4 3 2 12 x + 23 x + 46 x + 103 x + 76 x + 64 x + 40 === A.B (mod 13) 6 5 4 3 2 12 x + 10 x + 7 x + 12 x + 11 x + 12 x + 1 === Using A/(x^N+1) . B (X^N+1) 3 2 12 x + 12 x + 2 x + 7 === Using A.B/(x^N+1) 3 2 12 x + 12 x + 2 x + 7
In this case. In our operations we are only interested in the remainders of the division operations. We have \(A=4x^3+x^2+11x+10\) and \(B=3x^3+5x^2+2x+4\) and the result of the multiplications is \(AB/(x^3+1)=12x^3+12x^2+2x+7\). The code is:
import numpy as np import sys import numpy q=13 A=[4,1,11,10] B=[3,5,2,4] if (len(sys.argv)>1): A=list(eval(sys.argv[1])) if (len(sys.argv)>2): B=list(eval(sys.argv[2])) n=len(A) xN_1 = [1] + [0] * (n-1) + [1] print ("== X^N+1") print (np.poly1d(xN_1)) print ("== A") print (np.poly1d(A)) print ("== B") print (np.poly1d(B)) print A = np.floor( np.polydiv(A,xN_1)[1]) % q B = np.floor( np.polydiv(B,xN_1)[1]) % q res=np.polymul(A,B) print (f"\n=== A.B\n",np.poly1d(res)) res=res%q print (f"\n=== A.B (mod {q})\n",np.poly1d(res)) print ("\n=== Using A/(x^N+1) . B (X^N+1)") r = np.floor(np.polydiv(res,xN_1)[1]) %q print print(np.poly1d(r)) res=np.polymul(A,B) print ("\n=== Using A.B/(x^N+1)") r=np.floor(np.polydiv(res,xN_1)[1]) %q print print(np.poly1d(r))