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

DOI10.1007/978-3-662-46800-5_30MaRDI QIDQ2948355zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(6)

• Fast Fourier orthogonalization
• Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space
• Fast Fourier Orthogonalization over NTRU Lattices
• 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

Describes a project that uses

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)