A new and improved paradigm for hybrid encryption secure against chosen-ciphertext attack

We present a new encryption scheme which is secure against adaptive chosen-ciphertext attack (or CCA2-secure) in the standard model (i.e., without the use of random oracle). Our scheme is a hybrid one: it first uses a public-key step (the Key Encapsulation Module or KEM) to encrypt a random key, which is then used to encrypt the actual message using a symmetric encryption algorithm (the Data Encapsulation Module or DEM). Our scheme is a modification of the hybrid scheme presented by Shoup in (Euro-Crypt'97, Springer LNCS, vol. 1233, pp. 256-266, 1997) (based on the Cramer-Shoup scheme in CRYPTO'98, Springer LNCS, vol. 1462, pp. 13-25, 1998). Its major practical advantage is that it saves the computation of one exponentiation and produces shorter ciphertexts. This efficiency improvement is the result of a surprising observation: previous hybrid schemes were proven secure by proving that both the KEM and the DEM were CCA2-secure. On the other hand, our KEM is not CCA2-secure, yet the whole scheme is, assuming the Decisional Diffie-Hellman (DDH) Assumption. Finally we generalize our new scheme in two ways: (i) we show that security holds also if we use projective hash families (as the original Cramer-Shoup), and (ii) we show that in the random oracle model we can prove security under the weaker Computational Diffie-Hellman (CDH) Assumption. © 2009 International Association for Cryptologic Research.