Lehrplan Lektion 133 von 156 · Privatsphäre-Technologie über das Blockieren hinaus
Privatsphäre-Technologie über das Blockieren hinaus

Die Mathematik, die du brauchst

Warum das wichtig ist Die Datenschutz-Tools in diesem Modul, wie das Finden gemeinsamer Kunden ohne Listen zu tauschen oder das Veröffentlichen von Statistiken, die jede Person schützen, basieren auf drei kleinen Stücken Mathematik. Du brauchst keinen Mathematik-Abschluss. Du brauchst Uhrzeit-Arithmetik, ein Gefühl für Zufall und die Idee, dass zufälliges Rauschen in großen Gruppen wegfällt. Diese Lektion gibt dir genau das, mit Python zum Ausprobieren.

1. Uhrarithmetik

Es ist 22:00 Uhr. Wie spät ist es 5 Stunden später? Nicht 27:00: die Uhr schlägt um, also ist es 03:00 Uhr. Du hast 22 + 5 = 27 genommen und den Rest nach der Teilung durch 24 behalten.

Modulare Arithmetik: Arithmetik, bei der Zahlen nach Erreichen einer festen Größe um den Modulus herumspringen. "27 mod 24" ist 3, der Rest nach der Division von 27 durch 24. In Python ist der Restoperator %: 27 % 24 ist 3.

Wrapping hält Zahlen eine feste Größe, egal wie viel du addierst oder multiplizierst, was es für Kryptographie nützlich macht. Python hat auch eine schnelle eingebaute Funktion für "hoch rechnen, dann wrappen": pow(base, exponent, modulus).

print((22 + 5) % 24)       # 3
print(pow(3, 4, 7))        # 3*3*3*3 = 81, and 81 % 7 = 4
print(pow(5, 200, 23))     # instant, even though 5 to the 200 is huge

2. Einfach in eine Richtung, schwer in die andere

Gelb und Blau zu Grün zu mischen ist einfach. Grün wieder in das exakte Gelb und Blau zu entmischen ist praktisch unmöglich. Manche Mathematik funktioniert genauso.

Wähle einen großen Primzahlmodul P und eine Zahl h. Die Berechnung von pow(h, a, P) für ein Geheimnis a ist sofort erledigt. Aber wenn man nur die Antwort hat, ist das erneute Finden von a für ausreichend große Zahlen so langsam, dass niemand es tun kann. Diese Einweg-Eigenschaft wird als discrete logarithm problem genannt.

Noch eine Tatsache, und sie treibt die nächsten Labs an. Das Erhöhen auf a und dann auf b gibt das gleiche Ergebnis wie das Erhöhen auf b und dann auf a, weil beide gleich h hoch a mal b:

sind.
P = 1019                     # a small prime: fine for learning, useless for security
h, a, b = 42, 123, 456
print(pow(pow(h, a, P), b, P) == pow(pow(h, b, P), a, P))    # True

Wie zwei Schlösser an einer Kiste spielt die Reihenfolge, in der du sie anbringst, keine Rolle. Zwei Personen können jeweils ihr eigenes Geheimnis hinzufügen und am selben Ziel ankommen, ohne jemals ihre Geheimnisse zu verraten.

3. Wahrscheinlichkeit in einem Absatz

A Wahrscheinlichkeit ist eine Zahl von 0 (nie) bis 1 (immer). Eine faire Münze landet mit einer Wahrscheinlichkeit von 0.5 auf Kopf. Wenn zwei Dinge unabhängig sind, ist die Chance für beides das Produkt: zwei Köpfe hintereinander sind 0.5 x 0.5 = 0.25. Der expected value ist der langfristige Durchschnitt: würfle einen fairen Würfel viele Male und der Durchschnitt nähert sich 3.5 an.

4. Rauschen wird in einer Menge ausgeblendet

Noise: ein zufälliger Betrag, der absichtlich zu einem wahren Wert hinzugefügt wird, damit der exakte Wert verborgen bleibt. Wenn das Noise genauso wahrscheinlich nach oben wie nach unten ist, gleicht es sich über viele Werte auf Null aus.

Hier ist ein klassischer Umfragetrick namens randomised response. Du willst wissen, wie viele Leute etwas Peinliches getan haben. Jede Person wirft heimlich eine Münze. Kopf: antworte wahrheitsgemäß. Zahl: wirf erneut und antworte bei Kopf mit "ja" und bei Zahl mit "nein". Jedes einzelne "ja" könnte nur die Münze sein, also beweist die Antwort von niemandem etwas über sie.

Doch die Gesamtsumme der Menge ist immer noch nützlich. Wenn der wahre Anteil p ist, ist der Anteil der "ja" Antworten, den du erwartest, 0.5 x p + 0.25. Wenn also 35% ja sagen, ist p etwa (0.35 - 0.25) / 0.5 = 0.2, oder 20%. Je größer die Menge ist, desto näher liegt die Schätzung, weil das zufällige Rauschen im Verhältnis zur Gesamtsumme schrumpft, während die Menge wächst.

import random
rng = random.Random(1)               # seeded: the same "random" numbers every run
truth = [rng.random() < 0.2 for _ in range(10000)]   # 20% really did it
answers = []
for did_it in truth:
    if rng.random() < 0.5:
        answers.append(did_it)             # heads: tell the truth
    else:
        answers.append(rng.random() < 0.5) # tails: random yes or no
yes = sum(answers) / len(answers)
print(round((yes - 0.25) / 0.5, 3))       # close to 0.2

Das Rauschen, das in Differential Privacy verwendet wird, genannt Laplace noise, ist eine glatte Version derselben Idee: meist klein, gelegentlich größer, gleich wahrscheinlich nach oben oder unten. Sein scale legt fest, wie groß es typischerweise ist.

In anderen Sprachen

JavaScripts % funktioniert für positive Zahlen genauso, und große Zahlen nutzen BigInt (geschrieben mit einem n). Es gibt keine eingebaute modulare Potenz, also ist hier die Standard-Schleife:

function powMod(base, exp, mod) {
  let result = 1n;
  base %= mod;
  while (exp > 0n) {
    if (exp & 1n) result = (result * base) % mod;
    base = (base * base) % mod;
    exp >>= 1n;
  }
  return result;
}
console.log(powMod(3n, 4n, 7n));   // 4n

In Go macht new(big.Int).Exp(base, exp, mod) von math/big den gleichen Job.

Ein häufiges Missverständnis

"Das Hinzufügen von Rauschen macht die Daten nutzlos." Für den Wert einer Person, ja, und das ist der Punkt. Für eine große Gruppe hebt sich das Rauschen weitgehend auf, also bleiben Summen und Durchschnitte nützlich. Privatsphäre-Technologie lebt in dieser Lücke: unscharf für Individuen, scharf für Menschenmengen.

Zusammenfassung

  • Modulare Arithmetik rundet Zahlen an einen Modulus; Python verwendet % und pow(b, e, m).
  • Das Erhöhen auf eine geheime Potenz ist auf eine Weise einfach und praktisch unmöglich rückgängig zu machen, und die Reihenfolge von zwei geheimen Potenzen spielt keine Rolle.
  • Unabhängige Chancen multiplizieren sich; der Erwartungswert ist der Durchschnitt auf lange Sicht.
  • Zufälliges Rauschen verbirgt Einzelpersonen, wird aber in großen Gruppen ausgeglichen, so funktioniert die randomisierte Antwort.

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.