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

Ramprasad Sarkar; Mriganka Mandal; Sourav Mukhopadhyay

doi:10.3934/amc.2022026

Article Contents

2022. Doi: 10.3934/amc.2022026

Previous Article Next Article

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.

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

1.
Department of Mathematics, Indian Institute of Technology Kharagpur, Kharagpur, India- 721302
2.
^ΨDepartment of Computer Science and Engineering, National Sun Yat-sen University, 70, Lienhai Road, Kaohsiung, Taiwan- 80424
3.
Institute of Mathematics for Industry, Kyushu University, 744 Motooka, Nishi-ku, Fukuoka, Japan- 8190395
4.
R. C. Bose Centre for Cryptology and Security, Indian Statistical Institute, 203 B. T. Road, Kolkata, India- 700108

^*Corresponding author: rpsarkar@iitkgp.ac.in
^*Corresponding author: rpsarkar@iitkgp.ac.in

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

Received: November 30, 2021

Revised: February 28, 2022

Early access: April 2022

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

Abstract

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.

Keywords:

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

Citation:

FullText(HTML)

Figure 1. System model of $\textsf{IBBE-MPKC}$

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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{Schemes}$	$\textsf{Communication Bandwidth}$	$\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}$	$2n(n+1)$ $+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{Scheme}$	$\textsf{Encryption Technique}$	$\textsf{Provable Security Model}$	$\textsf{Assumption}$	$\textsf{IBE}$
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{Scheme}$	$\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

Related Papers

Cited by

References

[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. 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. doi: 10.1007/978-3-030-45721-1_2.
[3]	D. Beckman, A. Chari, S. 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. 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. 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. 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. 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. 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. Du, Y. Wang, J. 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. 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. Jongkil, W. Susilo, M. 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. doi: 10.1007/978-3-540-30576-7_23.
[18]	D. Naor, M. 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. 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. 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. doi: 10.1007/11734666_7.
[25]	H. Yu, S. Fu, Y. Liu and S. Zhang, Certificateless broadcast multisignature scheme based on MPKC, IEEE Access, 8 (2020), 12146-12153. doi: 10.1109/ACCESS.2020.2965978.