November 19, 2007 | Craig Gentry, Chris Peikert, Vinod Vaikuntanathan
This paper presents a method for constructing cryptographic tools based on the worst-case hardness of standard lattice problems. The authors show how to build trapdoor functions with preimage sampling, efficient digital signature schemes, universally composable oblivious transfer, and identity-based encryption using lattice-based assumptions. A key component is an efficient algorithm that samples lattice points from a Gaussian-like distribution, which is oblivious to the geometry of the lattice basis. The algorithm is based on a randomized variant of Babai's nearest-plane algorithm, and uses the concept of smoothing parameters to ensure statistical closeness to a discrete Gaussian distribution. The paper also discusses the implications of these results for cryptographic constructions, including the use of lattice-based encryption and digital signatures, and highlights the advantages of lattice-based cryptography over other approaches. The authors demonstrate that their constructions are secure under standard lattice assumptions and provide detailed proofs of their results.This paper presents a method for constructing cryptographic tools based on the worst-case hardness of standard lattice problems. The authors show how to build trapdoor functions with preimage sampling, efficient digital signature schemes, universally composable oblivious transfer, and identity-based encryption using lattice-based assumptions. A key component is an efficient algorithm that samples lattice points from a Gaussian-like distribution, which is oblivious to the geometry of the lattice basis. The algorithm is based on a randomized variant of Babai's nearest-plane algorithm, and uses the concept of smoothing parameters to ensure statistical closeness to a discrete Gaussian distribution. The paper also discusses the implications of these results for cryptographic constructions, including the use of lattice-based encryption and digital signatures, and highlights the advantages of lattice-based cryptography over other approaches. The authors demonstrate that their constructions are secure under standard lattice assumptions and provide detailed proofs of their results.