Quest-ce quun “ circuit brouillé ”?

Un circuit est juste une façon de représenter un calcul. Il ny a rien de spécifiquement cryptographique dans un circuit. Cela signifie simplement un calcul en ligne droite (pas de constructions en boucle ou de contrôle de flux) consistant uniquement en des opérations sur bits , comme AND, OR, NOT.

A circuit brouillé est un moyen de « crypter un calcul » qui ne révèle que la sortie du calcul, mais ne révèle rien sur les entrées ou les valeurs intermédiaires . Nous utilisons le terme «circuit» parce que les circuits brouillés fonctionnent en prenant le calcul qui vous tient à cœur, exprimé sous forme de circuit , puis en effectuant des opérations cryptographiques pour chaque opération (ET, OU, PAS) dans le circuit .

Si nous voulons être un peu plus précis, un « schéma de brouillage » consiste en:

• (Garble) Un moyen de convertir un (simple) circuit $ C $ en un circuit brouillé $ \ widehat C $.

• (Encode) Un moyen de convertir nimporte quelle entrée (simple) $ x $ pour le circuit dans une entrée brouillée $ \ widehat x $. Vous avez besoin du caractère aléatoire secret qui a été utilisé pour brouiller le circuit pour encoder $ x $ en $ \ widehat x $.

• (Évaluer) Un moyen de prendre un brouillage circuit $ \ widehat C $ et brouillé entrent $ \ widehat x $ et calculent la sortie du circuit $ C (x) $. Tout le monde peut le faire, vous navez pas besoin de connaître $ x $ ou le caractère aléatoire secret dans $ \ widehat C $ pour évaluer et apprendre $ C (x) $.

Je simplifie un peu ici. Mais lidée principale de la sécurité est que $ \ widehat C $ et $ \ widehat x $ ne divulguent pas plus dinformations que $ C (x) $. En particulier, ils ne révèlent rien sur $ x $, mais ils permettent de faire le calcul $ C (x) $ (inconsciemment). Cest ce que jentends par « chiffrer un calcul ».

Lapplication principale des circuits brouillés est le calcul sécurisé à deux parties. Imaginez quAlice ait une entrée privée $ x $ et Bob une entrée privée $ y $. Ils sont daccord sur une fonction $ f $ et conviennent quils veulent tous les deux apprendre $ f (x, y) $, mais ne veulent pas que leur adversaire apprenne quelque chose de plus que $ f (x, y) ) $. Pour y parvenir, ils peuvent faire ce qui suit (cest le protocole classique de Yao):

1. Les parties saccordent sur un moyen dexprimer $ f $ comme un (simple ) circuit. Alice brouille le circuit $ f \ mapsto \ widehat f $. Elle envoie $ \ widehat f $ à Bob ainsi que sa propre « entrée brouillée » $ \ widehat x $.

2. Alice sait encoder nimporte quelle entrée pour $ f $ en une entrée « brouillée », mais seul Bob connaît son entrée privée $ y $. Alors les parties sarrangent pour que Bob prenne une version déformée $ \ widehat y $ sans quAlice apprenne ce quétait $ y $. Cela peut être fait avec une primitive appelée transfert inconscient.

3. Maintenant, Bob a le circuit brouillé $ \ widehat f $, et une entrée brouillée $ \ widehat x, \ widehat y $ pour ce circuit. Il peut ensuite exécuter la procédure dévaluation et apprendre $ f (x, y) $. Il peut révéler $ f (x, y) $ à Alice.

Nous pouvons affirmer que le protocole ne révèle pas plus de $ f (x, y) $ dans ce qui suit manière:

• Alice ne voit rien dautre que la réponse finale $ f (x, y) $ dans ce protocole (la sécurité du transfert inconscient garantit quelle napprend rien à létape 2).

• Même si Bob voit $ \ widehat f $, $ \ widehat x $ et $ \ widehat y $, la sécurité des circuits brouillés garantit que ces valeurs ne sont pas  » t révéler quoi que ce soit au-delà de $ f (x, y) $.

Cette approche fonctionne quand Alice & Bob est semi-honnête (cest-à-dire quils suivent le protocole comme indiqué). Mais quand Alice est malveillante, elle peut brouiller une autre fonction $ f « $ au lieu des $ f $ sur lesquels ils se sont mis daccord.Il faut donc ajouter dautres éléments au protocole pour éviter que cela ne se produise, lorsque nous voulons une sécurité contre des adversaires malveillants.

Matériel de référence:

• La construction de Yao et sa preuve de sécurité (vidéo), Yehuda Lindell
• Une preuve du protocole de Yao pour le calcul bilatéral sécurisé , Yehuda Lindell & Benny Pinkas
• Fondations de circuits déformés , Mihir Bellare, Viet Tung Hoang, Phillip Rogaway
• Bref historique des optimisations pratiques de circuits déformés , une de mes vidéos . Les premières diapositives couvrent la construction « classique » des circuits déformés.

Commentaires

• Comment Bob déforme-t-il y sans connaître le caractère aléatoire secret quAlice a choisi lorsquelle a inventé le schéma de brouillage?
• Le codage brouillé fonctionne petit à petit. Prenez Bob . Alice peut penser en elle-même: " si Bob a entré le bit 0 alors son encodage brouillé devrait être $ G_0 $. Sil a le bit dentrée 1, son encodage brouillé devrait être $ G_1 $. " Oblivious transfer est une primitive où Alice fournit deux chaînes $ G_0, G_1 $ comme entrée. Bob fournit un bit $ b $ en entrée et apprend $ G_b $ (mais pas lautre $ G_ {1-b} $). Alice napprend pas ' $ b $. Les parties peuvent effectuer un transfert inconscient pour chaque bit dentrée de Bob '. Quant à comment le transfert inconscient fonctionne vraiment, cest une autre question;)
• À côté de Yao ' le circuit brouillé de ' t être réutilisé. Pouvez-vous sil vous plaît résoudre ma confiance que " Est-il permis dattribuer différentes clés à chaque fois quun circuit brouillé est exécuté ou que les clés sont fixées pour les bits dentrée 0 et 1 "