La matematica che ti serve
Perché è importante Gli strumenti per la privacy di questo modulo, come trovare i clienti in comune senza scambiarsi le liste o pubblicare statistiche che proteggono ogni persona, si basano su tre piccoli pezzi di matematica. Non ti serve una laurea in matematica. Ti servono l'aritmetica dell'orologio, un'idea del caso, e il concetto che il rumore casuale si annulla nei grandi gruppi. Questa lezione ti dà esattamente questo, con Python da provare.
1. L'aritmetica dell'orologio
Sono le 22:00. Che ore sono 5 ore dopo? Non le 27:00: l'orologio ricomincia il giro, quindi sono le 03:00. Hai fatto 22 + 5 = 27 e hai tenuto il resto della divisione per 24.
Aritmetica modulare: un'aritmetica in cui i numeri ricominciano il giro dopo aver raggiunto una grandezza fissa, il modulo. "27 mod 24" fa 3, il resto della divisione di 27 per 24. In Python l'operatore del resto è %: 27 % 24 fa 3.
Ricominciare il giro tiene i numeri di grandezza fissa per quanto tu sommi o moltiplichi, ed è questo che la rende utile per la crittografia. Python ha anche una funzione integrata veloce per "eleva a potenza, poi ricomincia il giro": 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. Facile in un verso, difficile nell'altro
Mescolare vernice gialla e blu per fare il verde è facile. Separare il verde di nuovo nell'esatto giallo e blu è praticamente impossibile. Una parte della matematica funziona allo stesso modo.
Scegli un grande modulo primo P e un numero h. Calcolare pow(h, a, P) per un a segreto è immediato. Ma avendo solo il risultato, ritrovare a è così lento con numeri abbastanza grandi che nessuno ci riesce. Questa proprietà a senso unico si chiama problema del logaritmo discreto.
Un altro fatto, ed è quello che fa funzionare i prossimi laboratori. Elevare ad a e poi a b dà lo stesso risultato che elevare a b e poi ad a, perché entrambi sono uguali a h elevato ad a per 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
Come due lucchetti su una scatola, l'ordine in cui li metti non conta. Due persone possono aggiungere ciascuna il proprio segreto e arrivare allo stesso punto senza mai rivelare i propri segreti.
3. La probabilità in un paragrafo
Una probabilità è un numero da 0 (mai) a 1 (sempre). Una moneta equa esce testa con probabilità 0.5. Quando due cose sono indipendenti, la probabilità che succedano entrambe è il prodotto: due teste di fila è 0.5 × 0.5 = 0.25. Il valore atteso è la media sul lungo periodo: lancia molte volte un dado equo e la media si avvicina a 3.5.
4. Il rumore si annulla nella folla
Rumore: una quantità casuale aggiunta di proposito a un valore vero, così il valore esatto resta nascosto. Se il rumore ha la stessa probabilità di andare su o giù, su molti valori si annulla in media.
Ecco un classico trucco dei sondaggi chiamato risposta randomizzata. Vuoi sapere quante persone hanno fatto qualcosa di imbarazzante. Ogni persona lancia in segreto una moneta. Testa: risponde sinceramente. Croce: lancia di nuovo e risponde "sì" se esce testa e "no" se esce croce. Qualsiasi "sì" potrebbe venire solo dalla moneta, quindi la risposta di nessuno prova niente su di lui.
Eppure il totale della folla resta utile. Se la frazione vera è p, la frazione di risposte "sì" che ti aspetti è 0.5 x p + 0.25. Quindi se il 35% dice sì, p vale circa (0.35 - 0.25) / 0.5 = 0.2, cioè il 20%. Più grande è la folla, più la stima è vicina, perché il rumore casuale si riduce rispetto al totale man mano che la folla cresce.
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
Il rumore usato nella privacy differenziale, chiamato rumore di Laplace, è una versione morbida della stessa idea: di solito piccolo, a volte più grande, con la stessa probabilità di andare su o giù. La sua scala stabilisce quanto è grande di solito.
In altri linguaggi
Il % di JavaScript funziona allo stesso modo con i numeri positivi, e i numeri grandi usano BigInt (scritti con una n). Non c'è una potenza modulare integrata, quindi ecco il ciclo standard:
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) da math/big fa lo stesso lavoro.
Un equivoco comune
"Aggiungere rumore rende i dati inutili." Per il valore di una sola persona sì, ed è proprio questo lo scopo. Per un grande gruppo il rumore si annulla in buona parte, quindi totali e medie restano utili. Le tecnologie per la privacy vivono in quello spazio: sfocate per gli individui, nitide per le folle.
Riepilogo
- L'aritmetica modulare fa ricominciare il giro ai numeri attorno a un modulo; Python usa
%epow(b, e, m). - Elevare a una potenza segreta è facile in un verso e praticamente impossibile da annullare, e l'ordine di due potenze segrete non conta.
- Le probabilità indipendenti si moltiplicano; il valore atteso è la media sul lungo periodo.
- Il rumore casuale nasconde gli individui ma si annulla nei grandi gruppi, ed è così che funziona la risposta randomizzata.
Hai notato un problema in questa lezione? Segnalalo · Chiedi qualcosa su questa lezione
Questo esercizio si apre presto
Finisci la lezione precedente e questa si sblocca. L'intero corso è gratuito, senza account, e puoi leggere questa lezione subito.
Questo browser blocca i cookie per learn.floati.life, quindi le lezioni che hai finito qui non si possono aprire in ordine. Consenti i cookie per questo sito e ricarica.