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

Генератор для семейства функций

generator for a function family
Пусть $N$ — подмножество $\mathbb N$. Пусть также при всех $n\in N$ определено непустое конечное множество $D_n\subseteq\{0,1\}^*$. Предположим, что каждой паре $(n,d)$, где $n\in N$ и $d\in D_n$, поставлена в соответствие функция $f_{n,d}\colon X_{n,d}\to\{0,1\}^*$, где $X_{n,d}\subseteq\{0,1\}^*$. Тогда пара полиномиальных алгоритмов $(\mathcal G,\mathcal E)$ называется генератором для семейства функций $(f_{n,d}\,|\, n\in N,\, d\in D_n)$, если
  • $\mathcal G$ — вероятностный алгоритм, а $\mathcal E$ — детерминированный;
  • для любого $n\in N$ случайная величина $\mathcal G(1^n)$ распределена равномерно на $D_n$;
  • $\mathcal E(1^n,d,x)=f_{n,d}(x)$ для любых $n\in N$, $d\in D_n$ и $x\in X_{n,d}$.
Таким образом, алгоритм $\mathcal G$ генерирует случайные описания функций рассматриваемого семейства, а алгоритм $\mathcal E$ вычисляет значения функций этого семейства. Очевидно, что генераторы для вышеуказанного семейства функций существуют тогда и только тогда, когда это семейство доступно и полиномиально вычислимо.

Понятие генератора для семейства функций носит технический характер и предназначено для определения генератора псевдослучайных функций, генератора псевдослучайных перестановок и генератора сильно псевдослучайных перестановок.

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