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

k-анонимность — это свойство анонимизированного набора данных, гарантирующее, что информация о каждом субъекте, содержащемся в этом наборе, не может быть выделена из группы, состоящей как минимум из k субъектов. Достигается это путём обобщения или подавления (удаления) идентифицирующих атрибутов (квази-идентификаторов) до тех пор, пока каждая запись в данных не станет неотличима от k-1 других записей по набору этих атрибутов. Понятие введено в 2002 году Латой Свани и Пьером Самиром как одна из первых формальных моделей защиты приватности при публикации данных.

¶История и предпосылки появления

До появления концепции k-анонимности основным методом деидентификации данных было удаление прямых идентификаторов (имён, номеров паспортов, телефонов). Однако в конце 1990-х годов было показано, что этого недостаточно. Классическим примером стала атака на анонимизированные медицинские данные штата Массачусетс (США), проведённая в 1997 году Латаньей Суини. Она сопоставила обезличенные записи о госпитализации с открытым списком избирателей, используя комбинацию почтового индекса, даты рождения и пола (квази-идентификаторы), и таким образом идентифицировала медицинские записи губернатора Уильяма Уэлда. Этот инцидент продемонстрировал, что простое удаление имён не гарантирует анонимности, и стимулировал разработку формальных моделей защиты.

В 2002 году Л. Суини и П. Самир формализовали модель k-анонимности в работе «k-Anonymity: A Model for Protecting Privacy». Они предложили математический критерий, при котором риск повторной идентификации субъекта в опубликованном наборе данных не превышает 1/k.

¶Основные понятия и определения

¶Квази-идентификаторы

Квази-идентификаторы (QID) — это набор атрибутов, которые сами по себе не являются уникальными идентификаторами, но в совокупности могут быть сопоставлены с внешними данными для идентификации субъекта. Типичные примеры: почтовый индекс, дата рождения, пол, раса, профессия. Выбор QID критически важен для обеспечения k-анонимности.

¶Классы эквивалентности

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

¶Атака на связывание (linkage attack)

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

¶Методы достижения k-анонимности

Для приведения набора данных к состоянию k-анонимности используются два основных подхода:

¶Обобщение (generalization)

Замена точных значений квази-идентификаторов на более общие. Например:

• Точный возраст (34 года) заменяется на возрастной диапазон (30–39 лет).
• Точный почтовый индекс (12345) заменяется на первые три цифры (123**).
• Название улицы заменяется на район или город.

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

¶Подавление (suppression)

Удаление отдельных записей или значений атрибутов, которые невозможно обобщить без потери анонимности. Например, если в наборе данных есть всего один человек с определённым редким заболеванием в конкретном районе, его запись может быть полностью удалена. Подавление может быть на уровне ячейки (удаление одного значения) или на уровне кортежа (удаление всей записи).

¶Алгоритмы реализации

Существует несколько алгоритмов, реализующих k-анонимность. Наиболее известные:

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

¶Критика и ограничения

Несмотря на свою популярность, модель k-анонимности имеет ряд существенных недостатков, которые были выявлены в последующие годы.

¶Атаки на однородность (homogeneity attack)

Если в одном классе эквивалентности все записи имеют одинаковое значение чувствительного атрибута (например, диагноза «ВИЧ»), то даже при k=100 злоумышленник узнаёт, что все субъекты в этом классе имеют данный диагноз. k-анонимность не защищает от раскрытия информации, если чувствительные данные внутри класса не разнообразны.

¶Атаки на фоновые знания (background knowledge attack)

Злоумышленник может использовать дополнительные знания о субъекте для сужения возможных значений чувствительного атрибута. Например, если известно, что пациент — мужчина, а в классе эквивалентности есть как мужчины, так и женщины, то злоумышленник может исключить женские диагнозы. k-анонимность не учитывает внешние знания атакующего.

¶Потеря полезности данных

Сильное обобщение или подавление, необходимое для достижения высокого k, может сделать данные практически бесполезными для анализа. Например, обобщение возраста до диапазона «20–60 лет» уничтожает возможность изучения возрастных закономерностей.

¶Отсутствие защиты от атак на композицию

Если один и тот же набор данных публикуется несколько раз с разными уровнями обобщения, злоумышленник может объединить эти публикации для восстановления исходных данных. Это называется атакой на композицию.

¶Развитие и альтернативы

В ответ на ограничения k-анонимности были разработаны более совершенные модели:

• l-разнообразие (l-diversity): требует, чтобы в каждом классе эквивалентности было не менее l «хорошо представленных» значений чувствительного атрибута. Это защищает от атак на однородность.
• t-близость (t-closeness): требует, чтобы распределение чувствительного атрибута в каждом классе эквивалентности было близко к его распределению во всём наборе данных. Это защищает от атак на фоновые знания.
• Дифференциальная приватность (differential privacy): более строгая математическая модель, которая добавляет случайный шум к результатам запросов, гарантируя, что присутствие или отсутствие любого субъекта в базе данных не влияет на результат. Дифференциальная приватность считается более надёжной, чем k-анонимность, но может быть сложнее в реализации.

¶Применение

Модель k-анонимности и её производные находят применение в различных областях, где требуется публикация данных с сохранением приватности:

• Медицинские исследования: публикация обезличенных данных о пациентах для эпидемиологических исследований.
• Государственная статистика: публикация данных переписей населения, социальных опросов.
• Маркетинговые исследования: анализ покупательского поведения без раскрытия личных данных клиентов.
• Образовательные учреждения: публикация данных об успеваемости студентов для аккредитационных отчётов.

В России вопросы анонимизации данных регулируются Федеральным законом «О персональных данных» (№ 152-ФЗ), который требует обезличивания персональных данных при их обработке в статистических или исследовательских целях. Роскомнадзор выпускает методические рекомендации по обезличиванию, в которых k-анонимность упоминается как один из возможных методов.

¶Интересные факты

• Термин «k-анонимность» происходит от латинского «k» — переменная, обозначающая минимальный размер группы.
• Первая реализация алгоритма k-анонимности была выполнена в 2002 году на языке Java.
• В 2010 году была опубликована работа, показавшая, что k-анонимность NP-трудна для оптимального обобщения, что делает задачу поиска наилучшего решения вычислительно сложной.
• Модель k-анонимности используется в некоторых коммерческих продуктах для анонимизации данных, например, в ARX Data Anonymization Tool.