Secure Multiparty Computation II
summary
Uses a correlated randomness dealer that gives each party additive shares of a shifted truth table (random cyclic DX,DY) so online the parties exchange only X+DX and Y+DY and two share openings; online comm equals input+output size and security is information‑theoretic but not malicious‑robust unless augmented with one‑time MACs. Extends to a dealer‑free three‑party construction and links to PIR/LDC giving best known upper bound around 2^{√n} for preprocessing size; main open problem is closing the huge gap versus the linear lower bound.
AI-written summary · about
chapters (15)
- 0:00Feasibility: open questions
- 7:17A simple MPC protocol
- 12:583-Party MPC for g(x,y,z)
- 27:00Approaches to passive MPC
- 36:21Active-Secure MPC
- 40:53Back to the 1980s
- 43:12Message of this part of talk
- 45:14Zero-knowledge proofs
- 47:37MPC → ZK [IKOS07]
- 51:18Analysis
- 52:59Extensions
- 56:18Applications
- 57:51General 2-party protocols [IPS08]
- 58:43A dream goal
- 59:48Outer protocol
related talks
01h 03mSecure Computation 2
01h 08mSecure Computation 1
01h 00mSecure Computation 3
28mAsynchronous Distributed Key Generation
25mFaster Malicious 2-Party Secure Computation with Online/Offline Dual Execution
44mMultiparty Protocols
29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing
34mEfficient Robust Private Aggregation for DP