K-анонимность - K-anonymity

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

k-анонимность получила широкое освещение в СМИ в 2018 году, когда британский ученый-компьютерщик Джунаде Али использовал собственность рядом с криптографическое хеширование создать протокол связи для анонимной проверки, произошла ли утечка пароля, без раскрытия найденного пароля.^[5][6] Этот протокол был реализован как публичный API в Трой Хант с Меня поймали? сервис и используется несколькими сервисами, включая менеджеры паролей^[7][8] и расширения браузера.^[9][10] Позднее этот подход был воспроизведен Google функция проверки пароля.^[11][12][13]

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

В контексте k- проблемы анонимизации, база данных - это таблица с п ряды и м столбцы. Каждая строка таблицы представляет собой запись, относящуюся к определенному члену совокупности, и записи в различных строках не обязательно должны быть уникальными. Значения в различных столбцах - это значения атрибутов, связанных с членами совокупности. Следующая таблица представляет собой неанонимную базу данных, состоящую из карт пациентов какой-то фиктивной больницы в Кочи.

Имя	Возраст	Пол	Государство граждан по месту жительства	Религия	Болезнь
Рамша	30	женский	Тамил Наду	Индуистский	Рак
Яду	24	женский	Керала	Индуистский	Вирусная инфекция
Салима	28	женский	Тамил Наду	Мусульманин	Туберкулез
Солнечный	27	Мужской	Карнатака	Парси	Нет болезни
Джоан	24	женский	Керала	Христианин	Связанный с сердцем
Bahuksana	23	Мужской	Карнатака	Буддийский	Туберкулез
Рамба	19	Мужской	Керала	Индуистский	Рак
Кишор	29	Мужской	Карнатака	Индуистский	Связанный с сердцем
Джонсон	17	Мужской	Керала	Христианин	Связанный с сердцем
Джон	19	Мужской	Керала	Христианин	Вирусная инфекция

В этих данных 6 атрибутов и 10 записей. Есть два распространенных метода достижения k-анонимность за некоторую стоимость k.

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

В следующей таблице показана анонимная база данных.

Имя	Возраст	Пол	Государство граждан по месту жительства	Религия	Болезнь
*	20 <Возраст ≤ 30	женский	Тамил Наду	*	Рак
*	20 <Возраст ≤ 30	женский	Керала	*	Вирусная инфекция
*	20 <Возраст ≤ 30	женский	Тамил Наду	*	Туберкулез
*	20 <Возраст ≤ 30	Мужской	Карнатака	*	Нет болезни
*	20 <Возраст ≤ 30	женский	Керала	*	Связанный с сердцем
*	20 <Возраст ≤ 30	Мужской	Карнатака	*	Туберкулез
*	Возраст ≤ 20	Мужской	Керала	*	Рак
*	20 <Возраст ≤ 30	Мужской	Карнатака	*	Связанный с сердцем
*	Возраст ≤ 20	Мужской	Керала	*	Связанный с сердцем
*	Возраст ≤ 20	Мужской	Керала	*	Вирусная инфекция

Эти данные имеют 2-анонимность по отношению к атрибутам «Возраст», «Пол» и «Государство проживания», поскольку для любой комбинации этих атрибутов, найденных в любой строке таблицы, всегда есть как минимум 2 строки с этими точными атрибутами. Атрибуты, доступные противнику, называются квазиидентификаторы. Каждый кортеж квазиидентификатора встречается как минимум в k записи для набора данных с k-анонимность.^[14]

Мейерсон и Уильямс (2004) продемонстрировали, что оптимальный k-анонимность - это NP-жесткий проблема, однако эвристические методы, такие как k-Оптимизация, предложенная Баярдо и Агравалом (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-Анонимность была в значительной степени развита Джунаде Али, первоначально для предотвращения Взломанная проверка учетных данных^[22][23][24] а затем для анонимизации в реальном времени MAC-адреса.^[25]

Этот подход работает, если взять криптографический хеш одномерных данных и усечение хэша так, чтобы было не менее ${\displaystyle k-1}$ хеш-коллизии. Такой подход позволяет осуществлять эффективный анонимный поиск в больших наборах данных, таких как взломанные пароли.^[26] Этот подход может также использоваться для обеспечения формально демонстрируемого уровня анонимности конфиденциальных данных, позволяя найти точный компромисс между утечкой информации и функциональностью.^[27][28]

Смотрите также

• т-ближенность
• л-разнообразие
• Дифференциальная конфиденциальность

Рекомендации

1. Самарати, Пиерангела; Суини, Латанья (1998). «Защита конфиденциальности при раскрытии информации: k-анонимность и обеспечение ее соблюдения посредством обобщения и подавления» (PDF). Лаборатория конфиденциальности данных Гарварда. Получено 12 апреля, 2017.
2. П. Самарати. Защита личности респондентов при выпуске микроданных. IEEE Transactions on Knowledge and Data Engineering archive, том 13, выпуск 6, ноябрь 2001 г.
3. Л. Суини. «Безопасность базы данных: k-анонимность». Получено 19 января 2014.
4. Л. Суини. k-анонимность: модель защиты конфиденциальности. Международный журнал по неопределенности, нечеткости и системам, основанным на знаниях, 10, 2002; 557-570.
5. «Узнайте, был ли введен ваш пароль - без отправки его на сервер». Ars Technica. Получено 2018-05-24.
6. "1Password болтает при проверке" введенного пароля "- TechCrunch". techcrunch.com. Получено 2018-05-24.
7. «1Password интегрируется с« Pwned Passwords », чтобы проверить, не просочились ли ваши пароли в Интернет». Получено 2018-05-24.
8. Конгер, Кейт. «1Password поможет вам узнать, взломан ли ваш пароль». Gizmodo. Получено 2018-05-24.
9. Кондон, Стефани. «Okta предлагает бесплатную многофакторную аутентификацию с новым продуктом One App | ZDNet». ZDNet. Получено 2018-05-24.
10. Корен, Майкл Дж. «Самая большая в мире база данных взломанных паролей теперь является расширением Chrome, которое автоматически проверяет ваш». Кварцевый. Получено 2018-05-24.
11. Wagenseil I, Пол. "Новое расширение Google Chrome находит ваши взломанные пароли". www.laptopmag.com.
12. «Google запускает расширение для проверки пароля, чтобы предупреждать пользователей о взломе данных». КровотечениеКомпьютер.
13. Дсуза, Мелиша (6 февраля 2019 г.). «Новое расширение Google Chrome 'Password CheckUp' проверяет, не было ли ваше имя пользователя или пароль взломано третьими лицами». Packt Hub.
14. Нараянан, Арвинд; Шматиков, Виталий. «Надежная деанонимизация больших разреженных наборов данных» (PDF).
15. Роберто Х. Баярдо; Ракеш Агравал (2005). Конфиденциальность данных через Optimal k-анонимизация (PDF). ICDE '05 Труды 21-й Международной конференции по инженерии данных. С. 217–28. Дои:10.1109 / ICDE.2005.42. ISBN  978-0-7695-2285-2. ISSN  1084-4627. S2CID  17044848. Деидентификация данных согласовывает спрос на раскрытие данных для исследовательских целей и требование конфиденциальности со стороны отдельных лиц. В этой статье предлагается и оценивается алгоритм оптимизации для мощной процедуры деидентификации, известной как k-анонимизация. А k-анонимизированный набор данных обладает тем свойством, что каждая запись неотличима как минимум от k - еще 1. Даже простые ограничения оптимизированного k-анонимность NP-сложна, что приводит к значительным вычислительным трудностям. Мы представляем новый подход к исследованию пространства возможных анонимизаций, которое укрощает комбинаторику проблемы, и разрабатываем стратегии управления данными, чтобы уменьшить зависимость от дорогостоящих операций, таких как сортировка. Экспериментируя с реальными данными переписи, мы показываем, что полученный алгоритм может найти оптимальные k-анонимизация в рамках двух репрезентативных стоимостных мер и широкого диапазона k. Мы также показываем, что алгоритм может обеспечить хорошую анонимизацию в обстоятельствах, когда входные данные или входные параметры не позволяют найти оптимальное решение в разумные сроки. Наконец, мы используем алгоритм для изучения влияния различных подходов к кодированию и вариаций проблем на качество и производительность анонимности. Насколько нам известно, это первый результат, демонстрирующий оптимальные k-анонимизация нетривиального набора данных в рамках общей модели проблемы.
16. Адам Мейерсон; Райан Уильямс (2004). О сложности оптимального K-Анонимность (PDF). PODS '04 Материалы двадцать третьего симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных. Нью-Йорк, штат Нью-Йорк: ACM. С. 223–8. Дои:10.1145/1055558.1055591. ISBN  978-1581138580. S2CID  6798963. Метод k-анонимизации был предложен в литературе как альтернативный способ раскрытия общедоступной информации, гарантирующий как конфиденциальность, так и целостность данных. Мы доказываем, что две общие версии оптимальной k-анонимизации отношений NP-трудны, включая версию с подавлением, которая сводится к выбору минимального количества записей для удаления из отношения. Мы также представляем алгоритм с полиномиальным временем для оптимальной k-анонимности, который достигает коэффициента аппроксимации, независимого от размера базы данных, когда k является постоянным. В частности, это приближение O (k log k), где константа в большом O не превышает 4. Однако время выполнения алгоритма экспоненциально по k. Несколько более умный алгоритм устраняет это условие, но является приближением O (k logm), где m - степень отношения. Мы считаем, что этот алгоритм потенциально может быть довольно быстрым на практике.
17. Кениг, Батья; Тасса, Тамир (2012). «Практический алгоритм приближения для оптимальной k-анонимности». Интеллектуальный анализ данных и обнаружение знаний. 25: 134–168. Дои:10.1007 / s10618-011-0235-9. S2CID  14158546.
18. Аггарвал, Чару С. (2005). "На k-Анонимность и проклятие размерности ». VLDB '05 - Материалы 31-й Международной конференции по очень большим базам данных. Тронхейм, Норвегия. CiteSeerX  10.1.1.60.3155. ISBN  1-59593-154-6.
19. де Монжуа, Ив-Александр; Сезар А. Идальго; Мишель Верлейсен; Винсент Д. Блондель (25 марта 2013 г.). «Уникальный среди толпы: границы приватности и мобильности человека» (PDF). Научные отчеты. 3: 1376. Bibcode:2013НатСР ... 3Э1376Д. Дои:10.1038 / srep01376. ЧВК  3607247. PMID  23524645.
20. Ангиули, Оливия; Джо Блитцштейн; Джим Уолдо. «Как деидентифицировать ваши данные». Очередь ACM. ACM.
21. Ангиули, Оливия; Джим Уолдо (Июнь 2016). «Статистические компромиссы между обобщением и подавлением при деидентификации крупномасштабных наборов данных». Международная конференция IEEE Computer Society по компьютерам, программному обеспечению и приложениям: 589–593. Дои:10.1109 / COMPSAC.2016.198. ISBN  978-1-4673-8845-0. S2CID  17716908.
22. Ли, Люси; Пал, Биджита; Али, Джунаде; Салливан, Ник; Чаттерджи, Рахул; Ристенпарт, Томас (4 сентября 2019 г.). «Протоколы проверки взломанных учетных данных». arXiv:1905.13737 [cs.CR ].
23. «Узнайте, был ли введен ваш пароль - без отправки его на сервер». Ars Technica. Получено 2018-05-24.
24. "1Password болтает при проверке" введенного пароля "- TechCrunch". techcrunch.com. Получено 2018-05-24.
25. Али, Джунаде; Дё, Владимир (2020). «Практическая анонимность на основе хэша для MAC-адресов». 17-я Международная конференция по безопасности и криптографии (SECRYPT 2020): 572–579. arXiv:2005.06580. Дои:10.5220/0009825105720579. ISBN  978-989-758-446-6. S2CID  218629946.
26. Томас, Курт; Пуллман, Дженнифер; Йео, Кевин; Рагхунатан, Анант; Келли, Патрик Гейдж; Инверницци, Лука; Бенко, Борбала; Пьетрашек, Тадек; Патель, Сарвар; Бонех, Дэн; Бурштейн, Эли (2019). Защита учетных записей от переполнения учетных данных с помощью предупреждений о взломе пароля. С. 1556–1571. ISBN  9781939133069. Получено 22 мая 2020.
27. Али, Джунаде; Дё, Владимир (2020). «Практическая анонимность на основе хэша для MAC-адресов». 17-я Международная конференция по безопасности и криптографии (SECRYPT 2020): 572–579. arXiv:2005.06580. Дои:10.5220/0009825105720579. ISBN  978-989-758-446-6. S2CID  218629946.
28. Демир, Левент; Кумар, Амрит; Кунч, Матье; Лораду, Седрик (2018). «Ловушки хеширования для обеспечения конфиденциальности». Опросы и учебные пособия по коммуникациям, IEEE Communications Society. 20 (1): 551. Дои:10.1109 / COMST.2017.2747598. S2CID  3571244. Получено 22 мая 2020.