Семейство псевдоперестановок
Пусть $k$ — полиномиальный параметр. Пусть также при всех $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\}^{k(n)}$. Число $n$ играет роль параметра стойкости, а $d$ — роль описания функции $f_{n,d}$ в семействе таких функций, соответствующих данному значению $n$.
- это семейство полиномиально вычислимо;
- это семейство доступно;
- для любого полиномиального вероятностного алгоритма $\mathcal A$ величина \[ \Pr\left(\mathcal A(1^n,d)=(x,y),\, x,y\in\{0,1\}^{k(n)},\, x\ne y,\, f_{n,d}(x)=f_{n,d}(y)\right), \] где $d\in_{\mathfrak U} D_n$, пренебрежимо мала как функция от $n\in\mathbb N$.
Условие 3 этого определения является формализацией условия трудности нахождения экзистенциальных коллизий функции $f_{n,d}$. Определение семейства псевдоперестановок отличается от определения семейства хэш функций с трудно обнаружимыми коллизиями лишь тем, что функции из семейства псевдоперестановок сохраняют длину аргумента, а функции из семейства хэш функций с трудно обнаружимыми коллизиями уменьшают ее.
Для существования семейств псевдоперестановок не требуется никаких недоказанных предположений. Так, в частности, если $f_{n,d}$ — перестановка множества $\{0,1\}^{k(n)}$ для любых $n\in\mathbb N$ и $d\in D_n$, то семейство $(f_{n,d}\,|\, n\in\mathbb N,\, d\in D_n)$ будет семейством псевдоперестановок при условии его полиномиальной вычислимости и доступности. Понятие семейства псевдоперестановок было введено в работах [1], [2] для формулировки критерия существования семейств хэш функций с трудно обнаружимыми коллизиями.Литература