Garbled Circuits

The fundamental mechanism of a garbled circuit involves treating a boolean function as a logical circuit and encrypting it gate by gate. The garbler assigns two random cryptographic labels to each wire in the circuit, representing the values 0 and 1. For each logic gate, the garbler encrypts the output label using the corresponding input labels as keys. The evaluator can only decrypt the single output label that corresponds to their specific inputs, learning nothing about the alternative path.

To initiate the protocol without revealing the evaluator's private input, garbled circuits rely on Oblivious Transfer (OT). The evaluator needs the wire labels corresponding to their input bits, but cannot ask the garbler directly without exposing those bits. OT allows the evaluator to select and receive the correct labels for their input from the garbler, while the garbler remains oblivious to which labels were chosen. This ensures the evaluator's input privacy from the very first step.

A standard garbled circuit is inherently single-use. The cryptographic keys (wire labels) are generated for a specific execution. If the same garbled circuit were evaluated twice with different inputs, the evaluator could use the labels learned from the first execution to decrypt additional gates in the second, violating the garbler's input privacy. This property necessitates generating a fresh circuit for every computation, which is a primary driver of the protocol's computational overhead.

A significant advantage of the garbled circuit protocol is its constant number of communication rounds. The interaction between the garbler and evaluator is minimal: the garbler sends the garbled circuit and their input labels, the evaluator performs the OT for their input labels, and finally, the evaluator computes the result. This fixed, low-latency interaction pattern is independent of the circuit's depth, making it highly suitable for high-latency networks where minimizing back-and-forth is critical.

A critical optimization to reduce evaluation cost is the point-and-permute technique. Without it, the evaluator would need to attempt decrypting a gate's ciphertext with multiple key combinations to find the correct one. Point-and-permute appends a random 'pointer' bit to each wire label. The garbler orders the gate's ciphertexts based on these pointer bits, allowing the evaluator to immediately identify which single ciphertext to decrypt using the pointer bits of the input labels they hold, reducing evaluation to one decryption per gate.

The classic Yao's garbled circuit protocol is proven secure in the semi-honest (or honest-but-curious) security model. This assumes both parties follow the protocol exactly but may try to learn additional information from the messages they receive. It guarantees that the evaluator learns only the final output and their own input, while the garbler learns nothing about the evaluator's input. Extensions using cut-and-choose techniques or zero-knowledge proofs are required to achieve security against malicious adversaries who may deviate from the protocol.

A fundamental cryptographic protocol that serves as the input-handling mechanism for garbled circuits. In an OT, a sender transmits multiple messages, but the receiver only learns one, while the sender remains oblivious to which was selected.

• 1-out-of-2 OT: The most common variant where the receiver chooses one of two messages.
• Role in Garbled Circuits: The circuit evaluator uses OT to privately retrieve the garbled keys corresponding to their private input bits from the circuit generator.
• OT Extension: A performance optimization that uses a small number of computationally expensive 'base' OTs to generate a vast number of efficient OTs using only symmetric-key operations.

A standard optimization technique that eliminates the need for the evaluator to attempt decrypting all four rows of a garbled gate to find the correct output.

• Mechanism: A random permutation bit is appended to each wire label. The garbled table rows are sorted based on these external bits.
• Efficiency Gain: The evaluator simply uses the permutation bits of the two input labels to index directly into the correct row of the garbled table, reducing evaluation cost by a factor of four.
• Security: The permutation bit is independent of the actual truth value, revealing no semantic information about the underlying computation.

A groundbreaking optimization that allows XOR gates to be evaluated without any cryptographic operations and without transmitting any ciphertext.

• Method: The circuit generator chooses a global random offset R. For every wire, the 0-label and 1-label differ by this same offset. The XOR of two labels naturally produces a valid output label.
• Impact: Since XOR gates are ubiquitous in boolean circuits, this technique drastically reduces communication and computation overhead, making garbled circuits practical for complex functions.

A state-of-the-art optimization that reduces the cost of garbling an AND gate to just two ciphertexts, down from the original four.

• Technique: An AND gate is decomposed into two 'half-gates'—one generated by each party. The first half-gate uses a technique similar to Free-XOR, while the second leverages the evaluator's knowledge of one input label.
• Result: Combined with Free-XOR, the total cost of a garbled circuit is reduced to 2 ciphertexts per AND gate, making it the most efficient known garbling scheme for boolean circuits.

A security mechanism that defends against a malicious circuit generator who might construct an incorrect or corrupt circuit to leak private information.

• Protocol: The generator creates multiple independent garbled copies of the circuit. The evaluator randomly selects a fraction to be 'opened' and verified for correctness.
• Assurance: If all opened circuits are correct, the remaining unopened circuits are evaluated with majority voting. The probability of undetected cheating decreases exponentially with the number of circuits.
• Modern Variants: Optimizations like LEGO and TinyLEGO use soldering techniques to reduce the replication overhead.

A modern paradigm shift that moves from the cut-and-choose model to a more efficient single-circuit execution with malicious security.

• Mechanism: The generator commits to the correct garbling of each gate using cryptographic authentication. During evaluation, the evaluator verifies these commitments without revealing their input.
• Key Protocols: Systems like WRK (Wang, Ranellucci, Katz) and Authenticated Garbling (Hazay et al.) achieve malicious security with only a constant factor overhead over semi-honest protocols.
• Advantage: Eliminates the statistical security parameter and the high replication cost of cut-and-choose.