MPC Protocols for Multiple Parties
What you'll learn: How BGW and GMW protocols enable secure computation among multiple parties (not just two) with different trade-offs between security and performance.
Beyond Two-Party Computation
So far, you've seen how garbled circuits and oblivious transfer enable two parties to compute together securely. But what happens when you need three or more parties to jointly compute something without revealing their private inputs? That's where multi-party MPC protocols come in.
BGW Protocol (Ben-Or, Goldwasser, Wigderson)
The BGW protocol uses secret sharing (which you already know!) as its foundation. Here's how it works:
- Each party splits their input into shares distributed among all participants
- Computation happens directly on the shares using addition and multiplication operations
- The protocol can tolerate up to t < n/2 corrupted parties (where n is the total number)
- Trade-off: Provides information-theoretic security (doesn't rely on computational assumptions) but requires more communication rounds
Think of it like a group of friends computing the average salary without anyone revealing their individual income—each person's salary is split into puzzle pieces, calculations happen on the pieces, and the final average emerges without exposing individual values.
GMW Protocol (Goldreich, Micali, Wigderson)
The GMW protocol takes a different approach:
- Uses Boolean circuits and oblivious transfer as building blocks
- Can tolerate up to t < n corrupted parties
- Relies on computational security (cryptographic assumptions)
- Trade-off: Generally more efficient for certain types of computations but depends on OT operations
Key Takeaway: BGW offers stronger security guarantees with information-theoretic protection but requires honest majorities, while GMW provides more flexibility in corruption tolerance using cryptographic assumptions—choose based on your trust model and performance needs.