Abstract
Gaussian sampling is the major class of algorithms for solving the close vector problem (CVP) of lattices. In this paper we present a novel Gaussian sampling algorithm, which has the same cryptographic applications with original Gaussian sampling algorithms. Our novel Gaussian sampling algorithm has smaller deviations, meaning smaller space sizes of lattice based public-key ciphers. The shape of our novel algorithm is almost repeated implementations of original algorithm, with random repeating times. Major result is that the deviation can be reduced to 0.64 ∼ 0.75 of that of original Gaussian sampling algorithm without clearly increasing the average time cost.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Goldreich O, Goldwasser S, Halevi S. Public-key cryptosystem from lattice reduction problems. In: Proceedings of CRYPTO’1997, Santa Barbara, 1997. 112–131
Hoffstein J, Howgrave-Graham N, Pipher J, et al. NTRUSign: digital signatures using the NTRU lattice. In: Proceedings of CT-RSA’2003, San Francisco, 2003. 122–140
Szydlo M. Hypercubic lattice reduction and analysis of GGH and NTRU signatures. In: Proceedings of EUROCRYPT’ 2003, Warsaw, 2003. 433–448
Nguyen P Q, Regev O. Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures. In: Proceedings of EUROCRYPT’2006, Saint Petersburg, 2006. 271–288
Hu Y P, Wang B C, He W C. NTRUSign with a new perturbation. IEEE Trans Inf Theory, 2008, 54: 3216–3221
Klein P. Finding the closest lattice vector when it’s unusually close. In: Proceedings of SODA’2000, San Francisco, 2000. 937–941
Gentry C, Peikert C, Vaikuntanathan V. How to use a short basis: trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of STOC’2008, Victoria, 2008. 197–206
Peikert C. An efficient and parallel Gaussian sampler for lattices. In: Proceedings of CRYPTO’2010, Santa Barbara, 2010. 80–97
Babai, Lovász. Lattice reduction and the nearest lattice point problem. Combinatorica, 1986, 6: 1–13
Cash D, Hofheinz D, Kiltz E, et al. Bonsai trees, or how to delegate a lattice basis. In: Proceedings of Eurocrypt’2010, Nice, 2010. 523–552
Agrawal S, Boneh D, Boyen X. Efficient lattice (H)IBE in the standard model. In: Proceedings of Eurocrypt’2010, Nice, 2010. 553–572
Rückert M. Lattice-based blind signatures. In: Proceedings of ASIACRYPT’2010, Singapore, 2010. 413–430
Gordo S D, Katz J, Vaikuntanathan V. A group signature scheme from lattice assumptions. In: Proceedings of ASIACRYPT’2010, Singapore, 2010. 395–412
Rückert M. Strongly ungorgeable signatures and hierarchical identity-based signatures from lattices without random oracles. In: Proceedings of PQCrypto’2010, Darmstadt, 2010. 182–200
Wang F H, Hu Y P, Wang B C. Lattice-based linearly homomorphic signature scheme over binary field. Sci China Inf Sci, 2013, 56: 112108
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hu, Y., Lei, H., Wang, F. et al. Gaussian sampling of lattices for cryptographic applications. Sci. China Inf. Sci. 57, 1–8 (2014). https://doi.org/10.1007/s11432-013-4843-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11432-013-4843-4