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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Формализованная постановка задачи[править | править вики-текст]

В конфиденциальном вычислении участвуют N участников p1, p2, …, pN, у каждого участника есть тайные входные данные d1, d2, …, dN соответственно. Участники хотят найти значение F(d1, d2, …, dN), где F — известная всем участникам вычислимая функция от N аргументов. Допускается, что среди участников будут получестные нарушители, то есть те, которые верно следуют протоколу, но пытаются получить дополнительную информацию из любых промежуточных данных.

Описание протокола[править | править вики-текст]

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

  • Представим функцию F в виде логического контура. На вход логического контура подаются биты всех аргументов функции F, сам контур состоит из логических гейтов AND, OR и NOT, и на выходе выдаёт результат функции F в двоичном формате.
  • Участник p1 генерирует для каждого провода логической схемы два различных случайных числа k0 u k1: они представляют ноль и единицу в этом проводе соответственно.
  • Участник p1 создаёт для каждого контура зашифрованную таблицу вычисления. Для бинарного гейта 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. Следует выбрать симметричную схему шифрования, обладающую одним дополнительным свойством: при попытке расшифровать с неправильным ключом алгоритм возвращает ошибку.

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

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

Примечания[править | править вики-текст]

  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