Aggregazione sicura
Perché è importante Un'app di fitness vuole il totale dei passi fatti in una città; un produttore di tastiere vuole sapere quanto spesso una parola viene scritta su tutti i telefoni. In ogni caso l'azienda ha bisogno di un solo numero da molti dispositivi. L'aggregazione sicura le permette di scoprire quel totale senza mai vedere il valore di una singola persona, ed è sorprendentemente semplice.
Crittografia didattica, non sicura: i numeri nei laboratori di questo modulo sono abbastanza piccoli da leggere e la casualità usa un seme fisso così la correzione è ripetibile. I sistemi veri usano librerie verificate e numeri molto più grandi. Non copiare mai codice didattico in un prodotto.
Il trucco dello stipendio
Tre amici vogliono il loro stipendio medio senza che nessuno riveli il proprio. La prima aggiunge un grande numero casuale al suo stipendio e sussurra il risultato al secondo. Lui aggiunge il suo stipendio e sussurra avanti. La terza aggiunge il suo e lo passa indietro. La prima sottrae il suo numero casuale, ed ecco il totale. Ogni sussurro sembrava un numero casuale a chi lo sentiva.
Aggregazione sicura: calcolare un totale (o una media) dei valori di molte persone in modo che nessun singolo valore venga rivelato a nessuno, compreso il server che li raccoglie.
Condivisione additiva del segreto: tagliare un numero segreto in più quote che da sole sembrano casuali ma sommate danno il segreto. Una qualsiasi quota, o qualsiasi gruppo a cui manca almeno una quota, non rivela niente del segreto.
Come funzionano le quote
Per dividere il numero 7,350 in tre quote, scegli due numeri casuali e scegli il terzo in modo che tutti e tre sommati diano 7,350. Con l'aritmetica che ricomincia il giro (modulo M, qui 2 alla 32, poco più di 4 miliardi), ogni quota da sola è un numero casuale uniforme:
M = 2 ** 32
s1, s2 = 3919211450, 120775123 # random
s3 = (7350 - s1 - s2) % M # whatever makes it add up
print((s1 + s2 + s3) % M) # 7350
Perché ricominciare il giro? Senza, una quota a volte sarebbe negativa o sospettosamente vicina al segreto. Con, ogni valore di quota ha la stessa probabilità qualunque sia il segreto, quindi una singola quota non porta nessuna informazione.
Molti dispositivi, più server
Ora ogni telefono divide il proprio conteggio dei passi in una quota per server e invia la quota 1 al server 1, la quota 2 al server 2, e così via. Ogni server somma le quote che ha ricevuto. Il totale di ogni server sembra ancora casuale. Solo quando i totali dei server vengono sommati compare il vero totale della città. Finché i server non mettono insieme le quote grezze di uno stesso telefono, il valore di nessun telefono viene mai visto.
La versione del mondo reale
I sistemi usati per addestrare modelli su molti telefoni (noti come apprendimento federato) usano una variante più ingegnosa con un solo server: coppie di dispositivi si accordano su maschere casuali che si annullano quando tutto viene sommato, più passi extra per gestire i telefoni che vanno offline a metà. L'idea di fondo è quella che costruirai: pezzi dall'aspetto casuale che hanno senso solo insieme.
Che cosa non fa l'aggregazione sicura
Il totale viene rivelato esattamente. Se hanno contribuito solo due persone e una conosce il proprio valore, può sottrarlo e scoprire quello dell'altra. Se il totale stesso è delicato, aggiungigli anche rumore di privacy differenziale. I due strumenti funzionano bene insieme: l'aggregazione nasconde gli input, la DP nasconde l'effetto di ogni persona sul risultato.
In altri linguaggi
La divisione in JavaScript, usando il giro a 32 bit con >>> 0 e la fonte casuale sicura del browser:
function split(value, n) {
const shares = Array.from(crypto.getRandomValues(new Uint32Array(n - 1)));
const sum = shares.reduce((a, b) => (a + b) >>> 0, 0);
shares.push((value - sum) >>> 0);
return shares;
}E in Rust, dove wrapping_sub su un u32 fa il giro al posto tuo:
let last = value.wrapping_sub(shares.iter().fold(0u32, |a, &b| a.wrapping_add(b)));Riepilogo
- L'aggregazione sicura rivela un totale ma nessun singolo contributo.
- La condivisione additiva del segreto divide un valore in quote dall'aspetto casuale che sommate lo ricompongono, usando l'aritmetica che ricomincia il giro.
- Ogni server vede solo quote dall'aspetto casuale; solo tutti i totali dei server insieme danno la risposta.
- Il totale stesso viene rivelato esattamente, quindi abbinalo al rumore DP quando il totale potrebbe esporre qualcuno.
Scrivi tre funzioni, usando M (2 alla 32) dal mondo di prova. split(value, n, rng) restituisce una lista di n quote: le prime n - 1 da rng.randrange(M), l'ultima uguale a (value - sum(shares)) % M. combine(shares) restituisce sum(shares) % M. aggregate(values, n_servers, rng) divide ogni valore con split, aggiunge la quota j a server_totals[j] (mod M), e restituisce una tupla (total, server_totals) dove total = combine(server_totals).
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.