Problème MPC et circuits brouillés de Yao

Le MPC permet à n parties, détenant chacune une entrée privée x_i, de calculer conjointement f(x_1,...,x_n) sans se révéler mutuellement leurs entrées — comme si un tiers de confiance effectuait le calcul.

Le problème des millionnaires de Yao, formulé en 1982 : Alice et Bob veulent savoir qui est le plus riche sans révéler leur fortune. Aucun tiers de confiance n’est utilisé. Le MPC résout ce problème avec des garanties cryptographiques.

1. Confidentialité : les parties n’apprennent que le résultat et ce qu’elles peuvent en déduire. 2. Exactitude : le résultat est correct même si certaines parties sont corrompues. 3. Il existe des variantes pour les adversaires semi-honnêtes et malveillants.

Toute fonction peut être exprimée sous la forme d’un circuit booléen (portes AND, XOR et NOT). Les protocoles MPC fonctionnent souvent au niveau du circuit et évaluent chaque porte de manière sécurisée.

Alice (la brouilleuse) attribue deux étiquettes aléatoires à chaque fil : une pour 0 et une pour 1. Elle chiffre la table de vérité de chaque porte avec les étiquettes des fils d’entrée. Bob (l’évaluateur) n’obtient que les étiquettes correspondant à ses entrées grâce à un transfert oblivieux.

Bob reçoit des tables brouillées (4 chiffrages par porte AND). Il déchiffre exactement une ligne à l’aide de ses étiquettes d’entrée et obtient l’étiquette de sortie, sans savoir si elle représente 0 ou 1.

Associez un « bit de sélection » aléatoire à chaque étiquette. Bob utilise ces bits de sélection pour trouver la bonne ligne brouillée en O(1), au lieu d’essayer les quatre déchiffrements. Cela réduit le calcul d’un facteur 4.

Kolesnikov et Schneider (2008) : choisissez un décalage global Δ. Ensuite, label_1 = label_0 ⊕ Δ pour chaque fil. Les portes XOR deviennent gratuites (aucun chiffrement n’est nécessaire), ce qui économise environ 30 % de bande passante.

Zahur et ses collaborateurs (2015) : chaque porte AND ne nécessite plus que 2 textes chiffrés, contre 4 auparavant. Combinée à l’optimisation XOR libre, cette méthode divise par deux la bande passante des circuits brouillés classiques.

Les circuits brouillés classiques sont conçus pour deux parties. Les extensions multipartites (par exemple, le protocole BMR) parallélisent le brouillage entre toutes les parties, mais nécessitent une communication en O(n²). Elles sont pratiques pour un petit nombre de parties.

Le MPC permet aux parties de calculer conjointement sans révéler leurs entrées. Les circuits brouillés représentent les fonctions booléennes sous forme de tables de vérité chiffrées. Les optimisations (XOR libre, demi-portes, pointage et permutation) les rendent pratiques. Le transfert OT fournit à Bob les étiquettes de ses entrées en privé.