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

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

weak(ly) one-way collection of functions
Определение слабо одностороннего семейства функций получается из определения одностороннего семейства функций (см. определение 1 из статьи Семейство функций одностороннее) заменой условия 2 на следующее условие: существует полином $p$ такой, что для любого полиномиального вероятностного алгоритма $\mathcal A$ неравенство \[ \Pr\left(\mathcal A(1^n,i,f_i(x))\in f_i^{-1}(f_i(x))\right)\leqslant1-\frac1{p(n)}, \] где $i\leftarrow\mathfrak I_n$ и $x\leftarrow\mathfrak X_i$, выполняется для всех достаточно больших $n\in\mathbb N$. См. также [1]. Между слабо односторонними семействами функций и слабо односторонними функциями существует такая же связь, как и описанная в статье Семейство функций одностороннее связь между односторонними семействами функций и односторонними функциями.

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)

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