It's easy to see that the crucial part of any lattice scheme is the added error. And different schemes seem to use different error distributions, some use Gaussian some use centered Binomial. Though, what do we know currently about the different error distributions used in lattices? I mean which one should be used when, and how does it affect the security of a lattice scheme? What are some important results that specifically study the effect of the error in lattice schemes?

  • $\begingroup$ Could you please give me a reference about some scheme that uses Binomial distribution to sample the noise? :) $\endgroup$ Feb 22 '18 at 7:26
  • $\begingroup$ @HilderVitorLimaPereira NewHope (eprint.iacr.org/2015/1092.pdf), and Kyber too. $\endgroup$
    – tinker
    Feb 22 '18 at 8:48
  • $\begingroup$ I think you just need something small with enough entropy not to be guessed, I think I saw some schemes using uniform bounded noise also $\endgroup$ Feb 22 '18 at 9:27
  • $\begingroup$ You should have a quick look at this excellent lattice survey web.eecs.umich.edu/~cpeikert/pubs/lattice-survey.pdf There's some discussion about non-gaussian errors at the end of page 26 $\endgroup$ Feb 22 '18 at 9:40

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.