Most influential/illuminating papers/books/courses on lattice based cryptography?

Question

I'm interested in some sort of "compendium" on lattice-based crypto. There are a bunch of maths behind FALCON and other stuff. A lot of articles are devoted to lattice crypto, but not of them are of paramount importance. The other problem is that there are papers that are obviously influential, but they are hard to understand "from scratch".

To start with something I may notice some of them:

GPV framework:

1. "How to Use a Short Basis: Trapdoors for Hard Lattices and New Cryptographic Constructions".

Cryptanalysis:

1. "Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures"

Basic courses :

1. winter school on lattice-based crypto (https://cyber.biu.ac.il/event/the-2nd-biu-winter-school)
2. Regev course on lattices in CS (https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/)
3. Vinod's course (http://people.csail.mit.edu/vinodv/6876-Fall2015/index.html)

Surveys:

1. "Lattice-based Cryptography" part from the book "Post-Quantum Cryptography".
2. "A Decade of Lattice Cryptography", Peikert.

Unfortunately, I didn't find anything on discrete Gaussian distributions and properties of continuous Gaussians (why is it "not far from" uniform over any "small" parallelopiped), how to generate them; on smoothing parameter and its "intuitive" meaning. Also, reductions from average to worst-case are somewhat tricky and uneasy to understand form Ajtai papers. And there is a direction of research on ideal lattices, which somehow related to integer rings of number fields ($\mathbb{Z}_K$), this is completely obscure.

Answer 1

You seem to have a few questions:

Why are Discrete Gaussians "not far" from the uniform distribution when you work mod the lattice?

This is worked out in the paper they are introduced in (Miccancio Regev 2004). See Lemma 4.1 in particular.

How to generate them?

It depends on whether you care about constant-time generation or not. Either way, there are a few techniques. These include using "generic samplers" (that work for any discrete probability distribution), including:

• Inverse CDT (cumulative density table) --- If $F_X(x)$ is the cumulative density function of $X$, and $U\sim \mathcal{U}([0,1])$, then $F_X^{-1}(U)\sim X$. This can be used to generate samples from any distribution.

• Knuth-Yao sampling --- You create a certain binary tree, then preform an unbiased walk on it, and return a sample based on what leaf you end up in. Very entropy efficient (and where the "Entropy is equal to the # of coin flips you need to sample from a distribution) comes from, but hard to make constant time without destroying the entropy efficiency.

• Alias sampling. A little harder to explain, but you can reduce sampling from any distribution to sampling from a uniform distribution, then sampling a (pre-computed) biased coin depending on the uniform value sampled.

There is a non-generic sampler known as Karney's method as well. Moreover, there's a sampling technique known as "convolution sampling", which allows one to generate discrete gaussians of larger parameters from discrete gaussians of small parameters, so one can restrict to the small parameter case.

Recent work can be seen here, and the references can be useful pointers for the rest of the literature (it misses out on some recent work trying to make KY sampling constant time, but that's about it).

Smoothing Parameter's intuitive meaning

Intuitively, it's the amount of Gaussian mass one has to place on each lattice point such that it "blurs" throughout space. One can think of the lattice $\Lambda$ as initially a set of points (having discrete gaussians of parameter $\sigma$ of "0" on each point). As you increase $\sigma$, these points "blur" out. If you increase $\sigma$ enough, they'll "cover" the whole space (and then, when working mod the lattice, will approach the uniform distribution). The smoothing parameter measures when a "phase transition" of this form happens, between being quite close to uniform, and non-uniform.

If you're more familiar with geometric notions of the lattice one could think about continually increasing balls around lattice points (instead of gaussians), until one finally covers all points of the ambient space in some ball. This has another quantity associated with its phase transition known as the "covering radius".