Score:0

# Example of enhanced trapdoor perrmutation (Enhanced TDP)

I am currently reading about Trapdoor Permutations (TDP). While I can totally understand and think of examples of TDP. I cannot think of any examples of Enhanced TDP. The definition of both TDP and Enhanced TDP is given below :

Standard Trapdoor Permutations Collection : It is a collection of finite permutations, denoted $$\left\{f_{\alpha}: D_{\alpha} \rightarrow\right.$$ $$\left.D_{\alpha}\right\}$$, accompanied by four probabilistic polynomial-time algorithms, denoted $$I, S, F$$ and $$B$$ (for index, sample, forward and backward), such that the following (syntactic) conditions hold:

1. On input $$1^{n}$$, algorithm $$I$$ selects at random an $$n$$-bit long index $$\alpha$$ (not necessarily uniformly) of a permutation $$f_{\alpha}$$, along with a corresponding trapdoor $$\tau$$;
2. On input $$\alpha$$, algorithm $$S$$ samples the domain of $$f_{\alpha}$$, returning an almost uniformly distributed element in it;
3. For any $$x$$ in the domain of $$f_{\alpha}$$, given $$\alpha$$ and $$x$$, algorithm $$F$$ returns $$f_{\alpha}(x)$$ (i.e., $$\left.F(\alpha, x)=f_{\alpha}(x)\right)$$;
4. For any $$y$$ in the range of $$f_{\alpha}$$ if $$(\alpha, \tau)$$ is a possible output of $$I\left(1^{n}\right)$$, then, given $$\tau$$ and $$y$$, algorithm $$B$$ returns $$f_{\alpha}^{-1}(y)$$ (i.e., $$\left.B(\tau, y)=f_{\alpha}^{-1}(y)\right)$$.

Let $$I_{1}\left(1^{n}\right)$$ denote the first element in the output of $$I\left(1^{n}\right)$$ (i.e., the index), it is required that, for every probabilistic polynomial-time algorithm $$A$$ (resp., every non-uniform family of polynomial-size circuits $$A=\left\{A_{n}\right\}_{n}$$ ), we have $$\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),$$

or equivalently

$$\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)$$

Enchanced Trapdoor Permutations Collection : The only thing that changes it the last condition, where the adversary has access to the random coins of $$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),$$

I was confused with the notation used here. RSA is indeed both TDP and Enhanced TDP. Since there isn't any related question in the SE, I will try to answer it myself when I have time if none else does. The notation became more clearer when I read the Definitions section of this paper https://www.wisdom.weizmann.ac.il/~oded/VO/tdp.pdf
I sit in a Tesla and translated this thread with Ai: