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

Матеріал з testwiki
Перейти до навігації Перейти до пошуку

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

k-анонімність отримала широке висвітлення у ЗМІ у 2018 році, коли британський вчений-комп'ютерник Джунаде Алі використав властивість разом із криптографічним хешуванням для створення протоколу взаємодії, щоб анонімно перевірити, чи був пароль у даних, що витікли, без розкриття пароля, що перевіряється.[5][6] Цей протокол був реалізований як загальнодоступний API у службі Have I Been Pwned? Шаблон:Не перекладено і використовується кількома службами, включаючи менеджери паролів[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-анонімізації з гарантією апроксимації O(log⁡k), був представлений Кенігом і Тассою.[17]

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

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

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

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

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

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

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

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

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

Цей підхід працює, обчислюючи криптографічний хеш від одновимірних даних і обрізаючи хеш-значення таким чином, щоб було щонайменше k−1 колізій хешування. Цей підхід дозволяє здійснювати ефективний анонімний пошук у великих наборах даних, таких як зламані паролі.[24] Крім того, цей підхід можна використовувати для забезпечення формально підтвердженого рівня анонімності приватних даних, що дозволить зробити точний компроміс між витоком інформації та функціональністю (наприклад, для Шаблон:Не перекладено).[23][25]

Див. також

Примітки

Шаблон:Reflist

  1. ↑ Шаблон:Cite web
  2. ↑ P. Samarati. Protecting Respondents' Identities in Microdata Release Шаблон:Webarchive. IEEE Transactions on Knowledge and Data Engineering archive Volume 13 Issue 6, November 2001.
  3. ↑ Шаблон:Cite web
  4. ↑ L. Sweeney. k-anonymity: a model for protecting privacy Шаблон:Webarchive. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10 卌, 2002; 557—570.
  5. ↑ 5,0 5,1 Шаблон:Cite news
  6. ↑ 6,0 6,1 Шаблон:Cite web
  7. ↑ Шаблон:Cite news
  8. ↑ Шаблон:Cite news
  9. ↑ Шаблон:Cite news
  10. ↑ Шаблон:Cite news
  11. ↑ Шаблон:Cite web
  12. ↑ Шаблон:Cite web
  13. ↑ Шаблон:Cite web Шаблон:Webarchive
  14. ↑ Шаблон:Cite web
  15. ↑ Шаблон:Cite book
  16. ↑ Шаблон:Cite book Шаблон:Webarchive
  17. ↑ Шаблон:Cite journal
  18. ↑ Шаблон:Cite conference
  19. ↑ Шаблон:Cite journal
  20. ↑ Шаблон:Cite web
  21. ↑ Шаблон:Cite journal
  22. ↑ Шаблон:Cite arXiv
  23. ↑ 23,0 23,1 Шаблон:Cite journal
  24. ↑ Шаблон:Cite book
  25. ↑ Шаблон:Cite journal
Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=K-анонімність&oldid=9526