Lower Bounds for Information-Theoretic MPC
summary
Unconditional MPC requires many messages: computing AND with n players and t corruptions needs omega(nt) messages, and for three players with one corruption exactly 6 messages are necessary and sufficient. Allowing many players to be lazy still needs n ≥ 3t+1 (malicious) or n ≥ 2t+1 (semi‑honest) to tolerate t lazy parties. Gate‑by‑gate multiplication subprotocols must exchange at least two messages per multiplication, and packed sharings only help if the number of players grows with the parallelism.
AI-written summary · about
chapters (8)
- 0:00Intro
- 1:19The Really Hard Problem
- 2:25Message Complexity
- 3:47The Result
- 12:45Gate by Gate Protocols
- 14:37Warm-up: Honest Majority
- 17:06Shares of input
- 22:38Dishonest Majority, Preprocessing
related talks
32mNew Techniques for Building Information-Theoretic Asynchronous MPC with Linear Communication
23mRecent progress in MPC-in-the-Head protocols
01h 31mIntroduction to Secure Multi-Party Computation
41mMPC-in-the-Head based Zero Knowledge Proofs
52mGame-Theoretically Secure Protocols Inspired by Blockchains
27mComputation Over the Noisy Broadcast Channel with Malicious Parties
45mPrice of Active Security in Multiparty Computation
34mPrivacy Preserving Aggregation of Ad Conversions using MPC