# CDH solver algorithm construction

If $$A$$ is an efficient algorithm that solves the Computational Diffie-Hellman problem for $$\frac{1}{2}$$ of the inputs and returns a special symbol for the rest, how can I use $$A$$ to construct another algorithm B which solves $$CDH$$ with a higher probability ($$1 -\frac{1}{2^k}$$) ?

• Hint: Can you perhaps transform a given CDH challenge into an independent-looking different one from a solution of which you can recover the original answer?
– SEJPM
Jul 17 at 12:31
• @SEJPM I am not able to understand how. Could you please elaborate a bit more? For any random instance how should B use A as a subroutine ? Jul 17 at 14:55
• I mean, how should B query A to get the correct answer ? Jul 17 at 15:02
• As A is unreliable, B needs to construct fresh, related CDH challenge inputs, can you think of ways to create $g^x,g^y$ from $g^a,g^b$ s.t. $g^{xy}$ helps you recover $g^{ab}$?
– SEJPM
Jul 17 at 22:22
• @SEJPM By taking some k multiple of a,b as x,y ? Jul 18 at 4:40

Suppose $$C_k: (g, g^a, g^b) \mapsto g^{ab}$$ is your CDH-solver, that solves it with probability $$1 - \frac{1}{2^k}$$ and the special symbol otherwise. Let's construct them from $$C_1$$ recursively.
Construction of $$C_{k+1}$$:
1. Calculate $$C_k(g, g^a, g^b)$$. If it returns $$g^{ab}$$, output it (probability of this is $$1 - \frac{1}{2^k}$$). Otherwise, go to the second step.
2. Generate two independent random numbers $$x$$ and $$y$$ uniformly distributed from 1 to $$p-1$$.
3. Calculate $$g^{ax}$$ and $$g^{by}$$. Note, that they are independent from $$g^a$$ and $$g^b$$.
4. Calculate $$C_1(g, g^{ax}, g^{by})$$. If it returns the special symbol, output it (probability of it is $$\frac{1}{2^{k+1}}$$). Otherwise it has calculated $$g^{abxy}$$. Go to the fifth step.
5. Use the extended Euclidean algorithm to find $$z$$, such that $$xyz \equiv 1 (\mod p-1)$$.
6. Calculate $$g^{abxyz} = g^{ab}$$ and output it (probability of it is $$\frac{1}{2^{k+1}}$$).
It is not hard to see, that the total probability of outputting $$g^{ab}$$ is $$1 - \frac{1}{2^k}$$ now.