Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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$?

share|improve this question
1  
"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

1 Answer 1

up vote 2 down vote accepted

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.

These kinds of groups are constructed based on various types of elliptic curve, my intuition is that a pairing "out of" a curve group won't help you compute new elements in the group itself.

This kind of group appeared in Boneh, Boyen and Shacham (eprint 2004/174) where they used the Decision Linear assumption instead of DDH, since DLIN can be hard even in the presence of a pairing.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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