5
$\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.

Improve this question
$\endgroup$
5
  • 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, 2019 at 1:11
  • $\begingroup$ @TMM Thanks! Can you give me more references or explanations on the differences? $\endgroup$
    – Licheng Wang
    Apr 18, 2019 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, 2019 at 23:53
  • 1
    $\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$
    – Léo Colisson
    Mar 7, 2021 at 7:38
  • $\begingroup$ Thanks for your wonderful answer! $\endgroup$
    – Licheng Wang
    Sep 21 at 2:49

1 Answer 1

Reset to default
1
$\begingroup$

I've seen a paper that may be related to this question. In following a short paragraph of this paper, explains about $\color{blue}{discrete}$ Gaussian distribution and the $\color{blue}{discretized}$ Gaussian distribution.

Reference: [Daniele Micciancio, Petros Mol. "Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions," In Crypto 2011, IACR 2011/521]

enter image description here

Improve this answer
$\endgroup$

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.