Efficient Asynchronous Verifiable Secret Sharing and Multiparty Computation ∗

Secure Multi-Party Computation (MPC) providing information theoretic security allows a set of n parties to securely compute an agreed function F over a finite field F, even if t parties are under the control of a computationally unbounded active adversary. Asynchronous MPC (AMPC) is an important variant of MPC, which works over an asynchronous network. It is well known that perfect AMPC is possible if and only if n ≥ 4t + 1, while statistical AMPC is possible if and only if n ≥ 3t + 1. In this paper, we study the communication complexity of AMPC protocols (both statistical and perfect) designed with exactly n = 4t+ 1 parties. Our major contributions in this paper are as follows: 1. Asynchronous Verifiable Secret Sharing (AVSS) is one of the main building blocks for AMPC. In this paper, we design two AVSS protocols with 4t + 1 parties: the first one is statistically secure and has non-optimal resilience, while the second one is perfectly secure and has optimal resilience. Both these schemes achieve a common interesting property, which was not achieved by the previous schemes. Specifically, our AVSS schemes allow to share a secret through a polynomial of degree at most d, where t ≤ d ≤ 2t. In contrast, the existing AVSS schemes can share a secret only through a polynomial of degree at most t. The new property of our AVSS simplifies th