t-близость¶

t-близость — это понятие в теории баз данных, используемое для оценки степени анонимности данных, опубликованных в виде таблицы, после применения методов деидентификации, в частности, после обеспечения k-анонимности. t-близость является одним из критериев, позволяющих определить, насколько хорошо защищены чувствительные атрибуты (например, диагнозы, доходы, политические взгляды) от атак на основе знания фоновой информации или атак на однородность. Она была предложена в 2006 году исследователями Нинхуи Ли, Тяньчэном Ли и С. Венкатасубраманианом как развитие и дополнение к l-разнообразию.

¶Определение и цель

t-близость требует, чтобы распределение значений чувствительного атрибута в любом кластере эквивалентности (группе записей с одинаковыми квазиидентификаторами) было «близким» к распределению этого атрибута во всей таблице. Мера «близости» определяется параметром t — пороговым значением, которое задаёт максимально допустимое расстояние между двумя распределениями. Если расстояние между распределением в кластере и глобальным распределением не превышает t, то свойство считается выполненным.

Формально, пусть \( P \) — распределение значений чувствительного атрибута во всей таблице, а \( Q \) — распределение того же атрибута в конкретном кластере эквивалентности. Тогда таблица удовлетворяет t-близости, если для каждого кластера эквивалентности выполняется неравенство:

\[ D(P, Q) \leq t \]

где \( D \) — некоторая функция расстояния между распределениями (например, расстояние Вассерштейна, расстояние Кульбака-Лейблера или вариационное расстояние).

¶Предпосылки возникновения

¶Ограничения k-анонимности

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

¶Ограничения l-разнообразия

l-разнообразие требует, чтобы в каждом кластере эквивалентности было не менее \( l \) «хорошо представленных» значений чувствительного атрибута. Однако этот критерий не учитывает семантическую близость значений. Например, если в кластере есть два значения — «грипп» и «пневмония» — это может быть недостаточно для защиты, если оба относятся к респираторным заболеваниям, или если распределение в кластере сильно отличается от общего распределения. Кроме того, l-разнообразие неэффективно при атаках на основе фоновых знаний, когда злоумышленник знает, что конкретный человек не может иметь определённое значение (например, «ВИЧ»).

¶Методы измерения расстояния между распределениями

Для вычисления \( D(P, Q) \) в t-близости могут использоваться различные метрики. Выбор метрики влияет на строгость критерия и вычислительную сложность.

¶Вариационное расстояние (расстояние полной вариации)

Определяется как половина суммы абсолютных разностей вероятностей:

\[ \delta(P, Q) = \frac{1}{2} \sum_{i} |p_i - q_i| \]

Это простая метрика, но она не учитывает порядок или семантику значений (например, различие между «доход 10 000» и «доход 10 001» считается таким же, как между «доход 10 000» и «доход 1 000 000»).

¶Расстояние Кульбака-Лейблера (KL-дивергенция)

\[ D_{KL}(P || Q) = \sum_{i} p_i \log \frac{p_i}{q_i} \]

Не является симметричной метрикой и может быть бесконечной, если в \( Q \) есть нулевые вероятности. Используется реже из-за этих недостатков.

¶Расстояние Вассерштейна (Earth Mover’s Distance)

Учитывает «стоимость» перемещения вероятностной массы между значениями, что позволяет семантически интерпретировать близость. Например, для числовых атрибутов (доход, возраст) расстояние между 10 000 и 20 000 будет меньше, чем между 10 000 и 100 000. Это делает его более предпочтительным для t-близости, особенно при работе с упорядоченными или числовыми данными.

¶Свойства и критика

¶Преимущества

• Учёт фоновых знаний: t-близость позволяет моделировать атаки, при которых злоумышленник знает глобальное распределение чувствительного атрибута.
• Семантическая интерпретация: при использовании расстояния Вассерштейна t-близость учитывает, насколько значения близки друг к другу по смыслу.
• Гибкость: параметр t можно настраивать в зависимости от требуемого уровня защиты.

¶Недостатки

• Сложность выбора метрики: разные метрики дают разные результаты, и выбор подходящей зависит от конкретной задачи.
• Высокая вычислительная сложность: для больших таблиц вычисление распределений и расстояний может быть затратным.
• Необходимость знания глобального распределения: в некоторых случаях глобальное распределение может быть недоступно или нерепрезентативно.
• Возможность утечки информации через глобальное распределение: если злоумышленник знает глобальное распределение, это может облегчить атаку.

¶Применение

t-близость используется в задачах публикации статистических данных, медицинских записей, данных переписи населения и других конфиденциальных наборов, где требуется сохранить полезность данных для анализа, но при этом защитить индивидуальную информацию. Она часто применяется в сочетании с другими методами анонимизации, такими как обобщение (generalization) и подавление (suppression), для достижения компромисса между анонимностью и точностью данных.

¶Пример

Рассмотрим таблицу с диагнозами пациентов. Пусть глобальное распределение диагнозов: грипп — 50%, пневмония — 30%, рак — 20%. После k-анонимизации получен кластер эквивалентности, в котором распределение: грипп — 60%, пневмония — 10%, рак — 30%. Если выбрать t=0.2 и использовать вариационное расстояние, то:

\[ \delta = 0.5 \times (|0.5-0.6| + |0.3-0.1| + |0.2-0.3|) = 0.5 \times (0.1 + 0.2 + 0.1) = 0.2 \]

Поскольку \( \delta \leq t \), свойство выполняется. Если бы распределение было: грипп — 100%, пневмония — 0%, рак — 0%, то \( \delta = 0.5 \times (0.5 + 0.3 + 0.2) = 0.5 > 0.2 \), и t-близость не была бы достигнута.

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

t-близость является частью семейства моделей анонимности, включающего также k-анонимность, l-разнообразие, (α, k)-анонимность, δ-присутствие и дифференциальную приватность. Последняя, предложенная Синтией Дворк в 2006 году, считается более строгой и математически обоснованной моделью, но её применение может приводить к большей потере полезности данных. t-близость, в отличие от дифференциальной приватности, не требует добавления случайного шума и может быть реализована детерминированными методами обобщения.

¶Источники

1. Li, N., Li, T., & Venkatasubramanian, S. (2007). t-Closeness: Privacy Beyond k-Anonymity and l-Diversity. Proceedings of the 23rd International Conference on Data Engineering (ICDE).
2. Sweeney, L. (2002). k-Anonymity: A Model for Protecting Privacy. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems.
3. Machanavajjhala, A., Gehrke, J., Kifer, D., & Venkitasubramaniam, M. (2006). l-Diversity: Privacy Beyond k-Anonymity. Proceedings of the 22nd International Conference on Data Engineering (ICDE).
4. Dwork, C. (2006). Differential Privacy. Proceedings of the 33rd International Colloquium on Automata, Languages and Programming.