×

A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks. (English) Zbl 1239.94038

Joux, Antoine (ed.), Advances in cryptology – EUROCRYPT 2009. 28th annual international conference on the theory and applications of cryptographic techniques, Cologne, Germany, April 26–30, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-01000-2/pbk). Lecture Notes in Computer Science 5479, 351-368 (2009).
Summary: Recently, at Crypto 2008 [Lect. Notes Comput. Sci. 5157, 108–125 (2008; Zbl 1183.94025)], D. Boneh, S. Halevi, M. Hamburg and R. Ostrovsky (BHHO) solved the long-standing open problem of “circular encryption,” by presenting a public key encryption scheme and proving that it is semantically secure against key dependent chosen plaintext attack (KDM-CPA security) under standard assumptions (and without resorting to random oracles). However, they left as an open problem that of designing an encryption scheme that simultaneously provides security against both key dependent chosen plaintext and adaptive chosen ciphertext attack (KDM-CCA2 security). In this paper, we solve this problem. First, we show that by applying the Naor-Yung “double encryption” paradigm, one can combine any KDM-CPA secure scheme with any (ordinary) CCA2 secure scheme, along with an appropriate non-interactive zero-knowledge proof, to obtain a KDM-CCA2 secure scheme. Second, we give a concrete instantiation that makes use the above KDM-CPA secure scheme of BHHO, along with a generalization of the Cramer-Shoup CCA2 secure encryption scheme, and recently developed pairing-based NIZK proof systems. This instantiation increases the complexity of the BHHO scheme by just a small constant factor.
For the entire collection see [Zbl 1161.94003].

MSC:

94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing

Citations:

Zbl 1183.94025
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Backes, M., Dürmuth, M., Unruh, D.: OAEP is secure under key-dependent messages. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 506–523. Springer, Heidelberg (2008) · Zbl 1206.94050 · doi:10.1007/978-3-540-89255-7_31
[2] Backes, M., Pfitzmann, B., Scedrov, A.: Key-dependent message security under active attacks - BRSIM/UC-soundness of symbolic encryption with key cycles. In: CSF, pp. 112–124 (2007) · doi:10.1109/CSF.2007.23
[3] Bellare, M., Boldyreva, A., Micali, S.: Public-key encryption in a multi-user setting: Security proofs and improvements. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 259–274. Springer, Heidelberg (2000) · Zbl 1082.94504 · doi:10.1007/3-540-45539-6_18
[4] Bellare, M., Rogaway, P.: Optimal asymmetric encryption. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92–111. Springer, Heidelberg (1995) · Zbl 0881.94010 · doi:10.1007/BFb0053428
[5] Black, J., Rogaway, P., Shrimpton, T.: Encryption-scheme security in the presence of key-dependent messages. In: Selected Areas in Cryptography, pp. 62–75 (2002) · Zbl 1027.68594
[6] Bleichenbacher, D.: Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 1–12. Springer, Heidelberg (1998) · Zbl 0931.94017 · doi:10.1007/BFb0055716
[7] Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications (extended abstract). In: STOC 1988, pp. 103–112 (1988)
[8] Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004) · Zbl 1104.94044 · doi:10.1007/978-3-540-28628-8_3
[9] Boneh, D., Halevi, S., Hamburg, M., Ostrovsky, R.: Circular-secure encryption from decision diffie-hellman. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 108–125. Springer, Heidelberg (2008) · Zbl 1183.94025 · doi:10.1007/978-3-540-85174-5_7
[10] Camenisch, J., Chandran, N., Shoup, V.: A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks. Cryptology ePrint Archive, Report 2008/375 (2008), http://eprint.iacr.org/ · Zbl 1239.94038
[11] Camenisch, J.L., Lysyanskaya, A.: An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 93–118. Springer, Heidelberg (2001) · Zbl 0981.94043 · doi:10.1007/3-540-44987-6_7
[12] Camenisch, J.L., Shoup, V.: Practical verifiable encryption and decryption of discrete logarithms. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 126–144. Springer, Heidelberg (2003) · Zbl 1122.94357 · doi:10.1007/978-3-540-45146-4_8
[13] Cramer, R., Shoup, V.: A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 13–25. Springer, Heidelberg (1998) · Zbl 0931.94018 · doi:10.1007/BFb0055717
[14] Cramer, R., Shoup, V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, p. 45. Springer, Heidelberg (2002), http://eprint.iacr.org/2001/085 · Zbl 1055.94011 · doi:10.1007/3-540-46035-7_4
[15] Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography (extended abstract). In: STOC 1991, pp. 542–552 (1991)
[16] Feige, U., Lapidot, D., Shamir, A.: Multiple non-interactive zero knowledge proofs based on a single random string (extended abstract). In: FOCS 1990, pp. 308–317 (1990)
[17] Goldwasser, S., Micali, S.: Probabilistic encryption and how to play mental poker keeping secret all partial information. In: STOC 1982, pp. 365–377 (1982) · doi:10.1145/800070.802212
[18] Groth, J.: Simulation-sound NIZK proofs for a practical language and constant size group signatures. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 444–459. Springer, Heidelberg (2006) · Zbl 1172.94615 · doi:10.1007/11935230_29
[19] Groth, J., Ostrovsky, R., Sahai, A.: Perfect non-interactive zero knowledge for NP. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 339–358. Springer, Heidelberg (2006) · Zbl 1129.94025 · doi:10.1007/11761679_21
[20] Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415–432. Springer, Heidelberg (2008) · Zbl 1149.94320 · doi:10.1007/978-3-540-78967-3_24
[21] Haitner, I., Holenstein, T.: On the (im)possibility of key dependent encryption. In: TCC 2009 (2009) · Zbl 1213.94105
[22] Halevi, S., Krawczyk, H.: Security under key-dependent inputs. In: CCS 2007: Proceedings of the 14th ACM conference on Computer and communications security, pp. 466–475. ACM, New York (2007)
[23] Hofheinz, D., Kiltz, E.: Secure hybrid encryption from weakened key encapsulation. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 553–571. Springer, Heidelberg (2007) · Zbl 1215.94051 · doi:10.1007/978-3-540-74143-5_31
[24] Hofheinz, D., Unruh, D.: Towards key-dependent message security in the standard model. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 108–126. Springer, Heidelberg (2008) · Zbl 1149.94321 · doi:10.1007/978-3-540-78967-3_7
[25] IBM. IBM CCA Basic Services Reference and Guide for the IBM 4758 PCI and IBM 4764 PCI-X Cryptographic Coprocessors: Releases 2.53, 2.54, 3.20, 3.23, 3.24, 3.25, 3.27, and 3.30 (2008)
[26] Kiltz, E.: Chosen-ciphertext security from tag-based encryption. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 581–600. Springer, Heidelberg (2006) · Zbl 1113.94008 · doi:10.1007/11681878_30
[27] Kiltz, E.: Chosen-ciphertext secure key-encapsulation based on gap hashed diffie-hellman. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 282–297. Springer, Heidelberg (2007) · Zbl 1127.94016 · doi:10.1007/978-3-540-71677-8_19
[28] Lim, C.H., Lee, P.J.: Another method for attaining security against adaptively chosen ciphertext attacks. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 420–434. Springer, Heidelberg (1994) · Zbl 0870.94033 · doi:10.1007/3-540-48329-2_36
[29] MacKenzie, P.D., Reiter, M.K., Yang, K.: Alternatives to non-malleability: Definitions, constructions, and applications. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 171–190. Springer, Heidelberg (2004) · Zbl 1197.94193 · doi:10.1007/978-3-540-24638-1_10
[30] Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: STOC 1990, pp. 427–437 (1990) · doi:10.1145/100216.100273
[31] Rackoff, C., Simon, D.R.: Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 433–444. Springer, Heidelberg (1992) · Zbl 0767.94006 · doi:10.1007/3-540-46766-1_35
[32] Rogaway, P., Shrimpton, T.: A provable-security treatment of the key-wrap problem. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 373–390. Springer, Heidelberg (2006) · Zbl 1140.94369 · doi:10.1007/11761679_23
[33] RSA Laboratories. PKCS #11 v2.20: Cryptographic Token Interface Standard (2004)
[34] Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: FOCS 1999, pp. 543–553 (1999) · doi:10.1109/SFFCS.1999.814628
[35] De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., Sahai, A.: Robust non-interactive zero knowledge. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 566–598. Springer, Heidelberg (2001) · Zbl 1003.94526 · doi:10.1007/3-540-44647-8_33
[36] Shacham, H.: A Cramer-Shoup encryption scheme from the linear assumption and from progressively weaker linear variants. Cryptology ePrint Archive, Report 2007/074 (2007), http://eprint.iacr.org/
[37] Shoup, V.: A proposal for an ISO standard for public key encryption, version 2.1 (2001), http://shoup.net/papers/
[38] Shoup, V., Gennaro, R.: Securing threshold cryptosystems against chosen ciphertext attack. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 1–16. Springer, Heidelberg (1998) · Zbl 0919.94031 · doi:10.1007/BFb0054113
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.