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

Семейство функций доступное

accessible collection of functions

Семейство функций вида $(f_{i,d}\,|\, i\in I,\, d\in D_i)$, где $I$ — подмножество $\{0,1\}^*$ или $\mathbb N$, а $D_i$ — непустое конечное подмножество $\{0,1\}^*$ при каждом $i\in I$, называется доступным, если семейство равномерных распределений вероятностей на множествах $D_i$ (индексированное множеством $I$) полиномиально конструируемо. Неформальный смысл этого условия состоит в возможности эффективной равновероятной генерации по $i\in I$ описания функции из семейства $(f_{i,d}\,|\, d\in D_i)$.

Пусть $(f_{i,d}\,|\, i\in I,\, d\in D_i)$ — доступное семейство функций. Предположим сначала, что $I\subseteq\{0,1\}^*$. Выберем полиномиальный вероятностный алгоритм $G$ и полиномиальный параметр $k$ такие, что для любого $i\in I$ случайная величина $G(i)$ распределена равномерно на $D_i$ и алгоритм $G$ при вычислении на входе $i$ использует не более $k(\lvert{i}\rvert)$ случайных битов. Тогда во многих случаях вместо рассматриваемого семейства функций можно рассматривать семейство $\left(f_{i,G(i;r)}\,\left|\, i\in I,\, r\in \{0,1\}^{k(\lvert{i}\rvert)}\right.\right)$ и предполагать, что $D_i=\{0,1\}^{k(\lvert{i}\rvert)}$ при всех $i\in I$. Аналогично, если $I\subseteq\mathbb N$, то можно выбрать полиномиальный вероятностный алгоритм $G$ и полиномиальный параметр $k$ такие, что для любого $i\in I$ случайная величина $G(1^i)$ распределена равномерно на $D_i$ и алгоритм $G$ при вычислении на входе $1^i$ использует не более $k(i)$ случайных битов. Тогда во многих случаях вместо рассматриваемого семейства функций можно рассматривать семейство $\left(f_{i,G(1^i;r)}\,\left|\, i\in I,\, r\in \{0,1\}^{k(i)}\right.\right)$ и предполагать, что $D_i=\{0,1\}^{k(i)}$ при всех $i\in I$. Те же самые рассуждения проходят и в случае, когда требуется генерировать за полиномиальное время случайные элементы множества $D_i$, распределенные не обязательно равномерно на этом множестве.

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