Can anyone explain to me what a trapdoor one-way permutation is? Is RSA a trapdoor one-way permutation?
Context: I was reading about ring signatures. On page 560, it describes steps to implementing a ring signature. I am confused by step 3, where $g()$ is a trap-door permutation. The paper briefly says that $g()$ is an RSA trap-door permutation. I thought that RSA was a public-key encryption protocol. Is RSA a trapdoor permutation?
Read Wikipedia: Trapdoor function
Then read Luca Trevisan's lecture notes (jump straight to section 2. Trapdoor Permutations and Encryption). Or, read any other textbook or lecture notes that covers trapdoor permutations.
For instance, if $(n,e)$ is a RSA public key, then $f(x) = x^e \bmod n$ is a trapdoor permutation. It is a permutation, since the function $f:S\to S$ is bijective (where $S=(\mathbb{Z}/n\mathbb{Z})^*$). It is a trapdoor one-way permutation, since given $x$ and the public key, we can easily compute $f(x)$, but given $y$ and the public key, it is difficult to compute $f^{-1}(y)$; yet with the private key (the trapdoor), we can easily compute $f^{-1}(y)$, given $y$.
That should answer your question.
External links referenced by this document: