Cryptography
rsa public-key terminology trapdoor
Updated Wed, 08 Jun 2022 13:59:39 GMT

# 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?

## Solution

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

• +0 – @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. — Nov 14, 2012 at 20:00