Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Kurosawa-Desmedt KEM, IND-CCA security, hash proof systems, standard model.

Date: received 18 Nov 2013, last revised 8 Jan 2014

Contact author: phong at nict go jp

Available format(s): PDF | BibTeX Citation

Note: Add more experimental results.

Version: 20140109:060848 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]