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

5.5.2.1 Определение Наора и Юнга

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

Пусть $ A$ -- противник, имеющий ограниченные вычислительные ресурсы. В однородной модели вычислений $ A$ -- вероятностная машина Тьюринга, работающая за полиномиальное время; в неоднородной модели $ A$ -- семейство схем полиномиального размера. Подробнее о моделях вычислений говорится в главе 14. Противник знает семейство хэш-функций, и его задача состоит в выборе сначала некоторого значения $ x$ и затем в поиске коллизии для функции $ h$, выбранной наудачу из семейства, т. е. значения $ 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$ -- вероятностный алгоритм, работающий за полиномиальное время, который на входе $ k$ выдает строку $ x\in \{0,1\}^{n_{1_{k}}}$, называемую исходным значением, и затем для данной случайной $ h\in H_{k}$ пытается найти $ y\in \{0,1\}^{n_{1_{k}}}$ такое, что $ h(x)=h(y)$, но $ x\ne y$.

Определение 2.  Семейство $ U$ называется универсальным семейством односторонних хэш-функций, если для всех полиномов $ p$, для всех полиномиальных вероятностных алгоритмов $ A$ и всех достаточно больших $ k$ выполняются следующие условия:     1. Если $ x\in \{0,1\}^{n_{1_{k}}}$ -- исходное значение для $ A$, то

$\displaystyle \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}$.

Заметим, что $ H_{k}$ рассматривается как набор описаний функций: два разных описания могут соответствовать одной и той же функции.

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

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

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