2
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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