4
$\begingroup$

In lattice cryptography, we always face the probem of discrete gaussian sampling. To the beginners, it is a bit complex. However, gaussian sampling from a continous space is much easier to understand, and a lot of tools are available. Say, we can use MATLAB to do gaussian sampling very efficiently. So, I want to know what is the difference between the following to process:

(1) discrete-then-gaussian: Just as required is many lattice cryptography papers.

(2) gaussian-then-discrete: At first, get continous gaussian samples, say by using MATLAB, and then perform nearest rounding operations, i.e., discrete to the nearest integers.

$\endgroup$
4
  • 1
    $\begingroup$ The resulting distributions of (1) and (2) are not quite the same, and in some applications even a tiny difference in these distributions can be fatal for proving/guaranteeing security. $\endgroup$
    – TMM
    Apr 18 '19 at 1:11
  • $\begingroup$ @TMM Thanks! Can you give me more references or explanations on the differences? $\endgroup$ Apr 18 '19 at 6:10
  • 1
    $\begingroup$ Simply from looking at both definitions you should be able to see there is no immediate reason for the two distributions to be equivalent - sure, they both mimic a continuous Gaussian on a discrete set, but the probability mass function is different. $\endgroup$
    – TMM
    Apr 18 '19 at 23:53
  • $\begingroup$ @TMM But in Regev05, what is proven secure (i.e. reduces to GapSVP) is the use of the "gaussian-then-discrete" version. I started this thread to talk about the security of the discrete-then-gaussian approach crypto.stackexchange.com/questions/88685/… $\endgroup$ Mar 7 at 7:38

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.