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.