New Techniques for Building Information-Theoretic Asynchronous MPC with Linear Communication
summary
Constructs information‑theoretic asynchronous MPC with malicious security and guaranteed delivery at resilience n = 3t + 1 and reduces prior astronomical costs to a final communication overhead of roughly n^6 (previous work had n^12–n^14 in key steps). Key tools are ACSS and an improved asynchronous packed information‑checking primitive; triple generation uses CP17 triple extraction plus party virtualization (n^2 virtual parties from pairwise 2PC) to extract a linear fraction of Beaver triples. Protocol is concrete and provably correct, but n^6 still limits hundreds‑party practicality.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 1:48Previous protocol limits
- 4:00Communication overhead sources
- 8:20Triple generation challenges
- 12:37Efficient triple generation
- 17:40Secret sharing improvements
- 24:08Authentication in async setting
- 30:19Communication overhead analysis
- 31:52Q&A
related talks
30mLower Bounds for Information-Theoretic MPC
23mRecent progress in MPC-in-the-Head protocols
45mPrice of Active Security in Multiparty Computation
33mInteraction Preserving Compilers for Secure Computation
01h 31mIntroduction to Secure Multi-Party Computation
51mDistributed Zero-Knowledge Proofs and Applications to Secure Computation
49mCompiling to preserve our privacy
27mComputation Over the Noisy Broadcast Channel with Malicious Parties