International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Black-Box Constructions of Protocols for Secure Computation

Iftach Haitner
Yuval Ishai
Eyal Kushilevitz
Yehuda Lindell
Erez Petrank
Search ePrint
Search Google
Abstract: 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.
  title={Black-Box Constructions of Protocols for Secure Computation},
  booktitle={IACR Eprint archive},
  keywords={foundations / black-box constructions, oblivious transfer, semi-honest to malicious, defensible adversaries},
  note={This paper is a combined full version of the papers of Ishai, Kushilevitz, Lindell and Petrank from STOC 2006 and Haitner from TCC 2008. 14695 received 27 Mar 2010},
  author={Iftach Haitner and Yuval Ishai and Eyal Kushilevitz and Yehuda Lindell and Erez Petrank},