3
$\begingroup$

Do there exist cryptographic primitives that have proved that they cannot be constructed from CDH assumption only but can from DDH assumption? More generally, do there exist cryptographic primitives that must require decisional problems for their security?

$\endgroup$
2
  • $\begingroup$ Related, DDH implies CDH hardness: crypto.stackexchange.com/q/43370/1172. Probably more on topic: crypto.stackexchange.com/q/44264/1172. Could you indicate if this last link possibly answers your question? If not, can you explain what you are missing? $\endgroup$
    – Maarten Bodewes
    Commented Oct 30, 2023 at 16:02
  • 2
    $\begingroup$ I don't think it answers the question, since the question is asking "are there primitives we can obtain if we assume 'there exists a group G where DDH is hard' but not if we instead make the weaker assumption 'there exists a group G where CDH is hard'?". Having a group where CDH might hold but DDH does not doesn't answer this question. $\endgroup$ Commented Oct 30, 2023 at 16:55

1 Answer 1

4
$\begingroup$

This is a very good question -- but we don't know! The trouble is that if a primitive $X$ exists (i.e. admits any realization in the real world), then CDH logically implies $X$ (the construction is trivial: ignore the CDH assumption and output any construction of $X$ which you believe exists). Hence, you cannot hope to prove that there is a cryptographic primitive which is not implied by CDH! (this is true whether CDH holds or not)

The best you could hope to do would be to restrict your attention to classes of constructions and show that no constructions of this form can be obtained from CDH alone. However, I'm not aware of any result of this form. The best I can say is that there are several important primitives for which we have DDH-based constructions, but getting them from CDH is a major open problem. This includes:

  • Additively-homomorphic encryption (for small messages), which you can get from DDH via Exponential ElGamal.
  • Two-round private information retrieval with polylogarithmic communication. This has been recently achieved from DDH, but getting that from CDH looks very hard. The best we have (in one of my recent works) is a polylogarithmic-communication and logarithmic-round PIR protocol from CDH.
  • Lossy trapdoor functions (or even just lossy functions). We have very nice DDH-based constructions (and they have tons of applications), but under CDH, the best we have so far are just trapdoor function (not lossy), and even that is a fairly recent result that was open for a long time.
  • Non-interactive zero-knowledge proofs are now known from the subexponential hardness of DDH, but the best known result from CDH is my very recent work which suffers from a lot of caveats (in short, it achieves something weaker than a true non-interactive ZK proof).
  • Dual-mode cryptosystems, which are known from DDH. One of their main applications is to the construction of efficient oblivious transfer protocols with strong security properties. We now know how to get this application from CDH via a different route, but this is considerably less efficient, and we still don't have dual-mode cryptosystems from CDH.

There are many other examples of this kind, and even more cases where we have a CDH-based construction, but it is much less efficient than the DDH-based one.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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