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
-
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},
url = {https://eprint.iacr.org/2009/524}
}
