Yao's garbled circuits

For two parties who want to compute any function, Yao proposed in 1986 an elegant technique: garbled circuits. The idea is to turn the function into a logic circuit, then encrypt it.

A function is a circuit

Any computable function can be written as a boolean circuit: an assembly of logic gates (AND, OR, NOT) connecting input bits to output bits.

  a --->|     |
        | ET  |---> s
  b --->|     |

Comparing two fortunes, adding two numbers, testing an equality: all of this reduces to a circuit of gates. Yao's trick consists of encrypting this circuit.

Garbling the truth tables

One party, called the garbler, takes each gate and encrypts its truth table. Where a classic AND gate is written like this:

 a | b | a ET b
---+---+-------
 0 | 0 |   0
 0 | 1 |   0
 1 | 0 |   0
 1 | 1 |   1

the garbler replaces each 0 and each 1 with a random secret key, and encrypts each output row with the keys of the corresponding inputs. The real values of the bits disappear: all you see are keys that make no sense in the clear.

Evaluating blindly

The other party, the evaluator, receives this garbled circuit. For each gate, it can decrypt only one row: the one corresponding to the keys it holds. It thus obtains the output key without ever knowing the real bits flowing through.

One problem remains: how does the evaluator obtain the keys corresponding to its own inputs, without revealing them to the garbler? Thanks to oblivious transfer:

Brouilleur possède : cle_pour_bit_0  et  cle_pour_bit_1
Évaluateur veut    : la clé de SON bit (0 ou 1)

  -> l'évaluateur reçoit UNIQUEMENT la clé de son bit
  -> le brouilleur n'apprend PAS lequel des deux a été demandé

The evaluator obtains exactly the key it needs, and the garbler does not know which one. No input is disclosed.

The complete flow

1. Brouilleur : transforme f en circuit, brouille chaque porte
2. Brouilleur : envoie le circuit brouillé + ses clés d'entrée
3. Transfert inconscient : l'évaluateur récupère les clés de SES entrées
4. Évaluateur : déchiffre porte après porte -> clé de sortie
5. Les deux traduisent la clé finale en résultat clair

In the end, both parties know f(a, b) — for example "Alice is richer" — without either having seen the other's input.

In summary

Yao's garbled circuits represent the function as a boolean circuit. The garbler encrypts the truth tables of each gate; the evaluator decrypts them blindly, obtaining its own keys through oblivious transfer, without ever learning the other party's inputs.