Integral Matrix Gram Root and Lattice Gaussian Sampling Without Floats

Autor: Yang Yu, Léo Ducas, Steven D. Galbraith, Thomas Prest
Přispěvatelé: Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands
Jazyk: angličtina
Rok vydání: 2020
Předmět:
Zdroj: Advances in Cryptology – EUROCRYPT 2020
Lecture Notes in Computer Science
Lecture Notes in Computer Science-Advances in Cryptology – EUROCRYPT 2020
Advances in Cryptology – EUROCRYPT 2020 ISBN: 9783030457235
EUROCRYPT (2)
Advances in Cryptology – EUROCRYPT 2020-39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part II
ISSN: 0302-9743
1611-3349
Popis: 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 floating-point arithmetic (FPA) at some point, which has numerous drawbacks in practice: it requires numerical stability analysis, extra storage for high-precision, 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbf {\Sigma }= \mathbf {A}\mathbf {A}^t$$\end{document}Σ=AAt of the target covariance matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbf {\Sigma }$$\end{document}Σ. The suggested decomposition, e.g. the Cholesky decomposition, gives rise to a square matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbf {A}$$\end{document}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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbf {A}$$\end{document}A to being a square matrix, we show that such a decomposition can be efficiently found by allowing \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbf {A}$$\end{document}A to be wider (say \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n \times 9n$$\end{document}n×9n). This can be viewed as an extension of Lagrange’s four-square theorem to matrices. In addition, we adapt our integral decomposition algorithm to the ring setting: for power-of-2 cyclotomics, we can exploit the tower of rings structure for improved complexity and compactness.
Databáze: OpenAIRE
Externí odkaz: