Резюме: иногда важно знать основы! Это третье сообщение в блоге из серии Основы дифференциальной конфиденциальности, охватывающее быстрое и простое введение в определение дифференциальной конфиденциальности - Epsilon, delta и т. Д. Чтобы увидеть больше подобных сообщений о дифференциальной конфиденциальности, подпишитесь на Shaistha Fathima в твиттере.

Серия "Основы дифференциальной конфиденциальности"

Что такое конфиденциальность?

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

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

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

Согласно наиболее распространенному определению DP, данному Синтией Дворк в ее книге Алгоритмические основы дифференциальной конфиденциальности

Дифференциальная конфиденциальность описывает обещание, данное держателем данных или куратором субъекту данных (владельцу), и обещание выглядит следующим образом: «Разрешение ваших данных не повлияет на вас каким-либо иным образом. для использования в любом исследовании или анализе, независимо от того, какие другие исследования, наборы данных или источники информации доступны ».

Формальное определение дифференциальной конфиденциальности:

Формула Синтии Дворк:

Где,

M: рандомизированный алгоритм, то есть query(db) + noise или query(db + noise).

S: весь потенциальный выход M, который можно было спрогнозировать.

x: Записи в базе данных. (т.е. N)

y: записи в параллельной базе данных (т. е. N-1)

ε: максимальное расстояние между запросом в базе данных (x) и таким же запросом в базе данных (y).

δ: вероятность случайной утечки информации.

ПРИМЕЧАНИЕ. Это определение действительно для ОДНОГО ЗАПРОСА в базе данных, а не для нескольких запросов.

Ключевые моменты, на которые следует обратить внимание:

  • Это определение DP не создает DP, вместо этого оно является мерой «Насколько конфиденциальность обеспечивается запросом?»
  • Он позволяет сравнить выполнение запроса M к базе данных (x) и параллельной базе данных (y) (на одну запись меньше, чем в исходной базе данных).
  • Мера, по которой эти две вероятности случайного распределения полной базы данных (x) и параллельной базы данных (y) могут различаться, задается значениями Epsilon (ε) и дельта (δ).

(1) Эпсилон (ε):

Это максимальное расстояние между запросом в базе данных (x) и таким же запросом в базе данных (y). То есть это показатель потери конфиденциальности при различном изменении данных (т. Е. Добавлении или удалении 1 записи). Также известен как параметр конфиденциальности или бюджет конфиденциальности.

(i) Когда ε мало

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

Все малые эпсилоны (ε) одинаковы, т. Е. характер гарантий конфиденциальности с разными, но маленькими эпсилонами очень похож.

(ii) Когда ε велико

Неспособность быть (15,0) -дифференциально закрытой просто означает, что существуют соседние базы данных и выход M, для которого отношение вероятностей наблюдения M при условии, что база данных будет, соответственно, x или y, велико.

Выход M может быть очень маловероятным (это решается с помощью (ε, δ) -дифференциальной конфиденциальности); для баз данных x и y могут быть ужасно надуманными и вряд ли появятся в «реальном мире»; злоумышленник может не иметь нужной вспомогательной информации, чтобы распознать, что произошел разоблачительный результат; или может не знать достаточно о базах данных, чтобы определить значение их симметричной разницы.

Меньшее ε даст лучшую конфиденциальность, но менее точный ответ.

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

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

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

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

(i) Epsilon Zero (ε = 0): ВЫХОД запроса для всех параллельных баз данных имеет то же значение, что и полная (исходная) база данных. Часто, если чувствительность = 0, то и ε = 0 тоже.

(ii) Epsilon One (ε = 1): максимальное расстояние между всеми запросами будет равно 1 ИЛИ максимальное расстояние между двумя случайными распределениями M (x) и M (y) равно 1.

Также можно указать, что ε или бюджет конфиденциальности - это ограничение отдельных лиц на то, насколько конфиденциально они согласны с утечкой.

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

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

Примеры из реального мира

1. Бюджеты Apple и конфиденциальности:

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

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

2. Перепись 2020:

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

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

(2) Дельта (δ):

Это вероятность случайной утечки информации. Если δ = 0, мы говорим, что выход M является ε-дифференциально частным.

Обычно нас интересуют значения δ, которые меньше обратного любого полинома в размере базы данных.

(i) Значения δ порядка 1 / ∥x∥1 очень опасны: они разрешают «сохранение конфиденциальности» путем публикации полные записи небольшого числа участников базы данных - это именно философия «всего нескольких», согласно которой защищены только те люди, которые, как считается, имеют большую озабоченность по поводу конфиденциальности.

(ii) Когда δ пренебрежимо мало или равно нулю: это называется ε-дифференциальной конфиденциальностью или (ε, 0) -дифференциальной конфиденциальностью.

Примечание. ε не зависит от размера базы данных, где, как и в случае δ, вероятность утечки информации может увеличиваться с увеличением размера базы данных. Следовательно, в идеале мы хотели бы установить значение δ меньше, чем величина, обратная размеру базы данных.

Это подводит нас к вопросу - (ε, 0) или ε -дифференциальная конфиденциальность VS (ε, δ) -дифференциальная конфиденциальность?

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

В то время как,

(ε, δ) -дифференциальная конфиденциальность говорит о том, что для каждой пары соседних баз данных x, y крайне маловероятно, что ex post facto наблюдаемое значение M (x) будет намного больше или гораздо менее вероятно, что они будут сгенерированы, когда база данных равна x, чем когда база данных равна y. Это гарантирует, что для всех соседних x, y, абсолютное значение потери конфиденциальности будет ограничено ε с вероятностью не менее 1 − δ.

Итак, что это значит?

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

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

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

Вот и все, ребята! В следующем посте этой серии мы рассмотрим типы механизмов добавления шума в Differential Privacy и их сравнение.

А пока вы можете ознакомиться с другой моей серией для начинающих: