4
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I had thought of a way during the night, but you beat me on elegance and simplicity! $\endgroup$
    – fgrieu ♦
    Commented Sep 12, 2016 at 6:33
  • $\begingroup$ 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. $\endgroup$
    – tylo
    Commented Sep 12, 2016 at 13:26
  • $\begingroup$ @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) $\endgroup$
    – poncho
    Commented Sep 12, 2016 at 13:37
  • $\begingroup$ That is exactly what I just said. And it is missing from the argument in the answer. Just saying "it's in a subgroup and it's uniform random there" isn't enough. $\endgroup$
    – tylo
    Commented Sep 12, 2016 at 13:42
  • 2
    $\begingroup$ @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)$ $\endgroup$
    – poncho
    Commented Sep 12, 2016 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.