Advertisement
Published in:
2012 | OriginalPaper | Chapter
Faster Gaussian Lattice Sampling Using Lazy Floating-Point Arithmetic
Authors : Léo Ducas, Phong Q. Nguyen
Published in: Advances in Cryptology – ASIACRYPT 2012
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 floating-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
Õ
(n3) where n is the lattice dimension. However, we introduce a laziness technique that can significantly speed up these algorithms. Namely, in certain cases such as NTRUSign lattices, laziness can decrease the complexity to
Õ
(n2) or even
Õ
(n). Furthermore, our analysis is practical: for typical parameters, most of the floating-point operations only require the double-precision IEEE standard.