Fact-checked by Grok 2 weeks ago

Garbled circuit

A garbled circuit is a that enables two untrusted parties to jointly evaluate a on their private inputs, revealing only the output while keeping the inputs and intermediate computations hidden from each other. Introduced by Andrew Chi-Chih Yao in 1986 as part of his foundational work on secure computation, the technique models the target as a and "garbles" it by encrypting the truth tables of its gates, allowing secure evaluation through the exchange of garbled inputs and the circuit itself. This approach, often combined with protocols, provides a generic method for secure two-party computation (2PC) under the semi-honest adversary model, where parties follow the protocol but may attempt to infer information from received messages. The protocol originates from Yao's solution to the "millionaires' problem," where two parties compare their wealth without disclosing the exact amounts, demonstrating the feasibility of general-purpose secure function evaluation (SFE). Although Yao presented the idea in an oral talk at FOCS 1986, a formal description first appeared in a 1987 paper by , Silvio Micali, and Avi Wigderson, who integrated it into broader frameworks for secure computation. Over time, garbled circuits have evolved from a theoretical construct to a practical tool, with modern implementations supporting applications like privacy-preserving auctions, secure inference, and outsourced computation in cloud environments. In operation, one party (the garbler) constructs the garbled circuit by assigning random keys to each wire representing input bits (0 or 1) and encrypting the gate outputs such that only the semantically correct key propagates through the circuit. The evaluator receives the garbled circuit and uses to obtain garbled versions of their input keys without learning the garbler's keys, then evaluates the circuit by decrypting gates in to compute the garbled output, which is finally decoded to reveal the function result. Security relies on the indistinguishability of garbled encodings and the hiding properties of , ensuring that no additional information leaks beyond the output. Key advancements have addressed initial efficiency concerns, such as high communication and computation costs, through optimizations like row reduction (halving gate sizes for AND gates), free XOR gates (evaluating XORs without encryption), and the use of pseudorandom functions or block ciphers like for faster garbling. These improvements enable practical performance, with recent schemes achieving sublinear evaluator costs for certain functions and extensions to malicious security via zero-knowledge proofs or cut-and-choose techniques. Garbled circuits remain a cornerstone of 2PC, influencing hybrid protocols that combine them with for multi-party settings.

Historical Development

Origins in Secure Computation

The concept of secure two-party computation emerged prominently in 1982 through Andrew Yao's formulation of the "Millionaires' Problem," a foundational scenario illustrating the need for parties to jointly evaluate a function—such as comparing their wealth—without revealing private inputs or relying on a trusted third party. In this problem, two millionaires seek to determine who is richer while keeping their exact fortunes secret, serving as a canonical example that motivated the development of protocols ensuring privacy and correctness in distributed computing environments. Yao's work highlighted the theoretical possibility of such computations under idealized assumptions, laying the groundwork for broader secure computation paradigms. Building on this motivation, introduced the garbled circuit technique in as a practical method to solve the Millionaires' Problem and enable secure of arbitrary represented as . This approach involved "garbling" the —encrypting its in a way that allows the evaluator to compute the output without learning the underlying structure or the other party's inputs—marking the first explicit description of circuit garbling for privacy-preserving . Presented orally at the 27th Annual Symposium on Foundations of (FOCS ), Yao's demonstrated how garbled could achieve secure two-party by leveraging to simulate trusted execution. A formal description first appeared in the 1987 paper by , Silvio Micali, and Avi Wigderson. This innovation occurred amid the Cold War-era cryptographic research climate of the 1980s, a period of heightened geopolitical tensions that spurred advancements in and computation to counter espionage and threats. Concurrently, the field shifted from —relying on perfect secrecy against unbounded adversaries, as in earlier secret-sharing schemes—to computational security assumptions, which assume adversaries are limited by polynomial-time computation and base security on problems like factoring. Yao's garbled circuits exemplified this transition, enabling efficient protocols under realistic computational hardness assumptions rather than requiring unlimited resources for unconditional security.

Key Milestones and Contributors

The concept of garbled circuits was introduced by Andrew Chi-Chih Yao in 1986 as a method for secure two-party computation, building on earlier work in cryptographic protocols to enable the evaluation of a over inputs without revealing them. In the late 1980s and 1990s, researchers extended this foundation to address both semi-honest and malicious adversaries; notably, Donald Beaver, Silvio Micali, and Phillip Rogaway formalized multi-party extensions of garbled circuits in their 1990 analysis of secure protocol round complexity, allowing for fault-tolerant computations among multiple parties. Concurrently, , Silvio Micali, and Avi Wigderson developed the GMW paradigm in 1987, an interactive protocol for using oblivious transfers on boolean circuits, which provided an alternative to Yao's garbled circuits by emphasizing arithmetic sharing and higher interactivity but enabling security against dishonest majorities. During the 2000s, efficiency improvements focused on reducing computational and communication overheads in garbled circuit protocols. Vladimir Kolesnikov and Thomas Schneider proposed in a construction that evaluates XOR gates "for free" without additional encryption, significantly lowering the cost for circuits with many linear operations and integrating with extensions to minimize base calls. Building on this, Benny Pinkas, Thomas Schneider, Nigel P. Smart, and Stephen C. Williams demonstrated in 2009 that optimized garbled circuits could support practical implementations, introducing techniques like row reduction to shrink garbled tables from four to three ciphertexts per gate, enabling secure evaluation of functions like with feasible runtime on commodity hardware. Key contributors to garbled circuits include as the inventor of the core technique, Goldreich, Micali, and Wigderson for establishing the comparative GMW paradigm that highlighted trade-offs in round efficiency and adversary models, and early implementers Abhi Shelat and Chih-Hao Shen, who in 2011 provided real-world benchmarks evaluating non-trivial circuits such as 128-bit encryption in under a second using optimized garbling and . A pivotal milestone occurred in 2011 with Shelat and Shen's work, marking the first practical demonstration of garbled circuits for complex, real-world computations and proving their viability beyond theoretical constructs.

Theoretical Foundations

Basics of Secure Two-Party Computation

Secure two-party computation (2PC) enables two parties, , to jointly compute the output of an arbitrary f(x, y), where x is Alice's private input and y is Bob's private input, such that each party learns only the output while keeping their inputs secret from the other party and from any eavesdropper. This framework ensures privacy and correctness even if the parties do not trust each other, making it a cornerstone of cryptographic protocols for tasks like secure auctions, private database queries, and collaborative . Security in 2PC is analyzed under two primary adversary models: semi-honest (or honest-but-curious) adversaries, who adhere to the protocol but attempt to extract additional information from received messages, and malicious adversaries, who may arbitrarily deviate from the protocol to compromise privacy or correctness. The standard security definition employs the ideal/real-world simulation paradigm, where a protocol is secure if any attacker's view in the real execution can be indistinguishable from a simulation in an ideal world where a trusted functionality computes f(x, y) directly and delivers outputs privately. This paradigm, formalized in the 1980s and refined in subsequent works, guarantees that semi-honest security preserves input privacy and output correctness, while malicious security additionally ensures robustness against protocol deviations, often at higher computational cost. Garbled circuits serve as a foundational circuit-based method for realizing 2PC, offering an alternative to the secret-sharing approach in the GMW protocol, which distributes shares of and intermediate values modulo a prime to evaluate the function. In contrast to GMW's reliance on additive or multiplicative for circuits, garbled circuits operate directly on representations, encoding computations as randomized permutations of truth tables to hide during evaluation. This model aligns with hardware-efficient implementations but requires as a subprotocol for secure input provision. A key prerequisite for circuit-based 2PC, including garbled circuits, is the representation of the target function as a , a composed of input wires, output wires, and gates implementing basic operations such as AND, OR, and XOR. Each gate processes two input bits to produce one output bit according to its , allowing any to be expressed as a composition of these primitive operations, provided the circuit size is in the input length. This model ensures universality, as any can be simulated by a family of circuits, facilitating the general applicability of 2PC protocols.

Oblivious Transfer Protocol

() serves as a cornerstone in secure two-party , enabling one party to selectively receive without compromising . In the specific case of 1-out-of-2 , the sender provides two distinct input values, while the receiver specifies a choice bit to obtain exactly one of those values; the sender remains oblivious to the receiver's selection, and the receiver gains no about the unselected value. This protocol ensures both sender security—where the receiver cannot distinguish between the two possible inputs for the chosen index—and receiver security—where the sender learns nothing about the choice bit. The concept originated with Michael O. Rabin's 1981 proposal for a basic form of oblivious transfer, framed as a probabilistic mechanism for secret exchange where the sender has no knowledge of whether the receiver successfully obtained the transferred information, with success probability 1/2 per transfer. This information-theoretic precursor laid the groundwork but required enhancements for practical use. In 1985, Shimon Even, Oded Goldreich, and Abraham Lempel formalized the 1-out-of-2 variant as a computational protocol, assuming the hardness of factoring (via the RSA assumption), which transformed Rabin's idea into an efficient building block for cryptographic applications like contract signing. Within garbled circuits, facilitates secure input sharing by allowing the evaluator to acquire the appropriate wire labels for their private inputs without disclosing the input bits to the garbler or revealing the labels for alternative bit values. This integration supports the privacy goals of secure two-party computation by preventing leakage during the protocol's input phase. The security of such OT protocols is captured by computational indistinguishability under , where an adversary's advantage in distinguishing real from ideal executions is negligible: \left| \Pr\left[ \mathcal{A}(\view^{\real}) = 1 \right] - \Pr\left[ \mathcal{A}(\view^{\ideal}) = 1 \right] \right| \leq \negl(\lambda) Here, \view^{\real} and \view^{\ideal} denote the adversary's view in the real and ideal OT executions, respectively, and \lambda is the security parameter. To address the inefficiency of base OT protocols, which rely on costly public-key cryptography, extension techniques have been developed to amplify a minimal set of base OTs into many correlated instances. The seminal IKNP protocol, introduced by Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank in 2003, leverages pseudorandom functions and random oracles to extend k base OTs into m \gg k OTs with symmetric-key efficiency, reducing overall computational overhead by orders of magnitude in large-scale secure computations. This approach has become widely adopted, enabling practical deployments of garbled circuits in real-world applications.

Definitions and Notations

In the context of garbled circuits, a C is formally defined as a (DAG) that computes a f: \{0,1\}^n \times \{0,1\}^m \to \{0,1\}^l, consisting of input wires carrying the inputs x \in \{0,1\}^n from one party and y \in \{0,1\}^m from the other, a set of (primarily AND, OR, and XOR with fan-in 2), and output wires producing the result. The evaluation is denoted C(x, y), yielding the output bits corresponding to f(x, y). This representation allows arbitrary functions to be expressed as circuits of size for problems in NC^1 or similar classes, with the number of gates q bounded by a in the input size. Each wire w in the is assigned two distinct random labels, denoted e_w^0 and e_w^1, which are typically \kappa-bit keys (e.g., 128 bits for parameter \kappa = 128) encoding the possible bit values 0 and 1 on that wire, respectively. These labels serve as secret encodings that obscure the actual bit values during computation, ensuring that only the semantically correct label propagates through the . The assignment of semantics (which label corresponds to 0 or 1) is randomized per wire to enhance . For a garbled AND gate with input wires a and b, and output wire c, the garbled table comprises four encrypted entries, one for each input combination: \begin{align*} \{e_a^0, e_b^0\} &\to e_c^0, \\ \{e_a^0, e_b^1\} &\to e_c^0, \\ \{e_a^1, e_b^0\} &\to e_c^0, \\ \{e_a^1, e_b^1\} &\to e_c^1, \end{align*} where each entry is an of the output label using a key derived from the input labels, such that only the matching input pair decrypts correctly to reveal the output label. The table entries are permuted randomly before transmission to prevent deduction of input relationships. Similar tables are constructed for other types, with XOR gates often optimized to avoid full . The security parameter \lambda (often denoted \kappa) specifies the bit length of cryptographic primitives, ensuring negligible probability of distinguishing the garbled circuit from random strings under computational bounded adversaries. Garbling relies on a pseudorandom (PRF) family, denoted \text{PRF}_k(m), where k is a secret key of length \lambda and m is an input message (e.g., a gate index or wire identifier), producing pseudorandom outputs used to generate labels and encrypt table entries. This PRF instantiation enables efficient, secure label generation without revealing circuit structure.

Core Protocol Mechanics

Circuit Preparation and Representation

In the garbled circuit protocol, the initial preparation involves representing the target function f as a consisting of gates with 2, such as AND, OR, and NOT, which can universally express any . This conversion ensures the circuit is in a form amenable to the garbling process, where each gate computes a single bit based on its two input bits. A representative example is the for Yao's Millionaires' problem, in which two parties determine which has the greater without disclosing their . The is implemented as a comparison that processes n-bit bit by bit, starting from the most significant bit: for each position i, it checks using XOR and propagates a "greater than" signal through subsequent bits via conditional AND , ultimately outputting 1 if the first party's value exceeds the second's. This results in a with O(n) for an efficient implementation. The is organized in , with gates numbered sequentially from 1 to m such that all input wires to a are outputs of preceding gates, enabling evaluation to proceed without or cycles. The generator, denoted , constructs and fully knows the circuit structure, including its topology and types, while the evaluator, Bob, receives no information about it beyond the garbled form. Constant wires—those fixed to 0 or 1 throughout the computation—are incorporated by pre-assigning dedicated labels, avoiding the need for on these inputs. Circuit size is quantified by the number of G and wires W, with the preparation incurring an initial computational cost of O(G \kappa), where \kappa denotes the security parameter and key length in bits.

Garbling Process

The garbling process in garbled circuits involves the generator () transforming the truth table of each in the Boolean circuit into an encrypted form known as a garbled table, ensuring that only parties with the appropriate input labels can decrypt the correct output label. For each wire, generates two random \kappa-bit labels (tokens) X^0 and X^1, where the superscript denotes the semantic bit value it encodes, and the least significant bit (type bit) is set randomly for non-output wires (or to the semantic value for output wires). These labels serve as keys and carry the semantic information implicitly through the construction. For a binary gate g with input wires A and B, and output wire C, the garbled table P has four entries indexed by the type bits a, b \in \{0,1\} of the input tokens. For each pair (a, b), Alice computes the tweak T = g \| a \| b (where \| denotes and g is the gate index), selects the input tokens X_a^A and X_b^B (whose types are a and b), and encrypts the corresponding output token X_\gamma^C where \gamma = gate function(a, b), using a dual-key cipher: P[g, a, b] = E^T_{X_a^A, X_b^B}(X_\gamma^C) = F_{(X_a^A)'}(T) \oplus F_{(X_b^B)'}(T) \oplus X_\gamma^C, with F a pseudorandom function (PRF) and ( \cdot )' denoting the label without the LSB. The rows are fixed by the type indices, providing a random permutation of the truth table in the type space. The complete garbled circuit (GC) is the ordered collection of all such garbled tables for every gate in topological order, which Alice sends to the evaluator (Bob). In Yao's original construction, the encryption for each row used a symmetric scheme akin to two-key triple-DES, with keys derived from the input wire labels to double-encrypt the output. Modern implementations replace this with fixed-key as the underlying primitive for F, treating as a PRF where the key is fixed and the input is the tweak T, such as E(A, B, T, X) = \pi(\sigma(A, B, T)) \oplus \sigma(A, B, T) \oplus X, with \pi fixed-key and \sigma a simple mixing function like $2A \oplus 4B \oplus T. This approach leverages hardware-accelerated for efficiency while maintaining security.

Input Encoding and Transfer

In garbled circuits, the generator encodes their own input bits directly into the corresponding input wire labels. Each input wire w is assigned two random cryptographic keys or labels, denoted e_w^0 and e_w^1, representing the bit values 0 and 1, respectively. For a generator input bit x_i = b (where b \in \{0,1\}), the generator selects and retains e_w^b as the starting label for that wire. These selected labels for all generator input wires are then transmitted to the evaluator alongside the garbled circuit, enabling the evaluator to begin computation without learning the underlying bit values due to the randomness of the labels. The evaluator's input bits are handled through oblivious transfer (OT) to ensure privacy, as the evaluator must obtain the appropriate labels without revealing their input to the generator. For each of the evaluator's m input bits y_j, the generator prepares the pair (e_{w_j}^0, e_{w_j}^1) for the corresponding input wire w_j. The parties then execute m instances of 1-out-of-2 OT, where the generator acts as the sender inputting the label pair, and the evaluator acts as the receiver inputting their bit y_j to selectively obtain e_{w_j}^{y_j} without disclosing y_j. This process leverages the OT primitive to securely transfer only the necessary labels, preserving the security of the computation. The overall protocol flow for input transfer involves the generator first garbling the circuit and preparing the label pairs, followed by sending the garbled tables and their own input labels to the evaluator. The m OT invocations then occur to provide the evaluator's labels, after which evaluation proceeds. The communication cost for this phase is O(\kappa m), where \kappa is the security parameter determining the label size, dominated by the OT exchanges. Constant inputs, which are predefined bit values known to the parties (e.g., constants or fixed inputs from one party), are encoded by pre-setting the corresponding wire to e_w^b where b is the constant value. This is directly provided to the evaluator without requiring , as no selection is needed, thereby reducing communication and computation overhead for such wires.

Circuit Evaluation

In the circuit evaluation phase of the garbled protocol, the evaluator computes the garbled output by processing the received garbled and their garbled input labels in , without learning any intermediate values beyond what is necessary for the computation. The evaluator begins with garbled input labels () X^{w_i}_{\sigma_i} for each input wire w_i encoding their input bit \sigma_i \in \{0,1\}, where each token is a \kappa-bit . The , specifying the gates, their types (e.g., AND or XOR), and interconnections, is public or provided separately by the garbler, allowing the evaluator to traverse the deterministically. The garbled consists of garbled tables for each non-input gate, each table containing four entries indexed by input token types. For a binary gate g with input wires w_1, w_2 and output wire w_3, the evaluator holds the current input tokens X^{w_1}_{\alpha} and X^{w_2}_{\beta}, where \alpha, \beta \in \{0,1\} are the encoded bits. The evaluator extracts the type bits a = \mathrm{lsb}(X^{w_1}_{\alpha}) and b = \mathrm{lsb}(X^{w_2}_{\beta}), forms the tweak T = g \| a \| b, and retrieves the entry P[g, a, b] from the garbled table. The output token is then computed as X^{w_3}_{\gamma} = D^T_{X^{w_1}_{\alpha}, X^{w_2}_{\beta}} (P[g, a, b]) = P[g, a, b] \oplus F_{(X^{w_1}_{\alpha})'}(T) \oplus F_{(X^{w_2}_{\beta})'}(T), where \gamma = gate function(\alpha, \beta). This decryption yields the correct output token corresponding to the semantic input bits, as the table indexing and encryption ensure alignment with the gate's truth table. The evaluator selects this unique result and propagates it as the input token for subsequent gates connected to w_3. For an AND gate, \gamma = \alpha \land \beta, so the output token encodes 1 only if both inputs encode 1. For an XOR gate in the basic construction, the table is garbled similarly, though optimizations exist to handle XORs more efficiently. This gate-by-gate evaluation continues until the tokens on the output wires are computed, producing the garbled output. The process is deterministic once the input tokens and garbled circuit are obtained. The time complexity of evaluation is O(G \kappa), where G is the total number of gates, arising from performing symmetric operations (PRF evaluations) per gate, each requiring O(\kappa) time in standard cryptographic models using pseudorandom functions (PRFs) for the dual-key cipher. This efficiency makes garbled circuits practical for circuits of moderate size, with the evaluator gaining no knowledge of the underlying computation or the garbler's inputs beyond the output and the public topology.

Output Decoding and Revelation

In Yao's garbled circuits protocol under the semi-honest model, the evaluator completes circuit evaluation by obtaining the garbled output tokens for the output wires, which are the random keys X^0_w or X^1_w corresponding to the computed bit values on those wires. These tokens are then transmitted to the generator, who maintains the decoding information d—a mapping that associates each output token with its plaintext bit (0 or 1), as the generator generated both possible encodings for output wires during garbling (with LSBs set to the semantic values). The generator applies the decoding algorithm \mathrm{De}(d, Y) to these tokens, where Y denotes the garbled output, yielding the plaintext output y = f(x, y') that is revealed to both parties. The security of this revelation step relies on the properties of the garbling scheme: the evaluator cannot interpret the output tokens without the decoding information, ensuring that only the final output y is disclosed, while inputs and all intermediate wire tokens remain private due to the semantic security of the underlying encryption and the oblivious transfer used for inputs. This design prevents leakage beyond the agreed-upon function evaluation, as the garbled circuit and any transferred tokens reveal nothing about private data except through the explicit decoding of outputs.

Optimization Techniques

Point-and-Permute Method

In the standard garbling process for an , the garbler constructs a garbled table consisting of four rows, each corresponding to one of the possible input label pairs, with each row containing an encryption of the corresponding output ; this results in 4 rows of κ bits each, totaling 4κ bits per gate, where κ denotes the security parameter. The point-and-permute method optimizes the evaluation of the garbled table by allowing the evaluator to directly compute the position of the correct row using a pseudorandom (PRF), avoiding trial decryption of all rows. Introduced by , Micali, and Rogaway in , this technique assigns a selection bit (or color) to each wire and orders the rows based on the selection bits of the input labels, enabling the evaluator to select and decrypt only one row per gate, reducing computational overhead from four to one decryption. When combined with garbled row reduction, the communication cost can be further lowered to 3κ bits per gate while maintaining the single-decryption evaluation. The garbler precomputes a for the rows and uses the PRF with one input as key on the other to derive the position. The output is recovered via the equation: \text{Output label} = \text{PRF}_{\text{input1}}(\text{input2}) \oplus \text{permuted output} where the permuted output is the at the indicated position. This ensures correctness and through permutation and PRF properties. This approach incurs minor additional computational cost for the garbler but significantly reduces evaluator computation and, with row reduction, communication bandwidth, making it essential for practical implementations.

Row Reduction

Row reduction techniques in garbled circuits aim to minimize the size of garbled tables by eliminating redundant encryptions, thereby reducing communication overhead while preserving security. Introduced by Naor, Pinkas, and Sumner in , one key approach involves reusing the output labels of a directly as the input labels for downstream gates, which decreases the total number of unique labels required across the circuit. This chaining ensures that the κ-bit labels generated for an output wire serve as the authenticators for subsequent input wires without generating new random values, limiting the label space to two per circuit wire overall. In circuits with , where a single output wire connects to multiple input wires of downstream gates, this label reuse becomes particularly efficient. A single pair of output labels from the source gate can authenticate inputs across all fan-out destinations, avoiding duplication. For AND gates, which typically require four encryptions in the basic garbling scheme, this shared labeling combined with row reduction lowers the cost to 3κ bits per gate, as one row can be deterministically derived, enabling consistent decryption across connected tables without additional overhead. These row reduction methods yield significant size savings, achieving up to 30% reduction in the overall garbled circuit size for large-scale circuits with extensive interconnections and , making them essential for practical secure deployments.

Free XOR Gates

In the free XOR gates optimization, XOR gates are garbled and evaluated without incurring additional communication or costs beyond the wire labels themselves. Introduced by Kolesnikov and Schneider in , this leverages a global random offset R to relate the two labels on each wire: the label for bit value 1 is the label for bit value 0 XORed with R. For an XOR gate with inputs on wires a and b, the output label for bit b on wire c is then computed directly as e_c^b = e_a^b \oplus e_b^b, where the fixed offset R ensures consistency without requiring pseudorandom function (PRF) evaluations or garbled tables for the gate. This approach is particularly advantageous for chains of XOR operations, as the output labels propagate through the chain at negligible cost after establishing the initial input labels, avoiding the overhead of individual garbling for each . The integrates seamlessly into standard garbled circuit protocols by applying the global R consistently across all wires, while non-XOR gates (such as AND gates) are garbled using conventional methods. Security relies on the model and provides selective privacy for semi-honest adversaries. Circuits dominated by linear operations benefit substantially from free XOR gates; for example, encryption circuits, which contain a high proportion of XOR gates in their linear layers, achieve approximately 50% reductions in overall communication and computation compared to unoptimized garbled circuits. This efficiency stems from eliminating the four ciphertexts typically required per gate in Yao's original construction, replacing them with zero for XORs. To address limitations against adaptive adversaries, where the must garble the before seeing the input, extensions incorporate dual-key mechanisms for XOR labels, ensuring the fixed offset does not reveal correlations under adaptive corruption. These dual-key XOR variants maintain the "free" property while upgrading to adaptive under standard assumptions like the of one-way .

Fixed-Key Block Ciphers

In garbled circuits, fixed-key block ciphers provide an efficient instantiation of the pseudorandom (PRF) required for the , where a single fixed secret key is used across all PRF evaluations rather than generating variable keys for each gate. This approach, originally proposed by Naor, Pinkas, and Sumner for privacy-preserving auctions, leverages block ciphers such as or triple-DES with a fixed key K to mask output labels in the garbled , treating input wire labels as messages to the PRF. The method significantly improves efficiency by avoiding the overhead of key scheduling for each PRF call, allowing multiple evaluations with a single key setup and enabling hardware-accelerated implementations on modern CPUs via instructions like . Bellare et al. formalized and optimized this for , demonstrating that it requires only one AES invocation per nonlinear gate, achieving garbling speeds of approximately 55 cycles per gate and evaluation at 23 cycles per gate in their JustGarble system. This reduces computational costs compared to variable-key PRFs, as the fixed key eliminates per-gate key derivation while maintaining security under the PRF assumption for the . For a given gate, the garbled row corresponding to input labels A and B (representing the encoded bits on the input wires) is computed as: \text{Garbled row} = \text{AES}_K(A \| B) \oplus X where K is the fixed key, \| denotes concatenation (often with a gate tweak prepended), and X is the output label for the corresponding truth table entry. The evaluator decrypts by computing \text{AES}_K(A \| B) and XORing it with each row to recover the matching output label. This fixed-key approach is fully compatible with the point-and-permute optimization, where the least significant bit of each label serves as a selector to order and identify the correct row without additional checks, further minimizing evaluation overhead while preserving privacy.

Half Gates

Half gates represent an optimization technique for garbling s in garbled circuits, reducing the communication cost to 2κ bits per , where κ is the security parameter. Introduced by Zahur, Rosulek, and Evans, this method splits each into two asymmetric "half gates": a left half gate and a right half gate. In the left half gate, the garbler uses the zero encoding of the first input wire as the key for a pseudorandom (PRF), effectively "pointing" to the correct row based on the second input, while the right half gate employs a on the first input's encodings to ensure selective decryption. The garbling process for half gates builds on the point-and-permute method by leveraging fixed select bits and row reduction to minimize ciphertexts. For an AND gate with input encodings e_a^0, e_a^1 for wire A and e_b^0, e_b^1 for wire B, and output encodings e_c^0, e_c^1, the left half gate computes the output for the case where the first input is 0 using: e_c^b = \text{PRF}_{e_a^0}(e_b^b) \oplus \text{offset} for b \in \{0,1\}, where the offset ensures compatibility with the overall circuit garbling. The right half gate then handles the case for the first input being 1 by permuting and encrypting a single ciphertext that the evaluator can decrypt only with the appropriate key. This asymmetry allows the garbler to precompute one half efficiently while the evaluator processes the other during evaluation. In terms of computational cost, half gates require only 2 PRF evaluations per —compared to 4 in standard garbling—achieved through the reduced number of ciphertexts (two per ) and integration with free-XOR for linear gates. Subsequent variants have further optimized this to 1.5κ bits per on average. This approach has become a in modern garbled circuit implementations, including the EMP-toolkit library, which adopts half gates to achieve up to 33% smaller sizes and 25% lower latency in practical secure protocols. These optimization techniques—point-and-permute, row reduction, free XOR gates, fixed-key block ciphers, and half gates—are often combined in modern systems, achieving overall communication costs of approximately 1κ bits per gate for typical arithmetic circuits when using as the PRF.

Extensions and Modern Variants

Multi-Party Garbled Circuits

Multi-party garbled circuits extend the garbled circuit paradigm from two-party secure computation to scenarios involving an arbitrary number n of parties, enabling joint evaluation of a function on private inputs while preserving privacy and correctness against semi-honest or malicious adversaries. In these protocols, the garbling process is distributed across all parties using techniques such as additive over , where each party generates and holds shares of the garbled gate entries rather than a single party constructing the entire . This distribution ensures that no single party learns the full garbled circuit, and reconstruction occurs only during evaluation through simple operations like XOR. Such approaches maintain the constant-round of garbled circuits while scaling to multiple participants, often relying on (OT) extensions for securely sharing multi-party inputs into additive shares before garbling begins. A representative construction is the constant-round protocol by Hazay and Scholl (2017), which combines BMR-style distributed garbling with -based preprocessing to handle multi-input scenarios securely. In this setup, parties first use to secret-share their inputs, then collaboratively garble the such that each garbled requires O(n) ciphertexts shared among the parties. During evaluation, each party locally computes partial decryptions on their shares and combines them via XOR to obtain the output labels, ensuring the computation proceeds without revealing intermediate values. This method achieves security against an honest majority and supports arbitrary , with linear in the circuit size and number of parties. The wire labels in these protocols are themselves secret-shared, with the aggregated global label for a wire w and bit b formed as the XOR of all parties' local shares: e_w^b = \bigoplus_{i=1}^n s_{i,w}^b, where s_{i,w}^b denotes the share held by party i. This additive sharing ensures that individual shares reveal no information about the true label, and the XOR aggregation reconstructs the effective label only when all shares are combined during evaluation. To optimize communication in n-party settings, row reduction techniques have been developed that further share garbled rows across parties, minimizing redundancy in the garbled tables. The work by Cong, Orsini, and Zajonc (CRYPTO 2025) introduces full row reduction for HSS17-style multi-party garbling, reducing the size of each garbled AND gate from $4n to $3n ciphertexts by splitting the multiplicative component of the garbling equation into a shared single ciphertext (for the primary product) and additional masked terms distributed among parties. The evaluator then decrypts the shared ciphertext and XORs the results to cancel offsets and recover the output, achieving up to 6x lower preprocessing communication compared to prior constructions while preserving constant rounds and security. This advancement is particularly impactful for large n, as it scales the per-gate cost more gracefully. Despite these improvements, multi-party garbled circuits encounter scalability challenges, including a O(n^2) increase in invocations for input sharing and garbling in some designs, stemming from the need for pairwise or broadcast-like interactions among parties. Hybrid protocols address this by integrating garbled circuits with secret-sharing-based frameworks like SPDZ, where SPDZ handles linear operations and preprocessing triples efficiently, while garbled circuits manage non-linear gates with fewer rounds. For instance, the construction by Lindell et al. (2015) combines BMR garbling for the nonlinear part with SPDZ for the arithmetic components, reducing overall costs and enabling practical performance for circuits up to millions of gates across dozens of parties.

Garbled Random Access Machines

Garbled Random Access Machines (GRAM) extend the garbled paradigm to efficiently handle computations in the () model, allowing secure evaluation of RAM programs without converting them into expansive circuits. Introduced by Lu and Ostrovsky in 2013, GRAM enables the garbler to produce a garbled version of a RAM program directly, concealing both the program's logic and access patterns from the evaluator. This approach addresses the inefficiency of traditional garbled circuits for data-intensive tasks, where circuit sizes grow quadratically with size due to explicit wiring of all accesses. The core mechanics of GRAM involve garbling three primary components: the CPU, , and (PC). The CPU is garbled using a fixed-size circuit that processes the current state, input queries, and outputs the next state along with memory read/write requests, ensuring constant overhead per step independent of memory size. Memory accesses are hidden through integration with oblivious RAM (ORAM), where each memory location stores encrypted values tagged with pseudorandom keys derived from the access time via a pseudorandom function; this prevents leakage of access patterns as the evaluator follows garbled ORAM emulation circuits. The PC, embedded in the CPU state, is updated non-interactively across program steps using a sequence of garbled circuits, one per execution step, allowing the evaluator to simulate the entire program without revealing . This builds on standard garbled circuit techniques for gate evaluation but adapts them to RAM semantics. GRAM achieves sublinear overhead for memory operations, with a cost of O(\mathrm{polylog} N) per access for programs operating on N words of , resulting in total garbled program size of O(t \cdot \mathrm{polylog} N) for t steps—vastly more efficient than the O(t N) size of equivalent garbled circuits. This efficiency makes GRAM suitable for data-intensive tasks, such as secure database queries or simulations requiring frequent memory interactions, where traditional circuits become impractical due to and evaluation time. Recent advances in 2025 have incorporated stacked garbling into GRAM to better handle conditional branches, reducing communication and computation for programs with divergent execution paths. In the Toss protocol by Ng and Kolesnikov, stacked garbling is integrated with GRAM for efficient conditional evaluation in garbled , achieving O(\sqrt{N} m \sqrt{\kappa}) communication for databases of size N and message length m, with \kappa-bit security, while maintaining polylogarithmic overhead per conditional step. This enables GRAM to scale to complex, branch-heavy RAM programs without proportional cost increases across all paths.

Recent Advances (2023–2025)

In 2023, researchers introduced logic synthesis techniques to optimize garbled circuits at the gate level prior to garbling, enabling more efficient secure computation by minimizing the garbling cost through compact representations of functions. This approach, detailed in a study by Yu et al., employs exact algorithms for small-scale functions and heuristic methods for larger ones, achieving up to 50% reduction in garbled circuit size for benchmarks like and SHA-256 compared to traditional And-Or-Inverter representations. Advancing efficiency in 2025, bitwise garbling schemes were proposed at , establishing a model where AND gates incur a cost of 1.5λ bits under free-XOR assumptions, proving this as optimal for arbitrary garbled AND gates and extending to fan-in 3 gates with a 2λ-bit lower bound when free-XOR is forbidden. This work by Xu et al. refines prior "three-halves" schemes, reducing ciphertext sizes and enabling more compact garbled circuits for practical applications. Concurrently, the Toss protocol emerged for garbled (PIR), leveraging table-only stacking to achieve dramatically reduced —up to 10x lower than prior garbled PIR methods like LogRow—while supporting tables up to 2^20 rows with constant rounds. Developed by Ng and Kolesnikov, Toss builds on stacked garbling to handle conditional accesses efficiently without full circuit evaluation. Also in 2025, publicly auditable were introduced on , incorporating a preprocessing with pre-communication to generate correlations and authenticated masks, allowing a verifier to confirm correctness via constant-round proofs with negligible error. Ling et al.'s combines WRK17 garbling with VOLEitH, achieving malicious and public auditability with overhead linear in size but independent of depth, suitable for verifiability. Extensions to Garbled Random Access Machines (GRAM) integrated stacked garbling for conditionals, enabling communication proportional to the longest execution path rather than the full program tree, as refined in recent constructions like those supporting SIMD tri-state circuits under DDH assumptions. This addresses branching overhead in RAM-model computations, with PicoGRAM achieving O(λ · (W log N + log³ N)) amortized cost per access. These developments fill key gaps in : enhanced GPU for garbled circuit , as in Dash's arithmetic GC framework, yields 5-10x speedups on private inference tasks by offloading garbling to parallel hardware. Additionally, n-party row reduction techniques at CRYPTO 2025 reduce multi-party garbled circuit communication by up to 75% through optimized preprocessing and authentication, extending two-party methods to arbitrary n while preserving free-XOR benefits.

Applications

Privacy-Preserving Machine Learning

Garbled circuits facilitate privacy-preserving machine learning by enabling secure two-party computation of neural network operations, ensuring that neither the input data nor the model parameters are revealed during inference or training. In secure inference, the neural network is compiled into a boolean circuit representing its layers, including linear transformations and nonlinear activations like ReLU, which is then garbled for evaluation. This allows a client to obtain predictions on private data held by a server without data leakage, leveraging the semi-honest security model of garbled circuits. For instance, the TinyGarble framework optimizes circuit compression and scalability, enabling practical garbling of convolutional neural networks (CNNs) such as LeNet-5 for image classification tasks. The practicality of garbled neural networks for was demonstrated in , showing that garbled circuits achieve inference times comparable to schemes while supporting for accuracy. Hybrid protocols often combine garbled circuits for nonlinear operations with or for linear layers, reducing overall communication costs. Examples include secure face recognition, where garbled circuits evaluate comparisons on encrypted biometric data alongside for feature extraction. Similarly, privacy-preserving protocols use garbled circuits to compute decision trees or predictions on patient records without exposing sensitive health information. For training, garbled circuits support secure gradient computation and model updates in two-party settings, often hybridized with to add and bound leakage beyond cryptographic guarantees. The computational cost scales linearly with the network depth and width, approximately O(layers × neurons × κ), where κ is the security parameter, due to the circuit size for activation functions like ReLU dominating the overhead. Such approaches enable distributed training on private datasets, as explored in scalable systems for and neural networks. Recent advances from have extended garbled circuits to architectures, critical for large language models, by optimizing mechanisms through low-round garbling and hybrid encodings, achieving up to 9.5× speedup in private inference latency compared to prior methods. These developments, such as in , focus on approximating softmax and matrix multiplications efficiently within garbled circuits. A key benefit is the elimination of trusted servers, as parties jointly compute without a central , enhancing applicability in federated or cloud-based scenarios.

Secure Auctions and Voting

Garbled circuits provide a foundation for secure auctions by enabling private comparison of bids, building on , where two parties determine which has greater wealth without revealing their values. This secure comparison primitive is extended to multi-party auctions, such as , through multi-round protocols where bids are iteratively compared using garbled circuits to identify the highest bid and compute the winning price without disclosing individual bids. In Vickrey auctions, the garbled evaluates the minimum among the highest bids excluding the winner, ensuring and ; efficiency is achieved with O(n log n) circuit size and communication for n bidders, leveraging optimized building blocks like free XOR gates for comparisons. For malicious , cut-and-choose techniques are employed, where the garbler generates multiple garbled circuits and the evaluator checks a to verify correctness, bounding the security loss to the of the number of circuits while maintaining semi-honest base . Garbled circuits also support secure voting by garbling comparison and summation circuits to tally votes without revealing individual choices, allowing parties to jointly compute election outcomes while preserving voter privacy. For example, in small-scale elections, implementations from 2011 demonstrate practical feasibility for tallying with low communication overhead, suitable for dozens of voters using optimized garbled circuit frameworks. In real-world applications, garbled circuits enhance blockchain privacy for secure bidding, enabling confidential auctions on public ledgers without exposing bid details, as integrated in protocols for decentralized finance.

Private Information Retrieval

Private information retrieval (PIR) protocols enable a client to query a database held by a server without revealing the queried index, while garbled circuits extend this capability into secure two-party computation settings. In garbled PIR (GPIR), the client garbles a query circuit representing the desired lookup and sends it to the server, who evaluates the circuit on the database to retrieve the relevant data item without learning the client's index. This approach leverages garbled circuits to perform the retrieval non-interactively and sublinearly in the database size, allowing the retrieved value to be seamlessly integrated into further circuit evaluation. Compared to traditional PIR schemes, which typically support linear or simple indexed lookups with sublinear communication but limited expressiveness, GPIR enables more complex, non-linear queries by embedding the retrieval logic directly into the garbled circuit. It integrates with () protocols to facilitate oblivious selection of database rows, ensuring the server learns nothing about the client's input while the client obtains the output securely. For instance, in secure search applications over encrypted databases, GPIR allows a client to perform keyword matching or range queries on sensitive data, such as medical records, with of O(κ log N), where κ is the and N is the database size. Recent advances from 2023 to 2025 have optimized GPIR efficiency, notably through the Toss protocol, which employs table-only stacking—a technique that builds lookup tables in a stacked manner to achieve O(log N) computational cost for the evaluator without the overhead of full garbling. Toss enables the client to garble a compact query for an N-row, κ-bit database, yielding over 10x throughput improvements in practical settings, such as 1000 lookups per second on a 100 Mbps channel. Additionally, hybrid constructions combining GPIR with garbled machines (GRAM) support dynamic databases by allowing adaptive updates and queries, reducing by more than 50% for large-scale scenarios like N=2^20 with 8-bit items.

Security Analysis

Security Models and Definitions

Security in garbled circuit protocols for two-party computation (2PC) is analyzed under various adversarial models, distinguishing between semi-honest and malicious adversaries, with stronger notions like universally composable (UC) security providing composability guarantees. These models ensure (adversary learns only its input and output), correctness (output matches the function evaluation), and, in stronger variants, robustness against deviations. In the semi-honest model, adversaries follow the protocol but may attempt to extract additional information from the transcript. Security requires that for any probabilistic polynomial-time adversary \mathcal{A}, there exists a simulator \mathcal{S} such that the adversary's in the real execution is computationally indistinguishable from \mathcal{S}'s simulated , which uses only the adversary's input and the protocol's output. Formally, for parties P_1 with input x and P_2 with input y, and functionality f(x,y) = (f_1(x,y), f_2(x,y)), the distributions \{ (\mathcal{S}_1(x, f_1(x,y)), f_1(x,y)) \}_{x,y} \approx_c \{ (\mathsf{[view](/page/View)}_{\pi_1}(x,y), \mathsf{output}_{\pi_1}(x,y)) \}_{x,y} and similarly for P_2, where \approx_c denotes computational indistinguishability and \mathsf{view} includes the party's local input, output, and messages received. This model applies directly to Yao's basic garbled circuit construction, where the garbler encrypts gates using a secure encryption scheme, and the evaluator decrypts along a path determined by inputs via (OT). The malicious model strengthens against adversaries who may arbitrarily deviate from the to cheat or disrupt execution. Here, full must account for deviations: a simulator \mathcal{S} interacts with an functionality \mathcal{F} (which receives inputs and delivers outputs) such that no \mathcal{Z} can distinguish the real execution from the one with non-negligible probability. This is achieved in garbled circuits via techniques like cut-and-choose, where the garbler generates multiple copies of the circuit, the evaluator verifies a random for correctness using zero-knowledge proofs, and evaluates the remainder, accepting the majority output. The cheating probability is exponentially small in the number of circuits, e.g., approximately $2^{-0.311s} for s circuits. Unlike semi-honest , malicious requires additional mechanisms to enforce input and prevent selective failures. UC security provides the strongest notion, ensuring the protocol remains secure when composed with other protocols, even concurrently or adaptively. In the UC framework, a protocol \pi securely realizes \mathcal{F} if for any real-world adversary \mathcal{A}, there exists an ideal-world simulator \mathcal{S} such that no environment \mathcal{Z} distinguishes \mathsf{EXEC}_{\pi, \mathcal{A}, \mathcal{Z}} (real execution) from \mathsf{IDEAL}_{\mathcal{F}, \mathcal{S}, \mathcal{Z}} (ideal execution with \mathcal{F}). Garbled circuits achieve UC security in a hybrid model assuming secure OT, often in the common reference string (CRS) model, by combining garbling for function evaluation with OT for input privacy and non-interactive zero-knowledge for proofs. The overall indistinguishability is bounded by |\Pr[\mathcal{Z}(\mathsf{EXEC}_{\pi, \mathcal{A}, \mathcal{Z}) = 1] - \Pr[\mathcal{Z}(\mathsf{IDEAL}_{\mathcal{F}, \mathcal{S}, \mathcal{Z}) = 1]| < \mathsf{negl}(\lambda), where \lambda is the security parameter. Garbled circuit security relies on standard computational assumptions, including the hardness of the decisional Diffie-Hellman () problem for OT extensions and pseudorandom functions (PRFs) for efficient gate garbling via symmetric encryption with indistinguishable encryptions. In the hybrid model, the protocol reduces to ideal OT, inheriting its security; PRFs ensure that garbled tables reveal no beyond the evaluation path. These assumptions enable proofs in the or , with security reducing to the underlying primitives' hardness.

Proofs of Security

The security of the standard protocol in the semi-honest model is established via the simulation paradigm, where for every party there exists a probabilistic polynomial-time simulator that, on input the party's input and the output of the functionality, generates a indistinguishable from the party's actual of the protocol execution. This proof, formalized by Lindell and Pinkas, demonstrates that the protocol realizes ideal-model security against static semi-honest adversaries assuming the existence of and a secure private-key scheme. For the garbler (sender), the simulator extracts the sender's input from the functionality output and the receiver's input labels, then generates a simulated garbled circuit by regarbling it using a fresh random tape, while simulating the oblivious transfers as if the receiver's input were known. For the evaluator (receiver), the simulator constructs a "fake" garbled circuit where each gate's four encryptions are replaced by encryptions of a single random key under all four input key combinations, ensuring the evaluator can only obtain the correct output key if starting from valid input keys, and simulates the oblivious transfers using the functionality output. The indistinguishability of these simulated views relies on the pseudorandomness of the function used to generate the gate encryptions, typically a pseudorandom function (PRF), which ensures that real and fake garbled gates are computationally indistinguishable. A key component of the proof for the evaluator's is a simulation-based hybrid argument over the circuit's gates. Let H_i denote the hybrid where the first i gates are fake (simulated) and the remaining |G| - i gates are real, with H_0 being the real execution and H_{|G|} the fully simulated , where |G| is the number of gates. Each consecutive hybrid H_i and H_{i+1} is indistinguishable because replacing a real gate with a fake one changes only four encryptions, whose (from the PRF) hides the underlying keys from a semi-honest evaluator. The overall thus reduces, via hybrid argument, to the of for input and the PRF (or equivalently, CPA-secure symmetric ) for . To achieve against malicious adversaries, Yao's protocol is extended using a cut-and-choose technique, where the garbler generates $2s independent garbled circuits for the same functionality, the evaluator randomly selects s to "open" (reveal all keys and verify correctness against the circuit description), and evaluates the remaining s unopened circuits using on the inputs, outputting the result across them. This ensures with error probability at most $2^{-s}, as a malicious garbler must construct at least s+1 incorrect circuits to bias the output with non-negligible probability, but the random selection makes this event exponentially unlikely. The preservation follows from the semi-honest security of the unopened circuits, combined with the simulation paradigm adapted to the multiple-circuit setting.

Limitations and Known Attacks

Garbled circuits exhibit significant scalability challenges primarily due to their , which grows linearly as O(|C| · κ), where |C| denotes the circuit size in gates and κ is the security parameter, often requiring hundreds of megabytes of transfer for moderately sized . This overhead restricts practical deployments to with roughly 10^6 gates or fewer without advanced optimizations like pipelining, beyond which and become prohibitive for applications. Additionally, phases are susceptible to cache-timing attacks, such as the Goblin attack, which exploits timing variations in memory access patterns during free-XOR and half-gate optimizations to recover the garbler's input with over 90% success rate using on single traces. Known attacks highlight vulnerabilities in both implementation and protocol levels. Side-channel attacks, including single-trace power analysis, target the secret-dependent order of AES encryptions in garbled gates, enabling recovery of wire labels and private inputs across all non-XOR gates with near-100% success on software platforms like 32-bit and up to 80% on FPGAs, affecting major frameworks such as TinyGarble and JustGarble. In malicious settings, selective () attacks leverage the malleability of standard OT protocols, allowing a corrupt garbler to inject bogus values during input encoding, thereby revealing evaluator input bits with probability 1/2 per bit unless mitigated by commitments and verification. These practical weaknesses contrast with the ideal-case security proofs, where adversaries are assumed not to exploit leaks. The security of garbled circuits fundamentally depends on cryptographic assumptions that, if violated, lead to complete breakdown. Constructions typically instantiate garbling with a pseudorandom function (PRF) like AES; a weak PRF allows distinguishers to identify real garbled tables from random ones, compromising privacy and authenticity by exposing wire correlations. Moreover, classical garbled circuits offer no inherent quantum resistance, as quantum adversaries can break the underlying OT extensions based on Diffie-Hellman assumptions, necessitating post-quantum OT variants, such as lattice-based protocols, to preserve security. Mitigations focus on both implementation hardening and hybrids to address these limitations. Constant-time garbling and routines, which eliminate secret-dependent branches and accesses, effectively thwart timing and side-channels by ensuring uniform execution paths across inputs. For handling large-scale beyond circuit limits, hybrid protocols integrate garbled circuits with (HE), using HE for efficient arithmetic on encrypted vectors (e.g., on millions of records) while reserving for non-arithmetic logic, achieving up to 38x performance gains over pure in privacy-preserving tasks.