Lattice Encryption Has A Similar Approach to ElGamal Encryption

Elliptic Curves become vectors and matrices

I had recently 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):