Cryptology ePrint Archive: Report 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{\'a}-Trub\'{\i}niov{\'a}, 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{\'a}-Trub\'{\i}niov{\'a} 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.

Category / Keywords: cryptographic protocols /

Date: received 13 Nov 2013, last revised 17 Nov 2013

Contact author: aniket at mmci uni-saarland de, partho31@gmail com

Available format(s): PDF | BibTeX Citation

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.

Version: 20131117:145950 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]