k-анонимность

Свойство определенных анонимных данных

k -анонимность — это свойство, которым обладают определенные обезличенные данные . Термин k -анонимность был впервые введен Пьерангелой Самарати и Латанией Суини в статье, опубликованной в 1998 году ^[1] , хотя эта концепция восходит к статье Торе Далениуса 1986 года. ^[2]

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

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

Чтобы использовать k -анонимность для обработки набора данных, чтобы его можно было опубликовать с защитой конфиденциальности, специалист по данным должен сначала изучить набор данных и решить, является ли каждый атрибут (столбец) идентификатором ( идентифицирующим), неидентифицирующим (неидентифицирующим) ), или квазиидентификатор (в некоторой степени идентифицирующий). Идентификаторы, такие как имена, подавляются, неидентифицирующие значения могут оставаться, а квазиидентификаторы необходимо обрабатывать так, чтобы каждая отдельная комбинация квазиидентификаторов обозначала как минимум k записей.

В приведенной ниже таблице в качестве примера представлена ​​вымышленная неанонимизированная база данных, состоящая из записей пациентов вымышленной больницы. Столбец « Имя » является идентификатором, «Возраст» , «Пол» , «Штат проживания» и «Религия» — квазиидентификаторами, а «Болезнь» — неидентифицирующим конфиденциальным значением. А как насчет роста и веса ? Являются ли они также неидентифицирующими конфиденциальными значениями или являются квазиидентификаторами?

В этих данных содержится 6 атрибутов и 10 записей. Существует два распространенных метода достижения k -анонимности для некоторого значения k :

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

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

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

Критика k -анонимности

Следующий пример демонстрирует недостаток k -анонимности: могут существовать другие записи данных, которые можно связать с переменными, которые предположительно неидентифицируют. Например, предположим, что злоумышленник может получить журнал от человека, который измерял показатели жизнедеятельности в рамках исследования, и узнает, что Кишор находился в больнице 30 апреля и его рост 180 см. Эту информацию можно использовать, чтобы связаться с «анонимной» базой данных (которая могла быть опубликована в Интернете) и узнать, что у Кишора есть сердечно-сосудистое заболевание. Злоумышленник, знающий, что Кишор посетил больницу 30 апреля, может сделать вывод об этом, просто зная, что рост Кишора 180 см, вес примерно 80–82 кг, и он родом из Карнатаки.

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

Хотя k-анонимность защищает от раскрытия личности, она не защищает от раскрытия конкретных атрибутов. Это становится проблематичным, когда злоумышленники обладают базовыми знаниями. Кроме того, отсутствие разнообразия в чувствительных областях может привести к раскрытию личной информации. В таких сценариях выбор ℓ-разнообразия может обеспечить более надежную защиту конфиденциальности.[1]

Мейерсон и Уильямс (2004) продемонстрировали, что оптимальная k -анонимность является NP-сложной проблемой, однако эвристические методы, такие как k -Optimize, предложенные Баярдо и Агравалом (2005), часто дают эффективные результаты. ^{[7] [8]} Практический алгоритм аппроксимации, который позволяет решить проблему k -анонимизации с гарантией аппроксимации, был представлен Кенигом и Тассой. ^[9] ${\displaystyle O(\log k)}$

Атаки

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

• Атака на однородность . Эта атака использует случай, когда все значения конфиденциального значения в наборе из k записей идентичны. В таких случаях, даже если данные были k -анонимизированы, чувствительное значение для набора из k записей может быть точно предсказано.
• Атака с использованием фоновых знаний . Эта атака использует связь между одним или несколькими атрибутами квазиидентификатора с конфиденциальным атрибутом, чтобы уменьшить набор возможных значений для конфиденциального атрибута. Например, Мачанавайджхала, Кифер, Герке и Венкитасубраманиам (2007) показали, что знание того, что сердечные приступы происходят с меньшей частотой у японских пациентов, можно использовать для сужения диапазона значений чувствительного признака заболевания пациента.
• Атака с понижением кодирования . Эта атака, представленная в 2022 году Алони Коэном, использует способ, которым алгоритмы анонимности объединяют атрибуты в отдельных записях. Поскольку агрегирование является детерминированным, можно провести реверс-инжиниринг исходного образа данных и во многих случаях выявить исходные данные, которые должны были быть защищены. Эта атака не требует базовых знаний, но усиливается ими. ^[10]

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

K -анонимизация не является хорошим методом анонимизации многомерных наборов данных. ^[11]

Также было показано, что k -анонимность может исказить результаты набора данных, если она непропорционально подавляет и обобщает точки данных с нерепрезентативными характеристиками. ^[12] Однако алгоритмы подавления и обобщения, используемые для k -анонимизации наборов данных, могут быть изменены, чтобы они не оказывали такого искажения. ^[13]

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

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

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

1. Самарати, Пьерангела; Суини, Латанья (1998). «Защита конфиденциальности при раскрытии информации: k-анонимность и ее обеспечение посредством обобщения и подавления» (PDF) . Гарвардская лаборатория конфиденциальности данных . Проверено 12 апреля 2017 г.
2. Торе Далениус, «В поисках иголки в стоге сена», Журнал официальной статистики, Том. 2, № 3, 1986, стр. 326–336.
3. Самарати, Пьерангела (ноябрь 2001 г.). «Защита личности респондентов при публикации микроданных» (PDF) . Транзакции IEEE по знаниям и инженерии данных . 13 (6): 1010–1027. дои : 10.1109/69.971193. S2CID  561716.
4. Суини, Латанья. «Безопасность баз данных: к-анонимность» . Проверено 19 января 2014 г.
5. Суини, Латанья (2002). «К-анонимность: модель защиты конфиденциальности» (PDF) . Международный журнал неопределенности, нечеткости и систем, основанных на знаниях . 10 (5): 557–570. дои : 10.1142/S0218488502001648. S2CID  361794.
6. Нарайанан, Арвинд; Шматиков, Виталий. «Надежная деанонимизация больших разреженных наборов данных» (PDF) .
7. Роберто Дж. Баярдо; Ракеш Агравал (2005). «Конфиденциальность данных посредством оптимальной k-анонимизации». 21-я Международная конференция по инженерии данных (ICDE'05) (PDF) . стр. 217–228. дои : 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 -анонимизацию нетривиального набора данных в рамках общей модели задачи.
8. Адам Мейерсон; Райан Уильямс (2004). «О сложности оптимальной К-анонимности». Материалы двадцать третьего симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных (PDF) . Нью-Йорк, штат Нью-Йорк: ACM. стр. 223–228. дои : 10.1145/1055558.1055591. ISBN 978-1581138580. S2CID  6798963. Метод k -анонимизации был предложен в литературе как альтернативный способ раскрытия публичной информации, обеспечивая при этом как конфиденциальность, так и целостность данных. Мы доказываем, что два общих варианта оптимальной k -анонимизации отношений являются NP-трудными, включая вариант с подавлением, который сводится к выбору минимального числа записей для удаления из отношения. Мы также представляем алгоритм с полиномиальным временем для оптимальной k -анонимности, который обеспечивает коэффициент аппроксимации, не зависящий от размера базы данных, когда k постоянно. В частности, это O ( k  log  k )-аппроксимация, где константа в большом O не превышает 4. Однако время выполнения алгоритма является экспоненциальным по k . Немного более умный алгоритм устраняет это условие, но представляет собой O ( k  log  m )-аппроксимацию, где m — степень отношения. Мы считаем, что этот алгоритм потенциально может быть довольно быстрым на практике.
9. Кениг, Батя; Тасса, Тамир (2012). «Практический алгоритм аппроксимации для оптимальной k -анонимности». Интеллектуальный анализ данных и обнаружение знаний . 25 : 134–168. дои : 10.1007/s10618-011-0235-9. S2CID  14158546.
10. Атаки на защиту деидентификации, Алони Коэн, USENIX Security 2022, обладатель награды «Выдающаяся бумага». https://www.usenix.org/conference/usenixsecurity22/presentation/cohen
11. Аггарвал, Чару К. (2005). «О k -анонимности и проклятии размерности». VLDB '05 – Материалы 31-й Международной конференции по очень большим базам данных . Тронхейм, Норвегия. CiteSeerX 10.1.1.60.3155 . ISBN  1-59593-154-6.
12. Ангиули, Оливия; Джо Блицштейн; Джим Уолдо . «Как деидентифицировать ваши данные». Очередь АКМ . АКМ.
13. Ангиули, Оливия; Джим Уолдо (июнь 2016 г.). «Статистические компромиссы между обобщением и подавлением при деидентификации крупномасштабных наборов данных». 40-я ежегодная конференция IEEE по компьютерному программному обеспечению и приложениям (COMPSAC) , 2016 г. стр. 589–593. doi :10.1109/COMPSAC.2016.198. ISBN 978-1-4673-8845-0. S2CID  17716908.