Joe Kilian
ABSTRACT
Suppose your netmail is being erratically censored by Captain Yossarian. Whenever you send a message, he censors each bit of the message with probability 1/2, replacing each censored bit by some reserved character. Well versed in such concepts as redundancy, this is no real problem to you. The question is, can it actually be turned around and used to your advantage? We answer this question strongly in the affirmative. We show that this protocol, more commonly known as oblivious transfer, can be used to simulate a more sophisticated protocol, known as oblivious circuit evaluation([Y]). We also show that with such a communication channel, one can have completely noninteractive zero-knowledge proofs of statements in NP. These results do not use any complexity-theoretic assumptions. We can show that they have applications to a variety of models in which oblivious transfer can be done.
- AF.Abadi, Martin, Joan Feigenbaum, "A Simple and Efficient Protocol for Secure Circuit Computation,'' to appear.Google Scholar
- AL.Angluin, Dana and David Lichtenstein. "Provable Security of Cryptosystems: a Survey," YALEU/DCS/TR-288, 1983.Google Scholar
- B.Barrington, D. "Bounded Width Polynomial Size Branching Programs Recognize Exactly Those Languages in NCTM, Proceedings of I8th STOC, 1986, pp. 1-5. Google ScholarDigital Library
- BC.Brassard, Gilles and Claude Cr~peau. "Zero-Knowledge Simulation of Boolean Circuits,'' Proceedings of the 27th FOCS, IEEE, 1986, 188-195.Google Scholar
- BGKW.Ben-Or, Michael, Shaft Goldwasser, Joe Kilian, and Avi Wigderson, "Multi-Prover interactive Proof Systems, Removing Intractibility Assumptions," These proceedings. Google ScholarDigital Library
- BHZ.Boppana, Ravi, Johan Hastad, and Stathis Zachos. "Does CoNP Have Short Interactive Proofs?," IPL, 25, 1987, 127-132. Google ScholarDigital Library
- C.Cripeau Claude, "On the Equivalence of Two Types of Oblivious Transfer", Crypto87.Google Scholar
- CCD.D. Chaum, C. Crdpeau and I. Damgard, Multiparty unconditionally secure protocols, These proceedings.Google Scholar
- CDG.Chaum, David, Ivan Damgard, and Jeroen van de Graaf. "Multiparty Computations Ensuring Secrecy of Each Party's Input and Correctness of the Output," Proceedings of CRYPTO '87. Proceedings of CRYPTO '85, Springer- Voting, 1986, 477-488. Google ScholarDigital Library
- EGL.Even S., Goldreich O., and A. Lempel, A Randomized Protocol for Signing Contracts, CACM, vol. 28, no. 6, 1985, pp. 637-647. Google ScholarDigital Library
- For.Fortnow, Lance. "The Complexity of Perfect Zero-Knowledge," Proceedings of the 19ta STOC, ACM, 1987, 204-209. Google ScholarDigital Library
- FRS.Fortnow, Lance, Mike Sipser, John Rompel, "On the Power of Multi-Prover Interactive Proof Systems," to appear.Google Scholar
- GHY.Galil Z., Haber S., and Yung M., "A Prirate Interactive Test of ~ Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystem", Proceedings of the ~6th FOGS, 1985, pp. 360-371.Google Scholar
- GMR.Goldwasser, Shaft, Silvio Micali, and Charles Rackoff. "The Knowledge Complexity of Interactive Proof-Systems," Proceedings of the 17ta STOC, ACM, 1985, 291-304. Google ScholarDigital Library
- GMW1.Goldreich, Oded, Silvio Micali, and A- vi Wigderson. "Proofs that Yield Nothing but the Validity of the Assertion, and a Methodology of Cryptographic Protocol Design," Proceedings of the 27th FOGS, IEEE, 1986, 174-187.Google Scholar
- GMW2.Goldreich, Oded, Silvio Micali, and Avi Wigderson. "How to Play ANY Mental Game," Proceedings of the 19th STOC, ACM, 1987, 218- 229. Google ScholarDigital Library
- GV.Goldreich, O., Vainish, R. "How to Solve any Protocol Problem: An Efficiency Improvement'', Crypto 87. Google ScholarDigital Library
- M.Micali, Silvio, Personal Communication.Google Scholar
- R.Rabin, M., "How to exchange secrets by oblivious transfer", Tech. Memo TR-81, Aiken Computation Laboratory, Harvard University, 1981.Google Scholar
- Y.Yao, Andrew C. "How to Generate and Exchange Secrets," Proceedings of the 27th FOGS, IEEE, 1986, 162-167.Google Scholar
Index Terms
- Founding crytpography on oblivious transfer
Recommendations
Founding Cryptography on Oblivious Transfer --- Efficiently
CRYPTO 2008: Proceedings of the 28th Annual conference on Cryptology: Advances in CryptologyWe present a simple and efficient compiler for transforming secure multi-party computation (MPC) protocols that enjoy security only with an honest majority into MPC protocols that guarantee security with no honest majority, in the oblivious-transfer (OT)...
Computationally Secure Oblivious Transfer
We describe new computationally secure protocols of 1-out-of-N oblivious transfer, k-out-of-N oblivious transfer, and oblivious transfer with adaptive queries. The protocols are very efficient compared with solutions based on generic two-party ...
More Efficient Oblivious Transfer Extensions
Oblivious transfer (OT) is one of the most fundamental primitives in cryptography and is widely used in protocols for secure two-party and multi-party computation. As secure computation becomes more practical, the need for practical large-scale OT ...
Comments