2
$\begingroup$

Analysis of security of recent LWE based Key-exchange schemes, the error and secret vector is always chosen from the same Gaussian distribution. What will be the impact on the security if $\sigma_s\neq \sigma_e$? In particular, if $\delta=$root-hermite factor, $d=$dimension of the lattice $m+n$, $m=$number of samples, $q=$ LWE modulus, and $\sigma=\sigma_s=\sigma_e$.

  • The primal attack the BKZ block size ($b$) is optimized such that $\sigma\sqrt{b}\leq \delta^{2b-d-1}\cdot q^{m/d}$, where In the dual attack, we try to find a short vector in the dual lattice $w \in \Lambda' = \{ (x,y) \in \mathbb{Z}^m \times \mathbb{Z}^n : A^t x=y\mod q\}$. We try to find a short vector ($w,v$) of length $l$ such that, if ($A,As+e$) is a LWE sample ($w^ts+v^te \mod q$) is distributed as Gaussian. The advantage with which this vector can be distinguished from a random vector is $\epsilon=4e^{-2\pi^2\tau^2}$ where $\tau=l\sigma/q$. Now. if $\sigma\neq\sigma_s\neq\sigma_e$ how will the above equations change? For the primal attack can I replace $\sigma\sqrt{b}$ as $\sqrt{\sigma_s^2+\sigma_e^2}\sqrt{b}\leq\delta^{2b-d-1}\cdot q^{m/d}$ or in the dual attack $\tau=l\sqrt{\sigma_s^2+\sigma_e^2}/q$.

  • My second question is if $\sigma_s<<\sigma_e$ will the above equations hold? Is the new dual attack by Albrecht et al. for small secrets applicable here even though the secret is not binary?

The bounds are obtained from the security analysis of Newhope (Section 6.3 and 6.4) or this recent presentation by Albrecht

$\endgroup$
  • $\begingroup$ For your first question, could you cite the source of those bounds? I can't remember where they came from. In Lemma 3.1 of this paper give constraints on $\sigma_e$ and $\sigma_s$ (I think these are the $s_e$ and $s_k$ in the lemma). $\endgroup$ – user47922 Jun 20 '17 at 1:46
  • $\begingroup$ And in general, I think your hypothesis is correct assuming your distributions have no covariance? $\endgroup$ – user47922 Jun 20 '17 at 1:48
  • $\begingroup$ @galvatron That lemma is for the correctness of LWE encryption scheme but here I am not bothered about correctness only the security. I assume I have some scheme which will make my scheme correct always. For the source of bounds, I have added them in question. I would love to hear your feedback. $\endgroup$ – Rick Jun 20 '17 at 8:17
  • $\begingroup$ Strictly speaking, in NewHope, they use centered binomial distributions , $\psi_{16}$, since they are more efficient with a very small security trade-off. The some of two binomial distributions has a more complicated form than that of Gaussians. In this case, it may be a Poisson binomial distribution. $\endgroup$ – user47922 Jun 20 '17 at 16:53
  • $\begingroup$ But if you are wanting to stick to Gaussians anyway, the calculations look right to me, as Gaussians don't really appear in other ways besides the standard deviations. $\endgroup$ – user47922 Jun 20 '17 at 16:56

Your Answer

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

Browse other questions tagged or ask your own question.