Polynomials Will Secure The Internet …

Polynomials Will Secure The Internet …

The security of the Internet will radically change over the next decade or so, and the methods we use to prove identity, to digitally sign, and to create our secure tunnels for information will radically change. Why? Because quantum computers threaten our existing public-key methods. We will thus need to find other ways to do our public key trap door functions, and many of the routes lead to lattice cryptography.

With lattice methods, we have multi-dimensional spaces, and where to plot our points within there. Most of the time we think in one dimension (x), or it two dimensions (x, y) or three dimensions (x,y and z), but, in a lattice, we may have thousands of dimensions. Each point we have then fitted into a lattice of these points. To make a hard problem to solve, we add a small amount of error to the point. It is then extremely difficult to find the nearest point to the point with the error.

So, why have I said polynomials in the title, when we are dealing with lattice methods? Well, it’s quite simple … they are an excellent way of representing multi-dimension spaces. For example, if I have a point of (9, 5, 16), I would represent it with a quadratic equation of:

16x²+5x+9

This could be represented by a polynomial of [16, 9, 5]. If I have another polynomial of 2x²+x+7, and I multiplied them together, I would get:

f = (16x²+5x+9)(2x²+x+7) =32 x⁴ + 26 x³ + 135 x² + 44 x + 63

In Python, we can determine this with:

from numpy.polynomial import Polynomial

import numpy as np

f=Polynomial([16,9,5])

g=Polynomial([2,1,7])

r = f*g

print(r.coef)

print(np.poly1d(r.coef))

And a sample run gives:

[ 32.  26. 135.  44.  63.]
    4      3       2
32 x + 26 x + 135 x + 44 x + 63

Mod polynomials

With polynomials, for an order of five, we have the form:

ax⁵+bx⁴+cx³+dx²+ex+f

We can then represent this as an integer array of:

[a,b,c,d,e,f]

In Python, the polynomial of 5x⁴+4x³+x²+11x+10 is implemented and printed as:

import numpy as np
A=[5,4,1,11,10]
print ("A:")
print(np.poly1d(A))

This gives:

A:
   4     3     2
5 x + 4 x + 1 x + 11 x + 10

Let’s take an example of:

A=10x²+6x+2

B=12x²+3x+2

If we add these we get:

A+B=10x²+6x+2+12x²+3x+2=22x²+9x+4

Within cryptography, we normally use finite fields, and where the values are constrained by 0 and p-1, and where p is a prime number. For this we can perform a (mod) operation on this, such as with (mod13):

A+B (mod 13)=22x²+9x+4 (mod 13)=9x²+9x+4

Now let’s look at multiplication, for this we have:

A×B=(10x²+6x+2)×(12x²+3x+2)=120x⁴+30x³+20x²+72x³+180x²+12x+24x²+6x+4

A×B=120x⁴+102x³+62x²+18x+4

And now (mod 13):

A×B(mod13)=120x⁴+102x³+62x²+18x+4(mod13)=3x⁴+11x³+10x²+5x+4

Next we will perform a polynomial subtraction:

A−B=(10x²+6x+2)−(12x²+3x+2)=−2x²+3x

And now (mod 13):

A−B(mod13)=−2x²+3x=11x²+3x

Next, we will perform a polynomial division:

A÷B=(10x²+6x+2)÷(12x²+3x+2)=3x

And now (mod 13):

A÷B(mod 13)=3x

A sample run is:

Lattices

With lattice methods we use the shortest vector problem in a lattice, and which has an underpinning difficulty of factorizing polynomials. The lattice vector points are represented as polynomial values.

For this, we create modulo polynomial and then generate its inverse. In this case, we will create a polynomial (f) and then find its modulo inverse (f_p) [here], and which will result in:

f⋅f_p=1 (mod p)

Thus, if we then take a message (m) and multiply by f and then by f_p, we should be able to recover the message. Let’s take an example, with N=11 (the highest polynomial factor), p=31 and where Bob picks polynomial factors (f) of:

f=[−1,1,1,0,−1,0,1,0,0,1,−1]

f(x)=−1x¹⁰+1x⁹+1x⁶−1x⁴+1x²+1x−1 (mod 31)

We then determine the inverse of this with:

f_p:[9,5,16,3,15,15,22,19,18,29,5]

fp(x)=5x¹⁰+29x⁹+18x⁸+19x⁷+22x⁶+15x⁵+15x⁴+3x³+16x²+5x+9 (mod 31)

So, we can now take a message (m) and multiply it by f to gain a ciphertext, and then multiply it with f_p to recover the message. In the following we will use a message of:

m=[1,0,1,0,1,1,1,1]

m=1x⁷+1x⁶+1x⁵+1x⁴+1x²+1

A test run is [here]:

The code is based on this code [here]:

Here are a few more examples:

• N=11, p=3, f=[-1,1,1,0, -1,0,1,0,0,1,-1], m=[1,0,1,1,0 ,1,0,0,1,0,1] Try
• N=11, p=97, f=[-1,1,1,0, -1,0,1,0,0,1,-1], m=[1,0,1,1,0 ,1,0,0,1,0,1] Try
• N=11, p=997, f=[-1,1,1,0, -1,0,1,0,0,1,-1], m=[1,0,1,1,0 ,1,0,0,1,0,1] Try
• N=11, p=997, f=[-1,1,1,-1, -1,0,1,0,0,1,1], m=[1,1,1,1,0,1, 0,0,1,0,1] Try

Want to find out more about polynomial and lattice operations, try here:

https://asecuritysite.com/gf/