Member preview

Mod P Polynomial Operations … Towards Quantum Robust Crypto

There you go … you can’t accuse me of click-baiting. With a title like this, you’re only going to click on this page, if you really want to read about quantum cryptography.

A demo of this method is defined here.

Mod P polynomials are used in some of the proposed methods in quantum computer robust cryptography, such as with lattice cryptography and especially with Ring Learning With Errors (R-LWE). In this we have polynomial equations with factors for each of the polynomial values. When we normally add we just collect the polynomial powers together and add their values:

a=2x⁴+3x³+10x+3

b=3x⁵+14x³+10x+4

The result will be:

z = a + b = 3x⁵+2x⁴+(3+14)x³+(10+10)x+(3+4) = 3x⁵+2x⁴+20x+7

z = a −b = 3x⁵+2x⁴+(3-14)x³+(10−10)x+(3−4) = 3x⁵+2x⁴–11x³−1

But in Mod P polynomials, we take a value (P), and the take the modulus of the factors. Normally we use a prime number number of P, so that we can perform operations. Let’s say we have:

a=2x⁴+3x³+10x+3

b=3x⁵+14x³+10x+4

Then to add Mod 17, we get:

a+ b = 3x⁵+2x⁴+3x+7 (mod 17)

Then to subtract Mod 17, we get:

a−b = 14x⁵+2x⁴+6x³+16 (mod 17)

Then to multiply Mod 17, we get:

a 𝗑 b = 6x⁹+9x⁸+11x⁷+4x⁶+12x⁵+8x⁴+3x³+15x²+2x+12 (mod 17)

A sample run is:

a(x)=	[3, 10, 0, 3, 2]
b(x)= [4, 10, 0, 14, 0, 3]
p= 17
== Operations ===
A + B (mod p): [7, 3, 0, 0, 2, 3]
A * B (mod p): [12, 2, 15, 3, 8, 12, 4, 11, 9, 6]
A - B (mod p): [16, 0, 0, 6, 2, 14]
Using Polynomial notation
a(x)= 2x^4 + 3x^3 + 10x + 3
b(x)= 3x^5 + 14x^3 + 10x + 4
p= 17
== Operations ===
A + B (mod p): 3x^5 + 2x^4 + 3x + 7
A * B (mod p): 6x^9 + 9x^8 + 11x^7 + 4x^6 + 12x^5 + 8x^4 + 3x^3 + 15x^2 + 2x + 12
A - B (mod p): 14x^5 + 2x^4 + 6x^3 + 16

Here is an outline of the code, and which shows the power of Python when dealing with lists:

import sys
import fracModulo
import math
from fractions import gcd
from fractions import Fraction as frac
from operator import add
from operator import neg
from operator import mod

if (len(sys.argv)>1):
p=int(sys.argv[1])
if (len(sys.argv)>2):
a=eval("["+sys.argv[2]+"]")
if (len(sys.argv)>3):
b=eval("["+sys.argv[3]+"]")
def modPoly(c,k):
if(k==0):
print "Error in modPoly(c,k). Integer k must be non-zero"
else:
return map(lambda x: fracModulo.fracMod(x,k),c)
def subPoly(c1,c2):
[c1,c2]=resize(c1,c2)
c2=map(neg,c2)
out=map(add, c1, c2)
return trim(out)
def multPoly(c1,c2):
order=(len(c1)-1+len(c2)-1)
out=[0]*(order+1)
for i in range(0,len(c1)):
for j in range(0,len(c2)):
out[j+i]=out[j+i]+c1[i]*c2[j]
return trim(out)
def resize(c1,c2):
if(len(c1)>len(c2)):
c2=c2+[0]*(len(c1)-len(c2))
if(len(c1)<len(c2)):
c1=c1+[0]*(len(c2)-len(c1))
return [c1,c2]

def trim(seq):
if len(seq) == 0:
return seq
else:
for i in range(len(seq) - 1, -1, -1):
if seq[i] != 0:
break
return seq[0:i+1]
def divPoly(N,D):
N, D = map(frac,trim(N)), map(frac,trim(D))
degN, degD = len(N)-1, len(D)-1
if(degN>=degD):
q=[0]*(degN-degD+1)
while(degN>=degD and N!=[0]):
d=list(D)
[d.insert(0,frac(0,1)) for i in range(degN-degD)]
q[degN-degD]=N[degN]/d[len(d)-1]
d=map(lambda x: x*q[degN-degD],d)
N=subPoly(N,d)
degN=len(N)-1
r=N
else:
q=[0]
r=N
return [trim(q),trim(r)]
def addPoly(c1,c2):
[c1,c2]=resize(c1,c2)
out=map(add, c1, c2)
return trim(out)
class Poly(list): 
def __repr__(self):
# joiner[first, negative] = str
joiner = {
(True, True): '-',
(True, False): '',
(False, True): ' - ',
(False, False): ' + '
}
        result = []
for power, coeff in reversed(list(enumerate(self))):
j = joiner[not result, coeff < 0]
coeff = abs(coeff)
if coeff == 1 and power != 0:
coeff = ''
            f = {0: '{}{}', 1: '{}{}x'}.get(power, '{}{}x^{}')
if (coeff<>0):
result.append(f.format(j, coeff, power))
        return ''.join(result) or '0'

p=17

a=[3,10,0,3,2]
b=[4,10,0,14,0,3]
print "a(x)=\t",a
print "b(x)=\t",b
print "p=\t",p

print "\n== Operations ==="
print "A + B (mod p):\t",modPoly(addPoly(a,b),p)
print "A * B (mod p):\t",modPoly(multPoly(a,b),p)
print "A - B (mod p):\t",modPoly(subPoly(a,b),p)
print "\nUsing Polynomial notation"
print "a(x)=\t",Poly(a)
print "b(x)=\t",Poly(b)
print "p=\t",p

print "\n== Operations ==="
print "A + B (mod p):\t",Poly(modPoly(addPoly(a,b),p))
print "A * B (mod p):\t",Poly(modPoly(multPoly(a,b),p))
print "A - B (mod p):\t",Poly(modPoly(subPoly(a,b),p))

A demo of this method is defined here.

The great thing about using mod P operations (and where P is a prime) is that we can multiply, divide, add and subtract values. For example:

a (mod P) + b (mod P) = (a+b) mod P

a (mod P) x b (mod P) = (a x b) mod P

If you want to see how Mod P applies to real-life quantum robust methods, click here.

Conclusions

We have a problem. Our existing ‘hard’ methods in public key encryption are not going to be that difficult any more with the advent for quantum computers, and we must investigate new ways of digitally signing and key exchange. Mod P polynomials give us a method of generating key pairs which is both a hard problem to crack, but where it is also computationally easy to use the keys.