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