Paper 2009/524

Chosen-Ciphertext Security from Slightly Lossy Trapdoor Functions

Petros Mol and Scott Yilek

Abstract

Lossy Trapdoor Functions (LTDFs), introduced by Peikert and Waters (STOC 2008) have been useful for building many cryptographic primitives. In particular, by using an LTDF that loses a (1-1/omega(log n)) fraction of all its input bits, it is possible to achieve CCA security using the LTDF as a black-box. Unfortunately, not all candidate LTDFs achieve such a high level of lossiness. In this paper we drastically improve upon previous results and show that an LTDF that loses only a non-negligible fraction of a single bit can be used in a black-box way to build numerous cryptographic primitives, including one-way injective trapdoor functions, CPA secure public-key encryption (PKE), and CCA-secure PKE. We then describe a novel technique for constructing such slightly-lossy LTDFs and give a construction based on modular squaring.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
lossy trapdoor functionspublic-key encryptionchosen-ciphertext attack
Contact author(s)
syilek @ cs ucsd edu
History
2009-11-02: received
Short URL
https://ia.cr/2009/524
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/524,
      author = {Petros Mol and Scott Yilek},
      title = {Chosen-Ciphertext Security from Slightly Lossy Trapdoor Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2009/524},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/524}},
      url = {https://eprint.iacr.org/2009/524}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.