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

5.5.2.2 Определение Дамгорда

Статья Дамгорда [D] предшествовала работе Наора и Юнга и была, по-видимому, первой попыткой формализации понятия семейства криптографически стойких хэш-функций. Мы будем называть хэш-функции Дамгорда функциями с трудно обнаружимыми коллизиями (хотя в оригинале "collision-free" -- функции без коллизий, но это название не соответствует действительности).

Определение Дамгорда отличается от определения Наора и Юнга той задачей, которую должен решать противник. А именно, от него не требуется теперь предварительно генерировать исходное значение. Противник начинает работу, получив описание хэш-функции $ h$, выбранной наудачу из семейства, и должен найти пару значений $ x\ne y$ такую, что $ h(x)=h(y)$. Таким образом, задача противника здесь проще, т. е. к семействам хэш-функций с трудно обнаружимыми коллизиями предъявляются более жесткие требования, чем к универсальным семействам односторонних хэш-функций.

Пусть $ \{n_{1_{i}}\}$ и $ \{n_{0_{i}}\}$ -- две возрастающие последовательности натуральных чисел такие, что для всех $ i$     $ n_{0_{i}}\leqslant n_{1_{i}}$ и существует такой полином $ q$, что $ q(n_{0_{i}})\geqslant n_{1_{i}}$ (как и в предыдущем подразделе, такие последовательности называются полиномиально связанными). Пусть $ H_{k}$ -- коллекция функций такая, что для всех $ h\in H_{k}$

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

и пусть $ U= \bigcup\limits_{k}H_{k}$. Предположим, что $ A$ -- вероятностный алгоритм, работающий за полиномиальное время, который для данной случайной $ h\in H_{k}$ пытается найти $ x,y\in \{0,1\}^{n_{1_{k}}}$ такие, что $ h(x)=h(y)$, но $ x\ne y$.

Определение 3.  Семейство $ U$ называется семейством хэш-функций с трудно обнаружимым коллизиями, если для всех полиномов $ p$, для всех полиномиальных вероятностных алгоритмов $ A$ и всех достаточно больших $ k$ выполняются следующие условия:     1. $ \Pr[A(h)=(x,y),\ h (x)=h(y),\ y\ne x]<1/p(n_{1_{k}})$, где вероятность берется по всем $ h$ из $ H_{k}$ и по всем случайным выборам алгоритма $ A$.

    2. Для любой $ h\in H_{k}$ существует описание $ \overline h$ полиномиальной (от $ n_{1_{k}}$) длины такое, что по этому описанию и по $ x$ значение $ h(x)$ вычислимо за полиномиальное время.

    3. Коллекция $ H_{k}$ доступна, т. е. существует алгоритм $ G$, который на входе $ k$ равномерно по вероятности генерирует описание функции $ h\in H_{k}$.

Замечание относительно неоднородной модели вычислений, сделанное после определения 2, полностью применимо и к данному определению.

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

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