Welcome to the resource topic for 2012/441
Title:
Adaptively Secure Multi-Party Computation with Dishonest Majority
Authors: Sanjam Garg, 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.
ePrint: https://eprint.iacr.org/2012/441
Talk: https://www.youtube.com/watch?v=GdnLnHpZAB8
Slides: https://iacr.org/cryptodb/archive/2012/CRYPTO/presentation/2-2-Garg.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .