Paper 2015/257
Quadratic Time, Linear Space Algorithms for GramSchmidt Orthogonalization and Gaussian Sampling in Structured Lattices
Vadim Lyubashevsky and Thomas Prest
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 timeefficient (quadratictime) variant requires the storage of the GramSchmidt 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 linearstorage when working on lattices used in ideallattice cryptography. The reduced storage directly leads to a reduction in keysizes by a factor of $\Omega(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 GramSchmidt 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 ddimensional vector $b$, our algorithm for computing the orthogonalization of $(b,r(b),r^2(b),...,r^{d1}(b))$ uses $O(d^2)$ floating point operations. This is in contrast to $O(d^3)$ such operations that are required by the standard GramSchmidt algorithm. This improvement is directly applicable to bases that appear in ideallattice cryptography because those bases exhibit such ``isometric structure''. The abovementioned algorithm improves on a previous one of Gama, HowgraveGraham, Nguyen (EUROCRYPT 2006) which used different techniques to achieve only a constantfactor speedup for similar lattice bases. Interestingly, our present ideas can be combined with those from Gama et al. to achieve an even an larger practical speedup. We next show how this new GramSchmidt algorithm can be applied towards lattice sampling in quadratic time using only linear space. The main idea is that rather than precomputing and storing the GramSchmidt vectors, one can compute them ``onthefly'' while running the sampling algorithm. We also rigorously analyze the required arithmetic precision necessary for achieving negligible statistical distance between the outputs of our sampling algorithm and the desired Gaussian distribution. The results of our experiments involving NTRU lattices show that the practical performance improvements of our algorithms are as predicted in theory.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published by the IACR in EUROCRYPT 2015
 Keywords
 Latticebased CryptographyLattice TechniquesGaussian SamplingGramSchmidt OrthogonalizationIdeal Lattices
 Contact author(s)
 thomas prest @ ens fr
 History
 20150320: received
 Short URL
 https://ia.cr/2015/257
 License

CC BY
BibTeX
@misc{cryptoeprint:2015/257, author = {Vadim Lyubashevsky and Thomas Prest}, title = {Quadratic Time, Linear Space Algorithms for GramSchmidt Orthogonalization and Gaussian Sampling in Structured Lattices}, howpublished = {Cryptology ePrint Archive, Paper 2015/257}, year = {2015}, note = {\url{https://eprint.iacr.org/2015/257}}, url = {https://eprint.iacr.org/2015/257} }