November 19, 2007 | Craig Gentry, Chris Peikert, Vinod Vaikuntanathan
The paper presents a method to construct various cryptographic tools, such as trapdoor functions with preimage sampling, efficient digital signature schemes, universally composable oblivious transfer, and identity-based encryption, based on the hardness of standard lattice problems. The core technique involves an efficient algorithm that samples from a Gaussian-like probability distribution over arbitrary lattices, given a basis. This algorithm is crucial for the security of the cryptographic constructions, as it ensures that the output distribution is oblivious to the geometry of the given basis. The paper also discusses the theoretical foundations of these constructions, including the smoothing parameter and the discrete Gaussian distribution, and provides detailed proofs for the correctness and security of the proposed methods.The paper presents a method to construct various cryptographic tools, such as trapdoor functions with preimage sampling, efficient digital signature schemes, universally composable oblivious transfer, and identity-based encryption, based on the hardness of standard lattice problems. The core technique involves an efficient algorithm that samples from a Gaussian-like probability distribution over arbitrary lattices, given a basis. This algorithm is crucial for the security of the cryptographic constructions, as it ensures that the output distribution is oblivious to the geometry of the given basis. The paper also discusses the theoretical foundations of these constructions, including the smoothing parameter and the discrete Gaussian distribution, and provides detailed proofs for the correctness and security of the proposed methods.