1
$\begingroup$

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.

$\endgroup$
  • $\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 Karonen Aug 24 '16 at 12:17
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So in essence if we don't worry about the memory KY sampling is still fastest, right? $\endgroup$ – Rick Aug 23 '16 at 21:57
  • $\begingroup$ yes, as far as i know. $\endgroup$ – blowfish Aug 24 '16 at 1:35
  • $\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$ – Rick Aug 29 '16 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.