Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-080 | 7th August 2007 00:00

Lossy Trapdoor Functions and Their Applications


Authors: Chris Peikert, Brent Waters
Publication: 17th August 2007 20:00
Downloads: 4175


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.

ISSN 1433-8092 | Imprint