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?


1 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.

  • $\begingroup$ You are right, I edited the question @poncho. $\endgroup$
    – Fiono
    Commented Apr 21, 2021 at 14:50

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.