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

Семейство хэш-функций универсальное одностороннее

universal one-way hash function (UOWHF) family
Синонимы: одностороннее семейство хэш-функций

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

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

Условие 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$ — полиномиальный параметр, принимающий только положительные значения и удовлетворяющий следующему условию:
  1. существует полином $q$ такой, что $k_{l(n)}(n)\leqslant q(k_0(n))$ при любом $n\in\mathbb N$.
Предположим, что имеют место следующие равномерные варианты условий определения 1:
  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)}$, полиномиально вычислима;
  2. существует полиномиальный вероятностный алгоритм $\mathcal G$ такой, что для любых $i\in\mathbb N\setminus\{0\}$ и $n\in\mathbb N$ случайная величина $\mathcal G(1^i,1^n)$ распределена равномерно на $D_{i,n}$;
  3. пусть $\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 выполняются автоматически.
Теорема 2 о композиции
Пусть для любых $n\in\mathbb N$ и $d=\left(d_1,\dots,d_{l(n)}\right)$, где $d_i\in D_{i,n}$, функция $h_{n,d}\colon\{0,1\}^{k_{l(n)}(n)}\to\{0,1\}^{k_0(n)}$ определена как композиция функций $h_{l(n),n,d_{l(n)}},\dots,h_{1,n,d_1}$, взятая в указанном порядке. Тогда семейство \[ \left(h_{n,d}\,\left|\,n\in\mathbb N,\, d\in D_{1,n}\times\dots \times D_{l(n),n}\right.\right), \] является универсальным односторонним семейством хэш функций.

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

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

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

Теорема 4
Универсальные односторонние семейства хэш функций существуют тогда и только тогда, когда существуют односторонние функции.

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

Теорема 5
Пусть для произвольных $n\in\mathbb N$, $a\in\{0,1\}^{n+1}\setminus\left\{0^{n+1}\right\}$ и $b\in\{0,1\}^{n+1}$ функция $h_{n,(a,b)}\colon\{0,1\}^{n+1}\to\{0,1\}^n$ определяется как $x\mapsto(af(x)\oplus b)_{[1,\dots,n]}$. Тогда семейство \[ \left(h_{n,(a,b)}\,\left|\,n\in\mathbb N,\, a\in\{0,1\}^{n+1}\setminus\left\{0^{n+1}\right\},\, b\in\{0,1\}^{n+1}\right.\right), \] является универсальным односторонним семейством хэш функций.
Данная конструкция была обобщена в работе [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

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