Yao's Garbled Circuits: Computing on Data Neither Party Sees

The problem: computing on inputs you're not allowed to see

Suppose Alice holds input x and Bob holds input y, and they want to compute f(x, y). The naive solution is to hand everything to a trusted third party. Secure two-party computation (2PC) removes that trusted party: the protocol itself acts as the trusted intermediary, so both learn f(x, y) and nothing else.

Yao's insight was to represent f as a Boolean circuit of AND/XOR/NOT gates, then encrypt that circuit so it can be evaluated blind. The canonical illustration is Yao's own millionaires' problem: two people compare wealth to see who is richer without disclosing amounts. Real applications generalize this:

• Private set intersection — which contacts do two people share?
• Privacy-preserving auctions — highest bid without revealing bids.
• Secure ML inference — run a model on data the model owner never sees.

Crucially, garbled circuits are general-purpose: any function expressible as a circuit can be evaluated securely, which is why the technique underpins so much of applied cryptography.

How it works: garbling wires, gates, and the double-encrypted truth table

The garbler compiles f into a Boolean circuit, then processes it in five conceptual steps.

1. Assign wire labels. For every wire w, pick two random k-bit keys: W_0 (represents bit 0) and W_1 (represents bit 1). The evaluator will only ever hold one of the two, and cannot tell which bit it encodes.
2. Garble each gate. For a gate computing c = g(a, b), build a 4-row table. Each row encrypts the correct output-wire key under the two relevant input-wire keys: Enc(A_i, B_j) → C_{g(i,j)}.
3. Permute the rows so their order leaks nothing about the truth table.
4. Transfer keys. The garbler sends its own input keys directly. The evaluator obtains keys for its inputs via 1-out-of-2 oblivious transfer (OT), so the garbler never learns which bit the evaluator chose, and the evaluator gets only the one key it needs.
5. Evaluate. Holding one input key per wire, the evaluator decrypts exactly the one gate row that works, yielding an output-wire key, and repeats through the circuit.

garble_gate(g, A0,A1, B0,B1, C0,C1):
  rows = []
  for i in {0,1}, j in {0,1}:
     out = C0 if g(i,j)==0 else C1
     rows.append( Enc(A_i, Enc(B_j, out)) )
  shuffle(rows)   # hide truth-table order
  return rows

A final output-decoding table maps the final wire keys back to real bits.

Complexity and a worked AND-gate trace

Let the circuit have |C| gates and n input bits. In classic Yao, garbling is O(|C|) symmetric encryptions and evaluation is O(|C|) decryptions; communication is O(|C| · k) bits (four ciphertexts per gate at security parameter k, typically 128). OT cost is O(n) and, critically, the protocol is constant-round — round count does not grow with circuit depth, which is its headline advantage over gate-by-gate interactive schemes.

Modern optimizations slash the constant. With point-and-permute the evaluator decrypts just 1 row instead of trying all 4; with free-XOR, XOR gates cost 0 ciphertexts; with half-gates, an AND gate needs only 2 ciphertexts.

AND gate, inputs a,b, output c
  keys:  A0,A1  B0,B1  C0,C1
  truth: 0&0=0  0&1=0  1&0=0  1&1=1
  garbled rows (then shuffled):
    Enc(A0,B0 -> C0)
    Enc(A0,B1 -> C0)
    Enc(A1,B0 -> C0)
    Enc(A1,B1 -> C1)
  evaluator holds A1,B1 -> only the 4th row decrypts -> gets C1 (=bit 1)
  it never learns a=1 or b=1, only the opaque key C1

So the evaluator computes 1 AND 1 = 1 without ever seeing a plaintext bit.

Where it's used in real systems

Garbled circuits moved from theory to deployed infrastructure over the last decade:

• Private set intersection at scale — contact-discovery and ad-conversion measurement systems (e.g., private matching between advertiser and platform user sets) build on 2PC primitives.
• Password / credential checks — protocols that test whether your password appears in a breach corpus without either side revealing the full set.
• Threshold and MPC wallets — splitting an ECDSA signing key so no single machine holds it; several custody products use garbled-circuit-based 2PC for the signing step.
• Privacy-preserving ML inference — frameworks such as ABY, MP-SPDZ, and mixed-protocol systems combine garbled circuits (good for comparisons, max, non-linearities like ReLU) with arithmetic secret sharing (good for multiplications).
• Genomic and medical analytics — running risk scores across institutions that legally cannot pool raw records.

In practice engineers rarely garble everything: they use GC for the Boolean-heavy parts (comparisons, bit tests) and switch to arithmetic sharing for multiply-add-heavy parts, converting between representations mid-protocol.

How it compares to the alternatives

Garbled circuits are one of three mainstream approaches to secure computation, each with a sharp tradeoff.

• vs. GMW / secret-sharing MPC: GMW also evaluates circuits but needs a round of interaction per circuit layer, so latency scales with depth. Yao is constant-round, winning on high-latency networks (WANs) but sending more data per gate. Secret-sharing shines for arithmetic and 3+ parties.
• vs. homomorphic encryption (HE): Fully homomorphic encryption is non-interactive — one party can compute on ciphertext alone — but per-gate cost is orders of magnitude higher and bootstrapping is expensive. Garbled circuits need a live counterparty and OT, yet run far faster for one-shot Boolean functions.
• vs. trusted execution (SGX/enclaves): Enclaves are fast but rest on hardware trust and have a long history of side-channel breaks; GC's guarantees are purely cryptographic.

The rule of thumb: choose Yao for low-round-count, Boolean-heavy, two-party tasks over slow links; choose secret sharing for arithmetic or many parties; choose HE when interaction is impossible.

Pitfalls, failure modes, and significance

The most important caveat: plain Yao is only secure against semi-honest (honest-but-curious) adversaries. If the garbler is malicious it can garble the wrong function — e.g., a circuit that leaks the evaluator's input — and the evaluator can't detect it. Achieving malicious security requires expensive add-ons like cut-and-choose (garble many copies, open some to check, evaluate the rest), which multiplies cost.

• Garble once, or leak everything. A garbled circuit is single-use. Reusing wire labels across evaluations breaks security, because two decryptable rows reveal the truth-table structure.
• OT is the trust hinge. Break the oblivious transfer and the whole guarantee collapses; OT extension (IKNP) makes it cheap but must be implemented carefully.
• Circuit size dominates cost. Everything is per-gate, so a function that's cheap in plaintext (a loop, a memory lookup) can explode into millions of gates. Oblivious RAM and specialized sub-circuits mitigate this.

Yao's construction was revolutionary: it proved that any efficiently computable function can be evaluated privately, launching the entire field of practical MPC. Decades later, free-XOR, half-gates, and OT extension turned a 1986 theorem into production cryptography.

Garbled-circuit garbling schemes and where 2PC alternatives land

Scheme / technique	Ciphertexts per AND gate	Ciphertexts per XOR gate	Note
Classic Yao (1986)	4	4	Full 4-row garbled table per gate
Point-and-permute (BMR 1990)	4	4	Evaluator decrypts only 1 row, not 4
Row reduction (GRR3)	3	3	First row fixed to all-zeros, omitted
Free-XOR (Kolesnikov-Schneider 2008)	3	0	XOR done by XORing wire keys
Half-gates (Zahur-Rosulek-Evans 2015)	2	0	Long-standing 2-ciphertext optimum for a while
Homomorphic encryption (alt. to GC)	n/a	n/a	Non-interactive but far higher per-op cost