Конфиденциальное вычисление
Необходимо отметить, что арифметика над GF(2) реализует также, что –1=+1.
Имеют место следующие соотношения:
Из этого соотношения можно увидеть, что каждый процессор может сам вычислить элемент (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-арная функция для получестной модели конфиденциально вычислима.
