Ideal vs. Real World Paradigm

Security is defined by comparison to an ideal world where a trusted third party (TTP) collects all inputs, computes f, and distributes outputs. A protocol is secure if no adversary can distinguish the real execution from the ideal one.

  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

Construction

  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

Beaver's Multiplication Protocol

  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  ✓

Gate-by-Gate Evaluation

Each wire w carries a secret-shared bit: w = w_A ⊕ w_B (Alice holds w_A, Bob holds w_B).

  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

Half-Gates Technique (Zahur, Rosulek, Evans 2015)

Key insight: decompose AND(a, b) into two "half-gates" — one where the garbler knows one input, one where the evaluator knows one input. Each half-gate costs 1 ciphertext, totaling 2 ciphertexts per AND gate. Combined with Free XOR, this is optimal for a class of linear garbling schemes.

SPDZ Architecture: Offline + Online

  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⁻ˢ

BGW Protocol

  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

MP-SPDZ Example: Millionaires' Problem

  # 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

  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)]

  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

  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

  # 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=6
  z1 = p1.compute_product(d, e, True); z2 = p2.compute_product(d, e)
  assert (z1 + z2) % p == (7 * 13) % p     # 91 mod 97 = 91 ✓