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 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 $\softO(n^3)$ 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 $\softO(n^2)$ or even $\softO(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
}