×
Garg, Sanjam; Gay, Romain; Hajiabadi, Mohammad

Master-key KDM-secure IBE from pairings. (English) Zbl 1500.94028

Kiayias, Aggelos (ed.) et al., Public-key cryptography – PKC 2020. 23rd IACR international conference on practice and theory of public-key cryptography, Edinburgh, UK, May 4–7, 2020. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 12110, 123-152 (2020).
Summary: Identity-based encryption (IBE) is a generalization of public-key encryption (PKE) by allowing encryptions to be made to user identities. In this work, we seek to obtain IBE schemes that achieve key-dependent-message (KDM) security with respect to messages that depend on the master secret key. Previous KDM-secure schemes only achieved KDM security in simpler settings, in which messages may only depend on user secret keys.
An important motivation behind studying master-KDM security is the application of this notion in obtaining generic constructions of KDM-CCA secure PKE, a primitive notoriously difficult to realize.
We give the first IBE that achieves master-KDM security from standard assumptions in pairing groups. Our construction is modular and combines techniques from KDM-secure PKE based from hash-proof systems, together with IBE that admits a tight security proof in the multi-challenge setting, which happens to be unexpectedly relevant in the context of KDM security. In fact, to the best of our knowledge, this is the first setting where techniques developed in the context of realizing tightly secure cryptosystems have led to a new feasibility result.
As a byproduct, our KDM-secure IBE, and thus the resulting KDM-CCA-secure PKE both enjoy a tight security reduction, independent of the number of challenge ciphertexts, which was not achieved before.
For the entire collection see [Zbl 1496.94004].

Cited in 1 Review
Cited in 4 Documents

MSC:

94A60 Cryptography

Keywords:

identity-based encryption; key-dependent-message security
Cite Review PDF
Full Text: DOI

References:

[1] Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 595-618. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_35 · Zbl 1252.94044 · doi:10.1007/978-3-642-03356-8_35
[2] Attrapadung, N., Hanaoka, G., Yamada, S.: A framework for identity-based encryption with almost tight security. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015, Part I. LNCS, vol. 9452, pp. 521-549. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_22 · Zbl 1380.94069 · doi:10.1007/978-3-662-48797-6_22
[3] Alperin-Sheriff, J., Peikert, C.: Circular and KDM security for identity-based encryption. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 334-352. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30057-8_20 · Zbl 1294.94030 · doi:10.1007/978-3-642-30057-8_20
[4] Applebaum, B.: Key-dependent message security: generic amplification and completeness. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 527-546. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_29 · Zbl 1291.94048 · doi:10.1007/978-3-642-20465-4_29
[5] Brakerski, Z., Goldwasser, S.: Circular and leakage resilient public-key encryption under subgroup indistinguishability. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 1-20. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_1 · Zbl 1280.94042 · doi:10.1007/978-3-642-14623-7_1
[6] Boyle, E., Gilboa, N., Ishai, Y.: Breaking the circuit size barrier for secure computation under DDH. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 509-539. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_19 · Zbl 1384.94038 · doi:10.1007/978-3-662-53018-4_19
[7] Brakerski, Z., Goldwasser, S., Kalai, Y.T.: Black-box circular-secure encryption beyond affine functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 201-218. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19571-6_13 · Zbl 1295.94028 · doi:10.1007/978-3-642-19571-6_13
[8] Barak, B., Haitner, I., Hofheinz, D., Ishai, Y.: Bounded key-dependent message security. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 423-444. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_22 · Zbl 1280.94038 · doi:10.1007/978-3-642-13190-5_22
[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). https://doi.org/10.1007/978-3-540-85174-5_7 · Zbl 1183.94025 · doi:10.1007/978-3-540-85174-5_7
[10] Blazy, O., Kiltz, E., Pan, J.: (Hierarchical) identity-based encryption from affine message authentication. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 408-425. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_23 · Zbl 1345.94044 · doi:10.1007/978-3-662-44371-2_23
[11] Brakerski, Z., Lombardi, A., Segev, G., Vaikuntanathan, V.: Anonymous IBE, leakage resilience and circular security from new assumptions. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part I. LNCS, vol. 10820, pp. 535-564. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_20 · Zbl 1423.94056 · doi:10.1007/978-3-319-78381-9_20
[12] Black, J., Rogaway, P., Shrimpton, T.: Encryption-scheme security in the presence of key-dependent messages. In: Nyberg, K., Heys, H. (eds.) SAC 2002. LNCS, vol. 2595, pp. 62-75. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36492-7_6 · Zbl 1027.68594 · doi:10.1007/3-540-36492-7_6
[13] Camenisch, J., Chandran, N., Shoup, V.: A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 351-368. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01001-9_20 · Zbl 1239.94038 · doi:10.1007/978-3-642-01001-9_20
[14] Chen, J., Gay, R., Wee, H.: Improved dual system ABE in prime-order groups via predicate encodings. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 595-624. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_20 · Zbl 1375.94109 · doi:10.1007/978-3-662-46803-6_20
[15] 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). https://doi.org/10.1007/978-3-540-24676-3_13 · Zbl 1122.94358 · doi:10.1007/978-3-540-24676-3_13
[16] Chen, J., Wee, H.: Fully, (almost) tightly secure IBE and dual system groups. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 435-460. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_25 · Zbl 1311.94072 · doi:10.1007/978-3-642-40084-1_25
[17] Damgård, I.: Towards practical public key systems secure against chosen ciphertext attacks. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 445-456. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_36 · Zbl 0764.94015 · doi:10.1007/3-540-46766-1_36
[18] Döttling, N., Garg, S.: From selective ibe to full IBE and selective HIBE. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part I. LNCS, vol. 10677, pp. 372-408. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_13 · Zbl 1385.94034 · doi:10.1007/978-3-319-70500-2_13
[19] Döttling, N., Garg, S.: Identity-based encryption from the Diffie-Hellman assumption. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part I. LNCS, vol. 10401, pp. 537-569. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_18 · Zbl 1385.94033 · doi:10.1007/978-3-319-63688-7_18
[20] Gong, J., Dong, X., Chen, J., Cao, Z.: Efficient IBE with tight reduction to standard assumption in the multi-challenge setting. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part II. LNCS, vol. 10032, pp. 624-654. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_21 · Zbl 1407.94111 · doi:10.1007/978-3-662-53890-6_21
[21] Gentry, C.: Fully homomorphic encryption using ideal lattices. In: 41st ACM STOC, pp. 169-178. ACM Press, May/June (2009) · Zbl 1304.94059
[22] Gay, R., Hofheinz, D., Kiltz, E., Wee, H.: Tightly CCA-secure encryption without pairings. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part I. LNCS, vol. 9665, pp. 1-27. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_1 · Zbl 1347.94032 · doi:10.1007/978-3-662-49890-3_1
[23] Galindo, D., Herranz, J., Villar, J.: Identity-based encryption with master key-dependent message security and leakage-resilience. In: Foresti, S., Yung, M., Martinelli, F. (eds.) ESORICS 2012. LNCS, vol. 7459, pp. 627-642. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33167-1_36 · Zbl 1404.94074 · doi:10.1007/978-3-642-33167-1_36
[24] 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 2015. LNCS, vol. 9020, pp. 799-822. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46447-2_36 · Zbl 1345.94069 · doi:10.1007/978-3-662-46447-2_36
[25] Hofheinz, D.: Circular chosen-ciphertext security with compact ciphertexts. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 520-536. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_31 · Zbl 1312.94056 · doi:10.1007/978-3-642-38348-9_31
[26] Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random generation from one-way functions (extended abstracts). In: 21st ACM STOC, pp. 12-24. ACM Press, May 1989
[27] Kitagawa, F., Matsuda, T.: CPA-to-CCA transformation for KDM security. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019, Part II. LNCS, vol. 11892, pp. 118-148. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36033-7_5 · Zbl 1455.94173 · doi:10.1007/978-3-030-36033-7_5
[28] Kitagawa, F., Matsuda, T., Tanaka, K.: CCA security and trapdoor functions via key-dependent-message security. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part III. LNCS, vol. 11694, pp. 33-64. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_2 · Zbl 1436.94076 · doi:10.1007/978-3-030-26954-8_2
[29] Kitagawa, F., Tanaka, K.: A framework for achieving KDM-CCA secure public-key encryption. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part II. LNCS, vol. 11273, pp. 127-157. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03329-3_5 · Zbl 1446.94146 · doi:10.1007/978-3-030-03329-3_5
[30] Lombardi, A., Quach, W., Rothblum, R.D., Wichs, D., Wu, D.J.: New constructions of reusable designated-verifier NIZKs. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part III. LNCS, vol. 11694, pp. 670-700. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_22 · Zbl 1509.94117 · doi:10.1007/978-3-030-26954-8_22
[31] Waters, B.: Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 619-636. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_36 · Zbl 1252.94101 · doi:10.1007/978-3-642-03356-8_36
[32] Wee, H.: KDM-security via homomorphic smooth projective hashing. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016, Part II. LNCS, vol. 9615, pp. 159-179. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49387-8_7 · Zbl 1395.94315 · doi:10.1007/978-3-662-49387-8_7
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.