Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 5.5.2 Семейства односторонних хэш-функций Вверх: 5.5 Теоретические аспекты Назад: 5.5 Теоретические аспекты   Содержание   Предметный указатель


5.5.1 Универсальные семейства хэш-функций

Понятие универсального семейства хэш-функций было введено в 1979 г. Картером и Вегманом [CW].

Определение 1.  Пусть $ A$ и $ B$ -- два конечных множества и $ H$ -- семейство функций из $ A$ в $ B$. $ H$ называется универсальным семейством хэш-функций, если для любых $ x_1\ne x_2\in A$ и $ y_1,y_2\in B$

$\displaystyle \Pr[h(x_1)= y_{1}\land h(x_{2})=y_{2}]=1/\vert B\vert^{2}. $

Вероятность берется по случайному равновероятному выбору функции $ h$ из семейства $ H$.

Обычно предполагается, что мощность образа (множества $ B$) меньше, чем мощность прообраза ($ A$), и что хэш-функции "сжимают" входные слова. Как правило, рассматриваются семейства хэш-функций, которые переводят множество всех двоичных строк длины $ n$ в множество всех двоичных строк длины $ m$, где $ m<n$. Говоря неформально, универсальное семейство хэш-функций -- это метод "перемешивания" с сокращением длины строк, при котором выходные значения распределены равномерно.

Семейство хэш-функций из определения 1 принято назвать 2-универсальным семейством. Если в этом определении заменить пары значений $ x$ и $ y$ на наборы из $ k$ значений, то получим определение $ k$-универсального семейства хэш-функций (см., например, [Ro]).

Лемма о композиции [DeSY].  Пусть $ H_1$ и $ H_2$ -- 2-универсальные семейства хэш-функций, действующих из $ C_1$ в $ C_2$ и из $ C_2$ в $ C_3$ соответственно. Тогда

$\displaystyle H=\{h=h_2\circ h_1\,\vert\,h_1\in H_1,\ h_2\in H_2\}, $

где $ \circ$ обозначает композицию, является 2-универсальным семейством хэш-функций, действующих из $ C_1$ в $ C_3$.

Некоторые из многочисленных примеров применения универсальных семейств хэш-функций в математике можно найти в работах [CW], [Sip], [GS], [IZ], [Nis]. Нас же эти семейства интересуют в основном как инструмент для определения и построения семейств односторонних хэш-функций, рассматриваемых в следующем подразделе.

С прикладной точки зрения универсальные семейства хэш-функций должны удовлетворять некоторым дополнительным требованиям. Во-первых, хэш-функции должны быть эффективно вычислимыми. Часто это требование включают в определение универсального семейства и формализуют следующим образом. У каждой хэш-функции $ h\in H$ имеется достаточно короткое описание $ \overline h$ и существуют два эффективных алгоритма, первый из которых по запросу выдает случайное $ \overline h\in H$, а второй по $ \overline h$ и аргументу $ x$ вычисляет $ h(x)$.

Во-вторых, во многих случаях требуются семейства хэш-функций, которые определяются не на строках только данной фиксированной длины, а на строках всех длин (или бесконечной последовательности длин). В этом случае множество $ H_{n}$, которое действует согласно определению 1 на строках длины $ n$, называют коллекцией хэш-функций, а универсальным семейством называют $ \{H_{n}\}$.

В-третьих, для криптографических приложений иногда требуется так называемое свойство доступности коллизий (collision accessibility). Оно требует существования эффективного алгоритма, который по данным $ x_{1}$ и $ x_{2}$ выбирает $ h\in H$ такую, что $ h(x_{1})=h(x_{2})$, равновероятным образом среди всех функций из $ H$, удовлетворяющих этому свойству. Наор и Юнг [NY] формулируют это требование как дополнительное. Ромпель [Ro] включает несколько более сильное требование непосредственно в определение $ k$-универсального семейства хэш-функций: существует эффективный алгоритм, который для данных

$\displaystyle j\leqslant k,\quad x_{1},\ldots,x_{j}$   и$\displaystyle \quad y_{1},\ldots,y_{j}, $

где все $ x_{l}$ различны, выбирает равновероятным образом среди всех функций $ h_{i}$ таких, что $ h_{i}(x_{1})=y_{1},\ldots,h_{i}(x_{j})=y_{j}$.

Есть несколько хорошо известных эффективных путей построения универсальных семейств хэш-функций. Мы сначала опишем две конструкции 2-универсальных семейств, в каждой из которых длина описания хэш-функции линейно зависит от длины описания элемента из области определения множества $ A$.

1. Пусть $ F$ -- произвольное конечное поле и $ A=B=F$. Семейство $ H$, которое состоит из всех линейных функций на $ F$, является 2-универсальным семейством хэш-функций. Иными словами,

$\displaystyle H=\{ax+b\,\vert\,a,b\in F\}, $

и каждая функция $ h\in H$ определяется единственным образом двумя элементами $ a$ и $ b$.

Наор и Юнг [NY] использовали следующую модификацию этого семейства. Пусть $ F=GF(2^{k})$ и $ \qopname\relax o{chop}\colon\{0,1\}^{k}\to\{0,1\}^{k-1}$ -- функция, которая просто отбрасывает последний бит. Тогда семейство хэш-функций $ \{\qopname\relax o{chop}(ax+b)\}$ является 2-универсальным и удовлетворяет свойству доступности коллизий.

2. Пусть $ A=\{0,1\}^{n}$ и $ B=\{0,1\}^{m}$. Для $ x\in\{0,1\}^{n}$ и $ y\in \{0,1\}^{n+m-1}$ определим конволюцию $ y\circ x$ элементов $ y$ и $ x$ как вектор длины $ m$, $ i$-я координата которого определяется по формуле

$\displaystyle z_{i}=\sum_{j=1}^{n} x_{j}y_{i+j-1}\bmod2. $

Тогда семейство

$\displaystyle H=\{(a\circ x)\oplus b\,\vert\,a\in \{0,1\}^{n+m-1}, b\in \{0,1\}^{m}\} $

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

В качестве примера $ k$-универсального семейства хэш-функций можно предложить следующее семейство, удовлетворяющее определению Ромпеля [Ro].

3. Пусть $ F=GF(2^{m})$, $ A=B=F$. Семейство

$\displaystyle H=\left\{\left.h_{a_{0},\ldots,a_{k-1}}(x)= a_{0}+a_{1}x+\ldots+a_{k-1}x^{k-1}\,\right\vert\, a_{0},\ldots, a_{k-1}\in F\right\} $

является $ k$-универсальным.

Наконец, последний пример.

4. Пусть $ H_{n,m}$ -- множество всех тёплицевых матриц размера $ m\times n$ над $ GF(2)$. $ H_{n,m}$ является 2-универсальным семейством хэш-функций. Поскольку элементы тёплицевых матриц удовлетворяют соотношению $ a_{i,j}=a_{i+1,j+1}$, такая матрица полностью определяется своими первой строкой и первым столбцом. Поэтому описание хэш-функции имеет длину $ o(n+m)$.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 5.5.2 Семейства односторонних хэш-функций Вверх: 5.5 Теоретические аспекты Назад: 5.5 Теоретические аспекты   Содержание   Предметный указатель

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100