Which discrete Gaussian sampling algorithm does NFLlib use?

quarkslab / NFLlib

NTT-based Fast Lattice library

MIT License

165 stars 52 forks source link

Which discrete Gaussian sampling algorithm does NFLlib use? #22

Closed iF2007 closed 7 years ago

iF2007 commented 7 years ago

Thanks.

carlosaguilarmelchor commented 7 years ago

No. Precomputed CDT (Cumulative Distribution Tables). For fixed center sampling over Z^n it is the fastest alternative and it has a reasonable memory usage (typically <100Kbytes and for a constrained device this can be tuned to go around a few Kbytes).

It samples at roughly 1-3 cycles/sample if I remember correctly.

It is not cache-attack resistant though. It is possible to patch it for it, but we have not planned to do it anytime soon ....

iF2007 commented 7 years ago

@carlosaguilarmelchor Thanks for your reply. NFLlib is quite efficient. Do you have any further update plans?

carlosaguilarmelchor commented 7 years ago

Not right now. It would be nice to give a constant-time / cache attack resistance compilation flag.

Making the NTT constant time and cache attack resistant should be very easy. On the other hand for the gaussian sampling it will be harder.

Making NFLlib compilable under ARM would be a nice add on too.

But no plans at the moment ...

iF2007 commented 7 years ago

Thank you!

aguinet commented 7 years ago

What are the issues with ARM @carlosaguilarmelchor ?

carlosaguilarmelchor commented 7 years ago

I see three issues :

I know nothing about ARM
We have not tried
There will be no SIMD acceleration at all as we have specific SSE/AVX code

Oh and a fourth :

You are already overwhelmed with a ton of things to do ;)