8
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ This question is pretty vague and open-ended. Can you rephrase to ask something specific that you’re interested in knowing? $\endgroup$ Nov 27, 2019 at 13:57
  • $\begingroup$ @ChrisPeikert What are you smoothing with it? Why do you need to do this smoothing in lattices-based schemes? $\endgroup$
    – user4936
    Nov 28, 2019 at 10:46

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ The distribution of t is close to uniform on its own, but not given e. If we are given e, then t is completely determined and hence very far from uniform. I think you may be mixing up the “smoothing” property and the discrete Gaussian distribution, which are different things. $\endgroup$ Jan 8, 2020 at 18:36
  • $\begingroup$ yes, sorry. answer has been edited to reflect this comment $\endgroup$
    – cryptocog
    Jan 8, 2020 at 19:18
  • $\begingroup$ a better way to explain this would have been that the original distribution I described, the one that outputs both $e$ and $t$, would be to say that it's indistinguishable from a distribution that first samples $t$ uniformly over $P(B)$, then samples $e$ according to the correct distribution, which is that $e$ is sampled from a continuous, zero-centered Gaussian with parameter s and $e \equiv t \mod P(B)$ $\endgroup$
    – cryptocog
    Jan 8, 2020 at 19:22
  • 2
    $\begingroup$ That’s true, but trivially so just by definition of conditional distribution—it doesn’t have anything to do with the smoothing parameter per se. The near-uniformity of t is the key relevant fact. $\endgroup$ Jan 8, 2020 at 21:10
  • $\begingroup$ @crytpocog Thanks for the answer. $\endgroup$
    – user4936
    Jan 17, 2020 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.