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…
