Identity-based key aggregate cryptosystem from multilinear maps

Sikhar Patranabis; Debdeep Mukhopadhyay

doi:10.3934/amc.2019044

Article Contents

2019, Volume 13, Issue 4: 759-778. Doi: 10.3934/amc.2019044

This issue Previous Article The secure link prediction problem Next Article Cryptographically significant mds matrices over finite fields: A brief survey and some generalized results

Identity-based key aggregate cryptosystem from multilinear maps

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

Received: September 30, 2018

Revised: February 28, 2019

Published: June 2019

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 11T71, 68P25, 94A60; Secondary: 68R01.

Citation:

Full Text(HTML)

Table 1. 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 $

| Show Table

DownLoad: CSV

Table 2. 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 $

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.
[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.
[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.
[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.
[5]	D. Boneh, D. J. Wu and J. Zimmerman, Immunizing multilinear maps against zeroizing attacks, IACR Cryptology ePrint Archive, 2014 (2014), 930.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[15]	D. Moshkovitz, An alternative proof of the schwartz-zippel lemma., in Electronic Colloquium on Computational Complexity (ECCC), 17 (2010), 34.
[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.
[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.
[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.