Garbled Circuits

The function to be computed jointly must first be represented as a Boolean circuit—a directed acyclic graph of logic gates (AND, XOR, NOT). This is the fundamental abstraction that distinguishes garbled circuits from arithmetic-based MPC protocols. The circuit is agreed upon by both parties before the protocol begins and is public knowledge. The size of the circuit directly impacts performance: each AND gate requires cryptographic operations, making circuit optimization a critical engineering concern.

The garbler constructs the encrypted circuit by assigning two random cryptographic labels (representing 0 and 1) to every wire in the circuit. For each gate, the garbler encrypts the output label using the two input labels as keys, creating a garbled truth table. The resulting encrypted gate entries are randomly permuted so the evaluator cannot determine which row corresponds to which input combination. This process ensures the evaluator can compute the gate's output only if they possess exactly one label per input wire.

The evaluator must obtain the wire labels corresponding to their private input bits without revealing those bits to the garbler. This is achieved through Oblivious Transfer (OT). For each input bit, the garbler offers two labels; the evaluator selects one via OT. The garbler remains oblivious to the choice. This primitive is the only step requiring public-key cryptography in the online phase, and its efficiency is dramatically improved by OT extension protocols that amplify a few base OTs into many using only symmetric-key operations.

Introduced by Kolesnikov and Schneider, the Free-XOR technique eliminates all cryptographic operations and ciphertext transmission for XOR gates. The garbler chooses a global random offset R and generates wire labels such that the label for 0 and the label for 1 on any wire differ by exactly R. An XOR gate's output label is simply the XOR of its two input labels, requiring no encryption or decryption. Since XOR gates often constitute the majority of a circuit, this optimization yields a substantial reduction in computation and bandwidth.

The Half-Gates technique, introduced by Zahur, Rosulek, and Evans, reduces the cost of each AND gate to just two ciphertexts (down from four in classical Yao). It decomposes an AND gate into two 'half-gates' where one party knows one input. This is the current state-of-the-art for garbled circuit AND gates and, when combined with Free-XOR, makes the protocol remarkably efficient. The construction is proven secure in the random oracle model and is the standard in modern implementations.

To enable the evaluator to correctly decrypt the garbled truth table without knowing the semantic values of the labels, the point-and-permute technique appends a single random select bit to each wire label. The garbled table is sorted by these select bits, allowing the evaluator to identify the correct row to decrypt using only the select bits of their input labels. This eliminates the need to trial-decrypt all entries, reducing evaluation cost to a single decryption per gate.