International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Almost-Asynchronous MPC with Faulty Minority

Zuzana Beerliová-Trubíniová
Martin Hirt
Jesper Buus Nielsen
Search ePrint
Search Google
Abstract: Secure multiparty computation (MPC) allows a set of parties to securely evaluate any agreed function of their inputs, even when up to $t$ of the $n$ parties are faulty. Protocols for synchronous networks (where every sent message is assumed to arrive within a constant time) tolerate up to $t<n/2$ faulty parties, whereas in the more realistic asynchronous setting (with no \emph{a priory} information on maximal message delay) only security against $t<n/3$ is possible. We present the first protocol that achieves security against $t<n/2$ without assuming a fully synchronous network. Actually our protocol guarantees security against any faulty minority in an \emph{almost asynchronous} network, i.e. in a network with one single round of synchronous broadcast (followed by a fully asynchronous communication). Furthermore our protocol takes inputs of all parties (in a fully asynchronous network only inputs of $n-t$ parties can be guaranteed), and so achieves everything that is possible in synchronous networks (but impossible in fully asynchronous networks) at the price of just one synchronous broadcast round. As tools for our protocol we introduce the notions of \emph{almost non-interactive verifiable secret-sharing} and \emph{almost non-interactive zero-knowledge proof of knowledge}, which are of independent interest as they can serve as efficient replacements for fully non-interactive verifiable secret-sharing and fully non-interactive zero-knowledge proof of knowledge.
  title={Almost-Asynchronous MPC with Faulty Minority},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / Multiparty computation},
  note={ 14155 received 29 Sep 2008, last revised 3 Oct 2008},
  author={Zuzana Beerliová-Trubíniová and Martin Hirt and Jesper Buus Nielsen},