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

Функция честная

honest function

Функция $f\colon X\to\{0,1\}^*$, где $X\subseteq\{0,1\}^*$, называется честной, если существует полином $p$ такой, что $\lvert{x}\rvert\leqslant p(\lvert{f(x)}\rvert)$ для всех $x\in X$. Говоря неформально, условие честности означает, что функция не очень сильно уменьшает длину своего аргумента. Это условие используется в определении односторонней функции и родственных ей понятий. Значение данного условия состоит в том, что без него полиномиальному алгоритму может не хватить времени даже на выписывание какого либо прообраза входного значения $f(x)$ относительно функции $f$.

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