K-anonimato

Il k-anonimato (o "anonimato k", dall'inglese k-anonimity) è una proprietà di anonimato posseduta da un dataset sotto determinate condizioni. Il concetto di k-anonimato è stato introdotto per la prima volta da Latanya Sweeney e Pierangela Samarati in un articolo pubblicato nel 1998 come tentativo di risolvere il problema: "Forniti dei dati strutturati sul campo, produrre un rilascio dei dati con garanzie scientifiche che le persone che sono i soggetti ai quali i dati si riferiscono non possano essere identificate nuovamente mentre i dati rimangono di utilità pratica". Si dice che la versione anonimizzata di un dataset possiede la proprietà di k-anonymity (o k-anonimato, poco usato in italiano) se le informazioni, per ogni persona contenutevi, non possono essere distinte da almeno altri $k-1$ soggetti le cui informazioni compaiono nel rilascio di dati stesso.

Il k-anonimato ha ricevuto una vasta copertura mediatica nel 2018 quando lo scienziato informatico britannico Junade Ali ha usato la proprietà congiuntamente all'hash crittografico per creare un protocollo di comunicazione con lo scopo di verificare anonimamente se una password fosse trapelata senza però rivelare la password cercata. Questo protocollo è stato implementato come un'API pubblica in Troy Hunt del servizio Have I Been Pwned? ed è utilizzato da vari servizi, inclusi gestori password ed estensioni dei browser. Questo approccio è stato successivamente replicato dalla funzione di controllo password di Google.

Metodi per la k-anonimizzazione

Nel contesto dei problemi di k-anonimizzazione, un database è una tabella con n righe ed m colonne. Ogni riga della tabella rappresenta un record relativo a un membro specifico di una popolazione e le voci nelle varie righe non devono essere univoche. I valori nelle varie colonne sono i valori degli attributi associati ai membri della popolazione. La tabella seguente è un database non anonimo che comprende le cartelle dei pazienti di un ospedale fittizio a Kochi.

Nome	Età	Genere	Domicilio	Religione	Malattia
Ramsha	30	Femmina	Tamil Nadu	Induista	Cancro
Yadu	24	Femmina	Kerala	Induista	Infezione virale
Salima	28	Femmina	Tamil Nadu	Musulmano	TBC
Sunny	27	Maschio	Karnataka	Parsi	non malato
Joan	24	Femmina	Kerala	Cristiano	Cardiopatia
Bahuksana	23	Maschio	Karnataka	Buddista	TBC
Rambha	19	Maschio	Kerala	Induista	Cancro
Kishor	29	Maschio	Karnataka	Induista	Cardiopatia
Johnson	17	Maschio	Kerala	Cristiano	Cardiopatia
John	19	Maschio	Kerala	Cristiano	Infezione virale

Ci sono 6 attributi e 10 record in questi dati. Esistono due metodi comuni per ottenere k-anonimato per un certo valore di k.

1. Soppressione : in questo metodo, alcuni valori degli attributi sono sostituiti da un asterisco '*'. Tutti o alcuni valori di una colonna possono essere sostituiti da '*'. Nella tabella anonima di seguito, abbiamo sostituito tutti i valori nell'attributo 'Nome' e tutti i valori nell'attributo 'Religione' con un '*'.
2. Generalizzazione : in questo metodo, i singoli valori degli attributi vengono sostituiti da una categoria più ampia. Ad esempio, il valore '19' dell'attributo 'Età' può essere sostituito da '≤ 20', il valore '23' da '20 <Età ≤ 30 ', ecc.

La tabella successiva mostra il database anonimo.

Nome	Età	Genere	Domicilio	Religione	Malattia
*	20 < età ≤ 30	Femmina	Tamil Nadu	*	Cancro
*	20 < età ≤ 30	Femmina	Kerala	*	Infezione virale
*	20 < età ≤ 30	Femmina	Tamil Nadu	*	TBC
*	20 < età ≤ 30	Maschio	Karnataka	*	nessuna
*	20 < età ≤ 30	Femmina	Kerala	*	Cardiopatia
*	20 < età ≤ 30	Maschio	Karnataka	*	TBC
*	età ≤ 20	Maschio	Kerala	*	Cancro
*	20 < età ≤ 30	Maschio	Karnataka	*	Cardiopatia
*	età ≤ 20	Maschio	Kerala	*	Cardiopatia
*	età ≤ 20	Maschio	Kerala	*	Infezione virale

Questi dati hanno un valore di 2-anonimato rispetto agli attributi 'Età', 'Sesso' e 'Stato di domicilio' poiché per qualsiasi combinazione di questi attributi trovati in qualsiasi riga della tabella ci sono sempre almeno 2 righe con quegli attributi esatti. Gli attributi disponibili per un avversario sono chiamati quasi-identificatori. Ogni tupla di quasi-identificatore si verifica in almeno k record per un set di dati con k-anonimato.

Meyerson e Williams (2004) hanno dimostrato che il k-anonimato ottimale è un problema NP-difficile, tuttavia metodi euristici come k-Optimize forniti da Bayardo e Agrawal (2005) spesso danno risultati efficaci. Un algoritmo di approssimazione pratico che consente di risolvere il problema di anonimizzazione k con una garanzia di approssimazione di $O(\log k)$ è stato presentato da Kenig e Tassa.

Possibili attacchi

Nonostante il k-anonimato sia un buon approccio iniziale da adottare per l'anonimizzazione basata su gruppi, data la sua semplicità e la vasta gamma di algoritmi che la eseguono, è tuttavia suscettibile a molti attacchi. Quando è disponibile una conoscenza del background per un utente malintenzionato, tali attacchi diventano ancora più efficaci. Tra i possibili attacchi troviamo:

• Homogeneity attack : questo attacco sfrutta il caso in cui tutti i valori per un valore sensibile all'interno di un set di k record sono identici. In tali casi, anche se i dati sono stati k-anonimizzati, è possibile prevedere esattamente il valore sensibile per l'insieme di k record.
• Attacco basato sulla conoscenza del contesto (background) : questo attacco sfrutta un'associazione tra uno o più attributi di quasi-identificatore con l'attributo sensibile per ridurre l'insieme dei possibili valori per l'attributo sensibile. Ad esempio, Machanavajjhala, Kifer, Gehrke e Venkitasubramaniam (2007) hanno mostrato che sapere che gli attacchi di cuore si verificano a una velocità ridotta nei pazienti giapponesi potrebbe essere usato per restringere l'intervallo di valori per un attributo sensibile della malattia di un paziente.

Avvertenze

Poiché la k-anonimizzazione non include alcuna randomizzazione, gli aggressori possono ancora fare deduzioni sui set di dati che potrebbero danneggiare le persone. Ad esempio, se è noto che il diciannovenne John del Kerala si trova nel database sopra, allora si può affermare con certezza che ha un cancro, una malattia correlata al cuore o un'infezione virale.

La k-anonimizzazione non è un buon metodo per anonimizzare set di dati ad alta dimensione.

È stato anche dimostrato che l'anonimato k può distorcere i risultati di un set di dati se sopprime e generalizza in modo sproporzionato punti di dati con caratteristiche non rappresentative. Gli algoritmi di soppressione e generalizzazione utilizzati per k-anonimizzare i set di dati possono essere modificati, tuttavia, in modo che non abbiano un tale effetto distorto.

Voci correlate

• i-vicinanza
• l-diversità
• Privacy differenziale