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

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

Определения

Позволять быть сборником всех наборов данных и - вещественная функция. В чувствительность [1] функции, обозначенной , определяется

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

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

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

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

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

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

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

Чтобы утверждать, что механизм удовлетворяет -дифференциальная конфиденциальность, достаточно показать, что выходное распределение является закрыть в мультипликативном смысле к повсюду.

Первое неравенство следует из неравенства треугольника, второе - из оценки чувствительности. Аналогичное рассуждение дает нижнюю оценку .

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

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

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

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

обеспечивает -дифференциальная конфиденциальность.

Обратите внимание, что, в отличие от механизма Лапласа, только удовлетворяет -дифференциальная конфиденциальность с . Чтобы доказать это, достаточно показать, что с вероятностью не менее , распределение близко к . Доказательство немного сложнее (см. Приложение A в книге Дворка и Рота.[5]).


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

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

куда представляет собой чувствительность под норма и представляет -мерный вектор, где каждая координата является шумом, выбранным в соответствии с независимо от других координат (см. Дворк и Рот[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.