Les circuits brouillés de Yao (garbled circuits)

Pour deux parties qui veulent calculer n'importe quelle fonction, Yao a proposé en 1986 une technique élégante : les circuits brouillés (en anglais garbled circuits). L'idée est de transformer la fonction en circuit logique, puis de le chiffrer.

Une fonction, c'est un circuit

Toute fonction calculable peut s'écrire comme un circuit booléen : un assemblage de portes logiques (ET, OU, NON) reliant des bits d'entrée à des bits de sortie.

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

Comparer deux fortunes, additionner deux nombres, tester une égalité : tout cela se ramène à un circuit de portes. L'astuce de Yao consiste à chiffrer ce circuit.

Brouiller les tables de vérité

Une partie, appelée le brouilleur (garbler), prend chaque porte et chiffre sa table de vérité. Là où une porte ET classique s'écrit ainsi :

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

le brouilleur remplace chaque 0 et chaque 1 par une clé secrète aléatoire, et chiffre chaque ligne de sortie avec les clés des entrées correspondantes. Les valeurs réelles des bits disparaissent : on ne voit plus que des clés qui n'ont aucun sens en clair.

Évaluer à l'aveugle

L'autre partie, l'évaluateur, reçoit ce circuit brouillé. Pour chaque porte, elle ne peut déchiffrer qu'une seule ligne : celle qui correspond aux clés qu'elle détient. Elle obtient donc la clé de sortie sans jamais connaître les bits réels qui circulent.

Reste un problème : comment l'évaluateur obtient-il les clés correspondant à ses propres entrées, sans les révéler au brouilleur ? Grâce au transfert inconscient (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é

L'évaluateur obtient exactement la clé dont il a besoin, et le brouilleur ne sait pas laquelle. Aucune entrée n'est dévoilée.

Le déroulé complet

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

À la fin, les deux parties connaissent f(a, b) — par exemple « Alice est plus riche » — sans qu'aucune n'ait vu l'entrée de l'autre.

En résumé

Les circuits brouillés de Yao représentent la fonction comme un circuit booléen. Le brouilleur chiffre les tables de vérité de chaque porte ; l'évaluateur les déchiffre à l'aveugle, obtenant ses propres clés par transfert inconscient, sans jamais apprendre les entrées de l'autre partie.