Advanced

Garbled Circuits

Yao's garbled circuits protocol enables two-party secure computation with constant round complexity. One party creates an encrypted version of a Boolean circuit, and the other evaluates it without learning intermediate values.

How Garbled Circuits Work

The protocol involves two parties: the garbler (who creates the encrypted circuit) and the evaluator (who computes the result):

  1. Circuit Representation

    Express the desired computation as a Boolean circuit (AND, OR, XOR gates connected by wires).

  2. Garbling

    The garbler assigns two random cryptographic keys to each wire — one for 0 and one for 1. For each gate, the garbler encrypts the output keys under the corresponding input keys, creating a garbled truth table.

  3. Input Encoding

    The garbler sends the garbled circuit and the keys corresponding to their own input bits. The evaluator obtains keys for their input bits via oblivious transfer (OT).

  4. Evaluation

    The evaluator processes the circuit gate by gate, using the keys to decrypt exactly one entry in each garbled truth table, obtaining the output keys.

  5. Output Decoding

    The garbler provides a mapping from output keys to actual output bits. The evaluator learns only the final result.

💡
Key property: The evaluator processes each gate using exactly one key per wire. They cannot tell which bit (0 or 1) any key represents, so they learn nothing about intermediate values — only the final output.

Oblivious Transfer (OT)

Oblivious Transfer is a crucial building block where a sender holds two messages (m0, m1) and the receiver has a choice bit b. After the protocol:

  • The receiver learns mb (the message corresponding to their choice)
  • The sender does not learn which message was chosen (does not learn b)
  • The receiver does not learn the other message

In garbled circuits, OT is used for the evaluator to obtain keys for their input bits without the garbler learning those bits.

Optimizations

Free XOR

XOR gates can be evaluated without any cryptographic operations or communication. The garbler chooses a global offset R, and for each wire, the key for 1 is the key for 0 XORed with R. XOR gates are computed by simply XORing input keys.

Point-and-Permute

Attach a "color bit" to each key that indicates which row of the garbled truth table to decrypt. This eliminates the need to try all rows, reducing evaluation to a single decryption per gate.

Half Gates

Reduces AND gates from 4 ciphertexts to 2, cutting communication by 50% for AND-heavy circuits.

OT Extension

Perform millions of OTs using only a small number (128) of base OTs plus symmetric-key operations. This makes the cost of OT nearly free for large circuits.

Garbled Circuits for ML

In secure ML inference, garbled circuits are particularly useful for:

  • ReLU activations: ReLU(x) = max(0, x) requires a comparison, which is natural in Boolean circuits.
  • Argmax: Finding the predicted class requires comparisons across output neurons.
  • Sign function: Used in various ML operations that need to determine positive/negative.
✅
Hybrid approach: Modern secure ML frameworks like CrypTen use secret sharing for linear layers (matrix multiplications — the bulk of computation) and garbled circuits only for non-linear activations. This combines the strengths of both approaches for optimal performance.