Garbled circuit

Originally a technique for achieving semi-honest-secure 2PC, garbled circuits are now recognized as a useful primitive in their own right (see BHR12). Yao's foundational paper Y86 is credited with introducing the technique. Roughly, the idea is to associate two bitstrings called wire labels to each wire in a boolean circuit. These wire labels abstractly represent true and false for that wire. Then a garbled circuit contains for each gate an encrypted truth table. For each of the four possible inputs to the gate, we encrypt an output wire label using the corresponding input wires as keys. Intuitively, an evaluator will only know one wire label on each of the input wires, and hence only be able to open one ciphertext and learn one wire label on the output wire.