Семейство хэш-функций с трудно обнаружимыми коллизиями
Говоря неформально, в криптографии хэш функцией называется полиномиально вычислимая и уменьшающая длину входного значения функция, для которой задача нахождения коллизий вычислительно трудна. Одной из формализаций этого понятия является понятие семейства хэш функций с трудно обнаружимыми коллизиями, введенное Дамгордом в [1]. Поэтому семейства хэш функций с трудно обнаружимыми коллизиями уместно называть семействами хэш функций Дамгорда. Следует отметить, что англоязычный термин «collision free hash function family» неточно отражает сущность этого понятия. А именно, коллизии заведомо существуют, но их трудно находить.
Понятие семейства хэш функций с трудно обнаружимыми коллизиями моделирует ситуацию, когда противник сначала получает случайное описание хэш функции $h$, а затем пытается найти пару $(x,y)$ различных значений аргумента $h$ такую, что $h(x)=h(y)$. В определении семейства хэш функций с трудно обнаружимыми коллизиями требуется, чтобы никакой полиномиально ограниченный противник указанного вида не мог достичь цели с не пренебрежимо малой вероятностью. В работе [2] произвольная пара $(x,y)$, удовлетворяющая вышеуказанным условиям, называется экзистенциальной коллизией для функции $h$. Поэтому говорят, что понятие семейства хэш функций с трудно обнаружимыми коллизиями формализует условие трудности нахождения экзистенциальных коллизий. Основным применением семейств хэш функций с трудно обнаружимыми коллизиями в математической криптографии является построение схем электронной подписи.
Перейдем к формальному определению. Пусть $k$ и $m$ — полиномиальные параметры такие, что $m(n)<k(n)\leqslant p(m(n))$ для каждого $n\in\mathbb N$, где $p$ — некоторый полином. Пусть также при всех $n\in\mathbb N$ определено непустое конечное множество $D_n\subseteq\{0,1\}^*$. Предположим, что каждой паре $(n,d)$, где $n\in\mathbb N$ и $d\in D_n$, поставлена в соответствие функция $h_{n,d}\colon\{0,1\}^{k(n)}\to\{0,1\}^{m(n)}$. Число $n$ играет роль параметра стойкости, а $d$ — роль описания функции $h_{n,d}$ в семействе таких функций, соответствующих данному значению $n$.
- это семейство полиномиально вычислимо;
- это семейство доступно;
- для любого полиномиального вероятностного алгоритма $\mathcal A$ величина \[ \Pr\left(\mathcal A(1^n,d)=(x,y),\, x,y\in\{0,1\}^{k(n)},\, x\ne y,\, h_{n,d}(x)=h_{n,d}(y)\right), \] где $d\in_{\mathfrak U} D_n$, пренебрежимо мала как функция от $n\in\mathbb N$.
Условие 3 этого определения является формализацией условия трудности нахождения экзистенциальных коллизий функции $h_{n,d}$.
В оригинальной работе [1] семейство хэш функций с трудно обнаружимыми коллизиями было построено исходя из семейства пар перестановок с трудно обнаружимыми зубцами. (Впрочем, в этой работе вместо пар рассматривались множества, что не является принципиальным).
Этот результат нельзя назвать глубоким, так как семейства пар псевдоперестановок с трудно обнаружимыми зубцами в некотором смысле очень близки к семействам хэш функций с трудно обнаружимыми коллизиями.
Следующий результат работы [2] можно рассматривать как свидетельство в пользу того, что для доказательства существования семейств хэш функций с трудно обнаружимыми коллизиями требуется более сильное криптографическое предположение, чем предположение о существовании произвольных односторонних перестановок.
Литература
- [1] Damg\aard, I. B. «Collision free hash functions and public key signature schemes» 1987
- [2] Simon, D. R. «Finding collisions on a one-way street: Can secure hash functions be based on general assumptions?» 1998
- [3] Russell, A. «Necessary and sufficient conditions for collision-free hashing» 1992
- [4] Russell, A. «Necessary and sufficient conditions for collision-free hashing» 1995