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

18.12.2020

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

Введение

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

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

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

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

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

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

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

    Пусть ε — положительное действительное число и A — вероятностный алгоритм, который принимает на вход набор данных (представляет действия доверенной стороны, обладающей данными). Образ A обозначим imA. Алгоритм A является ε-дифференциально приватным, если для всех наборов данных D 1 {displaystyle D_{1}} и D 2 {displaystyle D_{2}} , которые отличаются одним элементом (то есть данными одного человека), а также всех подмножеств S множества imA:

    P [ A ( D 1 ) ∈ S ] ≤ e ϵ × P [ A ( D 2 ) ∈ S ] , {displaystyle P[{mathcal {A}}(D_{1})in S]leq e^{epsilon } imes P[{mathcal {A}}(D_{2})in S],}

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

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

    Например, предположим, что у нас есть база данных медицинских записей D 1 {displaystyle D_{1}} где каждая запись представляет собой пару (Имя, X), где X {displaystyle X} является нулём или единицей, обозначающим, имеет ли человек гастрит или нет:

    Теперь предположим, что злонамеренный пользователь (часто называемый злоумышленником) хочет найти, имеет ли Михаил гастрит или нет. Также предположим, что он знает, в какой строке находится информация о Михаиле в базе данных. Теперь предположим, что злоумышленнику разрешено использовать только конкретную форму запроса Q i {displaystyle Q_{i}} , который возвращает частичную сумму первых i {displaystyle i} строк столбца X {displaystyle X} в базе данных. Чтобы узнать, есть ли гастрит у Михаила, злоумышленник выполняет запросы: Q 4 ( D 1 ) {displaystyle Q_{4}(D_{1})} и Q 3 ( D 1 ) {displaystyle Q_{3}(D_{1})} , затем вычисляет их разницу. В данном примере, Q 4 ( D 1 ) = 3 {displaystyle Q_{4}(D_{1})=3} , а Q 3 ( D 1 ) = 2 {displaystyle Q_{3}(D_{1})=2} , поэтому их разность равна 1 {displaystyle 1} . Это значит, что поле «Наличие гастрита» в строке Михаила должно быть равно 1 {displaystyle 1} . Этот пример показывает, как индивидуальная информация может быть скомпрометирована даже без явного запроса данных конкретного человека.

    Продолжая этот пример, если мы построим набор данных D 2 {displaystyle D_{2}} , заменив (Михаил, 1) на (Михаил, 0), то злоумышленник сможет отличить D 2 {displaystyle D_{2}} от D 1 {displaystyle D_{1}} путём вычисления Q 4 − Q 3 {displaystyle Q_{4}-Q_{3}} для каждого набора данных. Если бы злоумышленник получал значения Q i {displaystyle Q_{i}} через ε-дифференциально приватный алгоритм, для достаточно малого ε, то он не смог бы отличить два набора данных.

    Пример с монеткой, описанный выше является ( ln ⁡ 3 ) {displaystyle (ln 3)} -дифференциально приватным.

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

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

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

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

    Пусть d {displaystyle d} — положительное целое число, D {displaystyle {mathcal {D}}} — набор данных и f : D → R d {displaystyle fcolon {mathcal {D}} ightarrow mathbb {R} ^{d}} — функция. Чувствительность функции, обозначаемая Δ f {displaystyle Delta f} , определяется формулой

    Δ f = max ‖ f ( D 1 ) − f ( D 2 ) ‖ 1 , {displaystyle Delta f=max lVert f(D_{1})-f(D_{2}) Vert _{1},}

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

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

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

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

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

    p d f ( T A , D 1 ( x ) = t ) p d f ( T A , D 2 ( x ) = t ) = noise ( t − f ( D 1 ) ) noise ( t − f ( D 2 ) ) {displaystyle {frac {mathrm {pdf} ({mathcal {T}}_{{mathcal {A}},D_{1}}(x)=t)}{mathrm {pdf} ({mathcal {T}}_{{mathcal {A}},D_{2}}(x)=t)}}={frac {{ ext{noise}}(t-f(D_{1}))}{{ ext{noise}}(t-f(D_{2}))}},!}

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

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

    Композиция

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

    Если мы выполним запрос в ε-дифференциально защищённой T {displaystyle T} раз, и вносимый случайный шум независим для каждого запроса, тогда суммарная приватность будет (εt)-дифференциальной. В более общем случае, если есть N {displaystyle N} независимых механизмов: M 1 , … , M n {displaystyle {mathcal {M}}_{1},dots ,{mathcal {M}}_{n}} , чьи гарантии приватности равны ϵ 1 , … , ϵ n {displaystyle epsilon _{1},dots ,epsilon _{n}} соответственно, то любая функция g ( M 1 , … , M n ) {displaystyle g({mathcal {M}}_{1},dots ,{mathcal {M}}_{n})} будет ( ∑ i = 1 n ϵ i ) {displaystyle (sum limits _{i=1}^{n}epsilon _{i})} -дифференциально приватной.

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

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

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

    Дифференциальная приватность в целом предназначена для защиты конфиденциальности между базами данных, которые отличаются только одной строкой. Это означает, что ни один злоумышленник с произвольной вспомогательной информацией не может узнать, представил ли какой-либо один отдельно взятый участник свою информацию. Однако это понятие можно расширить на группу, если мы хотим защитить базы данных, отличающиеся на c {displaystyle c} строк, чтобы злоумышленник с произвольной вспомогательной информацией, не мог узнать, предоставили ли c {displaystyle c} отдельных участников свою информацию. Это может быть достигнуто если в формуле из определения заменить exp ⁡ ( ϵ ) {displaystyle exp(epsilon )} на exp ⁡ ( ϵ c ) {displaystyle exp(epsilon c)} , тогда для D1 и D2 отличающихся на c {displaystyle c} строчек

    Pr [ A ( D 1 ) ∈ S ] ≤ exp ⁡ ( ϵ c ) × Pr [ A ( D 2 ) ∈ S ] {displaystyle Pr[{mathcal {A}}(D_{1})in S]leq exp(epsilon c) imes Pr[{mathcal {A}}(D_{2})in S],!}

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

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

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

    • Бюро переписи населения США при показе статистики
    • Google RAPPOR для сборе статистики о нежелательном программном обеспечении, ущемляющем настройки пользователей (реализация RAPPOR с открытым исходным кодом)
    • Google, для обмена статистикой истории трафика.
    • 13 июня 2016 года Apple объявила о своём намерении использовать дифференциальную приватность в iOS 10 для улучшения своей интеллектуальной поддержки и предложений технологий


    Имя:*
    E-Mail:
    Комментарий:
    Информационный некоммерческий ресурс fccland.ru © 2020
    При цитировании и использовании любых материалов ссылка на сайт обязательна