Advanced Search
Article Contents
Article Contents

Quantum-safe identity-based broadcast encryption with provable security from multivariate cryptography

Ψ The author is currently affiliated at the Department of Computer Science and Engineering, National Sun Yat-sen University

This work is supported by the University Grants Commission, Government of India under Grant No. 1228/(CSIRNETJUNE-2019); Ministry of Science and Technology of Taiwan under Grant No. MOST 111-2811-E-110-001; and Science and Engineering Research Board (SERB), Department of Science and Technology (DST), Government of India under Grant No. EMR/2017/002214

Abstract Full Text(HTML) Figure(2) / Table(4) Related Papers Cited by
  • Identity-Based Broadcast Encryption ($\textsf{IBBE}$) is a novel concept that can efficiently and securely transmit confidential content to a group of authorized users without the traditional Public-Key Infrastructure ($\textsf{PKI}$). After carefully exploring these areas, we have observed that none of the existing works have adopted the quantum-attack resistant cryptographic machinery Multivariate Public-Key Cryptography ($\textsf{MPKC}$) with provable security. We are the first to design a quantum-safe $\textsf{IBBE}$ that solely relies on the $\textsf{MPKC}$ framework. Our proposed protocol has achieved $ \mathcal{O}(n) $-size communication bandwidth and $ {n^3}\cdot\mathcal{O}\big(\max\big\{N, {\delta}^4\big\}\big) $-size overhead storage without any security breach. Here, $ n $ is the number of variables for each multivariate polynomial, $ N $ represents the total number of system users, and $ \delta $ denotes a positive fixed-length. More positively, our design has achieved the adaptive INDistinguishable Chosen-Ciphertext Attack ($\textsf{IND-CCA}$) security in the Random Oracle Model ($\textsf{ROM}$) under the hardness of standard Multivariate Quadratic ($\textsf{MQ}$) problem. We emphasize that our system can also be immune against collusion attacks where several users come together to create an illicit decryption box.

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


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  System model of $\textsf{IBBE-MPKC}$

    Figure 2.  Flow diagram of our proposed $\textsf{IBBE-MPKC}$

    Table 1.  Notations

    Symbol Description
    $ \eta $ Security parameter of the system
    $ \perp $ Null string
    $ ID_u $ Identity for the user $ u $
    $ |M| $ Length of a message $ M $
    $ I_S $ The index set for a set $ S $
    $ |S| $ Cardinality of a set $ S $
    $ [N] $ $ \{1, 2, \ldots, N\} $
    $ \delta $$ \in_R $ $ \{0, 1\} $ Bit $ \delta $ is chosen randomly from the set $ \{0, 1\} $
    $\textsf{IND-ID-CCA}$ Indistinguishability under identity chosen-ciphertext attack
     | Show Table
    DownLoad: CSV

    Table 2.  Comparison of communication bandwidth and storage overhead

    $\textsf{Schemes}$ $\textsf{Communication Bandwidth}$ $\textsf{Storage Overhead}$
    $\textsf{MPK}$ $\textsf{MSK}$ $\textsf{SKey}_\textsf{u}$
    Srivastava et al. [23] $n{{N+9}\choose 9}+1$ $n{n+2 \choose 2}{N+8 \choose 8}$ $\big(2n(n+1)$
    +$n{n+2 \choose 2}\big){N+2 \choose 2}$
    $+n{n+2 \choose 2}$
    Our Scheme $n$ $n{n+2 \choose 2}{\delta+4 \choose 4}$ $(n+4)\delta{n+1 \choose 2}$ $(n+4)N{n+1 \choose 2}$
    $\textsf{MPK}$= master-public key, $\textsf{MSK}$= master-secret key, $\textsf{SKey}_\textsf{u}$= secret-key of a user, $n$= the number of variables, $N$= the total number of users in the system, $\delta \le N$= a positive integer
     | Show Table
    DownLoad: CSV

    Table 3.  Comparison of security and other functionalities

    $\textsf{Scheme}$ $\textsf{Encryption Technique}$ $\textsf{Security}$ $\textsf{IBE}$
    $\textsf{Provable Security Model}$ $\textsf{Assumption}$
    Srivastava et al. [23] $\textsf{KEM}$ × $\textsf{MQ Problem}$
    Our scheme $\textsf{DEM}$ Adaptive $\textsf{IND-CCA}$ $\textsf{MQ Problem}$
    $\textsf{KEM}$= Key Encapsulation Mechanism, $\textsf{DEM}$= Data Encapsulation Mechanism, $\textsf{IBE}$= Identity-based Encryption, $\textsf{MQ}$= Multivariate Quadratic, $\textsf{IND-CCA}$= Indistinguishable Chosen-Ciphertext Attack
     | Show Table
    DownLoad: CSV

    Table 4.  Comparison of computation costs

    $\textsf{Scheme}$ $\textsf{Encryption Cost}$ $\textsf{Decryption Cost}$
    $\textsf{#M}$ $\textsf{#A}$ $\textsf{#M}$ $\textsf{#I}$
    Srivastava et al. [23] $ nN{N+8 \choose 8}\big[n+N{n+2 \choose 2}\big] $ $ n $ n$ \sum_{i=1}^{9}i{N+i-1 \choose i} $ 0
    Our Scheme $ Nn\big[{n+2 \choose 2 }\sum_{i=1}^{4}{\delta+i-1 \choose i}+ {n+1 \choose 2}\big] $ $ 0 $ $ 2nN^2 $ $ N $
    $\textsf{#M}$ = cost of modular multiplication over finite field, $\textsf{#A}$= cost of modular addition over finite field, $\textsf{#I}$= cost to invert a function over a finite field.
     | Show Table
    DownLoad: CSV
  • [1] S. Agrawal, D. Wichs and S. Yamada, Optimal broadcast encryption from LWE and pairings in the standard model, Theory of Cryptography Conference, Springer, Cham, 12550 (2020), 149–178. doi: 10.1007/978-3-030-64375-1_6.
    [2] S. Agrawal and S. Yamada, Optimal broadcast encryption from pairings and LWE, Advances in Cryptology, Springer, Cham, 12105 (2020), 13–43. doi: 10.1007/978-3-030-45721-1_2.
    [3] D. BeckmanA. ChariS. Devabhaktuni and J. Preskill, Efficient networks for quantum factoring, Phys. Rev. A, 54 (1996), 1034-1063.  doi: 10.1103/PhysRevA.54.1034.
    [4] A. Bogdanov, T. Eisenbarth, A. Rupp and C. Wolf, Time-area optimized public-key Engines: $\textsf{MQ}$- Cryptosystems as Replacement for elliptic curves?, Cryptographic Hardware and Embedded Systems - CHES 2008, LNCS, Springer, Berlin, Heidelberg, 5154 (2008), 45–61. doi: 10.1007/978-3-540-85053-3_4.
    [5] D. Boneh, C. Gentry and B. Waters, Collusion resistant broadcast encryption with short ciphertexts and private keys, Annual International Cryptology Conference, Springer, Berlin, 3621 (2005), 258–275. doi: 10.1007/11535218_16.
    [6] D. Boneh and B. Waters, A fully collusion resistant broadcast, trace, and revoke system, In Proceedings of the 13th ACM Conference on Computer and Communications Security, (2006), 211–220.
    [7] Z. Brakerski and V. Vaikuntanathan, Lattice-inspired broadcast encryption and succinct ciphertext-policy ABE, IACR Cryptol. ePrint Arch., (2020), 191.
    [8] A. I. Chen, M. Chen, T. Chen, C. Cheng, J. Ding, E. L. Kuo, F. Y. Lee and B. Yang, SSE Implementation of Multivariate PKCs on Modern x86 CPUs, Cryptographic Hardware and Embedded Systems - CHES 2009, LNCS, Springer, Berlin, Heidelberg, 5747 (2005), 33–48. doi: 10.1007/978-3-642-04138-9_3.
    [9] C. Delerablée, Identity-based broadcast encryption with constant size ciphertexts and private keys, Advances in Cryptology, Springer, Berlin, 4833 (2007), 200–215. doi: 10.1007/978-3-540-76900-2_12.
    [10] J. Ding, A. Petzoldt and D. S. Schmidt, Multivariate Public Key Cryptosystems, 2$^{nd}$ edition, Advances in Information Security, Springer, New York, 2020. doi: 10.1007/978-1-0716-0987-3.
    [11] Y. Dodis and N. Fazio, Public key broadcast encryption for stateless receivers, Digital Rights Management, 2696 (2021), 61-80.  doi: 10.1007/978-3-540-44993-5_5.
    [12] X. DuY. WangJ. Ge and Y. Wang, An ID-based broadcast encryption scheme for key distribution, IEEE Transactions on Broadcasting, 51 (2005), 264-266.  doi: 10.1109/TBC.2005.847600.
    [13] A. Fiat and M. Naor, Broadcast encryption, Annual International Cryptology Conference, Springer, Berlin, Heidelberg, (1993), 480–491. doi: 10.1007/3-540-48329-2_40.
    [14] 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.
    [15] J. Herranz, D. Hofheinz and E. Kiltz, KEM/DEM: Necessary and sufficient conditions for secure hybrid encryption, IACR Cryptol. ePrint Arch., 2006/265.
    [16] K. JongkilW. SusiloM. H. Au and J. Seberry, Adaptively secure identity-based broadcast encryption with a constant-sized ciphertext, IEEE Transactions on Information Forensics and Security, 10 (2015), 679-693.  doi: 10.1109/TIFS.2014.2388156.
    [17] W. Nagao, Y. Manabe and T. Okamoto, A universally composable secure channel based on the KEM-DEM framework, Theory of Cryptography, Springer, Berlin, 3378 (2005), 426–444. doi: 10.1007/978-3-540-30576-7_23.
    [18] D. NaorM. Naor and J. Lotspiech, Revocation and tracing schemes for stateless receivers, Advances in Cryptology, 2139 (2001), 41-62.  doi: 10.1007/3-540-44647-8_3.
    [19] O. Ore, On a special class of polynomials, Trans. Amer. Math. Soc., 35 (1933), 559-584.  doi: 10.1090/S0002-9947-1933-1501703-0.
    [20] O. Ore, Contributions to the theory of finite fields, Trans. Amer. Math. Soc., 36 (1934), 243-274.  doi: 10.1090/S0002-9947-1934-1501740-7.
    [21] R. Sakai and J. Furukawa, Identity-based broadcast encryption, IACR Cryptol. ePrint Arch., 20072/17.
    [22] W. P. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE, (1994), 124–134. doi: 10.1109/SFCS.1994.365700.
    [23] V. Srivastava, S. K. Debnath, P. Stanica and S. K. Pal, A multivariate identity-based broadcast encryption with applications to the internet of things, Advances in Mathematics of Communications, 2021. doi: 10.3934/amc.2021050.
    [24] B. Yang, C. Cheng, B. Chen and J. Chen, Implementing minimized multivariate PKC on low-resource embedded systems, International Conference on Security in Pervasive Computing, Springer, Berlin, Heidelberg, 3934 (2006), 73–81. doi: 10.1007/11734666_7.
    [25] H. YuS. FuY. Liu and S. Zhang, Certificateless broadcast multisignature scheme based on MPKC, IEEE Access, 8 (2020), 12146-12153.  doi: 10.1109/ACCESS.2020.2965978.
  • 加载中




Article Metrics

HTML views(3284) PDF downloads(858) Cited by(0)

Access History



    DownLoad:  Full-Size Img  PowerPoint