Протокол конфиденциального вычисления

В криптографии протокол конфиденциального вычисления (также безопасное/защищенное/тайное многостороннее вычисление, англ. secure multi-party computation) — криптографический протокол, позволяющий нескольким участникам произвести вычисление, зависящее от тайных входных данных каждого из них, таким образом, чтобы ни один участник не смог получить никакой информации о чужих тайных входных данных. Впервые задача конфиденциального вычисления была поднята Эндрю Яо (англ. Andrew Yao) в 1982 году в статье^[1]. Два миллионера, Алиса и Боб, хотят выяснить, кто же из них богаче, при этом они не хотят разглашать точную сумму своего благосостояния. Яо предложил в своей статье оригинальный способ решения этой задачи. Гораздо позже, в 2004 году Йехуда Линделл (Yehuda Lindell) и Бенни Пинкас (Benny Pinkas) предоставили математически строгое доказательство корректности протокола Яо в статье^[2]. Задача конфиденциального вычисления тесно связана с задачей разделения секрета.

Формализованная постановка задачи

В конфиденциальном вычислении участвуют N участников p₁, p₂, …, p_N, у каждого участника есть тайные входные данные d₁, d₂, …, d_N соответственно. Участники хотят найти значение F(d₁, d₂, …, d_N), где F — известная всем участникам вычислимая функция от N аргументов. Допускается, что среди участников будут получестные нарушители, то есть те, которые верно следуют протоколу, но пытаются получить дополнительную информацию из любых промежуточных данных.

Описание протокола

Для простоты допустим, что в вычислении участвуют 2 участника, то есть N=2.

• Представим функцию F в виде логического контура. На вход логического контура подаются биты всех аргументов функции F, сам контур состоит из логических гейтов AND, OR и NOT, и на выходе выдаёт результат функции F в двоичном формате.
• Участник p₁ генерирует для каждого провода логической схемы два различных случайных числа k⁰ u k¹: они представляют ноль и единицу в этом проводе соответственно.
• Участник p₁ создаёт для каждого контура зашифрованную таблицу вычисления. Для бинарного гейта OR такая таблица будет выглядеть следующим образом:

Входной провод w1	Входной провод w2	Выходной провод w3	Зашифрованая таблица вычисления
$k_1^0$	$k_2^0$	$k_3^0$	$c_1 = E_{k_1^0}(E_{k_2^0}(k_3^0))$
$k_1^0$	$k_2^1$	$k_3^1$	$c_2 = E_{k_1^0}(E_{k_2^1}(k_3^1))$
$k_1^1$	$k_2^0$	$k_3^1$	$c_3 = E_{k_1^1}(E_{k_2^0}(k_3^1))$
$k_1^1$	$k_2^1$	$k_3^1$	$c_4 = E_{k_1^1}(E_{k_2^1}(k_3^1))$

Здесь $E_{k}(x)$ означает результат шифрования значения x ключом k, а $D_{k}(y)$ — соответственно расшифровка шифротекста y ключом k. Следует выбрать симметричную схему шифрования, обладающую одним дополнительным свойством: при попытке расшифровать с неправильным ключом алгоритм возвращает ошибку.

Смысл этой таблицы таков: если мы знаем зашифрованные значения сигнала k₁ u k₂ на входных проводах гейта w₁ u w₂ соответственно, то мы можем вычислить зашифрованое же значение сигнала вычислив для всех i=1…4 значение $d_i = D_{k_2}(D_{k_1}(c_i))$. В трёх случаях из четырёх должна возникнуть ошибка, а в оставшемся четвёртом мы получим зашифрованное значение k₃ сигнала на выходе гейта.

• Участник p₁ передаёт логический контур и зашифрованные таблицы вычисления для всех контуров участнику p₂.
• Участник p₁ передаёт участнику p₂ зашифрованные значения сигналов входных проводов для тех входов, которые соответствуют входным данным участника p₁.
• Для каждого входного провода w_i соответствующего входным данным p₂, участник p₁ передаёт участнику p₂ с помощью протокола забывчивой передачи число $k_i^{b_i}$, где b_i — значение бита тайных входных данных p₂. При такой передаче p₁ не узнает значения b_i'.
• Теперь у участника p₂ есть зашифрованная логическая схема и зашифрованные значения всех входных проводов. Он вычисляет в зашифрованном виде как было описано выше все гейты схемы один-за-одним, и затем передаёт зашифрованный результат p₁.
• Участник p₁ расшифровывает результат и сообщает его p₂.

Примечания

1. ↑ Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982: 160—164
2. ↑ Yehuda Lindell, Benny Pinkas: A Proof of Yao’s Protocol for Secure Two-Party Computation, Cryptology ePrint Archive, Report 2004/175