International Association
for Cryptologic Research

While the hybrid public key encryption scheme of Kurosawa and Desmedt (CRYPTO 2004) is provably secure against chosen ciphertext attacks (namely, IND-CCA-secure), its associated key encapsulation mechanism (KEM) is not IND-CCA-secure (Herranz et al. 2006, Choi et al. 2009). In this paper, we show a simple twist, yet neglected in the literature, on the Kurosawa-Desmedt KEM turning it into a scheme with IND-CCA security under the decisional Diffie-Hellman assumption. Our KEM beats the standardized version of Cramer-Shoup KEM in ISO/IEC 18033-2 by margins of around 30% in encapsulation speed, and 20% ~ 60% in decapsulation speed. Moreover, the public and secret key sizes in our schemes are at least 160-bit smaller than those of the Cramer-Shoup KEM. We then generalize the technique into hash proof systems, proposing several KEM schemes with IND-CCA security under decision linear and decisional composite residuosity assumptions respectively. All the KEMs are in the standard model, and use standard, computationally secure symmetric building blocks.