International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Efficient Asynchronous Multiparty Computation with Optimal Resilience

Arpita Patra
Ashish Choudhary
C. Pandu Rangan
Search ePrint
Search Google
Abstract: We propose an efficient information theoretic secure asynchronous multiparty computation (AMPC) protocol with optimal fault tolerance; i.e., with $n = 3t+1$, where $n$ is the total number of parties and $t$ is the number of parties that can be under the influence of a Byzantine (active) adversary ${\cal A}_t$ having unbounded computing power. Our protocol communicates O(n^5 \kappa)$ bits per multiplication and involves a negligible error probability of $2^{- O(\kappa)}$, where $\kappa$ is the error parameter. As far as our knowledge is concerned, the only known AMPC protocol with $n = 3t+1$ providing information theoretic security with negligible error probability is due to \cite{BenOrPODC94AsynchronousMPC}, which communicates $\Omega(n^{11} \kappa^4)$ bits and A-Casts $\Omega(n^{11} \kappa^2 \log(n))$ bits per multiplication. Here A-Cast is an asynchronous broadcast primitive, which allows a party to send the same information to all other parties identically. Thus our AMPC protocol shows significant improvement in communication complexity over the AMPC protocol of \cite{BenOrPODC94AsynchronousMPC}. As a tool for our AMPC protocol, we introduce a new asynchronous primitive called Asynchronous Complete Verifiable Secret Sharing (ACVSS), which is first of its kind and is of independent interest. For designing our ACVSS, we employ a new asynchronous verifiable secret sharing (AVSS) protocol which is better than all known communication-efficient AVSS protocols with $n=3t+1$.
  title={Efficient Asynchronous Multiparty Computation with Optimal Resilience},
  booktitle={IACR Eprint archive},
  keywords={foundations /},
  note={ 14287 received 2 Oct 2008, last revised 11 Feb 2009},
  author={Arpita Patra and Ashish Choudhary and C. Pandu Rangan},