DCR ⇒ FAC

Fully-black-box reduction · standard model · folklore · security loss: tight: one factoring call, advantage factor $1-1/n$

Statement

If DCR is hard, then factoring is hard for the same distribution of $n=pq$: a factoring algorithm yields, with one call, a DCR distinguisher whose advantage is $1-1/n$ times the factoring success probability — folklore.

Sketch

Given a DCR challenge $(n,c)$, run the factoring algorithm on $n$. If it returns a prime factor $p$, set $q:=n/p$ and output $0$ iff $c^{(p-1)(q-1)}\equiv 1(\mathrm{mod}{n}^2)$, which holds iff $c$ is an $n$-th residue; otherwise output a uniform bit. A uniform element of ${\mathbb{Z}}_{n^2}^{\ast }$ is an $n$-th residue with probability $1/n$, which gives the factor $1-1/n$.

Notes

• Whether factoring hardness implies DCR hardness is open — folklore; Pai99, which introduced DCR, proves no such implication.