Efficient Multiparty Protocols via Log-Depth Threshold Formulae
summary
Presents a reduction that builds n‑party MPC from small‑constant MPC by player emulation: n parties are mapped into a recursive tree where each virtual player is emulated by 3 parties for passive security (so security holds up to strictly less than half corrupted) and by 4 parties for active security (matching the <1/3 bound). Uses a log‑depth 3‑input majority formula (Valiant randomized construction and partial derandomization giving correctness when majority margin ≥ 1/2+2^{-√log n}, and a conditional full derandomization from strong one‑way functions), and instantiates the base case with Maurer’s and BGW-style 3‑/4‑party protocols; complexity is polynomial when the formula has log depth.
AI-written summary · about
chapters (10)
- 0:00Start
- 0:04Secure Multiparty Computation (MPC)
- 0:35Feasibility Results: Perfect Security
- 2:35Applications
- 7:143PC MPC
- 12:59Efficient MPC via Player Emulation
- 13:233-Party Protocols
- 14:15Majority from Majorities
- 17:16Active Security
- 19:47Summary
related talks
29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing
30mOn the Optimal Round Complexity of Multi-Party Computation in the Plain Model
58mSecure Multiparty Computation I
01h 08mSecure Computation 1
40mApplied MPC
01h 03mClosing Keynote Day 2
45mPrice of Active Security in Multiparty Computation
01h 10mSecure Multiparty Computation II