Paper 2009/087

Unconditionally Secure Asynchronous Multiparty Computation with Quadratic Communication Per Multiplication Gate

Arpita Patra, Ashish Choudhary, and C. Pandu Rangan

Abstract

Secure multiparty computation (MPC) allows a set of $n$ parties to securely compute an agreed function, even if up to $t$ parties are under the control of an adversary. In this paper, we propose a new {\it Asynchronous secure multiparty computation} (AMPC) protocol that provides information theoretic security with $n = 4t+1$, where $t$ out of $n$ parties can be under the influence of a {\it Byzantine (active)} adversary ${\cal A}_t$ having {\it unbounded computing power}. Our protocol communicates ${\cal O}(n^2 \log|{\mathbb F}|)$ bits per multiplication and involves a negligible error probability of $2^{-\Omega(\kappa)}$, where $\kappa$ is the error parameter and ${\mathbb F}$ is the field over which the computation is carried out. The best known information theoretically secure AMPC with $n=4t+1$ communicates ${\cal O}(n^3 \log|{\mathbb F}|)$ bits per multiplication and does not involve any error probability in computation. Though a negligible error probability is involved, our AMPC protocol provides the best communication complexity among all the known AMPC protocols providing information theoretic security. Moreover, the communication complexity of our AMPC is same as the communication complexity of the best known AMPC protocol with {\it cryptographic assumptions}. As a tool for our AMPC protocol, we propose a new method of efficiently generating {\it $d$-sharing} of multiple secrets concurrently in asynchronous setting, which is of independent interest, where $t \leq d \leq 2t$. In the literature, though there are protocols for generating $t$-sharing and $2t$-sharing separately, there is no generic protocol for generating {\it $d$-sharing} for the range $t \leq d \leq 2t$. Moreover, our protocol provides better communication complexity than the existing methods for generating $2t$-sharing.

Note: The article is withdrawn, as it it now merged with the articled no Cryptology ePrint Archive: Report 2010/007