Cryptology ePrint Archive: Report 2017/1006

Round and Communication Efficient Unconditionally-secure MPC with $t < n/3$ in Partially Synchronous Network

Ashish Choudhury and Arpita Patra and Divya Ravi

Abstract: In this work, we study unconditionally-secure multi-party computation (MPC) tolerating $t < n/3$ corruptions, where $n$ is the total number of parties involved. In this setting, it is well known that if the underlying network is completely asynchronous, then one can achieve only statistical security; moreover it is impossible to ensure input provision and consider inputs of all the honest parties. The best known statistically-secure asynchronous MPC (AMPC) with $t<n/3$ requires a communication of $O(n^5)$ field elements per multiplication. We consider a partially synchronous setting, where the parties are assumed to be globally synchronized initially for few rounds and then the network becomes completely asynchronous. In such a setting, we present a MPC protocol, which requires $O(n^2)$ communication per multiplication while ensuring input provision. Our MPC protocol relies on a new four round, communication efficient statistical verifiable secret-sharing (VSS) protocol with broadcast communication complexity independent of the number of secret-shared values.

Category / Keywords: Verifiable Secret Sharing, Partial Synchronous, Multi-party computation, statistical security

Original Publication (with major differences): ICITS 2017

Date: received 10 Oct 2017, last revised 15 Oct 2017

Contact author: divya 18oct at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20171016:045328 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]