Paper 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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
bwaters @ csl sri com
History
2008-03-15: last of 2 revisions
2007-08-07: received
See all versions
Short URL
https://ia.cr/2007/279
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/279,
      author = {Chris Peikert and Brent Waters},
      title = {Lossy Trapdoor Functions and Their Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2007/279},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/279}},
      url = {https://eprint.iacr.org/2007/279}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.