Криптография
Многосторонние вычисления (MPC)
Больница А имеет данные 1000 пациентов. Больница Б - 2000. Совместный датасет улучшит диагностику, но privacy laws запрещают обмен данными. MPC: обе больницы обучают модель совместно, ни одна не видит данные другой. Google делает то же с клавиатурой на миллиарде Android устройств.
- **Fireblocks**: MPC threshold ECDSA для institutional crypto custody. $15+ млрд, ключ никогда не существует в одном месте.
- **Google Gboard**: Federated Learning + Secure Aggregation. Модель улучшается от миллиарда пользователей без Google видя их набор текста.
- **Signal Private Contact Discovery**: PSI без раскрытия телефонной книги. Узнать какие контакты есть в Signal без передачи всей книги серверу.
- **SCALE-MAMBA / MP-SPDZ**: открытые MPC фреймворки. Используются в исследованиях и первых production-развертываниях в финансах и здравоохранении.
Garbled Circuits: шифрование схемы
Garbled Circuit (Яо, 1986): Garbler шифрует булеву схему так, что Evaluator может вычислить выход, не зная входные значения Garbler. Каждый провод имеет два случайных ключа - для 0 и для 1. Таблица истинности каждого гейта зашифрована парами ключей.
Два раунда протокола Яо: Garbler отправляет garbled circuit + свои входные ключи. Evaluator получает ключи для своих входов через Oblivious Transfer (без раскрытия Garbler). Evaluator вычисляет результат и отправляет Garbler (или оба видят output). Используется в Secure Two-Party Computation (2PC).
Почему Evaluator не может узнать входные значения Garbler из garbled circuit?
Oblivious Transfer: передача без знания
Oblivious Transfer (OT): Sender имеет n сообщений. Receiver хочет получить i-е без раскрытия i Sender. Sender не знает что получил Receiver. 1-of-2 OT - строительный блок для MPC. OT Extension позволяет из константного числа базовых OT получить миллионы за O(n) симметричных операций.
OT - фундаментальный примитив: из OT строится Garbled Circuits, GMW протокол, любой MPC. OT Extension (Ishai-Kilian-Nissim-Petrank 2003) делает OT практичным: вместо n EC-операций - n AES-операций. Современные реализации (libOTe, EMP-toolkit) достигают 10+ млн OT/секунду.
Какое ключевое свойство Oblivious Transfer (OT) делает его строительным блоком MPC?
Secret Sharing MPC: арифметика на закрытых данных
Arithmetic Secret Sharing MPC: каждый участник держит share числа. Сложение shares = share суммы (без коммуникации). Умножение требует коммуникации. Протоколы: BGW (информационно-теоретический), SPDZ (вычислительный, быстрее).
SPDZ (2012) и его вариации (MASCOT, OVERDRIVE) - доминирующий протокол для MPC с malicious security. Offline фаза генерирует Beaver triples (дорого). Online фаза: быстро (почти как plaintext). MP-SPDZ - открытый фреймворк для экспериментов с MPC протоколами.
Почему сложение в SS-MPC не требует коммуникации, а умножение - требует?
MPC в production: реальные случаи
MPC вышел из академических лабораторий в production. Применения: secure aggregation в federated learning (Google), threshold custody (Fireblocks, Coinbase), private set intersection (Apple CSAM proposal, Facebook contact discovery), auction privacy (Bosch car data marketplace).
Latency MPC: Garbled Circuits ~1ms/gate (быстро, но O(n^2) коммуникация при n участниках), SS-MPC ~1-10ms/умножение, Homomorphic Encryption ~1-1000ms/операция. Выбор зависит от числа участников, числа умножений и требований к latency. Для banking: SS-MPC. Для 2PC: GC. Для server-side: FHE.
Почему Google использует Secure Aggregation в Federated Learning вместо передачи градиентов напрямую?
Итоги
- **Garbled Circuits**: Garbler шифрует булеву схему. Evaluator вычисляет выход, не зная входы Garbler. Basis для 2PC протоколов Яо.
- **Oblivious Transfer**: Sender не знает что передал, Receiver не раскрывает выбор. Фундаментальный примитив, OT Extension = миллионы OT за O(n) AES.
- **SS-MPC**: arithmetic sharing + Beaver triples. Сложение бесплатно, умножение = 1 раунд коммуникации. SPDZ - стандарт для malicious MPC.
- **Production**: Fireblocks threshold custody, Google Federated Learning, Signal PSI. MPC из теории в $15+ млрд production систему.
Связанные темы
MPC объединяет все продвинутые примитивы:
- Разделение секрета — Secret Sharing (Шамир) - основа SS-MPC. VSS обеспечивает верификацию shares в MPC с malicious участниками.
- Гомоморфное шифрование — FHE - альтернатива MPC для server-side вычислений. MPC = несколько участников, FHE = один сервер на зашифрованных данных.
- Цифровые подписи — Threshold ECDSA через MPC - подпись без полного ключа. FROST = threshold Schnorr через MPC-inspired протокол.
Вопросы для размышления
- Federated Learning + Secure Aggregation защищает индивидуальные градиенты. Но если в группе только 2 участника - можно ли вычесть и восстановить данные второго?
- Garbled Circuits - 2PC протокол. Как расширить на 3+ участников? Что меняется в архитектуре?
- MPC с malicious участниками требует доказательств корректности каждого шага. SPDZ использует MACs для этого. Как это работает и какова стоимость?