The Trap Door with Polynomials — Towards a Post-Quantum Crypto Era

The Trap Door with Polynomials — Towards a Post-Quantum Crypto Era

Public key encryption is all about setting up a trapdoor function, where someone who knows a given secret will fall through a function. As much as possible we need a difficult problem to solve, and one which is known to be hard to solve. Knowing a secret allows the hard problem to become simple. For example, I might have a secret value of 6, and then use a secret multiplier of 5. My cipher method can then be to multiply my message by the secret to give:

Cipher = 6 x 5 = 30

Now, my trap door is now the inverse of my secret: 1/5. If you know that, you can now multiply the Cipher by the inverse value. But in this case, the inverse of 5 is easy to find, so we need tougher ways.

In public-key encryption, such as RSA, we encrypt with C=M^e (mod N) and decrypt with M=C^d (mod N). We pick a value of e, and then must find its inverse, by finding a value of d when:

d.e (mod N)=1

For this we need to perform an inverse mod operation:

d=e^{−1} (mod N) =1

Unfortunately, RSA, along with Elliptic Curve Cryptography, are at risk from quantum computers, so we must find another way. One of the methods proposed is lattice cryptography, and which uses polynomials. With polynomials — such as 1+6x — 5x²+2x² - we will operate with our mathematical operations, such as add :

(a+bx+c x²) + (d + ex+fx²) = (a+d) + (b+e) x + (c+f)x²

and subtract:

(a+bx+c x²) -(d + ex+fx²) = (a-d) + (b-e) x + (c-f)x²

and multiply:

(a+bx+c x²) x (d + ex+fx²) = (ad) + ae x + af x² + bd x + be x² + bf x³ + cd x² + ce x³ + cf x⁴

We can also divide using a long-division method. But one important operation is the inverse mod p operation, for where we find f^{-1} for f (mod p). The method most often used to find the inverse mod is the Extended Euclidean method applied to polynomial values. In lattice methods, we use polynomials, such as:

f=−1+x²+x³ (mod p)

To define a key, we often use trinary values of {−1,0,+1}as our factors. Then we need to find f^{-1}(mod p) in order to provide the reverse operation. Luckily we can do this with the Extended Euclidean method applied to polynomials. So let’s take an example, and prove it. With {-1,0,1,1}, we can represent with a polynomial of:

f=−1+x²+x³ (mod p)

and want to find the inverse mod of this for (mod 32), we can determine it as [solution]:

f′=19+7x+13x²+26x³

Now let’s prove that this is true. For this, we can do a multiplication of the original with the inverse, and hopefully, we will get an answer of unity. Let’s do:

r=f×f′=(mod p)

This gives

r=f×f′=(−1+x²+x³)×(-19+7x+13x²+26x³)(mod 23)

r=f×f′=(−19−7x−13x²−26x³+19x²+7x³+13x⁴+26x⁵+19x³+7x⁴+13x⁵+26x⁶) (mod p)

We then get the result of:

r=(−19−7x−13x²+19x²−26x³+19x³+7x³+13x⁴+7x⁴+26x⁵+13x⁵+26x⁶)

r=−19−7x+6x²+20x⁴+39x⁵+26x⁶

With polynomial operations in cryptography, we then limit the highest power of the polynomial by dividing by D=x⁴−1 and where 3 is the highest polynomial power we can have:

r=(−19−7x+6x²+20x⁴+39x⁵+26x⁶)/(x⁴−1)

and which gives a result of 1. The code is here:

If you are interested, here is NTRU:

and lattice:

https://asecuritysite.com/lattice