Relationship between public key encryption and oblivious transfer

Yael Gertner, Sampath Kannan, Tal Malkin, Omer Reingold, Mahesh Viswanathan

Research output: Contribution to journalConference articlepeer-review


In this paper we study the relationships among some of the most fundamental primitives and protocols in cryptography: public-key encryption (i.e. trapdoor predicates), oblivious transfer (which is equivalent to general secure multiparty computation), key agreement and trapdoor permutations. Our main results show that public-key encryption and oblivious transfer are incomparable under black-box reductions. These separations are tightly matched by our positive results where a restricted (strong) version of one primitive does imply the other primitive. We also show separations between oblivious transfer and key agreement. Finally, we conclude that neither oblivious transfer nor trapdoor predicates imply trapdoor permutations. Our techniques for showing negative results follow the oracle separations of Impagliazzo and Rudich.

Original languageEnglish (US)
Pages (from-to)325-335
Number of pages11
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - 2000
Externally publishedYes
Event41st Annual Symposium on Foundations of Computer Science (FOCS 2000) - Redondo Beach, CA, USA
Duration: Nov 12 2000Nov 14 2000

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'Relationship between public key encryption and oblivious transfer'. Together they form a unique fingerprint.

Cite this