What Does a Secret Key Look Like in Homomorphic Encryption?

Like it or not, the rise of quantum computers will see the end of the RSA, discrete logs and elliptic curve methods in our public key encryption, digital signatures and key exchange. One of the best alternatives is to use lattice methods, which use polynomial operations. This uses an LWE (Learning With Errors) approach, where we create a vector (a) and a secret key vector (s). The message is also converted into a binary vector format, and a noise vector is added. The cipher then becomes:

cipher = a.s + m + noise (mod q)

and where q is the modulus value for the vector values. The a.s element is a dot product of two vectors; where the addition operations are vector additions. The cipher is then (a, cipher). To decrypt, we perform:

decrypt = cipher — a.s (mod q)

We can represent binary values with a polynomial. For example, for the bit pattern of 1011, we can use the form of:

x³+x+1

Then we could multiply this polynomial with 5x²+1 to get:

(x³+x+1)(5x²+1) = 5x⁵+x³+5x³+x+5x²+1 = 5x⁵+6x³+5x²+x+1

If we divide again by (x²+1), we should get our original polynomial back. Within our cryptography operations, we constrain the coefficients by a modulus value (q). This basically…