Дифференциальная конфиденциальность

редактировать

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

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

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

Содержание

1 История
2 ε-дифференциальная конфиденциальность
- 2.1 Определение ε-дифференциальной конфиденциальности
- 2.2 Возможность комбинирования
- 2.3 Устойчивость к постобработке
- 2.4 Конфиденциальность группы
3 ε-дифференциально частные механизмы
- 3.1 Чувствительность
- 3.2 Механизм Лапласа
- 3.3 Рандомизированный ответ
- 3.4 Устойчивые преобразования
4 Другие понятия дифференциальной конфиденциальности
5 Принятие дифференциальной конфиденциальности в реальном мировые приложения
6 См. также
7 Ссылки
8 Дополнительная литература
9 Внешние ссылки

История

Официальные статистические организации обязаны собирать информацию от частных лиц или учреждений и публиковать совокупные данные данные в интересах общества. Например, в ходе переписи 1790 г. в США была собрана информация о лицах, проживающих в США, и опубликованы таблицы, основанные на полу, возрасте, расе и условиях подневольного труда. Статистические организации давно собирают информацию, обещая конфиденциальность, что предоставленная информация будет использоваться в статистических целях, но публикации не будут содержать информацию, которая может быть прослежена до конкретного человека или учреждения. Для достижения этой цели статистические организации долгое время скрывали информацию в своих публикациях. Например, в таблице, в которой представлены продажи каждого бизнеса в городе, сгруппированные по бизнес-категориям, ячейка, содержащая информацию только от одной компании, может быть скрыта, чтобы сохранить конфиденциальность конкретных продаж этой компании.

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

В 1977 году Тор Далениус формализовал математику подавления клеток.

В 1979 году Дороти Деннинг, Питер Дж. Деннинг и Майер Д. Шварц формализовал концепцию трекера, злоумышленника, который может узнать конфиденциальное содержимое статистической базы данных, создав серию целевых запросов и запомнив результаты. Это и дальнейшие исследования показали, что свойства конфиденциальности в базе данных можно сохранить только при рассмотрении каждого нового запроса в свете (возможно, всех) предыдущих запросов. Это направление работы иногда называют конфиденциальностью запросов, в результате чего отслеживание влияния запроса на конфиденциальность отдельных лиц в базе данных было NP-сложной задачей.

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

В 2006 году Синтия Дворк, Фрэнк МакШерри, Кобби Ниссим и Адам Д. Смит опубликовали статью, формулирующую количество шума, которое необходимо добавить, и предложение общего механизма для этого. Их работа стала со-обладателем награды TCC Test-of-Time Award 2016 и Gödel Prize.

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

ε-дифференциальная конфиденциальность

В статье Дворка, МакШерри, Ниссима и Смита 2006 года была представлена концепция ε-дифференциальной конфиденциальности, математическое определение потери конфиденциальности, связанной с любой выпуск данных из статистической базы данных. (Здесь термин «статистическая база данных» означает набор данных, которые собираются под залогом конфиденциальности с целью получения статистических данных, которые в результате их производства не ставят под угрозу конфиденциальность тех лиц, которые предоставили данные.)

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

Конечно, вклад каждого человека в результат базы данных частично зависит от того, сколько данных людей задействовано в запросе. Если база данных содержит данные от одного человека, данные этого человека составляют 100%. Если база данных содержит данные от сотни человек, данные каждого человека составляют всего 1%. Ключевое понимание дифференциальной конфиденциальности состоит в том, что, поскольку запрос выполняется на основе данных все меньшего и меньшего числа людей, необходимо добавить больше шума к результату запроса, чтобы обеспечить такую же степень конфиденциальности. Отсюда и название статьи 2006 года «Калибровка шума по чувствительности при анализе частных данных».

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

Определение ε-дифференциальной конфиденциальности

Пусть ε будет положительным действительным числом и $A {\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ быть рандомизированным алгоритмом, который принимает набор данных в качестве входных данных (представляющий действия доверенной стороны, хранящей данные). Пусть $im A {\ displaystyle {\ textrm {im}} \ {\ mathcal {A}}}$ ${\ displaystyle {\ textrm {im}} \ {\ mathcal {A}}}$ обозначает изображение из $A {\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ . Считается, что алгоритм $A {\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ обеспечивает $ϵ {\ displaystyle \ epsilon}$ $\ epsilon$ -дифференциальную конфиденциальность, если для всех наборы данных $D 1 {\ displaystyle D_ {1}}$ $D_ {1}$ и $D 2 {\ displaystyle D_ {2}}$ $D_ {2}$ , которые отличаются одним элементом (т. е. данные одного человека), и все подмножества $S {\ displaystyle S}$ $S$ из $im A {\ displaystyle {\ textrm {im}} \ {\ mathcal {A}}}$ ${\ displaystyle {\ textrm {im}} \ {\ mathcal {A}}}$ :

$Pr [A (D 1) ∈ S] ≤ ехр ⁡ (ϵ) ⋅ Pr [A (D 2) ∈ S], {\ displaystyle \ Pr [{\ mathcal {A}} (D_ {1}) \ в S] \ leq \ exp \ left (\ epsilon \ right) \ cdot \ Pr [{\ mathcal {A}} (D_ {2}) \ in S],}$ ${\ displaystyle \ Pr [{\ mathcal {A}} (D_ {1}) \ in S] \ leq \exp \left(\epsilon \right)\cdot \Pr[{\mathcal {A}}(D_{2})\in S],}$

где вероятность берется по случайность, используемая алгоритмом.

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

Composabilit y

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

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

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

Устойчивость к постобработке

Для любой детерминированной или рандомизированной функции $F {\ d isplaystyle F}$ $F$ , определенный поверх образа механизма $A {\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ , если $A {\ displaystyle {\ mathcal { A}}}$ ${\ mathcal {A}}$ удовлетворяет ε-дифференциальной конфиденциальности, так же как и $F (A) {\ displaystyle F ({\ mathcal {A}})}$ ${\ displaystyle F ({\ mathcal {A}})}$ .

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

Групповая конфиденциальность

В общем, ε-дифференциальная конфиденциальность предназначена для защиты конфиденциальности между соседними базами данных, которые отличаются только в одной строке. Это означает, что ни один противник с произвольной вспомогательной информацией не может знать, предоставил ли один конкретный участник свою информацию. Однако это также можно расширить, если мы хотим защитить базы данных, различающиеся строками $c {\ displaystyle c}$ $c$ , что означает, что злоумышленник с произвольной вспомогательной информацией может знать, $c {\ displaystyle c}$ $c$ конкретные участники представили свою информацию. Этого можно достичь, потому что если $c {\ displaystyle c}$ $c$ элементы изменяются, расширение вероятности ограничивается $exp ⁡ (ϵ c) {\ displaystyle \ exp (\ epsilon c)}$ $\ exp (\ epsilon c)$ вместо $exp ⁡ (ϵ) {\ displaystyle \ exp (\ epsilon)}$ $\exp ( \epsilon)$ ,т.е. для D 1 и D 2 различаются на $c {\ displaystyle c}$ $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) \ cdot \ Pr [{\ mathcal {A}} (D_ {2}) \ in S] \, \!}

{\ displaystyle \ Pr [{\ mathcal {A}} (D_ {1}) \ in S] \ leq \ exp (\ epsilon c) \ cdot \ Pr [{\ mathcal {A}} (D_ {2}) \ in S] \, \!}

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

ε-дифференциально частные механизмы

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

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

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

Δ f = max ‖ f (D 1) - f (D 2) ‖ 1., {\ displaystyle \ Delta f = \ max \ lVert f (D_ {1}) - f (D_ {2}) \ rVert _ {1},}

{\ displaystyle \ Delta f = \ max \ lVert f (D_ {1}) - f (D_ {2}) \ rVert _ {1},}

где максимум - по всем парам наборов данных $D 1 {\ displaystyle D_ {1}}$ $D_ {1}$ и $D 2 {\ displaystyle D_ {2}}$ $D_ {2}$ в $D {\ displaystyle {\ mathcal {D} }}$ ${\ mathcal {D}}$ отличается не более чем одним элементом, а $‖ ⋅ ‖ 1 {\ displaystyle \ lVert \ cdot \ rVert _ {1}}$ ${\ Displaystyle \ lVert \ cdot \ rVert _ {1}}$ обозначает $ℓ 1 {\ displaystyle \ ell _ {1}}$ $\ ell _ {1}$ norm.

В примере из медицинской базы данных ниже, если мы рассматриваем $f {\ displaystyle f}$ $f$ как быть функцией $Q i {\ displaystyle Q_ {i}}$ $Q_ {i}$ , тогда чувствительность функции равна единице, так как изменение любой из записей в базе данных приводит к изменению вывода функции либо на ноль, либо на единицу.

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

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

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

pdf (TA, D 1 (x) = t) pdf (TA, D 2 (x) = t) = шум (t - f (D 1)) шум (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 {{\ text {noise}} (tf (D_ {1})) } {{\ text {noise}} (tf (D_ {2}))}} \, \!}

\ frac {\ mathrm {pdf} (\ mathcal {T} _ {\ mathcal {A}, D_1} (x) = t)} {\ mathrm {pdf} (\ mathcal {T} _ {\ mathcal {A}, D_2 } (x) = t)} = \ frac {\ text {noise} (tf (D_1))} {\ text {noise} (tf (D_2))} \, \!

., которое не превышает $e | f (D 1) - f (D 2) | λ ≤ е Δ (е) λ {\ Displaystyle е ^ {\ гидроразрыва {| f (D_ {1}) - f (D_ {2}) |} {\ lambda}} \ leq e ^ {\ frac {\ Delta (f)} {\ lambda}} \, \!}$ $e ^ {\ frac {| f (D_ {1}) - f (D_ {2}) |} {\ lambda}} \ leq e ^ {\ frac {\ Delta (f)} {\ lambda}} \, \!$ . Мы можем рассматривать $Δ (f) λ {\ displaystyle {\ frac {\ Delta (f)} {\ lambda}} \, \!}$ $\ frac { \ Delta (f)} {\ lambda} \, \!$ как фактор конфиденциальности $ϵ { \ Displaystyle \ epsilon \, \!}$ $\ epsilon \, \!$ . Таким образом, $T {\ displaystyle {\ mathcal {T}} \, \!}$ $\ mathcal {T} \, \!$ следует дифференциально закрытому механизму (как видно из определения выше). Если мы попытаемся использовать эту концепцию в нашем примере с диабетом, то из полученного выше факта следует, что для того, чтобы иметь $A {\ displaystyle {\ mathcal {A}} \, \!}$ $\mathcal{A}\,\!$ как $ϵ {\ displaystyle \ epsilon \, \!}$ $\ epsilon \, \!$ -дифференциальный частный алгоритм, который нам нужен $λ = 1 / ϵ {\ displaystyle \ lambda = 1 / \ epsilon \, \ !}$ $\ lambda = 1 / \ epsilon \, \!$ . Хотя здесь мы использовали шум Лапласа, можно использовать и другие формы шума, такие как гауссовский шум, но они могут потребовать небольшого ослабления определения дифференциальной конфиденциальности.

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

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

Имя	Диабет (X)
Росс	1
Моника	1
Джои	0
Фиби	0
Чендлер	1
Рэйчел	0

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

Продолжая этот пример, если мы построим $D 2 {\ displaystyle D_ {2}}$ $D_ {2}$ , заменив (Chandler, 1) на (Chandler, 0), тогда этот злонамеренный противник будет уметь отличать $D 2 {\ displaystyle D_ {2}}$ $D_ {2}$ от $D 1 {\ displaystyle D_ {1}}$ $D_ {1}$ путем вычисления $Q 5 - Q 4 {\ displaystyle Q_ {5} -Q_ {4}}$ ${\ displaystyle Q_ {5} -Q_ {4}}$ для каждого набора данных. Если противник должен был получить значения $Q i {\ displaystyle Q_ {i}}$ $Q_ {i}$ через $ϵ {\ displaystyle \ epsilon}$ $\ epsilon$ -дифференциально закрытый алгоритм, для достаточно маленького $ϵ {\ displaystyle \ epsilon}$ $\ epsilon$ он или она не сможет различить два набора данных.

Случайный ответ

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

Подбросьте монету.
Если выпадет орел, то снова подбросьте монету (игнорируя результат) и честно ответьте на вопрос.
Если выпала решка, то снова подбросьте монету и ответьте «Да», если решка, и «Нет», если решка.

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

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

В частности, если атрибут A является синонимом незаконного поведения, то ответ «Да» не является компрометирующим, поскольку у человека есть вероятность ответа «Да», каким бы он ни был.

Хотя этот пример, вдохновленный рандомизированным ответом, может быть применим к микроданным (т. Е. Выпуск наборов данных с каждым отдельным ответом), по определению дифференциальная конфиденциальность исключает выпуск микроданных и применимо только к запросам (т. е. объединению отдельных ответов в один результат), поскольку это нарушит требования, в частности правдоподобное отрицание того, участвовал или нет субъект.

Стабильные преобразования

A преобразование $T {\ displaystyle T}$ $T$ является $c {\ displaystyle c}$ $c$ -устойчивым, если расстояние Хэмминга между $T (A) {\ displaystyle T (A)}$ $T (A)$ и $T (B) {\ displaystyle T (B)}$ $T(B)$ не более $c {\ displaystyle c}$ $c$ -кратное расстояние Хэмминга между $A {\ displaystyle A}$ $A$ и $B {\ displaystyle B}$ $B$ для любых двух баз данных $A, B {\ displaystyle А, В}$ $A,B$ . Теорема 2 утверждает, что если существует механизм $M {\ displaystyle M}$ $M$ , который является $ϵ {\ displaystyle \ epsilon}$ $\ epsilon$ -дифференциально частным, то составной механизм $M ∘ T {\ displaystyle M \ circ T}$ $M \ circ T$ is $(ϵ × c) {\ displaystyle (\ epsilon \ times c)}$ $(\ epsilon \ times c)$ -дифференциально закрытый.

Это можно обобщить на конфиденциальность группы, поскольку размер группы можно представить как расстояние Хэмминга $h {\ displaystyle h}$ $ч$ между $A {\ displaystyle A }$ $A$ и $B {\ displaystyle B}$ $B$ (где $A {\ displaystyle A}$ $A$ содержит группу, а $B {\ displaystyle B}$ $B$ - нет). В этом случае $M ∘ T {\ displaystyle M \ circ T}$ $M \ circ T$ равно $(ϵ × c × h) {\ displaystyle (\ epsilon \ times c \ times h)}$ $(\ epsilon \ times c \ раз ч)$ - дифференциально частный.

Другие понятия дифференциальной конфиденциальности

Поскольку дифференциальная конфиденциальность считается слишком сильной или слабой для некоторых приложений, было предложено множество ее версий. Наиболее распространенное ослабление - (ε, δ) -дифференциальная конфиденциальность, которая ослабляет определение, допуская дополнительную малую плотность вероятности δ, при которой верхняя граница ε не выполняется.

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

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

2008: США Бюро переписи, для демонстрации схем передвижения.
2014: Google RAPPOR, для телеметрии, такой как изучение статистики о нежелательном ПО, захватывающем настройки пользователей (RAPPOR's open- реализация источника ).
2015: Google, для обмена исторической статистикой трафика.
2016: Apple объявила о намерении использовать дифференциальную конфиденциальность в iOS 10 для улучшения своей Интеллектуальный персональный помощник технология.
2017: Microsoft, для телеметрии в Windows.
2019: Privitar Lens - это API, использующий дифференциальную конфиденциальность.
2020: LinkedIn для запросов рекламодателей.

См. Также

Квазиидентификатор
Экспоненциальный механизм (дифференциальная конфиденциальность) - метод разработки дифференциально частных алгоритмов
k-анонимность
Дифференциально конфиденциальный анализ графики

Ссылки

Дополнительная литература

Список литературы по дифференциальной конфиденциальности
Абоуд, Джон. 2017. «Как будут работать статистические агентства, когда все данные будут Частный?". Журнал конфиденциальности и конфиденциальности 7 (3). doi : 10.29012 / jpc.v7i3.404 (слайды )
«Differential Privacy: A Primer for a Нетехническая аудитория ", Кобби Ниссим, Томас Стейнке, Александра Вуд, Мика Альтман, Аарон Бембенек, Марк Бун, Марко Габоарди, Дэвид Р. О'Брайен и Салил Вадхан, Harvard Privacy Tools Project, 14 февраля 2018 г.
Динур, Ирит и Кобби Ниссим.2003. Раскрытие информации при сохранении конфиденциальности. В материалах двадцать второго симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных (PODS '03). ACM, Нью-Йорк, Нью-Йорк, США, 202–210. doi : 10.1145 / 773153.773173.
Дворк, Синтия, Фрэнк МакШерри, Кобби Ниссим и Адам Смит. 2006. в Халеви., S. Rabin, T. (Eds.) Калибровка шума по чувствительности в теории анализа частных данных криптографии: Третья конференция по теории криптографии, TCC 2006, Нью-Йорк, Нью-Йорк, США, 4–7 марта 2006 г. Proceedings, Springer Берлин Гейдельберг, 265-284, doi : 10.1007 / 11681878 14.
Дворк, Синтия. 2006. Differential Privacy, 33-й международный коллоквиум по автоматам, языкам и программированию, часть II (ICALP 2006), Springer Verlag, 4052, 1-12, ISBN 3-540-35907- 9.
Дворк, Синтия и Аарон Рот. 2014. Алгоритмические основы дифференциальной конфиденциальности. Основы и тенденции теоретической информатики. Vol. 9, №№ 3–4. 211–407, doi : 10.1561 / 0400000042.
Мачанаваджхала, Ашвин, Дэниел Кифер, Джон М. Абоуд, Йоханнес Герке и Ларс Вилхубер. 2008. Конфиденциальность: теория соответствует практике на карте, Международная конференция по инженерии данных (ICDE) 2008: 277-286, doi : 10.1109 / ICDE.2008.4497436.
Дворк, Синтия и Мони Наор. 2010. О трудностях предотвращения раскрытия информации в статистических базах данных или аргументах в пользу особой конфиденциальности, Журнал неприкосновенности частной жизни и конфиденциальности: Vol. 2: Вып. 1, статья 8. Доступно по адресу: http://repository.cmu.edu/jpc/vol2/iss1/8.
Кифер, Дэниел и Ашвин Мачанаваджхала. 2011. Никакого бесплатного обеда в области конфиденциальности данных. В материалах Международной конференции ACM SIGMOD 2011 года по управлению данными (SIGMOD '11). ACM, Нью-Йорк, Нью-Йорк, США, 193-204. doi : 10.1145 / 1989323.1989345.
Эрлингссон, Эльфар, Василий Пихур и Александра Королова. 2014. ДОКЛАД: рандомизированный агрегированный порядковый ответ с сохранением конфиденциальности. В материалах конференции ACM SIGSAC 2014 по компьютерной и коммуникационной безопасности (CCS '14). ACM, Нью-Йорк, Нью-Йорк, США, 1054-1067. doi : 10.1145 / 2660267.2660348.
Абоуд, Джон М. и Ян М. Шмутте. 2017 г. Пересмотр экономики конфиденциальности: статистика населения и защита конфиденциальности как общественные блага. Институт динамики труда Корнельского университета, Институт динамики труда Корнельского университета, на https://digitalcommons.ilr.cornell.edu/ldi/37/
Абоуд, Джон М. и Ян М. Шмутте. Скоро. Экономический анализ защиты конфиденциальности и статистической точности как социального выбора. American Economic Review, arXiv : 1808.06303
Apple, Inc., 2016. Apple представляет iOS 10, самую крупную версию iOS за всю историю. Пресс-релиз (13 июня). https://www.apple.com/newsroom/2016/06/apple-previews-ios-10-biggest-ios-release-ever.html.
Дин, Болин, Джанардхан Кулькарни и Сергей Еханин, 2017. Сбор данных телеметрии в частном порядке, NIPS 2017.
http://www.win-vector.com/blog/2015/10/a-simpler-explanation-of-differential-privacy/
Ryffel, Theo, Andrew Траск и др. al. «Общая структура для сохранения конфиденциальности глубокого обучения»

Внешние ссылки

Дифференциальная конфиденциальность, Синтия Дворк, ICALP, июль 2006 г.
Алгоритмические основы дифференциальной конфиденциальности, Синтия Дворк и Аарон Рот, 2014.
Дифференциальная конфиденциальность: обзор результатов, Синтия Дворк, Microsoft Research, апрель 2008 г.
Конфиденциальность динамических данных: постоянное наблюдение и общая конфиденциальность, Мони Наор, Институт передовых технологий Исследование, ноябрь 2009 г.
Учебное пособие по дифференциальной конфиденциальности от Катрина Лигетт, Калифорнийский технологический институт, декабрь 2013 г.
Практическое руководство по дифференциальной конфиденциальности для новичков от Кристин Таск, Университет Пердью, Апрель 2012 г.
Private Map Maker v0.2 в блоге Common Data Project
Изучение статистики с конфиденциальностью, с помощью брошенной монеты Эльфара Эрлингссона, исследовательский блог Google, октябрь 2014 г.