Overview of Asynchronous MPC with Linear Communication and Optimal Resilience
Explore the concepts of Asynchronous Multiparty Computation (MPC) with Linear Communication and Optimal Resilience, discussing the model, motivation, and differences between synchronous and asynchronous protocols. The goal is to ensure correctness and privacy in a setting where parties may be corrupted, while addressing challenges such as arbitrary delays and malicious behavior in communication.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Asynchronous MPC with Linear Asynchronous MPC with Linear Communication and Optimal Resilience Communication and Optimal Resilience Xiaoyu Ji Chen-Da Liu-Zhang Vipul Goyal Junru Li Yifan Song NTT Research & CMU Tsinghua University ShanghaiTech University Lucerne U. of Applied Sciences and Arts Tsinghua University & Web3 Foundation & Shanghai Qi Zhi Institute
Multiparty Computation Multiparty Computation Setting ? parties ? corrupted Complete network of bilateral channels
Multiparty Multiparty Computation Computation Setting ? parties ? corrupted Complete network of bilateral channels Goal Correctness: All honest parties finally obtain correct output (GOD) Privacy: Adversary does not learn anything beyond the computed output
Model Model Asynchronous: Arbitrary delays, messages delivered out of order Malicious: Arbitrary behavior, can send wrong messages Adversary may be unbounded (IT Security)
Motivation for Asynchronous Protocols Motivation for Asynchronous Protocols Synchronous: Assume network has delay up to
Motivation for Asynchronous Protocols Motivation for Asynchronous Protocols Synchronous: Assume network has delay up to Problem: How to set ? too small: If actual network delay is larger, we can lose security / liveness too large: Inefficient protocol
Motivation for Asynchronous Protocols Motivation for Asynchronous Protocols Synchronous: Assume network has delay up to Problem: How to set ? too small: If actual network delay is larger, we can lose security / liveness too large: Inefficient protocol Asynchronous: Delays can be arbitrary Protocol runs at speed of actual network delay
Differences between Sync. and Differences between Sync. and Async Async. . Sync:
Differences between Sync. and Differences between Sync. and Async Async. . Sync: If no answer after , assume received
Differences between Sync. and Differences between Sync. and Async Async. . Sync: Statistical ? < ?/2 Perfect ? < ?/3
Differences between Sync. and Differences between Sync. and Async Async. . Sync: Statistical ? < ?/2 Perfect ? < ?/3 Async: T1 T2 ??? Waiting A B
Differences between Sync. and Differences between Sync. and Async Async. . Sync: Statistical ? < ?/2 Perfect ? < ?/3 Async: Cannot distinguish dishonest sender not sending vs slow honest sender T1 T2 ??? Waiting A B
Differences between Sync. and Differences between Sync. and Async Async. . Sync: Statistical ? < ?/2 Perfect ? < ?/3 Async: Cannot distinguish dishonest sender not sending vs slow honest sender T1 T2 ??? Waiting A B
Differences between Sync. and Differences between Sync. and Async Async. . Sync: Statistical ? < ?/2 Perfect ? < ?/3 Async: Cannot distinguish dishonest sender not sending vs slow honest sender T1 T2 Statistical ? < ?/3 Perfect ? < ?/4 ??? Waiting A B
Communication Complexity Communication Complexity Perfect ? < ?/? [BH08]: Synch ?(??) [BCG93] ?(??6) [SR00] ?(??5) [BH07] ?(??3) ?(??2) [PCR10] [AAPP24] ?(??)
Communication Complexity Communication Complexity Perfect ? < ?/? [BH08]: Synch ?(??) [BCG93] ?(??6) [SR00] ?(??5) [BH07] ?(??3) ?(??2) [PCR10] [AAPP24] ?(??) Statistical ? < ?/? [BFO12]: Synch. ?(??) [CP23] ?(??4) [BKR94] ?(??11) [PCR08] ?(??5)
Communication Complexity Communication Complexity Can we achieve Asynchronous MPC with optimal resilience ? < ?/3 and ?(??) communication?
Our Result Our Result Theorem. Let ? = 3? + 1. For any circuit over a finite field of size ? + 1 of size ? and depth ?, there is an information-theoretic asynchronous MPC protocol with guaranteed output delivery and statistical error negligible in ?. The total communication complexity is ?(?? + ??2+ ?14?2) field elements.
Shamir Secret Sharing Shamir Secret Sharing Use a degree-? polynomial Each share is an evaluation point of this polynomial Any ? shares are independent of the secret Any ? + 1 shares can reconstruct the polynomial P6 P7 P1 P2 P3 P4 P5 Shares ?? Secret s
Shamir Secret Sharing Shamir Secret Sharing Properties Linear Homomorphism ? + ??= ??+ ?? Error Correction: ?? can be recovered even if ? out of ? P6 P7 P1 P2 P3 P4 P5 shares are incorrect Shares ?? Secret s
General Approach General Approach Input: Each party secretly shares his input ? ?? Computation: All parties jointly compute a secret sharing for every wire value ?? ?? Gate ?? Output: All parties reconstruct the sharings for output wires ?? ?
General Approach General Approach Computation: All parties jointly compute a secret sharing for every wire value ?? ?? ?? ?? ? + ?? ? ?? + Linear Homomorphism Beaver Triples
Beaver Triple Beaver Triple ?,?: random values ? ? ? Review: A Beaver triple ( ??, ??, ??) Given ??, ??, to compute ? ?? Only need to reconstruct ? + ?? ??+ ?? Main Observation ? + ?? ??+ ?? We can write ? ? = ? + ? ? (? + ? ?) ? ??= ? + ? ? + ? ? + ? ?? ? + ? ??+ ?? One Multiplication = Two Public Reconstructions: cost ?(??) [DN07]: ?(?) Public Reconstructions: cost ?(??)
General Approach General Approach Computation: All parties jointly compute a secret sharing for every wire value ?? ?? ?? ?? ? + ?? ? ?? + Linear Homomorphism Beaver Triples Cost: ?(?? + ??2) + ?(?) Beaver Triples
Triple Generation Triple Generation Step 1: Prepare ( ??, ??) UseAsynchronous Complete Secret Sharing (ACSS) Lie on a valid degree-? polynomial. Allow a dealer ? to share degree-? Shamir sharings such that: If an honest party accepts his share, all honest parties eventually obtain valid shares
Triple Generation Triple Generation Step 1: Prepare ( ??, ??) UseAsynchronous Complete Secret Sharing (ACSS) Lie on a valid degree-? polynomial. Allow a dealer ? to share degree-? Shamir sharings such that: If an honest party accepts his share, all honest parties eventually obtain valid shares Best Prior Work: ?(?3) per sharing [CP23]
Triple Generation Triple Generation Step 1: Prepare ( ??, ??) UseAsynchronous Complete Secret Sharing (ACSS) Lie on a valid degree-? polynomial. Allow a dealer ? to share degree-? Shamir sharings such that: If an honest party accepts his share, all honest parties eventually obtain valid shares Best Prior Work: ?(?3) per sharing [CP23] Use [DN07] for ?(?3) communication per random sharing
Triple Generation Triple Generation Step 1: Prepare ( ??, ??) UseAsynchronous Complete Secret Sharing (ACSS) Lie on a valid degree-? polynomial. Allow a dealer ? to share degree-? Shamir sharings such that: If an honest party accepts his share, all honest parties eventually obtain valid shares Best Prior Work: ?(?3) per sharing [CP23] ?(?2) overhead Use [DN07] for ?(?3) communication per random sharing
Triple Generation Triple Generation Step 1: Prepare ( ??, ??) UseAsynchronous Complete Secret Sharing (ACSS) Lie on a valid degree-? polynomial. Allow a dealer ? to share degree-? Shamir sharings such that: If an honest party accepts his share, all honest parties eventually obtain valid shares This work: ?(?) per sharing [JLS24] Use [DN07] for ?(?) communication per random sharing
Triple Generation Triple Generation Step 2: Compute ??with ? = ? ? Best Result: ?(?2) communication plus Sharing ?(?) deg-? Shamir sharings via ACSS per triple [CP17]
Triple Generation Triple Generation Step 2: Compute ??with ? = ? ? ?(?) overhead using [JLS24] Best Result: ?(?2) communication plus Sharing ?(?) deg-? Shamir sharings via ACSS per triple [CP17]
Triple Generation Triple Generation Step 2: Compute ??with ? = ? ? ?(?) overhead using [JLS24] Best Result: ?(?2) communication plus Sharing ?(?) deg-? Shamir sharings via ACSS per triple [CP17] This work: ?(?) communication plus Sharing ?(1) deg-? Shamir sharings via ACSS per triple [GLS24]
How Previous Approach Works How Previous Approach Works Construction from [CP17]: All parties together prepare three polynomials ? ? ,? ? , ? = ? ? ?(?) where ? and ? have degree (parameter) For each point ?, ( ? ? ?) is a Beaver triple ?, ? ? ?, ?
How Previous Approach Works How Previous Approach Works Construction from [CP17]: Point ?(?) ?(?) ? = ? ? ?(?) Generated by P1 ?1 ?1 ? ?1 ? ?1 ? ?2 ?2 ? ?2 ? ?2 ? Generated by P2 ACSS Generated by P +1 ? +1 ? +1 ? ? +1 ? ? +1 ?
How Previous Approach Works How Previous Approach Works Construction from [CP17]: Point ?(?) ?(?) ? = ? ? ?(?) Generated by P1 ?1 ?1 ? ?1 ? ?1 ? ?2 ?2 ? ?2 ? ?2 ? Generated by P2 ACSS Generated by P +1 ? +1 ? +1 ? ? +1 ? ? +1 ? ? +2 ? ? +2 ? ? +2 ? ? ?2 +1 ? ?2 +1 ? ?2 +1 ? ?
How Previous Approach Works How Previous Approach Works Construction from [CP17]: Point ?(?) ?(?) ? = ? ? ?(?) Generated by P1 ?1 ?1 ? ?1 ? ?1 ? ?2 ?2 ? ?2 ? ?2 ? Generated by P2 ACSS Generated by P +1 ? +1 ? +1 ? ? +1 ? ? +1 ? Using Beaver Triple Generated by P +2 ? +2 ? ? +2 ? ? +2 ? ? +2 ?(? +2)? ? ? Using Beaver Triple Generated by P2 +1 ?2 +1 ? ?2 +1 ? ?2 +1 ? ?2 +1 ?(?2 +1)? ? ?
How Previous Approach Works How Previous Approach Works Construction from [CP17]: Point ?(?) ?(?) ? = ? ? ?(?) ?1 ?1 ? ?1 ? ?1 ? Corrupted parties learn at most ? rows ?2 ?2 ? ?2 ? ?2 ? Can extract + 1 ? random Beaver Triples. ? +1 ? +1 ? ? +1 ? ? +1 ? +1 ? ? ?? ?, ? ?? ?, ?? ? ?=1 ? +2 ? ? +2 ? ? +2 ? ? +2 ?(? +2)? ? ? ?2 +1 ? ?2 +1 ? ?2 +1 ? ?2 +1 ?(?2 +1)? ? ?
How Previous Approach Works How Previous Approach Works Construction from [CP17]: Efficiency Analysis Corrupted parties learn at most ? rows To build Polynomials: ?( ?) communication Output size: + 1 ? random Beaver Triples Can extract + 1 ? random Beaver Triples. +1 ? ? ?? ?, ? ?? ?, ?? We need 2 + 1 parties to participate. For ? ?=1 optimal corruption, can only expect = ? Need ?(?2) per triple!
Our Idea Our Idea Idea 1: Use Large Extract + 1 ? Beaver triples. If + 1 ? = ?(?), the amortized cost per triple is linear. Require 2 + 1 > 2? + 1 parties participate! May never succeed... Failure Reason: Honest Parties will always participate. But may have too few corrupted parties participate.
Our Idea Our Idea Idea 2: Use Packing Use Packed Shamir to store ? = ?(?) secrets. Extract One Packed Beaver Triple. Depack to ? = ?(?) Standard Beaver Triples. Cannot Rely on Error Correction to Guarantee Correctness! Not Known How to Share Packed Shamir Sharing efficiently Failure Reason: Too many incorrect shares from corrupted parties. May have too many corrupted parties participate.
Our Idea Our Idea Idea 1: Use Large Idea 2: Use Packing Extract + 1 ? Beaver triples. Use Packed Shamir to store ? = ?(?) secrets. If + 1 ? = ?(?), the amortized cost per triple is linear. Extract One Packed Beaver Triple. Depack to ? = ?(?) Standard Beaver Triples. Require 2 + 1 > 2? + 1 parties participate! May never succeed... Cannot Rely on Error Correction to Guarantee Correctness! Not Known How to Share Packed Shamir Sharing efficiently Failure Reason: Failure Reason: Honest Parties will always participate. Too many incorrect shares from corrupted parties. But may have too few corrupted parties participate. May have too many corrupted parties participate.
Our Idea Our Idea Process 1 Use Large P? Run in Parallel Process 2 Use Packing P?
Our Idea Our Idea Unite Process 1 and Process 2 Process 1 Use Large In Process 1, a party P? participates if he shares Beaver triples using ACSS Run in Parallel Requirement: P? accepts P? s messages in Process 2 Process 2 only after P? finishes ACSS led by P? Use Packing
Our Idea Our Idea Either there are enough corrupted Process 1 parties participate process 1 Use Large Process 1 eventually succeeds Run in Parallel Or only a small number of corrupted Process 2 parties participate Process 2 Use Packing Process 2 eventually succeeds
Triple Generation Triple Generation Step 1: Prepare ( ??, ??) UseAsynchronous Complete Secret Sharing (ACSS) Lie on a valid degree-? polynomial. Allow a dealer ? to share degree-? Shamir sharings such that: If an honest party accepts his share, all honest parties eventually obtain valid shares This work: ?(?) per sharing [JLS24] Use [DN07] for ?(?) communication per random sharing
Why ACSS is Hard to Build Why ACSS is Hard to Build Honest Party P2: Corrupt Dealer: With bad network (network delay ?) Send correct shares to honest party P1,but do not send anything to honest party P2. Honest Party P1: With good network and receive his share after some time ?
Why ACSS is Hard to Build Why ACSS is Hard to Build Honest Party P2: Corrupt Dealer: With bad network (network delay ?) Send correct shares to honest party P1,but do not send anything to honest Difficults: party P2. P2hasn t received anything. Cannot rely on P2 s response. Worst Case: Only ? + 1 honest parties obtain their shares at the moment P1 accepts. Honest Party P1: Need these ? + 1 parties help other When to accept his shares ? honest parties recover their shares.
A Weaker Goal: AVSS A Weaker Goal: AVSS Asynchronous Verifiable Secret Sharing (AVSS) Allow a dealer ? to share degree-? Shamir sharings such that: If an honest party accepts his share, all parties can eventually reconstruct the secret. Not all honest parties can receive their shares!
How Previous Approach Works How Previous Approach Works Step 1: Build AVSS via Bivariate Polynomial ?(?2) per sharing Step 2: Upgrade to ACSS Sharing?(?) AVSS per ACSS
