Cryptology ePrint Archive: Report 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.

Category / Keywords: lossy trapdoor functions, public-key encryption, chosen-ciphertext attack

Date: received 29 Oct 2009, last revised 29 Oct 2009

Contact author: syilek at cs ucsd edu

Available format(s): PDF | BibTeX Citation

Version: 20091102:203003 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]