What's the purpose of the smoothing parameter in lattice-based cryptography?

Question

I see nearly all the lattice-based crypto papers talk about the smoothing parameter $\eta$. And I believe even some parameters are chosen with respect to that. However, I do not quite understand what's the purpose of it. What's its relation to lattices? Why is it useful and important for cryptography?

Answer 1

As is mentioned in the comments above, there are many uses for the smoothing parameter. Here is one that provides some intuition of why it's useful.

For a basis $B$ of a full-rank $n$ dimensional lattice, let $P(B)$ be a parallelepiped of the lattice $\Lambda = L(B)$. Consider the operation of taking a point $x \in \mathbb{R}^n$ mod $P(B)$, which is to find the unique vector $y \in P(B)$ such that $x - y \in \Lambda$. In other words, $x \equiv y \mod P(B)$.

Now, consider a distribution that samples points in $P(B)$ in the following way. It first samples a point $e \in \mathbb{R}^n$ from the continuous Gaussian distribution with center at 0 and parameter s, then computes $t \equiv e \mod P(B)$. The output of the distribution is $t$. If the Gaussian parameter $s$ is greater than the lattice smoothing parameter $\eta$, then the distribution of $t$ is statistically indistinguishable from the uniform distribution over $P(B)$. Conversely, if $s$ is less than the smoothing parameter, than $t$ is likely to be close to some lattice point.

To provide a more geometric intuition of what's going on here, imagine placing balls around each vertex of the parallelepiped $P(B)$, and consider the region of each of these balls that intersects with $P(B)$. It is a nice exercise to show that these intersections in fact sum to one ball. Now, imagine going in the reverse, direction, taking a ball and dividing it up according to the angles of the vertices in the parallelepiped, then assigning each fragment of the ball to the corresponding vertex. This ball is the continuous Gaussian we started with in the distribution above. The smoothing parameter is the minimum "radius" of the ball such that, when the regions are assigned in this way, the overlapping distributions are indistinguishable from the uniform distribution over $P(B)$.

The smoothing parameter is intimately connected with many other lattice constants, especially parameters like covering radius and successive minima. This is just one of the many interesting properties that it has.