Die wiskunde wat jy nodig het
Waarom dit saak maak Die privaatheidstools in hierdie module, soos om gedeelde kliënte te vind sonder om lysse te ruil of statistieke te publiseer wat elke persoon beskerm, rus op drie klein stukke wiskunde. Jy het nie 'n wiskundegraad nodig nie. Jy het klok-aritmetika, 'n gevoel vir kans, en die idee dat willeke ruis in groot groepe uitkansel nodig. Hierdie les gee vir jou presies daardie dinge, met Python om dit te probeer.
1. Horlosie-aritmetika
Dit is 22:00. Hoe laat is dit 5 uur later? Nie 27:00 nie: die horlosie draai om, so dit is 03:00. Jy het 22 + 5 = 27 geneem en die res gehou nadat jy deur 24 gedeel het.
Modulêre rekenkunde: rekenkunde waar getalle ronddra nadat hulle 'n vaste grootte bereik, die modulus. "27 mod 24" is 3, die res nadat jy 27 deur 24 deel. In Python is die resoperator %: 27 % 24 is 3.
Wrapping hou nommers 'n vaste grootte, ongeag hoeveel jy byvoeg of vermenigvuldig. Dit is waarom dit nuttig is vir kriptografie. Python het ook 'n vinnige ingeboude funksie vir "verhoog tot 'n mag, dan wrap": 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. Maklik eenkant, moeilik die anderkant
Om geel en blou verf meng tot groen is maklik. Om groen terug te ontmeng tot die presiese geel en blou is byna onmoontlik. Sommige wiskunde werk op dieselfde manier.
Kies 'n groot priemmodulus en 'n getal P. Om h vir 'n geheim pow(h, a, P) te bereken is onmiddellik. Maar as jy net die antwoord het, is dit so stadig om a weer te vind vir groot genoeg getalle dat niemand dit kan doen nie. Hierdie eenweg-eienskap word die adiscrete logarithm problem genoem..
Nog een feit, en dit gee krag aan die volgende labs. Om te a en dan te b gee dieselfde resultaat as om te b en dan te a, omdat albei gelyk aan h tot die mag a maal 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
Soos twee slotte op een boks, maak die volgorde waarin jy dit byvoeg nie saak nie. Twee mense kan elk hul eie geheim byvoeg en by dieselfde plek uitkom sonder om hul geheime te verklik.
3. Waarskynlikheid in een paragraaf
A waarskynlikheid is 'n getal van 0 (nooit) tot 1 (altyd). 'n Regverdige munt land kopkant met 'n waarskynlikheid van 0.5. Wanneer twee dinge onafhanklik is, is die kans vir albei die produk: twee koppe op 'n ry is 0.5 x 0.5 = 0.25. Die expected value is die langtermyngemiddelde: gooi 'n regverdige dobbel baie keer en die gemiddelde nader 3.5.
4. Geraas vervaag in 'n skare
Noise: 'n willeke hoeveelheid wat doelbewus by 'n ware waarde gevoeg word, sodat die presiese waarde weggesteek word. As die noise net so waarskynlik is om op as af, gemiddeld uit tot nul oor baie waardes.
Hier is 'n klassieke opnametrukie genaamd randomised response. Jy wil weet hoeveel mense iets verleë het gedoen. Elke persoon gooi geheim 'n muntstuk. Kop: antwoord eerlik. Moker: gooi weer en antwoord "ja" vir kop en "nee" vir moker. Enige enkele "ja" kan net die muntstuk wees, so niemand se antwoord bewys iets oor hulle nie.
Maar die skare se totaal is steeds nuttig. As die ware breuk p is, is die breuk van "ja" antwoorde wat jy verwag 0.5 x p + 0.25. So as 35% ja sê, is p ongeveer (0.35 - 0.25) / 0.5 = 0.2, of 20%. Hoe groter die skare, hoe nader is die skatting, omdat willeke ruis relatief krimpt namate die skare groei.
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
Die geraas wat in differensiale privaatheid gebruik word, genaamd Laplace noise, is 'n gladde weergawe van dieselfde idee: gewoonlik klein, soms groter, en net so waarskynlik omop of af. Sy scale bepaal hoe groot dit gewoonlik is.
In ander tale
JavaScript se % werk dieselfde vir positiewe getalle, en groot getalle gebruik BigInt (geskryf met 'n n). Daar is geen ingeboude modulaire mag nie, so hier is die 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, new(big.Int).Exp(base, exp, mod) vanaf math/big doen dieselfde werk.
A algemene wanbeleefde
"Om geraas by te voeg maak die data nutteloos." Vir een persoon se waarde, ja, en dit is die punt. Vir 'n groot groep kanselleer die geraas grootliks, so totale en gemiddeltes bly nuttig. Privaatiese tegnologie leef in daardie gaping: vaag vir individue, skerp vir skare.
Opsomming
- Modulêre rekenkunde rondel getalle rondom 'n modulus; Python gebruik
%enpow(b, e, m). - Omhoog te verhef na 'n geheime mag is maklik eenkant en byna onmoontlik om ongedoen te maak, en die volgorde van twee geheime magte maak nie saak nie.
- Onhafhanklike kanses vermenigvuldig; die verwagting is die langtermyngemiddelde.
- Willeke geraas verberg individue maar kanselleer in groot groepe, dit is hoe randomised response werk.
Sien jy 'n probleem in hierdie les? Rapporteer dit · Vra oor hierdie les
Hierdie oefening open binnekort
Voltooi die lesie voor dit en hierdie een sal ontvanklik wees. Die hele kursus is gratis, geen rekening nodig nie, en jy kan hierdie les nou lees.
Hierdie blutser blokkeer koekies vir learn.floati.life, so lesse wat jy hier voltooi het kan nie in volgorde oopgaan nie. Laat koekies vir hierdie webwerf toe en laai nuut.