Протокол GMW и забывчивая передача

Протокол Goldreich-Micali-Wigderson (GMW) вычисляет булевы схемы с использованием секретов, распределённых посредством XOR. Значение каждого провода разделяется между всеми сторонами, которые взаимодействуют для каждого вентиля.

Сторона i хранит долю s_i, такую что s_1 ⊕ s_2 ⊕ ... ⊕ s_n = w (истинное значение провода). Вентили XOR бесплатны: каждая сторона локально выполняет XOR над своими долями.

Для вентиля AND над проводами a и b вычисление (a_1⊕a_2)(b_1⊕b_2) раскрывается в перекрёстные слагаемые. Вычисление перекрёстного слагаемого a_i·b_j между сторонами i≠j требует передачи с забыванием.

В передаче с забыванием 1-из-2 отправитель имеет сообщения (m_0, m_1), а получатель — бит выбора c. Получатель получает m_c; отправитель ничего не узнаёт о c, а получатель ничего не узнаёт о m_{1-c}.

Протокол основан на обмене ключами Диффи — Хеллмана: получатель создаёт два открытых ключа и знает дискретный логарифм только одного из них. Отправитель шифрует каждое сообщение одним из ключей. Получатель расшифровывает только выбранный им шифротекст.

Ishai и др. (2003): из k базовых OT можно получить m >> k передач с помощью только операций с симметричным ключом. Расширение IKNP снижает стоимость OT примерно до 3 вызовов AES на одну передачу после однократной настройки.

Для каждого вентиля AND требуется одна передача с забыванием между каждой парой сторон. При использовании расширения OT все передачи можно заранее вычислить на автономном этапе, и тогда на этапе выполнения для каждого вентиля потребуется только один обмен XOR-значениями.

GMW с противниками, следующими протоколу, можно сделать защищённым от злоумышленников с помощью доказательств с нулевым разглашением или OT с разбиением и выбором. Стоимость возрастает в 3–8 раз, но обеспечивается защита от жульничающих сторон.

MASCOT (Keller и др.) расширяет OT для создания аутентифицированных троек AND в модели злоумышленника, что делает возможным протокол SPDZ, который рассматривается в следующем уроке.

EMP-toolkit и MOTION реализуют GMW с расширением OT. Они достигают миллионов вентилей AND в секунду между двумя сторонами по LAN, благодаря чему реальные приложения становятся практически осуществимыми.

Почему в протоколе GMW вентили XOR не требуют обмена данными между сторонами?

GMW использует секреты, распределённые посредством XOR, в булевых схемах. Вентили XOR бесплатны, а для вентилей AND требуется OT. Расширение OT делает передачу с забыванием дешёвой. Защита от злоумышленников добавляет доказательства с нулевым разглашением или разбиение и выбор. Библиотеки вроде EMP обеспечивают практическую производительность для реальных приложений.