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

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

Определение

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

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

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

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

Вещественные функции

Механизм Лапласа

Представлено Дворком и др., этот механизм добавляет шум, полученный из распределения Лапласа :

Механизм Лапласа, обеспечивающий 0,5-дифференциальную конфиденциальность для функции с чувствительностью 1.

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

где $\mu$ — математическое ожидание распределения Лапласа и $b$ является параметром масштаба. Грубо говоря, мелкомасштабного шума должно быть достаточно для слабого ограничения конфиденциальности (что соответствует большому значению $\epsilon$), в то время как более высокий уровень шума обеспечит большую степень неопределенности в том, что было исходным входным сигналом (что соответствует небольшому значению $\epsilon$).

Утверждать, что механизм удовлетворяет $\epsilon$-дифференциальной конфиденциальности, достаточно показать, что выходное распределение ${\mathcal {M}}_{\mathrm {Lap} }(x,f,\epsilon )$ близко в мультипликативном смысле к ${\mathcal {M}}_{\mathrm {Lap} }(y,f,\epsilon )$ повсюду. $${\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}}$$ Первое неравенство следует из неравенства треугольника, а второе — из границы чувствительности. Аналогичный аргумент дает нижнюю границу $\exp(-\epsilon )$.

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

Гауссов механизм

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

Гауссов механизм.

${\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)$

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

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

Многомерные функции

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

${\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),$

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