# Effect of tail cutting and precision of discrete Gaussian sampling on LWE / Ring-LWE security

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.

• 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? – Ella Rose Mar 31 '18 at 14:51
• Added the definition of "tail-cut", along with links to papers and motivation for my question. Thanks! – Naruto999 Mar 31 '18 at 19:09

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$.