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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Введение[править | править код]

Дифференциальная приватность — математическое определение потери конфиденциальных данных отдельных лиц, когда их личная информация используется для создания продукта. Этот термин был введён Синтией Дворк[en]* в 2006 году[1], но он же используется в более ранней публикации Дворк, Фрэнка Макшерри[fr], Коби Ниссима[fr] и Адама Д. Смита[fr][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)-дифференциально приватным.

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

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

  • Бюро переписи населения США при показе статистики[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. 1 2 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. 1 2 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.

Литература[править | править код]