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

Общие положения. Для некоторых задач, решаемых в рамках методологии конфиденциальных вычислений, достаточно введения определения конфиденциального вычисления функции [MR].

Пусть в сети N, состоящей из n процессоров P1,P2,...,Pn со своими секретными входами x1,x2,...,xn, необходимо корректно (даже при наличии t

сбоящих процессоров) вычислить значение функции (y1,y2,...,yn)=f(x1,x2,...,xn) без разглашения информации о секретных аргументах функции, кроме той, информации, которая может содержаться в вычисленном значении функции.

По аналогии с идеальным и реальным сценариями, приведенными выше, можно ввести понятия «реальное и идеальное вычисление функции f» [MR].

Пусть множество входов и выходов обозначается как X и Y соответственно, размерности этих множеств ½X½=c и ½Y½=m. Множество случайных параметров, используемых всеми процессорами сети, обозначается через R, размерность - ½R½=n. Кроме того, через W

обозначим рабочее пространство параметров сети. Через T(r) обозначается трафик в r-раунде, через ti(r) – трафик для процессора i в r-том раунде, r0 и rk – инициализирующий и последний раунды протокола P соответственно и r* - заданный неким произвольным образом раунд выполнения протокола P.

Пусть функцию f

можно представить как композицию d

функций (суперпозицию функций) g1

...ghgh+1...gd:

f(x1,...,xn)=

=g1((w1,...,wn),(

,...,))...gh((w1,...,wn),(,...,))...

gd((w1,...,wn),(,...,)).

Аргументы функции gh

являются рабочими параметрами w1,...,wn участников протокола с трафиком (t1,...,tn) в r раунде. Значения данной функции gh

являются аргументами (рабочими параметрами протокола с трафиком (t1,...,tn) в r+1 раунде) для функции gh+1.

Из определения следует, что функция f:(XnÄRnÄW)®Y, где Ä

- декартово произведение множеств, реализует:

f(x1,...,xn)=gd((w1,...,wn),(

,...,))=((y1,...,yn),(,...,)).

Введем понятие моделирующего устройства M. Здесь можно проследить некоторые аналогии с моделирующей машиной в интерактивных системах доказательств с нулевым разглашением (см., например, [Ка14,КУ4]).

Пусть рQПрот

- распределение вероятностей над множеством историй (трафика Т и случайных параметров) сбоящих процессоров во время выполнения протокола Р.

Моделирующее устройство, взаимодействующее со сбоящими процессорами, осуществляет свое функционирование в рамках идеального сценария. Моделирующее устройство М создает распределение вероятностей параметров взаимодействия иQПрот

между М и сбоящим процессорами.

Протокол P конфиденциально вычисляет функцию f(x), если выполняются следующие условия:

Условие корректности. Для всех несбоящих процессоров Pi

функция

f(x1,...,xn)=

=g1((w1,...,wn),(,...,))...gh((w1,...,wn),(,...,))

gh+1((w1,...,wn),(,...,))...gd((w1,...,wn), (,...,))=

=((y1,...,yn),(,...,))

вычисляется с вероятностью ошибки близкой к 0.

Условие конфиденциальности.

Для заданной тройки (x,r,w)Î(XnÄRnÄW) распределения рQПрот

и иQПрот

являются статистически не различимыми.

Функция f, удовлетворяющая условиям предыдущего определения называется конфиденциально вычислимой.


Содержание раздела

---

---