Adaptively Secure
Multi-Party Computation with Dishonest Majority
Sanjam Garg (UCLA)
Amit Sahai (UCLA)
Abstract:
Adaptively secure multiparty computation is an essential and fundamental notion
in cryptography. In this work we focus on the basic question of constructing
a multiparty computation protocol secure against a malicious, adaptive
adversary in the stand-alone
setting without honest majority in the plain model.
It has been believed that this question can be resolved
by composing known protocols from the literature. We show that in fact, this
belief is fundamentally mistaken. In particular, we show:
- Round inefficiency is unavoidable
when using black-box simulation: There does not exist any $o(\frac{n}{\log{n}})$ round
protocol that adaptively securely realizes a (natural) $n$-party
functionality with a black-box simulator. Note that most previously known
protocols in the adaptive security setting relied on black-box simulators.
- A constant round protocol using non-black-box simulation: We
construct a constant round
adaptively secure multiparty computation protocol in a setting without honest majority that makes crucial use
of non-black box techniques.
Taken together, these results give the first resolution to the question of
adaptively secure multiparty computation protocols with a malicious dishonest
majority in the plain model, open since the first formal treatment of
adaptive security for multiparty computation in 1996.