DLOG ⇒ CRHF

Fully-black-box reduction · standard model · CvHP91 · security loss: none: every collision yields log_g h

Statement

Let $\mathbb{G}$ be a group of prime order $q$ in which DLOG is hard, and let $g,h$ be uniform generators. Then no efficient adversary finds a collision of

$${\mathsf{H}}_{g,h}(x_1,x_2):=g^{x_1}{h}^{x_2},(x_1,x_2)\in {\mathbb{Z}}_q^2,$$

except with negligible probability — CvHP91. If group elements are encoded in fewer than $2t$ bits for $t:=\lfloor \log q\rfloor$, as in a compactly encoded prime-order group, its restriction to $x_1,x_2<2^t$ compresses $\{0,1{\}}^{2t}$ and is a collision-resistant hash function.

Sketch

The reduction receives $h$ and sets the key to $(g,h)$. A collision $(x_1,x_2)\ne (x_1^{\prime },x_2^{\prime })$ gives $g^{x_1-x_1^{\prime }}=h^{x_2^{\prime }-x_2}$ with $x_2\ne x_2^{\prime }$ (otherwise $x_1=x_1^{\prime }$), so ${\log }_{g}h=(x_1-x_1^{\prime })(x_2^{\prime }-x_2{)}^{-1}\mathrm{mod}q$.

Notes

• CvHP91 take $\mathbb{G}$ to be the quotient ${\mathbb{Z}}_p^{\ast }/\{\pm 1\}$ for a safe prime $p=2q+1$, a group of prime order $q$ whose elements are represented by $\{1,\dots ,q\}$ — CvHP91. The order-$q$ subgroup of ${\mathbb{Z}}_p^{\ast }$, isomorphic to it by $\pm x\mapsto x^2$, is another presentation — standard.
• The encoding condition holds when elements have $(1+o(1))\log q$-bit encodings, as in elliptic-curve groups and both presentations above — standard.
• Prime order is needed: in a cyclic group of order $2r$ with $r$ an odd prime, $g^r$ is the unique element of order $2$ for every generator $g$, so with exponents in ${\mathbb{Z}}_{2r}$ the inputs $(r,0)$ and $(0,r)$ collide under every key, even when DLOG is hard in the subgroup of order $r$ — standard.
• Viewed as a commitment to $x_1$ with randomness $x_2$, the same function is the perfectly hiding Pedersen commitment — Ped91.
• Efficiency: two exponentiations, or one multi-exponentiation, per evaluation — standard.