Paper 2025/1614

Broadcast-Optimal Secure Computation From Black-Box Oblivious Transfer

Abstract

When investigating the round-complexity of multi-party computation protocols (MPC) protocols, it is common to assume that in each round parties can communicate over broadcast channels. However, broadcast is an expensive resource, and as such its use should be minimized. For this reason, Cohen, Garay, and Zikas (Eurocrypt 2020) investigated the tradeoffs between the use of broadcast in two-round protocols assuming setup and the achievable security guarantees. Despite the prolific line of research that followed the results of Cohen, Garay, and Zikas, none of the existing results considered the problem of minimizing the use of broadcast while relying in a 𝑏𝑙𝑎𝑐𝑘-𝑏𝑜𝑥 way on the underlying cryptographic primitives. In this work, we fully characterize the necessary and sufficient requirements in terms of broadcast usage in the 𝑑𝑖𝑠ℎ𝑜𝑛𝑒𝑠𝑡 𝑚𝑎𝑗𝑜𝑟𝑖𝑡𝑦 setting for round-optimal MPC with black-box use of minimal cryptographic assumptions. Our main result shows that to securely realize any functionality with 𝑢𝑛𝑎𝑛𝑖𝑚𝑜𝑢𝑠 𝑎𝑏𝑜𝑟𝑡 in the common reference string model with black-box use of two-round oblivious transfer it is necessary and sufficient for the parties to adhere to the following pattern: in the first two rounds the parties exchange messages over peer-to-peer channels, and in the last round the messages are sent over a broadcast channel. We also extend our results to the correlated randomness setting where we prove that one round of peer-to-peer interaction and one round of broadcast is optimal to evaluate any functionality with unanimous abort.