Безопасная агрегация
Почему это важно Фитнес-приложение хочет знать, сколько шагов в сумме прошли жители города; производитель клавиатуры хочет знать, как часто слово набирают на всех телефонах. В каждом случае компании нужно одно число от множества устройств. Безопасная агрегация позволяет узнать этот итог, не видя значения ни одного отдельного человека, и это удивительно просто.
Учебная криптография, не безопасная: числа в лабораториях этого модуля достаточно малы, чтобы их можно было прочитать, а случайность задана через seed, чтобы проверка была воспроизводимой. Настоящие системы используют проверенные библиотеки и гораздо большие числа. Никогда не копируйте учебный код в продукт.
Приём с зарплатой
Три друга хотят узнать среднюю зарплату, не раскрывая свою. Первая прибавляет к своей зарплате большое случайное число и шепчет результат второму. Он прибавляет свою зарплату и шепчет дальше. Третья прибавляет свою и передаёт обратно. Первая вычитает своё случайное число, и получается итог. Каждый шёпот выглядел для слышавшего как случайное число.
Безопасная агрегация: вычисление суммы (или среднего) значений многих людей так, что ни одно отдельное значение никому не раскрывается, включая сервер, который их собирает.
Аддитивное разделение секрета: разрезание секретного числа на несколько долей, которые по отдельности выглядят случайными, но в сумме дают секрет. Любая одна доля или любая группа, где не хватает хотя бы одной доли, ничего не раскрывает о секрете.
Как работают доли
Чтобы разделить число 7 350 на три доли, выберите два случайных числа, а третье подберите так, чтобы все три в сумме давали 7 350. С арифметикой с кругом (модуль M, здесь 2 в степени 32, чуть больше 4 миллиардов) каждая доля сама по себе - равномерно случайное число:
M = 2 ** 32
s1, s2 = 3919211450, 120775123 # random
s3 = (7350 - s1 - s2) % M # whatever makes it add up
print((s1 + s2 + s3) % M) # 7350
Зачем круг? Без него доля иногда была бы отрицательной или подозрительно близкой к секрету. С ним каждое значение доли одинаково вероятно, каким бы ни был секрет, поэтому одна доля не несёт информации.
Много устройств, несколько серверов
Теперь каждый телефон делит своё число шагов на одну долю на сервер и отправляет долю 1 на сервер 1, долю 2 на сервер 2 и так далее. Каждый сервер складывает полученные доли. Итог каждого сервера всё ещё выглядит случайным. Только когда итоги серверов складываются вместе, появляется настоящий итог по городу. Пока серверы не объединяют сырые доли одного телефона, значение ни одного телефона никто не видит.
Версия из реального мира
Системы, которые обучают модели на множестве телефонов (это называют федеративным обучением), используют более хитрый вариант с одним сервером: пары устройств договариваются о случайных масках, которые взаимно уничтожаются при сложении всего, плюс дополнительные шаги, чтобы справляться с телефонами, которые на полпути выходят из сети. Основная идея - та, которую вы построите: случайные на вид кусочки, которые имеют смысл только вместе.
Чего безопасная агрегация не делает
Итог раскрывается точно. Если вклад сделали только два человека и один знает своё значение, он может его вычесть и узнать значение другого. Если сам итог чувствителен, добавьте к нему ещё и шум дифференциальной приватности. Два инструмента хорошо работают вместе: агрегация скрывает входы, DP скрывает влияние каждого человека на результат.
На других языках
Разделение на JavaScript, с 32-битным кругом через >>> 0 и безопасным источником случайности браузера:
function split(value, n) {
const shares = Array.from(crypto.getRandomValues(new Uint32Array(n - 1)));
const sum = shares.reduce((a, b) => (a + b) >>> 0, 0);
shares.push((value - sum) >>> 0);
return shares;
}И на Rust, где wrapping_sub для u32 делает круг за вас:
let last = value.wrapping_sub(shares.iter().fold(0u32, |a, &b| a.wrapping_add(b)));Итоги
- Безопасная агрегация раскрывает итог, но ни одного отдельного вклада.
- Аддитивное разделение секрета делит значение на случайные на вид доли, которые в сумме его дают, с арифметикой с кругом.
- Каждый сервер видит только случайные на вид доли; ответ дают только все итоги серверов вместе.
- Сам итог раскрывается точно, поэтому сочетайте его с шумом DP, когда итог может выдать кого-то.
Напишите три функции, используя M (2 в степени 32) из учебного мира. split(value, n, rng) возвращает список из n долей: первые n - 1 из rng.randrange(M), последняя равна (value - sum(shares)) % M. combine(shares) возвращает sum(shares) % M. aggregate(values, n_servers, rng) делит каждое значение через split, прибавляет долю j к server_totals[j] (по модулю M) и возвращает кортеж (total, server_totals), где total = combine(server_totals).
Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке
Это упражнение откроется скоро
Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.
Этот браузер блокирует cookies для learn.floati.life, поэтому завершенные здесь уроки не могут открыться по порядку. Разрешите cookies для этого сайта и перезагрузите страницу.