Paper 2003/181

On the Security of Multiple Encryption or CCA-security+CCA-security=CCA-security?

Rui Zhang, Goichiro Hanaoka, Junji Shikata, and Hideki Imai


In a practical system, a message is often encrypted more than once by different encryptions, here called multiple encryption, to enhance its security. Additionally, new features may be achieved by multiple encrypting a message for a scheme, such as the key-insulated cryptosystems \cite{DKXY02} and anonymous channels \cite{Cha81}. Intuitively, a multiple encryption should remain ``secure'', whenever there is one component cipher unbreakable in it. In NESSIE's latest Portfolio of recommended cryptographic primitives (Feb. 2003), it is suggested to use multiple encryption with component ciphers based on different assumptions to acquire long term security. However, in this paper we show this needs careful discussion. Especially, this may \emph{not} be true according to (adaptive) chosen ciphertext attack ({\sf CCA}), even with all component ciphers {\sf CCA} secure. We define an extended version of {\sf CCA} called \emph{chosen ciphertext attack for multiple encryption} ({\sf ME-CCA}) to emulate real world partial breaking of assumptions, and give constructions of multiple encryption satisfying {\sf ME-CCA} security. Since {\sf CCA} security seems so stringent, we further relax it by introducing \emph{weak} {\sf ME-CCA} ({\sf ME-wCCA}), and prove {\sf IND-ME-wCCA} secure multiple encryption can be acquired from {\sf IND-gCCA} secure component ciphers. We also study the relation of various security notions for multiple encryption. We then apply these results to key-insulated cryptosystem. It is only previously known in \cite{DKXY02} that a generic construction exists provably secure against {\sf CPA} attack, however, we prove that this generic construction is in fact secure against {\sf ME-wCCA} by choosing all components {\sf IND-CCA} secure. We also give an efficient generic construction of key-insulated cryptosystem, which is so far the \emph{first} generic construction provably secure against {\sf CCA} (in the random oracle model).

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
zhang @ imailab iis u-tokyo ac jp
2003-09-20: last of 5 revisions
2003-09-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rui Zhang and Goichiro Hanaoka and Junji Shikata and Hideki Imai},
      title = {On the Security of Multiple Encryption or CCA-security+CCA-security=CCA-security?},
      howpublished = {Cryptology ePrint Archive, Paper 2003/181},
      year = {2003},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.