Paper 2019/159

Robust MPC: Asynchronous Responsiveness yet Synchronous Security

Chen-Da Liu-Zhang and Julian Loss and Ueli Maurer and Tal Moran and Daniel Tschudi

Abstract

Two paradigms for secure MPC are synchronous and asynchronous protocols, which differ substantially in terms of the guarantees they provide. While synchronous protocols tolerate more corruptions and allow every party to give its input, they are very slow because the speed depends on the conservatively assumed worst-case delay $\Delta$ of the network. In contrast, asynchronous protocols are as fast as the actual network allows, i.e., run in time proportional to the actual maximal network delay $\delta$, but unavoidably parties with slow network connections cannot give input. This paper proposes a new, composable model (of UC functionalities) capturing the best of both worlds. Each party obtains the output as fast as the network allows (a property called responsiveness), and it is guaranteed that all parties obtain the same output. We consider different corruption thresholds: correctness, privacy, and responsiveness are guaranteed for less than $T_C$, $T_P$, and $T_R$ corruptions, respectively, while termination is always guaranteed. We achieve a trade-off between correctness, privacy and responsiveness: For any $T_R\leq\frac{1}{3}n$, one can achieve $T_C = T_P=\min\{\frac{1}{2}n,n-2T_R\}$. In particular, setting $T_R = \frac{1}{4}n$ allows us to obtain $T_C = T_P = \frac{1}{2}n$, hence achieving substantial responsiveness, yet correctness and privacy much better than in an asynchronous protocol and as good as for a purely synchronous (slow) protocol. This result is achieved by a black-box compiler for combining an asynchronous and a synchronous protocol, involving new protocol techniques that may have applications in other contexts, and by devising an asynchronous protocol with $T_C = T_P = n-2T_R$, improving the correctness and privacy of known protocols achieving $T_C=T_P=\frac{1}{3}n$.