Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If I proved a scheme's security under GDH assumption, in real-life, if this DDH oracle does exist, then it's good, but what about other side ? In real-life, if this DDH oracle doesn't exist, then what's the meaning of proving?

share|improve this question
An oracle gives an advantage to the attacker. So absence of the oracle shouldn't hurt security. (Though for some schemes, absence of the oracle means that the legitimate user can't be implemented efficiently. For example BLS requires uses cheap DDH to validate the signature.) – CodesInChaos Dec 4 '13 at 12:31
@CodesInChaos : for example what? – T.B Dec 4 '13 at 12:39
Presence or absence of the oracle is irrelevant for the security of the scheme. If the security of your scheme is equivalent to a certain reduction not existing, then if that reduction exists, your scheme will be broken because the legitimate user acts as the relevant oracle. – K.G. Dec 4 '13 at 14:31
@CodesInChaos:cheap DDH ?can you show me an example ? – T.B Dec 6 '13 at 4:10

One might imagine that the object of a security proof is to know that if someone breaks your system, that means they have (essentially) found a way to do some computation that you couldn't do before. Sort of a consolation prize.

However, it is better to consider it as a statement of beliefs and consequences of those beliefs. We believe factoring is hard. If a practical attacker against a cryptosystem leads to easy factoring, we must believe that such a practical attacker cannot exist. We must believe that our cryptosystem is secure.

And from this point of view Gap Diffie-Hellman makes sense. We do not believe that CDH reduces to DDH, ergo we must also believe that cryptosystems based on GDH are sound.

share|improve this answer
when a scheme(e.g. protocol) is implemented over a group say $\mathbb{G}$ that does not admit a DDH oracle, if I prove the security of this scheme under GDH assumption,then if a successful adversary can be constructed, what does this mean ? – T.B Dec 4 '13 at 12:48
It means that you have a reduction from CDH to DDH, that is, the two problems are equivalent in that group. – K.G. Dec 4 '13 at 14:14
sorry it's hard for me to understand this, can you give me a clear explanation ? – T.B Dec 4 '13 at 14:24
Obviously not. It may help if you explain what exactly you don't understand. Do you know what a reduction is? What it means for two problems to be equivalent? – K.G. Dec 4 '13 at 14:33
An adversary against the GDH problem is an algorithm that solves the CDH problem given oracle access to a DDH oracle. A reduction from CDH to DDH is an algorithm that solves the CDH problem given oracle access to a DDH oracle. Up to some details I ignore, they're much the same, no? – K.G. Dec 5 '13 at 16:01

Your Answer


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.