garbler

A garbler is a party in cryptographic secure two-party computation who constructs a garbled circuit for later evaluation. In Yao's garbled circuits, two parties—one acting as the garbler and the other as the evaluator—compute a function on private inputs while revealing nothing beyond the output. The garbler’s role is to encode the circuit into a form that can be evaluated without exposing the inputs.

To garble a circuit, the garbler assigns a pair of cryptographic keys (labels) to every wire in the circuit, one label representing the value 0 and the other representing 1. A permutation bit may be attached to each wire to hide which input corresponds to which row in the garbled tables. For each gate, the garbler creates a garbled table consisting of ciphertext entries that correspond to the gate’s truth table. Each entry is encrypted with the input wire labels as keys such that, when the evaluator holds the correct input labels, decrypting one row yields the output wire label. The garbler may apply optimizations to reduce size and improve efficiency, such as Free-XOR, garbled row reduction, or point-and-permutation techniques.

During evaluation, the evaluator holds the appropriate input wire labels for their inputs and uses them to decrypt exactly one row per gate, thereby obtaining the output wire labels step by step. The final output labels are translated by the garbler into the actual function result, if needed. The process ensures that neither party learns the other’s private inputs: the garbler learns nothing about the evaluator’s inputs beyond what can be inferred from the output, and the evaluator learns only the output of the function. The concept dates to Yăo’s garbled circuits, introduced in the 1980s, and remains a foundational technique in secure function evaluation.