Garbled Circuits

Garbled circuits are a specific protocol for secure two-party computation (2PC). One party, the garbler, encrypts (garbles) a Boolean circuit representing the function to be computed. The other party, the evaluator, receives the garbled circuit and, using oblivious transfer to obtain encrypted input labels, evaluates it to produce an encrypted output, which only the garbler can decrypt. This allows both parties to learn the result while keeping their respective inputs private from each other.

The function to be computed must be expressed as a Boolean circuit composed of logic gates (AND, OR, XOR, NOT). Each wire in the circuit is assigned two random cryptographic labels (or keys), one representing logical '0' and one representing '1'. The computation proceeds gate-by-gate in this encrypted form. This requirement means complex functions can become large, deep circuits, impacting performance, which is a key engineering consideration.

A core security property is that a garbled circuit is usable only once. If evaluated on multiple input sets, it would leak information. The garbling scheme (the algorithm for encrypting the circuit) ensures this. Furthermore, the evaluator must obtain the correct input labels for their private inputs without the garbler learning which values they correspond to. This is achieved through a 1-out-of-2 oblivious transfer (OT) protocol for each of the evaluator's input bits.

Standard garbled circuit constructions provide computational security, relying on cryptographic assumptions like the existence of one-way functions. The garbler's security (hiding the circuit logic) is often information-theoretic, meaning it's secure even against a computationally unbounded evaluator. The evaluator's security (hiding their input) is typically computational, based on the security of the oblivious transfer protocol and the encryption used for the garbled tables.

Several optimizations make practical implementation feasible:

• Free XOR: Allows XOR gates to be garbled and evaluated without cryptographic cost, drastically improving performance for circuits with many XOR gates.
• Garbled Row Reduction (GRR3): Reduces the size of the encrypted truth table (garbled table) for non-XOR gates from 4 entries to 3 or even 2, cutting communication overhead.
• Pipelining & Parallelization: The circuit evaluation is highly parallelizable, as each gate can be processed as soon as its input wire labels are available.

In privacy-preserving machine learning (PPML), garbled circuits enable secure inference. For example, a client with a private medical image (input) can interact with a server holding a proprietary diagnostic model (the circuit). The server garbles the model circuit, and through oblivious transfer and evaluation, the client learns only the diagnosis (output), while the server learns nothing about the image or the result. This is a concrete application within privacy-preserving RAG for querying encrypted knowledge bases.

A Boolean Circuit is the computational model upon which garbled circuits operate. It is a directed acyclic graph where:

• Nodes are logic gates (AND, OR, NOT, XOR).

• Edges are wires carrying binary values (0 or 1).

• Input Wires receive the private inputs from the parties.

• Output Wires produce the final result of the computation.

• Critical Constraint: The function to be computed securely must first be expressed as a Boolean circuit. This compilation step is a major practical consideration, as complex programs (like machine learning inference) result in very large circuits, impacting performance.