Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
If there a proof in the literature which says the CONF Problem is equivalent to solving the discrete log ?
Let $g$ be a generator of a cyclic group $\mathbb{G}$ of prime order $q$
CONF problem: given $q,g, g^a, g^{ab}$ find $g^b$
Discrete log problem: given $q, g, g^x$ find $x$
No. There's no known proof that CONF is equivalent to the discrete log, in general. When $q$ is prime, CONF is equivalent to the Diffie-Hellman problem. And it's a long-standing problem whether the Diffie-Hellman problem is equivalent than the discrete log; see, e.g., Are there groups where the computational Diffie Hellman problem is easy but the discrete log problem is hard?.
Proof of equivalence:
Note that if we can solve the Diffie-Hellman problem, we can solve CONF. In particular, suppose $DH$ is a Diffie-Hellman oracle (so $DH(g,g^x,g^y)=g^{xy}$). Then given $g,g^a$, you can compute $g^{a^k}$ for any power $k$: you can add in the exponent using the identity $g^{x+y}=g^x g^y$, and you can multiply in the exponent using the DH-oracle $g^{xy}=DH(g,g^x,g^y)$, so you can do the square-and-multiply algorithm "in the exponent" to compute $g^{a^k}$ from $g^a$. Now setting $k=q-2$, we see that you can compute $g^{a^{q-2}}=g^{a^{-1}}$. Finally, $DH(g,g^{a^{-1}},g^{ab}) = g^b$, so with one more application of the DH-oracle, we can compute $g^b$, solving the CONF problem. Thus, CONF is no harder than the Diffie-Hellman problem.
Also, if we can solve CONF, then we can solve the Diffie-Hellman problem. Suppose $CONF$ is an oracle for the CONF problem, i.e., $CONF(g,g^a,g^{ab})=g^b$. Then
$$CONF(g^x,g,g^y)= CONF(g^x,(g^x)^{x^{-1}},(g^x)^{x^{-1}y}) = (g^x)^{y} = g^{xy},$$
so an efficient solution to the CONF problem lets us solve the Diffie-Hellman problem.
