5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – user47922 May 28 '17 at 23:22
  • $\begingroup$ I'm asking the first one: How to prove that the discrete Gaussian approximates the continuous one well when s≥8? $\endgroup$ – Hamidreza May 29 '17 at 5:31
6
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Chris Peikert May 30 '17 at 19:06
  • $\begingroup$ 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$. $\endgroup$ – user47922 May 30 '17 at 19:46
  • $\begingroup$ What's the base of the logarithm you're using? With natural log I still get 7.68. $\endgroup$ – Chris Peikert May 30 '17 at 19:59
  • $\begingroup$ Yep, I had the base right, but was dividing by $\sqrt{\pi}$ wrong. Thanks for the sanity check. $\endgroup$ – user47922 May 30 '17 at 20:17

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.