Garbled Circuits

Core Idea

Yao's garbled circuits enable two-party secure computation. The garbler converts a Boolean circuit into a "garbled" version where each wire carries random labels instead of 0/1 values, and each gate's truth table is encrypted so that knowing input labels reveals only the output label — not whether it represents 0 or 1. The evaluator obtains their input labels via oblivious transfer and evaluates the garbled circuit gate by gate, learning only the final output. Key optimizations (point-and-permute, free XOR, half-gates) reduce cost from 4 ciphertexts per gate to 1.5 for AND gates and zero for XOR gates, making garbled circuits practical for real applications.

Explainer

Yao's garbled circuits (1986) are the foundational technique for two-party secure computation. The idea is elegant: convert the function to be computed into a Boolean circuit, then "garble" the circuit so it can be evaluated on encrypted values without revealing any intermediate results. The construction involves two parties — the garbler (who builds the garbled circuit) and the evaluator (who evaluates it) — and achieves the remarkable property that the evaluator learns the function's output but nothing else, while the garbler learns nothing at all.

The garbling process works as follows. For each wire in the circuit, the garbler generates two random labels — one representing 0 and one representing 1. For each gate, the garbler creates a garbled truth table: four entries, one for each combination of input values, where each entry encrypts the corresponding output label under the two input labels. The entries are randomly permuted so their position doesn't reveal information. The garbler sends the garbled circuit (all garbled truth tables) to the evaluator, along with the labels corresponding to the garbler's own input bits. The evaluator obtains labels for their own input bits via oblivious transfer (ensuring the garbler doesn't learn the evaluator's input). The evaluator then evaluates gate by gate: for each gate, they use their two input labels to decrypt exactly one truth table entry, obtaining the output label. At the final output wires, a decoding table maps labels back to 0/1.

Three optimizations have transformed garbled circuits from a theoretical construct into a practical tool. Point-and-permute attaches a signal bit to each label, allowing the evaluator to identify the correct truth table entry directly (without trial decryption), reducing from 4 decryption attempts to 1. Free XOR establishes a global offset R such that the two labels on every wire differ by R; XOR gates then require zero ciphertexts — the output label is simply the XOR of input labels. Half-gates reduce AND gate cost from 3 to 2 ciphertexts by decomposing each AND into two specialized "half-gates." Together, these optimizations mean a garbled circuit costs essentially 2 AES evaluations per AND gate and nothing per XOR gate.

The main limitations of garbled circuits are one-time use (each garbled circuit can be evaluated only once, requiring a fresh circuit per computation) and linear communication (the garbled circuit must be transmitted in its entirety, costing bandwidth proportional to the circuit size). For repeated evaluations of the same function, secret-sharing-based MPC protocols (like SPDZ) may be more efficient because they amortize setup cost. Garbled circuits excel for one-shot computations and when minimizing round complexity is important (the basic protocol requires only constant rounds of interaction). Modern MPC frameworks like EMP-toolkit and ABY combine garbled circuits with other techniques, automatically selecting the most efficient approach for each sub-computation.