Редукция к от41

Вход.Процессорiсодержит (a_i,b_i){0,1}{0,1},i=1,2.

1. Первый процессор равномерно выбираетc₁_R{0,1}.

2. Оба процессора вызывают субпротоколOT⁴₁, где первый процессор играет роль отправителяS, а второй процессор играет роль получателяR.

Тогда вход для отправителя – это 4-элементный кортеж (c₁+a₁^b₁,c₁+a₁^(b₁+1),c₁+(a₁+1)^b₁,c₁+(a₁+1)^(b₁+1)), а вход получателя - 1+2a₂+b₂{1,2,3,4}.

Выход.Первый процессор выдаетc₁, в то время как второй процессор выдает результат, полученный при вызовеOT⁴₁.

В столбцах таблицы 3.1 приведены значения выходов процессора 2 как функции от значений его собственных входов и входы и выходы процессора 1 (то есть, a₁,b₁,c₁). Значения, с которыми процессор 2 инициализирует субпротоколОТ(то есть, 1+2a₂+b₂) показаны во второй строке и значения выходов (иOT, и всего протокола) показаны в третьей строке. Отметим, что в каждом случае, выход процессора 2 равняетсяc₁+(a₁+a₂)^(b₁+b₂).

Таблица 3.1

Значения (a2,b2)	(0,0)	(0,1)	(1,0)	(1,1)
ВыходОТ	1	2	3	4
Значения выхода	c1+a1^b1	c1+a1^(b1+1)	c1+(a1+1)^b1	c1+(a1+1)^ (b1+1)

Вначале отметим, что вышеупомянутая редукция корректна, так как выход процессора 2 равняется c₁+(a₁+a₂)^(b₁+b₂). Это следует из анализа вышеприведенной таблицы истинности, которая описывает значения выхода процессора 2, как функции от ее собственных входовa₁,b₁,c₁. Необходимо подчеркнуть, что выходная пара (c₁,c₂) равномерно распределена среди всех пар, для которыхc₁+c₂=(a₁+a₂) ^(b₁+b₂).

Таким образом, каждый из локальных выходов (т.e., либо процессора 1, либо процессора 2) равномерно распределен, хотя оба локальных выхода зависимы друг от друга (как в уравнении (3.2). Таким образом, легко увидеть, что редукция конфиденциально вычислима. Формальные аргументы приведены в [Go2].

Протокол вычислений на арифметической схеме над gf(2)

Теперь мы покажем, что процесс вычисления любой детерминированной вычислимой функции, которая вычисляется посредством арифметической схемы над GF(2), конфиденциально сводим к вычислению функции в соответствии с уравнениями (3.1) - (3.2). Напомним, что последняя вычислимая функция соответствует частному вычислению на мультипликативных вентилях для входов, общедоступных обоим процессорам. Таким образом, можно констатировать, что эта вычислимая функция может рассматриваться как эмулирование мультипликативного вентиля, как это описано выше. В частности разделение битового значенияvмежду обоими процессорами означает равномерно выбранную пару битов (v₁,v₂) так, чтоv=v₁+v₂, где первый процессор содержитv₁, второй -v₂. Наша цель заключается в разделении, через частные вычисления, долей входных линий схемы на доли всех линий схемы так, чтобы, в конце концов, мы получили бы доли выходных линий схемы.

В начале мы рассмотрим нумерацию всех линий схемы. Входные линии схемы (n) для каждого процессора будут пронумерованы 1,2,...,2nтак, что дляj=1,...,nj-тый вход процессора iсоответствует ((i-1)n+j)-той линии. Линии будут пронумерованы так, чтобы выходные линии каждого вентиля имеют большую нумерацию, чем его входные линии. Для простоты предположим, что каждый процессор получаетnвыходных битов, и что выходные биты второго процессора соответствуют последнимnлиниям схемы.

Ниже приводится алгоритм сведения любой детерминированной вычислимой функции к вычислениям на мультипликативном вентиле.