The Millionaires' Problem

Andrew Yao, 1982: Two millionaires want to know who is richer without revealing their actual wealth to each other. This deceptively simple problem launched the field of secure computation.

MPC: Formal Definition

n parties P₁, ..., P_n each hold private input x_i. They wish to jointly compute y = f(x₁, ..., x_n) such that each party learns only y (and nothing else about others' inputs).

  IDEAL WORLD:                    REAL WORLD:
  P1 --x1--> [TTP] --y--> P1     P1 <----protocol----> P2
  P2 --x2--> [TTP] --y--> P2         (no trusted party)
  ...                             ...
  Pn --xn--> [TTP] --y--> Pn     Pn <----protocol----> P1

Security Models

The strength of an MPC protocol depends on what adversary it resists. Two orthogonal axes: adversary behavior and corruption threshold.

Shamir's Secret Sharing

Adi Shamir (1979): A (t, n)-threshold scheme where any t+1 shares reconstruct the secret, but t or fewer shares reveal nothing. Based on polynomial interpolation over a finite field.

  Share(s, t, n):
    1. Choose random a₁, a₂, ..., aₜ ∈ F_p
    2. Define polynomial: f(x) = s + a₁x + a₂x² + ... + aₜxᵗ
    3. Give party Pᵢ the share: (i, f(i))

  Reconstruct(shares):
    Given t+1 points (xᵢ, yᵢ), use Lagrange interpolation:
    s = f(0) = Σᵢ yᵢ · Πⱼ≠ᵢ (xⱼ / (xⱼ - xᵢ))  mod p

Additive Secret Sharing

The simplest form of secret sharing: split a value into n random shares that sum (or XOR) to the secret. Every party must participate in reconstruction — a (n, n)-threshold scheme.

  Share(s):
    r₁, ..., rₙ₋₁ ← random bits
    rₙ = s ⊕ r₁ ⊕ ... ⊕ rₙ₋₁

  Reconstruct:
    s = r₁ ⊕ r₂ ⊕ ... ⊕ rₙ

  Share(s):
    r₁, ..., rₙ₋₁ ← random in F_p
    rₙ = s - r₁ - ... - rₙ₋₁ mod p

  Reconstruct:
    s = r₁ + r₂ + ... + rₙ mod p

Beaver Triples

Donald Beaver (1991): Precompute random multiplication triples (a, b, c) where c = a·b in an offline phase. Use them to multiply shared values in the online phase with a single round of communication.

  Given: shares [x], [y], and precomputed triple ([a], [b], [c]) where c = a·b

  1. Each party computes and opens:
     [d] = [x] - [a]  →  reveal d = x - a
     [e] = [y] - [b]  →  reveal e = y - b

  2. Each party locally computes:
     [x·y] = d·e + d·[b] + e·[a] + [c]

  Correctness: d·e + d·b + e·a + c
             = (x-a)(y-b) + (x-a)b + (y-b)a + ab
             = xy - ay - xb + ab + xb - ab + ay - ab + ab = xy  ✓

GMW Protocol

Goldreich, Micali, Wigderson (1987): Evaluate a Boolean circuit gate-by-gate using XOR secret shares. XOR gates are free; AND gates require oblivious transfer.

  XOR gate (z = x ⊕ y):
    Alice: z_A = x_A ⊕ y_A     (local computation — FREE)
    Bob:   z_B = x_B ⊕ y_B

  AND gate (z = x ∧ y):
    z = (x_A ⊕ x_B) ∧ (y_A ⊕ y_B)
      = x_A·y_A ⊕ x_A·y_B ⊕ x_B·y_A ⊕ x_B·y_B
    Alice knows x_A·y_A, Bob knows x_B·y_B
    Cross-terms x_A·y_B and x_B·y_A require 1-out-of-4 OT

Oblivious Transfer (OT)

The fundamental primitive of two-party computation. In 1-out-of-2 OT, a sender holds two messages (m₀, m₁). The receiver with choice bit b learns m_b and nothing about m_1-b. The sender learns nothing about b.

Garbled Circuits

Yao's garbled circuit protocol (1986): The garbler encrypts a Boolean circuit gate-by-gate. The evaluator decrypts exactly one output per gate without learning intermediate wire values.

Garbled Circuit Optimizations

Decades of research have reduced the cost of garbled circuits from 4 ciphertexts per gate to as low as 1.5.

BMR Protocol

Beaver, Micali, Rogaway (1990): Extends garbled circuits to n parties while maintaining constant rounds. All parties jointly generate one garbled circuit, then evaluate it non-interactively.

SPDZ Protocol

Damgard, Pastro, Smart, Zakarias (2012): Achieves malicious security with dishonest majority using information-theoretic MACs on all shared values. Name pronounced "Speedz."

  Each shared value x has MAC:  [x] = (x₁,...,xₙ)  with  [α·x] = MAC shares
  Global MAC key α is itself secret-shared: α = α₁ + ... + αₙ

  OFFLINE PHASE (expensive):
    Generate Beaver triples with MACs using Somewhat HE or OT
    All triples: ([a], [b], [c]) with [α·a], [α·b], [α·c]

  ONLINE PHASE (fast):
    Addition: [x+y] = [x] + [y], MACs add locally
    Multiplication: Beaver's protocol using precomputed triples
    Output: Open value, then MAC-check to detect cheating

  MAC CHECK: Verify α·x = Σᵢ m_i where m_i are MAC shares
    → Any deviation by malicious party detected with prob 1 - 2⁻ˢ

Shamir-Based MPC (Honest Majority)

When t < n/2 parties are corrupt, Shamir secret sharing enables highly efficient MPC over arithmetic circuits with information-theoretic security. The BGW protocol (1988) is the foundation.

  Share inputs: Each Pᵢ shares xᵢ with degree-t Shamir sharing

  Addition gate:  [x+y]ᵢ = [x]ᵢ + [y]ᵢ           (local, free)
  Constant mult:  [c·x]ᵢ = c · [x]ᵢ               (local, free)

  Multiplication gate (the hard part):
    1. Local multiply: hᵢ = [x]ᵢ · [y]ᵢ            (degree 2t polynomial!)
    2. Degree reduction: Reshare hᵢ with degree t
       → Each party sends shares to all others        (O(n²) communication)
       → Recombine using Lagrange on degree-2t points
    3. Result: degree-t sharing of x·y

Private Set Intersection (PSI)

Two parties hold sets X and Y. They want to learn X ∩ Y without revealing elements not in the intersection. A flagship MPC application with major real-world deployments.

Privacy-Preserving Machine Learning

MPC enables training and inference on joint datasets without revealing raw data. Critical for healthcare, finance, and cross-organizational collaboration.

More MPC Applications

MPC + FHE: Combining Approaches

Fully Homomorphic Encryption and MPC are complementary. FHE enables non-interactive computation on encrypted data; MPC distributes trust. Combining them yields powerful hybrid protocols.

Communication Complexity & Rounds

Communication is the dominant bottleneck in MPC. Understanding the cost structure is essential for choosing the right protocol.

Implementation Frameworks

Several mature open-source frameworks make MPC accessible to practitioners. Each targets different protocol families and security models.

# MP-SPDZ program — each party inputs their wealth privately
wealth_alice = sint.get_input_from(0)    # Party 0's private input
wealth_bob = sint.get_input_from(1)      # Party 1's private input

result = (wealth_alice > wealth_bob)      # Secure comparison
print_ln("Alice is richer: %s", result.reveal())  # Open result only

Real-World Deployments

MPC has moved from theory to production. Major technology companies deploy MPC at scale for privacy-critical applications.

Performance Benchmarks

Indicative orders of magnitude for representative computations at 128-bit security; published figures vary widely with hardware, network and implementation.

Code: Shamir Secret Sharing (1/2)

A complete implementation of Shamir's (t, n)-threshold secret sharing over a prime field.

import secrets

def shamir_share(secret: int, t: int, n: int, p: int) -> list:
    """Split secret into n shares with threshold t+1."""
    # Random polynomial: f(x) = secret + a1*x + a2*x^2 + ... + at*x^t
    coeffs = [secret] + [secrets.randbelow(p) for _ in range(t)]

    def eval_poly(x):
        return sum(c * pow(x, i, p) for i, c in enumerate(coeffs)) % p

    return [(i, eval_poly(i)) for i in range(1, n + 1)]

Code: Shamir Secret Sharing (2/2)

def lagrange_interpolate(shares: list, p: int) -> int:
    """Reconstruct secret from t+1 shares using Lagrange interpolation."""
    secret = 0
    for i, (xi, yi) in enumerate(shares):
        num, den = 1, 1
        for j, (xj, _) in enumerate(shares):
            if i != j:
                num = (num * (-xj)) % p
                den = (den * (xi - xj)) % p
        secret = (secret + yi * num * pow(den, -1, p)) % p
    return secret

# Example: (2, 5)-threshold sharing — need 3 of 5 shares
p = 2**127 - 1  # Mersenne prime
shares = shamir_share(42, t=2, n=5, p=p)
assert lagrange_interpolate(shares[:3], p) == 42   # Any 3 suffice
assert lagrange_interpolate(shares[2:5], p) == 42   # Any 3 suffice

Code: Beaver Triple Multiplication (1/2)

Two-party secure multiplication using precomputed Beaver triples over additive secret sharing.

class Party:
    def __init__(self, x_share, a_share, b_share, c_share, p):
        self.x = x_share; self.a = a_share
        self.b = b_share; self.c = c_share; self.p = p

    def compute_masked(self, y_share):
        """Step 1: Compute and broadcast masked values."""
        self.d_share = (self.x - self.a) % self.p   # [d] = [x] - [a]
        self.e_share = (y_share - self.b) % self.p   # [e] = [y] - [b]
        return self.d_share, self.e_share

    def compute_product(self, d, e, is_party_1=False):
        """Step 2: Compute share of x*y from opened d, e."""
        # [x*y] = d*e + d*[b] + e*[a] + [c]
        result = (d * self.b + e * self.a + self.c) % self.p
        if is_party_1:
            result = (result + d * e) % self.p  # Only P1 adds d*e
        return result

Code: Beaver Triple Multiplication (2/2)

# Simulation: x=7, y=13, a=3, b=5, c=15 (c = a*b), p=97
p = 97
# Additive shares: x=7 → (2, 5), y=13 → (8, 5), etc.
p1 = Party(2, 1, 3, 10, p)   # Party 1 shares
p2 = Party(5, 2, 2, 5,  p)   # Party 2 shares
d1, e1 = p1.compute_masked(8); d2, e2 = p2.compute_masked(5)
d, e = (d1 + d2) % p, (e1 + e2) % p     # Open d=4, e=8
z1 = p1.compute_product(d, e, True); z2 = p2.compute_product(d, e)
assert (z1 + z2) % p == (7 * 13) % p     # 91 mod 97 = 91 ✓

Current Research Frontiers