Trapdoors for hard lattices and new cryptographic constructions

摘要: We show how to construct a variety of "trapdoor" cryptographic tools assuming the worst-case hardness standard lattice problems (such as approximating length shortest nonzero vector within certain polynomial factors). Our contributions include new notion trapdoor function with preimage sampling, simple and efficient "hash-and-sign" digital signature schemes, identity-based encryption. A core technical component our constructions is an algorithm that, given basis arbitrary lattice, samples points from discrete Gaussian probability distribution whose deviation essentially longest Gram-Schmidt basis. crucial security property that output oblivious particular geometry