Protocole GMW et transfert inconscient

Le protocole Goldreich-Micali-Wigderson (GMW) évalue les circuits booléens à l’aide de partages de secrets par XOR. Chaque valeur de fil est répartie entre toutes les parties, qui interagissent porte par porte.

La partie i détient une part s_i telle que s_1 ⊕ s_2 ⊕ ... ⊕ s_n = w (la véritable valeur du fil). Les portes XOR sont gratuites : chaque partie effectue localement un XOR sur ses parts.

Pour une porte AND appliquée aux fils a et b, le calcul de (a_1⊕a_2)(b_1⊕b_2) se développe en termes croisés. L’évaluation du terme croisé a_i·b_j entre les parties i≠j nécessite un transfert oblivieux.

Dans un OT 1-sur-2, l’émetteur possède les messages (m_0, m_1) et le récepteur possède le bit de choix c. Le récepteur obtient m_c ; l’émetteur n’apprend rien sur c et le récepteur n’apprend rien sur m_{1-c}.

Ce protocole repose sur Diffie-Hellman : le récepteur génère deux clés publiques de sorte qu’il ne connaît le logarithme discret que de l’une d’elles. L’émetteur chiffre chaque message avec l’une des clés. Le récepteur ne déchiffre que le texte chiffré qu’il a choisi.

Ishai et ses collaborateurs (2003) : à partir de k OT de base, générez m >> k OT en utilisant uniquement des opérations à clé symétrique. L’extension IKNP réduit le coût à environ 3 appels à AES par OT après une configuration initiale unique.

Chaque porte AND nécessite un OT par paire de parties. Avec l’extension OT, le précalcul de tous les OT pendant une phase hors ligne permet de réduire la phase en ligne à un seul échange de XOR par porte.

Le protocole GMW semi-honnête peut être rendu sûr contre les adversaires malveillants à l’aide de preuves à divulgation nulle de connaissance ou d’un OT par découpage et sélection. Le coût est multiplié par 3 à 8, mais la sécurité est garantie contre les parties qui trichent.

MASCOT (Keller et ses collaborateurs) étend l’OT afin de produire des triplets AND authentifiés dans le modèle malveillant, ce qui permet le protocole SPDZ, présenté dans la leçon suivante.

EMP-toolkit et MOTION implémentent GMW avec l’extension OT. Ils atteignent plusieurs millions de portes AND par seconde entre deux parties sur un LAN, ce qui rend les applications réelles réalisables.

Pourquoi les portes XOR du protocole GMW ne nécessitent-elles aucune communication entre les parties ?

GMW utilise des partages de secrets par XOR sur des circuits booléens. Les portes XOR sont gratuites ; les portes AND nécessitent un OT. L’extension OT rend les OT peu coûteux. La sécurité contre les adversaires malveillants ajoute des preuves à divulgation nulle de connaissance ou un découpage et une sélection. Des bibliothèques comme EMP offrent un débit pratique pour les applications réelles.