Paper 2025/1710
Information-Theoretic Broadcast-Optimal MPC
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A minor revision of an IACR publication in TCC 2025
- Keywords
- Secure Multi-Party ComputationBroadcastRound-OptimalInformation-Theoretic SecurityVerifiable Secret Sharing
- Contact author(s)
-
michele ciampi @ ed ac uk
ivan @ cs au dk
d ravi @ uva nl
luisi @ dtu dk
sophia yakoubov @ cs au dk - History
- 2025-09-21: approved
- 2025-09-20: received
- See all versions
- Short URL
- https://ia.cr/2025/1710
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1710,
author = {Michele Ciampi and Ivan Damgård and Divya Ravi and Luisa Siniscalchi and Sophia Yakoubov},
title = {Information-Theoretic Broadcast-Optimal {MPC}},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1710},
year = {2025},
url = {https://eprint.iacr.org/2025/1710}
}