Cryptography
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.
What does "garbling" a circuit prevent?
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.
What makes Oblivious Transfer the foundational primitive of MPC?
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.
Why is multiplication in secret sharing MPC more expensive than addition?
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.
What security property does threshold ECDSA in custody wallets provide over HSM storage?
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?