Cryptology ePrint Archive: Report 2022/109

Perfectly-Secure Synchronous MPC with Asynchronous Fallback Guarantees

Ananya Appan and Anirudh Chandramouli and Ashish Choudhury

Abstract: Secure multi-party computation (MPC) is a fundamental problem in secure distributed computing. The optimal resilience for perfectly-secure MPC in synchronous and asynchronous networks is $t < n/3$ and $t < n/4$ respectively, where $n$ is the number of parties and $t$ is the number of corruptions. A natural question is whether there exists a protocol tolerating $t_s < n/3$ corruptions in a synchronous network and $t_a < n/4$ corruptions in an asynchronous network. We design such a protocol, if $3t_s + t_a < n$. For our protocol, we present a perfectly-secure Byzantine agreement (BA) protocol, tolerating $t < n/3$ corruptions in any network and a perfectly-secure verifiable secret-sharing (VSS) protocol, tolerating $t_s$ and $t_a$ corruptions in a $synchronous$ and an asynchronous network respectively.

Category / Keywords: cryptographic protocols / Byzantine faults, unconditional-security, Byzantine agreement, secret sharing, privacy, Multi Party Computation

Date: received 28 Jan 2022, last revised 29 Jan 2022

Contact author: ananya appan at iiitb ac in, anirudh c at iiitb ac in, ashish choudhury at iiitb ac in

Available format(s): PDF | BibTeX Citation

Version: 20220131:075245 (All versions of this report)

Short URL: ia.cr/2022/109