Quadratic time, linear space algorithms for Gram-Schmidt orthogonalization and Gaussian sampling in structured lattices

DOI10.1007/978-3-662-46800-5_30zbMATH Open1370.94532OpenAlexW2151785200MaRDI QIDQ2948355FDOQ2948355

Authors: Vadim Lyubashevsky, Thomas Prest 

Publication date: 30 September 2015

Published in: Advances in Cryptology -- EUROCRYPT 2015 (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01235176/file/Fast_Gram_Schmidt_paper.pdf

Recommendations

• An efficient and parallel Gaussian sampler for lattices
• Gaussian sampling of lattices for cryptographic applications
• Integral matrix Gram root and lattice Gaussian sampling without floats
• Simple Lattice Trapdoor Sampling from a Broad Class of Distributions
• Faster Gaussian lattice sampling using lazy floating-point arithmetic

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Cryptography (94A60)

Cited In (6)

• Fast Fourier Orthogonalization over NTRU Lattices
• Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space
• Fast Fourier orthogonalization
• Key recovery from Gram-Schmidt norm leakage in hash-and-sign signatures over NTRU lattices
• The whole is less than the sum of its parts: constructing more efficient lattice-based AKEs
• A linear algebra attack on the non-commuting cryptography class based on matrix power function

Uses Software

• mctoolbox

This page was built for publication: Quadratic time, linear space algorithms for Gram-Schmidt orthogonalization and Gaussian sampling in structured lattices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2948355)