Post-quantum: Lattice, Polynomials and Modulo
Post-quantum: Lattice, Polynomials and Modulo
If you are away from work over Christmas and have some spare time, why not learn a little bit of theory?
One thing that worries me about this modern world, is that there can sometimes be a lack of deep knowledge around some of the core theoretical aspects. As a profession, there must be core fundamental knowledge that moves away from a surface learning approach in order develop a deep understanding of the core principles. One current weak area is in post-quantum cryptography, and especially the move towards lattice cryptography. So let’s take a simple example.
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), 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]:
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
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]))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 read how this is used to created post-quantum cryptography, then read on: