Механизмы дифференциальной приватности с аддитивным шумом

Для работы аддитивных механизмов необходимо сначала определить чувствительность функции запроса. Чувствительность — это максимальное изменение ответа функции при добавлении или удалении одной записи о каком-либо лице в наборе данных. Например, для запроса, считающего количество лиц, соответствующих какому-либо критерию, чувствительность равна 1.

Формально определение чувствительности можно представить следующим образом.

Пусть ${\displaystyle {\mathcal {D}}}$ — множество всех возможных наборов данных, а ${\displaystyle f\colon {\mathcal {D}}\to \mathbb {R} }$ — вещественнозначная функция. Чувствительность^[1] функции, обозначаемая ${\displaystyle \Delta f}$, определяется формулой

${\displaystyle \Delta f=\max |f(x)-f(y)|,}$

где максимум берётся по всем парам наборов данных ${\displaystyle x}$ и ${\displaystyle y}$ из ${\displaystyle {\mathcal {D}}}$, различающимся не более чем одним элементом. Для многомерных функций чувствительность, как правило, измеряется в ${\displaystyle \ell _{1}}$ или ${\displaystyle \ell _{2}}$ нормах.

В этой статье ${\displaystyle {\mathcal {M}}}$ обозначает рандомизированный алгоритм, который публикует чувствительную функцию ${\displaystyle f}$ с гарантией ${\displaystyle \epsilon }$- (или ${\displaystyle (\epsilon ,\delta )}$-) дифференциальной приватности.

Вещественнозначная функция — это функция, возвращающая вещественное число (например, 0,5 или 1,32).

Механизм Лапласа, впервые предложенный Дворк и соавт^[1]., добавляет к значению функции шум, сгенерированный из распределения Лапласа:

${\displaystyle {\mathcal {M}}_{\mathrm {Lap} }(x,f,\epsilon )=f(x)+\mathrm {Lap} \left(\mu =0,b={\frac {\Delta f}{\epsilon }}\right),}$

где ${\displaystyle \mu }$ — математическое ожидание распределения Лапласа, а ${\displaystyle b}$ — параметр масштаба. Чем больше значение ${\displaystyle \epsilon }$ (то есть слабее требование к приватности), тем меньше требуется шум; чем меньше ${\displaystyle \epsilon }$, тем выше уровень неопределённости относительно исходных данных.

Для доказательства того, что механизм удовлетворяет ${\displaystyle \epsilon }$-дифференциальной приватности, достаточно показать, что выходные распределения ${\displaystyle {\mathcal {M}}_{\mathrm {Lap} }(x,f,\epsilon )}$ и ${\displaystyle {\mathcal {M}}_{\mathrm {Lap} }(y,f,\epsilon )}$ близки в мультипликативном смысле для всех ${\displaystyle x}$ и ${\displaystyle y}$:

$${\displaystyle {\begin{aligned}{\frac {\mathrm {Pr} ({\mathcal {M}}_{\mathrm {Lap} }(x,f,\epsilon )=z)}{\mathrm {Pr} ({\mathcal {M}}_{\mathrm {Lap} }(y,f,\epsilon )=z)}}&={\frac {\mathrm {Pr} (f(x)+\mathrm {Lap} (0,{\frac {\Delta f}{\epsilon }})=z)}{\mathrm {Pr} (f(y)+\mathrm {Lap} (0,{\frac {\Delta f}{\epsilon }})=z)}}\\&={\frac {\mathrm {Pr} (\mathrm {Lap} (0,{\frac {\Delta f}{\epsilon }})=z-f(x))}{\mathrm {Pr} (\mathrm {Lap} (0,{\frac {\Delta f}{\epsilon }})=z-f(y))}}\\&={\frac {{\frac {1}{2b}}\exp \left(-{\frac {|z-f(x)|}{b}}\right)}{{\frac {1}{2b}}\exp \left(-{\frac {|z-f(y)|}{b}}\right)}}\\&=\exp \left({\frac {|z-f(y)|-|z-f(x)|}{b}}\right)\\&\leq \exp \left({\frac {|f(y)-f(x)|}{b}}\right)\\&\leq \exp \left({\frac {\Delta f}{b}}\right)=\exp(\epsilon ).\end{aligned}}}$$

${\displaystyle \exp(-\epsilon )}$

Дискретная версия механизма Лапласа — геометрический механизм — является универсально оптимальным по полезности^[2]. Это означает, что для любого априорного распределения (например, дополнительной информации) и любой симметричной и монотонной одномерной функции потерь ожидаемый ущерб от любого дифференциально-приватного механизма не превышает ущерба от применения геометрического механизма с последующей независимой от данных постобработкой. Результат также справедлив для минимаксных (риск-нейтральных) потребителей^[3]. Для многомерных функций потерь универсального механизма не существует^[4].

Аналогично механизму Лапласа, механизм Гаусса добавляет шум, сгенерированный из гауссова распределения, с дисперсией, определяемой чувствительностью и параметрами приватности. Для любых ${\displaystyle \delta \in (0,1)}$ и ${\displaystyle \epsilon \in (0,1)}$ механизм задаётся формулой:

${\displaystyle {\mathcal {M}}_{\text{Gauss}}(x,f,\epsilon ,\delta )=f(x)+{\mathcal {N}}\left(\mu =0,\sigma ^{2}={\frac {2\ln(1.25/\delta )\cdot (\Delta f)^{2}}{\epsilon ^{2}}}\right)}$,

обеспечивая ${\displaystyle (\epsilon ,\delta )}$-дифференциальную приватность.

При этом, в отличие от механизма Лапласа, ${\displaystyle {\mathcal {M}}_{\text{Gauss}}}$ обеспечивает только ${\displaystyle (\epsilon ,\delta )}$-дифференциальную приватность при ${\displaystyle \epsilon <1}$. Доказательство (см. приложение А к монографии Дворк и Рота^[5]) сводится к тому, что с вероятностью не менее ${\displaystyle 1-\delta }$ выходное распределение ${\displaystyle {\mathcal {M}}_{\text{Gauss}}(x,f,\epsilon ,\delta )}$ близко к ${\displaystyle {\mathcal {M}}_{\text{Gauss}}(y,f,\epsilon ,\delta )}$.

Для многомерных функций ${\displaystyle f\colon {\mathcal {D}}\to \mathbb {R} ^{d}}$, где ${\displaystyle d\geq 2}$, чувствительность ${\displaystyle f}$ измеряется в ${\displaystyle \ell _{1}}$- или ${\displaystyle \ell _{2}}$-норме. Соответствующий механизм Гаусса, обеспечивающий ${\displaystyle (\epsilon ,\delta )}$-дифференциальную приватность для такой функции (при условии ${\displaystyle \epsilon <1}$), имеет вид:

${\displaystyle {\mathcal {M}}_{\text{Gauss}}(x,f,\epsilon ,\delta )=f(x)+{\mathcal {N}}^{d}\left(\mu =0,\sigma ^{2}={\frac {2\ln(1.25/\delta )\cdot (\Delta _{2}f)^{2}}{\epsilon ^{2}}}\right),}$

где ${\displaystyle \Delta _{2}f}$ — чувствительность функции ${\displaystyle f}$ в ${\displaystyle \ell _{2}}$-норме, а ${\displaystyle {\mathcal {N}}^{d}(0,\sigma ^{2})}$ — ${\displaystyle d}$-мерный вектор, компоненты которого независимы и распределены по закону ${\displaystyle {\mathcal {N}}(0,\sigma ^{2})}$. Для доказательства см. приложение А в работе Дворк и Рота^[5].