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