11
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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.
    Commented Nov 13, 2012 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
    Commented Nov 13, 2012 at 8:58

1 Answer 1

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Nov 14, 2012 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.
    Commented Nov 14, 2012 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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