Asynchronous Multiparty Computation with Linear Communication Complexity

Ashish Choudhary, Martin Hirt, Arpita Patra

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

17 Citations (Scopus)


Secure multiparty computation (MPC) allows a set of n parties to securely compute a function of their private inputs against an adversary corrupting up to t parties. Over the previous decade, the communication complexity of synchronous MPC protocols could be improved to O(n) per multiplication, for various settings. However, designing an asynchronous MPC (AMPC) protocol with linear communication complexity was not achieved so far. We solve this open problem by presenting two AMPC protocols with the corruption threshold t <n/4. Our first protocol is statistically secure (i.e. involves a negligible error) in a completely asynchronous setting and improves the communication complexity of the previous best AMPC protocol in the same setting by a factor of Theta(n). Our second protocol is perfectly secure (i.e. error free) in a hybrid setting, where one round of communication is assumed to be synchronous, and improves the communication complexity of the previous best AMPC protocol in the hybrid setting by a factor of Theta(n(2)).

Like other efficient MPC protocols, we employ Beaver's circuit randomization approach (Crypto '91) and prepare shared random multiplication triples. However, in contrast to previous protocols where triples are prepared by first generating two random shared values which are then multiplied distributively, in our approach each party prepares its own multiplication triples. Given enough such shared triples (potentially partially known to the adversary), we develop a method to extract shared triples unknown to the adversary, avoiding communication-intensive multiplication protocols. This leads to a framework of independent interest.

Original languageEnglish
Title of host publicationDISTRIBUTED COMPUTING
EditorsY Afek
Place of PublicationBERLIN
PublisherSpringer-Verlag Berlin
Number of pages15
ISBN (Print)978-3-642-41526-5
Publication statusPublished - 2013
Event27th International Symposium on Distributed Computing (DISC) - Jerusalem, Israel
Duration: 14 Oct 201318 Oct 2013

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conference27th International Symposium on Distributed Computing (DISC)


  • MPC

Cite this