International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Information-Theoretic Broadcast-Optimal MPC

Authors:
Divya Ravi , University of Amsterdam
Michele Ciampi , The University of Edinburgh, UK
Ivan Damgård , Aarhus University, Denmark
Luisa Siniscalchi , The Technical University of Denmark
Sophia Yakoubov , Aarhus University, Denmark
Download:
Search ePrint
Search Google
Conference: TCC 2025
Abstract: Broadcast, though often used as a black box in cryptographic protocols, is expensive to realize in terms of rounds and communication complexity. We investigate the minimal use of broadcast in round-optimal information-theoretic MPC, with statistical security. For information-theoretic MPC with guaranteed output delivery, four rounds of communication are necessary and sufficient (Applebaum, Kachlon and Patra, FOCS 2020; Applebaum, Kachlon and Patra, STOC 2023). We show that broadcast is unavoidable in the second and third rounds of statistical MPC protocols. To complement our lower bounds, we modify the protocol of Applebaum, Kachlon and Patra (STOC 2023) to make use of broadcast only in the second and third round. Along the way, we show that the sharing phase of any three-round information-theoretic VSS protocol must also make use of broadcast in the second and third rounds.
BibTeX
@inproceedings{tcc-2025-36222,
  title={Information-Theoretic Broadcast-Optimal MPC},
  publisher={Springer-Verlag},
  author={Divya Ravi and Michele Ciampi and Ivan Damgård and Luisa Siniscalchi and Sophia Yakoubov},
  year=2025
}