Paper 2019/320
Integral Matrix Gram Root and Lattice Gaussian Sampling without Floats
Léo Ducas, Steven Galbraith, Thomas Prest, and Yang Yu
Abstract
Many advanced lattice based cryptosystems require to sample lattice points from Gaussian distributions. One challenge for this task is that all current algorithms resort to floatingpoint arithmetic (FPA) at some point, which has numerous drawbacks in practice: it requires numerical stability analysis, extra storage for highprecision, lazy/backtracking techniques for efficiency, and may suffer from weak determinism which can completely break certain schemes. In this paper, we give techniques to implement Gaussian sampling over general lattices without using FPA. To this end, we revisit the approach of Peikert, using perturbation sampling. Peikert's approach uses continuous Gaussian sampling and some decomposition $\mathbf{\Sigma} = \mathbf{A} \mathbf{A}^t$ of the target covariance matrix $\mathbf{\Sigma}$. The suggested decomposition, e.g. the Cholesky decomposition, gives rise to a square matrix $\mathbf{A}$ with real (not integer) entries. Our idea, in a nutshell, is to replace this decomposition by an integral one. While there is in general no integer solution if we restrict $\mathbf{A}$ to being a square matrix, we show that such a decomposition can be efficiently found by allowing $\mathbf{A}$ to be wider (say $n \times 9n$). This can be viewed as an extension of Lagrange's foursquare theorem to matrices. In addition, we adapt our integral decomposition algorithm to the ring setting: for powerof2 cyclotomics, we can exploit the tower of rings structure for improved complexity and compactness.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 A minor revision of an IACR publication in EUROCRYPT 2020
 Keywords
 Lattice based cryptographyDiscrete Gaussian samplingMatrix decomposition
 Contact author(s)

ducas @ cwi nl
s galbraith @ auckland ac nz
thomas prest @ pqshield com
yang yu0986 @ gmail com  History
 20200530: last of 6 revisions
 20190329: received
 See all versions
 Short URL
 https://ia.cr/2019/320
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/320, author = {Léo Ducas and Steven Galbraith and Thomas Prest and Yang Yu}, title = {Integral Matrix Gram Root and Lattice Gaussian Sampling without Floats}, howpublished = {Cryptology ePrint Archive, Paper 2019/320}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/320}}, url = {https://eprint.iacr.org/2019/320} }