Семейство хэш-функций с трудно обнаружимыми коллизиями

collision-intractable hash function family

Говоря неформально, в криптографии хэш функцией называется полиномиально вычислимая и уменьшающая длину входного значения функция, для которой задача нахождения коллизий вычислительно трудна. Одной из формализаций этого понятия является понятие семейства хэш функций с трудно обнаружимыми коллизиями, введенное Дамгордом в [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$.

Определение 1 семейство хэш функций с трудно обнаружимыми коллизиями

Семейство $(h_{n,d}\,|\, n\in\mathbb N,\, d\in 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 [3], [4]

Семейства хэш функций с трудно обнаружимыми коллизиями $(h_{n,d}\,|\, n\in\mathbb N,\, d\in D_n)$, в которых $h_{n,d}$ отображает $\{0,1\}^{m(n)+1}$ в $\{0,1\}^{m(n)}$ для любых $n\in\mathbb N$ и $d\in D_n$, существуют тогда и только тогда, когда существуют семейства пар псевдоперестановок с трудно обнаружимыми зубцами.

Этот результат нельзя назвать глубоким, так как семейства пар псевдоперестановок с трудно обнаружимыми зубцами в некотором смысле очень близки к семействам хэш функций с трудно обнаружимыми коллизиями.

Пример 3 см. [3], [4]

Пусть $\left(\left.\left(f_{n,d}^0,f_{n,d}^1\right)\,\right|\, n\in\mathbb N,\, d\in D_n\right)$ — семейство пар псевдоперестановок с трудно обнаружимыми зубцами, в котором $f_{n,d}^0,f_{n,d}^1\in\operatorname{Fun}\left(\{0,1\}^{m(n)},\{0,1\}^{m(n)}\right)$. Для произвольных $n\in\mathbb N$ и $d\in D_n$ определим функцию $h_{n,d}\colon\{0,1\}^{m(n)+1}\to\{0,1\}^{m(n)}$ формулой \[ h_{n,d}(xb)=f_{n,d}^b(x)\quad\left(x\in\{0,1\}^{m(n)},\, b\in\{0,1\}\right). \] Тогда $(h_{n,d}\,|\, n\in\mathbb N,\, d\in D_n)$ — семейство хэш функций с трудно обнаружимыми коллизиями.

Следующий результат работы [2] можно рассматривать как свидетельство в пользу того, что для доказательства существования семейств хэш функций с трудно обнаружимыми коллизиями требуется более сильное криптографическое предположение, чем предположение о существовании произвольных односторонних перестановок.

Теорема 4

Имеется оракул, относительно которого существуют односторонние перестановки (и, следовательно, универсальные односторонние семейства хэш функций), но не существует семейств хэш функций с трудно обнаружимыми коллизиями.

Литература

[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

Математическая криптография

Семейство хэш-функций с трудно обнаружимыми коллизиями

Литература