Ran Cohen, Boston University and Northeastern

Abstract

Since the introduction of secure multiparty computation (MPC) in the '80s, it has been a common practice to consider a broadcast channel when designing MPC protocols. Well-known lower bounds show that the number of rounds of deterministic broadcast protocols must be linear in the number of corrupted parties. The seminal works of Ben-Or and Rabin showed how to overcome these limitations via randomization, igniting the study of protocols over point-to-point channels with emph{probabilistic termination} (PT) and expected constant round complexity. However, absent a rigorous simulation-based definition, the suggested protocols are proven secure in a property-based manner, and therefore guarantee limited, if any, composability.

Composing PT protocols affects the round complexity of the resulting protocol in somewhat unexpected ways. For instance, the expected round complexity of the parallel composition of expected-constant-round protocols might be logarithmic in number of instances. Sequential composition of PT protocol also raises subtle issues since the parties fall out-of-sync and cannot start the protocol at the same round.

In this work, we put forth the first simulation-based treatment of MPC with probabilistic termination in the UC framework and prove a universal composition theorem for PT protocols. Our theorem allows one to compile a protocol using deterministic-termination hybrids into a protocol that uses expected-constant-round subprotocols 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) over point-to-point channels for the following primitives: (1) expected-constant-round perfect Byzantine agreement, (2) expected-constant-round perfect parallel broadcast, and (3) MPC with round complexity independent of the number of parties.

We proceed to analyze whether the techniques used for parallel composition of broadcast (which is a privacy-free functionality) can be generalized for composing in parallel arbitrary MPC protocols, and provide both feasibility and infeasibility results. We show an efficient protocol-compiler that outputs a protocol that realizes the parallel composition of $m$ protocols, without increasing the expected round complexity; moreover, the compiler requires only black-box access to the underlying emph{protocols}. Using known techniques, a similar result cannot be achieved given only black-box access to the emph{functionalities} realized by the protocols.

This is a joint work with Sandro Coretti, Juan Garay and Vassilis Zikas.

Video