Garbled Circuits: Yao's Secure Two-Party Computation

From truth tables to garbled tables

Every boolean gate, whether AND, OR, or XOR, can be fully described by a truth table listing its output for each combination of input bits. In Yao's protocol the garbler starts by assigning each wire in the circuit two random cryptographic labels, one representing 0 and one representing 1, so a label by itself carries no meaning to an outside observer. For each gate the garbler encrypts the output label corresponding to each row of the truth table using the two input labels of that row as a symmetric key, typically via a keyed hash or an authenticated cipher. The four resulting ciphertexts are shuffled into random order so their position no longer hints at which row they came from, producing what is called a garbled table. This process repeats gate by gate across the entire circuit, and it can all be done offline by the garbler before any interaction with the evaluator takes place. The result is that someone holding only garbled tables and no labels learns absolutely nothing about the function's structure or intermediate values, since every ciphertext looks like random noise without the matching pair of input labels to decrypt it.

Oblivious transfer: handing over inputs blindly

The evaluator needs the garbled labels that correspond to their own private input bits, but obtaining them creates a delicate problem: the garbler must not learn which labels were requested, since that would reveal the evaluator's input, while the evaluator must not receive both labels for any wire, since that would let them evaluate the circuit on inputs other than their own. Oblivious transfer solves exactly this. In a 1-out-of-2 oblivious transfer, the garbler holds two labels for a wire and the evaluator holds a single selection bit; after running the protocol the evaluator learns only the label matching their bit, and the garbler learns nothing about which one was chosen. Modern implementations build oblivious transfer from public-key techniques such as elliptic-curve Diffie-Hellman, and clever extension techniques allow a handful of expensive base OTs to be stretched into millions of cheap ones using only symmetric-key operations. For the garbler's own inputs no OT is needed at all; the garbler simply sends the matching labels directly, since only the garbler ever knew the mapping between labels and bit values in the first place.

Evaluating the garbled circuit

Once the evaluator holds one label per input wire, evaluation proceeds gate by gate in topological order without ever needing to interact with the garbler again. At each gate the evaluator has exactly one label for each input wire and tries to decrypt each of the four ciphertexts in the garbled table using those two labels as a key; by construction only one ciphertext decrypts successfully, yielding a single valid output label for that gate's output wire, while the other three decrypt to garbage that a well-designed scheme lets the evaluator detect and discard. That output label then feeds as an input label into whichever gate consumes that wire next, and the process cascades until every gate has been evaluated. Because the evaluator only ever sees one label per wire, chosen obliviously and looking like random bits, they can compute the entire function while learning nothing about intermediate values, not even whether an internal wire carried a 0 or a 1. The final output wires are handled specially, with a small decoding table mapping each of the two possible final labels back to the corresponding plaintext bit, revealing only the answer.

Optimizations that made garbling practical

Naive garbled circuits are expensive: every gate needs four ciphertexts, each about a symmetric key long, and every AND or XOR gate needs its own cryptographic hashing. Decades of research have chipped away at this cost. The point-and-permute technique attaches a random permutation bit to each label so the evaluator can identify which of the four ciphertexts to try without leaking anything, avoiding wasted decryption attempts. The free XOR trick, introduced by Kolesnikov and Schneider, chooses labels so that XOR gates require no encryption or communication at all, collapsing their cost to nearly zero since XOR is linear over the label offset. Row reduction and later half-gates techniques by Zahur, Rosulek, and Evans cut AND gates down from four ciphertexts to two, roughly halving communication for the dominant gate type. Combined, these optimizations turned garbled circuits from an academic curiosity into the backbone of real deployed systems for private set intersection, secure auctions, and privacy-preserving machine learning inference, where two parties can run substantial computations while exchanging only a manageable amount of encrypted data.

Security guarantees and limitations

Yao's protocol as described achieves security against semi-honest adversaries, meaning both parties follow the protocol faithfully but try to learn extra information from the messages they see. Under this model the garbler learns nothing beyond what is implied by their own input and the final output, and the evaluator learns nothing beyond the output itself, a guarantee formalized through simulation-based proofs that show a simulator with no private inputs can produce a transcript indistinguishable from the real one. Extending this to malicious security, where a corrupted party can deviate arbitrarily, requires additional machinery such as cut-and-choose garbling of many redundant circuits, zero-knowledge proofs, or authenticated garbling, all of which add overhead but close the gap between theoretical and practical adversaries. It is also worth noting what garbled circuits do not hide: the size and topology of the circuit itself is typically public, so the function being computed must be fixed and known in advance, and any information that can be inferred purely from the output, such as who has the larger salary in the millionaires' problem, is an intentional and unavoidable leak inherent to the function rather than a flaw in the protocol.

Frequently asked questions

Try it live

Everything above runs in your browser — open Garbled Circuits: Yao's Secure Two-Party Computation and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.