DLOG ⇒ Statistically hiding commitment

Fully-black-box reduction · standard model · Ped91 · security loss: tight: one call to the binding adversary yields ${\log }_{g}h$

Statement

For $(\mathbb{G},g,p)\leftarrow \mathsf{GrGen}(1^{\lambda })$ with $\mathbb{G}$ of prime order $p$ and $h\stackrel{\$}{\leftarrow }\mathbb{G}\setminus \{1\}$, the Pedersen commitment to $m\in {\mathbb{Z}}_p$ is $c=g^m{h}^r$ for $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$, opened by revealing $(m,r)$. It is perfectly hiding, and computationally binding if DLOG is hard for $\mathsf{GrGen}$, since two openings $(m,r)\ne (m^{\prime },r^{\prime })$ of one $c$ give ${\log }_{g}h=(m-m^{\prime })(r^{\prime }-r{)}^{-1}\mathrm{mod}p$ — Ped91.

Sketch

Hiding: $h$ generates $\mathbb{G}$, so $h^r$ is uniform over $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$ and $c$ is uniform, independent of $m$. Binding: on DLOG challenge $X$ the reduction outputs $0$ if $X=1$, and otherwise sets $h=X$, runs the binding adversary and turns its two openings into ${\log }_{g}X$.

\begin{algorithm}
\algname{Algorithm}
\caption{$\Gen(1^\secpar)$}
\begin{algorithmic}
\State $(\GG, g, p) \gets \GrGen(1^\secpar)$; $h \getsr \GG \setminus \{1\}$
\Return $\pp \gets (\GG, g, p, h)$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Algorithm}
\caption{$\Com(\pp, m; r)$}
\begin{algorithmic}
\Return $(c, d) \gets (g^m h^r, (m, r))$
\Comment{$m, r \in \ZZ_p$}
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Algorithm}
\caption{$\Open(\pp, c, (m, r))$}
\begin{algorithmic}
\If{$c = g^m h^r$}
\Return $m$
\EndIf
\Return $\bot$
\end{algorithmic}
\end{algorithm}