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

Математика, которая вам понадобится

Почему это важно Инструменты приватности в этом модуле, например поиск общих клиентов без обмена списками или публикация статистики, защищающей каждого человека, держатся на трёх небольших кусочках математики. Диплом математика не нужен. Нужны арифметика часов, чувство вероятности и идея, что случайный шум в больших группах взаимно гасится. Этот урок даёт ровно это, с 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).
  • Возвести в секретную степень легко в одну сторону и практически невозможно отменить, а порядок двух секретных степеней не важен.
  • Вероятности независимых событий перемножаются; математическое ожидание - среднее на долгой дистанции.
  • Случайный шум скрывает отдельных людей, но гасится в больших группах, и именно так работает рандомизированный ответ.

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

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

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