6
$\begingroup$

In many lattice based cryptosystems, Gaussian distribution is used. Can you explain why only Gaussian distribution is preferred?

$\endgroup$
  • $\begingroup$ It's not quite the standard Gaussian distribution from statistics, though they are related. The use of discrete Gaussian sampling goes all the way back to Regev's result from 2005 on learning with errors: cims.nyu.edu/~regev/papers/qcrypto.pdf $\endgroup$ – pg1989 Feb 10 '16 at 17:19
  • $\begingroup$ If you're lucky Chris Peikert will see this question and write a solid answer. He lurks here and occasionally answers questions. $\endgroup$ – pg1989 Feb 10 '16 at 17:23
4
$\begingroup$

Most lattice based encryption and/or key-exchange algorithms are based on the LWE or Ring-LWE problems. Typically, their security is shown using a reduction to an average-case instance of the (Ring-)LWE problem.

As pg1989 commented, Regev proved a very important hardness theorem for LWE in 2005. Essentially it's a quantum, polynomial-time reduction using an oracle for LWE to solve the approximate SIVP problem (given a lattice, find a full-rank set of lattice vectors where the longest such vector is nearly as short as possible). This is very useful, because it is a worst-case hardness guarantee: as long as some SIVP instances are hard, then a random LWE instance is also hard.

A similar quantum worst-case hardness theorem exists for Ring-LWE to approximate Ideal-SVP (given an ideal lattice, find a vector nearly as short as possible). Note that classical reductions exist as well (at least for LWE), but with some extra restrictions on the parameters.

Both these problems have been intensively studied and appear to be intractable for reasonable approximation factors. IE, you can find exponential approximation factor solutions in polynomial time, or find polynomial approximation factor solutions in exponential time. Quantum algorithm attempts don't fare much better.

Now to answer your question: why are (discrete) Gaussian distributions used? Because (discretized) Gaussian error distributions are assumed in the worst-case hardness theorems that are essential to the security of (Ring-)LWE.

I don't really know if similar theorems are known/possible using other error distributions. My best guess is that the Gaussian nature of the error distribution is essential to the reduction.

$\endgroup$

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.