ФЭНДОМ


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

da:Sikker distribueret beregning en:Secure multi-party computation zh:安全多方计算

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на ФЭНДОМЕ

Случайная вики