Paper 2013/765

Kurosawa-Desmedt Key Encapsulation Mechanism, Revisited and More

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 widely known as not \CCA-secure. In this paper, we present a direct proof of IND-CCA security thanks to a simple twist on the Kurosawa-Desmedt KEM. Our KEM beats the standardized version of Cramer-Shoup KEM in ISO/IEC 18033-2 by margins of -- at least 20\% in encapsulation speed, and -- up to 60\% in decapsulation speed, which are verified by both theoretical comparison and experimental results. The efficiency of decapsulation can be even -- about 40\% better than the decapsulation of the PSEC-KEM in ISO/IEC 18033-2 -- only slightly worse than the decapsulation of the ECIES-KEM in ISO/IEC 18033-2 which is of independent interest since the security of both PSEC-KEM and ECIES-KEM are argued using the controversial random oracle heuristic in contrast to ours. 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. We finally show that, with additional simple yet innovative twists, the KEMs can be proved resilient to certain amount of leakage on the secret key. Specifically with the DDH-based scheme, a fraction of $1/4-o(1)$ of the secret key can be leaked, and when conditioned on a fixed leakage rate, we obtain the most efficient leakage-resilient KEMs regarding computation and storage.

Note: MAC-free schemes and leakage-resilient schemes are added in Sections 5 and 6.