K-анонімність

k-анонімність — це властивість, якою володіють певні анонімні дані^[en]. Поняття k-анонімності вперше було введено Латанією Свіні^[en] Латанія Свіні та Піеранджелою Самараті^[en] у статті, опублікованій у 1998 році^[1] як спроба вирішити проблему: «Враховуючи конкретні польові дані, опублікувати дані з науковими гарантіями того, що особи, які є суб'єктами даних, не можуть бути повторно ідентифіковані, поки дані залишаються практично корисними».^[2][3][4] Кажуть, що випуск даних має властивість k-анонімності, якщо інформацію про кожну особу, що міститься у опублікованих даних, неможливо відрізнити від принаймні ${\displaystyle k-1}$ осіб, чия інформація також з'являється у відкритому доступі.

k-анонімність отримала широке висвітлення у ЗМІ у 2018 році, коли британський вчений-комп'ютерник Джунаде Алі використав властивість разом із криптографічним хешуванням для створення протоколу взаємодії, щоб анонімно перевірити, чи був пароль у даних, що витікли, без розкриття пароля, що перевіряється.^[5][6] Цей протокол був реалізований як загальнодоступний API у службі Have I Been Pwned? Троя Ханта^[en] і використовується кількома службами, включаючи менеджери паролів^[7][8] і розширеннями браузера.^[9][10] Пізніше цей підхід був відтворений функцією перевірки пароля Google.^[11][12][13]

Методи для k-анонімізації

У контексті проблем k-анонімізації база даних — це таблиця з n рядками та m стовпцями. Кожен рядок таблиці представляє запис, що відноситься до певного члена сукупності, і записи в різних рядках не обов'язково повинні бути унікальними. Значення в різних стовпцях є значеннями атрибутів, пов'язаних з членами сукупності. Наступна таблиця є неанонімною базою даних, що складається з записів пацієнтів якоїсь фіктивної лікарні в Кочі.

Ім'я	Вік	Стать	Регіон	Релігія	Захворювання
Ramsha	30	Жіноча	Tamil Nadu	Індуізм	Рак
Yadu	24	Жіноча	Kerala	Індуізм	Вірусні захворювання
Salima	28	Жіноча	Tamil Nadu	Іслам	Туберкульоз
Sunny	27	Чоловіча	Karnataka	Парси	Немає хвороб
Joan	24	Жіноча	Kerala	Християнство	Серцево-судинні захворювання
Bahuksana	23	Чоловіча	Karnataka	Буддизм	Туберкульоз
Rambha	19	Чоловіча	Kerala	Індуізм	Рак
Kishor	29	Чоловіча	Karnataka	Індуізм	Серцево-судинні захворювання
Johnson	17	Чоловіча	Kerala	Християнство	Серцево-судинні захворювання
John	19	Чоловіча	Kerala	Християнство	Вірусні захворювання

У цих даних є 6 атрибутів і 10 записів. Є два поширені методи для досягнення k-анонімності для деякого значення k.

1. Придушення: у цьому методі певні значення атрибутів замінюються зірочкою '*'. Усі або деякі значення стовпця можна замінити на «*». В анонімізованій таблиці нижче ми замінили всі значення в атрибуті «Ім'я» і всі значення в атрибуті «Релігія» на «*».
2. Узагальнення: У цьому методі окремі значення атрибутів замінюються більш широкою категорією. Наприклад, значення «19» атрибута «Вік» можна замінити на « ≤ 20», значення «23» на «20 < Вік ≤ 30» тощо.

У наступній таблиці показано анонімізовану базу даних.

Ім'я	ВІк	Стать	Регіон	Релігія	Захворювання
*	20 < ВІк ≤ 30	Жіноча	Tamil Nadu	*	Рак
*	20 < Вік ≤ 30	Жіноча	Kerala	*	Вірусні захворювання
*	20 < ВІк ≤ 30	Жіноча	Tamil Nadu	*	Туберкульоз
*	20 < ВІк ≤ 30	Чоловіча	Karnataka	*	Немає хвороб
*	20 < ВІк ≤ 30	Жіноча	Kerala	*	Серцево-судинні захворювання
*	20 < ВІк ≤ 30	Чоловіча	Karnataka	*	Туберкульоз
*	ВІк ≤ 20	Чоловіча	Kerala	*	Рак
*	20 < ВІк ≤ 30	Чоловіча	Karnataka	*	Серцево-судинні захворювання
*	ВІк ≤ 20	Чоловіча	Kerala	*	Серцево-судинні захворювання
*	ВІк ≤ 20	Чоловіча	Kerala	*	Вірусні захворювання

Ці дані мають 2-анонімність щодо атрибутів «Вік», «Стать» і «Регіон», оскільки для будь-якої комбінації цих атрибутів, знайдених у будь-якому рядку таблиці, завжди є принаймні 2 рядки з цими точними атрибутами. Атрибути, доступні супротивнику, називаються квазі-ідентифікатор. Кожен кортеж квазі-ідентифікатора зустрічається принаймні в k записах для набору даних з k-анонімністю.^[14]

Мейерсон та Вільямс (2004) продемонстрували, що оптимальна k-анонімність є NP-складною проблемою, однак евристичні методи, такі як k-Optimize, як дають Баярдо та Агравал (2005), часто дають ефективні результати.^[15][16] Практичний алгоритм апроксимації, який дозволяє вирішити проблему k-анонімізації з гарантією апроксимації ${\displaystyle O(\log k)}$, був представлений Кенігом і Тассою.^[17]

Можливі атаки

Хоча k-анонімність є багатообіцяючим підходом для групової анонімізації, враховуючи її простоту та широкий набір алгоритмів, які її виконують, однак вона сприйнятлива до багатьох атак. Коли зловмиснику доступні базові знання, такі атаки стають ще ефективнішими. До таких атак відносяться:

• Атака однорідності: ця атака використовує випадок, коли всі значення для чутливої змінної в наборі k записів ідентичні. У таких випадках, навіть якщо дані були k-анонімізовані, чутливу змінну для набору k записів можна точно передбачити.
• Атака фонових знань: ця атака використовує зв'язок між одним або кількома атрибутами квазі-ідентифікатора з чутливим атрибутом, щоб зменшити набір можливих значень для чутливого атрибута. Наприклад, Machanavajjhala, Kifer, Gehrke та Venkitasubramaniam (2007) показали, що знання того, що серцеві напади відбуваються з меншою частотою у японських пацієнтів, можна використовувати для звуження діапазону чутливої змінної — ознаки захворювання пацієнта.

Застереження

Оскільки k-анонімізація не включає рандомізацію, зловмисники все одно можуть робити висновки про набори даних, які можуть завдати шкоди особам. Наприклад, якщо відомо, що 19-річний Джон з Керали є в базі даних вище, то можна з достовірністю сказати, що у нього рак, серцева хвороба або вірусна інфекція.

K-анонімізація не є хорошим методом анонімізації великорозмірних наборів даних.^[18] Наприклад, дослідники показали, що, маючи 4 точки, унікальність наборів даних про місцеположення з часовою міткою мобільного телефону (${\displaystyle {\mathcal {E}}_{4}}$, k -анонімність, коли ${\displaystyle k=1}$) може досягати 95 %.^[19]

Також було показано, що k-анонімність може спотворити результати набору даних, якщо вона непропорційно пригнічує та узагальнює точки даних з нерепрезентативними характеристиками.^[20] Алгоритми придушення та узагальнення, які використовуються для k-анонімізації наборів даних, можна змінити, щоб вони не мали такого ефекту перекосу.^[21]

k-анонімність на основі хешу

k-анонімність на основі хешів була значною мірою розроблена Джунаде Алі, спочатку для запобігання перевірки скомпрометованих облікових даних^{[en][5][6][22]} і пізніше для анонімізації MAC-адрес в реальному часі.^[23]

Цей підхід працює, обчислюючи криптографічний хеш від одновимірних даних і обрізаючи хеш-значення таким чином, щоб було щонайменше ${\displaystyle k-1}$ колізій хешування. Цей підхід дозволяє здійснювати ефективний анонімний пошук у великих наборах даних, таких як зламані паролі.^[24] Крім того, цей підхід можна використовувати для забезпечення формально підтвердженого рівня анонімності приватних даних, що дозволить зробити точний компроміс між витоком інформації та функціональністю (наприклад, для анонімізації MAC-адрес^[en]).^[23][25]

Див. також

• t-близькість^[en]
• l-диверсність^[en]
• Диференційна приватність