9
$\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$
0

1 Answer 1

16
$\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 to 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$
4
  • $\begingroup$ Also in a previous answer. $\endgroup$ Mar 31, 2019 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, 2019 at 1:23
  • $\begingroup$ The reduction shown in the end of the answer assumes that it is easy (efficient) to take fourth root of a group element in the underlying group. Is that always true? $\endgroup$ Dec 31, 2022 at 10:41
  • $\begingroup$ It is true in all groups whose order is known (if the order is $p$, you just need to compute $4^{-1} \bmod p$). It can be hard e.g. in multiplicative subgroups of $\mathbb{Z}_n$ (where $n$ is a product of two large primes) of order proportional to $\phi(n)$, since knowing the latter entails factoring $n$. But in the discrete log setting, we typically assume that the group order is known. $\endgroup$ Jan 1, 2023 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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