« Plusieurs centres hospitaliers souhaitent croiser les séquences génomiques de leurs patients atteints de cancer pour mener une étude statistique (GWAS), mais la réglementation (RGPD / HIPAA) interdit formellement qu’un seul octet de donnée brute ne sorte de chaque hôpital. » « Des banques concurrentes veulent détecter conjointement des réseaux de blanchiment d’argent interbancaires sans jamais dévoiler leurs listes de clients ni leurs graphes de transactions. »

À première vue, ces exigences semblent contradictoires : pour évaluer une fonction $f(x_1, x_2, \dots, x_n)$, ne faut-il pas qu’un tiers de confiance (Trusted Third Party, TTP) rassemble d’abord toutes les entrées $x_i$ en clair ? Pourtant, à la fin des années 1980, la cryptographie moderne a démontré un théorème fascinant : même en l’absence totale de tiers de confiance, des participants mutuellement méfiants peuvent évaluer conjointement n’importe quelle fonction calculable $f(x_1, \dots, x_n)$ de sorte que chacun apprenne le résultat exact sans qu’aucun participant ne découvre un seul bit d’information supplémentaire sur l’entrée secrète $x_i$ des autres.

Cette discipline s’appelle le calcul multipartite sécurisé (Secure Multi-Party Computation, MPC). Dans cet article, nous partons de deux expériences de pensée célèbres pour démontrer les deux grands moteurs mathématiques du MPC : le partage de secret à seuil $(t, n)$ d’Adi Shamir (interpolation de Lagrange, protocole BGW et triplets de Beaver) et l’approche par circuits booléens via le transfert inconscient ($\text{OT}_1^2$) de Rabin et les circuits brouillés (Garbled Circuits) de Yao.

1. Deux expériences de pensée paradoxales : « Le salaire moyen sans patron » et « Le problème des millionnaires de Yao »

1.1 Expérience de pensée 1 : Calculer le salaire moyen sans révéler aucun salaire individuel

Trois ingénieurs $A, B$ et $C$ veulent connaître leur salaire annuel moyen $\bar{x} = \frac{x_A + x_B + x_C}{3}$ sans qu’aucun ne découvre le salaire individuel $x_A, x_B$ ou $x_C$ d’un autre. Grâce au partage de secret additif (masquage par masque jetable / One-Time Pad), ils y parviennent sans aucun tiers :

1. Masque aléatoire et premier murmure ($A \to B$) : Les trois ingénieurs choisissent un grand entier public $M$ (par exemple $M = 10^9$). L’ingénieur $A$ tire secrètement un nombre aléatoire uniforme $r \xleftarrow{\$} \mathbb{Z}_M$, l'ajoute à son salaire $x_A$ et murmure uniquement $s_1 = (x_A + r) \bmod M$ à $B$. Comme $r$ est uniformément distribué sur $\mathbb{Z}_M$, $s_1$ l'est aussi quel que soit $x_A$ : par le théorème de Shannon sur le secret parfait, l'information mutuelle est nulle ($I(X_A; S_1) = 0$). $B$ n'apprend littéralement zéro bit sur $x_A$.
2. Additions successives ($B \to C \to A$) : $B$ ajoute son propre salaire $x_B$ et murmure $s_2 = (x_A + x_B + r) \bmod M$ à $C$ ; $C$ ajoute $x_C$ et transmet $s_3 = (x_A + x_B + x_C + r) \bmod M$ à $A$.
3. Démasquage : $A$ soustrait son masque secret $r$ modulo $M$, obtient la somme exacte $S = x_A + x_B + x_C$ et annonce la moyenne $\bar{x} = S / 3$.

[!NOTE] Pourquoi faut-il au moins 3 participants ($n \ge 3$) ? S’il n’y avait que deux personnes ($A$ et $B$), même si un ange parfait leur révélait uniquement la moyenne $\bar{x} = \frac{x_A + x_B}{2}$, $A$ déduirait immédiatement $x_B = 2\bar{x} - x_A$. Ce n’est pas une faille du protocole, mais une propriété intrinsèque de la fonction. Le MPC garantit qu’aucune information supplémentaire n’est révélée au-delà de ce qui découle logiquement de sa propre entrée et du résultat final.

1.2 Expérience de pensée 2 : Le « problème des millionnaires » d’Andrew Yao (1982)

L’addition est linéaire, mais qu’en est-il d’une comparaison d’ordre non linéaire ? En 1982, l’informaticien Andrew Chi-Chih Yao (futur prix Turing) a publié “Protocols for Secure Computations”, posant le célèbre problème des millionnaires : deux millionnaires, Alice ($x$ millions de dollars) et Bob ($y$ millions de dollars), veulent calculer uniquement le bit de vérité $f(x, y) = [x > y] \in \{0, 1\}$ (qui est le plus riche ?) sans révéler la valeur de $x$ ou $y$, ni même leur écart $x - y$.

2. Formalisation mathématique de la sécurité : Le paradigme de simulation Idéal/Réel

Pour prouver mathématiquement l’absence totale de fuite d’information, Goldreich, Micali et Wigderson (GMW 1987) ont introduit le paradigme de simulation Monde Idéal / Monde Réel :

  flowchart TD
    subgraph IdealWorld["Monde Idéal (Ideal World) : Référence absolue de confidentialité"]
        direction TB
        PA1["Partie P1 (Entrée secrète x1)"] -->|"Canal privé parfait"| TTP["Fonctionnalité Idéale Incorruptible F"]
        PA2["Partie P2 (Entrée secrète x2)"] -->|"Canal privé parfait"| TTP
        PAn["Partie Pn (Entrée secrète xn)"] -->|"Canal privé parfait"| TTP
        TTP -->|"Renvoie uniquement y = f(x1,...,xn)"| Out1["Chacun apprend uniquement y (Fuite intermédiaire nulle)"]
        Out1 --> Sim["Simulateur S (Fabrique une fausse trace à partir des seules entrées corrompues et de y)"]
    end

    subgraph RealWorld["Monde Réel (Real World) : Protocole cryptographique Π"]
        direction TB
        RB1["Partie P1 (Entrée secrète x1)"] <-->|"Messages chiffrés et parts aléatoires"| RB2["Partie P2 (Entrée secrète x2)"]
        RB2 <-->|"Messages chiffrés et parts aléatoires"| RBn["Partie Pn (Entrée secrète xn)"]
        RB1 <-->|"Messages chiffrés et parts aléatoires"| RBn
        RB2 --> View["Vue complète View_A(x1,...,xn) observée par l'adversaire A"]
    end

    Sim <-->|"Distributions de probabilité indistinguables (View_A ≈ Sim)"| View

On distingue les adversaires semi-honnêtes (Semi-Honest / Passive), qui suivent le protocole mais analysent les échanges, et les adversaires malveillants (Malicious / Active), qui tentent de tricher activement.

3. Moteur 1 : Partage de secret à seuil $(t, n)$ de Shamir, interpolation de Lagrange et BGW / SPDZ

3.1 Partage polynomial sur $\mathbb{F}_p$ et reconstruction de Lagrange

À l’inverse, avec $t - 1$ parts ou moins, chaque secret candidat $s' \in \mathbb{F}_p$ correspond à un unique polynôme de degré $t - 1$ équiprobable ($H(S \mid \text{Shares}_{t-1}) = H(S)$, sécurité inconditionnelle au sens de la théorie de l’information).

3.2 Protocole BGW et triplets de multiplication de Beaver

4. Moteur 2 : Transfert inconscient ($\text{OT}_1^2$) de Rabin et circuits brouillés (Garbled Circuits) de Yao

Pour les comparaisons binaires ($x > y$), l’approche par circuits booléens s’exécute en un nombre constant $O(1)$ de tours :

  flowchart TD
    subgraph Step1["1. Alice (Garbler) : Brouillage du circuit booléen"]
        W["Générer pour chaque fil w_i deux clés AES 128 bits aléatoires (k_i^0, k_i^1)"] --> G["Chiffrer doublement les 4 lignes de chaque porte logique : Enc(k_a^α, k_b^β, k_c^g(α,β))"]
        G --> P["Permuter aléatoirement les 4 chiffrés de chaque porte (Garbled Table)"]
    end

    subgraph Step2["2. Transfert des clés via Transfert Inconscient 1-parmi-2 (OT_1^2)"]
        P -->|"Envoyer les tables brouillées + la clé active d'Alice k_a^x"| Eval["Bob (Evaluator)"]
        BobIn["Bit secret de Bob y ∈ {0,1}"] --> OT["Transfert Inconscient 1-parmi-2 (OT_1^2)"]
        W -->|"Paire de clés candidates (k_b^0, k_b^1)"| OT
        OT -->|"Bob reçoit UNIQUEMENT k_b^y (Alice ignore tout de y)"| Eval
    end

    subgraph Step3["3. Bob (Evaluator) : Évaluation aveugle porte par porte"]
        Eval --> Dec["Déchiffrer exactement 1 des 4 lignes par porte avec (k_a^x, k_b^y) -> clé de sortie k_c^z"]
        Dec --> Out["Associer la clé du fil de sortie final au résultat en clair z = f(x,y)"]
    end

Grâce au transfert inconscient 1-parmi-2 ($\text{OT}_1^2$) de Michael Rabin, Bob récupère la clé $k_b^y$ correspondant à son bit secret $y$ sans qu’Alice ne découvre $y$ et sans que Bob ne découvre $k_b^{1-y}$. Les trois optimisations modernes — Point-and-Permute (bits de couleur indiquant directement la ligne à déchiffrer), Free-XOR ($k_i^1 = k_i^0 \oplus \Delta$ rendant toutes les portes XOR gratuites sans chiffré ni calcul AES) et Half-Gates (réduisant chaque porte AND à 2 chiffrés) — ont accéléré les circuits brouillés d’un facteur $1000$.

5. Implémentation complète en Python : Partage de Shamir et triplets de Beaver sur $\mathbb{F}_p$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

import secrets
from typing import List, Tuple

PRIME = (1 << 61) - 1  # Nombre premier de Mersenne de 61 bits p = 2^61 - 1

def mod_inv(a: int, p: int = PRIME) -> int:
    return pow(a % p, -1, p)

def shamir_share(secret: int, t: int, n: int, p: int = PRIME) -> List[Tuple[int, int]]:
    coeffs = [secret % p] + [secrets.randbelow(p) for _ in range(t - 1)]
    shares = []
    for i in range(1, n + 1):
        y = 0
        for c in reversed(coeffs):
            y = (y * i + c) % p
        shares.append((i, y))
    return shares

def lagrange_reconstruct(shares: List[Tuple[int, int]], p: int = PRIME) -> int:
    secret = 0
    k = len(shares)
    for i in range(k):
        xi, yi = shares[i]
        num, den = 1, 1
        for j in range(k):
            if i != j:
                xj, _ = shares[j]
                num = (num * (-xj)) % p
                den = (den * (xi - xj)) % p
        secret = (secret + yi * num * mod_inv(den, p)) % p
    return secret

def mpc_add(sa, sb, p=PRIME):
    return [(xa, (ya + yb) % p) for (xa, ya), (_, yb) in zip(sa, sb)]

def mpc_sub(sa, sb, p=PRIME):
    return [(xa, (ya - yb) % p) for (xa, ya), (_, yb) in zip(sa, sb)]

def mpc_scalar_mul(c, sa, p=PRIME):
    return [(xa, (c * ya) % p) for xa, ya in sa]

def mpc_add_const(c, sa, p=PRIME):
    return [(xa, (ya + c) % p) for xa, ya in sa]

def generate_beaver_triple(t: int, n: int, p: int = PRIME):
    u, v = secrets.randbelow(p), secrets.randbelow(p)
    return shamir_share(u, t, n, p), shamir_share(v, t, n, p), shamir_share((u * v) % p, t, n, p)

def mpc_beaver_mul(sx, sy, triple, t: int, p: int = PRIME):
    su, sv, sw = triple
    d = lagrange_reconstruct(mpc_sub(sx, su, p)[:t], p)
    e = lagrange_reconstruct(mpc_sub(sy, sv, p)[:t], p)
    res = mpc_add(mpc_add(sw, mpc_scalar_mul(d, sv, p), p), mpc_scalar_mul(e, su, p), p)
    return mpc_add_const((d * e) % p, res, p)

if __name__ == "__main__":
    t, n = 3, 5
    salaries = [85000, 92000, 78000]
    shared = [shamir_share(s, t, n) for s in salaries]
    total_shares = shared[0]
    for s in shared[1:]:
        total_shares = mpc_add(total_shares, s)
    print("Somme totale reconstruite :", lagrange_reconstruct(total_shares[:t]))

6. Comparaison des technologies de protection de la vie privée (PETs) et applications réelles

De la double enchère danoise sur les quotas de betteraves sucrières en 2008 à l’étude sur les écarts salariaux de la ville de Boston (BWWC), en passant par la vérification des mots de passe compromis dans Google Chrome et Apple iCloud (Private Set Intersection, PSI), les études génomiques inter-hospitalières (Secure GWAS) et les portefeuilles cryptographiques à seuil MPC (Fireblocks, Coinbase), le MPC remplace aujourd’hui la confiance institutionnelle par la certitude mathématique.