# American Institute of Mathematical Sciences

November  2019, 13(4): 759-778. doi: 10.3934/amc.2019044

## Identity-based key aggregate cryptosystem from multilinear maps

 Department of Computer Science and Engineering, Indian Institute of Technology Kharagpur, West Bengal 721302, India

Received  October 2018 Revised  March 2019 Published  June 2019

A key-aggregate cryptosystem (KAC) is the dual of the well-known notion of broadcast encryption (BE). In KAC, each plaintext message is encrypted with respect to some identity, and a single aggregate key can be generated for any arbitrary subset $\mathcal{S}$ of identities, such that any ciphertext designated for any identity in $\mathcal{S}$ can be decrypted using this aggregate key. A KAC scheme is said to be efficient if all public parameters, ciphertexts and aggregate keys have polynomial overhead, and can be generated using poly-time algorithms.

A KAC scheme is said to be identity-based if remains efficient even when the number of unique identities supported by the system is exponential in the security parameter $\lambda$. Unfortunately, existing KAC constructions do not satisfy this property. In particular, adopting these constructions to the identity-based setting leads to public parameters with exponential overhead.

In this paper, we propose new identity-based KAC constructions using multilinear maps that are secure in the generic multilinear map model, and are fully collusion resistant against any number of colluding parties. Our first construction is based on asymmetric multilinear maps, with a poly-logarithmic overhead for the public parameters, and a constant overhead for the ciphertexts and aggregate keys. Our second construction is based on the more generalized symmetric multilinear maps, and offers tighter security bounds in the generic multilinear map model. This construction has a poly-logarithmic overhead for the public parameters and the ciphertexts, while the overhead for the aggregate keys is still constant.

Citation: Sikhar Patranabis, Debdeep Mukhopadhyay. Identity-based key aggregate cryptosystem from multilinear maps. Advances in Mathematics of Communications, 2019, 13 (4) : 759-778. doi: 10.3934/amc.2019044
##### References:
 [1] D. Boneh, X. Boyen and E.-J. Goh, Hierarchical identity based encryption with constant size ciphertext, in Advances in Cryptology–EUROCRYPT 2005, Springer, 3494 (2005), 440–456. doi: 10.1007/11426639_26.  Google Scholar [2] D. Boneh, C. Gentry and B. Waters, Collusion resistant broadcast encryption with short ciphertexts and private keys, in Advances in Cryptology–CRYPTO 2005, Springer, 3621 (2005), 258–275. doi: 10.1007/11535218_16.  Google Scholar [3] D. Boneh and B. Waters, Constrained pseudorandom functions and their applications, in Advances in Cryptology-ASIACRYPT 2013, Springer, 8270 (2013), 280–300. doi: 10.1007/978-3-642-42045-0_15.  Google Scholar [4] D. Boneh, B. Waters and M. Zhandry, Low overhead broadcast encryption from multilinear maps, in Advances in Cryptology–CRYPTO 2014, Springer, 8616 (2014), 206–223. doi: 10.1007/978-3-662-44371-2_12.  Google Scholar [5] D. Boneh, D. J. Wu and J. Zimmerman, Immunizing multilinear maps against zeroizing attacks, IACR Cryptology ePrint Archive, 2014 (2014), 930. Google Scholar [6] J. H. Cheon, K. Han, C. Lee, H. Ryu and D. Stehlé, Cryptanalysis of the multilinear map over the integers, in Advances in Cryptology–EUROCRYPT 2015, Springer, 9056 (2015), 3–12. doi: 10.1007/978-3-662-46800-5_1.  Google Scholar [7] C.-K. Chu, S. S. Chow, W.-G. Tzeng, J. Zhou and R. H. Deng, Key-aggregate cryptosystem for scalable data sharing in cloud storage, Parallel and Distributed Systems, IEEE Transactions on, 25 (2014), 468-477.   Google Scholar [8] J. Coron, M. S. Lee, T. Lepoint and M. Tibouchi, Cryptanalysis of GGH15 multilinear maps, in Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II, 9815 (2016), 607–628. doi: 10.1007/978-3-662-53008-5_21.  Google Scholar [9] J.-S. Coron, T. Lepoint and M. Tibouchi, Practical multilinear maps over the integers, in Advances in Cryptology–CRYPTO 2013, Springer, 8042 (2013), 476–493. doi: 10.1007/978-3-642-40041-4_26.  Google Scholar [10] J.-S. Coron, T. Lepoint and M. Tibouchi, Cryptanalysis of two candidate fixes of multilinear maps over the integers, IACR Cryptology ePrint Archive, 2014 (2014), 975. Google Scholar [11] S. Garg, C. Gentry and S. Halevi, Candidate multilinear maps from ideal lattices, Advances in cryptology–EUROCRYPT 2013, 7881 (2013), 1-17.  doi: 10.1007/978-3-642-38348-9_1.  Google Scholar [12] C. Gentry, S. Gorbunov and S. Halevi, Graph-induced multilinear maps from lattices, in Theory of Cryptography, Springer, 9015 (2015), 498–527. doi: 10.1007/978-3-662-46497-7_20.  Google Scholar [13] C. Gentry, S. Halevi, H. K. Maji and A. Sahai, Zeroizing without zeroes: Cryptanalyzing multilinear maps without encodings of zero, IACR Cryptology ePrint Archive, 2014 (2014), 929. Google Scholar [14] J. Kilian, Founding crytpography on oblivious transfer, in Proceedings of the twentieth annual ACM symposium on Theory of computing, ACM, 1988, 20–31. doi: 10.1145/62212.62215.  Google Scholar [15] D. Moshkovitz, An alternative proof of the schwartz-zippel lemma., in Electronic Colloquium on Computational Complexity (ECCC), 17 (2010), 34. Google Scholar [16] M. Naor and O. Reingold, Number-theoretic constructions of efficient pseudo-random functions, Journal of the ACM (JACM), 51 (2004), 231-262.  doi: 10.1145/972639.972643.  Google Scholar [17] S. Patranabis, Y. Shrivastava and D. Mukhopadhyay, ynamic key-aggregate cryptosystem on elliptic curves for online data sharing, in Progress in Cryptology–INDOCRYPT 2015, Springer, 9462 (2015), 25–44. doi: 10.1007/978-3-319-26617-6_2.  Google Scholar [18] S. Patranabis, Y. Shrivastava and D. Mukhopadhyay, Provably secure key-aggregate cryptosystems with broadcast aggregate keys for online data sharing on the cloud, IEEE Trans. Computers, 66 (2017), 891–904. doi: 10.1109/TC.2016.2629510.  Google Scholar

show all references

##### References:
 [1] D. Boneh, X. Boyen and E.-J. Goh, Hierarchical identity based encryption with constant size ciphertext, in Advances in Cryptology–EUROCRYPT 2005, Springer, 3494 (2005), 440–456. doi: 10.1007/11426639_26.  Google Scholar [2] D. Boneh, C. Gentry and B. Waters, Collusion resistant broadcast encryption with short ciphertexts and private keys, in Advances in Cryptology–CRYPTO 2005, Springer, 3621 (2005), 258–275. doi: 10.1007/11535218_16.  Google Scholar [3] D. Boneh and B. Waters, Constrained pseudorandom functions and their applications, in Advances in Cryptology-ASIACRYPT 2013, Springer, 8270 (2013), 280–300. doi: 10.1007/978-3-642-42045-0_15.  Google Scholar [4] D. Boneh, B. Waters and M. Zhandry, Low overhead broadcast encryption from multilinear maps, in Advances in Cryptology–CRYPTO 2014, Springer, 8616 (2014), 206–223. doi: 10.1007/978-3-662-44371-2_12.  Google Scholar [5] D. Boneh, D. J. Wu and J. Zimmerman, Immunizing multilinear maps against zeroizing attacks, IACR Cryptology ePrint Archive, 2014 (2014), 930. Google Scholar [6] J. H. Cheon, K. Han, C. Lee, H. Ryu and D. Stehlé, Cryptanalysis of the multilinear map over the integers, in Advances in Cryptology–EUROCRYPT 2015, Springer, 9056 (2015), 3–12. doi: 10.1007/978-3-662-46800-5_1.  Google Scholar [7] C.-K. Chu, S. S. Chow, W.-G. Tzeng, J. Zhou and R. H. Deng, Key-aggregate cryptosystem for scalable data sharing in cloud storage, Parallel and Distributed Systems, IEEE Transactions on, 25 (2014), 468-477.   Google Scholar [8] J. Coron, M. S. Lee, T. Lepoint and M. Tibouchi, Cryptanalysis of GGH15 multilinear maps, in Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II, 9815 (2016), 607–628. doi: 10.1007/978-3-662-53008-5_21.  Google Scholar [9] J.-S. Coron, T. Lepoint and M. Tibouchi, Practical multilinear maps over the integers, in Advances in Cryptology–CRYPTO 2013, Springer, 8042 (2013), 476–493. doi: 10.1007/978-3-642-40041-4_26.  Google Scholar [10] J.-S. Coron, T. Lepoint and M. Tibouchi, Cryptanalysis of two candidate fixes of multilinear maps over the integers, IACR Cryptology ePrint Archive, 2014 (2014), 975. Google Scholar [11] S. Garg, C. Gentry and S. Halevi, Candidate multilinear maps from ideal lattices, Advances in cryptology–EUROCRYPT 2013, 7881 (2013), 1-17.  doi: 10.1007/978-3-642-38348-9_1.  Google Scholar [12] C. Gentry, S. Gorbunov and S. Halevi, Graph-induced multilinear maps from lattices, in Theory of Cryptography, Springer, 9015 (2015), 498–527. doi: 10.1007/978-3-662-46497-7_20.  Google Scholar [13] C. Gentry, S. Halevi, H. K. Maji and A. Sahai, Zeroizing without zeroes: Cryptanalyzing multilinear maps without encodings of zero, IACR Cryptology ePrint Archive, 2014 (2014), 929. Google Scholar [14] J. Kilian, Founding crytpography on oblivious transfer, in Proceedings of the twentieth annual ACM symposium on Theory of computing, ACM, 1988, 20–31. doi: 10.1145/62212.62215.  Google Scholar [15] D. Moshkovitz, An alternative proof of the schwartz-zippel lemma., in Electronic Colloquium on Computational Complexity (ECCC), 17 (2010), 34. Google Scholar [16] M. Naor and O. Reingold, Number-theoretic constructions of efficient pseudo-random functions, Journal of the ACM (JACM), 51 (2004), 231-262.  doi: 10.1145/972639.972643.  Google Scholar [17] S. Patranabis, Y. Shrivastava and D. Mukhopadhyay, ynamic key-aggregate cryptosystem on elliptic curves for online data sharing, in Progress in Cryptology–INDOCRYPT 2015, Springer, 9462 (2015), 25–44. doi: 10.1007/978-3-319-26617-6_2.  Google Scholar [18] S. Patranabis, Y. Shrivastava and D. Mukhopadhyay, Provably secure key-aggregate cryptosystems with broadcast aggregate keys for online data sharing on the cloud, IEEE Trans. Computers, 66 (2017), 891–904. doi: 10.1109/TC.2016.2629510.  Google Scholar
Theorem 1: Upper Bounds on Contributions to Length of $L$
 Query Stage Maximum Contribution to $|L|$ SetUp $m+2$ Oracle Query Phase $Q_E+Q_M+Q_P$ Aggregate Key Query Phase (1 and 2) $Q_K$ Challenge $5$ Total $Q_E+Q_M+Q_P+Q_K+m+7$
 Query Stage Maximum Contribution to $|L|$ SetUp $m+2$ Oracle Query Phase $Q_E+Q_M+Q_P$ Aggregate Key Query Phase (1 and 2) $Q_K$ Challenge $5$ Total $Q_E+Q_M+Q_P+Q_K+m+7$
Theorem 2: Upper Bounds on Contributions to Length of $L$
 Query Stage Maximum Contribution to $|L|$ SetUp $2m+1$ Oracle Query Phase $Q_E+Q_M+Q_P$ Aggregate Key Query Phase (1 and 2) $2Q_K$ Challenge $m+5$ Total $Q_E+Q_M+Q_P+2Q_K+3m+6$
 Query Stage Maximum Contribution to $|L|$ SetUp $2m+1$ Oracle Query Phase $Q_E+Q_M+Q_P$ Aggregate Key Query Phase (1 and 2) $2Q_K$ Challenge $m+5$ Total $Q_E+Q_M+Q_P+2Q_K+3m+6$
 [1] Yang Lu, Jiguo Li. Forward-secure identity-based encryption with direct chosen-ciphertext security in the standard model. Advances in Mathematics of Communications, 2017, 11 (1) : 161-177. doi: 10.3934/amc.2017010 [2] David Galindo, Javier Herranz, Eike Kiltz. On the generic construction of identity-based signatures with additional properties. Advances in Mathematics of Communications, 2010, 4 (4) : 453-483. doi: 10.3934/amc.2010.4.453 [3] Yang Lu, Quanling Zhang, Jiguo Li. An improved certificateless strong key-insulated signature scheme in the standard model. Advances in Mathematics of Communications, 2015, 9 (3) : 353-373. doi: 10.3934/amc.2015.9.353 [4] Rainer Steinwandt, Adriana Suárez Corona. Attribute-based group key establishment. Advances in Mathematics of Communications, 2010, 4 (3) : 381-398. doi: 10.3934/amc.2010.4.381 [5] Roman VodiČka, Vladislav MantiČ. An energy based formulation of a quasi-static interface damage model with a multilinear cohesive law. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1539-1561. doi: 10.3934/dcdss.2017079 [6] Helen Moore, Weiqing Gu. A mathematical model for treatment-resistant mutations of HIV. Mathematical Biosciences & Engineering, 2005, 2 (2) : 363-380. doi: 10.3934/mbe.2005.2.363 [7] Alex John Quijano, Michele L. Joyner, Edith Seier, Nathaniel Hancock, Michael Largent, Thomas C. Jones. An aggregate stochastic model incorporating individual dynamics for predation movements of anelosimus studiosus. Mathematical Biosciences & Engineering, 2015, 12 (3) : 585-607. doi: 10.3934/mbe.2015.12.585 [8] Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215 [9] Gerhard Keller. Maximal equicontinuous generic factors and weak model sets. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020132 [10] Woojoo Shim. On the generic complete synchronization of the discrete Kuramoto model. Kinetic & Related Models, 2020, 13 (5) : 979-1005. doi: 10.3934/krm.2020034 [11] Yanan Zhao, Yuguo Lin, Daqing Jiang, Xuerong Mao, Yong Li. Stationary distribution of stochastic SIRS epidemic model with standard incidence. Discrete & Continuous Dynamical Systems - B, 2016, 21 (7) : 2363-2378. doi: 10.3934/dcdsb.2016051 [12] Yixiang Wu, Necibe Tuncer, Maia Martcheva. Coexistence and competitive exclusion in an SIS model with standard incidence and diffusion. Discrete & Continuous Dynamical Systems - B, 2017, 22 (3) : 1167-1187. doi: 10.3934/dcdsb.2017057 [13] Abba B. Gumel, Baojun Song. Existence of multiple-stable equilibria for a multi-drug-resistant model of mycobacterium tuberculosis. Mathematical Biosciences & Engineering, 2008, 5 (3) : 437-455. doi: 10.3934/mbe.2008.5.437 [14] Marco Abate, Francesca Tovena. Formal normal forms for holomorphic maps tangent to the identity. Conference Publications, 2005, 2005 (Special) : 1-10. doi: 10.3934/proc.2005.2005.1 [15] Mohamed Baouch, Juan Antonio López-Ramos, Blas Torrecillas, Reto Schnyder. An active attack on a distributed Group Key Exchange system. Advances in Mathematics of Communications, 2017, 11 (4) : 715-717. doi: 10.3934/amc.2017052 [16] Abbas Bahri. Attaching maps in the standard geodesics problem on $S^2$. Discrete & Continuous Dynamical Systems - A, 2011, 30 (2) : 379-426. doi: 10.3934/dcds.2011.30.379 [17] Heikki Haario, Leonid Kalachev, Marko Laine. Reduction and identification of dynamic models. Simple example: Generic receptor model. Discrete & Continuous Dynamical Systems - B, 2013, 18 (2) : 417-435. doi: 10.3934/dcdsb.2013.18.417 [18] Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489 [19] Qun Liu, Daqing Jiang, Tasawar Hayat, Ahmed Alsaedi. Dynamical behavior of a multigroup SIRS epidemic model with standard incidence rates and Markovian switching. Discrete & Continuous Dynamical Systems - A, 2019, 39 (10) : 5683-5706. doi: 10.3934/dcds.2019249 [20] Changyou Wang, Shenzhou Zheng. Energy identity for a class of approximate biharmonic maps into sphere in dimension four. Discrete & Continuous Dynamical Systems - A, 2013, 33 (2) : 861-878. doi: 10.3934/dcds.2013.33.861

2019 Impact Factor: 0.734

## Metrics

• PDF downloads (130)
• HTML views (302)
• Cited by (0)

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]