Faster Gaussian Lattice Sampling Using Lazy Floating-Point Arithmetic

Léo Ducas 1 Phong Q. Nguyen 2, 3
1 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
2 CRYPT - Cryptanalyse
LIAMA - Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées, Inria Paris-Rocquencourt
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.
Type de document :
Communication dans un congrès
Xiaoyun Wang and Kazue Sako. ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, Dec 2012, Beijing, China. Springer, 7658, pp.415-432, 2012, Advances in Cryptology - ASIACRYPT 2012. 〈http://link.springer.com/chapter/10.1007%2F978-3-642-34961-4_26〉. 〈10.1007/978-3-642-34961-4_26〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00864360
Contributeur : Phong Q. Nguyen <>
Soumis le : samedi 21 septembre 2013 - 02:39:42
Dernière modification le : jeudi 11 janvier 2018 - 06:25:20
Document(s) archivé(s) le : vendredi 7 avril 2017 - 00:52:55

Fichier

DucasNguyen_Sampling.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Léo Ducas, Phong Q. Nguyen. Faster Gaussian Lattice Sampling Using Lazy Floating-Point Arithmetic. Xiaoyun Wang and Kazue Sako. ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, Dec 2012, Beijing, China. Springer, 7658, pp.415-432, 2012, Advances in Cryptology - ASIACRYPT 2012. 〈http://link.springer.com/chapter/10.1007%2F978-3-642-34961-4_26〉. 〈10.1007/978-3-642-34961-4_26〉. 〈hal-00864360〉

Partager

Métriques

Consultations de la notice

570

Téléchargements de fichiers

248