# Reduction to the discrete log problem

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?

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?

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.

• You are right, I edited the question @poncho. Apr 21 at 14:50