International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Lossy Trapdoor Functions and Their Applications

Authors:
Chris Peikert
Brent Waters
Download:
URL: http://eprint.iacr.org/2007/279
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2007-13560,
  title={Lossy Trapdoor Functions and Their Applications},
  booktitle={IACR Eprint archive},
  keywords={},
  url={http://eprint.iacr.org/2007/279},
  note={ bwaters@csl.sri.com 13843 received 20 Jul 2007, last revised 26 Nov 2007},
  author={Chris Peikert and Brent Waters},
  year=2007
}