Многосторонний протокол схемного вычисления
Ниже описывается m-арный аналог вышеописанного субпротокола «Редукция КВm=2». Показывается, что вычисления любой детерминированной функции, вычислимой посредством арифметической схемы над GF(2), конфиденциально сводимы к вычислениям функции из уравнений (3.3) - (3.4).
В частности разделение битового значения v
между m
процессорами означает равномерно выбранную m-арную последовательность битов (v1,...,vm) так, что v=
В начале мы рассмотрим нумерацию всех линий схемы. Входные линии схемы (n) для каждого процессора будут пронумерованы 1,2,...,mn так, что для j=1,...,n j-тый вход процессора i соответствует ((i-1)n+j)-той линии. Линии будут пронумерованы так, чтобы выходные линии каждого вентиля имеют большую нумерацию, чем его входные линии. Для простоты предположим, что каждый процессор получает n выходных битов, и что j-тый выходной бит j-того процессора соответствуют линии
N-(m+1-i)+j, где N
– размер схемы.
Ниже приводится алгоритм сведения любой детерминированной
m-арной вычислимой функции (m³2) к функции, вычислимой в соответствии с уравнениями (3.3) и (3.4).
Редукция к КВm
Вход.
Процессор i
содержит строку битов xi1...ximÎ{0,1}m, i=1,...,m.
1. Разделение входов. Каждый процессор делит каждый из своих входных битов с другим процессором. То есть для каждого i=1,...,m и j=1,...,n и каждого k¹i процессор i равномерно выбирает бит rk(i-1)n+j и посылает его процессору k, как долю входной линии (с нумерацией (i-1)n+j) последнего. Процессор i устанавливает свою собственную долю на входной линии с нумерацией (i-1)n+j
в значение xij+
2. Эмуляция схемы. Следуя нумерации линий, процессоры используют свои доли двух входных линий схемы, чтобы конфиденциально вычислить доли для выходной линии вентиля.
Предположим, что процессоры имеют общие две входные линии вентиля, то есть для i=1,...,m процессор i содержит доли ai,bi, где a1,...,am - доли на первой линии и b1,...,bm - доли на второй линии. Рассмотрим два случая.
2.1. Эмуляция аддитивного вентиля. Каждый процессор только устанавливают свою долю выходной линии вентиля в значение ai+bi.
2.2. Эмуляция мультипликативного вентиля. Доли выходной линии вентиля получаются посредством вызова оракула для вычисления функции (см.(3.4)-(3.5), где процессор i
обеспечивает вход (часть запроса) (ai,bi). После ответов оракула, каждый из процессоров устанавливают свою долю выходной линии вентиля в значение равное своей части ответа оракула.
3. Восстановление выходных битов. Как только доли выходных линий схемы вычислены, каждый процессор посылает долю с каждой из таких линий процессору, с которым линия связана. То есть для i=1,...,m и j=1,...,n
каждый процессор посылает свою долю с линии N-(m+1-i)n+j процессору i. Каждый из процессоров восстанавливает соответствующие выходные биты, складывая соответствующие m долей; то есть доли, которую он получил на шаге 2 и m-1 долей, полученных на текущем шаге.
Выход.
Каждый процессор локально выдает биты, восстановленные на шаге 3.
Сначала необходимо проверить, что выходы действительно корректны. Это можно сделать методом индукции, которая состоит в том, что значение доли каждой линии прибавляются к корректному значению на линии. Базис индукции – номер входной линии схемы. А именно,
((i-1)n+j)-тая линия имеет значение xij
и ее доли прибавляются xij. На каждом шаге индукции рассматривается эмуляция аддитивного или мультипликативного вентиля. Предположим, что значения входных линий – a и b
и что их доли a1,...,am и b1,...,bm действительно удовлетворяют
и
В случае мультипликативного вентиля доли выходной линии были установлены в значение c1,...,cm так, что
В работе [Go2] приводятся формальные аргументы для конфиденциального сведения вычисления на арифметической схеме над GF(2) к
m-арной функции, вычислимой в соответствии с уравнениями (3.3)-(3.4). А следующая теорема, устанавливает главный результат для конфиденциального вычисления любой вычислимой функции для многостороннего протокола взаимодействия.
Теорема 3.5.
Предположим, что односторонние перестановки с секретом существуют. Тогда любая вычислимая m-арная функция для получестной модели и m-стороннего протокола взаимодействия конфиденциально вычислима.
