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

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

pseudorandom permutation family

Пусть $k$ — полиномиальный параметр. Пусть также при всех $n\in\mathbb N$ определено непустое конечное множество $D_n\subseteq\{0,1\}^*$. Предположим, что каждой паре $(n,d)$, где $n\in\mathbb N$ и $d\in D_n$, поставлена в соответствие перестановка $f_{n,d}$ множества $\{0,1\}^{k(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{Per}\left(\{0,1\}^{k(n)}\right)$, пренебрежимо мала как функция от $n\in\mathbb N$.

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

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

Часто на псевдослучайные семейства перестановок накладывают дополнительное условие полиномиальной инвертируемости. Псевдослучайное семейство перестановок, которое строится в следующей теореме, удовлетворяет этому дополнительному условию.

Теорема 3 см. [3], [4], [1], [2]
Пусть $(f_{n,d}\,|\, n\in\mathbb N,\, d\in\{0,1\}^n)$ — псевдослучайное семейство функций, в котором $f_{n,d}\in\operatorname{Fun}\left(\{0,1\}^n,\{0,1\}^n\right)$ для всех $n\in\mathbb N$ и $d\in\{0,1\}^n$. Для произвольных $n\in\mathbb N$ и $d_1,d_2,d_3\in\{0,1\}^n$ определим перестановку $g_{n,(d_1,d_2,d_3)}\in\operatorname{Per}\left((\{0,1\}^n)^2\right)$ равенством \[ g_{n,(d_1,d_2,d_3)}(x)=\Phi_{f_{n,d_3}}\left(\Phi_{f_{n,d_2}} \left(\Phi_{f_{n,d_1}}(x)\right)\right)\quad \left(x\in(\{0,1\}^n)^2\right), \] где $\Phi_f$ — образ функции $f$ при преобразовании Файстеля. Тогда \[ \left(g_{n,\overline d}\,\left|\,n\in\mathbb N,\,\overline d\in(\{0,1\}^n)^3\right.\right) \] является псевдослучайным полиномиально инвертируемым семейством перестановок.
В связи с этой теоремой отметим, что псевдослучайные семейства функций, требуемые в ней, существуют тогда и только тогда, когда существуют односторонние функции (см. семейство функций псевдослучайное и генератор псевдослучайный).

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
  • [2] Luby, M. «Pseudorandomness and cryptographic applications» 1996
  • [3] Luby, M. and Rackoff, C. «Pseudo-random permutation generators and cryptographic composition» 1986
  • [4] Luby, M. and Rackoff, C. «How to construct pseudorandom permutations from pseudorandom functions» 1988

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