k -anonymitet

k -anonymitet är en egenskap som innehas av vissa anonymiserade data . Termen k -anonymitet introducerades först av Pierangela Samarati och Latanya Sweeney i en tidning som publicerades 1998, även om konceptet dateras till en tidning från 1986 av Tore Dalenius.

K-anonymitet är ett försök att lösa problemet: "Med tanke på personspecifika fältstrukturerade data, producera ett släpp av data med vetenskapliga garantier för att de individer som är föremål för data inte kan återidentifieras medan uppgifterna praktiskt taget finns kvar. användbar." En frigivning av data sägs ha k -anonymitet om informationen för varje person som finns i releasen inte kan särskiljas från minst $k-1$ individer vars information också förekommer i releasen. Tyvärr är garantierna från k-anonymitet strävande, inte matematiska.

Metoder för k -anonymisering

För att använda k-anonymitet för att bearbeta en datauppsättning så att den kan släppas med integritetsskydd måste en datavetare först undersöka datauppsättningen och avgöra om varje attribut (kolumn) är en identifierare (identifierande), en icke-identifierare ( ej identifierande ) . ), eller en kvasiidentifierare (något identifierande). Identifierare såsom namn undertrycks, icke-identifierande värden tillåts finnas kvar, och kvasi-identifierarna måste bearbetas så att varje distinkt kombination av kvasi-identifierare betecknar minst k poster .

I exemplet nedan presenteras en fiktiv icke-anonymiserad databas som består av patientjournalerna för ett fiktivt sjukhus. Kolumnen Namn är en identifierare, ålder, kön, hemviststat och religion är kvasiidentifierare, och sjukdom är ett icke-identifierande känsligt värde. Men hur är det med höjd och vikt ? Är de också icke-identifierande känsliga värden, eller är de kvasiidentifierare?

Patienter som behandlades i studien den 30 april

namn	Ålder	Kön	Höjd	Vikt	Hemviststat	Religion	Sjukdom
Ramsha	30	Kvinna	165 cm	72 kg	Tamil Nadu	hinduiskt	Cancer
Yadu	24	Kvinna	162 cm	70 kg	Kerala	hinduiskt	Virusinfektion
Salima	28	Kvinna	170 cm	68 kg	Tamil Nadu	muslim	Tuberkulos
Solig	27	Manlig	170 cm	75 kg	Karnataka	Parsi	Ingen sjukdom
Joan	24	Kvinna	165 cm	71 kg	Kerala	Christian	Hjärterelaterat
Bahuksana	23	Manlig	160 cm	69 kg	Karnataka	buddhist	Tuberkulos
Rambha	19	Manlig	167 cm	85 kg	Kerala	hinduiskt	Cancer
Kishor	29	Manlig	180 cm	81 kg	Karnataka	hinduiskt	Hjärterelaterat
Johnson	17	Manlig	175 cm	79 kg	Kerala	Christian	Hjärterelaterat
John	19	Manlig	169 cm	82 kg	Kerala	Christian	Virusinfektion

Det finns 6 attribut och 10 poster i denna data. Det finns två vanliga metoder för att uppnå k -anonymitet för något värde av k .

Undertryckning : I den här metoden ersätts vissa värden av attributen med en asterisk '*'. Alla eller vissa värden i en kolumn kan ersättas med '*'. I den anonymiserade tabellen nedan har vi ersatt alla värden i attributet 'Name' och alla värden i attributet 'Religion' med ett '*'.
Generalisering : I den här metoden ersätts individuella värden för attribut med en bredare kategori. Till exempel kan värdet '19' för attributet 'Age' ersättas med ' ≤ 20', värdet '23' med '20 < Age ≤ 30' osv.

Nästa tabell visar den anonymiserade databasen.

Patienter som behandlades i studien den 30 april

namn	Ålder	Kön	Höjd	Vikt	Hemviststat	Religion	Sjukdom
*	20 < Ålder ≤ 30	Kvinna	165 cm	72 kg	Tamil Nadu	*	Cancer
*	20 < Ålder ≤ 30	Kvinna	162 cm	70 kg	Kerala	*	Virusinfektion
*	20 < Ålder ≤ 30	Kvinna	170 cm	68 kg	Tamil Nadu	*	Tuberkulos
*	20 < Ålder ≤ 30	Manlig	170 cm	75 kg	Karnataka	*	Ingen sjukdom
*	20 < Ålder ≤ 30	Kvinna	165 cm	71 kg	Kerala	*	Hjärterelaterat
*	20 < Ålder ≤ 30	Manlig	160 cm	69 kg	Karnataka	*	Tuberkulos
*	Ålder ≤ 20	Manlig	167 cm	85 kg	Kerala	*	Cancer
*	20 < Ålder ≤ 30	Manlig	180 cm	81 kg	Karnataka	*	Hjärterelaterat
*	Ålder ≤ 20	Manlig	175 cm	79 kg	Kerala	*	Hjärterelaterat
*	Ålder ≤ 20	Manlig	169 cm	82 kg	Kerala	*	Virusinfektion

Dessa data har 2-anonymitet med avseende på attributen 'Ålder', 'Kön' och 'State of domicil' eftersom det för alla kombinationer av dessa attribut som finns i någon rad i tabellen alltid finns minst 2 rader med dessa exakta attribut. De attribut som är tillgängliga för en motståndare kallas kvasi-identifierare . Varje kvasi-identifierare tupel förekommer i minst k poster för en datauppsättning med k -anonymitet.

Kritik av k-anonymitet

Det här exemplet visar ett misslyckande med k -anonymitet: det kan finnas andra dataposter som kan länkas på variablerna som påstås vara icke-identifierande. Till exempel, om en angripare kan få en logg från personen som tog vitala tecken som en del av studien och får reda på att Kishor var på sjukhuset den 30 april och är 180 cm lång, kan denna information användas för att länka till den "anonymiserade" databasen (som kan ha publicerats på Internet) och få reda på att Kishor har en hjärtrelaterad sjukdom. En angripare som vet att Kishor besökte sjukhuset den 30 april kanske kan dra slutsatsen att det bara vet att Kishor är 180 cm hög, ungefär 80-82 kg, och kommer från Karnataka.

Roten till detta problem är kärnproblemet med k-anonymitet: det finns inget sätt att matematiskt, entydigt avgöra om ett attribut är en identifierare, en kvasi-identifierare eller ett icke-identifierande känsligt värde. Faktum är att alla värden är potentiellt identifierande, beroende på deras förekomst i befolkningen och på hjälpdata som angriparen kan ha. Andra integritetsmekanismer som differentiell integritet delar inte detta problem.

Meyerson och Williams (2004) visade att optimal k -anonymitet är ett NP-hårt problem, men heuristiska metoder som k -Optimize som ges av Bayardo och Agrawal (2005) ger ofta effektiva resultat. En praktisk approximationsalgoritm som möjliggör att lösa k -anonymiseringsproblemet med en approximationsgaranti på $O(\log k)$ presenterades av Kenig och Tassa.

Eventuella attacker

Även om k -anonymitet är ett lovande tillvägagångssätt för gruppbaserad anonymisering med tanke på dess enkelhet och breda utbud av algoritmer som utför den, är den dock mottaglig för många attacker. När bakgrundskunskap är tillgänglig för en angripare blir sådana attacker ännu mer effektiva. Sådana attacker inkluderar:

Homogenitetsattack : Denna attack utnyttjar fallet där alla värden för ett känsligt värde inom en uppsättning av k poster är identiska. I sådana fall, även om data har k -anonymiserats, kan det känsliga värdet för uppsättningen av k poster förutsägas exakt.
Bakgrundskunskapsattack : Denna attack utnyttjar en association mellan ett eller flera kvasiidentifieringsattribut med det känsliga attributet för att minska uppsättningen av möjliga värden för det känsliga attributet. Till exempel visade Machanavajjhala, Kifer, Gehrke och Venkitasubramaniam (2007) att vetskapen om att hjärtinfarkt inträffar i reducerad takt hos japanska patienter kan användas för att begränsa värdeintervallet för en känslig egenskap hos en patients sjukdom.

Varningar

Eftersom k -anonymisering inte inkluderar någon randomisering kan angripare fortfarande dra slutsatser om datamängder som kan skada individer. Till exempel, om den 19-årige John från Kerala är känd för att finnas i databasen ovan, kan man tillförlitligt säga att han har antingen cancer, en hjärtrelaterad sjukdom eller en virusinfektion.

K -anonymisering är ingen bra metod för att anonymisera högdimensionella datamängder. Till exempel visade forskare att, givet 4 platser, enhetligheten för mobiltelefon tidsstämpel-platsdatauppsättningar ( ${\mathcal {E}}_{4}$ , k -anonymitet när $k =1$ ) kan vara så hög som 95 %.

Det har också visat sig att k -anonymitet kan skeva resultaten av en datamängd om den oproportionerligt undertrycker och generaliserar datapunkter med oprepresentativa egenskaper. Undertrycknings- och generaliseringsalgoritmerna som används för att k -anonymisera datamängder kan dock ändras så att de inte har en sådan skevningseffekt.

Se även