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}$) ?

  • 2
    $\begingroup$ 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? $\endgroup$
    – SEJPM
    Jul 17 at 12:31
  • $\begingroup$ @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 ? $\endgroup$
    – user766787
    Jul 17 at 14:55
  • $\begingroup$ I mean, how should B query A to get the correct answer ? $\endgroup$
    – user766787
    Jul 17 at 15:02
  • $\begingroup$ 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}$? $\endgroup$
    – SEJPM
    Jul 17 at 22:22
  • $\begingroup$ @SEJPM By taking some k multiple of a,b as x,y ? $\endgroup$
    – user766787
    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.


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.