Private Set Intersection
Warum das wichtig ist Firmen wollen oft wissen, welche Kunden sie gemeinsam haben, für ein gemeinsames Angebot oder um zu messen, ob eine Anzeige gewirkt hat. Der einfache Weg ist, Kundenlisten zu tauschen, was bedeutet, dass deine E-Mail in der Datenbank einer anderen Firma landet. Private Set Intersection lässt sie die Überschneidung finden, ohne dass eine Seite ihre Liste herausgibt. Zu wissen, wie das funktioniert, lässt dich echten Datenschutz von "wir haben nur gehashte E-Mails geteilt" unterscheiden.
Krypto zum Lernen, nicht sicher: Die Zahlen in den Laboren dieses Moduls sind klein genug zum Lesen, und der Zufall hat einen festen Seed, damit die Bewertung wiederholbar ist. Echte Systeme benutzen geprüfte Bibliotheken und viel größere Zahlen. Kopiere nie Lerncode in ein Produkt.
Das Problem
Ein Shop und eine App haben jeweils eine Liste von Kunden-E-Mails. Sie wollen die E-Mails, die auf beiden Listen stehen, und sonst nichts: Der Shop darf die anderen Nutzer der App nicht erfahren, und die App nicht die anderen Kunden des Shops.
Schnittmenge: die Einträge, die zwei Listen gemeinsam haben. Private Set Intersection (PSI): ein Weg für zwei Parteien, sie zu berechnen und dabei sonst nichts über ihre Listen zu verraten.
Warum "einfach hashen" scheitert
Hash: eine Funktion, die Text in ein Gewirr fester Länge verwandelt (SHA-256 ist eine gängige). Dieselbe Eingabe ergibt immer dieselbe Ausgabe, und man kann sie nicht direkt rückwärts laufen lassen.
"Wir tauschen gehashte E-Mails, also sieht niemand die echten" klingt sicher. Aber E-Mails lassen sich erraten. Wer eine Liste wahrscheinlicher E-Mails hat, kann jede Vermutung hashen und nach Treffern suchen, wie jeden Schlüssel an einem großen Schlüsselbund ausprobieren. Deine Funktion naive_reverse macht genau das mit den 200 synthetischen E-Mails der Übungswelt. Hashen versteckt Daten nur, wenn sich die Eingaben nicht erraten lassen, und E-Mails, Telefonnummern und Namen lassen sich erraten.
Der Trick mit den zwei Schlössern
Erinnere dich an die Mathe-Lektion: Erst Geheimnis a anwenden, dann Geheimnis b, ergibt dasselbe wie erst b, dann a. Stell dir jede E-Mail als Kiste vor. Alice hängt ihr eigenes Schloss an jede ihrer Kisten und schickt sie an Bob. Bob hängt sein Schloss dazu und schickt sie zurück. Bob schließt auch seine eigenen Kisten ab und schickt sie an Alice, die ihr Schloss dazuhängt. Jetzt hat jede Kiste beide Schlösser, und zwei Kisten mit derselben E-Mail darin sehen gleich aus, egal welches Schloss zuerst dran war.
In Zahlen, mit der Übungsgruppe aus watched.leg7a_privacy (P, hash_to_group, random_secret):
- Alice schickt
blind(alice_items, a): jeder Eintrag in die Gruppe gehasht und dann hochagenommen. - Bob nimmt diese hoch
b(reblind) und schickt sie in derselben Reihenfolge zurück. - Bob schickt
blind(bob_items, b). - Alice nimmt Bobs Werte hoch
a. Jeder ihrer doppelt verschlossenen Werte, der in Bobs doppelt verschlossener Menge vorkommt, ist ein gemeinsamer Eintrag. Weil sie die Reihenfolge behalten hat, weiß sie, welcher ihrer Einträge jeder ist.
Warum ist das sicher, wo Hashen scheiterte? Um eine Vermutung zu prüfen, brauchst du beide Geheimnisse, und jede Seite behält ihr eigenes. Bob sieht Alices Werte immer nur mit ihrem Geheimnis darauf, und die sehen aus wie Zufallszahlen.
Diffie-Hellman-PSI: der Name dieses Protokolls, nach der Idee des Schlüsselaustauschs von 1976, die es borgt (zwei Parteien kombinieren geheime Exponenten). Echte Versionen benutzen elliptische Kurven (eine andere Art von Gruppe, mit derselben Eigenschaft "die Reihenfolge spielt keine Rolle" und viel kürzeren Zahlen) und sorgfältiges Hashen.
Die Antwort ist selbst eine Offenlegung
Selbst perfekte PSI verrät Alice, dass eine bestimmte Person Bobs Kunde ist. Ist Bob eine Klinik oder eine Schuldnerberatung, ist das sensibel. Oft braucht eine Firma nur, wie viele Kunden sie teilen. Bei PSI-Kardinalität mischt Bob seine Antwort in Schritt 2, sodass Alice Treffer zählen kann, aber nicht erkennt, zu welchen ihrer Einträge sie gehören. Frag nach dem Wenigsten, das die Frage beantwortet.
In anderen Sprachen
Der Blendschritt in JavaScript mit BigInt (mit einer Hilfsfunktion powMod wie in der Mathe-Lektion):
const blind = (items, secret) => items.map(x => powMod(hashToGroup(x), secret, P));
const reblind = (values, secret) => values.map(v => powMod(v, secret, P));Und in Go mit 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
}Benutze für echte Produkte eine geprüfte PSI-Bibliothek, statt deine eigene zu schreiben.
Zusammenfassung
- Gehashte E-Mails lassen sich mit einer Liste von Vermutungen leicht umkehren, also ist "wir haben nur Hashes geteilt" kein Datenschutz.
- Diffie-Hellman-PSI verschließt jeden Eintrag doppelt mit zwei Geheimnissen, deren Reihenfolge keine Rolle spielt, sodass Treffer sichtbar werden, ohne dass eine Liste offengelegt wird.
- Die Reihenfolge zu behalten verrät, welche Einträge passen; Mischen (PSI-Kardinalität) verrät nur, wie viele.
- Die Schnittmenge ist selbst personenbezogene Daten, also frag nach dem Wenigsten, das die Frage beantwortet.
Schreibe fünf Funktionen. naive_reverse(hashes, candidates) gibt die sortierte Liste der Kandidaten zurück, deren SHA-256 hex digest (hashlib.sha256(c.encode()).hexdigest()) in hashes ist. blind(items, secret) gibt [pow(hash_to_group(x), secret, P) for x in items] zurück. reblind(values, secret) erhöht jeden Wert auf secret modulo P und behält die Reihenfolge bei. psi(alice_items, bob_items, a_secret, b_secret) folgt den vier Schritten der Lektion unter Verwendung von blind und reblind und gibt die sortierte Liste von Alices Gegenständen zurück, die Bob auch hat. psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) macht dasselbe, aber mischt Bobs Antwort mit rng.shuffle und gibt nur die Anzahl der gemeinsamen Gegenstände zurück.
Ein Problem in dieser Lektion entdeckt? Melde es · Frage zu dieser Lektion
Diese Übung öffnet bald
Beende die vorherige Lektion, damit diese freigeschaltet wird. Der ganze Kurs ist kostenlos, kein Konto erforderlich, und du kannst diese Lektion jetzt direkt lesen.
Dieser Browser blockiert Cookies für learn.floati.life, daher können hier beendigte Lektionen nicht in der richtigen Reihenfolge geöffnet werden. Erlaube Cookies für diese Seite und lade sie neu.