# What is a trapdoor permutation?

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?

-
I edited your question to get to the essence of it, about what a trapdoor permutation is. If you still have questions after learning about trapdoor one-way permutations, please post a separate question with the question about ring signatures. –  D.W. Nov 13 '12 at 6:35
The name RSA is used for multiple things: A specific trapdoor one-way permutation, several public-key encryption schemes build on this permutation, several public key signature schemes build on this permutation, and a company which markets these algorithms (and other security-related stuff). Also, the initials of the inventors (Rivest, Shamir, Adleman).. –  Paŭlo Ebermann Nov 13 '12 at 8:58

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$.

-
Thanks for the explanation. I think I get the general idea, but I don't quite understand the math behind it. They describe the function g(x), which uses the RSA's public exponent e and modulus n. What would g(x)^-1 be in this case when provided with my RSA's private component d? –  user1812844 Nov 14 '12 at 19:27
@user1812844, If $g(x)=x^e \bmod n$, then $g^{-1}(y) = y^d \bmod n$. Again, read lecture notes or other stuff on trapdoor one-way permutations and RSA -- this is standard stuff that should be covered in textbooks. –  D.W. Nov 14 '12 at 20:00