Probabilistic Termination and Composability of Cryptographic Protocols

Ran Cohen, Sandro Coretti, Juan Garay, Vasileios Zikas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

When analyzing the round complexity of multi-party computation (MPC), one often overlooks the fact that underlying resources, such as a broadcast channel, can by themselves be expensive to implement. For example, it is impossible to implement a broadcast channel by a (deterministic) protocol in a sub-linear (in the number of corrupted parties) number of rounds. The seminal works of Rabin and Ben-Or from the early 80’s demonstrated that limitations as the above can be overcome by allowing parties to terminate in different rounds, igniting the study of protocols with probabilistic termination. However, absent a rigorous simulation-based definition, the suggested protocols are proven secure in a property-based manner, guaranteeing limited composability. In this work, we define MPC with probabilistic termination in the UC framework. We further prove a special universal composition theorem for probabilistic-termination protocols, which allows to compile a protocol using deterministic-termination hybrids into a protocol that uses expected-constant-round protocols for emulating these hybrids, preserving the expected round complexity of the calling protocol.

We showcase our definitions and compiler by providing the first composable protocols (with simulation-based security proofs) for the following primitives, relying on point-to-point channels: (1) expected-constant-round perfect Byzantine agreement, (2) expected-constant-round perfect parallel broadcast, and (3) perfectly secure MPC with round complexity independent of the number of parties.
Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2016
Number of pages30
ISBN (Electronic)978-3-662-53015-3
ISBN (Print)978-3-662-53014-6
Publication statusPublished - 21 Jul 2016
Event36th Annual International Cryptology Conference - University of California, Santa Barbara, United States
Duration: 14 Aug 201618 Aug 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Berlin, Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference36th Annual International Cryptology Conference
Abbreviated titleCRYPTO 2016
Country/TerritoryUnited States
CitySanta Barbara
Internet address


Dive into the research topics of 'Probabilistic Termination and Composability of Cryptographic Protocols'. Together they form a unique fingerprint.

Cite this