Goodbye RSA and ECC, And Hello To Polynomial Rings (X^N+1)

Goodbye RSA and ECC, And Hello To Polynomial Rings (X^N+1)

And so the era of RSA and ECC will come to an end within the next decade or so. While they have served us well, the advent of quantum computers will see them fade into the background. Our systems must then migrate, and one of the main contenders to replace them is lattice encryption. With this we use polynomials to represent our lattice points, and where we add errors to these points.

In a lattice we can have multiple dimensions, such as having hundreds of axis. And so, for an (x,y,z,w) point we might have a value of [4,1,11,10], and which we can represent as a polynomial with:

A=4x³+x²+11x+10

Let’s now say we have a secret key point of [3,5,2,4], we then have:

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

For A added to B, we get [ 7,6,13,14]:

A+B=7x³+6x²+13x+14

Often in public-key encryption, we constrain our values between 0 and a given prime number minus 1 (q-1). Thus, for a prime number of 13, we can perform a (mod 13) operation to get:

A+B (mod 13) = 7x³+6x²+1 (mod 13)

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

A.B = 12x⁶+23x⁵+46x⁴+103x³+76x²+64x+40

Next, we perform a (mod q) operation. For q=13 we get:

A.B (mod 13) = 12x⁶+10x⁵+7x⁴+12x³+11x²+12x+1 (mod 13)

But, now we have an order of six (x⁶), and which is greater than the number of vector axis’. The answer to this is to have a polynomial ring, and which is equivalent to having an integer ring. With an integer ring, we roll-around a prime number using the (mod p) operation, and where:

A +B (mod p) = B + A (mod p) = (B (mod p) + A (mod p)) (mod p)
A.B (mod p) = B.A (mod p) = (B (mod p) . A (mod p)) (mod p)

The polynomial ring thus limits the order of the polynomial, but rather than using a prime number, we do a polynomial divide by x^N+1, and where N-1 is the largest polynomial power. If we now divide A.B by x⁴+1 we get:

12x³ + 12x² + 2x + 7 [here]

Here is a sample run for dividing A by x⁴+1 and B by x⁴+1 and then multiplying, and (A.B) and then dividing by x⁴+1 [here]:

== 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

We can see the results are the same so that the ring is preserved whenever we divide by x^N+1. If you are interested in how this is used in public-key encryption and key exchange, have a look here: