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

Функция трудная

hard-core function
Определение 1 трудная функция; см. также [1]
Пусть $f$ — функция из $\{0,1\}^*$ в $\{0,1\}^*$. Пусть также $h\colon\{0,1\}^*\to\{0,1\}^*$ — полиномиально вычислимая функция, отображающая $\{0,1\}^n$ в $\{0,1\}^{m(n)}$ при любом $n\in\mathbb N$. Тогда функция $h$ называется трудной для функции $f$, если для независимых случайных величин $\widetilde u_n$ и $\widetilde r_{m(n)}$ ($n\in\mathbb N$), распределенных равномерно на $\{0,1\}^n$ и $\{0,1\}^{m(n)}$ соответственно, семейства случайных величин \[ ((f(\widetilde u_n),h(\widetilde u_n))\,|\, n\in\mathbb N)\quad\text{и}\quad \left(\left.\left(f(\widetilde u_n),\widetilde r_{m(n)}\right)\,\right|\, n\in\mathbb N\right) \] вычислительно неотличимы.

Если $m(n)=1$ для всех $n\in\mathbb N$, то трудная функция для $f$ называется трудным предикатом для $f$.

Понятие трудной функции для $f$ представляет собой формализацию понятия функции, значение которой на элементе $x$ вычисляется легко по $x$, но трудно по $f(x)$. Другой такой формализацией является понятие полиномиально вычислимой трудно аппроксимируемой функции по $f$. Всякая трудная функция для $f$ является полиномиально вычислимой и трудно аппроксимируемой по $f$, а при $m(n)=O(\log n)$ верно и обратное (см. функция трудно аппроксимируемая).

Следующая теорема известна как теорема Гольдрайха”– Левина [2] (см. также [1], [3]).

Теорема 2
Пусть $f$ — произвольная односторонняя функция. Пусть также $m$ — полиномиальный параметр такой, что $m(n)=O(\log n)$ для $n\in\mathbb N\setminus\{0\}$. Определим функцию $h$ (отображающую $\{0,1\}^n\times\{0,1\}^{m(n)+n-1}$ в $\{0,1\}^{m(n)}$ при любом $n\in\mathbb N$) равенствами \[ h(x,y)_{[i]}=\bigoplus_{j=1}^nx_{[j]}y_{[i+j-1]}\quad \left(x\in\{0,1\}^n,\, y\in\{0,1\}^{m(n)+n-1},\, n\in\mathbb N\right) \] для $i\in\{1,\dots,m(n)\}$. Тогда $h$ является трудной для функции $(x,y)\mapsto(f(x),y)$ ($x\in\{0,1\}^n$, $y\in\{0,1\}^{m(n)+n-1}$, $n\in\mathbb N$).

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
  • [2] Goldreich, O. and Levin, L. A. «A hard-core predicate for all one-way functions» 1989
  • [3] Luby, M. «Pseudorandomness and cryptographic applications» 1996

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