Garbled Circuits

A Garbled Circuit is constructed by one party, the garbler, who transforms a Boolean circuit representing the desired function into an encrypted version. Each logic gate's truth table is replaced with encrypted versions of its output labels, a process known as garbling. The garbler then sends this encrypted circuit and the labels corresponding to its own private input to the second party, the evaluator. The evaluator uses a cryptographic protocol called oblivious transfer to obtain only the labels for its own private input, without the garbler learning which specific input values were selected.

The evaluator then proceeds to evaluate the encrypted gate-by-gate, using the garbled truth tables and the input labels. Crucially, at each step, the evaluator can decrypt only one output label per gate, learning nothing about the underlying logic or the other possible outputs. This process continues until the final output labels are produced. The garbler then provides a mapping to translate these final labels back into the plaintext result of the computation, which is shared with both parties. The core security guarantee is that the evaluator learns nothing beyond the final output and what is inherently revealed by it.

Garbled Circuits are a cornerstone of secure multi-party computation (MPC) and are particularly efficient for functions with low circuit depth. Key optimizations like the Free XOR technique and half-gates have dramatically improved their performance, making them practical for real-world applications. Common use cases include privacy-preserving data analytics, secure auctions, genomic testing, and blockchain-based applications like private smart contracts and zk-SNARKs, where they are used within cryptographic primitives to prove correct execution without revealing underlying data.

A Garbled Circuit is a cryptographic protocol that allows two mistrusting parties, often called Alice and Bob, to compute any function f(x, y) where x is Alice's private input and y is Bob's private input. The core innovation is that the function's logic (e.g., an AND or XOR gate) is "garbled" or encrypted by one party, allowing the other to evaluate it on encrypted inputs without learning the underlying truth table or the other party's data. This process ensures that nothing is revealed beyond the final output of the computation, fulfilling the promise of privacy-preserving computation.

The protocol operates in a series of defined steps. First, one party (the garbler) compiles the function f into a Boolean circuit. They then "garble" this circuit by encrypting the truth table of each logic gate: for every possible input wire combination, the corresponding output wire label is doubly encrypted using a symmetric cipher like AES. The garbler sends this encrypted circuit to the other party (the evaluator), along with the garbled labels corresponding to their own private input. The evaluator then obtains the labels for their own input via a 1-out-of-2 Oblivious Transfer protocol, which delivers the correct label without the garbler learning which one was chosen.

With all input labels in hand, the evaluator can now decrypt, gate-by-gate, a single entry in each garbled truth table to propagate the correct output labels through the entire circuit. This process reveals no intermediate values, only the final garbled output labels. The garbler then provides a mapping to translate these final labels back into plaintext results, which are shared with both parties. The security relies on the assumption that the encryption scheme is secure and that the evaluator cannot decrypt more than one row per garbled gate, ensuring semantic security for all non-output values.

While powerful, classical Garbled Circuits have practical limitations, including significant communication overhead for large circuits and being restricted to two-party settings. Modern optimizations like the Free XOR technique, which allows XOR gates to be processed without cryptographic cost, and half-gates for AND gates, have drastically improved performance. Furthermore, frameworks like Yao's Protocol (the two-party case) and its extensions to multi-party computation (MPC) have cemented GCs as a vital tool for building privacy-enhancing applications such as private set intersection, secure auctions, and privacy-preserving machine learning.

The concept of garbled circuits was first introduced in 1986 by computer scientists Andrew Yao in his seminal paper "How to Generate and Exchange Secrets." Yao's pioneering work established the framework for secure two-party computation (2PC), where two distrustful parties can jointly compute a function on their private inputs without revealing those inputs to each other. The term "garbled" refers to the process of encrypting and permuting the values associated with each logic gate's truth table, rendering the circuit's internal workings unintelligible to the evaluator.

For nearly two decades, garbled circuits remained a theoretical construct, considered elegant but too computationally intensive for practical use. This changed in the 2000s with significant optimizations, most notably the point-and-permute technique and free XOR gates introduced by Vladimir Kolesnikov and Thomas Schneider. These breakthroughs drastically reduced the communication and computational overhead, transforming garbled circuits from a cryptographic curiosity into a viable tool for real-world secure multi-party computation (MPC) protocols.

The historical evolution of garbled circuits is marked by a continuous trade-off between security, efficiency, and functionality. Early schemes provided security against semi-honest (passive) adversaries. Later advancements, like the cut-and-choose technique, extended security to malicious (active) adversaries who may deviate from the protocol. Today, garbled circuits are a cornerstone of modern cryptographic libraries and are actively used in privacy-preserving applications such as private set intersection, genomic analysis, and secure auctions, fulfilling the vision first articulated by Yao decades earlier.