CryptoDB
Efficient Asynchronous Multiparty Computation with Optimal Resilience
Authors: | |
---|---|
Download: | |
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$. |
BibTeX
@misc{eprint-2008-18052, title={Efficient Asynchronous Multiparty Computation with Optimal Resilience}, booktitle={IACR Eprint archive}, keywords={foundations /}, url={http://eprint.iacr.org/2008/425}, note={ arpitapatra_10@yahoo.co.in 14287 received 2 Oct 2008, last revised 11 Feb 2009}, author={Arpita Patra and Ashish Choudhary and C. Pandu Rangan}, year=2008 }