В настоящее время я читаю о перестановках лазейки (TDP). Пока я вполне могу понять и придумать примеры TDP. Я не могу вспомнить ни одного примера Enhanced TDP. Определение как TDP, так и Enhanced TDP дано ниже:
Коллекция стандартных перестановок люка : это набор конечных перестановок, обозначаемых $\left\{f_{\alpha}: D_{\alpha} \rightarrow\right.$ $\left.D_{\alpha}\right\}$, сопровождаемый четырьмя вероятностными полиномиальными алгоритмами, обозначаемыми $И, С, Ф$ и $В$ (для индекса, образца, вперед и назад), так что выполняются следующие (синтаксические) условия:
- При вводе $1^{n}$, алгоритм $I$ случайным образом выбирает $n$-битный длинный индекс $\альфа$ (не обязательно равномерно) перестановки $f_{\alpha}$, вместе с соответствующим люком $\тау$;
- При вводе $\альфа$, алгоритм $S$ образцы домена $f_{\alpha}$, возвращая в нем почти равномерно распределенный элемент;
- Для любой $х$ в области $f_{\alpha}$, данный $\альфа$ и $х$, алгоритм $F$ возвращается $ f _ {\ альфа} (х) $ (т.е. $\left.F(\alpha, x)=f_{\alpha}(x)\right)$;
- Для любой $у$ в диапазоне $f_{\alpha}$ если $(\альфа,\тау)$ является возможным выходом $I\влево(1^{n}\вправо)$, то учитывая $\тау$ и $у$, алгоритм $В$ возвращается $ f _ {\ альфа} ^ {- 1} (у) $ (т.е. $\left.B(\tau, y)=f_{\alpha}^{-1}(y)\right)$.
Позволять $I_{1}\влево(1^{n}\вправо)$ обозначают первый элемент в выводе $I\влево(1^{n}\вправо)$ (т. е. индекс) требуется, чтобы для каждого вероятностного алгоритма с полиномиальным временем $А$ (соответственно всякое неоднородное семейство схем полиномиального размера $A=\left\{A_{n}\right\}_{n}$ ), у нас есть
$$
\ underset{\ substack{\alpha \leftarrow I_{1}\left(1^{n}\right) \ x \leftarrow S(\alpha)}}{\operatorname{Pr}}\left[A\left (\ альфа, f _ {\ альфа} (х) \ справа) = х \ справа] = \ му (п),
$$
или эквивалентно
$$
\ underset{\ substack{\alpha \leftarrow I_{1}\left(1^{n}\right) \ r \leftarrow R_{n}}}{\operatorname{Pr}}\left[A(\alpha , S (\ альфа; r)) = f _ {\ alpha} ^ {- 1} (S (\ alpha; r)) \ right] = \ mu (n)
$$
Коллекция расширенных перестановок люка : Единственное, что меняет это последнее условие, где противник имеет доступ к случайным монетам $S$
$$
\ underset{\ substack{\alpha \leftarrow I_{1}\left(1^{n}\right) \ r \leftarrow R_n}}{\operatorname{Pr}}\left[A(\alpha, r) = f _ {\ alpha} ^ {- 1} (S (\ alpha; r)) \ right] = \ mu (n),
$$
