k -анонимность — это свойство, которым обладают некоторые анонимизированные данные . Термин k -анонимность был впервые введен Пьеранджелой Самарати и Латанией Суини в статье, опубликованной в 1998 году, [1] хотя сама концепция восходит к статье Торе Далениуса 1986 года. [2]
k -анонимность — это попытка решить проблему «Данные структурированные по полю данные, относящиеся к конкретному человеку, выпустить данные с научными гарантиями того, что лица, являющиеся субъектами данных, не могут быть повторно идентифицированы, пока данные остаются практически полезными». [3] [4] [5] Говорят, что выдача данных имеет свойство k -анонимности, если информация о каждом лице, содержащаяся в выдаче, не может быть отделена по крайней мере от информации о лицах, информация о которых также появляется в выдаче. Гарантии, предоставляемые k -анонимностью, являются желательными, а не математическими.
Чтобы использовать k -анонимность для обработки набора данных, чтобы его можно было выпустить с защитой конфиденциальности, специалист по данным должен сначала изучить набор данных и решить, является ли каждый атрибут (столбец) идентификатором ( идентифицирующим), неидентификатором (не идентифицирующим) или квазиидентификатором (в некоторой степени идентифицирующим). Идентификаторы, такие как имена, подавляются, неидентифицирующие значения могут оставаться, а квазиидентификаторы должны обрабатываться таким образом, чтобы каждая отдельная комбинация квазиидентификаторов обозначала не менее k записей.
В таблице-примере ниже представлена вымышленная, неанонимная база данных, состоящая из записей пациентов вымышленной больницы. Столбец Имя — это идентификатор, Возраст , Пол , Штат проживания и Религия — квазиидентификаторы, а Заболевание — неидентифицирующее чувствительное значение. Но что насчет Роста и Веса ? Являются ли они также неидентифицирующими чувствительными значениями или они являются квазиидентификаторами?
В этих данных есть 6 атрибутов и 10 записей. Существует два распространенных метода достижения k- анонимности для некоторого значения k :
В следующей таблице показана анонимизированная база данных.
Эти данные имеют 2-анонимность относительно атрибутов Возраст , Пол и Штат проживания , поскольку для любой комбинации этих атрибутов, найденных в любой строке таблицы, всегда есть по крайней мере 2 строки с этими точными атрибутами. Атрибуты, доступные злоумышленнику, называются квазиидентификаторами . Каждый кортеж квазиидентификаторов встречается по крайней мере в k записях для набора данных с k -анонимностью. [6]
Следующий пример демонстрирует ошибку с k- анонимностью: могут существовать другие записи данных, которые могут быть связаны с переменными, которые предположительно не являются идентифицирующими. Например, предположим, что злоумышленник может получить журнал от человека, который измерял жизненные показатели в рамках исследования, и узнает, что Кишор был в больнице 30 апреля и его рост 180 см. Эту информацию можно использовать для связи с «анонимной» базой данных (которая могла быть опубликована в Интернете) и узнать, что у Кишора заболевание сердца. Злоумышленник, который знает, что Кишор посетил больницу 30 апреля, может сделать этот вывод, просто зная, что рост Кишора 180 см, вес примерно 80–82 кг и он из Карнатаки.
Корень этой проблемы — основная проблема с k- анонимностью: нет способа математически однозначно определить, является ли атрибут идентификатором, квазиидентификатором или неидентифицирующим чувствительным значением. Фактически, все значения потенциально идентифицируются в зависимости от их распространенности в популяции и от вспомогательных данных, которые могут быть у злоумышленника. Другие механизмы конфиденциальности, такие как дифференциальная конфиденциальность, не имеют этой проблемы.
Хотя k-анонимность защищает от раскрытия личности, она не защищает от раскрытия конкретных атрибутов. Это становится проблематичным, когда злоумышленники обладают фоновыми знаниями. Кроме того, отсутствие разнообразия в чувствительных доменах может привести к раскрытию личной информации. В таких сценариях выбор ℓ-разнообразия может обеспечить более надежную защиту конфиденциальности.[1]
Мейерсон и Уильямс (2004) продемонстрировали, что оптимальная k -анонимность является NP-трудной задачей, однако эвристические методы, такие как k -оптимизация, предложенная Байярдо и Агравалом (2005), часто дают эффективные результаты. [7] [8] Практический алгоритм аппроксимации, позволяющий решать задачу k -анонимизации с гарантией аппроксимации, был представлен Кенигом и Тассой. [9]
Хотя k -анонимность является относительно простым в реализации подходом для деидентификации набора данных перед публикацией, он подвержен многим атакам. Когда злоумышленнику доступны фоновые знания, такие атаки становятся еще более эффективными. Такие атаки включают:
Поскольку k -анонимизация не включает в себя никакой рандомизации, злоумышленники могут делать надежные, однозначные выводы о наборах данных, которые могут нанести вред отдельным лицам. Например, если известно, что 19-летний Джон из Кералы находится в базе данных выше, то можно с уверенностью сказать, что у него либо рак, либо сердечное заболевание, либо вирусная инфекция.
K -анонимизация не является хорошим методом для анонимизации многомерных наборов данных. [11]
Также было показано, что k -анонимность может исказить результаты набора данных, если она непропорционально подавляет и обобщает точки данных с нерепрезентативными характеристиками. [12] Однако алгоритмы подавления и обобщения, используемые для k -анонимизации наборов данных, можно изменить так, чтобы они не имели такого эффекта искажения. [13]
Деидентификация данных примиряет потребность в раскрытии данных для исследовательских целей и потребность в конфиденциальности от отдельных лиц. В этой статье предлагается и оценивается алгоритм оптимизации для мощной процедуры деидентификации, известной как k -анонимизация. K -анонимизированный набор данных обладает тем свойством, что каждая запись неотличима как минимум от k − 1 других. Даже простые ограничения оптимизированной k -анонимности являются NP-трудными, что приводит к значительным вычислительным проблемам. Мы представляем новый подход к исследованию пространства возможных анонимизаций, который укрощает комбинаторику проблемы, и разрабатываем стратегии управления данными для снижения зависимости от дорогостоящих операций, таких как сортировка. С помощью экспериментов на реальных данных переписи мы показываем, что полученный алгоритм может находить оптимальные k -анонимизации при двух репрезентативных мерах стоимости и широком диапазоне k. Мы также показываем, что алгоритм может производить хорошие анонимизации в обстоятельствах, когда входные данные или входные параметры исключают нахождение оптимального решения за разумное время. Наконец, мы используем алгоритм для изучения влияния различных подходов к кодированию и вариаций задач на качество и производительность анонимизации. Насколько нам известно, это первый результат, демонстрирующий оптимальную k -анонимизацию нетривиального набора данных в рамках общей модели задачи.
Методика k -анонимизации была предложена в литературе как альтернативный способ раскрытия публичной информации, обеспечивая при этом как конфиденциальность данных, так и целостность данных. Мы доказываем, что две общие версии оптимальной k -анонимизации отношений являются NP-трудными, включая версию подавления, которая сводится к выбору минимального количества записей для удаления из отношения. Мы также представляем полиномиальный алгоритм для оптимальной k -анонимности, который достигает коэффициента аппроксимации, независимого от размера базы данных, когда k является постоянным. В частности, это O ( k log k )-аппроксимация, где константа в большом O не больше 4. Однако время выполнения алгоритма экспоненциально по k . Немного более умный алгоритм устраняет это условие, но является O ( k log m )-аппроксимацией, где m - степень отношения. Мы считаем, что этот алгоритм потенциально может быть довольно быстрым на практике.
