Механизмы аддитивного шума - Additive noise mechanisms

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

Определения

Позволять ${\displaystyle {\mathcal {D}}}$ быть сборником всех наборов данных и ${\displaystyle f:{\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 )}$-) дифференциальная конфиденциальность.

Механизмы для функций с действительным значением

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

Представлено Dwork et al.,^[1] этот механизм добавляет шум, извлекаемый из Распределение Лапласа:

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

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

Для функций большой размерности вида ${\displaystyle f:{\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] для доказательства).

Рекомендации

1. Дворк, Синтия; МакШерри, Фрэнк; Ниссим, Кобби; Смит, Адам (2006). «Калибровка шума по чувствительности в анализе частных данных». Теория криптографии: 265–284. Дои:10.1007/11681878_14.
2. Гош, Арпита; Roughgarden, Тим; Сундарараджан, Мукунд (2012). «Универсальные механизмы конфиденциальности, максимизирующие полезность». SIAM Журнал по вычислениям. 41 (6): 1673–1693. arXiv:0811.2841. Дои:10.1137 / 09076828X.
3. Гупте, Мангеш; Сундарараджан, Мукунд (июнь 2010 г.). «Универсально оптимальные механизмы конфиденциальности для минимаксных агентов». Материалы двадцать девятого симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных (PODS): 135–146. arXiv:1001.2767. Дои:10.1145/1807085.1807105.
4. Бреннер, Хай; Ниссим, Кобби (январь 2014 г.). «Невозможность дифференциально частных универсально оптимальных механизмов». SIAM Журнал по вычислениям. 43 (5): 1513–1540. arXiv:1008.0256. Дои:10.1137/110846671.
5. Дворк, Синтия; Рот, Аарон (2013). «Алгоритмические основы дифференциальной конфиденциальности» (PDF). Основы и тенденции теоретической информатики. 9 (3–4): 211–407. Дои:10.1561/0400000042. ISSN  1551-305X.