Теория и практика защиты программ


Конфиденциальное вычисление cc2


Теперь мы непосредственно обращаемся к вычислимой функции, определенной в равенствах (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+ab1,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+ab1

c1+a1·(b1+1)

c1+(a1+1) · b1

c1+(a1+1)· (b1+1)

Вначале отметим, что вышеупомянутая редукция корректна, так как выход процессора 2 равняется c1+(a1+a2)·(b1+b2). Это следует из анализа вышеприведенной таблицы истинности, которая описывает значения выхода процессора 2, как функции от ее собственных входов a1,b1,c1. Необходимо подчеркнуть, что выходная пара (c1,c2) равномерно распределена среди всех пар, для которых c1+c2=(a1+a2) ·(b1+b2).

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




- Начало -  - Назад -  - Вперед -



Книжный магазин