Получестная модель

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

Рассмотрим схему с вычислениями над GF(2) для оценки значенияm-арной вычислимой функцииf. Сначала каждый из процессоров объединяет свои входные биты со всеми другими процессорами так, чтобы сумма всех долей равнялась некоторому входному биту.

Следуя от входных линий к выходным линиям, мы выполняем конфиденциальное вычисление доли на каждой линии схемы так, чтобы сумма долей равнялась бы корректному значению. Перед нами стоит только одна проблема. При вычислениях на мультипликативном вентиле, мы имеем процессор i, имеющий битыa_iиb_iи нам необходимо выполнить конфиденциальное вычисление так, чтобы этот процессор закончил работу со случайным битомc_iи выполнялось бы:.

Более точно, нас интересует конфиденциальное вычисление следующих рандомизированной вычислимой m-арной функции

((a₁,b₁),...,(a_m,b_m))(c₁,...,c_m)_R*{0,1}^m, (3.3)

и

. (3.4)

Таким образом, необходимо конфиденциально вычислить посредством m-стороннего протокола вышеупомянутую вычислимую функцию. Это делается посредством конфиденциального сведения (для независимогоm) вычисления уравнений (3.3)-(3.4) к вычислению тех же самых функциональных зависимостей для случаяm=2, которые, в свою очередь, соответствуют уравнениям (3.1)-(3.2).

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

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

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

=+= =(m-2)^+

Из этого соотношения можно увидеть, что каждый процессор может сам вычислить элемент (m-2)a_ib_i, в то время как каждые два процессора из двухэлементного подмножества {i,j} могут конфиденциально вычислить доли по элементам (a_i+a_j)^(b_i+b_j) (в соответствии с теоремой 3.2). Отсюда следует алгоритм сведения вычисления на основании (3.3) и (3.4)m-арной функции к вычислению на основании (3.1) и (3.2) функции для двух аргументов.

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

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

1. Редукция. Каждая пара процессоров (i,j), гдеi<j, вызывает 2-арную функцию (см. (3.1)-(3.2)). Процессорiобеспечивает входную пару (a_i,b_i), в то время как процессорjобеспечивает - (a_j,b_j). Кроме того, определим ответ оракула процессору iкакc_j^{i,j}.

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

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

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

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

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

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