In Our Existing Public Key Encryption, We Use Prime Numbers To Reduce Complexity.
In Our Existing Public Key Encryption, We Use Prime Numbers To Reduce Complexity. What Does Lattice Use?
Lattice uses Mod p and Irreducible Polynomials
The magic of our existing public key methods is to use the modulo of a prime number (p). And so all our calculations can be done with respect to (mod p). Thus:
a.b (mod p) = (a mod p) . (b mod p) (mod p)
The great advantage with this is that we constrain our values within a finite find (between 0 and p-1), and thus do not end up with extremely large values. And, so, with RSA, to encrypt we have:
C = M^e (mod N)
and where N is the multiplication of two large prime numbers, and to decrypt, we have:
M = C^e (mod N)
The computation of the exponential in respect to (mod N) is very efficient and is typically done through Mongomary Ladder method [here].
But, wait. Our existing public key methods will be cracked by quantum computers! For this, the main method that is proposed is to use lattice methods.
Polynomials (mod p)
In lattice methods, we represent the points on a lattice using a polynomial. Thus a 3D point of (99,65,3) could be represented with a polynomial as:
p = 99x² + 65x + 3
We can also introduce a prime number to make sure that the polynomial factors do not exceed a given value (as with a finite field). For example:
p = 99x² + 66x + 3 (mod 13) = 8x² + x + 3 (mod 13)
It we try a few operations, such as for multiply, add and subtract, and use the (mod p) operation we get [here]:
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
And thus, we can make sure that our factors of the polynomial values are constrained between 0 and p-1. But, if we multiply, we are going to get large polynomial values, such as 3x⁵¹ times 4x⁵² will give us a polynomial value of 12x¹⁰³. But, let’s say we only want the largest polynomial factor to be x⁶⁰. For this, we use an irreducible polynomial — and which reduces the complexity of the polynomial, without losing any of the information we need.
Irreduciable polynomials
In data communications and cryptography, we can represent binary values as polynomials in GF(2). These can then be processed with GF(2) arithmetic. A value of 10011 can then be represented in a polynomial form as x⁴+x+1. Every non-prime value can be reduced to a multiplication of prime numbers. For example, 14 is 2×7 and 16 is 2×2×2×2. The same can be done for polynomials in GF(2), and where we can factorize a polynomial. Within polynomials, the prime number equivalents are known as irreducible, as they cannot be factored.
Let’s try a few:
Val=2 Binary=10 Poly=x irreducible [Try!]
Val =3 Binary=11 Poly=x+1 irreducible [Try!]
Val=4 Binary=100 Poly=x² =(x)(x) [Try!]
Val=5 Binary 101 Poly=x³+1 = (x+1)(x+1) [Try!]
Val=6 Binary=110 Poly=x²+x = (x)(x+1) [Try!]
Val=7 Binary=111 Poly=x²+x+1 irreducible [Try!]
We can see that x²+x+1 is irreducible, while x² can be reduced to x times x. A more complete table is [here]:
Coding
The following is some code that will be able to test for irreducibility [here]:
from galois_field import GFpn
import sys
a=([1,0],[1,1],[1,1,1],[1,0,1,1],[1,1,0,1],[1,0,0,1,1],[1,1,0,0,1],[1,1,1,1,1],[1,0,0,1,0,1],[1,0,1,0,0,1],[1,0,1,1,1,1],[1,1,0,1,1,1],[1,1,1,0,1,1],[1,1,1,1,0,1],[1,0,0,0,0,1,1],[1,0,0,1,0,0,1],[1,0,1,0,1,1,1],[1,0,1,1,0,1,1],[1,1,0,0,0,0,1],[1,1,0,0,1,1,1],[1,1,0,1,1,0,1],[1,1,1,0,0,1,1],[1,1,1,0,1,0,1])
tofind=[1,0,0,1]
p=[1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1]
if (len(sys.argv)>1):
tofind=eval("["+sys.argv[1].replace(" ","")+"]")
if (len(tofind)>10): sys.exit()
try:
gf = GFpn(2,p )
except Exception as e:
print ("Error:" ,e)
sys.exit()
tofindval = gf.elm(tofind)
print (f"Factors of {tofindval}")
# Try one factor
try:
for i in range(0,len(a)):
aval1 = gf.elm(a[i])
res1=aval1
if (str(tofindval)==str(res1)):
print(a[i])
print(f"({aval1})")
sys.exit()
except:
sys.exit()
# Try two factors
try:
for i in range(0,len(a)):
for j in range(i,len(a)):
aval1 = gf.elm(a[i])
aval2 = gf.elm(a[j])
res2=aval1*aval2
if (str(tofindval)==str(res2)):
print(a[i],a[j])
print(f"({aval1})x({aval2})")
sys.exit()
except:
sys.exit()
# Try three factors
try:
for i in range(0,len(a)):
for j in range(i,len(a)):
for k in range(j,len(a)):
aval1 = gf.elm(a[i])
aval2 = gf.elm(a[j])
aval3 = gf.elm(a[k])
res3=aval1*aval2*aval3
if (str(tofindval)==str(res3)):
print(f"({aval1})x({aval2})x({aval3})")
print(a[i],a[j],a[k])
sys.exit()
except:
sys.exit()
A sample run gives [here]:
Factors of 1x^4 + 1x^3 + 1x^2 + 1
[1, 1] [1, 0, 1, 1]
(1x + 1)*(1x^3 + 1x + 1)
In this case x⁴+x³+x²+1 can be factorized by (x+1) and (x³+1x+1) in GF(2). This is true because:
f=(x+1)(x³+x+1)
f=x⁴+x²+x+x³+x+1
f=x⁴+x³+x²+1
Testing
We can then test:
- Factors of x for GF(2) — irreducible. Go!
- Factors of x² for GF(2). Go!
- Factors of x²+1 for GF(2). Go!
- Factors of x²+x for GF(2). Go!
- Factors of x² for GF(2). Go!
- Factors of x³+x²+x for GF(2). Go!
- Factors of x³+x²+1 for GF(2) — irreducible. Go!
- Factors of x⁴+x+1 for GF(2) — irreducible. Go!
Not just lattice …
With AES encryption, we use GF(2⁸), and where we constrain the largest polynomial value is x⁷. This allows us to operate on 8-bit values at a time, and significantly reduces the complexity of the processing. For this we use an irreducible polynomial of x⁸+x⁴+x³+x+1. If you want to see it in operation, try here:
https://asecuritysite.com/gf/gf01
Conclusions
And, so, lattice methods, have two tricks up their sleeve: the (mod p) operation to reduce the size of the polynomial factors, and irreducible polynomials to reduce the large polynomial factor. So, it’s a long goodbye to RSA, discrete logs and elliptic curves, and a quick hello to lattice methods and polynomials.