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$) ?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered Mar 30, 2019 at 17:56
-
-
$\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$ 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 at 11:15