Список обозначений
Семейство перестановок псевдослучайное
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)$ называется
псевдослучайным семейством перестановок, если
- это семейство полиномиально вычислимо;
- это семейство доступно;
- для любого полиномиального вероятностного алгоритма $\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