How the condition $s \geq 8$ is determined in Lindner-Peikert cryptosystem?

In Lindner & Peikert paper, the authors propose that to set the cryptosystem's parameters, one should choose $q$ to be large enough to allow for a Gaussian parameter $s \geq 8$.

My question is, how this condition ($s \geq 8$) is obtained? I guess this lower-bound on $s$ relates to the smoothing parameter, but I can't figure out how it is determined?

• In the paper they specify that $s \geq 8$ because the discrete Gaussian approximates the continuous one well in that regime. Are you asking how to prove that, or are you asking how they came up with the $s$ values in Figure 4, which are almost all $\geq 8$? – user47922 May 28 '17 at 23:22
• I'm asking the first one: How to prove that the discrete Gaussian approximates the continuous one well when s≥8? – Hamidreza May 29 '17 at 5:31

Note: I edited a lot of my speculation and calculations after comments from Chris Peikert (see comments below).

The smoothing parameter on a lattice, $\eta_\epsilon(\Lambda)$, is roughly the width of a discrete Gaussian $\mathcal{D}_{\Lambda,s}$ above which it is well-approximated by a continuous Gaussian; see the Regev quote on page 17 here.

In particular, for $\mathbb{Z}^n$, there is an upper bound for the smoothing parameter (see page 8):

$\eta_\epsilon(\mathbb{Z}^n) \leq \sqrt{\ln(2n(1 + 1/\epsilon))/\pi}$

Again, on page 17, if $s \geq \sqrt{2} \eta_\epsilon(\mathbb{Z}^n)$, then the sum of the discrete Gaussian $\mathcal{D}_{\Lambda,s}$ and a continuous Gaussian with width $s$ is basically equivalent ("within statistical distance $4\epsilon$") to a continous Gaussian of width $\sqrt{2} s$, and you want this to hide the discrete structure in the continuous noise.

So I thought at first that the critical quantity was $\sqrt{2} \eta_\epsilon(\mathbb{Z}^n)$. However! After a comment from one of the authors of the paper (see comments below!), it's enough to just consider $s \geq \eta_\epsilon$ with $\epsilon \ll 1/2$. Using the formula above with $\epsilon = 2^{-256}$:

• $n=128 \rightarrow s \geq 7.63$

• $n=1024 \rightarrow s \geq 7.68$

• $n=2048 \rightarrow s \geq 7.89$

So $\eta_\epsilon$ doesn't fluctuate that much and you can take $s \geq 8$ for a nice round number.

Of course you can vary $\epsilon$; I used Lemma 4.2 in this paper to justify constraining it $0 < \epsilon < 1$, but it should be a negligible function, like $\epsilon = 2^{-n}$.

Thanks to Chris Peikert for discussion and clarification in the comments!

• This is all basically right, except that we don't even need the $\sqrt{2}$ factor, and we should take $\epsilon \ll 1/2$. All we want is for the Gaussian parameter $s$ to exceed the smoothing parameter $\eta_\epsilon(\mathbb{Z})$ (or $\mathbb{Z}^n$; it hardly makes a difference) for some very tiny $\epsilon$. Even with $\epsilon=2^{-256}$ and $n=1024$, this gives us a lower bound of $\approx 7.68$; we rounded up to 8 for good measure. – Chris Peikert May 30 '17 at 19:06
• Phew, thanks! :) Did you use a different formula or bound for $\eta_\epsilon$ in that calculation? If I plug in $n=1024, 1/\epsilon=2^{256}$, I get sqrt(log(2*1024*(1 + pow(2,256))/pi)) or $13.56$. – user47922 May 30 '17 at 19:46
• What's the base of the logarithm you're using? With natural log I still get 7.68. – Chris Peikert May 30 '17 at 19:59
• Yep, I had the base right, but was dividing by $\sqrt{\pi}$ wrong. Thanks for the sanity check. – user47922 May 30 '17 at 20:17