Протокол вычислений на арифметической схеме над GF(
Теперь мы покажем, что процесс вычисления любой детерминированной вычислимой функции, которая вычисляется посредством арифметической схемы над GF(2), конфиденциально сводим к вычислению функции в соответствии с уравнениями(3.1) - (3.2). Напомним, что последняя вычислимая функция соответствует частному вычислению на мультипликативных вентилях для входов, общедоступных обоим процессорам. Таким образом, можно констатировать, что эта вычислимая функция может рассматриваться как эмулирование мультипликативного вентиля, как это описано выше. В частности разделение битового значения v
между обоими процессорами означает равномерно выбранную пару битов (v1,v2) так, что v=v1+v2, где первый процессор содержит v1, второй - v2. Наша цель заключается в разделении, через частные вычисления, долей входных линий схемы на доли всех линий схемы так, чтобы, в конце концов, мы получили бы доли выходных линий схемы.
В начале мы рассмотрим нумерацию всех линий схемы. Входные линии схемы (n) для каждого процессора будут пронумерованы 1,2,...,2n так, что для j=1,...,n j-тый вход процессора i соответствует ((i-1)n+j)-той линии. Линии будут пронумерованы так, чтобы выходные линии каждого вентиля имеют большую нумерацию, чем его входные линии. Для простоты предположим, что каждый процессор получает n выходных битов, и что выходные биты второго процессора соответствуют последним n
линиям схемы.
Ниже приводится алгоритм сведения любой детерминированной вычислимой функции к вычислениям на мультипликативном вентиле.
Редукция к МВ
Вход.
Процессор i
содержит строку битов xi1...xinÎ{0,1}n, i=1,2.
1. Разделение входов. Каждый процессор делит каждый из своих входных битов с другим процессором. То есть для каждого i=1,2 и j=1,...,n
процессор i равномерно выбирает бит rij и посылает его другому процессору, как долю входной линии (с нумерацией ((i-1)n+j) последнего. Процессор i устанавливает свою собственную долю на входной линии с нумерацией (i-1)n+j в значение xij+rij.
2. Эмуляция схемы. Следуя нумерации линий, процессоры используют свои доли двух входных линий схемы, чтобы конфиденциально вычислить доли для выходной линии вентиля.
Предположим, что процессоры имеют общие две входные линии вентиля, то есть процессор 1 содержит доли a1,b1, а процессор 2 содержит доли a2,b2, где a1,a2 - доли на первой линии и b1,b2 - доли на второй линии. Рассмотрим два случая.
2.1. Эмуляция аддитивного вентиля. Процессор 1 только устанавливают долю выходной линии вентиля в значение a1+b1, а процессор 2 устанавливают долю выходной линии вентиля в значение a2+b2.
2.2. Эмуляция мультипликативного вентиля. Доли выходной линии вентиля получаются посредством вызова оракула для вычисления функции (см.(3.1)-(3.2)), где процессор 1 обеспечивает вход (часть запроса) (a1,b1), а процессор 2 обеспечивает вход (a2,b2). После ответов оракула, каждый из процессоров устанавливают свою долю выходной линии вентиля в значение равное своей части ответа оракула.
3. Восстановление выходных битов. Как только доли выходных линий схемы вычислены, каждый процессор посылает долю с каждой из таких линий процессору, с которым линия связана. То есть доли на последних n
линиях посылаются процессором 1 процессору 2, в то время как доли n предшествующих линий посылаются процессором 2 процессору 1. Каждый из процессоров восстанавливает соответствующие выходные биты, складывая две доли; то есть доли, которую он получил на шаге 2 и доли, полученной на текущем шаге.
Выход.
Каждый процессор локально выдает биты, восстановленные на шаге 3.
Сначала необходимо проверить, что выходы действительно корректны. Это можно сделать методом индукции, которая состоит в том, что значение доли каждой линии прибавляется к корректному значению на линии. Базис индукции – номер входной линии схемы. А, именно,
((i-1)n+j)-тая линия имеет значение xij
и ее доли - rij и rij+xij.
На каждом шаге индукции рассматривается эмуляция аддитивного или мультипликативного вентиля. Предположим, что значения входных линий – a и b и что их доли a1,a2 и b1,b2, которые удовлетворяют a1+a2=a и b1+b2=b. В случае аддитивного вентиля доли на выходной линии устанавливаются в значения a1+b1 и a2+b2, что удовлетворяет (a1+b1)+(a2+b2)=(a1+a2)+(b1+b2)=a+b. В случае мультипликативного вентиля доли выходной линии были устанавливаются в значения c1
и c2 так, что c1+c2=(a1+a2)·(b1+b2). Таким образом, c1+c2=a·b, что и требовалось показать.
В работе [Go2] приводятся формальные аргументы для конфиденциального сведения вычисления на арифметической схеме над GF(2) к функции, вычислимой в соответствии с уравнениями (3.1)-(3.2). А следующая теорема, устанавливает главный результат для конфиденциального вычисления любой вычислимой функции для случая двухстороннего протокола взаимодействия.
Теорема 3.2.
Предположим, что односторонние перестановки с секретом существуют. Тогда любая вычислимая функция для получестной модели конфиденциально вычислима.
