Список обозначений

Доступность коллизий

collision accessibility

Пусть $I$ — подмножество $\{0,1\}^*$ или $\mathbb N$. Пусть также при всех $i\in I$ определено непустое конечное множество $D_i\subseteq\{0,1\}^*$. Предположим, что каждой паре $(i,d)$, где $i\in I$ и $d\in D_i$, поставлена в соответствие функция $h_{i,d}$, определенная на некотором множестве $X_i\subseteq\{0,1\}^*$. Тогда семейство функций $(h_{i,d}\,|\, i\in I,\, d\in D_i)$ удовлетворяет условию доступности коллизий, если существует полиномиальный вероятностный алгоритм $\mathcal G$ такой, что для любого $i\in I$ и любых различных $x,y\in X_i$ случайная величина $\mathcal G(i,x,y)$ (при $I\subseteq\{0,1\}^*$) или $\mathcal G(1^i,x,y)$ (при $I\subseteq\mathbb N$) распределена равномерно на множестве $\{d\in D_i\,|\, h_{i,d}(x)=h_{i,d}(y)\}$ (предполагается, что это множество непусто).

Неформальный смысл доступности коллизий состоит в возможности эффективной равновероятной генерации по $i\in I$ и различным $x,y\in X_i$ описания функции из семейства $(h_{i,d}\,|\, d\in D_i)$, для которой заданная пара $(x,y)$ образует экзистенциальную коллизию.

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна