7
$\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 '19 at 13:57
  • $\begingroup$ @ChrisPeikert What are you smoothing with it? Why do you need to do this smoothing in lattices-based schemes? $\endgroup$
    – tinker
    Nov 28 '19 at 10:46
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 '20 at 18:36
  • $\begingroup$ yes, sorry. answer has been edited to reflect this comment $\endgroup$
    – cryptocog
    Jan 8 '20 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 '20 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 '20 at 21:10
  • $\begingroup$ @crytpocog Thanks for the answer. $\endgroup$
    – tinker
    Jan 17 '20 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.