Broadcast Optimal Multi-Party Computation
summary
Asks which broadcast rounds can be replaced by point-to-point and what guarantees remain: many round‑optimal protocols keep the same round count if all rounds use only P2P but then only achieve selective abort; having only the last round broadcast suffices for unanimous output in most settings; by contrast, identifiable abort in dishonest‑majority requires broadcast in every round (lower bound). Introduces a new builder, one-or-nothing secret sharing, realized with correlated randomness and per-party keys to make sharing, voting and conditional reconstruction noninteractive in one round. Gives a statistical lower bound: 4 rounds are optimal for honest majority and removing the second-round broadcast breaks guaranteed output delivery (uses a deniability/hexagon style attack; t+1 round cost for deterministic broadcast is recalled).
AI-written summary · about
chapters (7)
- 0:00Broadcast in MPC protocols
- 2:29Round-optimal MPC patterns
- 5:43Upper and lower bounds
- 10:03Secret sharing construction
- 20:16Lower bound for second round
- 27:48Conclusions and future work
- 30:17Q&A
related talks
27mComputation Over the Noisy Broadcast Channel with Malicious Parties
58mSecure Multiparty Computation I
01h 03mClosing Keynote Day 2
01h 08mSecure Computation 1
01h 10mSecure Multiparty Computation II
26mCounting Distinct Elements in the Message Passing Model
01h 01mCommunication Complexity, Streaming and Computational Assumptions
24mAsymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks