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

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

Введение

Дифференциальная приватность — математическое определение потери конфиденциальных данных отдельных лиц, когда их личная информация используется для создания продукта. Этот термин был введён Синтией Дворк в 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 является ε-дифференциально приватным, если для всех наборов данных и , которые отличаются одним элементом (то есть данными одного человека), а также всех подмножеств 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)-дифференциально приватным.

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

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

Примечания

  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 (неопр.)., 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.
  16. Apple - Press Info - Apple Previews iOS 10, the Biggest iOS Release Ever. Apple. Дата обращения: 16 июня 2016.

Литература

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.