Говоря неформально, в криптографии хэш функцией называется полиномиально вычислимая и уменьшающая длину входного значения функция, для которой задача нахождения коллизий вычислительно трудна. Одной из формализаций этого понятия является понятие универсального одностороннего семейства хэш функций, введенное Наором и Юнгом в [1]. Поэтому универсальные односторонние семейства хэш функций уместно называть семействами хэш функций Наора”– Юнга. Иногда универсальные односторонние семейства хэш функций называют универсальными семействами односторонних хэш функций. Это менее точно, так как термин «односторонний» в данном случае относится ко всему семейству, а не к отдельным функциям из него.

Понятие универсального одностороннего семейства хэш функций моделирует ситуацию, когда противник сначала выбирает значение $x$ аргумента хэш функций, а затем, получив случайное описание хэш функции $h$, пытается найти значение $y\ne x$ аргумента хэш функций такое, что $h(y)=h(x)$. В определении универсального одностороннего семейства хэш функций требуется, чтобы никакой полиномиально ограниченный противник указанного вида не мог достичь цели с не пренебрежимо малой вероятностью. В работе [2] произвольный элемент $y$, удовлетворяющий вышеуказанным условиям, называется специфической коллизией для функции $h$ и элемента $x$. Поэтому говорят, что понятие универсального одностороннего семейства хэш функций формализует условие трудности нахождения специфических коллизий.

Основным применением универсальных односторонних семейств хэш функций в математической криптографии является построение схем электронной подписи, стойких против экзистенциальной подделки на основе адаптивной атаки с выбором сообщений (см. [1], [3], [4], [5]).

Перейдем к формальному определению. Пусть $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$ алгоритмом поиска специфических коллизий семейства $(h_{n,d}\,|\, n\in\mathbb N,\, d\in D_n)$, если он работает следующим образом. Сначала, получив на вход $1^n$ при произвольном $n\in\mathbb N$, алгоритм $\mathcal A$ вычисляет некоторую строку $x\in\{0,1\}^{k(n)}$, обозначаемую нами через $\mathcal A(1^n)$. Затем этому алгоритму подается на вход строка $d\in D_n$, после чего он вычисляет строку $y\in\{0,1\}^{k(n)}$, обозначаемую нами через $\mathcal A(1^n,x,d)$. В случае успеха строка $y$ должна быть специфической коллизией для функции $h_{n,d}$ и строки $x$.

Условие 3 этого определения является формализацией условия трудности нахождения специфических коллизий функции $h_{n,d}$.

В уже упоминавшейся пионерской работе [1] была доказана теорема о композиции, утверждающая, что класс универсальных односторонних семейств хэш функций при некоторых условиях замкнут относительно взятия композиции. Приведем обозначения и предположения, необходимые для формулировки этой теоремы. Пусть для каждого $i\in\mathbb N\setminus\{0\}$ определено универсальное одностороннее семейство хэш функций $(h_{i,n,d_i}\,|\, n\in\mathbb N,\, d_i\in D_{i,n})$, где $h_{i,n,d_i}$ отображает $\{0,1\}^{k_i(n)}$ в $\{0,1\}^{k_{i-1}(n)}$. Пусть также $l$ — полиномиальный параметр, принимающий только положительные значения и удовлетворяющий следующему условию:

существует полином $q$ такой, что $k_{l(n)}(n)\leqslant q(k_0(n))$ при любом $n\in\mathbb N$.

Предположим, что имеют место следующие равномерные варианты условий определения 1:

функция $(1^i,1^n,d_i,x)\mapsto h_{i,n,d_i}(x)$, где $i\in\mathbb N\setminus\{0\}$, $n\in\mathbb N$, $d_i\in D_{i,n}$ и $x\in\{0,1\}^{k_i(n)}$, полиномиально вычислима;
существует полиномиальный вероятностный алгоритм $\mathcal G$ такой, что для любых $i\in\mathbb N\setminus\{0\}$ и $n\in\mathbb N$ случайная величина $\mathcal G(1^i,1^n)$ распределена равномерно на $D_{i,n}$;
пусть $\mathcal A$ — произвольный полиномиальный вероятностный алгоритм, который на входе $(1^i,1^n)$, где $n\in\mathbb N$ и $i\in\{1,\dots,l(n)\}$, сначала вычисляет некоторую строку $x_i\in\{0,1\}^{k_i(n)}$, обозначаемую нами через $\mathcal A(1^i,1^n)$, а потом, получив на вход $d_i\in D_{i,n}$, вычисляет строку $y_i\in\{0,1\}^{k_i(n)}$, обозначаемую нами через $\mathcal A(1^i,1^n,x_i,d_i)$. Тогда величина \begin{align*} &\max_{i\in\{1,\dots,l(n)\}}\Pr\left(\mathcal A(1^i,1^n,x_i,d_i)=y_i\in\{0,1\}^{k_i(n)},\right.\\ &\qquad\left.\vphantom{\{0,1\}^{k_i(n)}} y_i\ne x_i,\, h_{i,n,d_i}(y_i)=h_{i,n,d_i}(x_i)\right), \end{align*} где $d_i\in_{\mathfrak U} D_{i,n}$ и $x_i=\mathcal A(1^i,1^n)$, пренебрежимо мала как функция от $n\in\mathbb N$.

Отметим, что если полиномиальный параметр $l$ ограничен сверху, то условия 1–3 выполняются автоматически.

Из теоремы о композиции можно получить важное

Следующая теорема была доказана в [3].

Доказательство этой теоремы довольно сложно. В следующей теореме в качестве примера приводится простая конструкция универсального одностороннего семейства хэш функций на основе односторонней перестановки $f$ (см. [1], [4]). Для каждого $n\in\mathbb N$ введем на множестве $\{0,1\}^{n+1}$ структуру поля (из $2^{n+1}$ элементов) таким образом, чтобы сложение в этом поле совпадало с $\oplus$, а умножение выполнялось за полиномиальное время.

Данная конструкция была обобщена в работе [6] на случай, когда $f$ — произвольная инъективная регулярная по длине односторонняя функция.

Литература

• [1] Naor, M. and Yung, M. «Universal one-way hash functions and their cryptographic applications» 1989
• [2] Simon, D. R. «Finding collisions on a one-way street: Can secure hash functions be based on general assumptions?» 1998
• [3] Rompel, J. «One-way functions are necessary and sufficient for secure signatures» 1990
• [4] Luby, M. «Pseudorandomness and cryptographic applications» 1996
• [5] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
• [6] De Santis, A. and Yung, M. «On the design of provably-secure cryptographic hash functions» 1990