quarkslab / NFLlib

NTT-based Fast Lattice library
MIT License
167 stars 52 forks source link

How is Gaussian sampling in NFLlib parameterized? #27

Closed iF2007 closed 7 years ago

iF2007 commented 7 years ago

I'm looking into this library and would like to bound l2-norm of a vector sampled from discrete Gaussian distribution. A sampled vector example (n=1024, \sigma=3) is here. Is the distribution parameterized as e^(-x^2/(2\sigma^2)) or e^(-\pi*x^2/s^2)?

I'm trying to verify the bound of l2-norm of above vector using lemma 2.5 in this paper, where the norm of my example vector is 96.13, which is larger than r=1 case (sqrt(3^21024)) for lemma 2.5 in above paper. Since the probability of norm > sqrt(3^21024) should extremely small, I would like to know how the discrete Gaussian distribution in NFLlib is parameterized.

Thanks

carlosaguilarmelchor commented 7 years ago

Hi, everything is in the source code :)

https://github.com/quarkslab/NFLlib/blob/92f8de0d6213bb14c79cc36a842cb3ae5ca8508c/include/nfl/prng/FastGaussianNoise.hpp#L80-L110

Best, Carlos

iF2007 commented 7 years ago

@carlosaguilarmelchor Hi Carlos. Thanks for your reply. I notice this header file after I open this issue and everything is clear. Thank you :)