Математика, которая вам понадобится
Почему это важно Инструменты приватности в этом модуле, например поиск общих клиентов без обмена списками или публикация статистики, защищающей каждого человека, держатся на трёх небольших кусочках математики. Диплом математика не нужен. Нужны арифметика часов, чувство вероятности и идея, что случайный шум в больших группах взаимно гасится. Этот урок даёт ровно это, с Python, чтобы попробовать.
1. Арифметика часов
Сейчас 22:00. Сколько времени будет через 5 часов? Не 27:00: часы делают круг, так что будет 03:00. Вы взяли 22 + 5 = 27 и оставили остаток от деления на 24.
Модульная арифметика: арифметика, где числа делают круг, достигнув фиксированного размера, модуля. "27 mod 24" - это 3, остаток от деления 27 на 24. В Python оператор остатка - %: 27 % 24 равно 3.
Круговой перенос держит числа фиксированного размера, сколько бы вы ни складывали или умножали, и именно это делает его полезным для криптографии. В Python также есть быстрая встроенная функция "возвести в степень, затем сделать круг": pow(base, exponent, modulus).
print((22 + 5) % 24) # 3
print(pow(3, 4, 7)) # 3*3*3*3 = 81, and 81 % 7 = 4
print(pow(5, 200, 23)) # instant, even though 5 to the 200 is huge
2. Легко в одну сторону, трудно в другую
Смешать жёлтую и синюю краску в зелёную легко. Разделить зелёную обратно на ровно те же жёлтую и синюю практически невозможно. Некоторая математика работает так же.
Возьмите большой простой модуль P и число h. Вычислить pow(h, a, P) для секретного a можно мгновенно. Но если есть только ответ, найти a снова для достаточно больших чисел так медленно, что никто не сможет. Это свойство одностороннести называют задачей дискретного логарифма.
Ещё один факт, и на нём работают следующие лаборатории. Возвести в a, а затем в b - то же самое, что возвести в b, а затем в a, потому что оба равны h в степени a, умноженное на b:
P = 1019 # a small prime: fine for learning, useless for security
h, a, b = 42, 123, 456
print(pow(pow(h, a, P), b, P) == pow(pow(h, b, P), a, P)) # True
Как два замка на одном ящике: порядок, в котором их вешают, не важен. Два человека могут каждый добавить свой секрет и прийти в одно и то же место, никогда не раскрывая своих секретов.
3. Вероятность в одном абзаце
Вероятность - число от 0 (никогда) до 1 (всегда). Честная монета падает орлом с вероятностью 0.5. Когда два события независимы, вероятность обоих - произведение: два орла подряд - это 0.5 × 0.5 = 0.25. Математическое ожидание - среднее на долгой дистанции: бросайте честный кубик много раз, и среднее приблизится к 3.5.
4. Шум гасится в толпе
Шум: случайная величина, намеренно добавленная к истинному значению, чтобы скрыть точное значение. Если шум с равной вероятностью идёт вверх и вниз, по многим значениям он в среднем даёт ноль.
Вот классический приём опросов, который называется рандомизированным ответом. Вы хотите узнать, сколько людей сделали что-то неловкое. Каждый тайно подбрасывает монету. Орёл: ответить честно. Решка: подбросить ещё раз и ответить "да" при орле и "нет" при решке. Любое отдельное "да" могло быть просто монетой, поэтому ничей ответ ничего о человеке не доказывает.
И всё же итог по толпе полезен. Если истинная доля - p, ожидаемая доля ответов "да" - 0.5 x p + 0.25. Так что если "да" сказали 35%, то p примерно (0.35 - 0.25) / 0.5 = 0.2, или 20%. Чем больше толпа, тем ближе оценка, потому что случайный шум с ростом толпы становится меньше относительно итога.
import random
rng = random.Random(1) # seeded: the same "random" numbers every run
truth = [rng.random() < 0.2 for _ in range(10000)] # 20% really did it
answers = []
for did_it in truth:
if rng.random() < 0.5:
answers.append(did_it) # heads: tell the truth
else:
answers.append(rng.random() < 0.5) # tails: random yes or no
yes = sum(answers) / len(answers)
print(round((yes - 0.25) / 0.5, 3)) # close to 0.2
Шум, используемый в дифференциальной приватности, называется шумом Лапласа и представляет собой гладкую версию той же идеи: обычно небольшой, иногда побольше, с равной вероятностью вверх или вниз. Его масштаб задаёт, насколько он обычно велик.
На других языках
% в JavaScript работает так же для положительных чисел, а для больших чисел используется BigInt (пишется с n). Встроенного модульного возведения в степень нет, поэтому вот стандартный цикл:
function powMod(base, exp, mod) {
let result = 1n;
base %= mod;
while (exp > 0n) {
if (exp & 1n) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1n;
}
return result;
}
console.log(powMod(3n, 4n, 7n)); // 4nВ Go то же самое делает new(big.Int).Exp(base, exp, mod) из math/big.
Распространённое заблуждение
"Добавление шума делает данные бесполезными." Для значения одного человека - да, и в этом весь смысл. Для большой группы шум в основном гасится, поэтому итоги и средние остаются полезными. Технологии приватности живут в этом зазоре: размыто для отдельных людей, чётко для толпы.
Итоги
- Модульная арифметика делает круг по модулю; в Python используются
%иpow(b, e, m). - Возвести в секретную степень легко в одну сторону и практически невозможно отменить, а порядок двух секретных степеней не важен.
- Вероятности независимых событий перемножаются; математическое ожидание - среднее на долгой дистанции.
- Случайный шум скрывает отдельных людей, но гасится в больших группах, и именно так работает рандомизированный ответ.
Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке
Это упражнение откроется скоро
Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.
Этот браузер блокирует cookies для learn.floati.life, поэтому завершенные здесь уроки не могут открыться по порядку. Разрешите cookies для этого сайта и перезагрузите страницу.