Asynchronous Multi-Party Computation in Large Networks
Preprint
Abstract
We describe an asynchronous protocol to solve the secure multi-party computation (MPC) problem over n parties, when less than a 1/8 fraction of the parties are controlled by a static malicious adversary. For any deterministic function that can be computed by an arithmetic circuit with m gates, our protocol requires each party to send a number of field elements and perform an amount of computation that is soft-O(m/n + sqrt(n)). This significantly improves over traditional algorithms which require each party to both send a number of messages and perform computation that is Omega(nm). We also show that our protocol provides perfect and universally-composable security. To achieve this result we define the threshold counting problem and present a distributed protocol to solve it in the asynchronous communication model. Our protocol is load balanced, with computation, communication and latency complexity of O(log n), and may be useful 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