Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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$

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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