конфиденциальным образом) этой вычислимой функции
Теперь мы непосредственно обращаемся к вычислимой функции, определенной в равенствах (3.1)-(3.2). Все арифметические операции выполняются в поле GF(2). Ниже приводится алгоритм редукции ( конфиденциальным образом) этой вычислимой функции к вычислению OT41.
Редукция к ОТ41
Вход.
Процессор i содержит (ai,bi)Î{0,1}´{0,1}, i=1,2.
1. Первый процессор равномерно выбирает c1ÎR{0,1}.
2. Оба процессора вызывают субпротокол OT41, где первый процессор играет роль отправителя S, а второй процессор играет роль получателя R.
Тогда вход для отправителя – это 4-элементный кортеж (c1+a1·b1,c1+a1·(b1+1),c1+(a1+1)·b1,c1+(a1+1)·(b1+1)), а вход получателя - 1+2a2+b2Î{1,2,3,4}.
Выход.
Первый процессор выдает c1, в то время как второй процессор выдает результат, полученный при вызове OT41.
В столбцах таблицы 3.1 приведены значения выходов процессора 2 как функции от значений его собственных входов и входы и выходы процессора 1 (то есть, a1,b1,c1). Значения, с которыми процессор 2 инициализирует субпротокол ОТ (то есть, 1+2a2+b2) показаны во второй строке и значения выходов (и OT, и всего протокола) показаны в третьей строке. Отметим, что в каждом случае, выход процессора 2 равняется c1+(a1+a2)·(b1+b2).
Таблица 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) |
Таким образом, каждый из локальных выходов (т.e., либо процессора 1, либо процессора 2) равномерно распределен, хотя оба локальных выхода зависимы друг от друга (как в уравнении (3.2). Таким образом, легко увидеть, что редукция конфиденциально вычислима. Формальные аргументы приведены в [Go2].
