International Association
for Cryptologic Research

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 \emph{a priory} information on maximal message delay) only security against $t<n/3$ is possible. We present the first 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 \emph{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 \emph{almost non-interactive verifiable secret-sharing} and \emph{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.

Secure function evaluation (SFE) allows a set of players to compute an arbitrary agreed function of their private inputs, even if an adversary may corrupt some of the players. Secure multi-party computation (MPC) is a generalization allowing to perform an arbitrary on-going (also called reactive or stateful) computation during which players can receive outputs and provide new inputs at intermediate stages. At Crypto~2006, Ishai \emph{et al.} considered mixed threshold adversaries that either passively corrupt some fixed number of players, or, alternatively, actively corrupt some (smaller) fixed number of players, and showed that for certain thresholds, cryptographic SFE is possible, whereas cryptographic MPC is not. However, this separation does not occur when one considers \emph{perfect} security. Actually, past work suggests that no such separation exists, as all known general protocols for perfectly secure SFE can also be used for MPC. Also, such a separation does not show up with \emph{general adversaries}, characterized by a collection of corruptible subsets of the players, when considering passive and active corruption. In this paper, we study the most general corruption model where the adversary is characterized by a collection of adversary classes, each specifying the subset of players that can be actively, passively, or fail-corrupted, respectively, and show that in this model, perfectly secure MPC separates from perfectly secure SFE. Furthermore, we derive the exact conditions on the adversary structure for the existence of perfectly secure SFE resp.~MPC, and provide efficient protocols for both cases.

We give improved upper bounds on the communication complexity of optimally-resilient secure multiparty computation in the cryptographic model. We consider evaluating an $n$-party randomized function and show that if $f$ can be computed by a circuit of size $c$, then $\O(c n^2 \kappa)$ is an upper bound for active security with optimal resilience $t < n/2$ and security parameter $\kappa$. This improves on the communication complexity of previous protocols by a factor of at least $n$. This improvement comes from the fact that in the new protocol, only $\O(n)$ messages (of size $\O(\kappa)$ each) are broadcast during the \emph{whole} protocol execution, in contrast to previous protocols which require at least $\O(n)$ broadcasts \emph{per gate}. Furthermore, we improve the upper bound on the communication complexity of passive secure multiparty computation with resilience $t<n$ from $\O(c n^2 \kappa)$ to $\O(c n \kappa)$. This improvement is mainly due to a simple observation.

We consider secure multi-party computation in the asynchronous model and present an efficient protocol with optimal resilience. For $n$ parties, up to $t<n/3$ of them being corrupted, and security parameter $\kappa$, a circuit with $c$ gates can be securely computed with communication complexity $O(c n^3 \kappa)$ bits. In contrast to all previous asynchronous protocols with optimal resilience, our protocol requires access to an expensive broadcast primitive only $O(n)$ times --- independently of the size $c$ of the circuit. This results in a practical protocol with a very low communication overhead. One major drawback of a purely asynchronous network is that the inputs of up to $t$ honest parties cannot be considered for the evaluation of the circuit. Waiting for all inputs could take infinitely long when the missing inputs belong to corrupted parties. Our protocol can easily be extended to a hybrid model, in which we have one round of synchronicity at the end of the input stage, but are fully asynchronous afterwards. In this model, our protocol allows to evaluate the circuit on the inputs of every honest party.

A broadcast protocol allows a sender to distribute a value among a set of players such that it is guaranteed that all players receive the same value (consistency), and if the sender is honest, then all players receive the sender's value (validity). Classical broadcast protocols for $n$ players provide security with respect to a fixed threshold $t<n/3$, where both consistency and validity are guaranteed as long as at most $t$ players are corrupted, and no security at all is guaranteed as soon as $t+1$ players are corrupted. Depending on the environment, validity or consistency may be the more important property. We generalize the notion of broadcast by introducing an additional threshold $t^+\ge t$. In a {\em broadcast protocol with extended validity}, both consistency and validity are achieved when no more than $t$ players are corrupted, and validity is achieved even when up to $t^+$ players are corrupted. Similarly, we define {\em broadcast with extended consistency}. We prove that broadcast with extended validity as well as broadcast with extended consistency is achievable if and only if $t+2t^+<n$ (or $t=0$). For example, six players can achieve broadcast when at most one player is corrupted (this result was known to be optimal), but they can even achieve consistency (or validity) when two players are corrupted. Furthermore, our protocols achieve {\em detection} in case of failure, i.e., if at most $t$ players are corrupted then broadcast is achieved, and if at most $t^+$ players are corrupted then broadcast is achieved or every player learns that the protocol failed. This protocol can be employed in the precomputation of a secure multi-party computation protocol, resulting in {\em detectable multi-party computation}, where up to $t$ corruptions can be tolerated and up to $t^+$ corruptions can either be tolerated or detected in the precomputation, for any $t,t^+$ with $t+2t^+<n$.

We present a very efficient multi-party computation protocol unconditionally secure against an active adversary. The security is maximal, i.e., active corruption of up to $t<n/3$ of the $n$ players is tolerated. The communication complexity for securely evaluating a circuit with $m$ multiplication gates over a finite field is $\O(mn^2)$ field elements, including the communication required for simulating broadcast. This corresponds to the complexity of the best known protocols for the passive model, where the corrupted players are guaranteed not to deviate from the protocol. Even in this model, it seems to be unavoidable that for every multiplication gate every player must send a value to every other player, and hence the complexity of our protocol may well be optimal. The constant overhead factor for robustness is small and the protocol is practical.