Lattice Encryption Has A Similar Approach to ElGamal Encryption
Elliptic Curves become vectors and matrices
On Friday, I had a great talk with Vadim Lyubashevsky from IBM Research, and who is a world leader in lattice-based cryptography. When asked about how we could explain lattice-based cryptography, he outlined that lattice-based encryption resembles an ElGamal-type encryption and that digital signing resembles a Schnorr approach. In his latest tutorial, he outlines this [here]:
So, let’s compare ElGamal using elliptic curves and a base point of G, with lattice methods:
With ElGamal, we have a secret key of s, and a public key which is t=s.G. To encrypt, we generate a random value (r). The encryption of a message (M) is then:
a=r.G
b=r.t+M
The cipher is (a,b). To decrypt, we recover the message with the secret key (s) and (a,b):
M= b — a.s
We can prove this with:
M= r.t+M -r.G.s = r.(s.G) + M — r.G.s = M
In lattice methods, rather than an elliptic curve point, we have a matrix (A). The secret key is a vector of s, and the public key is t=s.A+e_1. The cipher is then:
a=r.A+e_2
b=r.t+e_3+q/2 .M
In this case, e_1, e_2 and e_3 are small amounts of noise as a vector, and where q is the largest coefficient value of our matrix values. Our message is a vector with the values of 0 and 1 representing the message value. The cipher is then (a,b). To decrypt, we recover the message with the secret key (s) and (a,b):
M≈b-a.s
This is due to the message part being much greater than the error values. To prove:
Recovered= r.t+e_3+q/2 .M — a.s = r.t+e_3+q/2 .M — (r.A+e_2).s
= r.(A.s+e_1)+e_3+q/2 .M — (r.A.s+e_2.s)
= r.A.s + r.e_1 + e_3 + q/2.M — r.A.s — e_2.s
= r.e_1+ e_3 + q/2.M — e_2.s
If divided by q/2, we should get the message back as the error values will be small.
Here is the talk:
Here is encrypting with ElGamal:
and lattice methods:
