SPEAKER:
Carl Bosely

TITLE:
Lossy Trapdoor Functions and Their Applications - Part I

AUTHORS:
Chris Peikert and Brent Waters (Proc. of STOC 2008)

ABSTRACT:
We propose a general cryptographic primitive called lossy trapdoor functions (lossy TDFs), and use it
to develop new approaches for constructing several important cryptographic tools, including (injective)
trapdoor functions, collision-resistant hash functions, oblivious transfer, and chosen ciphertext-secure
cryptosystems (in the standard model). All of these constructions are simple, efficient, and black-box.

We realize lossy TDFs 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
for quantum algorithms (alternately, under an average-case hardness assumption for classical algorithms).

Taken together, our 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 chosen ciphertext-secure cryptosystem based solely on worst-case complexity
assumptions.

ONLINE VERSION:
http://people.csail.mit.edu/cpeikert/pubs/lossy_tdf.pdf