Lattice Encryption Has A Similar Approach to ElGamal Encryption

Elliptic Curves become vectors and matrices

Prof Bill Buchanan OBE FRSE
3 min readDec 1, 2024

--

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:

--

--

Prof Bill Buchanan OBE FRSE
Prof Bill Buchanan OBE FRSE

Written by Prof Bill Buchanan OBE FRSE

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. Based in Edinburgh. Old World Breaker. New World Creator. Building trust.

No responses yet