4
$\begingroup$

In this quote from Lattice Cryptography for the Internet (page 8), author says that we can use error distribution (the same one that we used to generate error) to generate secret. My question is considering that sampling from normal distribution is costly, is there any advantage to also use normal distribution to generate secret instead of normal approach which is generating secret from uniform distribution. I am just wondering. Is just to prove that if secret is also generated from the same normal distribution, proof works ...

Because it is confusing and it does not make sense, newHope generates secret from distribution (binomial in case of newhope) (page 3) and this key exchange protocol also uses normal distribution to generate secret (page 8).

If I understood it correctly, in LWE only error has to be generated from normal distribution, not the secret. The same goes for R-LWE and R-LWE key exchange. Sampling from normal distribution is costly and we want the error to be close to zero so we can reconcile the key but why secret should be close to zero?

We now recall the ring-LWE probability distribution and (decisional) computational problem. For simplicity and convenience for our applications, we present the problem in its discretized, "normal" form, where all quantities are from $R$ or $R_q = R/qR$, and the secret is drawn from the (discretized) error distribution.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

Neither the secret nor the error in Ring-LWE (or LWE) encryption needs to be generated from the normal distribution. Only to get the tightest security proofs does one care about the "shape" of the distribution. For practical cryptanalysis, this does not matter -- only the size of the secret (and noise) does.

Having said this, there is an advantage to the normal distribution. During decryption, terms that look like $\langle s,e\rangle$ (inner product of the secret vector $s$ and error vector $e$) appears in the decryption. What we want for security is that $s$ and $e$ have large norms. What we want to avoid decryption errors is that $\langle s,e\rangle$ is small. And if one wants to have vectors $s$ and $e$ of a particular $l_2$ norm and have their inner-product be as small as possible, then these vectors should be chosen from a normal distribution.

The binomial distribution is a very good approximation to the normal and is much easier to generate. This is why it's a good choice for practical applications.

Edit: My original answer was incomplete. Actually, the uniform distribution is just as good as the binomial one if one only cares about the above two properties. The main advantage of the binomial distribution is that it has more entropy. This is important to prevent brute force and man-in-the-middle attacks.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you so much for the answer. But what about R-LWE key exchange? Is there any advantage because there is no encryption and decryption in key exchange. $\endgroup$
    – Node.JS
    Dec 22, 2016 at 8:35
  • $\begingroup$ Key exchange is essentially encryption and decryption. So all of the above design principles apply to key exchange. $\endgroup$
    – Vadim L.
    Dec 22, 2016 at 8:42
  • $\begingroup$ Just to be clear, it is possible to do encryption/KEX with large or even uniform secrets -- Regev's original scheme does, for example. And this actually yields a tighter security proof in terms of the "error rate" (and worst-case hardness guarantees). But the communication is quite a bit larger, so this method has not been proposed for practice. $\endgroup$
    – Chris Peikert
    Dec 22, 2016 at 13:52
  • $\begingroup$ @VadimL. Question #1: I am wondering do you have a reference when the Gaussian distribution was introduced for the first time in LWE? I couldn't find it in (Regev's LWE survey) and (Peikert's key exchange: Lattice Cryptography for the Internet). Question #2: In key exchange we receive as shared key $= s \cdot (A\cdot s' + e') = A\cdot s \cdot s' + s\cdot e'$. So if both party choose small $s, e$ (hence their inner product would be small) then chance of reconciliation fail to extract the same key would be reduced. But how $l_2$ norm is related? $\endgroup$
    – Node.JS
    Dec 29, 2016 at 0:38
  • $\begingroup$ #1: That would be Regev's original paper "On lattices, learning with errors, random linear codes, and cryptography". #2: The $\ell_2$ norm is important in cryptanalysis. When an attacker is trying to recover the secret key or the message, he will set up a lattice and try to find a short vector. We know how to judge the running time of lattice-reduction algorithms based on the $\ell_2$ norm of the vector they're trying to find. In particular, LLL (and its variants) are analyzed in terms of the $\ell_2$ norm. If one could get a good analysis for a different norm, then we could use that one. $\endgroup$
    – Vadim L.
    Jan 1, 2017 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.