Paper 2013/765

Kurosawa-Desmedt Key Encapsulation Mechanism, Revisited

Kaoru Kurosawa and Le Trieu Phong

Abstract

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 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.

Note: Add more experimental results.