Paper 2009/492

Efficient Statistical Asynchronous Verifiable Secret Sharing and Multiparty Computation with Optimal Resilience

Arpita Patra, Ashish Choudhary, and C. Pandu Rangan

Abstract

Verifiable Secret Sharing (VSS) is a fundamental primitive used as a building block in many distributed cryptographic tasks, such as Secure Multiparty Computation (MPC) and Byzantine Agreement (BA). An important variant of VSS is Asynchronous VSS (AVSS) which is designed to work over asynchronous networks. AVSS is a two phase (Sharing, Reconstruction) protocol carried out among n parties in the presence of a computationally unbounded active adversary, who can corrupt up to t parties. We assume that every two parties in the network are directly connected by a pairwise secure channel. In this paper, we present a new statistical AVSS protocol with optimal resilience; i.e. with n = 3t+1. Our protocol privately communicates O((\ell n^3 + n^4 \log{\frac{1}{\epsilon}}) \log{\frac{1}{\epsilon}}) bits and A-casts O(n^3 \log(n)) bits to simultaneously share \ell \geq 1 elements from a finite field F, where \epsilon is the error parameter of our protocol. There are only two known statistical AVSS protocols with n = 3t+1 reported in [CR93] and [PCR09]. The AVSS protocol of [CR93] requires a private communication of O(n^9 (\log{\frac{1}{\epsilon}})^4) bits and A-cast of O(n^9 (\log{\frac{1}{\epsilon}})^2 \log(n)) bits to share a single element from F. Thus our AVSS protocol shows a significant improvement in communication complexity over the AVSS of [CR93]. The AVSS protocol of [PCR09] requires a private communication and A-cast of O((\ell n^3 + n^4) \log{\frac{1}{\epsilon}}) bits to share \ell \geq 1 elements. However, the shared element(s) may be NULL \not \in {\mathbb F}. Thus our AVSS is better than the AVSS of [PCR09] due to the following reasons: 1. The A-cast communication of our AVSS is independent of the number of secrets i.e. \ell; 2. Our AVSS makes sure that the shared value(s) always belong to F. Using our AVSS, we design a new primitive called Asynchronous Complete Secret Sharing (ACSS) which acts as an important building block of asynchronous multiparty computation (AMPC). Using our ACSS scheme, we design a statistical AMPC protocol with optimal resilience; i.e., with n = 3t+1, that privately communicates O(n^5 \log{\frac{1}{\epsilon}}) bits per multiplication gate. This significantly improves the communication complexity of only known optimally resilient statistical AMPC of [BKR93] that privately communicates \Omega(n^{11} (\log{\frac{1}{\epsilon}})^4) bits and A-cast \Omega(n^{11} (\log{\frac{1}{\epsilon}})^2 \log(n)) bits per multiplication gate. Both our ACSS and AVSS employ several new techniques, which are of independent interest.