De wiskunde die je nodig hebt
Waarom dit ertoe doet De privacytools in deze module, zoals het vinden van gedeelde klanten zonder lijsten uit te wisselen of statistieken te publiceren die elke persoon beschermen, rusten op drie kleine stukjes wiskunde. Je hebt geen wiskundegraad nodig. Je hebt klokrekening nodig, een gevoel voor kans en het idee dat willekeurige ruis wegvalt in grote groepen. Deze les geeft je precies die zaken, met Python om het te proberen.
1. Klokrekenen
Het is 22:00. Hoe laat is het 5 uur later? Niet 27:00: de klok slaat om, dus het is 03:00. Je nam 22 + 5 = 27 en hield de rest over na deling door 24.
Modulaire rekenkunde: rekenkunde waarbij getallen rondgaan na het bereiken van een vaste grootte, de modulus. "27 mod 24" is 3, de rest na het delen van 27 door 24. In Python is de restoperator %: 27 % 24 is 3.
Wrapping houdt getallen een vaste grootte, hoeveel je ook optelt of vermenigvuldigt, wat het nuttig maakt voor cryptografie. Python heeft ook een snelle ingebouwde voor "verheffen tot een macht, dan 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. Makkelijk de ene kant op, moeilijk de andere kant op
Het mengen van gele en blauwe verf tot groen is makkelijk. Het ontmengen van groen terug naar de exacte gele en blauwe kleur is praktisch onmogelijk. Sommige wiskunde werkt op dezelfde manier.
Kies een grote priemgetal modulus P en een getal h. Het berekenen van pow(h, a, P) voor een geheim a is onmiddellijk. Maar gegeven alleen het antwoord, is het opnieuw vinden van a zo traag voor grote genoeg getallen dat niemand het kan doen. Deze eenrichtings eigenschap wordt het discrete logarithm probleem genoemd.
Nog een feit, en het voedt de volgende labs. Verheffen naar a en dan naar b geeft hetzelfde resultaat als verheffen naar b en dan naar a, omdat beide gelijk zijn aan h tot de macht a keer b:
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
Net als twee sloten op één kist, maakt de volgorde waarin je ze plaatst niet uit. Twee mensen kunnen elk hun eigen geheim toevoegen en eindigen op dezelfde plek zonder hun geheimen ooit te onthullen.
3. Kansberekening in één alinea
A waarschijnlijkheid is een getal van 0 (nooit) tot 1 (altijd). Een eerlijke munt landt op kop met een waarschijnlijkheid van 0.5. Wanneer twee dingen onafhankelijk zijn, is de kans op beide het product: twee keer achter elkaar kop is 0.5 x 0.5 = 0.25. De expected value is het gemiddelde op de lange termijn: gooi een eerlijke dobbelsteen vaak en het gemiddelde nadert 3.5.
4. Ruis valt weg in een menigte
Noise: een willekeurige hoeveelheid die expres wordt toegevoegd aan een ware waarde, zodat de exacte waarde verborgen is. Als de noise even waarschijnlijk omhoog als omlaag is, middelt het uit naar nul over veel waarden.
Hier is een klassieke enquêtetruc genaamd randomised response. Je wilt weten hoeveel mensen iets gênants hebben gedaan. Iedereen gooit in het geheim een munt. Kop: antwoord eerlijk. Munt: gooi opnieuw en antwoord "ja" voor kop en "nee" voor munt. Elke individuele "ja" kan gewoon door de munt komen, dus het antwoord van niemand bewijst iets over hen.
Toch is het totaal van de menigte nog steeds nuttig. Als de ware fractie p is, is de fractie "ja" antwoorden die je verwacht 0.5 x p + 0.25. Dus als 35% ja zegt, is p ongeveer (0.35 - 0.25) / 0.5 = 0.2, of 20%. Hoe groter de menigte, hoe dichter het schatting, omdat willekeurige ruis krimpt ten opzichte van het totaal naarmate de menigte groeit.
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
De ruis die wordt gebruikt in differential privacy, genaamd Laplace noise, is een vloeiende versie van hetzelfde idee: meestal klein, soms groter, even waarschijnlijk omhoog of omlaag. De scale bepaalt hoe groot het meestal is.
In andere talen
JavaScript's % werkt op dezelfde manier voor positieve getallen, en grote getallen gebruiken BigInt (geschreven met een n). Er is geen ingebouwde modulaire macht, dus hier is de standaard loop:
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)); // 4nIn Go doet new(big.Int).Exp(base, exp, mod) van math/big hetzelfde werk.
A veelvoorkomende misvatting
"Het toevoegen van ruis maakt de data nutteloos." Voor de waarde van één persoon, ja, en dat is de bedoeling. Voor een grote groep valt de ruis grotendeels weg, dus totalen en gemiddelden blijven nuttig. Privacy techniek leeft in die kloof: wazig voor individuen, scherp voor menigten.
Samenvatting
- Modulaire rekenkunde rondt getallen af naar een modulus; Python gebruikt
%enpow(b, e, m). - Verheffen tot een geheime macht is op de ene manier eenvoudig en praktisch onmogelijk om ongedaan te maken, en de volgorde van twee geheime machten doet er niet toe.
- Onafhankelijke kansen vermenigvuldigen; de verwachtingswaarde is het gemiddelde op de lange termijn.
- Willekeurige ruis verbergt individuen maar valt weg in grote groepen, dat is hoe randomised response werkt.
Een probleem ontdekt in deze les? Meld het · Vraag naar deze les
Deze oefening opent binnenkort
Maak de les ervoor af voordat deze wordt ontgrendeld. De hele cursus is gratis, geen account nodig, en je kunt deze les nu lezen.
Deze browser blokkeert cookies voor learn.floati.life, dus lessen die je hier hebt afgerond kunnen niet in de juiste volgorde worden geopend. Sta cookies toe voor deze site en laad de pagina opnieuw.