The relationship between public key encryption and oblivious transfer
- 7 November 2002
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
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 multi-party 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 R. Impagliazzo and S. Rudich (1989).Keywords
This publication has 23 references indexed in Scilit:
- Lower bounds on the efficiency of generic cryptographic constructionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systemsJournal of the ACM, 1991
- Bit commitment using pseudorandomnessJournal of Cryptology, 1991
- One-way functions are necessary and sufficient for secure signaturesPublished by Association for Computing Machinery (ACM) ,1990
- Universal one-way hash functions and their cryptographic applicationsPublished by Association for Computing Machinery (ACM) ,1989
- How to generate and exchange secretsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- How to construct random functionsJournal of the ACM, 1986
- A randomized protocol for signing contractsCommunications of the ACM, 1985
- Theory and application of trapdoor functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- New directions in cryptographyIEEE Transactions on Information Theory, 1976