Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Методы k -анонимизации [ править ]

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

ИмяВозрастПолГосударство резидентстваРелигияБолезнь
Рамша30женскийТамил НадуИндуистскийРак
Яду24женскийКералаИндуистскийВирусная инфекция
Салима28 годженскийТамил НадуМусульманинТуберкулез
Солнечно27МужчинаКарнатакаПарсиНет болезни
Джоан24женскийКералаХристианинСвязанный с сердцем
Bahuksana23МужчинаКарнатакаБуддистТуберкулез
Рамба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 -Optimize, предложенные Баярдо и Агравалом (2005), часто дают эффективные результаты. [15] [16] Практический алгоритм аппроксимации, который позволяет решить проблему k -анонимизации с гарантией аппроксимации, был представлен Кенигом и Тассой. [17]

Возможные атаки [ править ]

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

  • Атака на однородность : эта атака использует случай, когда все значения для чувствительного значения в наборе из k записей идентичны. В таких случаях, даже если данные были k -анонимизированы, чувствительное значение для набора k записей может быть точно предсказано.
  • Атака фоновых знаний : эта атака использует связь между одним или несколькими атрибутами квазиидентификатора с чувствительным атрибутом, чтобы уменьшить набор возможных значений для чувствительного атрибута. Например, Machanavajjhala, Kifer, Gehrke и Venkitasubramaniam (2007) показали, что знание того, что сердечные приступы происходят с меньшей частотой у японских пациентов, можно использовать для сужения диапазона значений чувствительного атрибута болезни пациента.

Предостережения [ править ]

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

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

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

K- анонимность на основе хеша [ править ]

Основанная на хэшах k- анонимность была в значительной степени разработана Джунадой Али , первоначально для предотвращения взломанной проверки учетных данных [22] [23] [24], а затем для анонимизации MAC-адресов в реальном времени . [25]

Этот подход работает за счет взятия криптографического хеша одномерных данных и его усечения так, чтобы были, по крайней мере, коллизии хешей. Такой подход позволяет осуществлять эффективный анонимный поиск в больших наборах данных, таких как взломанные пароли. [26] Этот подход может также использоваться для обеспечения формально демонстрируемого уровня анонимности конфиденциальных данных, позволяя найти точный компромисс между утечкой информации и функциональностью (например, для анонимизации MAC-адреса ). [27] [28]

См. Также [ править ]

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

Ссылки [ править ]

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