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

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

Введение

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

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

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

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

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

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

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

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

Пусть ε — положительное действительное число и 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}$ является нулём или единицей, обозначающим, имеет ли человек гастрит или нет:

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

Теперь предположим, что злонамеренный пользователь (часто называемый злоумышленником) хочет найти, имеет ли Михаил гастрит или нет. Также предположим, что он знает, в какой строке находится информация о Михаиле в базе данных. Теперь предположим, что злоумышленнику разрешено использовать только конкретную форму запроса ${\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].

Граничные случаи

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

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

Чувствительность

Пусть ${\displaystyle d}$ — положительное целое число, ${\displaystyle {\mathcal {D}}}$ — набор данных и ${\displaystyle f\colon {\mathcal {D}}\rightarrow \mathbb {R} ^{d}}$ — функция. Чувствительность [9] функции, обозначаемая ${\displaystyle \Delta f}$, определяется формулой

${\displaystyle \Delta f=\max \lVert f(D_{1})-f(D_{2})\rVert _{1},}$

по всем парам наборов данных ${\displaystyle D_{1}}$ и ${\displaystyle D_{2}}$ в ${\displaystyle {\mathcal {D}}}$, отличающихся не более чем одним элементом и где ${\displaystyle \lVert \cdot \rVert _{1}}$ обозначает ${\displaystyle \ell _{1}}$ норму.

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

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

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

Метод Лапласа добавляет шум Лапласа, то есть шум от распределения Лапласа, который может быть выражен функцией плотности вероятности ${\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 T}$ раз, и вносимый случайный шум независим для каждого запроса, тогда суммарная приватность будет (εt)-дифференциальной. В более общем случае, если есть ${\displaystyle N}$ независимых механизмов: ${\displaystyle {\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n}}$, чьи гарантии приватности равны ${\displaystyle \epsilon _{1},\dots ,\epsilon _{n}}$ соответственно, то любая функция ${\displaystyle g({\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n})}$ будет ${\displaystyle (\sum \limits _{i=1}^{n}\epsilon _{i})}$-дифференциально приватной[11].

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

Кроме того, если запросы выполняются на непересекающихся подмножествах базы данных, то функция ${\displaystyle g}$ была бы ${\displaystyle (\max _{i}{\epsilon }_{i})}$-дифференциально приватной[11].

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

Дифференциальная приватность в целом предназначена для защиты конфиденциальности между базами данных, которые отличаются только одной строкой. Это означает, что ни один злоумышленник с произвольной вспомогательной информацией не может узнать, представил ли какой-либо один отдельно взятый участник свою информацию. Однако это понятие можно расширить на группу, если мы хотим защитить базы данных, отличающиеся на ${\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]

Примечания

1. Dwork Cynthia, 2006, p. 8.
2. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith=. Calibrating noise to sensitivity in private data analysis // Proceedings of the Third conference on Theory of Cryptography (TCC'06), Shai Halevi and Tal Rabin (Eds.). — Springer-Verlag, Berlin, Heidelberg, 2006. — С. 266. — doi:10.1007/11681878_14.
3. Dwork Cynthia, 2006, p. 12.
4. Nissim et al, 2003, pp. 202—206.
5. HILTON, MICHAEL. Differential Privacy: A Historical Survey (неопр.). Архивировано 1 марта 2017 года., p.1
6. Dwork, 2008, pp. 3—13.
7. Roth et al, 2014, p. 15.
8. Roth et al, 2014, p. 30.
9. Dwork et al, 2006, pp. 271—272.
10. Dwork, 2008, p. 16.
11. McSherry, 2009, p. 6.
12. Dwork Cynthia, 2006, p. 9.
13. Machanavajjhala et al, 2008, p. 1.
14. Erlingsson et al, 2014, p. 1.
15. Tackling Urban Mobility with Technology by Andrew Eland  (неопр.). Google Policy Europe Blog. Дата обращения: 19 декабря 2017. Архивировано 10 декабря 2017 года.
16. Apple - Press Info - Apple Previews iOS 10, the Biggest iOS Release Ever  (неопр.). Apple. Дата обращения: 16 июня 2016. Архивировано 29 апреля 2017 года.

Литература

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