WikiSort.ru - Не сортированное

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

Введение

Дифференциальная приватность — математическое определение потери конфиденциальных данных отдельных лиц, когда их личная информация используется для создания продукта. Этот термин был введен Синтией Дворк^[en]* в 2006 году^[1], но он же используется в более ранней публикации Дворк, Фрэнка Макшерри^[fr], Коби Ниссима^[fr] и Адама Д. Смита^[fr][2]. Работа основана в частности на исследованиях Ниссима и Ирита Динура^[3][4], которые показали, что невозможно публиковать информацию из частной статической базы данных, не раскрывая некоторую часть приватной информации, и что вся база данных может быть раскрыта путем публикации результатов достаточно небольшого числа запросов^[4].

После проведения исследования стало понятно, что обеспечение конфиденциальности в статистических базах данных с использованием существующих методов было невозможным, и, как следствие, появилась необходимость в новых, которые бы ограничивали риски, связанные с потерей частной информации, содержащихся в статистической базе данных. Как итог были созданы новые методы, позволяющие в большинстве случаев предоставить точную статистику из базы данных, и при этом обеспечивающие высокий уровень конфиденциальности^[5][6].

Формальное определение и пример использования

Пусть ε — положительное действительное число и A — вероятностный алгоритм, который принимает на вход набор данных (представляет действия доверенной стороны, обладающей данными). Образ A обозначим imA. Алгоритм A является ε-дифференциально приватным, если для всех наборов данных ${\displaystyle D_{1}}$ и ${\displaystyle D_{2}}$ , которые отличаются одним элементом (то есть данными одного человека), а также всех подмножеств S множества imA:

${\displaystyle P[{\mathcal {A}}(D_{1})\in S]\leq e^{\epsilon }\times P[{\mathcal {A}}(D_{2})\in S],}$

где P — вероятность.

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

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

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

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

Также пример с монеткой, описанный выше является ${\displaystyle (\ln 3)}$ -дифференциально приватным^[8].

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

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

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

${\displaystyle {\frac {\mathrm {pdf} ({\mathcal {T}}_{{\mathcal {A}},D_{1}}(x)=t)}{\mathrm {pdf} ({\mathcal {T}}_{{\mathcal {A}},D_{2}}(x)=t)}}={\frac {{\text{noise}}(t-f(D_{1}))}{{\text{noise}}(t-f(D_{2}))}}\,\!}$

которая не более ${\displaystyle e^{\frac {|f(D_{1})-f(D_{2})|}{\lambda }}\leq e^{\frac {\Delta (f)}{\lambda }}\,\!}$ (pdf — probability density function или функция плотности вероятности). В данном случае можно обозначить ${\displaystyle {\frac {\Delta (f)}{\lambda }}\,\!}$ фактором конфиденциальности ε. Таким образом ${\displaystyle {\mathcal {T}}\,\!}$ в соответствие с определением является ε-дифференциально приватной. Если мы попытаемся использовать эту концепцию в вышеприведенном примере про наличие гастрита, то для того, чтобы ${\displaystyle {\mathcal {A}}\,\!}$ была ε-дифференциальный приватной функцией, должно выполняться ${\displaystyle \lambda =1/\epsilon }$ , поскольку ${\displaystyle \Delta (f)=1}$ ).

Кроме шума Лапласа также можно использовать другие виды шума, например, гауссовский но они могут потребовать небольшого ослабления определения дифференциальной приватности^[10].

Композиция

Приватность группы

Дифференциальная приватность в целом предназначена для защиты конфиденциальности между базами данных, которые отличаются только одной строкой. Это означает, что ни один злоумышленник с произвольной вспомогательной информацией не может узнать, представил ли какой-либо один отдельно взятый участник свою информацию. Однако это понятие можно расширить на группу, если мы хотим защитить базы данных, отличающиеся на ${\displaystyle c}$ строк, чтобы злоумышленник с произвольной вспомогательной информацией, не мог узнать, предоставили ли ${\displaystyle c}$ отдельных участников свою информацию. Это может быть достигнуто если в формуле из определения заменить ${\displaystyle \exp(\epsilon )}$ на ${\displaystyle \exp(\epsilon c)}$ ^[12], тогда для D₁ и D₂ отличающихся на ${\displaystyle c}$ строчек

${\displaystyle \Pr[{\mathcal {A}}(D_{1})\in S]\leq \exp(\epsilon c)\times \Pr[{\mathcal {A}}(D_{2})\in S]\,\!}$

Таким образом, использование параметра (ε/c) вместо ε позволяет достичь необходимого результата и защитить ${\displaystyle c}$ строк. Другими словами, вместо того, чтобы каждый элемент был ε-дифференциально приватным, теперь каждая группа из ${\displaystyle c}$ элементов являются ε-дифференциально приватной, а каждый элемент (ε/c)-дифференциально приватным.

Применение дифференциальной приватности в реальных приложениях

На сегодняшний день известно несколько видов применения дифференциальной приватности:

• Бюро переписи населения США при показе статистики^[13]
• Google RAPPOR для сборе статистики о нежелательном программном обеспечении, ущемляющем настройки пользователей ^[14](реализация RAPPOR с открытым исходным кодом)
• Google, для обмена статистикой истории трафика^[15].
• 13 июня 2016 года Apple объявила о своем намерении использовать дифференциальную приватность в iOS 10 для улучшения своей интеллектуальной поддержки и предложений технологий^[16]

Примечания

Литература

• Ashwin Machanavajjhala, Daniel Kifer, John M. Abowd, Johannes Gehrke, Lars Vilhuber. Privacy: Theory meets Practice on the Map // In Proceedings of the 24th International Conference on Data Engineering, (ICDE). — 2008.
• Úlfar Erlingsson, Vasyl Pihur, Aleksandra Korolova. RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response // Proceedings of the 21st ACM Conference on Computer and Communications Security (CCS). — 2014.
• Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis // Theory of Cryptography Conference (TCC). — Springer, 2006. — DOI:10.1007/11681878_14.
• Frank D. McSherry. Privacy integrated queries: an extensible platform for privacy-preserving data analysis // Proceedings of the 35th SIGMOD International Conference on Management of Data (SIGMOD). — 2009. — DOI:10.1145/1559845.1559850.
• Cynthia Dwork, Aaron Roth. The Algorithmic Foundations of Differential Privacy // Foundations and Trends in Theoretical Computer Science. — 2014. — Август (vol. 9). — DOI:10.1561/0400000042.
• Dwork, Cynthia. Differential Privacy: A Survey of Results // Agrawal, Manindra; Du, Dingzhu; Duan, Zhenhua; Li, Angsheng Theory and Applications of Models of Computation. Lecture Notes in Computer Science. — Springer Berlin Heidelberg, 2008. — 25 апреля. — DOI:10.1145/773153.773173.
• Dwork, Cynthia. Differential Privacy. — International Colloquium on Automata, Languages and Programming (ICALP), 2006. — DOI:10.1007/11787006_1.
• Irit Dinur, Kobbi Nissim. Revealing information while preserving privacy // Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (PODS '03). — ACM, New York, NY, USA, 2003. — DOI:10.1145/773153.773173.