Paper 2013/745

Asynchronous MPC with t< n/2 Using Non-equivocation

Michael Backes, Fabian Bendun, Ashish Choudhury and Aniket Kate

Abstract

Secure Multiparty Computation (MPC) is a fundamental problem in distributed cryptography. Although MPC in the synchronous communication setting has received tremendous attention in security research, recent interest in deploying MPC in real-life systems requires going beyond the synchronous setting and working towards MPC in the weaker asynchronous communication setting. The asynchronous setting, however, does not come without a penalty: asynchronous MPC (AMPC) protocols among n parties can only tolerate up to t < n/3 active corruptions in contrast to the synchronous protocols, which can tolerate up to t<n/2 corruptions. In this work, we improve the resiliency bound for AMPC using non-equivocation. Non-equivocation is a mechanism to restrict a corrupted party from making conflicting statements to different (honest) parties, and it can be implemented using an increment-only counter, realizable with trusted hardware modules readily available in commodity computers and smartphone devices. In particular, using non-equivocation, we present an AMPC protocol in the asynchronous setting, tolerating t < n/2 faults. From a practical point of view, our AMPC protocol requires fewer setup assumptions than the previous AMPC protocol with t < n/2 by Beerliovä-Trub\'ıniovä, Hirt and Nielsen (PODC '10): unlike their AMPC protocol, it does not require any synchronous broadcast round at the beginning of the protocol and avoids the threshold homomorphic encryption setup assumption. Moreover, our AMPC protocol is also efficient and provides a gain of \Theta(n) in the communication complexity per multiplication gate, over the AMPC protocol of Beerliovä-Trub\'ıniovä et al. In the process, using non-equivocation, we also define the first asynchronous verifiable secret sharing (AVSS) scheme with t < n/2, which is of independent interest to threshold cryptographic protocols.

Note: This a preliminary version of the paper. A version with some technical (but not conceptual) modifications will be updated soon. The claimed results, however, will remain the same.