Practical key-dependent message chosen-ciphertext security based on decisional composite residuosity and quadratic residuosity assumptions

摘要

An encryption scheme is key-dependent message chosen plaintext attack (KDM-CPA) secure if it is secure even against an attacker who has access to encryptions of messages that depend on the secret key. Such situations naturally occur in some scenarios such as formal calculus, hard-disk encryption, or multi-party protocols. However, up to now, there are not many schemes that achieve KDM-CPA security, let alone KDM chosen ciphertext attack (KDM-CCA) security. The constructions proposed by Camenisch, Chandran, and Shoup (Eurocrypt 2009), and Hofheinz (Eurocrypt 2013) are the only two general constructions that can be proved to be KDM-CCA secure in the standard model. Besides, Qin, Liu, and Huang (ACISP 2013) also presented another concrete implementation. In particular, they showed how to obtain KDM-CCA security from the classic Cramer-Shoup cryptosystem (based on the decisional Diffie-Hellman assumption) w.r.t. a new ensemble of functions (we call QLH ensemble). Since the Cramer-Shoup scheme has short ciphertext size and higher computational efficiency, they obtain practical KDM-CCA security w.r.t. a reasonably large ensemble.In this paper, we study the KDM-CCA security of other cryptosystems proposed by Cramer and Shoup (Eurocrypt 2002). In particular, we prove that the schemes, based on decisional composite residuosity (DCR) and quadratic residuosity (QR) assumptions, respectively, also achieve KDM-CCA security w.r.t. the QLH ensemble. On the one hand, because the DCR-based and QR-based schemes of Cramer et al. are fairly practical, we also obtain practical KDM-CCA security based on DCR and QR assumptions, respectively. On the other hand, compared with the result of Qin et al., we need not tailor the original schemes of Cramer et al. because themselves have natural compatibility for the message space and the secret key space. Copyright (c) 2014 John Wiley & Sons, Ltd.