# Do Gap-CDH groups exist?

A Gap-CDH group is such that, given group elements $g, a = g^x, b = g^y$, it is hard to compute $g^{xy}$, but, given a group element $c$, easy to verify if $c = g^{xy}$. While such groups have been proposed, and it is obviously feasible to define a group where Decision Diffie-Hellman is demonstratively easy, exactly what grounds exist for the conjecture that Computational Diffie-Hellman is hard in such groups, beyond the observation that no known algorithms for solving it yet exist?

Are there ways to reduce the hardness of CDH in a Gap-CDH group (in general or some specific group), to the hardness of CDH in a group that has received more thorough scrutiny over the years? For instance, does there exist a group $G$, such that DDH is easy in $G$, and there exists a proof that the ability to solve CDH in $G$ implies the ability to solve CDH in $Z_p^*$ for a suitably large prime $p$?

• "beyond the observation that no known algorithms for solving it yet exist" I don't think we have anything more for any group we commonly use. – CodesInChaos Jul 8 '13 at 8:51
• @CodesInChaos: Arguably, the conjecture that CDH is hard in $\mathbb Z_p^*$ might inspire more confidence, than the conjecture that it is hard in $\mathbb F_{3^{6l}}$. Presented with a choice, I know of few practitioners who wouldn't prefer to place their trust in the former rather than the latter. Hence the question. – Henrick Hellström Jul 8 '13 at 8:58
• Along these lines, you find the paper "Separating Decision Diffie-Hellman from Computational Diffie-Hellman in Cryptographic Groups." J. Cryptology 16(4): 239-247 (2003) by Joux and Nguyen which shows that you can construct a group where DDH is easy and CDH equivalent to DLOG (it does not prove that it is hard but it feels like a step in the right direction). – minar Jul 8 '13 at 16:25
• @user7423: Everything that promotes the understanding of the underlying math, is of course a step in the right direction, in some trivial sense, but AFAICT that paper really only demonstrates the math behind how to weaken DDH in a group. Knowing that CDH is equivalent to DLOG is of little help, if you are not confident that DLOG is hard in the group to begin with. – Henrick Hellström Jul 8 '13 at 16:35
• What kind of reduction would you expect ? A great difficulty is that when DDH is easy in $G$, it is usually because there is a pairing that can also be used to transfert a Dlog problem from $G$ to some $Z/pZ$. A standard way to prove the kind of hardness you ask for would be to have a morphism in the other direction from $Z/pZ$ to $G$. Unfortunately, this would qualify as "pairing inversion" and the Dlog would become easy in both groups. Did you have a different kind of proof in mind ? – minar Jul 8 '13 at 18:26

The closest that I can think of is a "symmetric bilinear group" (a.k.a. Type-I pairing group) that was popular when bilinear groups were first introduced. This is actually a pair of groups $(G, G_T)$ together with an efficient non-degenerate bilinear map $\otimes: G \times G \to G_T$. Obviously DDH is easy in $G$, since one can on input $(g, U, V, W) \in (G_1)^3$ test whether $g \otimes W = U \otimes V$. But the pairing will not necessarily help you compute CDH in the source group, since the map $(\cdot \otimes g)$ is not meant to be easy to invert.