CryptoDB
Unconditionally Secure Asynchronous Multiparty Computation with Quadratic Communication
| Authors: | |
|---|---|
| Download: | |
| 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 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 Byzantine (active) adversary ${\cal A}_t$ having unbounded computing power. Our protocol communicates 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 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 cryptographic assumptions. As a tool for our AMPC protocol, we propose a new method of efficiently generating (t,2t)-sharing of multiple secrets concurrently in asynchronous setting, which is of independent interest. |
BibTeX
@misc{eprint-2009-18275,
title={Unconditionally Secure Asynchronous Multiparty Computation with Quadratic Communication},
booktitle={IACR Eprint archive},
keywords={foundations /},
url={http://eprint.iacr.org/2009/087},
note={ arpitapatra_10@yahoo.co.in 14294 received 18 Feb 2009},
author={Arpita Patra and Ashish Choudhary and C. Pandu Rangan},
year=2009
}