In Post-Quantum Crypto, What Is ℤ[X]/(Xn+1)?

In traditional public key encryption, we strength of the methods is either based on prime number factorization (RSA), discrete logarithms…

In Post-Quantum Crypto, What Is ℤ[X]/(X^n+1)?

In traditional public key encryption, the strength of the methods is either based on prime number factorization (RSA), discrete logarithms (ElGamal) or elliptic curves (ECC). Unfortunately, the security of each of these methods will be significantly reduced in an era of quantum computers. Thus one of the methods proposed to replace them is with lattice cryptography, and especially with Ring LWE (Learning With Errors). With this we add errors and also use polynomials for our operations. We then create a “ring”, where we use a (mod q) and a divide by (X^N+1), in order for our calculations to be constrained in the size of the polynomials used, and also for it to still work out mathematically.

And so the magical operation in finite fields for our public key methods is (mod p), and where p is a prime number (ℤp). For this we can have [a(mod p)×b(mod p)] (mod p) and which will equal ab (mod p). Then we can thus perform normal arithmetic operations, and 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³+5x²+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³+x²+11x+10

and B=[3,5,2,4]:

B=3x³+5x³+2x+4

For A multiplied by B, we get [ 12 ,23 ,46,103 ,76 ,64 ,40]:

12x⁶+23x⁵+46x⁴+103x³+76x²+64x+40

Next we perform a (mod q) operation and where q is a prime number. If q=13 we get:

12x⁶+3x⁵+4x⁴+3x³+6x²+12x+1

The magical 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 if N=3, we have x³+1. Now we perform a polynomial divide by x³+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:

A/(X^N+1)×B/(X^N+1)(mod q)

and find out it gives the same result as [here]:

AB/(X^N+1)(mod q)

In case you wonder what this is:

r = np.floor(np.polydiv(res,xN_1)[1]) %q

The “[1]” part takes the remainder of the polynomial divide, and the %q part does a (mod p) operation on the factors of the polynomials.

A sample run is [here]:

== 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³+x²+11x+10 and B=3x³+5x²+2x+4 and the result of the multiplications is AB=x²+5x+1.

The demo of the method is shown here.

Conclusions

Did you get that? Probably not, but stick at it! You will see it eventually. Try and some examples in Python, and hopefully you will start to see how all this works.