Cryptology ePrint Archive: Report 2004/194

A Note on An Encryption Scheme of Kurosawa and Desmedt

Rosario Gennaro and Victor Shoup

Abstract: Recently Kurosawa and Desmedt presented a new hybrid encryption scheme which is secure against adaptive chosen-ciphertext attack. Their scheme is a modification of the Cramer-Shoup encryption scheme. Its major advantage with respect to Cramer-Shoup is that it saves the computation of one exponentiation and produces shorter ciphertexts. However, the proof presented by Kurosawa and Desmedt relies on the use of information-theoretic key derivation and message authentication functions.

In this note we present a different proof of security which shows that the Kurosawa-Desmedt scheme can be instantiated with any computationally secure key derivation and message authentication functions, thus extending the applicability of their paradigm, and improving its efficiency.

Category / Keywords: public-key cryptography / public-key encryption, chosen ciphertext security

Date: received 10 Aug 2004, last revised 18 May 2005

Contact author: shoup at cs nyu edu

Available format(s): PDF | BibTeX Citation

Version: 20050518:203445 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]