K-anonymita - K-anonymity

k-anonymita je vlastnost vlastněná jistými anonymizovaná data. Koncept k-anonymita byla poprvé představena Latanya Sweeney a Pierangela Samarati v článku publikovaném v roce 1998^[1] jako pokus o vyřešení problému: „Vzhledem k terénně strukturovaným datům specifickým pro danou osobu vytvořte uvolnění dat s vědeckými zárukami, že jednotlivci, kteří jsou subjekty údajů, nemohou být znovu identifikováni, zatímco data zůstanou prakticky užitečná.“^[2][3][4] Uvolnění dat má údajně k-anonymita vlastnost, pokud informace o každé osobě obsažené ve verzi nelze odlišit alespoň od ${ displaystyle k-1}$ jednotlivci, jejichž informace se také objevují ve vydání.

k-anonymita získala široké mediální pokrytí v roce 2018, kdy britský počítačový vědec Junade Ali užívala nemovitost po boku kryptografický hash vytvořit komunikační protokol k anonymnímu ověření, zda došlo k úniku hesla, aniž by bylo nutné prozradit heslo.^[5][6] Tento protokol byl implementován jako veřejné API v Troy Hunt je Byl jsem Pwned? služba a je spotřebována několika službami včetně správci hesel^[7][8] a rozšíření prohlížeče.^[9][10] Tento přístup byl později replikován Google Funkce kontroly hesla.^[11][12][13]

Metody pro k-anonymizace

V kontextu k-anonymizace problémy, databáze je tabulka s n řádky a m sloupce. Každý řádek tabulky představuje záznam týkající se konkrétního člena populace a položky v různých řádcích nemusí být jedinečné. Hodnoty v různých sloupcích jsou hodnotami atributů přidružených k členům populace. V následující tabulce je neanonymizovaná databáze sestávající ze záznamů o pacientech z nějaké fiktivní nemocnice v Koči.

V těchto datech je 6 atributů a 10 záznamů. Existují dvě běžné metody dosažení k-anonymita pro určitou hodnotu k.

1. Potlačení: V této metodě jsou určité hodnoty atributů nahrazeny hvězdičkou '*'. Všechny nebo některé hodnoty sloupce mohou být nahrazeny znakem „*“. V níže uvedené anonymizované tabulce jsme nahradili všechny hodnoty v atributu „Název“ a všechny hodnoty v atributu „Náboženství“ znakem „*“.
2. Zobecnění: V této metodě jsou jednotlivé hodnoty atributů nahrazeny širší kategorií. Například hodnota „19“ atributu „Věk“ může být nahrazena hodnotou „≤ 20“, hodnota „23“ hodnotou „20

V následující tabulce je uvedena anonymizovaná databáze.

Tato data mají 2-anonymitu, pokud jde o atributy „Věk“, „Pohlaví“ a „Stát bydliště“, protože pro každou kombinaci těchto atributů nalezenou v libovolném řádku tabulky jsou vždy alespoň 2 řádky s těmito přesnými atributy. Atributy dostupné protivníkovi se nazývají kvaziidentifikátory. Každá n-tice kvaziidentifikátoru se vyskytuje minimálně k záznamy pro datovou sadu s k-anonymita.^[14]

To optimální prokázali Meyerson a Williams (2004) k-anonymita je NP-tvrdé problém, nicméně heuristické metody jako k-Optimalizace, jak uvádí Bayardo a Agrawal (2005), často přináší efektivní výsledky.^[15][16] Praktický aproximační algoritmus, který umožňuje řešení k-anonymizační problém se zárukou aproximace ${ displaystyle O ( log k)}$ představili Kenig a Tassa.^[17]

Možné útoky

Zatímco k-anonymita je slibný přístup pro skupinovou anonymizaci vzhledem ke své jednoduchosti a široké škále algoritmů, které ji provádějí, je však náchylný k mnoha útokům. Pokud má útočník k dispozici znalosti na pozadí, stanou se takové útoky ještě efektivnějšími. Mezi takové útoky patří:

• Homogenita útok: Tento útok využívá případ, kdy jsou všechny hodnoty pro citlivou hodnotu v sadě k záznamy jsou identické. V takových případech, přestože data byla k-anonymized, citlivá hodnota pro sadu k záznamy lze přesně předpovědět.
• Pozadí znalostního útoku: Tento útok využívá přidružení mezi jedním nebo více atributy kvaziidentifikátoru s citlivým atributem, aby se snížila sada možných hodnot pro citlivý atribut. Například Machanavajjhala, Kifer, Gehrke a Venkitasubramaniam (2007) prokázali, že znalosti o tom, že u japonských pacientů dochází k infarktu ve snížené míře, lze použít ke zúžení rozsahu hodnot citlivého atributu pacientovy nemoci.

Upozornění

Protože k-anonymizace nezahrnuje žádnou randomizaci, útočníci mohou stále dělat závěry o souborech dat, které mohou jednotlivcům ublížit. Například pokud je známo, že 19letý John z Kéraly je ve výše uvedené databázi, lze spolehlivě říci, že má buď rakovinu, srdeční onemocnění nebo virovou infekci.

K.-anonymizace není dobrá metoda k anonymizaci vysoko-dimenzionálních datových sad.^[18] Vědci například ukázali, že vzhledem k 4 lokalitám jednotnost souborů údajů o umístění časové značky mobilního telefonu (${ displaystyle { mathcal {E}} _ {4}}$, k-anonymita, když ${ displaystyle k = 1}$) může být až 95%.^[19]

Bylo také prokázáno, že k-anonymita může zkreslit výsledky datové sady, pokud neúměrně potlačuje a zobecňuje datové body s nereprezentativními charakteristikami.^[20] Dříve používané algoritmy potlačení a zobecnění k-anonymizovat datové sady lze však změnit, aby neměly takový efekt zkosení.^[21]

Hash-based k-Anonymita

Hash-based k-Anonymita byla do značné míry vyvinuta Junade Ali, zpočátku pro prevenci Napadená kontrola pověření^[22][23][24] a později pro anonymizaci v reálném čase MAC adresy.^[25]

Tento přístup funguje tak, že kryptografický hash jednorozměrných dat a zkrácení hashe tak, aby jich bylo alespoň ${ displaystyle k-1}$ hashovací kolize. Tento přístup umožňuje efektivní anonymizované vyhledávání velkých datových sad, jako jsou porušená hesla.^[26] Tento přístup lze dále použít k poskytnutí formálně prokazatelné úrovně anonymity údajům citlivým na soukromí, což umožňuje přesné kompromisy mezi únikem informací a funkčností.^[27][28]

Viz také

• t-blízkost
• l-rozmanitost
• Diferenciální soukromí

Reference