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

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

strong(ly) 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},f_{n,d}^{-1}}(1^n)=1\right)-\Pr\left(\mathcal A^{g,g^{-1}}(1^n)=1\right)}\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 алгоритм $\mathcal A$ имеет также доступ к оракулу, возвращающему значение обратной перестановки на заданном алгоритмом аргументе.

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

Теорема 2 см. [1], [2], [3], [4]
Пусть $(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,d_4\in\{0,1\}^n$ определим перестановку $g_{n,(d_1,d_2,d_3,d_4)}\in\operatorname{Per}\left((\{0,1\}^n)^2\right)$ равенством \[ g_{n,(d_1,d_2,d_3,d_4)}(x)=\Phi_{f_{n,d_4}} \left(\Phi_{f_{n,d_3}}\left(\Phi_{f_{n,d_2}} \left(\Phi_{f_{n,d_1}}(x)\right)\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)^4\right.\right) \] является сильно псевдослучайным полиномиально инвертируемым семейством перестановок.
В связи с этой теоремой отметим, что псевдослучайные семейства функций, требуемые в ней, существуют тогда и только тогда, когда существуют односторонние функции (см. семейство функций псевдослучайное и генератор псевдослучайный).

Литература

  • [1] Luby, M. and Rackoff, C. «Pseudo-random permutation generators and cryptographic composition» 1986
  • [2] Luby, M. and Rackoff, C. «How to construct pseudorandom permutations from pseudorandom functions» 1988
  • [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
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна