Advanced Search
Article Contents
Article Contents
Early Access

Early Access articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Early Access publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Early Access articles via the “Early Access” tab for the selected journal.

# A multivariate identity-based broadcast encryption with applications to the internet of things

The work is supported by DRDO, India (ERIP/ER/202005001/M/01/1775)
• When Kevin Ashton proposed the catchword 'Internet of Things' in 1999, little did he know that technology will become an indispensable part of human lives in just two decades. In short, the Internet of Things (IoT), is a catch-all terminology used to describe devices connected to the internet. These devices can share and receive data as well as provide instructions over a network. By design itself, the IoT system requires multicasting data and information to a set of designated devices, securely. Taking everything into account, Broadcast Encryption (BE) seems to be the natural choice to address the problem. BE allows an originator to broadcast ciphertexts to a big group of receivers in a well-organized and competent way, while ensuring that only designated people can decrypt the data. In this work, we put forward the first Identity-Based Broadcast Encryption scheme based on multivariate polynomials that achieves post-quantum security. Multivariate public key cryptosystems (MPKC), touted as one of the most promising post-quantum cryptography candidates, forms the foundation on which our scheme relies upon, which allows it to be very cost-effective and faster when implemented. In addition, it also provides resistance to collusion attack, and as a consequence our scheme can be utilized to form an efficient and robust IoT system.

Mathematics Subject Classification: Primary: 94A60; 68M12; 68P25; 68P30.

 Citation:

• Table 1.  Proposed practical parameters for ${\sf MulIB-BE}$ [26]

 Level of Security (in bit) Field ($\mathbb{F}_q$) Number of equations ($m$) Number of variables ($n$) 80 $\mathbb{F}_{2^{32}}$ 112 56 $\mathbb{F}_{2^{16}}$ 200 100 $\mathbb{F}_{2^{8}}$ 264 128 90 $\mathbb{F}_{2^{32}}$ 144 72 $\mathbb{F}_{2^{16}}$ 242 121 $\mathbb{F}_{2^{8}}$ 312 153 100 $\mathbb{F}_{2^{32}}$ 180 90 $\mathbb{F}_{2^{16}}$ 288 144 $\mathbb{F}_{2^{8}}$ 364 180

Table 2.  Communication and Storage Overheads of ${\sf MulIB-BE}$

 MPK Size $m\binom{n+2}{2}\binom{N+8}{8}$ field $(\mathbb{F}_q)$ elements Ciphertext Size $m\binom{N+9}{9}+1$ field $(\mathbb{F}_q)$ elements MSK Size $[m(m+1)+ n(n+1)+m\binom{n+2}{2}]\binom{N+2}{2}$ field ($\mathbb{F}_q$) elements SK Size $[m(m+1)+ n(n+1)+m\binom{n+2}{2}]$ field ($\mathbb{F}_q$) elements

Table 3.  Time complexity of ${\sf MulIB-BE}$ for 80-bit security level over $GF(256)$

 Time (in seconds) Setup 11.91 Key Extraction 0.56 Encryption 2.17 Decryption 1.25

Table 4.  Comparison with existing schemes for $100$-bit security level

 Scheme Secret key size (in kb) Ciphertext size (in kb) Post-quantum secure ZhanoZhang-IB-BE [30] 0.375 1.25 $\times$ A-IBBE [29] 0.05 0.875 $\times$ Delerablée-IB-BE [9] 0.06 0.5 $\times$ Kim, Jongkil et al. [21] 0.06 0.5 $\times$ He, Kai et al. [20] 0.06 0.28 $\times$ ${\sf MulIB-BE}$ 21.36 7.09 $\checkmark$
•  [1] L. Bettale, J.-C. Faugëre and L. Perret, Hybrid approach for solving multivariate systems over finite fields, J. Math. Cryptology, 3 (2009), 177-197.  doi: 10.1515/JMC.2009.009. [2] A. Bogdanov, T. Eisenbarth, A. Rupp and C. Wolf, Time-area optimized public-key engines: MQ-cryptosystems as replacement for elliptic curves?, Cryptographic Hardware and Embedded Systems-CHES 2008, 5154 (2008), 45-61.  doi: 10.1007/978-3-540-85053-3_4. [3] D. Boneh, C. Gentry and B. Waters, Collusion resistant broadcast encryption with short ciphertexts and private keys, Advances in Cryptology–CRYPTO 2005, 3621 (2005), 258-275.  doi: 10.1007/11535218_16. [4] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor and B. Pinkas, Multicast security: A taxonomy and some efficient constructions, IEEE INFOCOM '99. Conference on Computer Communications. Proceedings. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. The Future is Now (Cat. No.99CH36320), IEEE, 1999. doi: 10.1109/INFCOM.1999.751457. [5] A. I.-T. Chen, M.-S. Chen, T.-R. Chen, C.-M. Cheng, J. Ding, E. L.-H. Kuo, F. Y.-S. Lee and B.-Y. Yang, SSE implementation of multivariate PKCs on modern s86 CPUs, Cryptographic Hardware and Embedded Systems - CHES 2009, (2009), 33–48. doi: 10.1007/978-3-642-04138-9_3. [6] N. T. Courtois, Efficient zero-knowledge authentication based on a linear algebra problem MinRank, Advances in Cryptology–ASIACRYPT 2001, 2248 (2001), 402-421.  doi: 10.1007/3-540-45682-1_24. [7] N. T. Courtois, A. Klimov, J. Patarin and A. Shamir, Efficient algorithms for solving overdefined systems of multivariate polynomial equations, Advances in Cryptology–EUROCRYPT 2000, 1807 (2000), 392-407.  doi: 10.1007/3-540-45539-6_27. [8] C. Delerablée, Identity-based broadcast encryption with constant size ciphertexts and private keys, Advances in Cryptology–ASIACRYPT 2007, 4833 (2007), 200-215.  doi: 10.1007/978-3-540-76900-2_12. [9] C. Delerablée, Identity-based broadcast encryption with constant size ciphertexts and private keys, Advances in Cryptology–ASIACRYPT 2007, 4833 (2007), 200-215.  doi: 10.1007/978-3-540-76900-2_12. [10] J. Ding, L. Hu, X. Nie, J. Li and J. Wagner, High order linearization equation hole attack on multivariate public key cryptosystems, Public Key Cryptography – PKC 2007, 4450 (2007), 233-248.  doi: 10.1007/978-3-540-71677-8_16. [11] J. Ding, A. Petzoldt and D. S. Schmidt, Multivariate Public Key Cryptosystems, 2$^nd$ edition, Advances in Information Security, 80. Springer, New York, 2020. doi: 10.1007/978-1-0716-0987-3. [12] Y. Dodis and N. Fazio, Public key broadcast encryption for stateless receivers, Digital Rights Management, 2696 (2002), 61-80.  doi: 10.1007/978-3-540-44993-5_5. [13] J. C. Faugére, A new efficient algorithm for computing Gröbner bases without reduction to zero ($F_5$), Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, (2002), 75–83. [14] J.-C. Faugére, A new efficient algorithm for computing Gröbner bases ($F_4$), J. Pure Appl. Algebra, 139 (1999), 61-88.  doi: 10.1016/S0022-4049(99)00005-5. [15] A. Fiat and M. Naor, Broadcast encryption, Advances in Cryptology–CRYPTO' 93, 773 (1993), 480-491.  doi: 10.1007/3-540-48329-2_40. [16] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, A Series of Books in the Mathematical Sciences, 1979. [17] M. T. Goodrich, J. Z. Sun and R. Tamassia, Efficient tree-based revocation in groups of low-state devices, Advances in Cryptology–CRYPTO 2004, 3152 (2004), 511-527.  doi: 10.1007/978-3-540-28628-8_31. [18] L. Goubin and N. T. Courtois, Cryptanalysis of the TTM cryptosystem, Advances in Cryptology–ASIACRYPT 2000, 1976 (2000), 44-57.  doi: 10.1007/3-540-44448-3_4. [19] D. Halevy and A. Shamir, The LSD broadcast encryption scheme, Advances in Cryptology–CRYPTO 2002, 2442 (2002), 47-60.  doi: 10.1007/3-540-45708-9_4. [20] K. He, J. Weng, J.-N. Liu, J. K. Liu, W. Liu and R. H. Deng, Anonymous identity-based broadcast encryption with chosen-ciphertext security, In Proceedings of the 11th ACM on Asia Conference on Computer and Communications Security, (2016), 247–255. [21] J. Kim, S. Camtepe, W. Susilo, S. Nepal and J. Baek, Identity-based broadcast encryption with outsourced partial decryption for hybrid security models in edge computing, Proceedings of the 2019 ACM Asia Conference on Computer and Communications Security, (2019), 55–66. [22] D. Naor, M. Naor and J. Lotspiech, Revocation and tracing schemes for stateless receivers, Advances in Cryptology–CRYPTO 2001, 2139 (2001), 41-62.  doi: 10.1007/3-540-44647-8_3. [23] J. Patarin, Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt'88, Advances in Cryptology–CRYPT0' 95, 963 (1995), 248-261.  doi: 10.1007/3-540-44750-4_20. [24] R. Sakai and J. Furukawa, Identity-based broadcast encryption, IACR Cryptol. ePrint Arch., 20072/17, URL http://eprint.iacr.org/2007/217. [25] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Rev, 41 (1999), 303-332.  doi: 10.1137/S0036144598347011. [26] C. Tao, H. Xiang, A. Petzoldt and J. Ding, Simple matrix–a multivariate public key cryptosystem (MPKC) for encryption, Finite Fields Appl., 35 (2015), 352-368.  doi: 10.1016/j.ffa.2015.06.001. [27] B.-Y. Yang, C.-M. Cheng, B.-R. Chen and J.-M. Chen, Implementing minimized multivariate PKC on low-resource embedded systems,, Security in Pervasive Computing, Springer Berlin Heidelberg, 3934 (2006), 73–88. doi: 10.1007/11734666_7. [28] T. Yasuda, X. Dahan, Y.-J. Huang, T. Takagi and K. Sakurai, MQ Challenge: Hardness Evaluation of Solving Multivariate Quadratic Problems, Cryptology ePrint Archive, Report, 2015/275, 2015, https://eprint.iacr.org/2015/275. [29] Z. Zhao, F. Guo, J. Lai, W. Susilo, B. Wang and Y. Hu, Accountable authority identity-based broadcast encryption with constant-size private keys and ciphertexts, Theoret. Comput. Sci., 809 (2020), 73-87.  doi: 10.1016/j.tcs.2019.11.035. [30] X. Zhao and F. Zhang, Fully CCA2 secure identity-based broadcast encryption with black-box accountable authority, Journal of Systems and Software, 85 (2012), 708-716.

Tables(4)

## Article Metrics

HTML views(537) PDF downloads(546) Cited by(0)

## Other Articles By Authors

• on this site
• on Google Scholar

### Catalog

/

DownLoad:  Full-Size Img  PowerPoint