Is there any concrete group in which one CDH is exponentially easier (even it's still hard) than DLog.
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ I restate definitions: the DLog problem in group $G$ is computing $x$ given $g$ in $G$, and $g^x$ for unknown $x$ random in $\mathbb Z_{\lvert G\rvert}$. The CDH problem is computing $g^{ab}$ given $(g,g^a,g^b)$ for unknown $a$ and $b$ random in $\mathbb Z_{\lvert G\rvert}$. $\endgroup$– fgrieu ♦Jun 16, 2021 at 6:13
-
1$\begingroup$ While not what you ask, the question about the gap between DDH and CDH should probably be linked here. $\endgroup$– MarkJun 16, 2021 at 17:12
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
The paper The Relationship between Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms contains some results of interest, although they are somewhat technical.
Specifically, it needs:
Smoothness Assumption: For $n\in\mathbb{N}$, define $\nu(n)$ to be the minimum, over $d\in [n-2\sqrt{n}+1, n+2\sqrt{n}+1]$ of the largest prime factor of $d$. The smoothness assumption is that $\nu(n) = (\log n)^{O(1)}$.
In this setting, if one has some small "advice string" specific to $G$ (the paper states one needs the large prime factors of $|G|$ and certain parameters of elliptic curves --- the total advice is of length $O(\log |G|)$, then:
Corollary 5. If the smoothness assumption is true, then there exists a polynomial-time generic (non-uniform) algorithm computing discrete logarithms in cyclic groups of order $n$, making calls to a DH oracle for the same group, if and only if all the multiple prime factors of $n$ are of order $(\log n)^{O(1)}$.
Here, "multiple prime factors" mean mean prime powers $p^e \mid n$ for $e > 1$.
If all prime factors of $n$ are "single" (e.g. $n$ is square-free), it appears they can do somewhat better --- their theorem 2 covers this case, and appears to remove the requirement of knowledge of the elliptic curves + the smoothness assumption (one still needs the factorization), and they explicitly evaluate the complexity of the reduction. I won't copy it here, as the theorem statement is somewhat long.
This is all to say that under a certain number-theoretic assumption, in the non-uniform setting there is no gap between DLOG and CDH.
-
$\begingroup$ Is this result specific to elliptic curves, or would it apply to all cyclic groups? Neither your summary nor the abstract of the paper states it to be applicable only to EC groups; however the smoothness assumption involves a range suspiciously similar to the Hasse Interval... $\endgroup$– ponchoJun 16, 2021 at 21:51
-
-
$\begingroup$ @poncho The result is generic. The idea is to apply CRT/Pohlig Hellman to reduce the case to groups of the form $(\mathbb{Z}/p^e\mathbb{Z})^\times$. If $e > 1$, their proof proceeds by embedding this group into an elliptic curve group, hence the Hasse bound requirement. This is solely part of the proof though. $\endgroup$– MarkJun 17, 2021 at 21:09
-
$\begingroup$ The answer is "no" for non-uniform algorithms. If the order of $G$ is hard to compute though, it is unclear how to do this reduction, as factoring itself is plausibly hard (and I do not know the complexity of finding the correct elliptic curve parameters). Still though, this result means that there can't really be an explicit group you point to where the problems are different, and instead you might hope to look at some family of groups (say the RSA groups $(\mathbb{Z}/pq\mathbb{Z})^*$ for random prime $p, q$) that at least need to have order that is computationally hard to determine. $\endgroup$– MarkJun 17, 2021 at 21:13