Paper 2012/441

Adaptively Secure Multi-Party Computation with Dishonest Majority

Sanjam Garg and Amit Sahai

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 \emph{malicious}, \emph{adaptive} adversary in the \emph{stand-alone} setting without assuming an 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: \begin{itemize} \item[-]\textbf{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. \item[-]\textbf{A constant round protocol using non-black-box simulation:} We construct a \emph{constant round} adaptively secure multiparty computation protocol in a setting without \emph{honest majority} that makes crucial use of non-black box techniques. \end{itemize} 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.

Note: Full version of CRYPTO 2012 paper.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
adaptive security
Contact author(s)
sanjamg @ cs ucla edu
History
2012-08-05: received
Short URL
https://ia.cr/2012/441
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/441,
      author = {Sanjam Garg and Amit Sahai},
      title = {Adaptively Secure Multi-Party Computation with Dishonest Majority},
      howpublished = {Cryptology ePrint Archive, Paper 2012/441},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/441}},
      url = {https://eprint.iacr.org/2012/441}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.