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

Семейство функций полиномиально инвертируемое

polynomial-time invertible collection of functions

Пусть $I$ — подмножество $\{0,1\}^*$ или $\mathbb N$, а $(f_i\,|\, i\in I)$ — семейство, в котором $f_i\in\operatorname{Fun}(X_i,\{0,1\}^*)$ для любого $i\in I$, где $X_i\subseteq\{0,1\}^*$. Тогда это семейство называется полиномиально инвертируемым, если существует полиномиальный детерминированный алгоритм $\mathcal M$ такой, что $\mathcal M(i,y)$ (если $I\subseteq\{0,1\}^*$) или $\mathcal M(1^i,y)$ (если $I\subseteq\mathbb N$) принадлежит $f_i^{-1}(y)$ для произвольного $y\in f_i(X_i)$.

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