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.