## Black-Box Constructions for Secure Computation

### Yuval Ishai, Eyal Kushilevitz, Yehuda Lindell and Erez Petrank

### Abstract:

It is well known that the secure computation of non-trivial
functionalities in the setting of no 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., one-way trapdoor permutation) in a *black-box* way,
or must it be *nonblack-box* (by referring to the code that
computes this primitive)? Despite the fact that many general
constructions of cryptographic schemes (e.g., CPA-secure
encryption) refer to the underlying primitive in a black-box way
only, 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 present protocols that use only *black-box*
access to a family of (enhanced) trapdoor permutations or to a
homomorphic public-key encryption scheme. The result is a protocol
whose communication complexity is *independent* of the
computational complexity of the underlying primitive (e.g., a
trapdoor permutation) and whose computational complexity grows
only *linearly* with that of the underlying primitive. This
is the first protocol to exhibit these properties.

Postscript, gzipped Postscript.

Back Home