publication . Conference object . Part of book or chapter of book . 2015

Quadratic Time, Linear Space Algorithms for Gram-Schmidt Orthogonalization and Gaussian Sampling in Structured Lattices

Lyubashevsky, Vadim; Prest, Thomas;
Open Access English
  • Published: 01 May 2015
  • Publisher: HAL CCSD
  • Country: France
Abstract
International audience; 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 time-efficient (quadratic-time) variant requires the storage of the Gram-Schmidt 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 linear-storage when ...
Subjects
free text keywords: [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR]
Funded by
EC| SAFEcrypto
Project
SAFEcrypto
Secure Architectures of Future Emerging Cryptography
  • Funder: European Commission (EC)
  • Project Code: 644729
  • Funding stream: H2020 | RIA
24 references, page 1 of 2

[ABB10] Shweta Agrawal, Dan Boneh, and Xavier Boyen. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. In Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings, pages 98-115, 2010.

[Bab86] La´szlo´ Babai. On lova´sz' lattice reduction and the nearest lattice point problem. Combinatorica, 6(1):1-13, 1986.

[BGG+14] Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, and Dhinakaran Vinayagamurthy. Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits. In Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings, pages 533-556, 2014.

[Boy10] Xavier Boyen. Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more. In Public Key Cryptography, pages 499-517, 2010. [OpenAIRE]

[CHKP10] David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. Bonsai trees, or how to delegate a lattice basis. In EUROCRYPT, pages 523-552, 2010.

[DDLL13] L´eo Ducas, Alain Durmus, Tancr`ede Lepoint, and Vadim Lyubashevsky. Lattice signatures and bimodal gaussians. In CRYPTO (1), pages 40-56, 2013.

[DLP14] L´eo Ducas, Vadim Lyubashevsky, and Thomas Prest. Efficient identitybased encryption over NTRU lattices. In Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014, Proceedings, Part II, pages 22-41, 2014.

[Gal12] Steven D. Galbraith. Mathematics of Public Key Cryptography. Cambridge University Press, New York, NY, USA, 1st edition, 2012.

[GHN06] Nicolas Gama, Nick Howgrave-Graham, and Phong Q. Nguyen. Symplectic lattice reduction and ntru. In Proceedings of the 24th Annual International Conference on The Theory and Applications of Cryptographic Techniques, EUROCRYPT'06, pages 233-253, Berlin, Heidelberg, 2006. Springer-Verlag.

[GPV08] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, pages 197- 206, 2008.

[Hig02] Nicholas J. Higham. Accuracy and Stability of Numerical Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2nd edition, 2002.

[HPS98] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A ring-based public key cryptosystem. In ANTS, pages 267-288, 1998. [OpenAIRE]

[Kle00] Philip N. Klein. Finding the closest lattice vector when it's unusually close. In SODA, pages 937-941, 2000.

[LLL82] A. K. Lenstra, H. W. Lenstra, and L. Lova´sz. Factoring polynomials with rational coefficients. Mathematische Annalen, 261:515-534, 1982. [OpenAIRE]

[LM06] Vadim Lyubashevsky and Daniele Micciancio. Generalized compact knapsacks are collision resistant. In ICALP (2), pages 144-155, 2006.

24 references, page 1 of 2
Abstract
International audience; 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 time-efficient (quadratic-time) variant requires the storage of the Gram-Schmidt 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 linear-storage when ...
Subjects
free text keywords: [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR]
Funded by
EC| SAFEcrypto
Project
SAFEcrypto
Secure Architectures of Future Emerging Cryptography
  • Funder: European Commission (EC)
  • Project Code: 644729
  • Funding stream: H2020 | RIA
24 references, page 1 of 2

[ABB10] Shweta Agrawal, Dan Boneh, and Xavier Boyen. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. In Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings, pages 98-115, 2010.

[Bab86] La´szlo´ Babai. On lova´sz' lattice reduction and the nearest lattice point problem. Combinatorica, 6(1):1-13, 1986.

[BGG+14] Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, and Dhinakaran Vinayagamurthy. Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits. In Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings, pages 533-556, 2014.

[Boy10] Xavier Boyen. Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more. In Public Key Cryptography, pages 499-517, 2010. [OpenAIRE]

[CHKP10] David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. Bonsai trees, or how to delegate a lattice basis. In EUROCRYPT, pages 523-552, 2010.

[DDLL13] L´eo Ducas, Alain Durmus, Tancr`ede Lepoint, and Vadim Lyubashevsky. Lattice signatures and bimodal gaussians. In CRYPTO (1), pages 40-56, 2013.

[DLP14] L´eo Ducas, Vadim Lyubashevsky, and Thomas Prest. Efficient identitybased encryption over NTRU lattices. In Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014, Proceedings, Part II, pages 22-41, 2014.

[Gal12] Steven D. Galbraith. Mathematics of Public Key Cryptography. Cambridge University Press, New York, NY, USA, 1st edition, 2012.

[GHN06] Nicolas Gama, Nick Howgrave-Graham, and Phong Q. Nguyen. Symplectic lattice reduction and ntru. In Proceedings of the 24th Annual International Conference on The Theory and Applications of Cryptographic Techniques, EUROCRYPT'06, pages 233-253, Berlin, Heidelberg, 2006. Springer-Verlag.

[GPV08] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, pages 197- 206, 2008.

[Hig02] Nicholas J. Higham. Accuracy and Stability of Numerical Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2nd edition, 2002.

[HPS98] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A ring-based public key cryptosystem. In ANTS, pages 267-288, 1998. [OpenAIRE]

[Kle00] Philip N. Klein. Finding the closest lattice vector when it's unusually close. In SODA, pages 937-941, 2000.

[LLL82] A. K. Lenstra, H. W. Lenstra, and L. Lova´sz. Factoring polynomials with rational coefficients. Mathematische Annalen, 261:515-534, 1982. [OpenAIRE]

[LM06] Vadim Lyubashevsky and Daniele Micciancio. Generalized compact knapsacks are collision resistant. In ICALP (2), pages 144-155, 2006.

24 references, page 1 of 2
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue