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

       

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


Необходимо отметить, что арифметика над GF(2) реализует также, что –1=+1.

Имеют место следующие соотношения:

=
+
=                                      =(m-2)·
+
               

Из этого соотношения можно увидеть, что каждый процессор может сам вычислить элемент (m-2)aibi, в то время как каждые два процессора из двухэлементного подмножества {i,j} могут конфиденциально вычислить доли по элементам (ai+aj)·(bi+bj) (в соответствии с теоремой 3.2). Отсюда следует алгоритм сведения вычисления на основании (3.3) и (3.4) m-арной функции к вычислению на основании (3.1) и (3.2) функции для двух аргументов.

Редукция к КВm=2

Вход.

Процессор i

содержит (ai,bi)Î{0,1}´{0,1}, i=1,...,m.

1. Редукция. Каждая пара процессоров (i,j), где i<j, вызывает

2-арную функцию (см. (3.1)-(3.2)). Процессор i обеспечивает входную пару (ai,bi), в то время как процессор j обеспечивает - (aj,bj). Кроме того, определим ответ оракула процессору i

как cj{i,j}.

2. Процессор i устанавливает ci=(m-2)aibi+

.

3. Процессор i выдает ci.

Вышеприведенное сведение является корректным, так как выходы всех процессоров складываются в соответствии с алгоритмом. Конфиденциальность сведения определяется следующим предложением.

Предложение 3.1.

Алгоритм «Редукция к КВm=2» конфиденциально сводит вычисления на основании (3.3) и (3.4) m-арной функции к вычислению на основании (3.1) и (3.2) функции для двух аргументов.

В работе [Go2] приводятся формальные аргументы для доказательства корректности и конфиденциальности такой редукции. А следующая теорема, устанавливает главный результат для конфиденциального вычисления любой вычислимой функции для случая многостороннего протокола взаимодействия.

Теорема 3.4.

Предположим, что односторонние перестановки с секретом существуют. Тогда любая вычислимая m-арная функция для получестной модели конфиденциально вычислима.



Содержание раздела