3
$\begingroup$

How does tail cutting and precision of discrete Gaussian sampling implementations affect LWE / Ring-LWE security? Is there a rule of thumb or guideline for choosing the tail cut and the precision for a given standard deviation?

Tail cutting refers to chopping off the “tail” portion of the distribution ($|x| > \beta \sigma$) which has negligible total mass.

In this paper from 2015, the author recommends tail-cut at $|x| > 9.2\sigma$ and 64-bit precision for 128-bit security. However, it seems too conservative, since many of the NIST PQCrypto submissions are using smaller tail-cuts and much lower precision. For example, FrodoKEM uses tail-cut at $\approx 4\sigma$ and 16-bit precision. Also, FrodoKEM is using the Renyi divergence, instead of the statistical distance, between the theoretical and the quantized distributions, as a measure of accuracy of sampling.

$\endgroup$
  • 1
    $\begingroup$ You might want to define tail cutting, or link to something that does. I am presuming that it refers to the technique of truncating the least significant bits of a value instead of adding an error term to it? $\endgroup$ – Ella Rose Mar 31 '18 at 14:51
  • $\begingroup$ Added the definition of "tail-cut", along with links to papers and motivation for my question. Thanks! $\endgroup$ – Naruto999 Mar 31 '18 at 19:09
1
$\begingroup$

Tail cutting and precision refer to the problem of distinguishing the actual distribution used in your scheme and the distribution used in the proofs for the scheme. You want to somehow argue that an adversary cannot get any advantage from these two distributions being slightly different.

As you already mentioned, there are currently two more or less widely used approaches in lattice crypto. The traditional way is bounding the statistical distance (SD). Which really computes the difference between two distributions. The second approach is the Renyi divergence (RD). The Renyi divergence computes something like a weighted difference (depending a bit on which one you take). The best thing to do is to really read the paper which proposed this. They also discuss the different orders of Renyi divergence. There are now several follow up papers which improve this approach. Just ask your favorite search engine.

In general, there is not really a rule of thumb to estimate the outcome of such an analysis using either SD or RD.

However, when it comes to the tail cut it is comparatively easy though as the difference between the two distributions is typically known. If the total probability mass in the tails is something like $p = 2^{-k}$ for security parameter $k$, then the statistical distance between the distributions with and without tail is just $p$ and hence negligible. Which means that an adversary cannot distinguish the two distributions better than with probability bounded by $p$. Consequently, the difference in the success probability of any adversary attacking the scheme with one or the other distribution must also be bounded by $p$.

When it comes to the question of floating point precision everything gets more tricky. Here, the difference depends on the algorithm used and the way it is implemented. Hence, you need a new analysis for every implementation.

$\endgroup$

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.