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

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

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

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

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

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

Пациенты, прошедшие лечение в исследовании 30 апреля
Имя	Возраст	Пол	Высота	Масса	Государство проживания	Религия	Болезнь
Рамша	30	Женский	165 см	72 кг	Тамил Наду	индуистский	Рак
Распространение	24	Женский	162 см	70 кг	Керала	индуистский	Вирусная инфекция
Салима	28	Женский	170 см	68 кг	Тамил Наду	мусульманин	Туберкулез
Солнечно	27	Мужской	170 см	75 кг	Карнатака	Парси	Нет болезни
Джоан	24	Женский	165 см	71 кг	Керала	христианин	Связанный с сердцем
Бахуксана	23	Мужской	160 см	69 кг	Карнатака	буддист	Туберкулез
Рамбха	19	Мужской	167 см	85 кг	Керала	индуистский	Рак
Кишор	29	Мужской	180 см	81 кг	Карнатака	индуистский	Связанный с сердцем
Джонсон	17	Мужской	175 см	79 кг	Керала	христианин	Связанный с сердцем
Джон	19	Мужской	169 см	82 кг	Керала	христианин	Вирусная инфекция

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

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

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

Пациенты, прошедшие лечение в исследовании 30 апреля
Имя	Возраст	Пол	Высота	Масса	Государство проживания	Религия	Болезнь
*	20 < Возраст ≤ 30	Женский	165 см	72 кг	Тамил Наду	*	Рак
*	20 < Возраст ≤ 30	Женский	162 см	70 кг	Керала	*	Вирусная инфекция
*	20 < Возраст ≤ 30	Женский	170 см	68 кг	Тамил Наду	*	Туберкулез
*	20 < Возраст ≤ 30	Мужской	170 см	75 кг	Карнатака	*	Нет болезни
*	20 < Возраст ≤ 30	Женский	165 см	71 кг	Керала	*	Связанный с сердцем
*	20 < Возраст ≤ 30	Мужской	160 см	69 кг	Карнатака	*	Туберкулез
*	Возраст ≤ 20	Мужской	167 см	85 кг	Керала	*	Рак
*	20 < Возраст ≤ 30	Мужской	180 см	81 кг	Карнатака	*	Связанный с сердцем
*	Возраст ≤ 20	Мужской	175 см	79 кг	Керала	*	Связанный с сердцем
*	Возраст ≤ 20	Мужской	169 см	82 кг	Керала	*	Вирусная инфекция

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

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

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

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

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

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

Атаки

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

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

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

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

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

См. также

Ссылки

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

[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) .

[Optimal-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. дои : 10.1109/COMPSAC.2016.198 . ISBN 978-1-4673-8845-0 . S2CID 17716908 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]