Quadratic Time, Linear Space Algorithms for Gram-Schmidt Orthogonalization and Gaussian Sampling in Structured Lattices

Vadim Lyubashevsky 1, 2 Thomas Prest 1
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
Abstract : A procedure for sampling lattice vectors is at the heart of many lattice constructions, and the algorithm of Klein (SODA 2000) and Gentry, Peikert, Vaikuntanathan (STOC 2008) is currently the one that produces the shortest vectors. But due to the fact that its most time-efficient (quadratic-time) variant requires the storage of the Gram-Schmidt basis, the asymptotic space requirements of this algorithm are the same for general and ideal lattices. The main result of the current work is a series of algorithms that ultimately lead to a sampling procedure producing the same outputs as the Klein/GPV one, but requiring only linear-storage when working on lattices used in ideal-lattice cryptography. The reduced storage directly leads to a reduction in key-sizes by a factor of Ω(d), and makes cryptographic constructions requiring lattice sampling much more suitable for practical applications. At the core of our improvements is a new, faster algorithm for computing the Gram-Schmidt orthogonalization of a set of vectors that are related via a linear isometry. In particular, for a linear isometry r : R d → R d which is computable in time O(d) and a d-dimensional vector b, our algorithm for computing the orthogonalization of (b, r(b), r 2 (b),. .. , r d−1 (b)) uses O(d 2) floating point operations. This is in contrast to O(d 3) such operations that are required by the standard Gram-Schmidt algorithm. This improvement is directly applicable to bases that appear in ideal-lattice cryptography because those bases exhibit such " isometric structure ". The above-mentioned algorithm improves on a previous one of Gama, Howgrave-Graham, Nguyen (EUROCRYPT 2006) which used different techniques to achieve only a constant-factor speed-up for similar lattice bases. Interestingly, our present ideas can be combined with those from Gama et al. to achieve an even an larger practical speed-up. We next show how this new Gram-Schmidt algorithm can be applied towards lattice sampling in quadratic time using only linear space. The main idea is that rather than pre-computing and storing the Gram-Schmidt vectors, one can compute them " on-the-fly " while running the
Type de document :
Communication dans un congrès
Eurocrypt 2015, May 2015, Sofia, Bulgaria. Springer Verlag, Advances in Cryptology - EUROCRYPT 2015, LNCS, 2015, 〈10.1007/978-3-662-46800-5_30〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01235176
Contributeur : Vadim Lyubashevsky <>
Soumis le : samedi 28 novembre 2015 - 18:21:45
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : samedi 29 avril 2017 - 00:23:21

Fichier

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

Identifiants

Collections

Citation

Vadim Lyubashevsky, Thomas Prest. Quadratic Time, Linear Space Algorithms for Gram-Schmidt Orthogonalization and Gaussian Sampling in Structured Lattices. Eurocrypt 2015, May 2015, Sofia, Bulgaria. Springer Verlag, Advances in Cryptology - EUROCRYPT 2015, LNCS, 2015, 〈10.1007/978-3-662-46800-5_30〉. 〈hal-01235176〉

Partager

Métriques

Consultations de la notice

178

Téléchargements de fichiers

119