Дифференциальная приватность
Дифференциальная приватность — совокупность методов, которые обеспечивают максимально точные запросы в статистическую базу данных при одновременной минимизации возможности идентификации отдельных записей в ней.
Введение
Дифференциальная приватность — математическое определение потери конфиденциальных данных отдельных лиц, когда их личная информация используется для создания продукта. Этот термин был введён Синтией Дворк в 2006 году[1], но он же используется в более ранней публикации Дворк, Фрэнка Макшерри[фр.], Коби Ниссима[фр.] и Адама Д. Смита[фр.][2]. Работа основана в частности на исследованиях Ниссима и Ирит Динур[англ.][3][4], которые показали, что невозможно публиковать информацию из частной статической базы данных, не раскрывая некоторую часть приватной информации, и что вся база данных может быть раскрыта путём публикации результатов достаточно небольшого числа запросов[4].
После проведения исследования стало понятно, что обеспечение конфиденциальности в статистических базах данных с использованием существующих методов было невозможным, и, как следствие, появилась необходимость в новых, которые бы ограничивали риски, связанные с потерей частной информации, содержащихся в статистической базе данных. Как итог были созданы новые методы, позволяющие в большинстве случаев предоставить точную статистику из базы данных, и при этом обеспечивающие высокий уровень конфиденциальности[5][6].
Принцип и иллюстрация
Дифференциальная приватность основана на введении случайности в данные.
Простой пример, разработанный в социальных науках[7], заключается в том, чтобы попросить человека ответить на вопрос «Есть ли у вас атрибут А?» в соответствии со следующей процедурой:
- Подбросьте монету
- Если выпал орел, ответьте честно на вопрос.
- Иначе подбросьте ещё раз, если выпадет орел, ответь «Да», если решка — «Нет»
Конфиденциальность возникает, так как невозможно по ответу точно узнать, обладает ли человек данным атрибутом. Но тем не менее эти данные значительны, так как положительные ответы дают четверть от тех людей, у которых нет этого атрибута, и три четверти от тех, кто на самом деле им обладают. Таким образом, если p — истинная доля людей с A, то мы ожидаем получить (1/4) (1- p) + (3/4) p = (1/4) + p / 2 положительных ответов. Следовательно, можно оценить р.
Формальное определение и пример использования
Пусть ε — положительное действительное число и A — вероятностный алгоритм, который принимает на вход набор данных (представляет действия доверенной стороны, обладающей данными). Образ A обозначим imA. Алгоритм A является ε-дифференциально приватным, если для всех наборов данных и , которые отличаются одним элементом (то есть данными одного человека), а также всех подмножеств S множества imA:
где P — вероятность.
В соответствии с этим определением дифференциальная приватность является условием механизма публикации данных (то есть определяется доверенной стороной, выпускающей информацию о наборе данных), а не самим набором. Интуитивно это означает, что для любых двух схожих наборов данных, дифференциально-приватный алгоритм будет вести себя примерно одинаково на обоих наборах. Определение также даёт сильную гарантию того, что присутствие или отсутствие индивидуума не повлияет на окончательный вывод алгоритма.
Например, предположим, что у нас есть база данных медицинских записей где каждая запись представляет собой пару (Имя, X), где является нулём или единицей, обозначающим, имеет ли человек гастрит или нет:
Имя | Наличие гастрита (Х) |
---|---|
Иван | 1 |
Петр | 0 |
Василиса | 1 |
Михаил | 1 |
Мария | 0 |
Теперь предположим, что злонамеренный пользователь (часто называемый злоумышленником) хочет найти, имеет ли Михаил гастрит или нет. Также предположим, что он знает, в какой строке находится информация о Михаиле в базе данных. Теперь предположим, что злоумышленнику разрешено использовать только конкретную форму запроса , который возвращает частичную сумму первых строк столбца в базе данных. Чтобы узнать, есть ли гастрит у Михаила, злоумышленник выполняет запросы: и , затем вычисляет их разницу. В данном примере, , а , поэтому их разность равна . Это значит, что поле «Наличие гастрита» в строке Михаила должно быть равно . Этот пример показывает, как индивидуальная информация может быть скомпрометирована даже без явного запроса данных конкретного человека.
Продолжая этот пример, если мы построим набор данных , заменив (Михаил, 1) на (Михаил, 0), то злоумышленник сможет отличить от путём вычисления для каждого набора данных. Если бы злоумышленник получал значения через ε-дифференциально приватный алгоритм, для достаточно малого ε, то он не смог бы отличить два набора данных.
Пример с монеткой, описанный выше является -дифференциально приватным[8].
Граничные случаи
Случай, когда ε = 0, является идеальным для сохранения конфиденциальности, поскольку наличие или отсутствие любой информации о любом человеке в базе данных никак не влияет на результат алгоритма, однако такой алгоритм является бессмысленным с точки зрения полезной информации, так как даже при нулевом количестве людей он будет давать такой же или подобный результат.
Если устремить ε в бесконечность, то любой вероятностный алгоритм будет подходить под определение, поскольку неравенство — выполняется всегда.
Чувствительность
Пусть — положительное целое число, — набор данных и — функция. Чувствительность [9] функции, обозначаемая , определяется формулой
по всем парам наборов данных и в , отличающихся не более чем одним элементом и где обозначает норму.
На выше приведённом примере медицинской базы данных, если мы рассмотрим чувствительность функции , то она равна , так как изменение любой из записей в базе данных приводит к тому, что либо изменится на либо не изменится.
Механизм Лапласа
В связи с тем, что дифференциальная приватность является вероятностной концепцией, любой её метод обязательно имеет случайную составляющую. Некоторые из них, как и метод Лапласа, используют добавление контролируемого шума к функции, которую нужно вычислить.
Метод Лапласа добавляет шум Лапласа, то есть шум от распределения Лапласа, который может быть выражен функцией плотности вероятности и который имеет нулевое математическое ожидание и стандартное отклонение . Определим выходную функцию как вещественнозначную функцию в виде где , а — это запрос, который мы планировали выполнить в базе данных. Таким образом можно считать непрерывной случайной величиной, где
которая не более (pdf — probability density function или функция плотности вероятности). В данном случае можно обозначить фактором конфиденциальности ε. Таким образом в соответствие с определением является ε-дифференциально приватной. Если мы попытаемся использовать эту концепцию в вышеприведённом примере про наличие гастрита, то для того, чтобы была ε-дифференциальный приватной функцией, должно выполняться , поскольку ).
Кроме шума Лапласа также можно использовать другие виды шума (например, гауссовский), но они могут потребовать небольшого ослабления определения дифференциальной приватности[10].
Композиция
Последовательное применение
Если мы выполним запрос в ε-дифференциально защищённой раз, и вносимый случайный шум независим для каждого запроса, тогда суммарная приватность будет (εt)-дифференциальной. В более общем случае, если есть независимых механизмов: , чьи гарантии приватности равны соответственно, то любая функция будет -дифференциально приватной[11].
Параллельная композиция
Кроме того, если запросы выполняются на непересекающихся подмножествах базы данных, то функция была бы -дифференциально приватной[11].
Приватность группы
Дифференциальная приватность в целом предназначена для защиты конфиденциальности между базами данных, которые отличаются только одной строкой. Это означает, что ни один злоумышленник с произвольной вспомогательной информацией не может узнать, представил ли какой-либо один отдельно взятый участник свою информацию. Однако это понятие можно расширить на группу, если мы хотим защитить базы данных, отличающиеся на строк, чтобы злоумышленник с произвольной вспомогательной информацией, не мог узнать, предоставили ли отдельных участников свою информацию. Это может быть достигнуто если в формуле из определения заменить на [12], тогда для D1 и D2 отличающихся на строчек
Таким образом, использование параметра (ε/c) вместо ε позволяет достичь необходимого результата и защитить строк. Другими словами, вместо того, чтобы каждый элемент был ε-дифференциально приватным, теперь каждая группа из элементов являются ε-дифференциально приватной, а каждый элемент (ε/c)-дифференциально приватным.
Применение дифференциальной приватности в реальных приложениях
На сегодняшний день известно несколько видов применения дифференциальной приватности:
- Бюро переписи населения США при показе статистики[13]
- Google RAPPOR для сбора статистики о нежелательном программном обеспечении, ущемляющем настройки пользователей [14](реализация RAPPOR с открытым исходным кодом)
- Google, для обмена статистикой истории трафика[15].
- 13 июня 2016 года Apple объявила о своём намерении использовать дифференциальную приватность в iOS 10 для улучшения своей интеллектуальной поддержки и предложений технологий[16]
Примечания
- ↑ Dwork Cynthia, 2006, p. 8.
- ↑ 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.
- ↑ Dwork Cynthia, 2006, p. 12.
- ↑ 1 2 Nissim et al, 2003, pp. 202—206.
- ↑ HILTON, MICHAEL. Differential Privacy: A Historical Survey (неопр.). Архивировано 1 марта 2017 года., p.1
- ↑ Dwork, 2008, pp. 3—13.
- ↑ Roth et al, 2014, p. 15.
- ↑ Roth et al, 2014, p. 30.
- ↑ Dwork et al, 2006, pp. 271—272.
- ↑ Dwork, 2008, p. 16.
- ↑ 1 2 McSherry, 2009, p. 6.
- ↑ Dwork Cynthia, 2006, p. 9.
- ↑ Machanavajjhala et al, 2008, p. 1.
- ↑ Erlingsson et al, 2014, p. 1.
- ↑ Tackling Urban Mobility with Technology by Andrew Eland . Google Policy Europe Blog. Дата обращения: 19 декабря 2017. Архивировано 10 декабря 2017 года.
- ↑ Apple - Press Info - Apple Previews iOS 10, the Biggest iOS Release Ever . Apple. Дата обращения: 16 июня 2016. Архивировано 29 апреля 2017 года.
Литература
- Ú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.