Проблема MPC и искажённые схемы Яо

MPC позволяет n сторонам, каждая из которых владеет закрытым входным значением x_i, совместно вычислить f(x_1,...,x_n), не раскрывая друг другу свои входные данные, — как если бы вычисление выполняла доверенная третья сторона.

Задача миллионеров Яо 1982 года: Алиса и Боб хотят узнать, кто из них богаче, не раскрывая размер своего состояния. Доверенной третьей стороны нет. MPC решает эту задачу с криптографическими гарантиями.

1. Конфиденциальность: стороны узнают только результат и то, что могут из него вывести. 2. Корректность: результат остаётся правильным, даже если некоторые стороны скомпрометированы. 3. Существуют варианты для противников, следующих протоколу, и для злоумышленников.

Любую функцию можно представить в виде булевой схемы с вентилями AND, XOR и NOT. Протоколы MPC часто работают на уровне схем, безопасно вычисляя каждый вентиль.

Алиса, формирующая искажённую схему, назначает каждому проводу две случайные метки: одну для 0 и одну для 1. Она шифрует таблицу истинности каждого вентиля с использованием меток входных проводов. Боб, вычисляющий схему, получает только метки для своих входов с помощью передачи с забыванием.

Боб получает искажённые таблицы — по 4 шифрования для каждого вентиля AND. Он расшифровывает ровно одну строку с помощью меток своих входов и получает метку выхода, не узнавая, представляет ли она 0 или 1.

Добавьте к каждой метке случайный «бит выбора». С помощью этих битов Боб находит правильную строку искажённой таблицы за O(1), вместо того чтобы пробовать все четыре расшифрования. Это сокращает объём вычислений в 4 раза.

Kolesnikov и Schneider (2008): выберите глобальное смещение Δ. Тогда для каждого провода label_1 = label_0 ⊕ Δ. Вентили XOR становятся бесплатными — шифрование не требуется, что экономит примерно 30% пропускной способности.

Zahur и др. (2015): для каждого вентиля AND требуется всего 2 шифротекста вместо 4. В сочетании с Free-XOR это вдвое уменьшает пропускную способность стандартных искажённых схем.

Классические искажённые схемы рассчитаны на 2 стороны. Расширения для нескольких сторон (например, протокол BMR) распараллеливают формирование схемы между всеми сторонами, но требуют обмена данными сложности O(n²). Это практически применимо при небольшом n.

MPC позволяет сторонам совместно вычислять результат, не раскрывая входные данные. Искажённые схемы представляют булевы функции в виде зашифрованных таблиц истинности. Оптимизации (Free-XOR, полусхемы и «укажи и переставь») делают их практичными. OT позволяет Бобу конфиденциально получить метки для своих входов.