Дифференциальная приватность

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

ВведениеПравить

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

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

Принцип и иллюстрацияПравить

Дифференциальная приватность основана на введении случайности в данные.

Простой пример, разработанный в социальных науках, заключается в том, чтобы попросить человека ответить на вопрос «Есть ли у вас атрибут А?» в соответствии со следующей процедурой:

1. Подбросьте монету
2. Если выпал орел, ответьте честно на вопрос.
3. Иначе подбросьте ещё раз, если выпадет орел, ответь «Да», если решка — «Нет»

Конфиденциальность возникает, так как невозможно по ответу точно узнать, обладает ли человек данным атрибутом. Но тем не менее эти данные значительны, так как положительные ответы дают четверть от тех людей, у которых нет этого атрибута, и три четверти от тех, кто на самом деле им обладают. Таким образом, если p — истинная доля людей с A, то мы ожидаем получить (1/4) (1- p) + (3/4) p = (1/4) + p / 2 положительных ответов. Следовательно, можно оценить р.

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

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

$P[\mathcal{A}(D_1)\in <!--\; \in \; -->S]\le <!--\; \le \; -->e^{\mathrm{ϵ<!--\; ϵ\; -->}}\times <!--\; \times \; -->P[\mathcal{A}(D_2)\in <!--\; \in \; -->S],$$P[{\mathcal {A}}(D_{1})\in S]\leq e^{\epsilon }\times P[{\mathcal {A}}(D_{2})\in S],$ 

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

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

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

Имя	Наличие гастрита (Х)
Иван	1
Петр	0
Василиса	1
Михаил	1
Мария	0

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

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

Пример с монеткой, описанный выше является $(\ln <!--\; \; -->3)$$(\ln 3)$ -дифференциально приватным.

Граничные случаиПравить

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

Если устремить ε в бесконечность, то любой вероятностный алгоритм будет подходить под определение, поскольку неравенство $P[\mathcal{A}(D_1)\in <!--\; \in \; -->S]\le <!--\; \le \; -->\mathrm{\infty <!--\; \infty \; -->}\times <!--\; \times \; -->P[\mathcal{A}(D_2)\in <!--\; \in \; -->S],$$P[{\mathcal {A}}(D_{1})\in S]\leq \infty \times P[{\mathcal {A}}(D_{2})\in S],$  — выполняется всегда.

ЧувствительностьПравить

Пусть $d$$d$  — положительное целое число, $\mathcal{D}$$\mathcal{D}$  — набор данных и $f:<!--\; :\; -->\mathcal{D}\to <!--\; \to \; -->{\mathbb{R}}^d$$f\colon {\mathcal {D}}\rightarrow \mathbb {R} ^{d}$  — функция. Чувствительность функции, обозначаемая $\mathrm{\Delta <!--\; \Delta \; -->}f$$\Delta f$ , определяется формулой

$\mathrm{\Delta <!--\; \Delta \; -->}f=max\Vert <!--\; \Vert \; -->f(D_1)-<!--\; -\; -->f(D_2){\Vert <!--\; \Vert \; -->}_1,$$\Delta f=\max \lVert f(D_{1})-f(D_{2})\rVert _{1},$ 

по всем парам наборов данных $D_1$$D_{1}$  и $D_2$$D_{2}$  в $\mathcal{D}$$\mathcal{D}$ , отличающихся не более чем одним элементом и где $\Vert <!--\; \Vert \; -->\cdot <!--\; \cdot \; -->{\Vert <!--\; \Vert \; -->}_1$$\lVert \cdot \rVert _{1}$  обозначает ${\mathrm{\ell <!--\; \ell \; -->}}_1$$\ell _{1}$  норму.

На выше приведённом примере медицинской базы данных, если мы рассмотрим чувствительность $d$$d$  функции $Q_i$$Q_{i}$ , то она равна $1$$1$ , так как изменение любой из записей в базе данных приводит к тому, что $Q_i$$Q_{i}$  либо изменится на $1$$1$  либо не изменится.

Механизм ЛапласаПравить

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

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

$\frac{\mathrm{p}\mathrm{d}\mathrm{f}({\mathcal{T}}_{\mathcal{A},D_1}(x)=t)}{\mathrm{p}\mathrm{d}\mathrm{f}({\mathcal{T}}_{\mathcal{A},D_2}(x)=t)}=\frac{\text{noise}(t-<!--\; -\; -->f(D_1))}{\text{noise}(t-<!--\; -\; -->f(D_2))}$${\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}))}}\,\!$ 

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

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

КомпозицияПравить

Последовательное применениеПравить

Если мы выполним запрос в ε-дифференциально защищённой $T$$T$  раз, и вносимый случайный шум независим для каждого запроса, тогда суммарная приватность будет (εt)-дифференциальной. В более общем случае, если есть $N$$N$  независимых механизмов: ${\mathcal{M}}_1,\dots <!--\; \dots \; -->,{\mathcal{M}}_n$${\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n}$ , чьи гарантии приватности равны ${\mathrm{ϵ<!--\; ϵ\; -->}}_1,\dots <!--\; \dots \; -->,{\mathrm{ϵ<!--\; ϵ\; -->}}_n$$\epsilon _{1},\dots ,\epsilon _{n}$  соответственно, то любая функция $g({\mathcal{M}}_1,\dots <!--\; \dots \; -->,{\mathcal{M}}_n)$$g({\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n})$  будет $(\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{\mathrm{ϵ<!--\; ϵ\; -->}}_i)$$(\sum \limits _{i=1}^{n}\epsilon _{i})$ -дифференциально приватной.

Параллельная композицияПравить

Кроме того, если запросы выполняются на непересекающихся подмножествах базы данных, то функция $g$$g$  была бы $(\underset{i}{max}{\mathrm{ϵ<!--\; ϵ\; -->}}_i)$$(\max _{i}{\epsilon }_{i})$ -дифференциально приватной.

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

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

$Pr[\mathcal{A}(D_1)\in <!--\; \in \; -->S]\le <!--\; \le \; -->\exp <!--\; \; -->(\mathrm{ϵ<!--\; ϵ\; -->}c)\times <!--\; \times \; -->Pr[\mathcal{A}(D_2)\in <!--\; \in \; -->S]$$\Pr[{\mathcal {A}}(D_{1})\in S]\leq \exp(\epsilon c)\times \Pr[{\mathcal {A}}(D_{2})\in S]\,\!$ 

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

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

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

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

ЛитератураПравить

• 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.