Black-Box, Round-Efficient Secure Computation
via Non-Malleability Amplification
Hoeteck Wee
Queens College, CUNY
hoeteck@cs.qc.cuny.edu
Abstract
We present round-efficient protocols for secure multi-party computation
with a dishonest majority that rely on black-box access to the underlying
primitives. Our main contributions are:
• a O(log
∗
n)-round protocol that relies on black-box access to dense
cryptosystems, homomorphic encryption schemes, or lossy encryption
schemes. This improves upon the recent O(1)
log
∗
n
-round protocol
of Lin, Pass and Venkitasubramaniam (STOC 2009) that relies on
non-black-box access to a smaller class of primitives.
• a O(1)-round protocol requiring in addition, black-box access to a
one-way function with sub-exponential hardness, improving upon the
recent work of Pass and Wee (Eurocrypt 2010).
These are the first black-box constructions for secure computation with
sublinear round complexity. Our constructions build on and improve upon
the work of Lin and Pass (STOC 2009) on non-malleability amplification, as
well as that of Ishai et al. (STOC 2006) on black-box secure computation.
In addition to the results on secure computation, we also obtain
a simple construction of a O(log
∗
n)-round non-malleable commitment
scheme based on one-way functions, improving upon the recent O(1)
log
∗
n
-
round protocol of Lin and Pass (STOC 2009). Our construction uses a
novel transformation for handling arbitrary man-in-the-middle scheduling
strategies which improves upon a previous construction of Barak (FOCS
2002).
Keywords- secure multi-party computation, round complexity, black-
box constructions, non-malleable commitments.
1. Introduction
Secure multi-party computation (MPC) allows several
mutually distrustful parties to perform a joint computation
without compromising, to the greatest extent possible, the
privacy of their inputs or the correctness of the outputs.
The early work of Goldreich, Micali and Wigderson [13]
showed that we may realize secure multi-party computa-
tion with a dishonest majority under general cryptographic
assumptions. Over the last decade, substantial progress
was made towards improving the round complexity and
computational efficiency of these protocols in two separate
lines of works, culminating in (1) constant-round protocols
for secure computation [18, 23, 27, 31] as well as (2) black-
box constructions that avoid the use of (typically expensive)
Supported in part by NSF CAREER Award CNS-0953626 and PSC-CUNY
Award # 63888-00 41.
general NP reductions [8, 14, 16, 17, 19]. However, simulta-
neously achieving both of these efficiency guarantees has
so far remained quite elusive; the state-of-the-art for black-
box constructions is a O(n)-round protocol where n is
the number of parties.
1
This raises the following natural
question:
Does there exist a black-box, o(n)-round protocol
for secure multi-party computation, or is there an
inherent trade-off between round complexity and
computational efficiency?
Before stating our results, we provide some additional
context and motivation.
Round-efficient secure computation. In the GMW pro-
tocol for secure computation, each player takes turns to
sequentially commit to its input (along with a “proof of
knowledge”); any non-trivial improvement in round com-
plexity will require interweaving these input commitments,
which could potentially allow an adversary to violate in-
put independence via a man-in-the-middle attack. For this
reason, improvements in round complexity for secure com-
putation has often paralleled results on non-malleability [9].
Constant-round MPC protocols were first obtained by Katz,
Ostrosky and Smith [18] (relying on [2]) and by Pass [27]
based on the existence of enhanced trapdoor permutations
and in addition, collision-resistant hash functions. More
recently, Lin, Pass and Venkitasubramaniam [20, 23] showed
that the latter assumption can be eliminated while still
maintaining almost constant – specifically, O(1)
log
∗
n
–
round complexity. In follow-up work, Pass and Wee [31]
gave a constant-round protocol, assuming in addition one-
way functions with sub-exponential hardness. An advantage
of these latter two works is that they avoid the use of
non-black-box simulation techniques [1] along with the
sophisticated machinery (e.g. the PCP theorem) associated
with them.
1. Throughout the introduction, we use n to denote the number of parties;
in particular, the round complexity of all the protocols we discuss here
depends only on the number of parties, and is independent of the security
parameter.
