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

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

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

Существенно более эффективна конструкция Наора и Юнга [NY]. Пусть $ f$ -- односторонняя перестановка (см. п. 5.5.2.3), а $ G_{k}$ -- 2-универсальное семейство хэш-функций, удовлетворяющее условию доступности коллизий (см. подраздел 5.5.1). Тогда

$\displaystyle U=\bigcup_{k}H_{k},$   где$\displaystyle \quad H_{k}=\{h=g\circ f\,\vert\,g\in G_{k}\}, $

является универсальным семейством односторонних хэш-функций. Поскольку существуют достаточно эффективно вычислимые гипотетически односторонние перестановки, а также вполне приемлемые с практической точки зрения универсальные семейства хэш-функций (см. примеры в разделе 1), эта конструкция достаточно эффективна. Проблемы возникают, однако, из-за того, что подобное семейство $ H_{k}$ не обеспечивает достаточной для практических нужд степени сжатия информации (при использовании "сильно сжимающего" семейства хэш-функций $ G_{k}$ свойство доказуемой стойкости теряется!). Теорема 1 из п. 5.5.2.3 позволяет с помощью композиции универсальных семейств односторонних хэш-функций достичь любой полиномиальной степени сжатия, но при этом эффективность конструкции утрачивается. Кроме того, определенные проблемы возникают и с длиной описаний функций из $ H_{k}$ [NY].

Другой подход состоит в построении универсального семейства односторонних хэш-функций непосредственно из какой-либо гипотетически вычислительно трудной задачи. Нам известна единственная работа Импальяццо и Наора [IN], в которой этот подход реализован.

Пусть $ a=(a_{1},\ldots,a_{n})$ -- вектор целых чисел, каждое длиной $ l(n)$ битов. Задача поиска по данному вектору $ a$ и целому числу $ T$ такого подмножества $ S\subset\{1,\ldots,n\}$, что

$\displaystyle \sum_{i\in S}a_{i}\equiv T\mkern5mu\left({\rm mod}\,\,2^{l(n)}\right), $

хорошо известна под названием РЮКЗАК. Эта задача является NP-полной; известны многочисленные попытки использовать ее в криптографии. Эту задачу можно рассматривать как задачу инвертирования функции

$\displaystyle f(a,S)=\left(a,\sum_{i\in S}a_{i}\bmod 2^{l(n)}\right). $

Теорема 4 [IN].  Пусть $ l(n)=(1-c)n$ для некоторой константы $ c>0$. Если для данного $ l(n)$ функция $ f$ является односторонней, то эта же функция, рассматриваемая для каждого $ n$ как коллекция

$\displaystyle \left\{f_{a}(s)=f(a,s)\,\left\vert\,a_{1},\ldots ,a_{n}\in\{0,1\}^{l(n)}\right.\right\} $

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

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 6. Протоколы распределения криптографических ключей Вверх: 5.5.2 Семейства односторонних хэш-функций Назад: 5.5.2.3 Результаты   Содержание   Предметный указатель

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