- Протокол конфиденциального вычисления
-
В криптографии протокол конфиденциального вычисления (также безопасное/защищенное/тайное многостороннее вычисление, англ. 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 Зашифрованая таблица вычисления Здесь означает результат шифрования значения x ключом k, а — соответственно расшифровка шифротекста y ключом k. Следует выбрать симметричную схему шифрования, обладающую одним дополнительным свойством: при попытке расшифровать с неправильным ключом алгоритм возвращает ошибку.
Смысл этой таблицы таков: если мы знаем зашифрованные значения сигнала k1 u k2 на входных проводах гейта w1 u w2 соответственно, то мы можем вычислить зашифрованое же значение сигнала вычислив для всех i=1…4 значение . В трёх случаях из четырёх должна возникнуть ошибка, а в оставшемся четвёртом мы получим зашифрованное значение k3 сигнала на выходе гейта.
- Участник p1 передаёт логический контур и зашифрованные таблицы вычисления для всех контуров участнику p2.
- Участник p1 передаёт участнику p2 зашифрованные значения сигналов входных проводов для тех входов, которые соответствуют входным данным участника p1.
- Для каждого входного провода wi соответствующего входным данным p2, участник p1 передаёт участнику p2 с помощью протокола забывчивой передачи число , где bi — значение бита тайных входных данных p2. При такой передаче p1 не узнает значения bi'.
- Теперь у участника p2 есть зашифрованная логическая схема и зашифрованные значения всех входных проводов. Он вычисляет в зашифрованном виде как было описано выше все гейты схемы один-за-одним, и затем передаёт зашифрованный результат p1.
- Участник p1 расшифровывает результат и сообщает его p2.
Примечания
Категория:- Криптография
Wikimedia Foundation. 2010.