# Which lattice-based encryption scheme/signatures is fundamental?

If I would like to focus on only one signature scheme, and only one encryption based on lattices in a pedagogical context (to introduce the concept of lattice-based crypto to people familiar with cryptography)?

Is it possible to consider only one cryptographic problem in this context?

• If you really want to see the lattices, but not go into to much crypto technicalities this is how I introduced it: github.com/lducas/bamenda/blob/master/notes.pdf Jan 30 at 4:49
• I don't remember the full details of how to formulate this, so I'm not posting this as an answer, but I recall that there is a way to reduce RSA to a problem of finding the "best" lattice basis for a lattice with a fundamental region with volume $N$ (that's the determinant of the basis matrix if I recall). I think it is elementary to see that if $N=pq$ for two primes $p$ and $q$ then the "best" basis for the lattice on $\mathbb{Z}^2$ is $\{(p,0), (0,q)\}$
– Amit
Feb 2 at 17:27

This answer will only discuss LWE/SIS, but much of what is said could be extended to other assumptions (namely NTRU).

For encryption, the following is (roughly) canonical. It's also historically important --- it's the (secret key) cryptosystem Regev initially introduced in his paper introducing LWE.

You fix some distribution $$\chi$$ on $$\mathbb{Z}_q^n$$ (typically $$\chi$$ being i.i.d. Gaussians, or i.i.d. bounded uniform for simplicity). The secret is $$s\gets \chi$$ a draw from this distribution. To encrypt $$m\in\mathbb{Z}_q$$, you sample $$A\gets \mathbb{Z}_q^n$$, then output $$(A, b:= As + e + m)$$ where $$e\gets \chi$$.

This doesn't yet yield a correct cryptosystem (decrypting $$b - As = m + e\neq m$$). It can be made to be correct by encoding $$m$$ in an error-tolerant way, for example starting with $$m\in\mathbb{Z}_p$$ and encoding $$m\mapsto (q/p) m\in\mathbb{Z}_q$$. This is the cryptosystem Regev suggested (perhaps with $$p = 2$$), namely

1. $$\mathsf{KeyGen}$$: sample $$s\gets \chi$$
2. $$\mathsf{Enc}_s(m)$$ sample $$A\gets \mathbb{Z}_q^n$$, $$e\gets \chi$$, and return $$(A, As + e + (q/p)m)$$
3. $$\mathsf{Dec}_s(A, b)$$: Return $$\lfloor (b - As) / (q/p)\rceil = \lfloor m + e / (q/p)\rceil$$. This is equal to $$m$$ if $$|e / (q/p)| < 1/2$$, or if $$|e| .

I say this is roughly canonical as it is a key subroutine in

• both methods of constructing PKE from lattices (random linear combinations of encryptions of zero, and "noisy diffie hellman")
• all constructions of FHE.

in fact, most lattice-based encryption can be seen as doing the above, and

• varying the ring $$R = \mathbb{Z}_q$$ arithmetic occurs over,
• varying the encoding $$m\mapsto (q/p)m$$ one works with, or
• applying an aforementioned generic (for lattices) SKE to PKE transformation,
• using an LWR variant instead of an LWE variant (i.e. using "deterministic noise").

For signatures, things are a little less simple, because there are (at least) two main approaches to lattice-based signatures, namely

• "Hash and Sign" (or "GPV") signatures, and
• "Fiat Shamir with Aborts" (or "Lyubashevsky") signatures

that a priori seem quite different. They can be presented in a uniform way though, see theorem 1.4 of this paper.

Theorem 1.4 (Informal). Lattice-based Lyubashevsky signatures using the bit-decomposition Fiat-Shamir hash function are equivalent to lattice-based Hash-and-Sign signatures.

So in principle you can uniformly present a single lattice-based identification scheme that you convert into a signature in various ways, namely leading to either Hash and Sign or Fiat Shamir with Aborts signatures. I won't write as much about this though, as I haven't thought about it as much.