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


5.5.2.3 Результаты

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

Пусть $ H_{1},H_{2}, \ldots, H_{l}$ -- такие семейства функций, что для любого $ i$ и для любой $ h_{i}\in H_{i}$

$\displaystyle h_{i}\colon\{0,1\}^{n_{i}}\mapsto \{0,1\}^{n_{i-1}}$   и$\displaystyle \quad n_{i}<n_{i+1}. $

Мы называем

$\displaystyle H=\{h\,\vert\,h=h_{1}\circ h_{2}\circ \ldots \circ h_{l}\} $

$ l$-композицией семейств $ H_{1},H_{2}, \ldots, H_{l}$. Семейство $ H$ -- мультимножество; если

$\displaystyle h_{1}\circ h_{2}\circ\ldots\circ h_{l}=h_{1}'\circ h_{2}'\circ\ldots\circ h_{l}', $

для различных наборов

$\displaystyle (h_{1},h_{2},\ldots,h_{l})$   и$\displaystyle \quad(h_{1}',h_{2}',\ldots, h_{l}'), $

то оба эти набора являются элементами семейства $ H$.

Пусть $ \{n_{0_{i}}\}$, $ \{n_{1_{i}}\},\{n_{2_{i}}\},\ldots$ -- последовательность возрастающих последовательностей натуральных чисел, $ U_{1},U_{2},\ldots$ -- последовательность универсальных семейств односторонних хэш-функций таких, что $ U_{i}=\bigcup\limits_{k}H_{i,k}$, где для всякой $ h\in H_{i,k}$

$\displaystyle h: \{0,1\}^{n_{i_{k}}}\mapsto \{0,1\}^{n_{(i-1)_{k}}}. $

Мы также требуем, чтобы все $ U_{i}$ были одновременно сложными, т. е. для любого полинома $ p$ и для любого полиномиального вероятностного алгоритма $ A$ существует такое число $ K$, что для всех $ k>K$    $ A$ может находить коллизии лишь с вероятностью, меньшей $ 1/p(n_{i_{k}})$ для всех $ i\geqslant 1$. Пусть $ l\colon\mathbb{N}\mapsto\mathbb{N}$ -- функция, вычислимая за полиномиальное время такая, что для некоторого полинома $ q$ выполняется неравенство $ q(n_{0_{k}})>n_{l(k)_{k}}$. Наконец, пусть $ H_{k}$ -- $ l(k)$-композиция семейств

$\displaystyle H_{1,k},H_{2,k},\ldots,H_{l(k),k}, $

и пусть $ U= \bigcup\limits_{k}H_{k}$.

Теорема 1 [NY].  $ U$ является универсальным семейством односторонних хэш-функций.

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

$\displaystyle h\colon\{0,1\}^{{k}}\mapsto\{0,1\}^{k-1} $

для всякого $ h\in H_{k}$.

Первый шаг в поиске достаточных условий существования универсальных хэш-функций был сделан все в той же работе Наора и Юнга [NY]. Они построили такое семейство исходя из предположения о существовании односторонней перестановки.

Односторонняя перестановка -- это взаимно однозначная сохраняющая длину функция $ f$, которая вычислима за полиномиальное время и такова, что для любого полинома $ p$, любого вероятностного полиномиального алгоритма $ A$ и любого достаточного большого $ k$

$\displaystyle \Pr[A(f(x))=x]\leqslant 1/p(k), $

где вероятность берется равномерно по всем $ x\in\{0,1\}^{k}$ и по всем случайным выборам $ A$.

Теорема 2 [NY].  Если существует односторонняя перестановка, то для любых двух возрастающих полиномиально связанных последовательностей натуральных чисел $ \{n_{1_{i}}\}$ и $ \{n_{0_{i}}\}$ существует универсальное семейство односторонних хэш-функций $ U= \bigcup\limits_{k}H_{k}$ такое, что для всякой $ h\in H_{k}$

$\displaystyle h\colon\{0,1\}^{n_{1_{k}}}\mapsto \{0,1\}^{n_{0_{k}}}. $

Ромпель [Ro] решил эту задачу окончательно.

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

Отметим, что эти результаты справедливы как в однородной, так и в неоднородной модели вычислений. Но при этом, разумеется, требуется существование функции (или перестановки), односторонней в данной модели.

Для криптографии очень важно следующее следствие теоремы 3 (см. [Ro], [NY]): стойкие схемы электронной подписи существуют тогда и только тогда, когда существуют односторонние функции.

Как уже отмечалось выше, определение семейства хэш-функций с трудно обнаружимыми коллизиями накладывает на это семейство более жесткие требования, чем определение универсального семейства односторонних хэш-функций. Поэтому естественно, что существование семейства хэш-функций с трудно обнаружимыми коллизиями доказано на настоящий момент исходя из более сильных предположений, чем предположение о существовании односторонних функций. Так, Дамгорд [D] доказал существование такого семейства исходя из предположения о существовании не имеющей зубцов пары перестановок. Это понятие было введено в работе Гольдвассер, Микали и Ривеста [GMRiv]. Говоря неформально, две перестановки $ f_{0}$ и $ f_{1}$ с одной и той же областью определения образуют не имеющую зубцов пару (claw-free pair), если вычислительно трудно найти тройку $ x$, $ y$ и $ z$ такую, что $ f_{0}(x)= f_{1}(y)=z$. Существование таких пар перестановок доказано [GMRiv] исходя из предположения об отсутствии эффективных алгоритмов факторизации целых чисел. Кроме того, в работе [DeSY] без ссылки на источник указывается, что семейство хэш-функций с трудно обнаружимыми коллизиями можно построить исходя из предположения о существовании односторонних гомоморфизмов.

В той же работе Де Сантиса и Юнга [DeSY] предпринята попытка определить другие возможные семейства криптографически стойких хэш-функций и исследовать соотношения между ними.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 5.5.2.4 Методы построения универсальных семейств односторонних хэш-функций Вверх: 5.5.2 Семейства односторонних хэш-функций Назад: 5.5.2.2 Определение Дамгорда   Содержание   Предметный указатель

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