CryptoDB
Broadcast-Optimal Secure Computation From Black-Box Oblivious Transfer
| Authors: |
|
|---|---|
| Download: | |
| Conference: | ASIACRYPT 2025 |
| 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. |
BibTeX
@inproceedings{asiacrypt-2025-36113,
title={Broadcast-Optimal Secure Computation From Black-Box Oblivious Transfer},
publisher={Springer-Verlag},
author={Michele Ciampi and Divya Ravi and Luisa Siniscalchi and Yu Xia},
year=2025
}