The Communication Complexity Landscape of Information-theoretic MPC
summary
Draws a clear map: proofs show optimal-resiliency information-theoretic MPC needs Θ(n/s) communication per multiplication when n = 3t+s (synchronous) or n = 4t+s (asynchronous), so achieving full resilience (s=1) forces linear communication overhead. Gives the first expected‑round linear asynchronous protocols and constructs a weak-binding AVSS using trivariate packing to get constant amortized cost, plus a packed degree reduction trick (RS-style encoding + local resharing) that yields constant online cost; constructions and lower bounds match in the cases claimed.
AI-written summary · about
chapters (11)
- 0:00Information-theoretic MPC intro
- 1:50Communication complexity in MPC
- 3:40Synchronous vs asynchronous models
- 11:24Resiliency for perfect security
- 15:24Synchronous perfect MPC complexity
- 22:47Statistical security thresholds
- 25:41Asynchronous statistical MPC challenges
- 28:12MPC protocol building blocks
- 33:10Weak binding verifiable secret sharing
- 48:41Constant overhead online phase
- 55:16Summary and open questions
related talks
01h 08mSecure Computation 1
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
58mSecure Multiparty Computation I
01h 01mCommunication Complexity, Streaming and Computational Assumptions
10mDumbo-MPC: Efficient Fully Asynchronous MPC with Optimal Resilience
45mPrice of Active Security in Multiparty Computation
01h 03mClosing Keynote Day 2
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)