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

Abstract

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).

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
zhang @ imailab iis u-tokyo ac jp
History
2003-09-20: last of 5 revisions
2003-09-01: received
See all versions
Short URL
https://ia.cr/2003/181
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/181,
      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{https://eprint.iacr.org/2003/181}},
      url = {https://eprint.iacr.org/2003/181}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.