Is the gaussian sampling described in the original paper (https://eprint.iacr.org/2013/383.pdf) faster (samples/sec) than the Knuth Yao sampling. As far as I know KY sampler is the fastest discrete gaussian sampler. I found one survey here https://www.sav.sk/journals/uploads/0212094402follat.pdf. It mentions both of these algorithms but without any comparative analysis.
1
-
$\begingroup$ Is there something missing from your title? (Maybe the word "algorithms", or maybe "and [something]"?) As written, it sort of sounds like the old joke question "What is the difference between a duck?" $\endgroup$– Ilmari KaronenAug 24, 2016 at 12:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
KY is indeed the faster than the method you referenced. However, it also uses a lot of memory (it needs to store a little more than the probabilities of each possible output in high precision). Depending on the available memory and the width of the distribution you are trying to sample from, this can be prohibitively large, especially when implementing it on a constrained device. This is what the paper by Ducas et al. addresses: their method is relatively fast (much faster than rejection sampling, but not as fast as KY) and uses much less memory. In essence, it simply gives you a different time-memory trade-off.
-
$\begingroup$ So in essence if we don't worry about the memory KY sampling is still fastest, right? $\endgroup$– RickAug 23, 2016 at 21:57
-
-
$\begingroup$ Hi, I implemented a KY algorithm using the algorithm homes.esat.kuleuven.be/~fvercaut/papers/SAC13.pdf. but it is strange that my algorithm is slower than the invcdt algorithm. Is the method described in the paper is slower than the original KY algorithm? $\endgroup$– RickAug 29, 2016 at 18:18