Brent Waters
SRI International

Lossy Trapdoor Functions and Their Applications

In this talk I'll introduce a new general primitive called lossy
trapdoor functions (lossy TDFs).  Using lossy TDFs, I'll show new
approaches 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.

In addition, I'll describe how to realize lossy TDFs under number
theoretic assumptions, including hardness of the decisional
Diffie-Hellman (DDH) problem and the worst-case hardness of standard
lattice problems.  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

Chris Peikert and Brent Waters