Список обозначений

Функция интерактивная вероятностная

interactive probabilistic function
Предположим, что каждой паре $(x,y)$ строк из $\{0,1\}^*$ поставлено в соответствие распределение вероятностей $\mathfrak F_x(y)$ на множестве $\{0,1\}^*$. Тогда семейство $\mathfrak F=(\mathfrak F_x(y)\,|\, x,y\in\{0,1\}^*)$ называется интерактивной (вероятностной) функцией. В некотором смысле это понятие является обобщением понятия интерактивного вероятностного алгоритма. А именно, если $\mathfrak G=(\mathfrak G_x(y)\,|\, x,y\in\{0,1\}^*)$ — еще одна интерактивная вероятностная функция, то можно организовать обмен сообщениями между $\mathfrak F$ и $\mathfrak G$ на общем входе $x\in\{0,1\}^*$ следующим образом. Первое сообщение от $\mathfrak F$ к $\mathfrak G$ выбирается как $v_1\leftarrow\mathfrak F_x()$, первое сообщение от $\mathfrak G$ к $\mathfrak F$ — как $w_1\leftarrow\mathfrak G_x(v_1)$, второе сообщение от $\mathfrak F$ к $\mathfrak G$ — как $v_2\leftarrow\mathfrak F_x(v_1,w_1)$, второе сообщение от $\mathfrak G$ к $\mathfrak F$ — как $w_2\leftarrow\mathfrak G_x(v_1,w_1,v_2)$ и т. д. Таким образом, $\mathfrak F_x(y)$ — это распределение на пространстве сообщений, посылаемых от $\mathfrak F$, если $x$ — общий вход, а $y$ — последовательность всех предыдущих сообщений, перечисленных в порядке, в котором они были посланы (как от $\mathfrak F$, так и к $\mathfrak F$). См. также [1].

Литература

  • [1] Bellare, M. and Goldreich, O. «On defining proofs of knowledge» 1992

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна