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 O~(m/n+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(logn), and can also be used for designing other load-balanced applications in the asynchronous communication model.
We study the problem of secure message transmission among a group of parties in an insecure asynchronous network, where an adversary may repeatedly break into some parties for transient periods of time. A solution for this task is needed in order to use proactive cryptosystems in wide-area networks with loose synchronization. Parties have access to a secure hardware device that stores some cryptographic keys, but can carry out only a very limited set of operations. We provide a formal model of the system, using the framework for asynchronous reactive systems proposed by Pfitzmann and Waidner (Symposium on Security & Privacy, 2001), present a protocol for proactive message transmission, and prove it secure using the composability property of the framework.
Abstract. Secure multiparty computation (MPC) allows a set of parties to securely evaluate any agreed function of their inputs, even when up to t of the n parties are faulty. Protocols for synchronous networks (where every sent message is assumed to arrive within a constant time) tolerate up to t < n/2 faulty parties, whereas in the more realistic asynchronous setting (with no a priory information on maximal message delay) only security against t < n/3 is possible. Note that even asynchronous Byzantine agreement requires t < n/3. In this paper, we are interested in the minimal synchronicity assumption for achieving security against t < n/2. It turns out that the bottleneck of asynchronous MPC is the distribution of the inputs: Once the inputs are correctly distributed, any deterministic function can be computed over a fully asynchronous network with t < n/2. Furthermore, we show that the inputs can be verifiably distributed with t < n/2, if a single round of synchronous broadcast is available. Composing the above, we obtain the first MPC protocol that achieves security against t < n/2 without assuming a fully synchronous network. Actually our protocol guarantees security against any faulty minority in an almost asynchronous network, i.e. in a network with one single round of synchronous broadcast (followed by a fully asynchronous communication). Furthermore our protocol takes inputs of all parties (in a fully asynchronous network only inputs of n−t parties can be guaranteed), and so achieves everything that is possible in synchronous networks (but impossible in fully asynchronous networks) at the price of just one synchronous broadcast round. As tools for our protocol we introduce the notions of almost non-interactive verifiable secret-sharing and almost non-interactive zero-knowledge proof of knowledge, which are of independent interest as they can serve as efficient replacements for fully non-interactive verifiable secret-sharing and fully non-interactive zero-knowledge proof of knowledge.