Programme Leçon 135 sur 156 · Les technologies de vie privée au-delà du blocage
Les technologies de vie privée au-delà du blocage

La Private Set Intersection

Pourquoi c'est important Les entreprises veulent souvent savoir quels clients elles ont en commun, pour une offre conjointe ou pour mesurer si une publicité a marché. La façon facile est d'échanger les listes de clients, ce qui veut dire que ton e-mail atterrit dans la base de données d'une autre entreprise. La Private Set Intersection leur permet de trouver le recoupement sans qu'aucun des deux ne livre sa liste. Savoir comment ça marche te permet de distinguer une vraie confidentialité d'un « nous n'avons partagé que des e-mails hachés ».

De la crypto pédagogique, pas sûre : les nombres des labos de ce module sont assez petits pour être lus et l'aléatoire a une graine pour que la notation soit reproductible. Les vrais systèmes utilisent des bibliothèques éprouvées et des nombres bien plus grands. Ne copie jamais du code pédagogique dans un produit.

Le problème

Une boutique et une appli ont chacune une liste d'e-mails de clients. Elles veulent les e-mails présents sur les deux listes, et rien d'autre : la boutique ne doit pas apprendre les autres utilisateurs de l'appli, et l'appli ne doit pas apprendre les autres clients de la boutique.

Intersection d'ensembles : les éléments que deux listes ont en commun. Private Set Intersection (PSI) : une façon pour deux parties de la calculer sans rien révéler d'autre sur leurs listes.

Pourquoi « il suffit de hacher » échoue

Hash : une fonction qui transforme un texte en un brouillage de longueur fixe (SHA-256 est courante). La même entrée donne toujours la même sortie, et on ne peut pas la faire tourner directement à l'envers.

« Nous échangeons des e-mails hachés, donc personne ne voit les vrais », ça a l'air sûr. Mais les e-mails se devinent. Quiconque détient une liste d'e-mails probables peut hacher chaque supposition et chercher des correspondances, comme essayer chaque clé d'un gros trousseau. Ta fonction naive_reverse fera exactement ça avec les 200 e-mails synthétiques du monde d'entraînement. Le hachage ne cache les données que quand les entrées ne peuvent pas être devinées, et les e-mails, les numéros de téléphone et les noms peuvent l'être.

L'astuce des deux cadenas

Souviens-toi de la leçon de maths : poser le secret a, puis le secret b, revient à poser b puis a. Imagine chaque e-mail comme une boîte. Alice met son propre cadenas sur chacune de ses boîtes et les envoie à Bob. Bob ajoute son cadenas et les renvoie. Bob ferme aussi ses propres boîtes et les envoie à Alice, qui ajoute son cadenas. Maintenant, chaque boîte a les deux cadenas, et deux boîtes qui contiennent le même e-mail ont l'air identiques, quel que soit le cadenas posé en premier.

En nombres, avec le groupe d'entraînement de watched.leg7a_privacy (P, hash_to_group, random_secret) :

  1. Alice envoie blind(alice_items, a) : chaque élément haché dans le groupe puis élevé à a.
  2. Bob les élève à b (reblind) et les renvoie dans le même ordre.
  3. Bob envoie blind(bob_items, b).
  4. Alice élève les valeurs de Bob à a. Chacune de ses valeurs à double cadenas qui apparaît dans l'ensemble à double cadenas de Bob est un élément commun. Comme elle a gardé l'ordre, elle sait à quel élément à elle correspond chacune.

Pourquoi est-ce sûr là où le hachage a échoué ? Pour tester une supposition, il te faut les deux secrets, et chaque côté garde le sien. Bob ne voit jamais les valeurs d'Alice qu'avec son secret à elle posé dessus, et elles ressemblent à des nombres aléatoires.

PSI de Diffie-Hellman : le nom de ce protocole, d'après l'idée d'échange de clés de 1976 qu'il emprunte (deux parties qui combinent des exposants secrets). Les vraies versions utilisent des courbes elliptiques (une autre sorte de groupe, avec la même propriété « l'ordre n'a pas d'importance » et des nombres bien plus courts) et un hachage soigné.

La réponse est elle-même une divulgation

Même une PSI parfaite dit à Alice qu'une personne précise est cliente de Bob. Si Bob est une clinique ou un conseiller en dettes, c'est sensible. Souvent, une entreprise n'a besoin que de savoir combien de clients sont communs. Dans la PSI de cardinalité, Bob mélange sa réponse à l'étape 2, donc Alice peut compter les correspondances mais pas dire à quels éléments à elle elles appartiennent. Demande le minimum qui répond à la question.

Dans d'autres langages

L'étape d'aveuglement en JavaScript avec BigInt (avec une fonction d'aide powMod comme celle de la leçon de maths) :

const blind = (items, secret) => items.map(x => powMod(hashToGroup(x), secret, P));
const reblind = (values, secret) => values.map(v => powMod(v, secret, P));

Et en Go avec math/big :

func reblind(values []*big.Int, secret, p *big.Int) []*big.Int {
    out := make([]*big.Int, len(values))
    for i, v := range values {
        out[i] = new(big.Int).Exp(v, secret, p)
    }
    return out
}

Pour les vrais produits, utilise une bibliothèque de PSI auditée plutôt que d'écrire la tienne.

Récap

  • Les e-mails hachés sont faciles à retrouver avec une liste de suppositions, donc « nous n'avons partagé que des hashes » n'est pas de la confidentialité.
  • La PSI de Diffie-Hellman met deux cadenas sur chaque élément avec deux secrets dont l'ordre n'a pas d'importance, donc les correspondances apparaissent sans qu'aucune liste ne soit révélée.
  • Garder l'ordre révèle quels éléments correspondent ; mélanger (la PSI de cardinalité) ne révèle que combien.
  • L'intersection est elle-même une donnée personnelle, donc demande le minimum qui répond à la question.
À ton tour

Écris cinq fonctions. naive_reverse(hashes, candidates) renvoie la liste triée des candidats dont le condensé SHA-256 en hexadécimal (hashlib.sha256(c.encode()).hexdigest()) est dans hashes. blind(items, secret) renvoie [pow(hash_to_group(x), secret, P) for x in items]. reblind(values, secret) élève chaque valeur à secret modulo P, en gardant l'ordre. psi(alice_items, bob_items, a_secret, b_secret) suit les quatre étapes de la leçon avec blind et reblind, et renvoie la liste triée des éléments d'Alice que Bob a aussi. psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) fait la même chose mais mélange la réponse de Bob avec rng.shuffle et ne renvoie que le nombre d'éléments communs.

Tu as repéré un problème dans cette leçon ? Signale-le · Pose une question sur cette leçon

Cet exercice s'ouvre bientôt

Termine la leçon précédente pour débloquer celle-ci. Tout le cours est gratuit, aucun compte n'est requis, et tu peux lire cette leçon dès maintenant.