Skip to Main content Skip to Navigation
Conference papers

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
Document type :
Conference papers
Complete list of metadata
Contributor : Vadim Lyubashevsky <>
Submitted on : Saturday, November 28, 2015 - 6:21:45 PM
Last modification on : Tuesday, May 4, 2021 - 2:06:02 PM
Long-term archiving on: : Saturday, April 29, 2017 - 12:23:21 AM


Files produced by the author(s)




Vadim Lyubashevsky, Thomas Prest. Quadratic Time, Linear Space Algorithms for Gram-Schmidt Orthogonalization and Gaussian Sampling in Structured Lattices. Eurocrypt 2015, IACR, May 2015, Sofia, Bulgaria. ⟨10.1007/978-3-662-46800-5_30⟩. ⟨hal-01235176⟩



Record views


Files downloads