[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 ) \) |

## 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+3x^5+4x^4+3x^3+6x^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\)

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)-1 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 "=== 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))

A sample run is:

('AB', array([ 12, 23, 46, 103, 76, 64, 40])) ('AB (mod p)', array([12, 10, 7, 12, 11, 12, 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 1 x + 5 x + 1 === Using A.B/(x^N+1) 2 1 x + 5 x + 1

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\)