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.

  • 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 at 1:11
  • $\begingroup$ @TMM Thanks! Can you give me more references or explanations on the differences? $\endgroup$ – Licheng Wang Apr 18 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 at 23:53

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.