Bellare, Halevi, Sahai and Vadhan (CRYPTO '98) showed that if E is an IND-CPA secure cryptosystem, and $H$ is a random oracle, then $x \mapsto E(x,H(x))$ is an injective trapdoor function. In this work, we show that if E is a lossy encryption with messages at least 1-bit longer than randomness, and $h$ is a pairwise independent hash function, then $x \mapsto E(x,h(x))$ is a lossy trapdoor function, and hence also an injective trapdoor function. The works of Peikert, Vaikuntanathan and Waters and Hemenway, Libert, Ostrovsky and Vergnaud showed that statistically-hiding 2-round Oblivious Transfer (OT) is equivalent to Lossy Encryption. In their construction, if the sender randomness is shorter than the message in the OT, it will also be shorter than the message in the lossy encryption. This gives an alternate interpretation of our main result. In this language, we show that any 2-message statistically sender-private semi-honest oblivious transfer (OT) for strings longer than the sender randomness implies the existence of injective one-way trapdoor functions. This is in contrast to the black box separation of injective trapdoor functions from many common cryptographic protocols, e.g. IND-CCA encryption.
Category / Keywords: public-key cryptography / lossy trapdoor functions, decisional composite residuosity, randomness dependent message security Original Publication (with minor differences): IACR-ASIACRYPT-2013 Date: received 24 Feb 2015 Contact author: fbrett at cis upenn edu Available format(s): PDF | BibTeX Citation Version: 20150227:213640 (All versions of this report) Short URL: ia.cr/2015/156 Discussion forum: Show discussion | Start new discussion