În prezent, citesc despre Trapdoor Permutations (TDP). Deși pot să înțeleg pe deplin și să mă gândesc la exemple de TDP. Nu mă pot gândi la niciun exemplu de TDP îmbunătățit. Definiția atât a TDP, cât și a TDP îmbunătățit este dată mai jos:
Colecția standard de permutări de trapă : Este o colecție de permutări finite, notate $\left\{f_{\alpha}: D_{\alpha} \rightarrow\right.$ $\left.D_{\alpha}\right\}$, însoțită de patru algoritmi probabilistici în timp polinomial, notați $I, S, F$ și $B$ (pentru index, eșantion, înainte și înapoi), astfel încât să fie valabile următoarele condiții (sintactice):
- La intrare $1^{n}$, algoritm $I$ selectează la întâmplare an $n$-bit index lung $\alpha$ (nu neapărat uniform) a unei permutări $f_{\alpha}$, împreună cu o trapă corespunzătoare $\tau$;
- La intrare $\alpha$, algoritm $S$ eşantioane domeniul de $f_{\alpha}$, returnând un element aproape uniform distribuit în el;
- Pentru orice $x$ în domeniul $f_{\alpha}$, dat $\alpha$ și $x$, algoritm $F$ se intoarce $f_{\alpha}(x)$ (adică $\left.F(\alpha, x)=f_{\alpha}(x)\right)$;
- Pentru orice $y$ în intervalul de $f_{\alpha}$ dacă $(\alpha, \tau)$ este o posibilă ieșire a $I\stânga(1^{n}\dreapta)$, apoi, dat $\tau$ și $y$, algoritm $B$ se intoarce $f_{\alpha}^{-1}(y)$ (adică $\left.B(\tau, y)=f_{\alpha}^{-1}(y)\right)$.
Lăsa $I_{1}\stanga(1^{n}\dreapta)$ notează primul element din ieșirea lui $I\stânga(1^{n}\dreapta)$ (adică indicele), este necesar ca, pentru fiecare algoritm probabilistic în timp polinomial $A$ (respectiv, fiecare familie neuniformă de circuite de dimensiune polinomială $A=\stanga\{A_{n}\dreapta\}_{n}$ ), avem
$$
\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),
$$
sau echivalent
$$
\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)
$$
Colecție îmbunătățită de permutări de trapă : Singurul lucru care îl schimbă ultima condiție, în care adversarul are acces la monedele aleatorii ale $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),
$$
