# How to construct a hash function into a cyclic group such that its discrete log is intractable?

From the Linkable Ring Signatures paper:

Let $G = \langle g\rangle$ be a cyclic group of prime order $q$ such that the underlying discrete logarithm problem (DLP) is hard. Let $H_1 : {0, 1}^∗ \to \mathbb Z_q$ and $H_2 : {0, 1}^∗ \to G$ be distinct hash functions viewed as random oracles. Assume that for any $\alpha\in\{0, 1\}^*$, the discrete-log of $H_2(\alpha)$ to the base $g$ is intractable.

For that, as suggested on my previous question, I'll pick a large Sophie Germain Prime $q$ such that $2^{q} \bmod {(2q+1)} = 1$, with $2$ as the group generator. It would be tempting to define $H_2(a) = g^{H(a)}$, where $H$ is a hash function distinct from $H_1$. That would not work as intended, though, because, under that construction, $log_g(H_2(a)) = H(a)$. How can I, thus, construct an appropriate definition for $H_2$ on that problem?

The obvious way to create such a hash function would be to first define a hash function $H$ (distinct from $H_1$) that generates as output an integer in the range $[2, q]$, and then define $H_2(x) = H(x)^2 \bmod (2q+1)$ (that is, square $H(x)$ modulo $2q+1$).
If we treat $H$ as a random oracle, then $H_2(x)$ is a random element (uniformly distributed, other than 1) of the subgroup of $\mathbb Z^*_{2q+1}$ that consists of quadratic residues. We can see this is a random element because each possible value of $H(x)$ yields a distinct quadratic residue, and there are $q-1$ subgroup elements (other than 1), and so each output is generated with equal probability.
This subgroup is the order $q$ subgroup has that you're thinking of, and if the DLP is hard, then it's hard to solve DLP on random elements.
• I think the argument is missing a step there: Assuming $H$ is uniform distributed on the $q$ elements and the DLP is hard on the whole group $\mathbb{Z}_{2q+1}$, we can't necessarily say that it is hard on the subgroup. There is also a subgroup with two elements, and the DLP surely isn't hard there. However, you can actually do a reduction between the quadratic residues and the DLP over the full group with the additional assumption, that it is actually easy to calculate discrete quare roots. – tylo Sep 12 '16 at 13:26
• @tylo: actually, we can say that if the DLP is hard on the whole group, it's hard on the group of QR's; for one, it is easy to compute square roots on this group. In addition, if we have an Oracle that computes DLog in the QR group, we can use that to solve DLogs in the entire group; given $g, h$ (and want to find $g^x = h$, we use the Oracle to compute the Dlog $(g^2)^y = x^2$ (which is in the QR group), and then $x$ is either $y$ or $y + q$ (and it's easy to test which) – poncho Sep 12 '16 at 13:37
• @Viclib: Well, every element generated by $H_2$ is a quadratic residue. Going the other direction, for any quadratic residue $h$ (other than 1), we can find a value $j$ in the range $[2, q]$ for which $j^2 = h$ (as $h$ is a quadratic residue, there must be a $k$ with $k^2 = h$; then we just need to show that either $k$ or $2q+1-k$ (which has the same square) are in the range $[2, q]$). Then, if $H(x)=j$, then $H_2(x) = h$, and so $h$ is a possible result of $H_2(x)$ – poncho Sep 12 '16 at 17:43