Secure Multi-Party Computation

Overview

Secure multi-party computation (MPC) enables n parties, each holding private input x_i, to jointly compute a function f(x_1, ..., x_n) such that:

Correctness: All parties learn the correct output
Privacy: No party learns anything beyond the output and what can be inferred from their own input

Adversary models:

Semi-honest (passive): Adversary follows the protocol but tries to learn from transcripts
Malicious (active): Adversary can deviate arbitrarily from the protocol
Covert: Adversary cheats with bounded probability of detection

Corruption threshold: Protocols tolerate t < n/2 (honest majority) or t < n (dishonest majority, requiring computational assumptions and no guaranteed output delivery).

Yao's Garbled Circuits

The foundational two-party computation protocol (Yao, 1986).

Setup: Two parties, Alice (garbler) and Bob (evaluator), wish to compute f(x, y) where Alice holds x, Bob holds y.

Protocol:

Garbling: Alice assigns two random labels (k_0, k_1) to each wire in the Boolean circuit for f. For each gate with input wires (a, b) and output wire c, she creates a garbled table: four ciphertexts encrypting the output label under the corresponding input labels.

For an AND gate: Enc_{k_a^i, k_b^j}(k_c^{i AND j}) for all (i,j) in {0,1}^2

The table entries are randomly permuted (point-and-permute optimization: each label carries a selection bit to identify the correct row without trial decryption).
Transfer: Alice sends the garbled circuit and her input labels (for her actual input bits). Bob obtains his input labels via oblivious transfer (one per input bit).
Evaluation: Bob evaluates the circuit gate by gate, decrypting exactly one entry per gate using the labels he possesses. He obtains the output labels and can determine the output bits.

Optimizations:

Free XOR (Kolesnikov-Schneider): XOR gates cost zero communication by choosing labels with a global offset Delta. If k_a^0 XOR k_a^1 = Delta for all wires, then XOR of labels directly yields the output label.
Half gates (Zahur-Rosulek-Evans): AND gates require only 2 ciphertexts (down from 4). Combines two "half gates" -- one known to the garbler, one to the evaluator.
Row reduction: Derive one entry from the gate key, reducing table from 4 to 3 entries.

Complexity: Communication O(|C| * kappa) where |C| is circuit size and kappa is security parameter. Round complexity: constant (one round for OT + garbled circuit transfer).

GMW Protocol

The Goldreich-Micali-Wigderson protocol for multi-party computation.

Approach: Secret-share each wire value among all parties. Process gates interactively:

XOR gates: Each party locally XORs their shares (free, no interaction)
AND gates: Require interaction via OT (or precomputed multiplication triples)

For n parties with semi-honest security (honest majority): use additive secret sharing. Each wire value v is split into shares v_1, ..., v_n with v = v_1 XOR ... XOR v_n.

Round complexity: O(depth of circuit). Each AND gate layer requires one round of interaction.

Malicious security extension: Add zero-knowledge proofs for each step, or use the BMR (Beaver-Micali-Rogaway) protocol to convert GMW into a constant-round protocol.

A (t, n)-threshold scheme: any t shares reconstruct the secret; fewer than t shares reveal nothing.

Construction: To share secret s among n parties with threshold t:

Choose random polynomial p(x) of degree t-1 with p(0) = s
Give party i the share (i, p(i))
Reconstruction: Any t shares determine p(x) via Lagrange interpolation, recover s = p(0)

Information-theoretic security: t-1 shares are uniformly random (independent of s). No computational assumptions needed.

Properties: Linear -- shares of s_1 and s_2 can be locally added to get shares of s_1 + s_2. Multiplication of shared values requires interaction (degree doubling: product polynomial has degree 2(t-1), requiring degree reduction).

Special case of (n, n)-threshold: s = s_1 + s_2 + ... + s_n (mod q), where s_1, ..., s_{n-1} are random and s_n = s - sum_{i<n} s_i.

Simpler than Shamir but requires all parties for reconstruction. Commonly used in two-party protocols and as a building block in SPDZ.

For (t, n)-threshold with small n: each party holds C(n-1, t-1) shares from all subsets of size n-t. Enables efficient local computation for small party counts.

Oblivious Transfer (OT)

1-out-of-2 OT: Sender has (m_0, m_1), receiver has choice bit b. Receiver learns m_b; sender learns nothing about b.

OT is complete for MPC: any secure computation can be built from OT alone (Kilian, Ishai-Prabhakaran-Sahai).

Constructions:

Based on public-key crypto: Naor-Pinkas (DDH), Chou-Orlandi (simplified)
OT extension (IKNP): Generate many OTs from a small number of base OTs (e.g., 128 base OTs -> millions of OTs using only symmetric crypto). Cost: ~2 hash evaluations per OT after base OTs.
Silent OT (Boyle-Couteau-Gilboa-Ishai-Kohl-Scholl): Generate correlated OTs with sublinear communication using pseudorandom correlation generators.

Variants:

1-out-of-n OT: Receiver picks one of n messages
OT with preprocessing: Base OTs in offline phase, fast online extension
Random OT: Both messages and choice bit are random; useful as a correlation

MPC Frameworks

SPDZ (pronounced "Speedz")

Multi-party protocol for arithmetic circuits over Z_p, secure against a dishonest majority with malicious adversaries.

Key ideas:

Offline/online paradigm: Expensive preprocessing generates multiplication triples (Beaver triples: [a], [b], [c] where c = ab). Online phase uses these triples for fast, constant-round multiplication.
MAC-based verification: Each shared value [x] carries an information-theoretic MAC: [x] = (x_i, alpha * x + r_i) where alpha is the global MAC key. Any cheating is detected at verification time.
Online multiplication: Given triple ([a], [b], [c]) and values to multiply ([x], [y]):
1. Open epsilon = x - a and delta = y - b
2. [xy] = [c] + epsilon*[b] + delta*[a] + epsilon*delta

Variants: SPDZ2k (computation over Z_{2^k} instead of Z_p, matching machine arithmetic), Overdrive (improved preprocessing), MASCOT (OT-based triple generation).

ABY Framework

Supports three sharing types with efficient conversions:

Arithmetic sharing: Additive shares over Z_{2^l}, efficient for additions and multiplications
Boolean sharing: XOR shares, efficient for comparisons and bitwise operations
Yao sharing: Garbled circuit evaluation, constant-round

Conversions: A2B, B2A, Y2B, B2Y, A2Y, Y2A -- enable choosing the most efficient representation for each part of the computation. For example, use arithmetic for linear operations and Boolean/Yao for comparisons.

Private Set Intersection (PSI)

Compute the intersection of two sets without revealing non-intersecting elements.

Approaches:

OT-based PSI (KKRT): Encode set elements using OT extension and compare encodings. Communication: O(n * kappa) for sets of size n.
DH-based PSI: Both parties raise elements to secret exponents, compare. Simple but O(n) exponentiations.
Circuit-based PSI: Evaluate comparison circuit via garbled circuits or GMW. Enables computing functions of the intersection (PSI-cardinality, PSI-sum).
Unbalanced PSI: Optimized for |S_1| >> |S_2| (e.g., server has large database, client has small set). Uses cuckoo hashing and batched OT.

Applications: Contact discovery, ad measurement, supply chain matching, threat intelligence sharing.

Private Information Retrieval (PIR)

Client retrieves item i from server's database without server learning i.

Information-theoretic PIR: Requires multiple non-colluding servers. k-server PIR achieves O(n^{1/(2k-1)}) communication.

Computational PIR (cPIR): Single server, based on computational assumptions:

LWE-based: Encode query as an LWE encryption of e_i (unit vector). Server computes encrypted dot product with database. Communication: O(sqrt(n)) with SealPIR/MulPIR preprocessing.
FHE-based: Encrypt the index, server homomorphically evaluates lookup. Most flexible but computationally expensive.
DPF-based (Distributed Point Function): Two-server PIR with near-optimal O(lambda * log n) communication using function secret sharing.

Practical considerations: For large databases, the server must touch every element (otherwise access pattern leaks information). Amortized approaches (batch PIR) and preprocessing reduce per-query cost.

Secure Aggregation

Compute sum of private values without revealing individual contributions. Critical for federated learning.

Protocols:

Pairwise masking (Bonawitz et al.): Each pair of users generates a shared random mask. Masks cancel in the sum. Handles dropouts via threshold secret sharing of mask seeds. Communication: O(n^2) for n users.
DPF-based aggregation: Sublinear communication using distributed point functions.
HE-based: Users encrypt contributions, server sums ciphertexts, obtains encrypted sum. Requires threshold decryption or trusted key holder.

Differential privacy integration: Add calibrated noise to the aggregate for formal privacy guarantees. Distributed noise generation ensures no single party sees the true aggregate.

Performance Landscape

| Protocol | Rounds | Communication | Computation | Security | |----------|--------|---------------|-------------|----------| | Garbled circuits | Constant | O(|C| * kappa) | O(|C|) sym ops | Malicious (2PC) | | GMW | O(depth) | O(|C| * kappa) | O(|C|) OTs | Semi-honest | | SPDZ online | O(depth) | O(|C| * n) | O(|C|) field ops | Malicious | | ABY (mixed) | Varies | Varies | Varies | Semi-honest |

Modern MPC achieves millisecond-scale latency for simple functions and can process billions of gates per second for batch computations. The offline/online paradigm makes interactive applications practical by front-loading expensive preprocessing.