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

Семейство пар функций с трудно обнаружимыми зубцами

claw-free collection of pairs of functions

Пусть $k$ и $m$ — полиномиальные параметры. Пусть также при всех $n\in\mathbb N$ определено непустое конечное множество $D_n\subseteq\{0,1\}^*$. Предположим, что каждой паре $(n,d)$, где $n\in\mathbb N$ и $d\in D_n$, поставлены в соответствие функции $f_{n,d},g_{n,d}\colon\{0,1\}^{k(n)}\to\{0,1\}^{m(n)}$. Число $n$ играет роль параметра стойкости, а $d$ — роль описания функций $f_{n,d}$ и $g_{n,d}$ в семействах таких функций, соответствующих данному значению $n$.

Определение 1 семейство пар функций с трудно обнаружимыми зубцами
Семейство $((f_{n,d},g_{n,d})\,|\, n\in\mathbb N,\, d\in D_n)$ называется семейством пар функций с трудно обнаружимыми зубцами, если
  1. семейства функций $(f_{n,d}\,|\, n\in\mathbb N,\, d\in D_n)$ и $(g_{n,d}\,|\, n\in\mathbb N,\, d\in D_n)$ полиномиально вычислимы;
  2. семейство функций $(f_{n,d}\,|\, n\in\mathbb N,\, d\in D_n)$ (или, что эквивалентно, $(g_{n,d}\,|\, n\in\mathbb N,\, d\in D_n)$) доступно;
  3. для любого полиномиального вероятностного алгоритма $\mathcal A$ величина \[ \Pr\left(\mathcal A(1^n,d)=(x,y),\, x,y\in\{0,1\}^{k(n)},\, f_{n,d}(x)=g_{n,d}(y)\right), \] где $d\in_{\mathfrak U} D_n$, пренебрежимо мала как функция от $n\in\mathbb N$.

Условие 3 этого определения является формализацией условия трудности нахождения зубцов пары функций $(f_{n,d},g_{n,d})$. Отметим, что оригинальный англоязычный термин «claw-free collection of pairs of functions» неточно отражает сущность этого понятия: в определении требуется не отсутствие зубцов, а трудность их нахождения.

Иногда в определение семейства пар функций с трудно обнаружимыми зубцами добавляют следующее условие (см. [1]):
  1. для любых $n\in\mathbb N$ и $d\in D_n$ случайные величины $f_{n,d}\left(\widetilde u_{k(n)}\right)$ и $g_{n,d}\left(\widetilde u_{k(n)}\right)$ распределены одинаково.
В этом случае зубцы пары функций $(f_{n,d},g_{n,d})$ заведомо существуют. Кроме того, если существуют семейства пар функций с трудно обнаружимыми зубцами, удовлетворяющие условию 1, то существуют односторонние функции (см. также [1]).

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)

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