Garbled Circuits for Two-Party Computation
You'll learn how Yao's garbled circuit protocol enables two parties to jointly compute a function without revealing their private inputs.
The Core Problem
Imagine you and a colleague want to compare salaries to see who earns more, but neither wants to reveal the actual amount. This is the classic two-party computation problem: computing f(x,y) where you hold x, they hold y, and neither learns the other's input—only the result.
How Garbled Circuits Work
Yao's garbled circuit protocol (1986) solves this by treating the function as a Boolean circuit (logic gates: AND, OR, NOT):
- Circuit Construction: One party (the "garbler") converts the function into a circuit of logic gates
- Gate Garbling: Each gate's truth table is encrypted using random labels representing wire values (0 or 1)
- Oblivious Transfer: The other party (the "evaluator") obtains labels for their input bits without revealing which values they chose
- Evaluation: The evaluator processes the garbled gates using the labels, learning only the final output
- Output Decoding: The final wire labels are mapped back to the actual result
The beauty: the evaluator sees only encrypted gate tables and can decrypt exactly one output per gate—revealing nothing about intermediate values or the garbler's input.
Practical Implementation Challenges
- Circuit size: Complex functions require millions of gates, creating bandwidth overhead
- Oblivious transfer overhead: Expensive cryptographic operations for input selection
- Single-use limitation: Each garbled circuit can only be evaluated once securely
- Malicious security: Basic protocol assumes honest-but-curious parties; defending against cheating requires expensive zero-knowledge proofs or cut-and-choose techniques
Key Takeaway: Garbled circuits enable secure two-party computation by encrypting Boolean circuit gates so one party can evaluate the function without learning anything beyond the output, though practical implementations face significant performance and security challenges.