Интернет магазин китайских планшетных компьютеров

Компьютеры - Протокол конфиденциального вычисления - Формализованная постановка задачи

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

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

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

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

Входной провод w1	Входной провод w2	Выходной провод w3	Зашифрованая таблица вычисления

Здесь E_k означает результат шифрования значения x ключом k, а D_k — соответственно расшифровка шифротекста y ключом k. Следует выбрать симметричную схему шифрования, обладающую одним дополнительным свойством: при попытке расшифровать с неправильным ключом алгоритм возвращает ошибку. Смысл этой таблицы таков: если мы знаем зашифрованые значения сигнала k₁ u k₂ на входных проводах гейта w₁ u w₂ соответственно, то мы можем вычислить зашифрованое же значение сигнала вычислив для всех i=1…4 значение . В трех случаях из четырех должна возникнуть ошибка, а в оставшемся четвертом мы получим зашифрованое значение k₃ сигнала на выходе гейта.

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