Score:2

Gap between DLog and CDH

cn flag

Is there any concrete group in which one CDH is exponentially easier (even it's still hard) than DLog.

fgrieu avatar
ng flag
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}$.
Mark avatar
ng flag
While not what you ask, [the question](https://crypto.stackexchange.com/questions/44264/groups-for-which-ddh-is-easy-but-cdh-is-hard?rq=1) about the gap between DDH and CDH should probably be linked here.
Score:2
ng flag

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.

poncho avatar
my flag
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...
Ievgeni avatar
cn flag
So you insinuate the answer is "no"?
Mark avatar
ng flag
@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.
Mark avatar
ng flag
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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.