Strong RSA ⇒ COM

Fully-black-box reduction · standard model · FO97 · security loss: tight up to a negligible term: one run of the binding adversary yields a strong-RSA solution for the planted challenge, except with negligible probability over the part of ${\log }_{h}g$ hidden from the committer; hiding is statistical

Statement

Strong RSA implies a statistically hiding, computationally binding commitment scheme to integers. For an RSA modulus $n$ and public bases $g\in ⟨h⟩\subseteq {\mathbb{Z}}_n^{\ast }$ whose order is hidden from the committer, a commitment to $x\in \mathbb{Z}$ is $c=g^x{h}^r\mathrm{mod}n$ with $r$ uniform in a range much larger than $\mathrm{ord}(h)$. Hiding is statistical, and two openings of $c$ to distinct integers yield a strong-RSA solution — FO97. DF02 generalize the scheme to any abelian group whose order is hidden from the committer, with binding under the strong root assumption, and fill the gaps in FO97’s soundness proofs.

Sketch

Two openings $(x_1,r_1)\ne (x_2,r_2)$ of one commitment give $g^{x_1-x_2}=h^{r_2-r_1}$. The reduction plants the challenge as $h$ and sets $g=h^{\alpha }$ for a random $\alpha$ much larger than the group order; the committer’s view fixes $\alpha$ only modulo $\mathrm{ord}(h)$, so $M=\alpha (x_1-x_2)-(r_2-r_1)$ is a nonzero multiple of $\mathrm{ord}(h)$ except with negligible probability. For any prime $e\nmid M$, $h^{e^{-1}\mathrm{mod}M}$ is an $e$-th root of $h$.