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

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

pseudorandom function family

Пусть $k$ и $m$ — полиномиальные параметры. Пусть также при всех $n\in\mathbb N$ определено непустое конечное множество $D_n\subseteq\{0,1\}^*$. Предположим, что каждой паре $(n,d)$, где $n\in\mathbb N$ и $d\in D_n$, поставлена в соответствие функция $f_{n,d}\colon\{0,1\}^{k(n)}\to\{0,1\}^{m(n)}$. Число $n$ играет роль параметра стойкости, а $d$ — роль описания функции $f_{n,d}$ в семействе таких функций, соответствующих данному значению $n$.

Определение 1 псевдослучайное семейство функций
Семейство $(f_{n,d}\,|\, n\in\mathbb N,\, d\in D_n)$ называется псевдослучайным семейством функций, если
  1. это семейство полиномиально вычислимо;
  2. это семейство доступно;
  3. для любого полиномиального вероятностного алгоритма $\mathcal A$ величина \[ \left\lvert{\Pr\left(\mathcal A^{f_{n,d}}(1^n)=1\right)-\Pr(\mathcal A^g(1^n)=1)}\right\rvert, \] где $d\in_{\mathfrak U} D_n$ и $g\in_{\mathfrak U}\operatorname{Fun}\left(\{0,1\}^{k(n)},\{0,1\}^{m(n)}\right)$, пренебрежимо мала как функция от $n\in\mathbb N$.

Условие 3 этого определения означает, что никакой полиномиальный вероятностный алгоритм не может отличить $f_{n,d}$ при $d\in_{\mathfrak U} D_n$ от функции, выбранной случайно и равновероятно из множества $\operatorname{Fun}\left(\{0,1\}^{k(n)},\{0,1\}^{m(n)}\right)$. При этом алгоритм получает доступ к функциям посредством оракулов, возвращающих значение функции на заданном алгоритмом аргументе.

Теорема 2 см. [1], [2], [3], [4]
Если существуют псевдослучайные генераторы, то для любых полиномиальных параметров $k$ и $m$ существуют псевдослучайные семейства функций $(f_{n,d}\,|\, n\in\mathbb N,\, d\in\{0,1\}^n)$, в которых $f_{n,d}\in\operatorname{Fun}\left(\{0,1\}^{k(n)},\{0,1\}^{m(n)}\right)$ при всех $n\in\mathbb N$ и $d\in\{0,1\}^n$.

Эта теорема доказывается с помощью следующей конструкции. Пусть $k$ и $m$ — произвольные полиномиальные параметры. Пусть также $g$ — псевдослучайный генератор, отображающий $\{0,1\}^n$ в $\{0,1\}^{2n}$ для всех $n\in\mathbb N$, а $h$ — полиномиально вычислимая функция, отображающая $\{0,1\}^n$ в $\{0,1\}^{m(n)}$ для всех $n\in\mathbb N$ и такая, что семейство случайных величин $(h(\widetilde u_n)\,|\, n\in\mathbb N)$ псевдослучайно (в отличие от определения псевдослучайного генератора здесь не требуется выполнения неравенства $m(n)>n$). Такие функции $g$ и $h$ существуют в предположении существования псевдослучайных генераторов (см. генератор псевдослучайный). Положим $g_0(x)=g(x)_{[1,\dots,n]}$ и $g_1(x)=g(x)_{[n+1,\dots,2n]}$ для произвольных $x\in\{0,1\}^n$ и $n\in\mathbb N$. Тогда семейство $(f_{n,d}\,|\, n\in\mathbb N,\, d\in\{0,1\}^n)$, в котором функция $f_{n,d}$ определена равенством \[ f_{n,d}(x)=h\left(g_{x_{[k(n)]}}\left(\dots g_{x_{[2]}}\left(g_{x_{[1]}}(d)\right)\dots\right)\right) \quad\left(x\in\{0,1\}^{k(n)}\right), \] является искомым псевдослучайным семейством функций.

Предложение 3 см. также [3], [4]
Если полиномиальные параметры $k$ и $m$ удовлетворяют неравенствам $k(n)>\log_2n$ (для любого $n\in\mathbb N\setminus\{0\}$) и $m(n)\geqslant1$ (для любого $n\in\mathbb N$), то из существования псевдослучайных семейств функций $(f_{n,d}\,|\, n\in\mathbb N,\, d\in\{0,1\}^n)$, в которых $f_{n,d}\in\operatorname{Fun}\left(\{0,1\}^{k(n)},\{0,1\}^{m(n)}\right)$ при всех $n\in\mathbb N$ и $d\in\{0,1\}^n$, следует существование псевдослучайных генераторов.
В связи с теоремой 2 и предложением 3 отметим, что псевдослучайные генераторы существуют тогда и только тогда, когда существуют односторонние функции (см. генератор псевдослучайный).

Литература

  • [1] Goldreich, O. and Goldwasser, S. and Micali, S. «How to construct random functions» 1984
  • [2] Goldreich, O. and Goldwasser, S. and Micali, S. «How to construct random functions» 1986
  • [3] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
  • [4] Luby, M. «Pseudorandomness and cryptographic applications» 1996

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