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

В 2006 году Синтия Дворк, Фрэнк МакШерри, Кобби Ниссим и Адам Смит^[3] ввели строгое математическое определение — ε-дифференциальную приватность — для количественной оценки потери приватности при любом использовании статистической базы данных^[4]. Статистическая база данных в данном контексте — данные, собранные под обещание конфиденциальности для получения статистических показателей без риска раскрытия сведений об отдельных лицах.

Определение ε-дифференциальной приватности требует, чтобы изменение одной записи в базе вызывало только незначительное изменение вероятностного распределения выходных данных алгоритма, наблюдаемого противником^[3]. Интуитивно, приватность не может быть скомпрометирована статистической публикацией, если соответствующие данные отсутствуют в базе^[5]. Каждый участник получает примерно ту же степень приватности, что и в случае удаления его данных^[5]. Статистическая обработка не должна существенно меняться при удалении, добавлении или изменении отдельной записи^[5].

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

Пусть ε — положительное действительное число, а ${\displaystyle {\mathcal {A}}}$ — рандомизированный алгоритм, принимающий на вход набор данных (от имени доверенного держателя). Пусть ${\displaystyle {\textrm {im}}\ {\mathcal {A}}}$ обозначает образ этого алгоритма.

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

$${\displaystyle \Pr[{\mathcal {A}}(D_{1})\in S]\leq e^{\varepsilon }\Pr[{\mathcal {A}}(D_{2})\in S]+\delta .}$$

Здесь вероятность берётся по внутреннему случайному выбору алгоритма^[6]. Это определение иногда называют «приближённой дифференциальной приватностью»; случай δ = 0 — это «чистая дифференциальная приватность».

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

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

Пример: пусть имеется база медицинских записей ${\displaystyle D_{1}}$, где каждая запись — пара (Имя, X), X — булево значение (1 — есть диабет, 0 — нет):

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

Если вместо (Чендлер, 1) в базе ${\displaystyle D_{2}}$ стоит (Чендлер, 0), злоумышленник по тем же запросам отличает ${\displaystyle D_{1}}$ от ${\displaystyle D_{2}}$. Если бы ответы на ${\displaystyle Q_{i}}$ возвращал ε-дифференциально приватный алгоритм с малым ε, отличить два набора данных было бы невозможно.

Композиционность означает, что совокупность результатов (возможно, адаптивно выбираемых) разных дифференциально приватных механизмов сохраняет приватность^[3]

• Последовательная композиция. Если задать ε-дифференциальный механизм ${\displaystyle t}$ раз (независимыми запросами), итоговый механизм будет ${\displaystyle \varepsilon t}$-дифференциально приватным. Если есть n независимых механизмов с параметрами ${\displaystyle \varepsilon _{1},\dots ,\varepsilon _{n}}$, то любая функция от их выходов будет ${\displaystyle \left(\sum \limits _{i=1}^{n}\varepsilon _{i}\right)}$-дифференциально приватной.^[7].

• Параллельная композиция. Если механизмы применяются к непересекающимся подмножествам базы, итоговый механизм будет ${\displaystyle (\max _{i}\varepsilon _{i})}$-дифференциально приватным^[7].

Робастность к постобработке — если функция ${\displaystyle F}$ определена на выходе ${\displaystyle {\mathcal {A}}}$, и \mathcal{A} ε-дифференциально приватен, то F(\mathcal{A}) — тоже^[3]

Эти свойства позволяют строить сложные механизмы с модулярными гарантиями и формируют так называемый «бюджет утечки приватности». Если все элементы сложного механизма по отдельности дифференциально приватны, то и их комбинация (и даже любая последующая обработка результатов) такова же.^[3]

Обычно ε-дифференциальная приватность защищает отличие между наборами данных, различающимися в одной записи, то есть от раскрытия участия отдельного лица. Однако это свойство расширимо^[3]: если нужно защитить и группы из c участников, то вероятность расхождения ограничивается ${\displaystyle \exp(\varepsilon c)}$ вместо ${\displaystyle \exp(\varepsilon )}$.^[8]. То есть выбор ε/c вместо ε позволяет защищать группы; так, каждая группа из c записей защищена параметром ε, а отдельный элемент — (ε/c)-дифференциально приватен^[3]

Дифференциальную приватность можно понимать как ограничение ошибок первого и второго рода в задаче гипотез:

• ${\displaystyle H_{0}}$: данных индивидуума в базе нет.
• ${\displaystyle H_{1}}$: данные присутствуют.

Соответственно:

• Ложно-положительная (FPR): ${\displaystyle P_{\text{FP}}=\Pr[{\text{противник выбирает }}H_{1}|H_{0}]}$
• Ложно-отрицательная (FNR): ${\displaystyle P_{\text{FN}}=\Pr[{\text{выбран }}H_{0}|H_{1}]}$

При заданном (ε, δ) возможные пары ошибок удовлетворяют:

• ${\displaystyle \{(P_{\text{FP}},P_{\text{FN}})\mid P_{\text{FP}}+e^{\varepsilon }P_{\text{FN}}\geq 1-\delta ,\ e^{\varepsilon }P_{\text{FP}}+P_{\text{FN}}\geq 1-\delta \}}$

Поскольку дифференциальная приватность опирается на вероятностные методы, практически все приватные механизмы являются рандомизированными. Некоторые, как механизм Лапласа, используют добавление контролируемого шума; другие, например, экспоненциальный механизм^[9]. и выборка из апостериорного распределения^[10], строят выборки из семейства распределений, зависящего от задачи.

Ключевое понятие для построения приватных механизмов — чувствительность функции^[3] Пусть d — положительное целое, ${\displaystyle {\mathcal {D}}}$ — множество наборов данных, а f — отображение ${\displaystyle f\colon {\mathcal {D}}\to \mathbb {R} ^{d}}$. Тогда чувствительность f, обозначим её ${\displaystyle \Delta f}$, определяется как:

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

${\displaystyle D_{1}}$

${\displaystyle D_{2}}$

${\displaystyle \lVert \cdot \rVert _{1}}$

Для других пространств расстояний (метрик), например, при использовании гауссовского шума потребуется L2-норма.^[3]

Существует ряд методов, позволяющих получать дифференциально приватные оценки для функций с разной чувствительностью.^[3]

Механизм Лапласа добавляет шум из распределения Лапласа, плотность функции которого задаётся как ${\displaystyle {\text{noise}}(y)\propto \exp(-|y|/\lambda )}$, где среднее 0, а стандартное отклонение ${\displaystyle {\sqrt {2}}\lambda }$. Пусть функция результата алгоритма ${\displaystyle {\mathcal {A}}}$ задаётся как ${\displaystyle {\mathcal {T}}_{\mathcal {A}}(x)=f(x)+Y}$, где ${\displaystyle Y\sim {\text{Lap}}(\lambda )}$.

Для любых двух наборов данных различие в распределениях выхода не превышает ${\displaystyle e^{\Delta (f)/\lambda }}$. Если положить ${\displaystyle \lambda =\Delta (f)/\varepsilon }$, то получаем ε-дифференциальную приватность. Для нашего примера (сумма по столбцу, чувствительность 1) надо использовать ${\displaystyle \lambda =1/\varepsilon }$. Можно применять другие распределения шума, например гауссовское, но для них потребуется ослабленное определение приватности.^[8]

Простейший случай — рандомизированный ответ, введённый в социологии.^[11]. Пример процедуры:

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

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

Общая доля положительных ответов позволяет оценить истинную частоту признака по формуле: если p — доля носителей, то ожидаемое число «да» — (¼)(1 − p) + (¾)p = ¼ + p/2.

Если признак — противоправное поведение, то даже «да» не компрометирует участника, поскольку всегда остаётся вероятность случайного попадания.

Хотя эта схема применяется к микроданным (индивидуальным ответам), классическая дифференциальная приватность касается лишь агрегированных запросов, так как публикация микроданных подрывает принцип правдоподобного отрицания участия^[12][13].

Преобразование ${\displaystyle T}$ называется c-стабильным, если расстояние Хэмминга между ${\displaystyle T(A)}$ и ${\displaystyle T(B)}$ не больше c раз превышает расстояние между ${\displaystyle A}$ и ${\displaystyle B}$. Если механизм ${\displaystyle M}$ ε-дифференциально приватен, то композиция ${\displaystyle M\circ T}$ обладает (ε×c)-дифференциальной приватностью^[7].

С помощью этой идеи обобщается групповая приватность: группа размера h защищена с коэффициентом ε×c×h.

В 1977 году шведский статистик Туре Далениус заложил математические основы блокировки ячеек для минимизации утечек при публикации таблиц^[14]. Его ключевой вывод: статистические базы не должны раскрывать информации об индивидууме, которую нельзя получить иначе^[15]. Он также предложил типологию видов раскрытий^[4].

В 1979 году Дороти Деннинг, Питер Дж. Деннинг и Майер Шварц предложили концепцию трекера: противника, способного восстановить приватные сведения на основе последовательности целевых запросов и запоминания их результатов^[16]. Было показано, что учёт влияния каждого нового запроса на приватность индивидов — задача очень сложная (NP-трудная).

В 2003 году Кобби Ниссим и Ирит Динур доказали невозможность открытой публикации любого количества запросов к приватной статистической базе без риска раскрытия личных данных: уже относительно небольшое число случайных выборок позволяет восстановить всю базу^[17]. Это явление называют «фундаментальным законом восстановления информации»: для защиты приватности необходим ввод случайного шума.

В 2006 году Синтия Дворк, Фрэнк МакШерри, Кобби Ниссим и Адам Смит^[3] предложили формальный способ калибровки объёма случайного шума и универсальный механизм защиты приватности. В этой же работе впервые было строго определено само понятие дифференциальной приватности^[4]. Их статья получила премии TCC Test-of-Time Award (2016)^[18] и премию Гёделя (2017)^[19].

Дальнейшие исследования показали, что можно получать достаточно точную статистику при существенно высоко гарантированной приватности^[1].

Известно более десяти внедрений дифференциальной приватности в реальных проектах, включая:

• 2008: Бюро переписи США — анализ схем ежедневных поездок на работу.
• 2014: Google RAPPOR — телеметрия (исследование вредоносных изменений настроек пользователя)^[20][21].
• 2015: Google — публикация исторической статистики дорожного движения^[22].
• 2016: Apple (iOS 10) — для интеллектуального помощника^[23].
• 2017: Microsoft — в телеметрии Windows^[24].
• 2021: Бюро переписи США — публикация данных о переразделении округов по итогам переписи 2020 года^[25].

Существует ряд вопросов дифференциальной приватности, имеющих значение для принятия решений (особенно для разработчиков стандартов, государственных структур и исследователей общественной политики):^[26]

• Полезность и точность данных. Главная проблема — компромисс между полезностью и приватностью: увеличение параметра приватности ведёт к потере точности (добавляется шум), а при приоритете полезности — приватность ухудшается. Для каждой задачи важен контекст выбора параметра. Снижение точности — не уникальная проблема дифференциальной приватности, но именно здесь у исследователей и регуляторов есть возможность управлять рисками за счёт выбора подхода.
• Приватность и безопасность данных. Дифференциальная приватность позволяет количественно управлять риском утечки и устанавливать верхнюю (гарантированную) границу компрометации, при этом делая настройку компромисса между точностью и приватностью явной. Метод устойчив к новым (ещё неизвестным) атакам. Одновременно рост открытости может повысить риск при неаккуратном использовании методов. Гарантия приватности в реальности зависит от правильного выбора параметра приватности.

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

• Мелкие аналитические и алгоритмические ошибки^[27][28].
• Тайминговые сайд-ченнел-атаки^[29]. Для дифференциальной приватности тайминговые каналы могут дать прямую утечку скрываемого бита информации в цели атаки.
• Утечки через особенности вычисления с плавающей точкой^[30]. Математическая модель не учитывает особенности реализации плавающей точки, что может приводить к потере приватности (особенно для «чистой» ε-дифференциальной приватности). Например, наивная реализация механизма Лапласа покрывает менее 80 % возможных двойной точности чисел, а распределения с разными средними могут быть различимы по одному пробному значению.
• Тайминговый канал даже из-за операций с вещественными числами^[31]. Некоторые значения могут обрабатываться в сотни раз дольше обычных (например, для субнормальных чисел), что делает эти операции заметными для атакующих^[32][33].