K-anonimato

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

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[1] 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".[2][3][4] 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 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.[5][6] Questo protocollo è stato implementato come un'API pubblica in Troy Hunt del servizio Have I Been Pwned?[7] ed è utilizzato da vari servizi, inclusi gestori password[8][9] ed estensioni dei browser.[10][11] Questo approccio è stato successivamente replicato dalla funzione di controllo password di Google.[12][13][14]

Metodi per la k-anonimizzazione[modifica | modifica wikitesto]

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.[15]

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.[16][17] Un algoritmo di approssimazione pratico che consente di risolvere il problema di anonimizzazione k con una garanzia di approssimazione di è stato presentato da Kenig e Tassa.[18]

Possibili attacchi[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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.[19]

È 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.[20] 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.[21]

Note[modifica | modifica wikitesto]

  1. ^ Pierangela Samarati, Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression (PDF), su Harvard Data Privacy Lab, 1998. URL consultato il April 12, 2017.
  2. ^ P. Samarati.
  3. ^ L. Sweeney, Database Security: k-anonymity, su latanyasweeney.org. URL consultato il 19 January 2014.
  4. ^ L. Sweeney. k-anonymity: a model for protecting privacy.
  5. ^ (EN) Find out if your password has been pwned—without sending it to a server, in Ars Technica. URL consultato il 24 maggio 2018.
  6. ^ (EN) 1Password bolts on a 'pwned password' check – TechCrunch, su techcrunch.com. URL consultato il 24 maggio 2018.
  7. ^ (EN) How to find out if your password has been leaked by hackers with this simple Google Chrome trick, in The Sun, 24 maggio 2018. URL consultato il 24 maggio 2018.
  8. ^ (EN) 1Password Integrates With 'Pwned Passwords' to Check if Your Passwords Have Been Leaked Online. URL consultato il 24 maggio 2018.
  9. ^ (EN) Kate Conger, 1Password Helps You Find Out if Your Password Is Pwned, in Gizmodo. URL consultato il 24 maggio 2018.
  10. ^ (EN) Stephanie Condon, Okta offers free multi-factor authentication with new product, One App | ZDNet, in ZDNet. URL consultato il 24 maggio 2018.
  11. ^ (EN) Michael J. Coren, The world’s biggest database of hacked passwords is now a Chrome extension that checks yours automatically, in Quartz. URL consultato il 24 maggio 2018.
  12. ^ Paul Wagenseil I, Google's New Chrome Extension Finds Your Hacked Passwords, su laptopmag.com.
  13. ^ (EN) Google Launches Password Checkup Extension to Alert Users of Data Breaches, su BleepingComputer.
  14. ^ Melisha Dsouza, Google’s new Chrome extension ‘Password CheckUp’ checks if your username or password has been exposed to a third party breach, su Packt Hub, 6 February 2019.
  15. ^ Arvind Narayanan, Robust De-anonymization of Large Sparse Datasets (PDF), su cs.utexas.edu.
  16. ^ Roberto J. Bayardo e Rakesh Agrawal, Data Privacy through Optimal k-anonymization (PDF), in ICDE '05 Proceedings of the 21st International Conference on Data Engineering, 2005, pp. 217-28, DOI:10.1109/ICDE.2005.42, ISBN 978-0-7695-2285-2, ISSN 1084-4627 (WC · ACNP).
    «Data de-identification reconciles the demand for release of data for research purposes and the demand for privacy from individuals. This paper proposes and evaluates an optimization algorithm for the powerful de-identification procedure known as k-anonymization. A k-anonymized dataset has the property that each record is indistinguishable from at least k- 1 others. Even simple restrictions of optimized k-anonymity are NP-hard, leading to significant computational challenges. We present a new approach to exploring the space of possible anonymizations that tames the combinatorics of the problem, and develop data-management strategies to reduce reliance on expensive operations such as sorting. Through experiments on real census data, we show the resulting algorithm can find optimal k-anonymizations under two representative cost measures and a wide range of k. We also show that the algorithm can produce good anonymizations in circumstances where the input data or input parameters preclude finding an optimal solution in reasonable time. Finally, we use the algorithm to explore the effects of different coding approaches and problem variations on anonymization quality and performance. To our knowledge, this is the first result demonstrating optimal k-anonymization of a nontrivial dataset under a general model of the problem.»
  17. ^ Adam Meyerson e Ryan Williams, On the Complexity of Optimal K-Anonymity (PDF), in PODS '04 Proceedings of the Twenty-third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, New York, NY, ACM, 2004, pp. 223-8, DOI:10.1145/1055558.1055591, ISBN 978-1581138580. URL consultato il 23 dicembre 2019 (archiviato dall'url originale il 28 maggio 2014).
    «The technique of k-anonymization has been proposed in the literature as an alternative way to release public information, while ensuring both data privacy and data integrity. We prove that two general versions of optimal k-anonymization of relations are NP-hard, including the suppression version which amounts to choosing a minimum number of entries to delete from the relation. We also present a polynomial time algorithm for optimal k-anonymity that achieves an approximation ratio independent of the size of the database, when k is constant. In particular, it is a O(k log k)-approximation where the constant in the big-O is no more than 4. However, the runtime of the algorithm is exponential in k. A slightly more clever algorithm removes this condition, but is a O(k logm)-approximation, where m is the degree of the relation. We believe this algorithm could potentially be quite fast in practice.»
  18. ^ Batya Kenig e Tamir Tassa, A practical approximation algorithm for optimal k-anonymity, in Data Mining and Knowledge Discovery, vol. 25, 2012, pp. 134-168, DOI:10.1007/s10618-011-0235-9.
  19. ^ 2005, ISBN 1-59593-154-6, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.3155&rep=rep1&type=pdf.
  20. ^ Olivia Angiuli, How to De-Identify Your Data, su ACM Queue, ACM.
  21. ^ Olivia Angiuli e Jim Waldo, Statistical Tradeoffs between Generalization and Suppression in the De-Identification of Large-Scale Data Sets, in IEEE Computer Society Intl Conference on Computers, Software, and Applications, June 2016.

Voci correlate[modifica | modifica wikitesto]

Estratto da "https://it.wikipedia.org/w/index.php?title=K-anonimato&oldid=135881327"