Дифференциальная приватность

Пусть ε — положительное действительное число, а ${\displaystyle {\mathcal {A}}}$ — рандомизированный алгоритм, принимающий на вход набор данных (от имени доверенного держателя). Пусть ${\displaystyle {\textrm {im}}\ {\mathcal {A}}}$ обозначает образ этого алгоритма.

Говорят, что алгоритм ${\displaystyle {\mathcal {A}}}$ удовлетворяет (ε, δ)-дифференциальной приватности, если для любых двух наборов данных ${\displaystyle D_{1}}$ и ${\displaystyle D_{2}}$, различающихся одной записью, и любого подмножества ${\displaystyle S}$ множества значений ${\displaystyle {\textrm {im}}\ {\mathcal {A}}}$ выполнено:

$${\displaystyle \Pr[{\mathcal {A}}(D_{1})\in S]\leq e^{\varepsilon }\Pr[{\mathcal {A}}(D_{2})\in S]+\delta .}$$

Здесь вероятность берётся по внутреннему случайному выбору алгоритма^[6]. Это определение иногда называют «приближённой дифференциальной приватностью»; случай δ = 0 — это «чистая дифференциальная приватность».

Дифференциальная приватность обладает рядом сильных свойств, важных для построения сложных систем: композиционность, устойчивость к постобработке, а также корректное ослабление гарантий при наличии коррелированных данных.

Определение относится к механизму публикации, а не данным как таковым. Для любых двух похожих наборов данных дифференциально приватный алгоритм ведёт себя почти одинаково. Это гарантирует — присутствие или отсутствие одной личности не оказывает существенного влияния на итоговый результат.

Пример: пусть имеется база медицинских записей ${\displaystyle D_{1}}$, где каждая запись — пара (Имя, X), X — булево значение (1 — есть диабет, 0 — нет):

Злоумышленник пытается узнать, болен ли Чендлер диабетом. Предполагается, что он знает, где находится его запись, и имеет возможность выполнять запрос ${\displaystyle Q_{i}}$, возвращающий сумму первых ${\displaystyle i}$ значений столбца X. Вызвав ${\displaystyle Q_{5}(D_{1})=3}$ и ${\displaystyle Q_{4}(D_{1})=2}$, он вычисляет разность (1) — стало быть, у Чендлера диабет. Этот пример иллюстрирует возможность утечки информации о конкретном лице даже без прямого поиска его данных.

Если вместо (Чендлер, 1) в базе ${\displaystyle D_{2}}$ стоит (Чендлер, 0), злоумышленник по тем же запросам отличает ${\displaystyle D_{1}}$ от ${\displaystyle D_{2}}$. Если бы ответы на ${\displaystyle Q_{i}}$ возвращал ε-дифференциально приватный алгоритм с малым ε, отличить два набора данных было бы невозможно.

Композиционность означает, что совокупность результатов (возможно, адаптивно выбираемых) разных дифференциально приватных механизмов сохраняет приватность^[3].

• Последовательная композиция. Если задать ε-дифференциальный механизм ${\displaystyle t}$ раз (независимыми запросами), итоговый механизм будет ${\displaystyle \varepsilon t}$-дифференциально приватным. Если есть n независимых механизмов с параметрами ${\displaystyle \varepsilon _{1},\dots ,\varepsilon _{n}}$, то любая функция от их выходов будет ${\displaystyle \left(\sum \limits _{i=1}^{n}\varepsilon _{i}\right)}$-дифференциально приватной^[7].

• Параллельная композиция. Если механизмы применяются к непересекающимся подмножествам базы, итоговый механизм будет ${\displaystyle (\max _{i}\varepsilon _{i})}$-дифференциально приватным^[7].

Робастность к постобработке — если функция ${\displaystyle F}$ определена на выходе ${\displaystyle {\mathcal {A}}}$, и ${\displaystyle {\mathcal {A}}}$ ε-дифференциально приватен, то ${\displaystyle F({\mathcal {A}})}$ — тоже^[3].

Эти свойства позволяют строить сложные механизмы с модулярными гарантиями и формируют так называемый «бюджет утечки приватности». Если все элементы сложного механизма по отдельности дифференциально приватны, то и их комбинация (и даже любая последующая обработка результатов) такова же^[3].

Обычно ε-дифференциальная приватность защищает отличие между наборами данных, различающимися в одной записи, то есть от раскрытия участия отдельного лица. Однако это свойство масштабируемо^[3]: если нужно защитить и группы из c участников, то вероятность расхождения ограничивается ${\displaystyle \exp(\varepsilon c)}$ вместо ${\displaystyle \exp(\varepsilon )}$^[8], то есть выбор ε/c вместо ε позволяет защищать группы; так, каждая группа из c записей защищена параметром ε, а отдельный элемент — (ε/c)-дифференциально приватен^[3].

Дифференциальную приватность можно понимать как ограничение ошибок первого и второго рода в задаче гипотез:

• ${\displaystyle H_{0}}$: данных индивидуума в базе нет;
• ${\displaystyle H_{1}}$: данные присутствуют.

Соответственно:

• Ложно-положительная (FPR): ${\displaystyle P_{\text{FP}}=\Pr[{\text{противник выбирает }}H_{1}|H_{0}]}$,
• Ложно-отрицательная (FNR): ${\displaystyle P_{\text{FN}}=\Pr[{\text{выбран }}H_{0}|H_{1}]}$.

При заданном (ε, δ) возможные пары ошибок удовлетворяют:

• ${\displaystyle \{(P_{\text{FP}},P_{\text{FN}})\mid P_{\text{FP}}+e^{\varepsilon }P_{\text{FN}}\geq 1-\delta ,\ e^{\varepsilon }P_{\text{FP}}+P_{\text{FN}}\geq 1-\delta \}}$.

Механизм Лапласа добавляет шум из распределения Лапласа, плотность функции которого задаётся как ${\displaystyle {\text{noise}}(y)\propto \exp(-|y|/\lambda )}$, где среднее 0, а стандартное отклонение ${\displaystyle {\sqrt {2}}\lambda }$. Пусть функция результата алгоритма ${\displaystyle {\mathcal {A}}}$ задаётся как ${\displaystyle {\mathcal {T}}_{\mathcal {A}}(x)=f(x)+Y}$, где ${\displaystyle Y\sim {\text{Lap}}(\lambda )}$.

Для любых двух наборов данных различие в распределениях выхода не превышает ${\displaystyle e^{\Delta (f)/\lambda }}$. Если положить ${\displaystyle \lambda =\Delta (f)/\varepsilon }$, то получаем ε-дифференциальную приватность. Для нашего примера (сумма по столбцу, чувствительность 1) надо использовать ${\displaystyle \lambda =1/\varepsilon }$. Можно применять другие распределения шума, например гауссовское, но для них потребуется ослабленное определение приватности^[8].

Простейший случай — рандомизированный ответ, введённый в социологии^[11]. Пример процедуры:

1. Бросить монету;
2. Если орёл — бросить ещё раз и ответить на вопрос честно;
3. Если решка — снова бросить монету; при орле ответить «да», при решке — «нет».

(Второй бросок в обоих случаях необходим, чтобы просто сам факт броска не свидетельствовал о содержании ответа.) Защита основывается на принципе опровержимости индивидуального ответа.

Общая доля положительных ответов позволяет оценить истинную частоту признака по формуле: если p — доля носителей, то ожидаемое число «да» — (¼)(1 − p) + (¾)p = ¼ + p/2.

Если признак — противоправное поведение, то даже «да» не компрометирует участника, поскольку всегда остаётся вероятность случайного попадания.

Хотя эта схема применяется к микроданным (индивидуальным ответам), классическая дифференциальная приватность касается лишь агрегированных запросов, так как публикация микроданных подрывает принцип правдоподобного отрицания участия^[12][13].

Преобразование ${\displaystyle T}$ называется c-стабильным, если расстояние Хэмминга между ${\displaystyle T(A)}$ и ${\displaystyle T(B)}$ не больше c раз превышает расстояние между ${\displaystyle A}$ и ${\displaystyle B}$. Если механизм ${\displaystyle M}$ ε-дифференциально приватен, то композиция ${\displaystyle M\circ T}$ обладает (ε×c)-дифференциальной приватностью^[7].

С помощью этой идеи обобщается групповая приватность: группа размера h защищена с коэффициентом ε×c×h.

В 1977 году шведский статистик Туре Далениус заложил математические основы блокировки ячеек для минимизации утечек при публикации таблиц^[14]. Его ключевой вывод: статистические базы не должны раскрывать информации об индивидууме, которую нельзя получить иначе^[15]. Он также предложил типологию видов раскрытий^[4].

В 1979 году Дороти Деннинг, Питер Дж. Деннинг и Майер Шварц предложили концепцию трекера: противника, способного восстановить приватные сведения на основе последовательности целевых запросов и запоминания их результатов^[16]. Было показано, что учёт влияния каждого нового запроса на приватность индивидов — задача очень сложная (NP-трудная).

В 2003 году Кобби Ниссим и Ирит Динур доказали невозможность открытой публикации любого количества запросов к приватной статистической базе без риска раскрытия личных данных: уже относительно небольшое число случайных выборок позволяет восстановить всю базу^[17]. Это явление называют «фундаментальным законом восстановления информации»: для защиты приватности необходим ввод случайного шума.

В 2006 году Синтия Дворк, Фрэнк МакШерри, Кобби Ниссим и Адам Смит^[3] предложили формальный способ калибровки объёма случайного шума и универсальный механизм защиты приватности. В этой же работе впервые было строго определено само понятие дифференциальной приватности^[4]. Их статья получила премии TCC Test-of-Time Award (2016)^[18] и премию Гёделя (2017)^[19].

Дальнейшие исследования показали, что можно получать достаточно точную статистику при существенно высоко гарантированной приватности^[1].