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

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

¶История

Концепция дифференциальной приватности была формально введена в 2006 году в работах Синтии Дворк, Фрэнка Макшерри, Коби Ниссима и Адама Смита. Она стала развитием идей, заложенных в более ранних методах защиты данных, таких как рандомизированный ответ (randomized response) и k-анонимность. Основным недостатком предшествующих подходов была их уязвимость к атакам, основанным на априорных знаниях атакующего. Дифференциальная приватность предложила строгую математическую модель, не зависящую от внешней информации.

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

¶Математическое определение

Формально алгоритм \( \mathcal{M} \) удовлетворяет \( \varepsilon \)-дифференциальной приватности, если для любых двух наборов данных \( D_1 \) и \( D_2 \), отличающихся ровно на одну запись (например, удаление или добавление данных одного человека), и для любого подмножества возможных результатов \( S \subseteq \text{Range}(\mathcal{M}) \) выполняется неравенство:

\[ \Pr[\mathcal{M}(D_1) \in S] \leq e^\varepsilon \cdot \Pr[\mathcal{M}(D_2) \in S] \]

Здесь \( \varepsilon \) (эпсилон) — параметр, называемый бюджетом приватности. Чем меньше \( \varepsilon \), тем сильнее гарантия конфиденциальности, но тем больше шума вносится в результат. Значение \( \varepsilon = 0 \) соответствует абсолютной приватности (независимость результата от данных), а \( \varepsilon = \infty \) — отсутствию какой-либо защиты.

¶Композиция

Одно из важных свойств дифференциальной приватности — композиция. Если несколько дифференциально-приватных алгоритмов применяются к одному и тому же набору данных, то общий уровень защиты ухудшается. Например, если два алгоритма, каждый с параметром \( \varepsilon_1 \), применяются последовательно, результирующий бюджет приватности будет не более \( 2\varepsilon_1 \). Это свойство позволяет оценивать совокупный риск при многократном использовании данных.

¶Механизмы реализации

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

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

Наиболее распространенный механизм для числовых данных. Шум добавляется из распределения Лапласа с математическим ожиданием 0 и масштабом, пропорциональным чувствительности запроса (максимальному изменению результата при изменении одной записи) и обратно пропорциональным \( \varepsilon \). Чувствительность запроса \( \Delta f \) — это максимальное изменение результата функции \( f \) при замене одной записи в наборе данных.

¶Механизм Гаусса

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

¶Экспоненциальный механизм

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

¶Применение

¶Технологические компании

• Apple: с 2016 года использует дифференциальную приватность для сбора данных о поведении пользователей в iOS и macOS. Данные обезличиваются на устройстве перед отправкой на серверы компании. Сбор включает информацию о частоте использования эмодзи, поисковых запросах в Safari, словарях и т.д.
• Google: разработала систему RAPPOR (Randomized Aggregatable Privacy-Preserving Ordinal Response), которая используется в Chrome для сбора статистики о вредоносных сайтах и настройках браузера. Также применяется в Google Maps для оценки загруженности дорог на основе данных о местоположении пользователей.
• Microsoft: использует дифференциальную приватность в телеметрии Windows и в некоторых сервисах Azure.

¶Государственная статистика

• Бюро переписи населения США: в 2020 году впервые применило дифференциальную приватность для публикации данных переписи. Это решение было принято для защиты конфиденциальности респондентов в условиях, когда злоумышленники могут использовать другие, доступные из открытых источников, данные для деанонимизации. Применение дифференциальной приватности привело к снижению точности некоторых статистических показателей, особенно для малых групп населения, что вызвало критику со стороны демографов и исследователей.

¶Машинное обучение

В обучении с подкреплением и глубоком обучении дифференциальная приватность применяется для защиты данных, используемых для обучения модели. Метод DP-SGD (Differentially Private Stochastic Gradient Descent) добавляет шум к градиентам на каждом шаге оптимизации, ограничивая влияние отдельных обучающих примеров на итоговую модель.

¶Критика и ограничения

• Потеря точности: основной недостаток дифференциальной приватности — неизбежное снижение точности результатов. Чем сильнее защита (меньше \( \varepsilon \)), тем больше шума и тем менее полезны данные. Выбор \( \varepsilon \) всегда является компромиссом между приватностью и полезностью.
• Сложность выбора \( \varepsilon \): не существует единого стандарта для «безопасного» значения \( \varepsilon \). В различных приложениях используются значения от 0.1 до 10 и выше. Критики утверждают, что без контекста и понимания атак, которые могут быть проведены, выбор \( \varepsilon \) остается произвольным.
• Атаки на композицию: хотя композиция формально определена, на практике применение множества запросов к одним и тем же данным может привести к накоплению утечек, которые сложно контролировать.
• Не защищает от всех угроз: дифференциальная приватность гарантирует, что присутствие или отсутствие конкретной записи не повлияет на результат. Однако она не защищает от атак, основанных на корреляциях между записями (например, если у двух людей одинаковые данные) или от атак, использующих информацию из других источников.
• Проблемы внедрения: реализация дифференциальной приватности в реальных системах сложна. Требуется точный расчет чувствительности запросов, управление бюджетом приватности и обеспечение корректности рандомизации. Ошибки в реализации могут полностью свести на нет защиту.

¶Источники

• Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006). Calibrating Noise to Sensitivity in Private Data Analysis. Theory of Cryptography.
• Dwork, C., & Roth, A. (2014). The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science.
• Apple. (2016). Differential Privacy Overview. Apple Developer Documentation.
• Erlingsson, Ú., Pihur, V., & Korolova, A. (2014). RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security.
• Abowd, J. M. (2018). The U.S. Census Bureau Adopts Differential Privacy. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.