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?

  • $\begingroup$ 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. $\endgroup$ – D.W. Nov 13 '12 at 6:35
  • 2
    $\begingroup$ 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).. $\endgroup$ – Paŭlo Ebermann Nov 13 '12 at 8:58

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.

  • $\begingroup$ 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? $\endgroup$ – user1812844 Nov 14 '12 at 19:27
  • $\begingroup$ @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. $\endgroup$ – D.W. Nov 14 '12 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.