Lossy Trapdoor Functions and Their Applications

We propose a new general primitive called lossy trapdoor functions (lossy TDFs), and realize it under a variety of dierent number theoretic assumptions, including hardness of the decisional Die-Hellman (DDH) problem and the worst-case hardness of lattice problems. Using lossy TDFs, we develop a new approach for constructing several important crypto- graphic primitives, including (injective) trapdoor functions, collision-resistant hash functions, oblivious transfer, and chosen ciphertext-secure cryptosystems. All of the constructions are simple, ecient, and black-box. These results resolve some long-standing open problems in cryptography. They give the first known injective trapdoor functions based on problems not directly related to integer factor- ization, and provide the first known CCA-secure cryptosystem based solely on the worst-case complexity of lattice problems.