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, such as the key-insulated cryptosystems and anonymous channels. 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 not be true according to adaptive chosen ciphertext attack (CCA), even with all component ciphers CCA-secure. We define an extended model of (standard) CCA called chosen ciphertext attack for multiple encryption (ME-CCA) emulating partial breaking of assumptions, and give constructions of multiple encryption satisfying ME-CCA-security. We further relax CCA by introducing weak ME-CCA (ME-wCCA) and study the relations among these definitions, proving ME-wCCA-security can be acquired by combining IND-CCA-secure component ciphers together. We then apply these results to key-insulated cryptosystem.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abe, M., Imai, H.: Flaws in some robust optimistic mix-nets. In: Safavi-Naini, R., Seberry, J. (eds.) ACISP 2003. LNCS, vol. 2727, pp. 39–50. Springer, Heidelberg (2003)
Aiello, B., Bellare, M., Di Crescenzo, G., Venkatesan, R.: Security amplification by composition: the case of doubly-iterated, ideal ciphers. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 390–407. Springer, Heidelberg (1998)
An, J.H., Dodis, Y., Rabin, T.: On the security of joint signature and encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 83–107. Springer, Heidelberg (2002)
Bellare, M., Desai, A., Pointcheval, D., Rogway, P.: Relations among notions of security for public-key encryption schemes. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, p. 26. Springer, Heidelberg (1998)
Canetti, R.: Composable security: A new paradigm for cryptographic protocols. In: 42nd FOCS, pp. 136–145 (2001)
Canetti, R., Krawczyk, H., Nielsen, J.: Relaxing chosen-ciphertext security. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 565–582. Springer, Heidelberg (2003); Full version available, http://eprint.iacr.org/2003/174/
Chaum, D.: Untraceable electronic mail, return address, and digitalpseudonyms. Communication of the ACM 24, 84–88 (1981)
Desmedt, Y., Frankel, Y.: Threshold cryptosystems. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 307–315. Springer, Heidelberg (1990)
Diffie, W., Hellman, M.E.: Exhaustive cryptananlysis of NBS data encryption standard. IEEE Computer Magazine 10(6), 74–84 (1977)
Dodis, Y., Katz, J.: On the chosen ciphertext security of multiple encryption. In: Rump session of Crypto 2003 (2003) manuscript available from the authors
Dodis, Y., Katz, J., Xu, S., Yung, M.: Key-insulated public key cryptosystems. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 65–82. Springer, Heidelberg (2002)
Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography. In: 23rd STOC, pp. 542–552. ACM, New York (1991)
Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography. In: SIAM Journal of Computing, vol. 30. ACM, New York (2000)
Frey, G., Rück, H.G.: A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Mathematics of Computation 62(206), 865–874 (1994)
Goldreich, O.: Foundations of Cryptography, vol. 2 (third posted version). Aavailable at, http://www.wisdom.weizmann.ac.il/oded/PSBookFrag/enc.ps
Goldreich, O.: Foundations of Cryptography, vol. 1. Cambridge University Press, New York (2001)
Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Science (28), 270–299 (1984)
Golle, P., Zhong, S., Boneh, D., Jakobsson, M., Juels, A.: Optimistic mixing for exit-polls. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 451–465. Springer, Heidelberg (2002)
Jakobsson, M.: A practical mix. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 448–461. Springer, Heidelberg (1998)
Juels, M., Jakobsson, M.: An optimally robust hybrid mix network. In: 20th annual ACM Symposium on Principles of Distributed Computation (2001)
Kumar, R., Rajagopalan, S., Sahai, A.: Coding constructions for blacklisting problems. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 609–623. Springer, Heidelberg (1999)
Maurer, U.M., Massey, J.L.: Cascade ciphers: The importance of being first. Journal of Cryptology: the journal of the International Association for Cryptologic Research 6(1), 55–61 (1993)
Menezes, Okamoto, T., Vanstone, S.: Reducing elliptic curve logarithms to lgarithms in a finite field. IEEE Trans. on Information Theory 39, 1639–1646 (1993)
Merkle, R., Hellman, M.: On the security of multiple encryption. Communications of the ACM 24(7), 465–467 (1981)
NESSIE. NESSIE Portfolio of recommended cryptographic primitives (Latest version: February 2003). Available at, https://www.cosic.esat.kuleuven.ac.be/nessie/deliverables/decision-final.pdf
Rackoff, C., Simon, D.: Noninteractive zero-knowledge proof of knowledge and chosen ciphertext attack. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 433–444. Springer, Heidelberg (1992)
Satoh, T., Araki, K.: Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Commentarii Mathematici Universitatis Sancti Pauli (47), 81–92 (1998)
Semaev: Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p. Mathematics of Computation (67), 353–356 (1998)
Shannon, C.: Communication theory of secrecy systems. Bell System Technical Journal 28 (1949)
Shoup, V.: OAEP reconsidered. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 239–259. Springer, Heidelberg (2001)
Shoup, V.: A proposal for an iso standard for public key encryption (version 2.1). Manuscript (2001)
Shoup, V., Gennaro, R.: Securing threshold cryptosystems against chosen ciphertext attack. Journal of Cryptology 15(2), 75–96 (2002)
Smart, N.: The discrete logarithm problems on elliptic curves of trace one. Journal of Cryptology 12, 193–196 (1999)
Watanabe, Y., Shikata, J., Imai, H.: Equivalence between semantic security and indistinguishability against chosen ciphertext attacks. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 71–84. Springer, Heidelberg (2002)
Zhang, R., Hanaoka, G., Shikata, J., Imai, H.: Full version of this paper, Available at, http://eprint.iacr.org/2003/181/
Zhang, R., Hanaoka, G., Shikata, J., Imai, H.: On the security of multi-layered encryption or CCA-security+CCA-security=CCA-security? In: SCIS 2003 (January 2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhang, R., Hanaoka, G., Shikata, J., Imai, H. (2004). On the Security of Multiple Encryption or CCA-security+CCA-security=CCA-security?. In: Bao, F., Deng, R., Zhou, J. (eds) Public Key Cryptography – PKC 2004. PKC 2004. Lecture Notes in Computer Science, vol 2947. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24632-9_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-24632-9_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21018-4
Online ISBN: 978-3-540-24632-9
eBook Packages: Springer Book Archive