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


Безопасные протоколы для получестной модели


В этом подразделе описывается метод построения протоколов конфиденциального вычисления любой заданной вычислимой функции. Конструкция представляет собой булеву схему для реализации заданной функции, вычисления в которой выполняются в соответствии с протоколом. Конструкция носит модульный характер.

Сначала определяется соответствующее понятие редукции

и показывается, как получить протокол для конфиденциального вычисления функции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). Ниже показывается, как это может быть сделано при условии существования односторонней перестановки с секретом (см. Приложение).




- Начало -  - Назад -  - Вперед -