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

Private Set Intersection

Почему это важно Компании часто хотят знать, какие клиенты у них общие, для совместного предложения или чтобы измерить, сработала ли реклама. Простой способ - обменяться списками клиентов, а это значит, что ваша почта попадает в базу другой компании. Private Set Intersection позволяет найти пересечение так, что ни одна сторона не отдаёт свой список. Зная, как это работает, вы отличите настоящую приватность от "мы передали только захэшированную почту".

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

Задача

У магазина и у приложения есть по списку адресов почты клиентов. Им нужны адреса, которые есть в обоих списках, и ничего больше: магазин не должен узнать других пользователей приложения, а приложение - других клиентов магазина.

Пересечение множеств: элементы, общие для двух списков. Private Set Intersection (PSI): способ для двух сторон вычислить его, не раскрывая ничего больше о своих списках.

Почему "просто захэшировать" не работает

Хэш: функция, которая превращает текст в мешанину фиксированной длины (распространённая - SHA-256). Один и тот же вход всегда даёт один и тот же выход, и прямо обратить её нельзя.

"Мы обмениваемся захэшированной почтой, так что настоящую никто не видит" звучит безопасно. Но адреса почты можно угадать. Любой, у кого есть список вероятных адресов, может захэшировать каждую догадку и искать совпадения, как перебирать все ключи на большой связке. Ваша функция naive_reverse сделает ровно это с 200 синтетическими адресами учебного мира. Хэширование скрывает данные, только когда входы нельзя угадать, а адреса почты, номера телефонов и имена угадать можно.

Приём с двумя замками

Вспомните урок математики: наложить секрет a, затем секрет b - то же самое, что b, затем a. Представьте каждый адрес почты как ящик. Алиса вешает свой замок на каждый свой ящик и отправляет их Бобу. Боб добавляет свой замок и отправляет обратно. Боб также запирает свои ящики и отправляет их Алисе, которая добавляет свой замок. Теперь на каждом ящике два замка, и два ящика с одинаковым адресом внутри выглядят одинаково, какой бы замок ни повесили первым.

В числах, с учебной группой из watched.leg7a_privacy (P, hash_to_group, random_secret):

  1. Алиса отправляет blind(alice_items, a): каждый элемент хэшируется в группу и возводится в a.
  2. Боб возводит их в b (reblind) и отправляет обратно в том же порядке.
  3. Боб отправляет blind(bob_items, b).
  4. Алиса возводит значения Боба в a. Любое из её дважды запертых значений, которое есть в дважды запертом наборе Боба, - общий элемент. Поскольку она сохранила порядок, она знает, каким из её элементов является каждое.

Почему это безопасно там, где хэширование провалилось? Чтобы проверить догадку, нужны оба секрета, а каждая сторона хранит свой. Боб видит значения Алисы только с её секретом, и они выглядят как случайные числа.

Diffie-Hellman PSI: название этого протокола, по идее обмена ключами 1976 года, которую он заимствует (две стороны комбинируют секретные показатели). Настоящие версии используют эллиптические кривые (другой вид группы с тем же свойством "порядок не важен" и гораздо более короткими числами) и аккуратное хэширование.

Ответ сам по себе раскрывает информацию

Даже идеальная PSI говорит Алисе, что конкретный человек - клиент Боба. Если Боб - клиника или консультант по долгам, это чувствительно. Часто компании нужно знать лишь, сколько клиентов общих. В PSI cardinality Боб перемешивает свой ответ на шаге 2, поэтому Алиса может посчитать совпадения, но не может понять, каким из её элементов они соответствуют. Просите минимум, который отвечает на вопрос.

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

Шаг ослепления на JavaScript с BigInt (с помощником powMod, как в уроке математики):

const blind = (items, secret) => items.map(x => powMod(hashToGroup(x), secret, P));
const reblind = (values, secret) => values.map(v => powMod(v, secret, P));

И на Go с math/big:

func reblind(values []*big.Int, secret, p *big.Int) []*big.Int {
    out := make([]*big.Int, len(values))
    for i, v := range values {
        out[i] = new(big.Int).Exp(v, secret, p)
    }
    return out
}

Для настоящих продуктов используйте проверенную аудитом библиотеку PSI, а не пишите свою.

Итоги

  • Захэшированную почту легко обратить списком догадок, поэтому "мы передали только хэши" - это не приватность.
  • Diffie-Hellman PSI дважды запирает каждый элемент двумя секретами, порядок которых не важен, поэтому совпадения проявляются без раскрытия списков.
  • Сохранение порядка раскрывает, какие элементы совпали; перемешивание (PSI cardinality) раскрывает только сколько.
  • Пересечение само по себе - персональные данные, поэтому просите минимум, который отвечает на вопрос.
Твоя очередь

Напишите пять функций. naive_reverse(hashes, candidates) возвращает отсортированный список кандидатов, чей шестнадцатеричный дайджест SHA-256 (hashlib.sha256(c.encode()).hexdigest()) есть в hashes. blind(items, secret) возвращает [pow(hash_to_group(x), secret, P) for x in items]. reblind(values, secret) возводит каждое значение в secret по модулю P, сохраняя порядок. psi(alice_items, bob_items, a_secret, b_secret) выполняет четыре шага урока с помощью blind и reblind и возвращает отсортированный список элементов Алисы, которые есть и у Боба. psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) делает то же, но перемешивает ответ Боба через rng.shuffle и возвращает только число общих элементов.

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

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

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