On the Optimal Round Complexity of Multi-Party Computation in the Plain Model
summary
Claims a black-box construction of general MPC in the plain model that matches the known four rounds lower bound for unanimous abort security against up to n−1 corruptions, assuming standard polynomial-time OT. It builds a new weaker watchlist (implemented via a k-out-of-n OT and list-simulatable OT in three rounds), combines IPS compiler, conditional disclosure of secret, garbled-circuit next-message evaluation, and extra OTs to protect inputs, and yields a working four-round protocol under polynomial assumptions while leaving identifiable-abort and communication blowup as open issues.
AI-written summary · about
chapters (15)
- 0:00MPC in plain model intro
- 1:11Round complexity in MPC
- 3:27Previous results gap
- 4:10IPS compiler building blocks
- 7:07IPS compiler round squeeze
- 9:00Four-round protocol bottleneck
- 10:26Watchlist functionality relaxation
- 14:45Three-round OT correlation
- 16:14Adversarial aborts security
- 17:39Inputless inner protocol
- 19:55Conditional disclosure for input
- 21:26Garbled circuits and OT
- 24:47Multiparty OT label reconstruction
- 26:43Key takeaways and open questions
- 27:47Conclusion and Q&A
related talks
58mSecure Multiparty Computation I
01h 08mSecure Computation 1
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
26mEfficient Multiparty Protocols via Log-Depth Threshold Formulae
45mPrice of Active Security in Multiparty Computation
01h 03mClosing Keynote Day 2
40mApplied MPC
35mOblivious RAM for MPC