Secure Multi-Party Computation in Large Networks
Preprint
Abstract
We describe scalable protocols for solving the secure multi-party computation (MPC) problem among a large number of parties. We consider both the synchronous and the asynchronous communication models. In the synchronous setting, our protocol is secure against a static malicious adversary corrupting less than a $1/3$ fraction of the parties. In the asynchronous setting, we allow the adversary to corrupt less than a $1/8$ fraction of parties. For any deterministic function that can be computed by an arithmetic circuit with $m$ gates, both of our protocols require each party to send a number of field elements and perform an amount of computation that is $\tilde{O}(m/n + \sqrt n)$. We also show that our protocols provide perfect and universally-composable security. To achieve our asynchronous MPC result, we define the \emph{threshold counting problem} and present a distributed protocol to solve it in the asynchronous setting. This protocol is load balanced, with computation, communication and latency complexity of $O(\log{n})$, and can also be used for designing other load-balanced applications in the asynchronous communication model.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Information-Theoretically Secure Protocols and Security under CompositionSIAM Journal on Computing, 2010
- On the composition of authenticated Byzantine AgreementJournal of the ACM, 2006
- Noncryptographic selection protocols2003
- Security and Composition of Multiparty Cryptographic ProtocolsJournal of Cryptology, 2000
- Software protection and simulation on oblivious RAMsJournal of the ACM, 1996
- Adaptively secure multi-party computation1996
- Fast perfect-information leader-election protocols with linear immunityCombinatorica, 1995
- Fast asynchronous Byzantine agreement with optimal resilience1993