## Abstract

Secure multi-party computation (MPC) allows several mutually distrustful parties to securely compute a joint function of their inputs and exists in two main variants: In

The two models—synchronous and asynchronous—have to a large extent developed in parallel with results on both feasibility and asymptotic efficiency improvements in either track. The most notable gap in this parallel development is with respect to round complexity. In particular, although under standard assumptions on a synchronous communication network (availability of secure channels and broadcast), synchronous MPC protocols with (exact) constant rounds have been constructed, to the best of our knowledge, thus far no constant-round asynchronous MPC protocols based on standard assumptions are known, with the best protocols requiring a number of rounds that is linear in the multiplicative depth of the arithmetic circuit computing the desired function.

In this work we close this gap by providing the first constant-round asynchronous MPC protocol that is optimally resilient (i.e., it tolerates up to

*synchronous*MPC parties are connected by a synchronous network with a global clock, and protocols proceed in*rounds*with strong delivery guarantees, whereas*asynchronous*MPC protocols can be deployed even in networks that deliver messages in an arbitrary order and impose arbitrary delays on them.The two models—synchronous and asynchronous—have to a large extent developed in parallel with results on both feasibility and asymptotic efficiency improvements in either track. The most notable gap in this parallel development is with respect to round complexity. In particular, although under standard assumptions on a synchronous communication network (availability of secure channels and broadcast), synchronous MPC protocols with (exact) constant rounds have been constructed, to the best of our knowledge, thus far no constant-round asynchronous MPC protocols based on standard assumptions are known, with the best protocols requiring a number of rounds that is linear in the multiplicative depth of the arithmetic circuit computing the desired function.

In this work we close this gap by providing the first constant-round asynchronous MPC protocol that is optimally resilient (i.e., it tolerates up to

*t*<*n*/3 corrupted parties), adaptively secure, and makes black-box use of a pseudo-random function. It works under the standard network assumptions for protocols in the asynchronous MPC setting, namely, a complete network of point-to-point (secure) asynchronous channels with eventual delivery and asynchronous Byzantine agreement (aka consensus). We provide formal definitions of these primitives and a proof of security in the Universal Composability framework.Original language | English |
---|---|

Title of host publication | Advances in Cryptology -- ASIACRYPT 2016 |

Editors | Jung Hee Cheon, Tsuyoshi Takagi |

Place of Publication | Berlin, Heidelberg |

Publisher | Springer Berlin Heidelberg |

Pages | 998-1021 |

Number of pages | 24 |

ISBN (Print) | 978-3-662-53890-6 |

DOIs | |

Publication status | E-pub ahead of print - 9 Nov 2016 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer, Berlin, Heidelberg |

Volume | 10032 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

Name | Security and Cryptology |
---|---|

Volume | 10032 |