Φ-Hiding ⇒ DS (RSA full-domain hash, tight)

Random oracle model · KK12 · security loss: tight: independent of $q_S$ and $q_H$

Statement

Let $e$ be a prime public exponent in the Φ-hiding regime $e\le N^{1/4-\epsilon }$. If the Φ-hiding assumption holds, RSA full-domain hash, which signs as $\mathsf{Sign}(d,m)=H(m{)}^d\mathrm{mod}N$ with $H:\{0,1{\}}^{\ast }\to {\mathbb{Z}}_N^{\ast }$ a random oracle, is EUF-CMA in the random oracle model, by a tight reduction whose loss does not depend on the numbers of signing and hash queries — KK12.

Notes

• The best known reduction from RSA itself loses a factor about $q_S$ (TDP ⇒ DS (full-domain hash)) — Cor00.
• A loss of about $q_S$ is unavoidable for full-domain hash over certified trapdoor permutations — Cor02. The impossibility needs certification and does not cover RSA in the Φ-hiding regime — KK12.