Безопасные протоколы для получестной модели
В этом подразделе описывается метод построения протоколов конфиденциального вычисления любой заданной вычислимой функции. Конструкция представляет собой булеву схему для реализации заданной функции, вычисления в которой выполняются в соответствии с протоколом. Конструкция носит модульный характер.
Сначала определяется соответствующее понятие редукции
и показывается, как получить протокол для конфиденциального вычисления функцииg по данной редукции (конфиденциально вычислимой) функции g к (конфиденциально вычислимой) функции f
вместе с протоколом для конфиденциального вычисления f. В частности мы сводим конфиденциальное вычисление обобщенных вычислимых функций к конфиденциальному вычислению детерминированных вычислимых функций.
Затем, без потери общности, рассматриваются булевы схемы с логическими вентилями and и xor с коэффициентом объединения по входу равным 2. В общем случае можно представить следующий сценарий. Первый процессор «содержит» параметры a1,b1, а второй процессор - a2,b2, где a1+a2 - значение одной входной линии и b1+b2 - значение другой входной линии. Необходимо обеспечить каждый из процессоров «случайной» долей значения выходной линии, то есть долей значения (a1+a2)·(b1+b2). Другими словами нас интересует конфиденциальное вычисление следующей рандомизированной вычислимой функции:
((a1,b1),(a2,b2))®(c1,c2), (3.1)
где c1+c2=(a1+a2) ·(b1+b2). (3.2)
То есть значения (с1,с2) равномерно выбраны среди всех решений c1+c2=(a1+a2)·(b1+b2). Вышеупомянутая вычислимая функция имеет конечную область значений и может быть вычислена (в общем случае) сведением к одному из вариантов забывающего обмена (OT). Ниже показывается, как это может быть сделано при условии существования односторонней перестановки с секретом (см. Приложение).
