My cryptography slides describe several relations between cryptographic problems. I don't still have a good justification on the following:

If decisional Diffie-Hellman problem is hard then there exists a CCA-secure public key encryption scheme.

How is this justified?

  • 2
    $\begingroup$ By the existence of Cramer-Shoup encryption? $\endgroup$ – Maeher Feb 25 '19 at 16:58
  • $\begingroup$ @Maeher yes i think that's an answer $\endgroup$ – Rodrigo Feb 25 '19 at 21:58

The answer is

Because Cramer-Shoup encryption exists.

The construction of Cramer-Shoup is essentially a modification of ElGamal encryption with an added checksum, that allows to detect tampering of ciphertexts.

The construction assumes a cyclic group $\mathbb{G}$ of order $q$ with two generators $g_1,g_2$ in which the DDH problem is hard, as well as a collision resistant hash function $H : \mathbb{G}^3 \to \mathbb{Z}_q$.

Collision resistant hash functions can be constructed based on the discrete logarithm assumption (See, e.g., Section 121 in these lecture notes by Rafael Pass. There's a bit more work involved in encoding inputs and outputs to match the required domain and range, but it's possible to do.) Since the discrete logarithm problem is hard if the DDH problem is hard, it thus follows that if DDH is hard, then CCA secure PKE exists.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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