Кратко — на примере и с пояснениями.
Пример (упрощённый, на реальном принципе утечки как в кейсе Sweeney/массачусетских пациентов или Netflix):
Оригинальная таблица (квазиидентификаторы: ZIP, возраст, пол; чувствительная колонка: диагноз)
- запись A: ZIP $02138$, возраст $28$, пол F, диагноз HIV
- запись B: ZIP $02139$, возраст $27$, пол F, диагноз HIV
- запись C: ZIP $02138$, возраст $29$, пол F, диагноз HIV
- запись D: ZIP $02150$, возраст $35$, пол M, диагноз Flu
- запись E: ZIP $02150$, возраст $36$, пол M, диагноз Flu
k-анонимность: допустим мы достигаем $k=3$ путём обобщения ZIP до первых трёх цифр и возрастов до интервалов:
- группа 1 (ZIP $021$, возраст $25\text{–}29$, пол F): все записи A,B,C — диагноз во всех случаях HIV
- группа 2 (ZIP $021$, возраст $35\text{–}36$, пол M): D,E — Flu (здесь $k=2$, но для примера)
Почему k-анонимность НЕ защищает приватность в этом кейсе:
- цель k-анонимности — скрыть индивидуальность в группе размера $\ge k$. Но если в группе чувствительное значение не разнообразно (все HIV), то знание принадлежности человека к этой группе раскрывает диагноз — это атрибутное раскрытие (attribute disclosure). Сопутствующая вспомогательная информация — ZIP, возраст, пол — позволяет атакующему установить принадлежность к группе, и тогда диагноз известен с высокой уверенностью. Это реальный тип атак, использовавшийся для де-анонимизации медицинских данных и Netflix.
Как дифференциальная приватность решает проблему (интуитивно и формула):
- Дифференциальная приватность (DP) требует, чтобы выход механизма практически не менялся при добавлении/удалении любой отдельной записи:
$\mathrm{Pr}[\mathcal{M}(D)\in S]\le e^{\epsilon }\mathrm{Pr}[\mathcal{M}(D^{\prime })\in S]$ для любых соседних баз $D,D^{\prime }$ и множества выходов $S$.
- Практически вместо публикации «сгруппированных сырьевых строк» DP отвечает через шумированные статистики. Например, чтобы опубликовать количество людей с HIV, берут истинный счёт $c$ и добавляют шум Лапласа:
$\tilde{c}=c+\eta ,\eta \sim \mathrm{Laplace}(\Delta f/\epsilon )$.
Для счётчика чувствительность $\Delta f=1$, значит шум имеет масштаб $1/\epsilon$.
- В нашем примере истинный счёт HIV в группе может быть $c=3$. При DP с $\epsilon =0.5$ шумовая шкала $1/\epsilon =2$, поэтому опубликованный результат может быть, скажем, $\tilde{c}=3+\eta$ и не даст уверенного вывода «этот конкретный человек болен», потому что похожие выходы возможны и для баз данных, где этот человек отсутствует.
Преимущества DP здесь:
- Защищает от атак с произвольной дополнительной информацией (формальный гарантийный предел изменения вывода при удалении/добавлении записи).
- Предотвращает атрибутное раскрытие, если ответы формируются через DP-механизмы, а не через публикацию необработанных/псевдоанонимизированных строк.
Ограничения и практические проблемы дифференциальной приватности:
- Точный выбор $\epsilon$ критичен: малое $\epsilon$ даёт сильную приватность, но ухудшает полезность (сильный шум). Большое $\epsilon$ — слабая защита. Как выбрать $\epsilon$ — нет единых правил. Все числовые примеры: $\epsilon$ обычно выбирают в диапазоне от $0.01$ до $10$ в зависимости от задачи.
- Композиция: многократные запросы на одну базу суммируют «расход приватности» (суммарный бюджет $\epsilon$), поэтому большое число ответов снижает защиту.
- Высокая размерность данных (много атрибутов) делает создание полезных DP-выходов сложным: шумы на множество статистик часто разрушают утилиту.
- DP защищает только результаты механизма; если сырые данные или плохо реализованный «анонимный» дамп публикуются, DP не применяется. Нужно, чтобы публикация и вся обработка были выполнены DP-механизмом.
- Практическая сложность внедрения и верификации корректности механизмов, а также распределение бюджета между задачами аналитики.
- Хотя DP формально защищает от атак с произвольным фоновым знанием, при слишком большом $\epsilon$ или при чрезмерной агрегации/почти детерминированных выводах риск восстановления/инференции сохраняется.
Вывод:
- k-анонимность может не предотвратить раскрытие чувствительных атрибутов при однородности групп или наличии вспомогательной информации (реальные случаи: Sweeney/Massachusetts, Netflix).
- Дифференциальная приватность предоставляет формальную гарантию против влияния одной записи на выводы и решает проблему атрибутного раскрытия при публикации статистик, но требует правильного выбора параметров ($\epsilon$), управления бюджетом и часто снижает полезность данных.