The seminal works of Rabin and Ben-Or from the early 80's demonstrated that limitations as the above can be overcome by using randomization and allowing parties to terminate at different rounds, igniting the study of protocols over point-to-point channels with probabilistic termination and expected constant round complexity. However, absent a rigorous simulation-based definition, the suggested protocols are proven secure in a property-based manner or via ad hoc simulation-based frameworks, therefore guaranteeing limited, if any, composability.
In this work, we put forth the first simulation-based treatment of multi-party cryptographic protocols with probabilistic termination. We define secure multi-party computation (MPC) with probabilistic termination in the UC framework and prove a universal composition theorem for probabilistic-termination protocols. Our theorem 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.Category / Keywords: cryptographic protocols / probabilistic termination, Universal Composition, cryptographic protocol, randomized Byzantine agreement Original Publication (with major differences): IACR-CRYPTO-2016 Date: received 1 Apr 2016, last revised 9 Oct 2016 Contact author: cohenrb at cs biu ac il Available format(s): PDF | BibTeX Citation Version: 20161009:123633 (All versions of this report) Short URL: ia.cr/2016/350 Discussion forum: Show discussion | Start new discussion