Faster Gaussian Lattice Sampling Using Lazy Floating-Point Arithmetic - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

Faster Gaussian Lattice Sampling Using Lazy Floating-Point Arithmetic

Résumé

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.
Fichier principal
Vignette du fichier
DucasNguyen_Sampling.pdf (442.26 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00864360 , version 1 (21-09-2013)

Identifiants

Citer

Léo Ducas, Phong Q. Nguyen. Faster Gaussian Lattice Sampling Using Lazy Floating-Point Arithmetic. ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, IACR, Dec 2012, Beijing, China. pp.415-432, ⟨10.1007/978-3-642-34961-4_26⟩. ⟨hal-00864360⟩
370 Consultations
349 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More