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
    
"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

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.