La privacy differenziale è balzata dai documenti di ricerca ai titoli delle notizie tecnologiche l’anno scorso quando, nel keynote WWDC, il VP di Apple di ingegneria Craig Federighi ha annunciato l’uso di Apple del concetto per proteggere la privacy degli utenti in iOS.

E ‘ stato l’ultimo esempio di una tendenza generale: gli utenti e gli ingegneri risveglio all’importanza della protezione della privacy nel software. Violazioni della privacy di alto profilo come la “modalità Dio” di Uber hanno dimostrato in termini severi la facilità con cui i dipendenti di un’azienda possono abusare dei dati sensibili raccolti dai loro clienti.

La quantità di dati sensibili che viene registrata digitalmente sta rapidamente aumentando. Le persone ora si affidano ai servizi digitali per più dei loro pagamenti, trasporti, navigazione, shopping e salute che mai. Questa nuova raccolta di dati crea sempre più modi per violare la privacy.

Ma crea anche interessanti opportunità—per migliorare le reti di trasporto, per ridurre la criminalità, per curare le malattie—se messi a disposizione dei dati giusti scienziati e ricercatori. C’è una tensione naturale tra la protezione della privacy degli individui nel set di dati e l’abilitazione di analisi che potrebbero portare a un mondo migliore.

Gli algoritmi differenzialmente privati sono una soluzione tecnica promettente che potrebbe alleviare questa tensione, consentendo agli analisti di eseguire analisi aggregate benigne garantendo al contempo una protezione significativa della privacy di ogni individuo.

Questo campo di sviluppo della tecnologia vale la pena considerare in qualsiasi sistema che cerca di analizzare i dati sensibili. Sebbene la garanzia di privacy differenziale sia stata concepita solo dieci anni fa, ha avuto successo nel mondo accademico e nell’industria. I ricercatori stanno rapidamente inventando e migliorando algoritmi differenzialmente privati, alcuni dei quali sono stati adottati sia in iOS di Apple e Chrome di Google.

Questo articolo discute i fattori storici che portano alla privacy differenziale nella sua forma attuale, insieme a una definizione di privacy differenziale e ad esempio algoritmi differenzialmente privati. Esamina quindi alcune recenti implementazioni di alto profilo di algoritmi differenzialmente privati di Google, Apple e altri.

Background

Gli algoritmi differenzialmente privati sono l’ultimo di un campo di tecnologie pluridecennale per l’analisi dei dati che preserva la privacy. Due concetti precedenti influenzavano direttamente la privacy differenziale:

1. Dimensione minima del set di query
2. Definizione di divulgazione statistica di Dalenius.

Spiegheremo questi primi in quanto forniscono uno sfondo utile per la privacy differenziale.

Dimensione minima del set di query Il primo concetto è una dimensione minima del set di query, che—come gli algoritmi differenzialmente privati—mira a garantire la sicurezza delle query aggregate. Le query aggregate sono quelle in cui il valore restituito viene calcolato in un sottoinsieme di record nel set di dati, ad esempio conteggi, medie o somme. Può essere utile pensare alle query aggregate come query SQL che iniziano con ” SELEZIONA SOMMA”, “SELEZIONA CONTEGGIO”o “SELEZIONA AVG”. Altri tipi di query aggregate includono tabelle di contingenza e istogrammi.

Una dimensione minima del set di query è un vincolo che cerca di garantire che le query aggregate non possano perdere informazioni sugli individui. Dato un certo numero di soglia configurato T, assicura che ogni query aggregata sia condotta su un insieme di almeno T record. Una dimensione minima del set di query bloccherebbe le query aggregate mirate a meno di individui T. Ad esempio, se T=2, bloccherebbe quanto segue:

“SELECT AVG(salary) WHERE name = ‘Troy Brown’;”.

perché questa query condurrebbe una media su un record (supponiamo che ci sia solo un Troy Brown).

L’utilizzo delle dimensioni minime del set di query impedisce determinati attacchi, ma non viene fornito con una garanzia di privacy e, in pratica, può essere aggirato da aggressori esperti. Ad esempio, l’attaccante potrebbe eseguire l’attacco sopra con:

“SELEZIONA SOMMA(stipendio);”.

“SELEZIONA SOMMA (stipendio) DOVE nome != ‘Troy Brown’;”.

O anche, se conosciamo l’età di Troy Brown (45) e la posizione(WR) lo identificano in modo univoco:

“SELEZIONA SUM (salary) WHERE position = ‘WR’;”.

“SELEZIONA SOMMA (stipendio) DOVE posizione = ‘WR’ ED età != 45;

Tali attacchi sono chiamati attacchi tracker e non possono essere fermati da un vincolo di dimensione minima del set di query. A causa di questi attacchi, le dimensioni minime dei set di query sono state ritenute una difesa inadeguata per proteggere i sistemi di query (vedere il lavoro di Denning). Qualcosa di meglio, con una garanzia, era necessario per garantire la privacy.

Definizione di divulgazione statistica di Dalenius

Nel 1977, lo statistico Tore Dalenius propose una definizione rigorosa della privacy dei dati: che l’attaccante non dovrebbe imparare nulla su un individuo che non conoscesse prima di utilizzare il set di dati sensibili. Anche se questa garanzia non è riuscita (e vedremo perché), è importante capire perché la privacy differenziale è costruita così com’è.

La definizione di Dalenius fallì perché, nel 2006, l’informatica Cynthia Dwork dimostrò che questa garanzia era impossibile da dare—in altre parole, qualsiasi accesso a dati sensibili violerebbe questa definizione di privacy. Il problema che ha trovato era che certi tipi di informazioni di base potrebbero sempre portare a una nuova conclusione su un individuo. La sua prova è illustrata nel seguente aneddoto: So che Alice è due pollici più alto della donna media lituana. Poi interagisco con un set di dati di donne lituane e calcolo l’altezza media, che non conoscevo prima. Ora conosco esattamente l’altezza di Alice, anche se non era nel set di dati. È impossibile tenere conto di tutti i tipi di informazioni di base che potrebbero portare a una nuova conclusione su un individuo dall’uso di un set di dati.

Dwork, dopo aver provato quanto sopra, ha proposto una nuova definizione: privacy differenziale.

Che cos’è la privacy differenziale?

La privacy differenziale garantisce quanto segue: che l’attaccante non può imparare praticamente nulla di più su un individuo di quanto imparerebbe se il record di quella persona fosse assente dal set di dati. Mentre più debole della definizione di privacy di Dalenius, la garanzia è abbastanza forte perché si allinea con gli incentivi del mondo reale—gli individui non hanno alcun incentivo a non partecipare a un set di dati, perché gli analisti di quel set di dati trarranno le stesse conclusioni su quell’individuo se l’individuo si include nel set di dati o meno. Poiché le loro informazioni personali sensibili sono quasi irrilevanti negli output del sistema, gli utenti possono essere certi che l’organizzazione che gestisce i loro dati non sta violando la loro privacy.

Gli analisti che imparano “praticamente nulla di più su un individuo” significa che sono limitati a un cambiamento insignificante nella credenza su qualsiasi individuo. (Qui e sotto, “modifica” si riferisce alla modifica tra l’utilizzo di un set di dati e l’utilizzo dello stesso set di dati meno il record di una persona.) L’entità di questa modifica è controllata da un parametro noto come ϵ, che imposta il limite sulla variazione della probabilità di qualsiasi risultato. Un valore basso di ϵ, come 0.1, significa che molto poco può cambiare nelle credenze su qualsiasi individuo. Un alto valore di ϵ, come 50, significa che le credenze possono cambiare sostanzialmente di più. La definizione formale è la seguente.

Un algoritmo A è differ-differenzialmente privato se e solo se:

Pr ≤ e^ * * Pr

per tutte le x e per tutte le coppie di set di dati D, D’ dove D’ è D con qualsiasi record—cioè i dati di una persona—mancante. Il simbolo e si riferisce alla costante matematica. Si noti che questa definizione ha senso solo per algoritmi randomizzati. Un algoritmo che fornisce un output deterministico non è un candidato per la privacy differenziale.

L’appello principale della garanzia privacy differenziale è la sua limitazione sulla quantità che ogni analista può conoscere un individuo. Inoltre, ha le seguenti proprietà utili:

• Composability: se a due query viene data risposta con garanzie di privacy differenziali di livello ϵ1 e ϵ2, la coppia di query è coperta da una garanzia di livello (ϵ1 + ϵ2). Ricordiamo che un valore più alto di ϵ significa una garanzia più debole.
• Forza contro informazioni di base arbitrarie: la garanzia non si basa in alcun modo su quali informazioni di base conosce l’attaccante. Questa proprietà è uno dei motivi principali per cui la privacy differenziale è più forte di una precedente garanzia di privacy, k-anonimato.
• Sicurezza in fase di post-elaborazione: non ci sono restrizioni su ciò che può essere fatto con un risultato differentemente privato – non importa con cosa è combinato o come viene trasformato, è ancora differentemente privato.

Come si ottiene questa garanzia nel software? Gli algoritmi differenzialmente privati sono algoritmi randomizzati che aggiungono rumore nei punti chiave all’interno dell’algoritmo. Uno degli algoritmi più semplici è il meccanismo di Laplace, che può post-elaborare i risultati delle query aggregate (ad esempio, conteggi, somme e mezzi) per renderli differenzialmente privati. Di seguito è riportato un esempio di codice Java per il meccanismo di Laplace specifico per contare le query:

import org.apache.commons.math3.distribution.LaplaceDistribution;double laplaceMechanismCount(long realCountResult, double epsilon) { LaplaceDistribution ld = new LaplaceDistribution(0, 1 / epsilon); double noise = ld.sample(); return realCountResult + noise;}

Le parti chiave di questa funzione sono

1. Istanziare una distribuzione di probabilità di Laplace (vedi Figura 1) centrata a 0 e ridimensionata di 1 / ϵ. Usiamo l’implementazione di Apache Commons, “LaplaceDistribution”, che è costruita con due argomenti: la media della distribuzione e la scala della distribuzione. Si noti che epsilon inferiore (più privacy) porta ad una scala più ampia e quindi una distribuzione più ampia e più rumore.
2. Disegna un campione casuale da questa distribuzione. Questa funzione sample () prende un numero casuale compreso tra 0 e 1 e applica la funzione di distribuzione cumulativa inversa (CDF) della distribuzione di Laplace a questo numero. Questo processo si traduce in un numero casuale tale che la sua probabilità di essere qualsiasi valore specifico corrisponde alla distribuzione. Come modo alternativo di pensarci, se questa funzione di esempio fosse invocata un milione di volte per ottenere un milione di campioni, la forma dell’istogramma di questi campioni corrisponderebbe strettamente alla forma della distribuzione di Laplace.
3. Perturbare il valore reale aggiungendo il valore casuale dal passaggio 2.

Consideriamo perché questo algoritmo è differenzialmente privato prendendo il punto di vista di un attaccante di nome Eve. Diciamo che il set di dati è dati di salute mentale, e Eve ha concepito un attacco tracker (vedi sopra) che rivelerà se il suo obiettivo, Bob, riceve consulenza per l’alcolismo o meno. Se il risultato della query è 48, Eve sa che Bob riceve consulenza; se è 47, Eve sa il contrario.

Se la risposta è 47 o 48, il meccanismo di Laplace restituirà un risultato rumoroso da qualche parte intorno a 47 o 48. Può restituire 49, 46, o anche, con minore probabilità, 44 o 51 (vedi Figura 2 per un istogramma). In pratica, è impossibile per Eva essere molto sicura se la vera risposta fosse 47 o 48 e, quindi, le sue convinzioni sul fatto che Bob sia in terapia per l’alcolismo o ora non cambieranno in modo significativo.

Figura 1: La distribuzione di Laplace centrata su 0 con scala di 1. Nella foto è la funzione di densità di probabilità (PDF) della distribuzione—l’asse y è la probabilità relativa che la variabile assumerà il valore sull’asse x.

Figura 2: I probabili risultati della query di conteggio per i due scenari, dove la risposta reale è 47 e quando è 48. Un piccolo numero di output non sarebbe sufficiente per distinguere da quale distribuzione provengano. Epsilon è impostato su 0.67.

Potresti aver osservato a questo punto che Eve potrebbe tagliare il rumore ripetendo la query molte volte e vedere se le risposte si raggruppano intorno a 47 o 48. Per evitare questa tattica, i sistemi differenzialmente privati devono avere un “budget per la privacy”, un limite alla somma degli ϵ utilizzati in ogni query. Questo tappo funziona a causa della proprietà composability differential privacy descritta sopra. Possono chiedere alcune query relativamente a basso rumore o molte centinaia di query ad alto rumore, ma in entrambi i casi, non saranno in grado di stabilire con sicurezza se la vera risposta è 47 o 48.

Infine, si noti che il meccanismo di Laplace per i conteggi è semplicemente un semplice algoritmo differenzialmente privato. Il meccanismo di Laplace può essere esteso per lavorare per somme e altre query aggregate. Inoltre, esistono algoritmi fondamentalmente diversi che hanno dimostrato di soddisfare la garanzia di privacy differenziale. Alcuni vale la pena esplorare sono l’algoritmo Pesi moltiplicativi privati, il meccanismo esponenziale pesi moltiplicativi, e DualQuery.

Privacy differenziale in azione

Nel giugno 2016, Apple ha annunciato che avrebbe iniziato a utilizzare algoritmi differenzialmente privati per raccogliere statistiche comportamentali da iPhone. Questo annuncio, oltre a causare un enorme picco di interesse per la privacy differenziale, ha dimostrato che la privacy differenziale può aiutare le principali organizzazioni a ottenere nuovo valore dai dati che in precedenza non toccavano a causa di problemi di privacy.

Anche se Apple ha finora reso pubblici alcuni dettagli, l’algoritmo utilizzato nell’iPhone sembra simile al progetto RAPPOR di Google. Google ha implementato una funzionalità in Chrome che raccoglie statistiche comportamentali dai browser Chrome attraverso un algoritmo di risposta randomizzato differentemente privato.

Nella risposta randomizzata, il rumore casuale viene aggiunto alle statistiche prima che vengano inviate al collector. Ad esempio, se la statistica reale è 0, il browser sostituirà con una certa probabilità 0 con uno 0 o 1 selezionato casualmente. Ogni utente ha un ampio grado di negabilità sul valore riportato dal proprio software, perché potrebbe essere un valore casuale. Ma collettivamente, il segnale si distingue per il rumore casuale e l’organizzazione che raccoglie le statistiche (ad esempio Google o Apple) può osservare con precisione le tendenze.

È interessante notare che né Google né Apple, a nostra conoscenza, hanno rivelato il valore di ϵ che va con la loro garanzia di privacy differenziale. Abbiamo bisogno di questo valore per capire la protezione offerta dalla garanzia. Se usano un valore abbastanza alto di ϵ, gli analisti possono ancora apprendere fatti sensibili sugli utenti con elevata fiducia. Un valore basso di ϵ è necessario per una protezione della privacy significativa.

Algoritmi differenzialmente privati sono stati implementati anche in prodotti di analisi che preservano la privacy, come quelli sviluppati dal mio datore di lavoro Privitar. Questi prodotti consentono alle aziende che lavorano con dati preziosi e sensibili di incorporare algoritmi differenzialmente privati nella loro architettura dei dati, fornendo garanzie di privacy ai propri utenti pur eseguendo analisi significative sui dati.

Guardando avanti

Entrambe le comunità di ingegneria e di ricerca hanno percorsi in avanti con privacy differenziale. Per gli ingegneri, il compito è quello di diventare istruiti sulla privacy differenziale e garantire che venga utilizzato, se del caso, per la protezione della privacy degli utenti. Per i ricercatori, è trovare algoritmi più e meglio differenzialmente privati, migliorando il set di strumenti con cui possiamo abilitare l’analisi dei dati che preserva la privacy.

Tutti possiamo trarre vantaggio dalla creazione di garanzie sulla privacy e dai successi dell’analisi dei dati. Per entrambi i motivi, non vediamo l’ora di più organizzazioni che abbracciano la privacy differenziale.

About the Author

Charlie Cabot è un senior data scientist presso Privitar, una startup sulla privacy dei dati che costruisce software ad alte prestazioni per l’anonimizzazione dei dati, inclusi algoritmi di perturbazione e generalizzazione e meccanismi differenzialmente privati, per facilitare l’uso sicuro di set di dati sensibili. Charlie si concentra sulle garanzie dimostrabili sulla privacy e sull’impatto statistico dell’anonimizzazione sull’analisi e sulla scienza dei dati. In precedenza, lavorando nella sicurezza informatica, Charlie ha progettato approcci basati sull’apprendimento automatico per il rilevamento di malware e ha modellato gli attacchi informatici sulle reti di computer.