Lattice, Polynomials … and NumPy

Lattice, Polynomials … and NumPy

There’s one library in Python that probably makes Python the language of choice, and the reason it is so popular: NumPy. If you deal with numbers, the mighty Numpy library is there to help you. So let’s look at polynomials and the mod operator, and which are used in lattice cryptography.

In 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 npA=[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

Now 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 (mod13):

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 (mod13):

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

Next, we will perform a polynomial division:

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

And now (mod13):

A÷B(mod13)=3x

import numpy as np

import numpy as np
import sys
import numpy

q=13

n=3

A=[5,4,1,11,10] 
B=[3,5,2,4] 

if (len(sys.argv)>1):
    A=list(eval(sys.argv[1]))
if (len(sys.argv)>2):
    B=list(eval(sys.argv[2]))

print ("A:")
print(np.poly1d(A))
print ("B:")
print(np.poly1d(B))

print ("\n\n====== A+B =====")
res=np.polyadd(A,B)
print(np.poly1d(res))

res=np.polyadd(A,B)%q

print ("\nA+B (mod",q,"):")
print(np.poly1d(res))

print ("\n\n====== A*B =====")
res=np.polymul(A,B)
print(np.poly1d(res))

res=np.polymul(A,B)%q

print ("\n\nA*B (mod",q,"):")
print(np.poly1d(res))

print ("\n\n====== A-B =====")
res=np.polysub(A,B)

print(np.poly1d(res))

res=np.polysub(A,B)%q

print ("\n\nA-B (mod",q,"):")
print(np.poly1d(res))

print ("\n\nA/B =====")

res=np.floor(np.polydiv(A,B)[1])
print(np.poly1d(res))

res=np.floor(np.polydiv(A,B)[1])%q
print ("\n\nA/B (mod",q,"):")
print(np.poly1d(res))

print ("\n\nA/B (mod",q,"):")
print(np.poly1d(res))

A sample run is:

A:
    2
10 x + 6 x + 2
B:
    2
12 x + 3 x + 2

====== A+B =====
    2
22 x + 9 x + 4

A+B (mod 13 ):
   2
9 x + 9 x + 4

====== A*B =====
     4       3      2
120 x + 102 x + 62 x + 18 x + 4

A*B (mod 13 ):
   4      3      2
3 x + 11 x + 10 x + 5 x + 4

====== A-B =====
    2
-2 x + 3 x

A-B (mod 13 ):
    2
11 x + 3 x

A/B =====
 
3 x

A/B (mod 13 ):
 
3 x

A/B (mod 13 ):
 
3 x

And code:

Here is a running version:

Inverse polynomial mod p

Along with the arithmetic operations, we have an important operation which is the inverse of a polynomial mod p. In this case we will created a polnomial (f) and then find its modulo inverse (f_p), and which will result in f⋅fp=1(mod p):

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)

f⋅f_p=1(mod p)

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]:

Values used:
 N= 11
 p= 31
========

Bob picks a polynomials (f):
f(x)=  [-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1]

     10     9     6     4     2
-1 x  + 1 x + 1 x - 1 x + 1 x + 1 x - 1

====Now we determine F_p ===
F_p: [9, 5, 16, 3, 15, 15, 22, 19, 18, 29, 5]

    10      9      8      7      6      5      4     3      2
5 x  + 29 x + 18 x + 19 x + 22 x + 15 x + 15 x + 3 x + 16 x + 5 x + 9

====Now we determine the message ===
Alice's Message:	 [1, 0, 1, 0, 1, 1, 1, 1]

    7     6     5     4     2
1 x + 1 x + 1 x + 1 x + 1 x + 1

====Encrypted message ===
Encrypted message:	 [0, 1, 2, 1, 30, 0, 0, 1, 2, 1, 30]

     10     9     8     7      4     3     2
30 x  + 1 x + 2 x + 1 x + 30 x + 1 x + 2 x + 1 x

====Decrypted message ===
Decrypted message:	 [1, 0, 1, 0, 1, 1, 1, 1]

    7     6     5     4     2
1 x + 1 x + 1 x + 1 x + 1 x + 1

Here is another example with p=97 [here]:

Values used:
 N= 11
 p= 97
========

Bob picks a polynomials (f):
f(x)=  [-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1]

     10     9     6     4     2
-1 x  + 1 x + 1 x - 1 x + 1 x + 1 x - 1

====Now we determine F_p ===
F_p: [62, 95, 77, 7, 5, 61, 76, 84, 12, 65, 39]

     10      9      8      7      6      5     4     3      2
39 x  + 65 x + 12 x + 84 x + 76 x + 61 x + 5 x + 7 x + 77 x + 95 x + 62

====Now we determine the message ===
Alice's Message:	 [1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1]

    10     8     5     3     2
1 x  + 1 x + 1 x + 1 x + 1 x + 1

====Encrypted message ===
Encrypted message:	 [2, 1, 96, 1, 0, 1, 2, 96, 1, 1, 96]

     10     9     8      7     6     5     3      2
96 x  + 1 x + 1 x + 96 x + 2 x + 1 x + 1 x + 96 x + 1 x + 2

====Decrypted message ===
Decrypted message:	 [1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1]

    10     8     5     3     2
1 x  + 1 x + 1 x + 1 x + 1 x + 1

The code is based on this code [here]:

from fracModulo import extEuclidPoly, modPoly, multPoly, reModulo
import numpy
import sys

N=11
p=31

f=[-1,1,1,0,-1,0,1,0,0,1,-1]
m=[1,0,1,0,1,1,1,1]

if (len(sys.argv)>1):
	N=int(sys.argv[1])
if (len(sys.argv)>2):
	p=int(sys.argv[2])
if (len(sys.argv)>3):
	f=eval("["+sys.argv[3]+"]")
if (len(sys.argv)>4):
	m=eval("["+sys.argv[4]+"]")

print("Values used:")
print(" N=",N)
print(" p=",p)
print("========")
print("\nBob picks a polynomials (f):")

print("f(x)= ",f)
print ("\n",numpy.poly1d(f[::-1]))

D=[0]*(N+1)
D[0]=-1
D[N]=1

print("\n====Now we determine F_p ===")
[gcd_f,s_f,t_f]=extEuclidPoly(f,D)

f_p=modPoly(s_f,p)

print("F_p:",f_p)
print ("\n",numpy.poly1d(f_p[::-1]))

x=multPoly(f,m)
enc=reModulo(x,D,p)

x=multPoly(enc,f_p)
dec=reModulo(x,D,p)[:len(m)]

print("\n====Now we determine F_p ===")
print("Alice's Message:\t",m)
print ("\n",numpy.poly1d(m[::-1]))

print("\n====Encrypted message ===")
print("Encrypted message:\t",enc)
print ("\n",numpy.poly1d(enc[::-1]))

print("\n====Decrypted message ===")
print("Decrypted message:\t",dec)
print ("\n",numpy.poly1d(dec[::-1]))

Conclusion

And so the usage of RSA, Elliptic Curve and Discrete Logs will likely be replaced soon, as they can be cracked by quantum computers. Currently, NIST is assessing the likely replaced, and lattice cryptography is likely to be one of the main contenders for a winner. As lattice methods use polynomials and mod operations, the operations I have outlined are going to be important for the future of the Internet.