The Magic of Lattice and The Eye of a Falcon
To understand lattice cryptography, you need to understand polynomials, as our bit values are converted into polynomials. Our operations are then conducted with polynomial multiplies and add, and taken with a (mod p) operation (and where p will be the maximum value we generate for the polynomial values). For example, to multiply (5x²+1) and (2x+3), we get:
10x³ + 15x² + 2x + 3
and if we had this with (mod 7), we would get:
10x³ + 15x² + 2x + 3 (mod 7) = 3x³ + x² + 2x + 3 (mod 7)
With lattice encryption, Bob and Alice agree to share N (the largest polynomial power), p and q. Bob generates two short polynomials (f and g), and generates his key pair from this. These polynomials have coefficients of -1, 0 and 1. For example:
We then should be able to calculate the inverse of f for (mod p) and (mod q). Thus:
For example, if we use N= 11 and p= 31 and Bob picks a values of (f):
f=[−1,1,1,0,−1,0,1,0,0,1,−1]
We get:
and also picks:
Using an inverse function we get [here]:
The public key then becomes:
and the private key is f and f_q. In this case we get [here]:
