Is It Even Possible? On the Parallel Composition of Asynchronous MPC Protocols
summary
Shows that generic black-box parallel composition of asynchronous MPC is impossible: both functionally black-box (FBB) and standard protocol black-box (PBB) composition fail (even against fail‑stop or semi‑malicious schedulers), with classic barriers like input incompleteness and the n/3 impossibility bound still active. Uses constructed counterexamples with two parallel point functions and an adversarial scheduler, and shows feasibility only when protocols expose a detectable subroutine (ACS‑decomposable) or when using extra tools such as threshold FHE or an asynchronous common coin, yielding round‑preserving parallel composition for known MPCs.
AI-written summary · about
chapters (14)
- 0:00Parallel composition in MPC
- 1:06Asynchronous MPC basics
- 5:55MPC results synchronous vs async
- 8:56Parallel execution in MPC
- 11:56MPC historical context
- 13:51Defining parallel composition
- 17:26Black-box composition in MPC
- 20:35Impossibility strong parallel MPC
- 22:09Weak parallel composition feasibility
- 25:10Adversary models implications
- 27:05ACS decomposable protocols
- 28:55Strong vs weak composition results
- 31:07Feasibility and impossibility summary
- 32:16Q&A
related talks
05mπMPC: Automatic Security Proofs for MPC Protocols
23mRecent progress in MPC-in-the-Head protocols
33mInteraction Preserving Compilers for Secure Computation
49mCompiling to preserve our privacy
41mMPC-in-the-Head based Zero Knowledge Proofs
53mFormal security analysis of MPC-in-the-headzero-knowledge protocols
31mSequential Composition of Rational Proofs
01h 31mIntroduction to Secure Multi-Party Computation