Free-XOR Optimization

The core insight of Free-XOR is that XOR gates require no ciphertexts and no cryptographic operations during evaluation. The garbler selects a global offset R (a random bit-string) and sets wire labels such that for any XOR gate with inputs A and B, the output label is simply A ⊕ B. The evaluator computes the output label by XORing the input labels they already possess, requiring only a single bitwise XOR operation rather than decrypting a garbled table. This eliminates the 4 ciphertexts per gate typically required in Yao's original construction.

Free-XOR relies on a global offset R chosen uniformly at random by the garbler. For every wire w, the garbler assigns two labels: W⁰ (representing logical 0) and W¹ = W⁰ ⊕ R (representing logical 1). This invariant ensures that for any XOR gate with input wires x and y and output wire z, the relationship Z⁰ = X⁰ ⊕ Y⁰ holds, and the offset R remains consistent across the entire circuit. The evaluator never learns R, preserving security while enabling free evaluation.

While XOR gates become free, AND gates still require cryptographic operations. Each AND gate in a Free-XOR circuit requires the garbler to construct a garbled table of 3 ciphertexts (reduced from 4 using the row-reduction technique). The evaluator must decrypt exactly one of these ciphertexts using the input labels. This asymmetry motivates circuit designers to minimize the multiplicative depth and express logic using as many XOR gates as possible, transforming AND-heavy circuits into XOR-heavy equivalents where feasible.

Free-XOR is fully compatible with the Half-Gates optimization (Zahur et al., Eurocrypt 2015), which reduces AND gate cost to 2 ciphertexts per gate. Together, these techniques form the backbone of modern efficient garbled circuit protocols. The combination yields a total communication cost of 2κ bits per AND gate (where κ is the computational security parameter) and 0 bits per XOR gate, making the protocol bandwidth nearly proportional to the number of AND gates in the circuit. This pairing is implemented in frameworks like EMP-toolkit and MP-SPDZ.

Free-XOR requires a stronger cryptographic assumption than standard garbled circuits. The construction relies on a correlation-robust hash function (or a random oracle) to mask the relationship between wire labels. Specifically, the hash function H must satisfy that H(W⁰, i) ⊕ H(W¹, i) is unpredictable even given W⁰ and W¹ = W⁰ ⊕ R. This property prevents the evaluator from learning the global offset R when decrypting AND gate ciphertexts. The assumption is strictly stronger than the dual-key cipher security used in non-Free-XOR constructions but is widely accepted as reasonable in practice.

Free-XOR transformed secure two-party computation from a theoretical curiosity into a practical tool. In typical circuits, XOR gates often constitute 30-70% of total gates, making the optimization substantial. For example, in AES evaluation (a common MPC benchmark), the S-box circuit contains approximately 56 XOR gates and 32 AND gates per round, meaning Free-XOR eliminates ciphertexts for over 60% of the gates. Combined with Oblivious Transfer Extension for input handling, Free-XOR enables secure evaluation of circuits with millions of gates in seconds rather than hours.