[Back] 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\)).

## \( R=\mathbb{Z}[X]/ ( X^{n}+1 ) \) - Adding polynomials |

## 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\) added to \(B\), we get [ 7,6,13,14]:

\(7x^3+6x^2+13x+14\)

Next we perform a \(\pmod q\) operation. If \(q=13\) we get:

\(7x^3+6x^2+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)} + \frac{B}{(X^N+1)} \pmod q\)

and find out it gives the same result as:

\( \frac{A+B}{(X^N+1)} \pmod q\)

import numpy as np import sys import numpy q=13 n=3 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])) xN_1 = [1] + [0] * (n-1) + [1] res=np.polyadd(A,B) print ("A+B:") print(np.poly1d(res)) res=np.polyadd(A,B)%q print ("\nA+B (mod p):") print(np.poly1d(res)) print ("\n== 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.polyadd(A,B) print ("=== 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.polyadd(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))

A sample run is:

A+B: 3 2 7 x + 6 x + 13 x + 14 A+B (mod p): 3 2 7 x + 6 x + 1 == X^N+1 3 1 x + 1 == A 3 2 4 x + 1 x + 11 x + 10 == B 3 2 3 x + 5 x + 2 x + 4 === Using A/(x^N+1) + B/(X^N+1) 2 6 x + 7 === Using (A+B)/(x^N+1) 2 6 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)=x^2+5x+1\)