Kurrikulum Leson 133 van 156 · Privaatheidstegnologie verder as blokkeer
Privaatheidstegnologie verder as blokkeer

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));   // 4n

In 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 % en pow(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.