Конфиденциальное вычисление функции
Общие положения. Для некоторых задач, решаемых в рамках методологии конфиденциальных вычислений, достаточно введения определения конфиденциального вычисления функции [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
f(x1,...,xn)=
=g1((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),(
Введем понятие моделирующего устройства M. Здесь можно проследить некоторые аналогии с моделирующей машиной в интерактивных системах доказательств с нулевым разглашением (см., например, [Ка14,КУ4]).
Пусть рQПрот
- распределение вероятностей над множеством историй (трафика Т и случайных параметров) сбоящих процессоров во время выполнения протокола Р.
Моделирующее устройство, взаимодействующее со сбоящими процессорами, осуществляет свое функционирование в рамках идеального сценария. Моделирующее устройство М создает распределение вероятностей параметров взаимодействия иQПрот
между М и сбоящим процессорами.
Протокол P конфиденциально вычисляет функцию f(x), если выполняются следующие условия:
Условие корректности. Для всех несбоящих процессоров Pi
функция
f(x1,...,xn)=
=g1((w1,...,wn),(
=((y1,...,yn),(
вычисляется с вероятностью ошибки близкой к 0.
Условие конфиденциальности.
Для заданной тройки (x,r,w)Î(XnÄRnÄW) распределения рQПрот
и иQПрот
являются статистически не различимыми.
Функция f, удовлетворяющая условиям предыдущего определения называется конфиденциально вычислимой.
