Reduction to the discrete log problem

Question

Let $G$ be a group of prime order $p$ and generator $g$.

Let $msk_i = (x_i, y_i) \in Z_p^2$ be two master secret keys and $mpk_i = (g^{x_i}, g^{y_i})$ the corresponding master public keys, $i \in [0, 1]$.

Let $dpk = g^{x_i} \cdot g^{H(y_i)} \in Z_p, i \in [0, 1]$ and $H$ is a hash function, be a derived public key from one of the master public keys.

We want to know if $dpk$ is derived from the first or the second master public key, i.e., if $i=0$ or $i=1$. This problem is equivalent to the discrete logarithm problem, right? How can I make the reduction?

Answer 1

This problem is equivalent to the discrete logarithm problem, right?

As written, the problem is informationally secure; that is, you haven't given enough information for anyone (even a computationally unbounded adversary) to solve it.

Here is a simplified version of the same problem: I am thinking of two numbers; one of them is 42; is that the first number I'm thinking of, or the second?

I suspect that you're giving the adversary more information (and whether the problem is reducible to DL would depend on what that more information is)

---

Update (now that you have revised the question): it's fairly obvious that your problem is no harder than DL (that is, with a DL oracle, it is straight-forward to solve your problem).

Going back the other way, it would appear to depend on what the hash function $H$ is. For example, if $H(x)$ is defined to be the lowest bit of $x$, that is, $x \land 1$ (which is stretching the definition of hash function a bit), then an Oracle that solved your problem with that specific $H$ could be used, given $g^z$, to recover the lsbit of $z$ (by passing the public keys $(g^1, g^z)$, $(g^0, g^z)$, and $dpk = g^1$); given an Oracle recovering the lsbit, it's straight-forward to read off the bits of $z$ sequentially.

On the other hand, if $H$ is constrained to be a real hash function (say, SHA-3), it's far less clear how such an Oracle could be used. One issue is that, when you submit a query to the Oracle, $dpk$ is constrained to correspond to one answer or the other; given that you have no knowledge of $z$, you can't compute a reasonable guess of $H(z)$ (or $H$ of any nontrivial linear function of $z$), and there is no other obvious way to proceed.

Now, given that the protocol is secure (assuming DLogs is hard) for the silly $H(x) = x \land 1$, it sounds plausible that it's also secure for $H(x) = \text{SHA3}(x)$; however it wouldn't appear we know how to prove that.