Защищенное многостороннее вычисление

В криптографии протокол конфиденциального вычисления (так же безопасное/защищенное/тайное многостороннее вычисление, англ. 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 u 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