Программа курса Урок 134 из 156 · Технологии приватности помимо блокировки
Технологии приватности помимо блокировки

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

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

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

Обещание

Представьте опрос, результаты которого публикуют с вашим ответом и без него. Если два опубликованных результата выглядят почти одинаково, то никто, читая их, не сможет сказать, участвовали ли вы, не говоря уже о том, что вы ответили. Это и есть всё обещание.

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

Эпсилон: число, которое говорит, насколько велико это "почти". Маленький эпсилон (скажем, 0.1) значит много шума и сильную приватность; большой эпсилон (скажем, 5) - мало шума и слабую приватность. Для простого подсчёта добавление шума Лапласа с масштабом 1 / epsilon даёт epsilon-DP, потому что один человек может изменить подсчёт не больше чем на 1.

Бюджет

Вот в чём подвох. Задайте один и тот же зашумлённый вопрос много раз и усредните ответы: шум гасится, как показал урок математики, и проступает истинное число. Значит, каждый ответ немного утекает, и утечки складываются.

Композиция: когда вы отвечаете на несколько вопросов об одних и тех же людях, их эпсилоны складываются. Четыре ответа с эпсилоном 0.25 стоят в сумме 1.0.

Бюджет приватности: общий эпсилон, который вы разрешаете для набора данных. Каждый ответ тратит часть. Когда бюджет исчерпан, вы перестаёте отвечать, как бы вежливо ни просил аналитик.

Представьте предоплаченную карту: каждый вопрос что-то стоит, баланс только уменьшается, а отклонённый вопрос ничего не стоит. Вы построите именно этот учёт. Шум уже готов: laplace(scale, rng) в учебном мире.

Локальная и центральная DP в реальном мире

Локальная DP: каждое устройство добавляет шум до отправки, поэтому у компании никогда нет истинных значений (рандомизированный ответ - это локальная DP). Центральная DP: доверенный сервер хранит истинные данные и добавляет шум только к результатам, которые публикует.

Apple объявила в 2016 году, что использует локальную дифференциальную приватность, чтобы узнавать, например, популярные новые слова и эмодзи с устройств, не собирая то, что напечатал конкретный человек. Ранняя система Google, RAPPOR (2014), тоже была локальной и использовалась для сбора статистики из её браузера. Локальной DP нужно очень много шума на человека, поэтому она даёт полезные ответы только для очень больших толп и довольно частых значений. Значительная часть более поздних опубликованных работ Google, например её библиотека дифференциальной приватности с открытым кодом (2019), использует центральную модель, где для того же эпсилона нужно гораздо меньше шума, ценой доверия серверу сырых данных.

Ни одна модель не является "единственно правильной". Локальная DP защищает вас даже от компании; центральная DP даёт более точную статистику. Безопасная агрегация, через два урока, - один из способов получить что-то от обеих.

На других языках

Та же проверка бюджета на JavaScript:

function spend(budget, epsilon) {
  if (epsilon <= 0) return false;
  if (budget.spent + epsilon > budget.total + 1e-9) return false;
  budget.spent += epsilon;
  budget.log.push(epsilon);
  return true;
}

И на Rust, где правила заимствования делают "ничего не менять при отказе" явным:

fn spend(b: &mut Budget, eps: f64) -> bool {
    if eps <= 0.0 || b.spent + eps > b.total + 1e-9 { return false; }
    b.spent += eps;
    b.log.push(eps);
    true
}

Зачем 1e-9?

Компьютеры хранят десятичные дроби приближённо: в Python 0.1 + 0.2 - это 0.30000000000000004. Без крошечного допуска трата ровно всего бюджета маленькими шагами могла бы ошибочно отклоняться. Настоящие библиотеки обрабатывают это аккуратнее; здесь достаточно маленького допуска.

Распространённое заблуждение

"Шум значит, что опубликованные числа неверны, поэтому DP бесполезна." Шум подобран, чтобы скрыть одного человека, а не тенденцию. Число 412, опубликованное как 409 или 415, всё ещё говорит магазину, какие страницы популярны, а число 31 посетитель деликатной страницы нельзя использовать, чтобы подтвердить, что конкретный человек был одним из них.

Итоги

  • DP обещает, что результаты почти не меняются с любым отдельным человеком или без него; эпсилон измеряет это "почти".
  • Для подсчёта шум Лапласа с масштабом 1 / epsilon даёт epsilon-DP.
  • Эпсилоны складываются по вопросам, поэтому бюджет нужно отслеживать и соблюдать, а отказы ничего не стоят.
  • Локальная DP (шум на устройстве) никому не доверяет, но требует огромных толп; центральная DP точнее, но доверяет серверу.
Твоя очередь

Напишите четыре функции, которые управляют бюджетом приватности. make_budget(total) возвращает {"total": total, "spent": 0.0, "log": []}. remaining(budget) возвращает total минус spent. spend(budget, epsilon) возвращает False и ничего не меняет, если epsilon - не конечное число больше 0 (0, отрицательное, nan или бесконечность: проскочивший nan сделал бы spent равным nan, и каждая следующая проверка проходила бы, так что бюджет никогда бы не кончился), или если трата подняла бы spent выше total больше чем на 1e-9; иначе она добавляет epsilon к spent, дописывает его в log и возвращает True. noisy_count(true_count, epsilon, budget, rng) возвращает None, если spend отказывает, иначе true_count + laplace(1 / epsilon, rng). Оценивается учёт, а не точные зашумлённые числа.

Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке

Это упражнение откроется скоро

Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.