Abstract
Encryption of data using multiple, independent encryption schemes (“multiple encryption”) has been suggested in a variety of contexts, and can be used, for example, to protect against partial key exposure or cryptanalysis, or to enforce threshold access to data. Most prior work on this subject has focused on the security of multiple encryption against chosen-plaintext attacks, and has shown constructions secure in this sense based on the chosen-plaintext security of the component schemes. Subsequent work has sometimes assumed that these solutions are also secure against chosen-ciphertext attacks when component schemes with stronger security properties are used. Unfortunately, this intuition is false for all existing multiple encryption schemes.
Here, in addition to formalizing the problem of chosen-ciphertext security for multiple encryption, we give simple, efficient, and generic constructions of multiple encryption schemes secure against chosen-ciphertext attacks (based on any component schemes secure against such attacks) in the standard model. We also give a more efficient construction from any (hierarchical) identity-based encryption scheme secure against selective-identity chosen plaintext attacks. Finally, we discuss a wide range of applications for our proposed schemes.
Chapter PDF
Similar content being viewed by others
References
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, p. 390. Springer, Heidelberg (1998)
Bellare, M., Boldyreva, A., Desai, A., Pointcheval, D.: Key-Privacy in Public-Key Encryption. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, p. 566. Springer, Heidelberg (2001)
Bellare, M., Desai, A., Pointcheval, D., Rogaway, 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)
Bellare, M., Namprempre, C.: Authenticated Encryption: Relations Among Notions and Analysis of the Generic Composition Paradigm. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, p. 531. Springer, Heidelberg (2000)
Bellare, M., Palacio, A.: Protecting against Key Exposure: Strongly Key-Insulated Encryption with Optimal Threshold, Available at http://eprint.iacr.org/2002/064
Bellare, M., Rogaway, P.: Collision-Resistant Hashing: Towards Making UOWHFs Practical. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 470–484. Springer, Heidelberg (1997)
Boneh, D., Boyen, X.: Efficient Selective-ID Secure Identity Based Encryption Without Random Oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (2004)
Boneh, D., Franklin, M.: Identity-Based Encryption From the Weil Pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 213. Springer, Heidelberg (2001)
Boneh, D., Di Crescenzo, G., Ostrovsky, R., Persiano, G.: Searchable Public Key Encryption. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 506–522. Springer, Heidelberg (2004)
Boneh, D., Katz, J.: Improved Efficiency for CCA-Secure Cryptosystems Built Using Identity Based Encryption. RSA — Cryptographers Track (2005) (to appear)
Canetti, R., Dodis, Y., Halevi, S., Kushilevitz, E., Sahai, A.: Exposure-Resilient Functions and All-or-Nothing Transforms. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, p. 453. Springer, Heidelberg (2000)
Canetti, R., Halevi, S., Katz, J.: Chosen-Ciphertext Security from Identity-Based Encryption. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 207–222. Springer, Heidelberg (2004)
Canetti, R., Goldwasser, S.: An Efficient Threshold Public-Key Cryptosystem Secure Against Adaptive Chosen-Ciphertext Attack. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 90. Springer, Heidelberg (1999)
Chaum, D.: Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms. Comm. ACM 24(2), 84–88 (1981)
Cramer, R., Shoup, V.: A Practical Public Key Cryptosystem Provably Secure Against Chosen Ciphertext Attack. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, p. 13. Springer, Heidelberg (1998)
Desmedt, Y.: Society and Group-Oriented Cryptography: a New Concept. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 120–127. Springer, Heidelberg (1988)
Dodis, Y., Fazio, N.: Public Key Broadcast Encryption for Stateless Receivers. In: ACM Workshop on Digital Rights Management (2002)
Dodis, Y., Fazio, N.: Public Key Broadcast Encryption Secure Against Adaptive Chosen Ciphertext Attack. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567. Springer, Heidelberg (2002)
Dodis, Y., Ivan, A.: Proxy Cryptography Revisited. In: NDSS 2003 (2003)
Dodis, Y., Katz, J., Xu, S., Yung, M.: Key-Insulated Public-Key Cryptosystems. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, p. 65. Springer, Heidelberg (2002)
Even, S., Goldreich, O.: On the Power of Cascade Ciphers. ACM Trans. Comp. Systems 3, 108–116 (1985)
Fiat, A., Naor, M.: Broadcast Encryption. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 480–491. Springer, Heidelberg (1994)
Franklin, M., Yung, M.: Communication Complexity of Secure Computation. In: STOC 1992 (1992)
Gentry, C.: Certificate-Based Encryption and the Certificate Revocation Problem. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656. Springer, Heidelberg (2003)
Gentry, C., Silverberg, A.: Hierarchical Id-Based Cryptography. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 548–566. Springer, Heidelberg (2002)
Goldschlag, D., Reed, M., Syverson, P.: Onion Routing. Comm. ACM 42(2), 39–41 (1999)
Goldwasser, S., Micali, S., Rivest, R.: A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. SIAM J. Computing 17(2), 281–308 (1988)
Herzberg, A.: On Tolerant Cryptographic Constructions, Available at http://eprint.iacr.org/2002/135/
Krawczyk, H.: Secret sharing made short. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 136–146. Springer, Heidelberg (1994)
MacKenzie, P.: An Efficient Two-Party Public Key Cryptosystem Secure Against Adaptive Chosen Ciphertext Attack. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 47–61. Springer, Heidelberg (2002)
Maurer, U., Massey, J.: Cascade Ciphers: the Importance of Being First. J. Crypto. 6(1), 55–61 (1993)
Merkle, R., Hellman, M.: On the Security of Multiple Encryption. Comm. ACM 24(7), 465–467 (1981)
Naor, D., Naor, M., Lotspiech, J.: Revocation and Tracing Schemes for Stateless Receivers. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 41. Springer, Heidelberg (2001)
NESSIE consortium. Portfolio of Recommended Cryptographic Primitives (Manuscript) (February 2003), Available at http://www.cosic.esat.kuleuven.ac.be/nessie/deliverables/decision-final.pdf
Rabin, M.: Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance. J. ACM 36(2), 335–348 (1989)
Rivest, R.: All-or-Nothing Encryption and the Package Transform. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 210–218. Springer, Heidelberg (1997)
Shamir, A.: How to Share a Secret. Comm. ACM 22(11), 612–613 (1979)
Shannon, C.: Communication Theory of Secrecy Systems. Bell System Technical Journal 28 (October 1949)
Shoup, V.: A Proposal for an ISO Standard for Public-Key Encryption, version 2.1, Available at http://eprint.iacr.org/2001/112/
Shoup, V., Gennaro, R.: Securing Threshold Cryptosystems Against Chosen Ciphertext Attack. J. Crypto 15(2), 75–96 (2002)
Zhang, R., Hanaoka, G., Shikata, J., Imai, H.: On the Security of Multiple Encryption, or CCA-security+CCA-security=CCA-security? In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol. 2947, pp. 360–374. Springer, Heidelberg (2004), Also available at http://eprint.iacr.org/2003/181
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dodis, Y., Katz, J. (2005). Chosen-Ciphertext Security of Multiple Encryption. In: Kilian, J. (eds) Theory of Cryptography. TCC 2005. Lecture Notes in Computer Science, vol 3378. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30576-7_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-30576-7_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24573-5
Online ISBN: 978-3-540-30576-7
eBook Packages: Computer ScienceComputer Science (R0)
Keywords
- Encryption Scheme
- Message Authentication Code
- Broadcast Encryption
- Challenge Ciphertext
- Multiple Encryption
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.