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

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

collection of pseudo-permutations

Пусть $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$.

Определение 1 семейство псевдоперестановок
Семейство $(f_{n,d}\,|\, n\in\mathbb N,\, d\in D_n)$ называется семейством псевдоперестановок, если
  1. это семейство полиномиально вычислимо;
  2. это семейство доступно;
  3. для любого полиномиального вероятностного алгоритма $\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] для формулировки критерия существования семейств хэш функций с трудно обнаружимыми коллизиями.

Литература

  • [1] Russell, A. «Necessary and sufficient conditions for collision-free hashing» 1992
  • [2] Russell, A. «Necessary and sufficient conditions for collision-free hashing» 1995

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