Paper 2010/164

Black-Box Constructions of Protocols for Secure Computation

Iftach Haitner, Yuval Ishai, Eyal Kushilevitz, Yehuda Lindell, and Erez Petrank


It is well known that secure computation without an honest majority requires computational assumptions. An interesting question that therefore arises relates to the way such computational assumptions are used. Specifically, can the secure protocol use the underlying primitive (e.g., a one-way trapdoor permutation) in a {\em black-box} way, treating it as an oracle, or must it be {\em nonblack-box} (by referring to the code that computes the primitive)? Despite the fact that many general constructions of cryptographic schemes refer to the underlying primitive in a black-box wayonly, there are some constructions that are inherently nonblack-box. Indeed, all known constructions of protocols for general secure computation that are secure in the presence of a malicious adversary and without an honest majority use the underlying primitive in a nonblack-box way (requiring to prove in zero-knowledge statements that relate to the primitive). In this paper, we study whether such nonblack-box use is essential. We answer this question in the negative. Concretely, we present a \emph{fully black-box reduction} from oblivious transfer with security against malicious parties to oblivious transfer with security against semi-honest parties. As a corollary, we get the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which only make a {\em black-box} use of semi-honest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption.

Available format(s)
Publication info
Published elsewhere. This paper is a combined full version of the papers of Ishai, Kushilevitz, Lindell and Petrank from STOC 2006 and Haitner from TCC 2008.
black-box constructionsoblivious transfersemi-honest to maliciousdefensible adversaries
Contact author(s)
lindell @ cs biu ac il
2010-12-12: revised
2010-03-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Iftach Haitner and Yuval Ishai and Eyal Kushilevitz and Yehuda Lindell and Erez Petrank},
      title = {Black-Box Constructions of Protocols for Secure Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2010/164},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.