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
