Faster Gaussian Lattice Sampling using Lazy Floating-Point ArithmeticLéo Ducas and Phong Nguyen. Published at ASIACRYPT' 12.Abstract: Many lattice cryptographic primitives require an efficient algorithm to sample lattice points according to some Gaussian distribution. All algorithms known for this task require long-integer arithmetic at some point, which may be problematic in practice. We study how much lattice sampling can be sped up using Foating-point arithmetic. First, we show that a direct Floating-point implementation of these algorithms does not give any asymptotic speedup: the Floating-point precision needs to be greater than the security parameter, leading to an overall complexity ~O(n^3) where n is the lattice dimension. However, we introduce a laziness technique that can signifficantly speed up these algorithms. Namely, in certain cases such as NTRUSign lattices, laziness can decrease the complexity to ~O(n^2) or even ~O(n). Furthermore, our analysis is practical: for typical parameters, most of the Floating-point operations only require the double-precision IEEE standard. Bibtex: @inproceedings{DuNg12a, author = {L. Ducas and P. Q. Nguyen}, title = {Learning a Zonotope and More: Cryptanalysis of {NTRUSign} Countermeasures}, booktitle= "Advances in Cryptology -- Proceedings of ASIACRYPT '12", publisher= {Springer}, series = {LNCS}, year = 2012 } Proceedings version (PDF) Slides (PDF) |