Strong RSA ⇒ RSA

Fully-black-box reduction · standard model · folklore · security loss: tight: one oracle call, advantage preserved

Statement

If strong RSA is hard for $\mathsf{GrGen}$, then RSA is hard for $\mathsf{GrGen}$, provided that, given $n$, the exponent $e$ can be sampled efficiently from its conditional distribution under $\mathsf{GrGen}$ (true of the usual choices: a fixed $e$, or a random prime) — folklore.

Sketch

On a strong-RSA challenge $(n,y)$, sample $e$ as $\mathsf{GrGen}$ does given $n$, run the RSA inverter on $(n,e,y)$, and output its answer $\hat{x}$ together with $e$. Since $y$ is uniform in ${\mathbb{Z}}_n^{\ast }$, the inverter sees a correctly distributed RSA instance, and whenever it succeeds, $(\hat{x},e)$ with ${\hat{x}}^e\equiv y(\mathrm{mod}n)$ and $e>1$ is a strong-RSA solution.

Notes

• Whether RSA hardness implies strong-RSA hardness is open — folklore.