Русская Википедия:Дифференциальная приватность

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

Введение

Дифференциальная приватность — математическое определение потери конфиденциальных данных отдельных лиц, когда их личная информация используется для создания продукта. Этот термин был введён Синтией Дворк в 2006 годуШаблон:Sfn, но он же используется в более ранней публикации Дворк, Шаблон:Iw, Шаблон:Iw и Шаблон:Iw[1]. Работа основана в частности на исследованиях Ниссима и Ирит ДинурШаблон:SfnШаблон:Sfn, которые показали, что невозможно публиковать информацию из частной статической базы данных, не раскрывая некоторую часть приватной информации, и что вся база данных может быть раскрыта путём публикации результатов достаточно небольшого числа запросовШаблон:Sfn.

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

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

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

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

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

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

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

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

<math>P[\mathcal{A}(D_1) \in S] \leq e^{\epsilon} \times P[\mathcal{A}(D_2) \in S],</math>

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

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

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

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

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

Продолжая этот пример, если мы построим набор данных <math>D_2</math>, заменив (Михаил, 1) на (Михаил, 0), то злоумышленник сможет отличить <math>D_2</math> от <math>D_1</math> путём вычисления <math>Q_4 - Q_3</math> для каждого набора данных. Если бы злоумышленник получал значения <math>Q_i</math> через ε-дифференциально приватный алгоритм, для достаточно малого ε, то он не смог бы отличить два набора данных.

Пример с монеткой, описанный выше является <math>(\ln 3)</math>-дифференциально приватнымШаблон:Sfn.

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

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

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

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

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

<math>\Delta f=\max \lVert f(D_1)-f(D_2) \rVert_1,</math>

по всем парам наборов данных <math>D_1</math> и <math>D_2</math> в <math>\mathcal{D}</math>, отличающихся не более чем одним элементом и где <math>\lVert \cdot \rVert_1</math> обозначает <math>\ell_1</math> норму.

На выше приведённом примере медицинской базы данных, если мы рассмотрим чувствительность <math>d</math> функции <math>Q_i</math>, то она равна <math>1</math>, так как изменение любой из записей в базе данных приводит к тому, что <math>Q_i</math> либо изменится на <math>1</math> либо не изменится.

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

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

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

<math>\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))}\,\!</math>

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

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

Композиция

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

Если мы выполним запрос в ε-дифференциально защищённой <math>T</math> раз, и вносимый случайный шум независим для каждого запроса, тогда суммарная приватность будет (εt)-дифференциальной. В более общем случае, если есть <math>N</math> независимых механизмов: <math>\mathcal{M}_1,\dots,\mathcal{M}_n</math>, чьи гарантии приватности равны <math>\epsilon_1,\dots,\epsilon_n</math> соответственно, то любая функция <math>g(\mathcal{M}_1,\dots,\mathcal{M}_n)</math> будет <math>(\sum\limits_{i=1}^{n} \epsilon_i)</math>-дифференциально приватнойШаблон:Sfn.

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

Кроме того, если запросы выполняются на непересекающихся подмножествах базы данных, то функция <math>g</math> была бы <math>(\max_i {\epsilon}_i)</math>-дифференциально приватнойШаблон:Sfn.

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

Дифференциальная приватность в целом предназначена для защиты конфиденциальности между базами данных, которые отличаются только одной строкой. Это означает, что ни один злоумышленник с произвольной вспомогательной информацией не может узнать, представил ли какой-либо один отдельно взятый участник свою информацию. Однако это понятие можно расширить на группу, если мы хотим защитить базы данных, отличающиеся на <math>c</math> строк, чтобы злоумышленник с произвольной вспомогательной информацией, не мог узнать, предоставили ли <math>c</math> отдельных участников свою информацию. Это может быть достигнуто если в формуле из определения заменить <math>\exp ( \epsilon )</math> на <math>\exp ( \epsilon c )</math>Шаблон:Sfn, тогда для D1 и D2 отличающихся на <math>c</math> строчек

<math>\Pr[\mathcal{A}(D_{1})\in S]\leq

\exp(\epsilon c)\times\Pr[\mathcal{A}(D_{2})\in S]\,\!</math>

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

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

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

Примечания

Шаблон:Примечания

Литература

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Статья
  2. ↑ Шаблон:Статья, p.1
  3. ↑ Шаблон:Cite web
  4. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Дифференциальная_приватность&oldid=9757188