Вычисления на мультипликативном вентиле
Пусть c=a·b – мультипликативный вентиль и пусть A(·), B(·) – полиномы, ассоциированные с входными линиями, а именно доли каждого процессора Pi
этих линий - A(i) и B(i) соответственно. Процессоры совместно вычисляют свои доли случайного полинома C(·) степени t, удовлетворяющий C(0)=A(0)·B(0), а именно доля каждого несбоящего процессора Pi на выходной линии будет C(i).
Сначала каждый процессор локально вычисляет свою долю полинома E(·)=A(·)·B(·), устанавливая E(i)=A(i)·B(i). Ясно, что E(·) имеет требуемый свободный коэффициент. Однако, полином E(·) имеет степень 2t и, кроме того, полином не является равномерно распределенным. Процессоры используют свои доли полинома E(·), чтобы вычислить свои доли требуемого полинома C(·) безопасным способом. Вычисления осуществляются в два этапа: на первом этапе процессоры совместно генерируют случайный полином D(·) степени 2t такой, чтобы D(0)=E(0). А именно, каждый процессор Pi будет иметь D(i). Затем, стороны используют их доли D(·), чтобы совместно вычислить свои доли полиномаC(·). Эти шаги описаны ниже.
Рандомизация. Сначала покажем, как генерируется полином D(·). Сначала процессоры генерируют случайный полином H(·) степени 2t и с H(0)=0; а именно, каждая сторона Pi будет иметь H(i). Мы сначала описываем, как полином H(·) делится в синхронной модели вычислений [BGW].
Каждый процессор Pi выбирает случайный полином Hi(·) степени 2t с Hi(0)=0 и делит его среди процессоров; а именно, каждый процессор Pj
получает Hi(j). Полином H(·) – устанавливается в H(·)=
В асинхронной модели вычислений процессор не может ждать, пока получит свою долю от всех других процессоров. Вместо этого, стороны соглашаются, используя субпротокол СОАМ, о множестве C процессоров, которые успешно разделили полиномы Hi. Затем полином H(·) будет установлен в H(·)=
Полином D(·)теперь определен как D(·)=E(·)+H(·); а именно каждый процессор Pi вычисляет D(i)=E(i)+H(i). Ясно, что D(0)=A(0)·B(0) и все другие коэффициенты D(·) равномерно и независимо распределены над F.
Редукция степени. На этом этапе процессоры используют свои доли полинома D(·), чтобы совместно и безопасно вычислить свои доли случайного полинома C(·) степени t с C(0)=D(0). Полином C(·) будет устанавливать «усечение» полинома D(·) к степени t; а именно t+1 коэффициентов C(·) являются коэффициентами t+1 более низкой степени полинома D(·). Важный момент здесь состоит в том, что информация, которую накапливают сбоящие процессоры (а именно t долей полинома D(·) вместе с t долями усеченного полинома C(·)), независима от C(0).
Пусть
размерностью n´n такая, что
В синхронной модели вычислений умножение входов на фиксированную матрицу может быть выполнено посредством безопасного вычисления соответствующих n фиксированных линейных комбинаций входов таких, что значение i-той линейной комбинации вскрываемо только процессором Pi. Линейные комбинации безопасно вычисляются следующим образом. Сначала каждый процессор разделяет свой вход; затем каждый процессор вычисляет линейную комбинацию своих долей и открывает эту линейную комбинацию специальному процессору; в заключение специальный процессор вычисляет значение выхода, интерполируя полином степени t из полученных комбинаций [Ca2].
Линейные комбинации всех входов не могут быть вычислены в асинхронной модели вычислений и, следовательно, синхронный метод, описанный выше, не может использоваться.
Ниже приводится решение для асинхронной модели вычислений. Сначала мы описываем метод для умножения входов на фиксированную матрицу в асинхронной модели для случая, когда матрица и множество входов связаны специальным образом. Кроме того, мы отметим также, что матрица М
и множество возможных входов (на этапе редукции степени) тоже связаны специальным образом.
Определение 3.7.
Пусть A – матрица размерностью n´n и пусть SÍFn - множество входных векторов. Будем говорить, что S – t-умножаемо на A, если для каждого множества GÍ[n] с |G|³n-t существует (легко вычислимая) матрица AG размером |G|´n такая, что для каждого входа
Пусть S – t-умножаемо на A. Тогда протокол, описанный ниже, «умножает входы из множества S
на матрицу». Пусть
вычислено, каждый процессор локально вычисляет AG. Затем, процессоры запускают n протоколов восстановления секрета АВс, где в i-том протоколе АВс процессоры позволяют процессору Pi вычислить
Протокол МАТ (xi,A)
Процессор Pi на входе xi и матрице A работает следующим образом.
1. Устанавливает (t,xi)АГПРС=(G,{si,j½G}).
2. Нумерует G=g1,...,g|G| и пусть в этом случае
3. Вычисляет AG.
4. Для 1£k£n
устанавливает ([
Подает на выход yi.
Далее будем говорить, что входной вектор
Для дальнейших рассуждений нам необходима матрица особого вида. Эта матрица, назовем ее M, описана в работе [BGW] и строится как
М=V-1TV, где V – матрица Вандермонда размерностью n´n (см, например, [Кн, стр.474]), определенная как Vi,j=ij, а T построена установкой всех элементов, кроме элементов первых t+1 столбцов, единичной матрицы в нули. (Пусть
– это вектор коэффициентов полинома D(·) и, таким образом,
Пусть GÍ[n] с |G|³n-t и пусть
G=g1,...,g|G|. Матрица MG строится следующим образом. Пусть матрица VG
размерностью |G|´|G| - это матрица V, спроектированная на индексы из матрицы G; а именно
Так как n³3t+1 мы имеем |G|³2t+1. Можно проверить, что в этом случае
Объединяя шаги рандомизации и редукции степени, мы получаем протокол для вычислений на мультипликативном вентиле. Этот протокол, обозначенный MUL, представлен ниже.
Субпротокол MUL(ai,bi)
Код для процессора Pi по входу ai,bi.
1. Установить (t)АГПРС=(C¢,{hi,j½jÎC¢}).
2. Пусть di=ai·bi+
3. Пусть Mn´n – матрица, определенная выше как M.
4. Установить (di,M)MAT=ci.
Подать на выход ci.
