Cryptology ePrint Archive: Report 2010/164

Black-Box Constructions of Protocols for Secure Computation

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

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.

Category / Keywords: foundations / black-box constructions, oblivious transfer, semi-honest to malicious, defensible adversaries

Publication Info: This paper is a combined full version of the papers of Ishai, Kushilevitz, Lindell and Petrank from STOC 2006 and Haitner from TCC 2008.

Date: received 27 Mar 2010, last revised 12 Dec 2010

Contact author: lindell at cs biu ac il

Available format(s): PDF | BibTeX Citation

Version: 20101212:092351 (All versions of this report)

Short URL: ia.cr/2010/164

Discussion forum: Show discussion | Start new discussion