Cryptology ePrint Archive: Report 2007/279

Lossy Trapdoor Functions and Their Applications

Chris Peikert and Brent Waters

Abstract: We propose a new general primitive called lossy trapdoor functions (lossy TDFs), and realize it under a variety of different number theoretic assumptions, including hardness of the decisional Diffie-Hellman (DDH) problem and the worst-case hardness of standard lattice problems.

Using lossy TDFs, we develop a new approach for constructing many important cryptographic primitives, including standard trapdoor functions, CCA-secure cryptosystems, collision-resistant hash functions, and more. All of our constructions are simple, efficient, and black-box.

Taken all together, 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 factorization, and provide the first known CCA-secure cryptosystem based solely on worst-case lattice assumptions.

Category / Keywords:

Date: received 20 Jul 2007, last revised 14 Mar 2008

Contact author: bwaters at csl sri com

Available formats: PDF | BibTeX Citation

Version: 20080315:003913 (All versions of this report)

Discussion forum: Show discussion | Start new discussion