Abstract
The security of public-key encryption (PKE) schemes in a multi-user setting is aimed at capturing real-world scenarios in which an adversary could attack multiple users and multiple ciphertexts of its choice. However, the fact that a real-world adversary can also mount key-exposure attacks for a set of multiple public keys requires us to consider a more realistic notion of security in multi-user settings. In this study, we establish the security notion of PKE in a multi-user setting with corruptions, where an adversary is able to issue (adaptive) encryption, decryption, and corruption (i.e., private key) queries. We then propose the first practical PKE scheme whose security is proven in a multi-user setting with corruptions. The security of our scheme is based on the computational Diffie–Hellman (CDH) assumption and is proven to be tightly chosen-ciphertext secure in a random oracle model. Our scheme essentially follows the recently proposed modular approach of combining KEM and augmented DEM in a multi-user setting, but we show that this modular approach works well in a multi-user setting with corruptions.
Similar content being viewed by others
Notes
“Almost” tightness means that the security loss L is determined by \(O(\lambda )\) for a security parameter \(\lambda \).
“Multi-instance” means that there exist multiple key generation centers, which correspond to multiple users in the process of converting from IBE to PKE.
Roughly speaking, our variant works as follows: for a public key \((g,X_{1}=g^{x_1}, X_{2}=g^{x_2})\) with a corresponding secret key \((x_1, x_2)\), encryption is done by computing \((g^{s}, X_{1}^{s}, X_{2}^{s})\) for a random s and outputting a ciphertext \((g^{s}, H(g^{s}, X_{1}^{s}, X_{2}^{s})\oplus m)\) for a message m.
References
Attrapadung N., Furukawa J., Gomi T., Hanaoka G., Imai H., Zhang R.: Efficient identity-based encryption with tight security reduction. In: Pointcheval D., Mu Y., Chen K. (eds.) CANS, vol. 4301, pp. 19–36. Lecture Notes in Computer ScienceSpringer, Berlin (2006).
Attrapadung N., Hanaoka G., Yamada S.: A framework for identity-based encryption with almost tight security. In: Iwata T., Cheon J.H. (eds.) ASIACRYPT, vol. 9452, pp. 521–549. Lecture Notes in Computer ScienceSpringer, Berlin (2015).
Bader, C., Hofheinz, D., Jager, T., Kiltz, E., Li, Y.: Tightly-secure authenticated key exchange. In: TCC’15, Springer, Lecture Notes in Computer Science, vol. 9014, pp. 629–658 (2015)
Bellare M., Rogaway P.: Introduction to Modern Cryptography. University of California at San Diego, San Diego (2005).
Bellare, M., Desai, A., Pointcheval, D., Rogaway, P.: Relations among notions of security for public-key encryption schemes. In: CRYPTO’98, vol. 1462, pp. 26–45. Springer (1998)
Bellare M., Boldyreva A., Micali S.: Public-key encryption in a multi-user setting: security proofs and improvements. In: Preneel B. (ed.) EUROCRYPT’00, vol. 1807, pp. 259–274. Lecture Notes in Computer ScienceSpringer, Berlin (2000).
Boneh D., Franklin M.K.: Identity-based encryption from the weil pairing. In: Kilian J. (ed.) CRYPTO‘01, vol. 2139, pp. 213–229. Lecture Notes in Computer ScienceSpringer, Berlin (2001).
Boneh D., Canetti R., Halevi S., Katz J.: Chosen-ciphertext security from identity-based encryption. SIAM J. Comput. 36(5), 1301–1328 (2007).
Cash D., Kiltz E., Shoup V.: The twin Diffie–Hellman problem and applications. In: Smart N. (ed.) EUROCRYPT, vol. 4965, pp. 127–145. Lecture Notes in Computer ScienceSpringer, Berlin (2008).
Cramer R., Shoup V.: A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. CRYPTO’98, Lecture Notes in Computer Science, vol. 1462, pp. 13–25. Springer, Berlin (1998).
Diffie W., Hellman M.E.: New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644–654 (2006).
Dolev D., Dwork C., Naor M.: Nonmalleable cryptography. SIAM J. Comput. 30(2), 391–437 (2000).
Fujisaki E., Okamoto T.: How to enhance the security of public-key encryption at minimum cost. In: Imai H., Zheng Y. (eds.) PKC, Lecture Notes in Computer Science, vol. 1560, pp. 53–68. Springer, Berlin (1999).
Gay R., Hofheinz D., Kiltz E., Wee H.: Tightly cca-secure encryption without pairings. In: Fischlin M., Coron J.S. (eds.) EUROCRYPT, Part I, Lecture Notes in Computer Science, vol. 9665, pp. 1–27. Springer, New York (2016).
Gay, R., Hofheinz, D., Kohl, L.: Kurosawa-desmedt meets tight security. In: CRYPTO’17, vol. 10403, pp. 133–160. Springer, Berlin (2017)
Giacon F., Kiltz E., Poettering B.: Hybrid encryption in a multi-user setting, revisited. In: Abdalla M., Dahab R. (eds.) PKC’18, Lecture Notes in Computer Science, vol. 10769, pp. 159–189. Springer, Berlin (2018).
Gjøsteen, K., Jager, T.: Practical and tightly-secure digital signatures and authenticated key exchange. In: CRYPTO’18, Lecture Notes in Computer Science, vol. 10992, pp. 95–125. Springer (2018)
Gong J., Chen J., Dong X., Cao Z., Tang S.: Extended nested dual system groups, revisited. In: Cheng C.M., Chung K.M., Persiano G., Yang B.Y. (eds.) PKC’16, Lecture Notes in Computer Science, vol. 9614, pp. 133–163. Springer, Berlin (2016).
Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. In: EUROCRYPT’08, Lecture Notes in Computer Science, vol. 4965, pp. 415–432. Springer (2008)
Hofheinz, D.: Adaptive partitioning. In: EUROCRYPT’17, Lecture Notes in Computer Science, vol. 10212, pp. 489–518. Springer (2017)
Hofheinz D., Jager T.: Tightly secure signatures and public-key encryption. In: Safavi-Naini R., Canetti R. (eds.) CRYPTO, Lecture Notes in Computer Science, vol. 7417, pp. 590–607. Springer, Cham (2012).
Hofheinz D., Koch J., Striecks C.: Identity-based encryption with (almost) tight security in the multi-instance, multi-ciphertext setting. In: Katz J. (ed.) PKC, Lecture Notes in Computer Science, vol. 9020, pp. 799–822. Springer, Cham (2015).
Hofheinz, D., Hövelmanns, K., Kiltz, E.: A modular analysis of the fujisaki-okamoto transformation. In: TCC’17, Lecture Notes in Computer Science, vol. 10677, pp. 341–371. Springer (2017)
Libert, B., Joye, M., Yung, M., Peters, T.: Concise multi-challenge cca-secure encryption and signatures with almost tight security. In: ASIACRYPT’14, Lecture Notes in Computer Science, vol. 8874, pp. 1–21. Springer (2014)
Libert B., Peters T., Joye M., Yung M.: Compactly hiding linear spans. In: Iwata T., Cheon J.H. (eds.) ASIACRYPT, Part I, Lecture Notes in Computer Science, vol. 9452, pp. 681–707. Springer, Cham (2015).
Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: H. Ortiz (ed.) STOC’90, pp. 427–437. ACM (1990)
Rackoff, C., Simon, D.R.: Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In: CRYPTO’91, vol. 576, pp. 433–444. Springer (1991)
Shamir A.: Identity-based cryptosystems and signature schemes. In: Blakley G.R., Chaum D. (eds.) CRYPTO‘84, Lecture Notes in Computer Science, vol. 196, pp. 47–53. Springer, Berlin (1984).
Acknowledgements
The study was funded by Institute for Information and communications Technology Promotion (Grant No. 2016-6-00600, A Study on Functional Encryption: Construction, Security Analysis, and Implementation).
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by R. Steinfeld.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Lee, Y., Lee, D.H. & Park, J.H. Tightly CCA-secure encryption scheme in a multi-user setting with corruptions. Des. Codes Cryptogr. 88, 2433–2452 (2020). https://doi.org/10.1007/s10623-020-00794-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-020-00794-z