Intermediate

MPC Protocols

MPC protocols vary in their security guarantees, performance characteristics, and the number of parties they support. Understanding these trade-offs is essential for choosing the right protocol for your application.

Security Models

Semi-Honest (Passive) Security

Parties follow the protocol correctly but may try to learn additional information from the messages they receive. This is the weaker but more efficient model:

  • All parties execute the protocol as specified
  • Adversary can only observe, not modify, protocol messages
  • Sufficient when parties are honest but curious (e.g., regulated entities)
  • Significantly faster than malicious security

Malicious (Active) Security

Parties may deviate from the protocol in arbitrary ways to try to learn private information or corrupt the output:

  • Adversary can send arbitrary messages, abort, or collude
  • Requires verification mechanisms (MACs, zero-knowledge proofs, cut-and-choose)
  • 2-20x more expensive than semi-honest protocols
  • Necessary when parties do not trust each other at all
FeatureSemi-HonestMalicious
Trust assumptionParties follow protocolNo trust required
PerformanceFast2-20x slower
CommunicationLowerHigher (verification overhead)
Use casesRegulated entities, internal teamsUntrusted parties, adversarial settings

Corruption Thresholds

MPC protocols specify how many parties can be corrupted while maintaining security:

  • Honest majority: At most t < n/2 parties can be corrupted (n = total parties). Enables more efficient protocols.
  • Dishonest majority: Up to t < n parties can be corrupted. More robust but less efficient. Required for two-party computation.

Protocol Families

Secret Sharing-Based Protocols

Data is split into shares distributed among parties. Computations are performed on shares. Best for arithmetic operations (addition, multiplication) and multi-party settings.

  • GMW protocol: Based on Boolean secret sharing. Supports any number of parties.
  • BGW protocol: Based on Shamir secret sharing. Efficient for honest majority.
  • SPDZ protocol: Supports dishonest majority with malicious security using MACs.

Garbled Circuit-Based Protocols

One party "garbles" (encrypts) a Boolean circuit; the other evaluates it. Optimized for two-party computation with low round complexity.

Hybrid Protocols

Modern frameworks combine both approaches: use arithmetic secret sharing for linear operations and garbled circuits for non-linear operations (comparisons, ReLU activations).

✅
For ML applications: Most ML computations are dominated by linear operations (matrix multiplications), which are efficient with secret sharing. Non-linearities (ReLU, softmax) are the bottleneck and are handled with garbled circuits or approximations.

Communication Complexity

The primary bottleneck in MPC is communication, not computation. Key metrics:

  • Round complexity: Number of communication rounds. Lower is better for high-latency networks.
  • Bandwidth: Total data transferred. Garbled circuits require transmitting the entire circuit.
  • Online vs offline: Many protocols separate into a data-independent offline phase (can be precomputed) and a fast online phase.