Breaking the O(n|C|) Barrier for Unconditionally Secure Asynchronous Multiparty Computation

Ashish Choudhary

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


In PODC 2012, Dani et al. presented an unconditionally secure multiparty computation (MPC) protocol, which allows a set of n parties to securely evaluate any arithmetic circuit C of size |C| on their private inputs, even in the presence of a computationally unbounded malicious adversary who can corrupt upto t<(13−ϵ)n parties, for any given non-zero ε with 0<ϵ<13. The total circuit-dependent communication complexity of their protocol is O(\ensuremathPolyLog(n)⋅|C|), which is a significant improvement over the standard MPC protocols, which has circuit-dependent complexity of the form O(\ensuremathPoly(n)⋅|C|). The key innovation in their protocol is that instead of following the standard method of having every party communicate with every other party for evaluating each gate of C, it is sufficient to involve only a small subset of parties of size Θ(PolyLog(n)) to communicate with each other for evaluating each gate of the circuit. The protocol was presented in a synchronous setting and it was left as an open problem to design an asynchronous MPC (AMPC) protocol, with a similar characteristic. In this work, we solve this open problem by presenting the first unconditionally secure AMPC protocol where the circuit dependent complexity is O(\ensuremathPolyLog(n)⋅|C|)
Original languageEnglish
Title of host publicationTopics in Cryptology - INDOCRYPT 2013
Place of PublicationINDOCRYPT
PublisherSpringer Berlin Heidelberg
Number of pages19
Publication statusPublished - 2013


Dive into the research topics of 'Breaking the O(n|C|) Barrier for Unconditionally Secure Asynchronous Multiparty Computation'. Together they form a unique fingerprint.

Cite this