7
$\begingroup$

We know that the CDH problem, computing $g^{ab}$ from given $(g, g^a, g^b)\in\mathbb Z_p^3$, is hard. Is it still hard with an auxilary information $\frac{a}{b}\bmod q$ (where both $p$ and $q$ are large primes with $q|p-1$, and $g$ is a generator with order $q$) ?

$\endgroup$
12
$\begingroup$

It is indeed a hard problem - in fact, it is at least as hard as the square Diffie-Hellman problem (SDH), which states that given $(g,g^a)$, it is infeasible to compute $g^{a^2}$. It is a standard and well-studied assumption, and it can be reduced do CDH (correcting a previous version of this answer where I said it does not - I was confusing with the decisional version for which no such reduction is known).

Intuition: intuitively, SDH is exactly a CDH instance together with the constraint $a/b=1$. Hence, it is a particular case of the problem you consider, where $a/b$ is known.

Reduction: given an algorithm $A$ solving your problem, here is how you solve an SDH instance: on input $g,g^a$, pick a random exponent $\lambda$, and compute $g^{\lambda^{-1}a^2} \gets A(g,g^a,g^{\lambda^{-1}a},\lambda)$. I let you check that the input to $A$ is indeed distributed as a random instance of your problem. Then, compute $(g^{\lambda^{-1}a^2})^{\lambda} = g^{a^2}$.

For the reduction from SDH to CDH, it's a standard one; the trick is to use the identity $(x+y)\cdot (x-y) = x^2-y^2$. Setting $x = (a+b)/2$ and $y = (a-b)/2$ gives $ab = ((a+b)^2-(a-b)^2)/4$, from which the reduction to CDH is straightforward, with two calls to an SDH oracle.

$\endgroup$
  • $\begingroup$ Also in a previous answer. $\endgroup$ – Samuel Neves Mar 31 at 13:36
  • $\begingroup$ @LichengWang Remember to mark this answer as accepted if it answered your question - not doing so implies that you are still looking for other answers. $\endgroup$ – Ella Rose Apr 1 at 1:23

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.