Tôi hiện đang đọc về Trapdoor Permutations (TDP). Trong khi tôi hoàn toàn có thể hiểu và nghĩ ra các ví dụ về TDP. Tôi không thể nghĩ ra bất kỳ ví dụ nào về TDP nâng cao. Định nghĩa của cả TDP và TDP nâng cao được đưa ra dưới đây:
Bộ sưu tập hoán vị Trapdoor tiêu chuẩn : Là tập hợp các hoán vị hữu hạn, kí hiệu $\left\{f_{\alpha}: D_{\alpha} \rightarrow\right.$ $\left.D_{\alpha}\right\}$, kèm theo bốn thuật toán thời gian đa thức xác suất, ký hiệu là $I, S, F$ và $B$ (đối với chỉ mục, mẫu, tiến và lùi), sao cho các điều kiện (cú pháp) sau đây được đáp ứng:
- trên đầu vào $1^{n}$, thuật toán $I$ chọn ngẫu nhiên một $n$-bit chỉ số dài $\alpha$ (không nhất thiết phải thống nhất) của một hoán vị $f_{\alpha}$, cùng với một cửa sập tương ứng $\tau$;
- trên đầu vào $\alpha$, thuật toán $S$ lấy mẫu miền của $f_{\alpha}$, trả về một phần tử được phân phối gần như đồng đều trong đó;
- Bất cứ gì $x$ trong miền của $f_{\alpha}$, được cho $\alpha$ và $x$, thuật toán $F$ lợi nhuận $f_{\alpha}(x)$ (I E., $\left.F(\alpha, x)=f_{\alpha}(x)\right)$;
- Bất cứ gì $y$ trong phạm vi của $f_{\alpha}$ nếu $(\alpha, \tau)$ là một đầu ra có thể có của $I\left(1^{n}\right)$, sau đó, đưa ra $\tau$ và $y$, thuật toán $B$ lợi nhuận $f_{\alpha}^{-1}(y)$ (I E., $\left.B(\tau, y)=f_{\alpha}^{-1}(y)\right)$.
Để cho $I_{1}\left(1^{n}\right)$ biểu thị phần tử đầu tiên trong đầu ra của $I\left(1^{n}\right)$ (nghĩa là chỉ mục), yêu cầu rằng, đối với mọi thuật toán thời gian đa thức xác suất $A$ (tương ứng, mọi họ mạch kích thước đa thức không đều $A=\left\{A_{n}\right\}_{n}$ ), chúng ta có
$$
\underset{\substack{\alpha \leftarrow I_{1}\left(1^{n}\right) \ x \leftarrow S(\alpha)}}{\operatorname{Pr}}\left[A\left (\alpha, f_{\alpha}(x)\right)=x\right]=\mu(n),
$$
hoặc tương đương
$$
\underset{\substack{\alpha \leftarrow I_{1}\left(1^{n}\right) \ r \leftarrow R_{n}}}{\operatorname{Pr}}\left[A(\alpha , S(\alpha ; r))=f_{\alpha}^{-1}(S(\alpha ; r))\right]=\mu(n)
$$
Bộ sưu tập hoán vị Trapdoor tăng cường : Điều duy nhất thay đổi nó là điều kiện cuối cùng, trong đó đối thủ có quyền truy cập vào các đồng tiền ngẫu nhiên của $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),
$$
