Founding crytpography on oblivious transfer

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.

REFERENCES

• AF: Abadi, Martin, Joan Feigenbaum, "A Simple and Efficient Protocol for Secure Circuit Computation,'' to appear.
• AL: Angluin, Dana and David Lichtenstein. "Provable Security of Cryptosystems: a Survey," YALEU/DCS/TR-288, 1983.
• B: D A Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.1-5, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12131]
• BC: Brassard, Gilles and Claude Cr~peau. "Zero-Knowledge Simulation of Boolean Circuits,'' Proceedings of the 27th FOCS, IEEE, 1986, 188-195.
• BGKW: Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Widgerson, Multi-prover interactive proofs: how to remove intractability assumptions, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.113-131, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62223]
• BHZ: R. B. Boppana , J. Hastad , S. Zachos, Does co-NP have short interactive proofs?, Information Processing Letters, v.25 n.2, p.127-132, 6 May 1987 [doi>10.1016/0020-0190(87)90232-8]
• C: Cripeau Claude, "On the Equivalence of Two Types of Oblivious Transfer", Crypto87.
• CCD: D. Chaum, C. Crdpeau and I. Damgard, Multiparty unconditionally secure protocols, These proceedings.
• CDG: David Chaum , Ivan Damgård , Jeroen van de Graaf, Multiparty Computations Ensuring Privacy of Each Party's Input and Correctness of the Result, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.87-119, August 16-20, 1987
• EGL: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• For: L. Fortnow, The complexity of perfect zero-knowledge, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.204-209, January 1987, New York, New York, United States [doi>10.1145/28395.28418]
• FRS: Fortnow, Lance, Mike Sipser, John Rompel, "On the Power of Multi-Prover Interactive Proof Systems," to appear.
• 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.
• GMR: S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
• 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.
• GMW2: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• GV: Oded Goldreich , Ronen Vainish, How to Solve any Protocol Problem - An Efficiency Improvement, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.73-86, August 16-20, 1987
• M: Micali, Silvio, Personal Communication.
• R: Rabin, M., "How to exchange secrets by oblivious transfer", Tech. Memo TR-81, Aiken Computation Laboratory, Harvard University, 1981.
• Y: Yao, Andrew C. "How to Generate and Exchange Secrets," Proceedings of the 27th FOGS, IEEE, 1986, 162-167.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Algorithms, Design, Performance, Security, Theory