Photo by Michael Dziedzic on Unsplash

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?

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
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]))
  • 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

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store