Using Hash Functions as a Hedge against Chosen Ciphertext Attacks

The cryptosystem recently proposed by Cramer and Shoup [R. Cramer, V. Shoup, in "Advances in Cryptology--Crypto '98, pp. 13-25, 1998] is a practical public key cryptosystem that is secure against adaptive chosen ciphertext attack provided the Decisional Diffie-Hellman assumption is true. Although this is a reasonable intractability assumption, it would be preferable to base a security proof on a weaker assumption, such as the Computational Diffie-Hellman assumption. Indeed, this cryptosystem in its most basic form is in fact insecure if the Decisional Diffie-Hellman assumption is false. In this paper, we present a practical hybrid scheme that is just as efficient as the scheme of Cramer and Shoup; we prove that the scheme is secure if the Decisional Diffie-Hellman assumption is true; we give strong evidence that the scheme is secure if the weaker, Computational Diffie-Hellman assumption is true by providing a proof of security in the random oracle model.