Garbled Circuit

Garbled circuit protocols require only a constant number of communication rounds regardless of circuit depth. The garbler sends the garbled circuit and its input labels in a single message, while the evaluator responds with its output. This makes garbled circuits ideal for high-latency networks where round-trip time dominates performance. Unlike secret-sharing-based protocols that require rounds proportional to circuit depth, garbled circuits collapse all interaction into a fixed, small number of back-and-forth exchanges.

The Free-XOR technique allows XOR gates to be evaluated without any cryptographic operations or ciphertexts. By setting the wire label relationship such that the two labels on a wire differ by a global offset Δ, XOR gates become a simple XOR of the input labels. This eliminates the need to garble XOR gates entirely, making circuits dominated by XOR operations—such as AES evaluation or matrix multiplication—dramatically more efficient. Modern garbling schemes achieve zero communication and zero computation cost for XOR gates.

The half-gate technique reduces the cost of garbling an AND gate to just two ciphertexts, down from four in classical Yao's construction. It decomposes each AND gate into two half-gates: one generated by the garbler and one by the evaluator. This optimization, introduced by Zahur, Rosulek, and Evans, achieves the theoretical lower bound for garbled AND gates under the random oracle model. Combined with Free-XOR, it makes garbled circuits the most communication-efficient approach for many secure computation tasks.

Authenticated garbling extends the standard semi-honest protocol to achieve malicious security by embedding cryptographic checks that prevent the garbler from constructing a circuit that deviates from the agreed function. Techniques include:

• Cut-and-choose: The evaluator requests opening of a random subset of garbled circuits to verify correctness
• Batched cut-and-choose: Amortizes verification across multiple executions
• Authenticated shares: Uses information-theoretic MACs on wire labels to detect cheating These methods ensure that even an actively malicious garbler cannot influence the output beyond choosing its own input.

The point-and-permute optimization prevents the evaluator from learning both labels on a wire, which would break privacy. Each wire's two labels are assigned a random select bit (0 or 1), and the garbled truth table is permuted according to these bits. The evaluator uses the select bit of its input label to locate the correct ciphertext without learning the semantic value. This eliminates the need for trial decryption and reduces evaluation to exactly one decryption per gate, making garbled circuit evaluation deterministic and fast.

Garbled circuits rely on Oblivious Transfer (OT) to deliver the evaluator's input wire labels without revealing the evaluator's input to the garbler. For each input bit, the evaluator retrieves exactly one of two labels via OT—learning the label corresponding to its input while the garbler remains oblivious to which label was selected. Modern protocols use OT extension to efficiently generate millions of OTs from a small number of base OTs using only symmetric-key operations, making the input phase negligible compared to circuit garbling and evaluation.

A standard optimization technique that prevents the evaluator from needing to decrypt all four rows of a garbled truth table to find the correct one. A select bit (or pointer bit) is appended to each wire label, and the garbled table rows are permuted based on these bits. The evaluator uses the select bits of their input keys to directly index the correct row, reducing evaluation cost from 4 decryptions per gate to 1 decryption per gate. This eliminates the trial-and-error decryption process while maintaining security.

A pivotal optimization that makes evaluation of XOR gates computationally free—requiring no garbled table entries and no cryptographic operations. It works by setting a global offset R such that the two wire labels on any wire differ by R. For an XOR gate, the output label is simply the XOR of the input labels, eliminating the need for any encrypted table. Since XOR gates are ubiquitous in Boolean circuits, this dramatically reduces both communication and computation costs in practical garbled circuit protocols.

A state-of-the-art optimization that reduces garbled AND gates to just two ciphertexts per gate (down from four in classical Yao). It decomposes each AND gate into two "half-gates"—one where the garbler knows one input and one where the evaluator knows one input—using the Free-XOR technique. Combined with Free-XOR, this yields the most efficient known garbling scheme, requiring only 2κ bits of communication per AND gate, where κ is the computational security parameter.

A technique for upgrading garbled circuit protocols from semi-honest security to malicious security. The garbler constructs multiple independent copies of the circuit, and the evaluator randomly selects a fraction to be "opened" and verified for correctness. If the opened circuits are correctly constructed, the remaining unopened circuits are evaluated with majority voting on the output. This statistical enforcement ensures a cheating garbler is caught with high probability, at the cost of increased computation and communication proportional to the replication factor.

A modern approach to achieving malicious security without the high replication overhead of cut-and-choose. The garbler commits to the entire garbled circuit, and during evaluation, the evaluator can verify correctness using Message Authentication Codes (MACs) embedded in the wire labels. Any deviation from the protocol specification causes a MAC verification failure, allowing immediate abort. This approach achieves malicious security with only a small constant factor overhead over semi-honest protocols, making it the preferred method in modern implementations.