Multi-Party Computation (MPC)

In 2021, Fireblocks processed $1.5 trillion in crypto transactions. Every single transaction required a private key signature without ever assembling the complete key on any single machine - using threshold ECDSA (MPC). The same mathematical primitives that Yao described in 1986 for comparing millionaires' wealth now protect institutional digital asset custody at trillion-dollar scale.

• **Fireblocks**: threshold ECDSA MPC for $3T+ annual transaction volume. Private key split 2-of-3; no single server holds the complete key.
• **Google PAPAYA**: MPC for cross-site ad measurement without revealing user browsing history to advertisers or Google.
• **iDASH competition**: annual secure computation on genomic data competition. MPC implementations now run genome-wide association studies on encrypted data.
• **Facebook private heavy hitters**: MPC protocol for finding popular crash reports without revealing which crashes individual users experienced.

Garbled Circuits: Encrypting a Circuit

Garbled Circuits (Yao, 1986) allow two parties to evaluate any boolean circuit on private inputs. The circuit is "garbled" (each wire has two random labels for true/false). Only the evaluator can follow the correct path through the circuit to the output.

Garbled circuits require one Oblivious Transfer per input bit of the evaluator. Performance: ~10 million gates/second with optimizations (free XOR, half-gates). Used for privacy-preserving ML inference: running a neural network on encrypted user data.

Oblivious Transfer: Sending Without Knowing

Oblivious Transfer (OT) is a fundamental MPC primitive: a sender has two messages (m0, m1); a receiver chooses bit b and receives m_b. The sender does not learn b; the receiver learns only m_b, not the other message. OT is the building block for garbled circuit evaluator input selection.

OT extension (IKNP protocol) generates n OTs from k base OTs in O(n) symmetric operations. This makes OT practical at scale: 1 million OTs per second on a network connection. OT is the information-theoretic lower bound of MPC - any two-party computation requires OT.

Secret Sharing MPC: Arithmetic on Private Data

Secret sharing MPC (GMW, BGW protocols) evaluates arithmetic circuits on shares. Addition is free (local); multiplication requires interaction. Achieves malicious security without a trusted dealer. Used for multi-party private set intersection and federated learning.

MOTION (University of Bochum) and MP-SPDZ are production-grade MPC frameworks. Obliv-C adds MPC semantics to C code. Google uses MPC for privacy-preserving ad measurement across browsers.

Real-World MPC: Production Cases

MPC is no longer just theory: Fireblocks uses threshold ECDSA for crypto custody, Google uses MPC for ad measurement, and privacy-preserving machine learning on medical data uses MPC for federated analysis without sharing raw data.

The 2023 MPC market is estimated at $400M+ in implementations for financial services alone. Fireblocks processes $3T+ in transactions annually using threshold ECDSA. The latency overhead for MPC vs plaintext: 2-10x for most practical applications with LAN connectivity.

Key Ideas

• **Garbled circuits**: Yao 1986. Evaluate any boolean circuit on encrypted inputs. O(1) decryption per gate; O(n) OTs for receiver input. Used in privacy-preserving ML inference.
• **Oblivious Transfer**: sender has m0/m1; receiver gets m_b without sender learning b. Information-theoretically necessary for MPC. OT extension scales to millions/second.
• **Secret sharing MPC**: Shamir-based arithmetic circuits. Addition = local; multiplication = Beaver triple + 1 communication round. Used in federated learning.
• **Production MPC**: Fireblocks threshold ECDSA, Google PSI for passwords, Apple CSAM detection, private ML aggregation.

Related Topics

MPC connects foundational theory to practical distributed security:

• Secret Sharing — Shamir secret sharing is the foundation of secret sharing MPC. t-of-n threshold schemes provide both sharing and computation.
• ZK Proofs — Malicious-secure MPC uses ZK proofs to verify that each party follows the protocol correctly.
• Homomorphic Encryption — Homomorphic encryption is an alternative to MPC for single-party computation on encrypted data with different tradeoffs.

Вопросы для размышления

• Garbled circuits require one OT per input bit. For a 256-bit AES key evaluation, how many OTs are needed, and what is the approximate computation cost?
• PSI (Private Set Intersection) for contact discovery requires O(n log n) communication. At 500 contacts per user and 1 billion users, is server-side PSI practical?
• Google uses MPC for ad attribution across Chrome and Android. What trust assumptions does this require from users compared to sending raw browsing data?

Связанные уроки

• prob-25-info-theory