RSA ⇒ TDP

Standard model · RSA78

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.

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.