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

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

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

Методи для 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-анонімністю.

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

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

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

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

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

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

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

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

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

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

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

Див. також

• ^[en]
• ^[en]
• Диференційна приватність

Примітки

1. Samarati, Pierangela; Sweeney, Latanya (1998). Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression (PDF). Harvard Data Privacy Lab. Архів оригіналу (PDF) за 11 березня 2021. Процитовано 12 квітня 2017.
2. P. Samarati. Protecting Respondents' Identities in Microdata Release [Архівовано 31 січня 2020 у Wayback Machine.]. IEEE Transactions on Knowledge and Data Engineering archive Volume 13 Issue 6, November 2001.
3. L. Sweeney. Database Security: k-anonymity. Архів оригіналу за 16 червня 2014. Процитовано 19 січня 2014.
4. L. Sweeney. k-anonymity: a model for protecting privacy [Архівовано 27 червня 2021 у Wayback Machine.]. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10 卌, 2002; 557—570.
5. Find out if your password has been pwned—without sending it to a server. Ars Technica (амер.). Архів оригіналу за 13 червня 2021. Процитовано 24 травня 2018.
6. 1Password bolts on a 'pwned password' check – TechCrunch. techcrunch.com (амер.). Архів оригіналу за 17 січня 2021. Процитовано 24 травня 2018.
7. 1Password Integrates With 'Pwned Passwords' to Check if Your Passwords Have Been Leaked Online (англ.). Архів оригіналу за 20 березня 2021. Процитовано 24 травня 2018.
8. Conger, Kate. 1Password Helps You Find Out if Your Password Is Pwned. Gizmodo (амер.). Архів оригіналу за 8 липня 2021. Процитовано 24 травня 2018.
9. Condon, Stephanie. Okta offers free multi-factor authentication with new product, One App | ZDNet. ZDNet (англ.). Архів оригіналу за 11 березня 2021. Процитовано 24 травня 2018.
10. Coren, Michael J. The world's biggest database of hacked passwords is now a Chrome extension that checks yours automatically. Quartz (амер.). Архів оригіналу за 17 лютого 2021. Процитовано 24 травня 2018.
11. Wagenseil I, Paul (5 лютого 2019). Google's New Chrome Extension Finds Your Hacked Passwords. www.laptopmag.com. Архів оригіналу за 27 червня 2021. Процитовано 16 березня 2022.
12. Google Launches Password Checkup Extension to Alert Users of Data Breaches. BleepingComputer (амер.). Архів оригіналу за 29 квітня 2021. Процитовано 16 березня 2022.
13. Dsouza, Melisha (6 лютого 2019). Google's new Chrome extension 'Password CheckUp' checks if your username or password has been exposed to a third party breach. Packt Hub. Архів оригіналу за 7 травня 2021. Процитовано 16 березня 2022. [Архівовано 2022-11-15 у Wayback Machine.]
14. Narayanan, Arvind; Shmatikov, Vitaly. Robust De-anonymization of Large Sparse Datasets (PDF). Архів оригіналу (PDF) за 26 січня 2021. Процитовано 17 березня 2022.
15. Roberto J. Bayardo; Rakesh Agrawal (2005). Data Privacy through Optimal k-anonymization (PDF). с. 217—28. doi:10.1109/ICDE.2005.42. ISBN . ISSN 1084-4627. S2CID 17044848. Архів оригіналу (PDF) за 23 листопада 2020. Процитовано 17 березня 2022. Data de-identification reconciles the demand for release of data for research purposes and the demand for privacy from individuals. This paper proposes and evaluates an optimization algorithm for the powerful de-identification procedure known as k-anonymization. A k-anonymized dataset has the property that each record is indistinguishable from at least k - 1 others. Even simple restrictions of optimized k-anonymity are NP-hard, leading to significant computational challenges. We present a new approach to exploring the space of possible anonymizations that tames the combinatorics of the problem, and develop data-management strategies to reduce reliance on expensive operations such as sorting. Through experiments on real census data, we show the resulting algorithm can find optimal k-anonymizations under two representative cost measures and a wide range of k. We also show that the algorithm can produce good anonymizations in circumstances where the input data or input parameters preclude finding an optimal solution in reasonable time. Finally, we use the algorithm to explore the effects of different coding approaches and problem variations on anonymization quality and performance. To our knowledge, this is the first result demonstrating optimal k-anonymization of a nontrivial dataset under a general model of the problem. {{}}: Проігноровано |journal= ()
16. Adam Meyerson; Ryan Williams (2004). On the Complexity of Optimal K-Anonymity (PDF). New York, NY: ACM. с. 223—8. doi:10.1145/1055558.1055591. ISBN . S2CID 6798963. Архів оригіналу (PDF) за 28 травня 2014. Процитовано 17 березня 2022. The technique of k-anonymization has been proposed in the literature as an alternative way to release public information, while ensuring both data privacy and data integrity. We prove that two general versions of optimal k-anonymization of relations are NP-hard, including the suppression version which amounts to choosing a minimum number of entries to delete from the relation. We also present a polynomial time algorithm for optimal k-anonymity that achieves an approximation ratio independent of the size of the database, when k is constant. In particular, it is a O(k log k)-approximation where the constant in the big-O is no more than 4. However, the runtime of the algorithm is exponential in k. A slightly more clever algorithm removes this condition, but is a O(k logm)-approximation, where m is the degree of the relation. We believe this algorithm could potentially be quite fast in practice. {{}}: Проігноровано |journal= () [Архівовано 28 травня 2014 у Wayback Machine.]
17. Kenig, Batya; Tassa, Tamir (2012). A practical approximation algorithm for optimal k-anonymity. Data Mining and Knowledge Discovery. 25: 134—168. doi:10.1007/s10618-011-0235-9. S2CID 14158546.
18. Aggarwal, Charu C. (2005). On k-Anonymity and the Curse of Dimensionality. VLDB '05 – Proceedings of the 31st International Conference on Very large Data Bases. Trondheim, Norway. CiteSeerX 10.1.1.60.3155. ISBN .
19. de Montjoye, Yves-Alexandre; César A. Hidalgo; Michel Verleysen; Vincent D. Blondel (25 березня 2013). Unique in the Crowd: The privacy bounds of human mobility. Scientific Reports. 3: 1376. Bibcode:2013NatSR...3E1376D. doi:10.1038/srep01376. PMC 3607247. PMID 23524645. Архів оригіналу (PDF) за 11 серпня 2021. Процитовано 17 березня 2022.
20. Angiuli, Olivia; Joe Blitzstein; . How to De-Identify Your Data. ACM Queue. ACM. Архів оригіналу за 22 квітня 2021. Процитовано 17 березня 2022.
21. Angiuli, Olivia; (June 2016). Statistical Tradeoffs between Generalization and Suppression in the De-Identification of Large-Scale Data Sets. IEEE Computer Society Intl Conference on Computers, Software, and Applications: 589—593. doi:10.1109/COMPSAC.2016.198. ISBN . S2CID 17716908.
22. Li, Lucy; Pal, Bijeeta; Ali, Junade; Sullivan, Nick; Chatterjee, Rahul; Ristenpart, Thomas (4 вересня 2019). Protocols for Checking Compromised Credentials. arXiv:1905.13737 [cs.CR].
23. Ali, Junade; Dyo, Vladimir (2020). Practical Hash-based Anonymity for MAC Addresses. 17th International Conference on Security and Cryptography (SECRYPT 2020): 572—579. arXiv:2005.06580. doi:10.5220/0009825105720579. ISBN . S2CID 218629946.
24. Thomas, Kurt; Pullman, Jennifer; Yeo, Kevin; Raghunathan, Ananth; Kelley, Patrick Gage; Invernizzi, Luca; Benko, Borbala; Pietraszek, Tadek; Patel, Sarvar; Boneh, Dan; Bursztein, Elie (2019). Protecting accounts from credential stuffing with password breach alerting (англ.). с. 1556—1571. ISBN . Архів оригіналу за 15 квітня 2021. Процитовано 22 травня 2020.
25. Demir, Levent; Kumar, Amrit; Cunche, Mathieu; Lauradoux, Cédric (2018). The Pitfalls of Hashing for Privacy. Communications Surveys and Tutorials, IEEE Communications Society (англ.). 20 (1): 551. doi:10.1109/COMST.2017.2747598. S2CID 3571244. Архів оригіналу за 27 листопада 2020. Процитовано 22 травня 2020.