RSA ⇒ TDP

Standard model · RSA78 · security loss: none: an inverter for the family is an RSA solver with the same advantage

Statement

If the RSA assumption holds for $\mathsf{GrGen}$, the RSA family is a trapdoor permutation: for $(n,e,d)\leftarrow \mathsf{GrGen}(1^{\lambda })$, with $n=pq$ and $ed\equiv 1(\mathrm{mod}\varphi (n))$, the map $x\mapsto x^e\mathrm{mod}n$ permutes ${\mathbb{Z}}_n^{\ast }$, the trapdoor $d$ inverts it as $y\mapsto y^d\mathrm{mod}n$, and one-wayness of the family is the RSA assumption — RSA78.

Sketch

Correctness is Euler’s theorem: $x^{ed}=x^{1+k\varphi (n)}=x$ for $x\in {\mathbb{Z}}_n^{\ast }$. An algorithm inverting $x\mapsto x^e\mathrm{mod}n$ on a uniform $x$ without $d$ is an RSA solver with the same advantage — RSA78.

Notes

• The domain is ${\mathbb{Z}}_n^{\ast }$ rather than $\{0,1{\}}^{\ell }$. Applications that sample domain elements from public coins, such as OT and NIZK, need the enhanced or doubly enhanced notions, which suffice for them — GR13.