K-anonymitet

k-anonymitet är ett mått på effektiviteten i pseudonymisering av data. Begreppet k-anonymitet introducerades först av Latanya Sweeney och Pierangela Samarati i en artikel publicerad 1998[1] för att lösa problemet: "Med utgångspunkt i personspecifik fältstrukturerad data, skapa en datastruktur där de berörda individerna inte kan återidentifieras, medan uppgifterna förblir praktiskt användbara."[2][3][4] En datastruktur har k-anonymitet om informationen för varje person som ingår inte kan särskiljas från minst k−1 andra personer i datastrukturen.

k-anonymitet fick omfattande mediebevakning 2018 när den brittiske datavetaren Junade Ali använde dess egenskap tillsammans med kryptografisk hashning för att skapa ett kommunikationsprotokoll för att anonymt verifiera om ett lösenord har läckt utan att avslöja vilket lösenord man sökte på. [5] [6] Detta protokoll implementerades som ett offentligt API i Troy Hunts app Have I Been Pwned? och används av flera tjänster inklusive lösenordshanterare[7][8] och webbläsartillägg.[9][10] Detta tillvägagångssätt replikerades senare av Googles egna funktion för lösenordskontroll.[11][12][13]

Metoder för k-anonymisering

Inom k -anonymiseringsproblem är en databas en tabell med n rader och m kolumner. Varje rad i tabellen representerar en post för en individ, dock behöver inte varje rad vara unik. Värdena i de olika kolumnerna är för attribut som är associerade med individerna. Följande tabell är en icke-anonymiserad databas som består av patientjournaler från något fiktivt sjukhus i Kochi.

Namn	Ålder	Kön	Delstat	Religion	Sjukdom
Ramsha	30	Kvinna	Tamil Nadu	Hindu	Cancer
Yadu	24	Kvinna	Kerala	Hindu	Virus
Salima	28	Kvinna	Tamil Nadu	Muslim	Tuberkulos
Sunny	27	Man	Karnataka	Parser	Ingen sjukdom
Joan	24	Kvinna	Kerala	Kristen	Hjärtsjukdom
Bahuksana	23	Man	Karnataka	Buddist	Tuberkulos
Rambha	19	Man	Kerala	Hindu	Cancer
Kishor	29	Man	Karnataka	Hindu	Hjärtsjukdom
Johnson	17	Man	Kerala	Kristen	Hjärtsjukdom
John	19	Man	Kerala	Kristen	Virus

I denna icke-anonymiserade tabell finns det 6 attribut och 10 poster. De två vanliga metoderna för att uppnå k-anonymitet för något värde av k är följande:

1. Undertryckning : I den här metoden ersätts vissa värden för attributen med en asterisk '*'. Alla eller vissa värden i en kolumn kan ersättas med '*'. I den anonymiserade tabellen nedan har alla värden i attributet 'Namn' och alla värden i attributet 'Religion' ersatts med en '*'.
2. Generalisering : I denna metod ersätts individuella värden för attribut med en bredare kategori. Till exempel kan värdet '19' för attributet 'Ålder' ersättas med '≤ 20', värdet '23' med '20 < Ålder ≤ 30' osv.

Nästa tabell visar databasen anonymiserad:

Namn	Ålder	Kön	Delstat	Religion	Sjukdom
*	20 < Ålder ≤ 30	Kvinna	Tamil Nadu	*	Cancer
*	20 < Ålder ≤ 30	Kvinna	Kerala	*	Virus
*	20 < Ålder ≤ 30	Kvinna	Tamil Nadu	*	Tuberkulos
*	20 < Ålder ≤ 30	Man	Karnataka	*	Ingen sjukdom
*	20 < Ålder ≤ 30	Kvinna	Kerala	*	Hjärtsjukdom
*	20 < Ålder ≤ 30	Man	Karnataka	*	Tuberkulos
*	Ålder ≤ 20	Man	Kerala	*	Cancer
*	20 < Ålder ≤ 30	Man	Karnataka	*	Hjärtsjukdom
*	Ålder ≤ 20	Man	Kerala	*	Hjärtsjukdom
*	Ålder ≤ 20	Man	Kerala	*	Virus

Denna tabell har 2-anonymitet med avseende på attributen 'Ålder', 'Kön' och 'Delstat' eftersom för alla kombinationer av dessa attribut så finns det alltid minst 2 poster med dessa exakta attribut. De attribut som är tillgängliga för en motståndare, för att identifiera en individ, kallas kvasiidentifierare. Varje tupel av kvasiidentifierare förekommer i minst k poster för en datauppsättning med k-anonymitet.[14]

Referenser

1. Samarati, Pierangela; Sweeney, Latanya (1998). ”Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression”. Harvard Data Privacy Lab. https://dataprivacylab.org/dataprivacy/projects/kanonymity/paper3.pdf. 
2. P. Samarati. Protecting Respondents' Identities in Microdata Release. IEEE Transactions on Knowledge and Data Engineering archive Volume 13 Issue 6, November 2001.
3. L. Sweeney. ”Database Security: k-anonymity”. Database Security: k-anonymity. http://latanyasweeney.org/work/kanonymity.html. 
4. L. Sweeney. k-anonymity: a model for protecting privacy. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10 卌, 2002; 557-570.
5. . https://arstechnica.com/information-technology/2018/02/new-tool-safely-checks-your-passwords-against-a-half-billion-pwned-passwords/. 
6. ”1Password bolts on a 'pwned password' check – TechCrunch” (på amerikansk engelska). techcrunch.com. https://techcrunch.com/2018/02/23/1password-bolts-on-a-pwned-password-check. 
7. . https://www.macrumors.com/2018/02/23/1password-pwned-passwords/. 
8. . https://gizmodo.com/1password-helps-you-find-out-if-your-password-is-pwned-1823272286. 
9. . https://www.zdnet.com/article/okta-offers-free-multi-factor-authentication-with-new-product-one-app/. 
10. . https://qz.com/1284488/the-worlds-biggest-database-of-hacked-passwords-is-now-a-chrome-extension-that-checks-yours-automatically/. 
11. ”Google's New Chrome Extension Finds Your Hacked Passwords”. www.laptopmag.com. https://www.laptopmag.com/articles/googles-new-chrome-extension-finds-hacked-passwords. 
12. ”Google Launches Password Checkup Extension to Alert Users of Data Breaches” (på amerikansk engelska). BleepingComputer. https://www.bleepingcomputer.com/news/security/google-launches-password-checkup-extension-to-alert-users-of-data-breaches/. 
13. ”Google's new Chrome extension 'Password CheckUp' checks if your username or password has been exposed to a third party breach”. Packt Hub. https://hub.packtpub.com/googles-new-chrome-extension-password-checkup-checks-if-your-username-or-password-has-been-exposed-to-a-third-party-breach/.  Arkiverad 15 november 2022 hämtat från the Wayback Machine.
14. Narayanan, Arvind; Shmatikov, Vitaly. ”Robust De-anonymization of Large Sparse Datasets”. Robust De-anonymization of Large Sparse Datasets. https://www.cs.utexas.edu/~shmat/shmat_oak08netflix.pdf.