Sichere Aggregation
Warum das wichtig ist Eine Fitness-App will die Gesamtzahl der in einer Stadt gegangenen Schritte; ein Tastaturhersteller will wissen, wie oft ein Wort auf allen Handys getippt wird. In jedem Fall braucht die Firma eine Zahl von vielen Geräten. Sichere Aggregation lässt sie diese Summe erfahren, ohne je den Wert einer einzelnen Person zu sehen, und sie ist überraschend einfach.
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.
Der Gehaltstrick
Drei Freunde wollen ihr Durchschnittsgehalt wissen, ohne dass jemand sein eigenes verrät. Die Erste addiert eine große Zufallszahl zu ihrem Gehalt und flüstert das Ergebnis dem Zweiten zu. Er addiert sein Gehalt und flüstert weiter. Die Dritte addiert ihres und gibt es zurück. Die Erste zieht ihre Zufallszahl ab, und heraus kommt die Summe. Jedes Flüstern sah für den, der es hörte, wie eine Zufallszahl aus.
Sichere Aggregation: eine Summe (oder einen Durchschnitt) der Werte vieler Menschen berechnen, sodass kein einzelner Wert irgendwem verraten wird, auch nicht dem Server, der sie sammelt.
Additives Secret Sharing: eine geheime Zahl in mehrere Anteile zerschneiden, die für sich allein zufällig aussehen, sich aber zum Geheimnis addieren. Ein einzelner Anteil, oder jede Gruppe, der mindestens ein Anteil fehlt, verrät nichts über das Geheimnis.
Wie Anteile funktionieren
Um die Zahl 7.350 in drei Anteile zu teilen, wähl zwei Zufallszahlen und bestimm die dritte so, dass sich alle drei zu 7.350 addieren. Mit Arithmetik, die überläuft und von vorn beginnt (Modulus M, hier 2 hoch 32, etwas über 4 Milliarden), ist jeder Anteil für sich eine gleichverteilte Zufallszahl:
M = 2 ** 32
s1, s2 = 3919211450, 120775123 # random
s3 = (7350 - s1 - s2) % M # whatever makes it add up
print((s1 + s2 + s3) % M) # 7350
Warum überlaufen lassen? Ohne das wäre ein Anteil manchmal negativ oder verdächtig nah am Geheimnis. Mit Überlauf ist jeder Anteilswert gleich wahrscheinlich, egal was das Geheimnis ist, also trägt ein einzelner Anteil keine Information.
Viele Geräte, mehrere Server
Jetzt teilt jedes Handy seine Schrittzahl in einen Anteil pro Server und schickt Anteil 1 an Server 1, Anteil 2 an Server 2 und so weiter. Jeder Server addiert die Anteile, die er bekommen hat. Die Summe jedes Servers sieht immer noch zufällig aus. Erst wenn die Summen der Server zusammengezählt werden, erscheint die echte Stadtsumme. Solange die Server ihre rohen Anteile für ein Handy nicht zusammenlegen, wird der Wert keines Handys je gesehen.
Die Version in der echten Welt
Systeme, mit denen Modelle über viele Handys trainiert werden (bekannt als föderiertes Lernen), benutzen eine klügere Variante mit einem Server: Paare von Geräten einigen sich auf zufällige Masken, die sich aufheben, wenn alles addiert wird, plus zusätzliche Schritte für Handys, die mittendrin offline gehen. Die Kernidee ist die, die du baust: zufällig aussehende Stücke, die nur zusammen Sinn ergeben.
Was sichere Aggregation nicht tut
Die Summe wird exakt offengelegt. Haben nur zwei Menschen beigetragen und einer kennt seinen eigenen Wert, kann er ihn abziehen und den des anderen erfahren. Ist die Summe selbst sensibel, füg ihr zusätzlich Rauschen für Differential Privacy hinzu. Die zwei Werkzeuge passen gut zusammen: Aggregation versteckt die Eingaben, DP versteckt den Einfluss jeder Person auf die Ausgabe.
In anderen Sprachen
Teilen in JavaScript, mit 32-Bit-Überlauf über >>> 0 und der sicheren Zufallsquelle des Browsers:
function split(value, n) {
const shares = Array.from(crypto.getRandomValues(new Uint32Array(n - 1)));
const sum = shares.reduce((a, b) => (a + b) >>> 0, 0);
shares.push((value - sum) >>> 0);
return shares;
}Und in Rust, wo wrapping_sub auf einem u32 den Überlauf für dich erledigt:
let last = value.wrapping_sub(shares.iter().fold(0u32, |a, &b| a.wrapping_add(b)));Zusammenfassung
- Sichere Aggregation verrät eine Summe, aber keinen einzelnen Beitrag.
- Additives Secret Sharing teilt einen Wert in zufällig aussehende Anteile, die sich zu ihm addieren, mit überlaufender Arithmetik.
- Jeder Server sieht nur zufällig aussehende Anteile; nur alle Serversummen zusammen ergeben die Antwort.
- Die Summe selbst wird exakt verraten, also kombiniere sie mit DP-Rauschen, wenn die Summe jemanden bloßstellen könnte.
Schreibe drei Funktionen, unter Verwendung von M (2 to the 32) aus der Praxiswelt. split(value, n, rng) gibt eine list von n shares zurück: das erste n - 1 von rng.randrange(M), das letzte gleich (value - sum(shares)) % M. combine(shares) gibt sum(shares) % M zurück. aggregate(values, n_servers, rng) teilt jeden Wert mit split, fügt share j in server_totals[j] (mod M) hinzu und gibt ein tuple (total, server_totals) zurück, wo total = combine(server_totals).
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.