Anonymous Identity Based Broadcast Encryption against Continual Side Channel Attacks in the State Partition Model

Abstract

In the past 10 years, many side-channel attacks have been discovered and exploited one after another by attackers, which have greatly damaged the security of cryptographic systems. Since no existing anonymous broadcast encryption scheme can resist the side-channel attack, the paper presents an anonymous identity-based broadcast encryption against continual side-channel attacks in the state partition model (CLR-SS-AIBBE). Based on split-state technology, the proposed scheme divides the private key into two states, and the decryption operations are correspondingly divided into two steps. Based on the three static hypotheses for a bilinear group with composite order, the proposed scheme can be proved to be fully secure by the dual system encryption technology in the standard model. The leakage ratio about the private key can reach 1/3.

1. Introduction

In the past 10 years, cryptography has made great progress in expanding the adversary model to cover side-channel attacks [1,2,3,4], and researchers have built some provably secure cryptographic schemes that can resist some side-channel attacks. In most theoretical work, it is assumed that the participants have complete confidentiality to their local computation. The attacker may only obtain the signature of the selected plaintext or the decryption of the selected ciphertext, but it is usually assumed that the signature or encryption process itself is completely secret to the adversary. In particular, theoretically, the related information of the private key that an adversary can obtain is only contained in a clear boundary, such as signature or decryption. Such adversaries are sometimes called “black box” attackers. Goldwasser and Micali pioneered work for modern cryptography. Based on some computational complexity assumptions, they proved the security of many cryptographic schemes under the black box model, such as encryption [5], signature [6] and the zero-knowledge proof [7].

However, real attackers do not always follow such clear boundaries. Various successful side-channel attacks have proven that the key information and internal state information related to the specific calculation may be leaked to a certain adversary. Since each cryptographic algorithm is ultimately implemented on the physical platform, it will inevitably affect the surrounding environment in a measurable way. The side-channel attack obtains secret information about the cryptographic system by measuring the surrounding environment of the machine that is executing the related algorithms. For example, an attacker obtains the relevant confidential information of the cryptographic system by measuring and analyzing the time [4] or the electromagnetic radiation [8] of the specific algorithm. Through the “cold start” attack [9], if an adversary can access the corresponding physical device, it can recover part of the key of the cryptographic system even when the power has just been cut off. Side-channel attacks [10,11] allow processes to violate isolation boundaries and read information from other processes on the same machine. In other words, the real attacker may not be the black box.

The emergence of side-channel attacks leads cryptographers to reevaluate the black box model and create new adversary models and provable security schemes. This work is called leakage-resilient cryptography.

As leakage-resilient cryptography is a relatively young research direction of cryptography, the theory and practice of leakage-resilient cryptography have made remarkable achievements in the past decade.

2. Related Work and Our Motivations

2.1. Leakage-Resilient Cryptography

Leakage-resilient (LR) cryptosystems are the cryptographic systems that are secure against side-channel attacks. The attack capability depends on specific limitations, which are usually abstracted as a leak function in the security model. According to different restrictions on the leakage function, the current leakage-resilient cryptography models are mainly as follows.

(1)

“Only calculation leaks”

Micali et al. [12] proposed the concept of “only calculation leaks” (OCL): it is required that the leakage can only occur in the computing portion, so the portion that does not participate in the computing does not leak information. The total leakage amount and the leakage function form are not limited. In this model, Dziembowski et al. [13] proposed a secure stream cipher scheme. Goldwasser et al. [14] constructed one time scheme, which was later widely used in other schemes.

(2)

Bounded-leakage model

For a cold start attack, even parts that do not participate in the computation can leak information. To solve this problem, Akavia et al. [15] gave the concept of bounded-leakage model (BLM). It is required that the leakage function has a bounded output. Naor et al. [16] extended the concept of bounded leakage and presented the entropy-bounded-leakage model. There is no requirement on the output length about the leakage function, only that the system’s secret information derived from the leakage function has a bounded entropy loss.

Akavia et al. [15] gave a specific public key encryption (PKE) scheme and an identity-based encryption scheme, which are leakage-resilient. Naor et al. [16] used the hash proof system (HPS) to obtain an encryption scheme with chosen plaintext attack (CPA) security and an encryption scheme with chosen ciphertext attack (CCA2) security, which resist side-channel attacks. The leakage rate of the private key for their scheme with CCA2 security can only reach one-sixth. Luo et al. [17] proposed a lattice-based PKE scheme. The paper [18] presented an effective LR PKE. The work [19] used anonymous HPS to construct an anonymous LR PKE. Li et al. [20] gave an efficient leakage-resilient identity-based encryption scheme.

Following the basic requirement of the “only calculation leaks” model and bounded-leakage model, Prouf et al. [21] introduced the noise-leakage model, which can capture the power consumption and electromagnetic leakage well. Duc et al. [22] proposed the random detection model, which includes noise leakage.

Unlike the construction of LR cryptosystems through specific number theory and algebraic hypothesis, Hazay et al. [23] constructed LR PKE schemes through any standard PKE under general and minimum assumptions. Only if a one-way function exists, then they can construct LR symmetric key encryption, etc.

Galindo et al. [24] weakened the limitations on the leakage function and only required that the output of the leakage function has sufficient minimum entropy. What is more, they did not limit the amount of leakage. The safety of their scheme was proven by using the general bilinear group theory. They proposed a scheme that was easily implemented by coding technology, and the scheme was implemented by software based on the MIRACL library.

Genkin et al. [25] designed hardware devices for the zero-knowledge proof and general multiparty computation. This construction can unconditionally capture the “only calculation leaks” of the real side-channel attack. They provided different tradeoffs between efficiency and security.

(3)

Continual leakage model

When the side-channel attack continues, the leakage may gradually increase and eventually exceed the given limit. BLM cannot solve this problem. Both refs. [26,27], respectively, presented the concept of the continuous-leakage model (CLM). Their main idea is to refresh the secret key periodically. The restrictions are that the leakage is bounded between two consecutive updates. The leakage of the whole process can be unlimited. The paper [28] gives a dynamic secret-sharing scheme with continual leakage resilience by using the state partition technique. The paper [29] proposed a hierarchical attribute-based encryption that resists a continuous-leakage attack.

The relationship about the three leakage models is given in Figure 1.

The “only calculation leaks” model allows information leakage only in the part currently performing the calculation of a cryptographic system. If we consider that there may be information leakage in the part that does not participate in calculation, the bounded-leakage model can solve the problem. In order to solve the problem that the leaked information will gradually exceed the given limit, given that it is necessary to update the key periodically, the continuous-leakage model is produced.

2.2. Identity-Based Broadcast Encryption

Ref. [30] provided the broadcast encryption (BE) scheme. From then on, many BE schemes have been proposed [31,32,33]. Broadcast encryption is widely used to multicast communication, copyright management, et al. For example, to solve the redundancy problem in information transmission for the vehicular ad hoc network, Zhong et al. [34] used broadcast encryption as the secure data sharing scheme from vehicle to infrastructure communication mode.

Ref. [35] constructed the first identity-based BE (IBBE) under the random oracle model (ROM). Since then, scholars have conducted in-depth research on IBBE from the aspects of efficiency and special performance, obtaining many achievements. Ren et al. [36] designed an IBBE scheme and proved its security in the standard model (STDM). In their proposed scheme, the length of ciphertext and public key are fixed. Zhang et al. [37] gave an IBBE in STDM and proved its security with dual-system technology. Their scheme has a fixed private key and ciphertext length. The anonymous IBBE constructed by Libert et al. [38] has a ciphertext that is not fixed in length and is positively related to the number of recipients.

The anonymous IBBE given by Zhang et al. [39] has a fixed ciphertext length, but the key is too long. The scheme is provably safe under STDM through dual-system technology. Li et al. [40] gave an anonymous certificate-based broadcast encryption. Lai et al. [41] gave an IBBE from inner products with fixed private key length, which supported infinite private key query in ROM. Jiang et al. [42] proposed an efficient IBBE with keyword search in cloud computing. It provides data retrieval and resists internal attack. Zhao et al. [43] presented a weak black box IBBE scheme in ROM, which has fixed private key size and public traceability for ciphertext. The tracking was performed through employing a public key of some suspicious user instead of its private key. Chen et al. [44] gave an efficient identity based anonymous broadcast encryption for cloud storage services, which has a fixed size for its public parameters, private key and ciphertext.

2.3. Our Motivations

Xiong et al. [28] presented a secret-sharing scheme that can resist side-channel attacks by the split-state technology. Since then, state partition technology has been gradually used to construct some cryptographic schemes with special performance. Liu et al. [45] ensured the security of their scheme in the case of continuous state partition leakage and tamper attacks from an algorithmic point of view by means of general reference string and nonmalleable code.

Faonio et al. [46] divided the code into two parts. By using a refresh process based on state division, non-extensible code has the ability to resist persistent leakage attacks. In these schemes based on state division technology, the state is usually divided into two parts. The state is sometimes divided into four or eight parts [47,48].

Since dual-system technology [49] was used to prove the security for cryptosystems, a lot of work has been carried out along this line. In view of bilinear groups with composite order, the orthogonality of subgroup elements can be fully utilized to carry effective information and hide invalid information. It is usually used to finish the security proof in combination with dual-system encryption technology. Refs. [50,51,52] achieve some schemes with leakage resilience through dual-system technology.

For the anonymous broadcast encryption, there is no leakage-resilient scheme at present. On the basis of the reference [53], we present an anonymous broadcast encryption scheme against the continuous leakage of a private key.

2.4. Our Contributions

We put forward an anonymous IBBE against a continual-leakage attack. First, for the first time, we use state division technology to obtain the leakage resilience of a broadcast encryption scheme. The main advantage is that it can ensure that the scheme has the ability to resist side-channel attacks and has relatively high computational efficiency at the same time. The computational efficiency is also one of the important considerations of the cryptographic scheme. Second, the scheme has anonymity, which protects the privacy of users. For example, for a health diagnosis and treatment system based on cloud storage, if the data owner (a hospital) wants to encrypt the data about coronary heart disease in the Department of Cardiology for the relevant patients, if there is no anonymity, a bystander can infer that a user accessing this data is suffering from heart disease. Thus, the identity information of the user is virtually leaked. Therefore, anonymity is also a very important aspect. In fact, ref. [53] provided an anonymous broadcast encryption. Although its efficiency is considered, a side-channel attack is not considered. Thirdly, our scheme has a good ability to resist a side-channel attack. The side-channel attack is a new cryptosystem attack form in the past 10 years. Therefore, if the designed cryptographic algorithm can capture the side-channel attacks, the security for the cryptographic scheme is better.

Figure 2 shows a whole framework about an anonymous leakage-resilient IBBE for cloud services. The system involves four entities: private key generator (PKG), cloud storage server (CSS), data user (DU) and data owner (DO). The PKG offers private keys for all DUs based on DUs’ identities. The PKG sends the system’s parameters to the DO and DU. The DO will authorize the data user in the target set as the receiver and encrypt the symmetric encryption key through anonymous IBBE. The DO encrypts its information by the session key and places the ciphertext on CSS. The symmetric encryption key is broadcast by the data owner to the target user set. The target user decrypts the ciphertext with their private key and obtains a symmetric encryption key. Next, the target user decrypts the ciphertext with the symmetric encryption key. In this process, the user cannot obtain the information of other users, so the system has anonymity.

3. Related Knowledge

We give some notations in

Table 1. Some notations.

Notation	Description
$G_1$$,G_2$	Cyclic groups
$N=w_1{w}_2{w}_3$	$\mathrm{Order}\mathrm{of}{G}_1$$\mathrm{and}{G}_2$
$\Phi$	Bilinear group generation algorithm
$G_{w_1}$$,G_{w_2}$$,G_{w_3}$	$\mathrm{Subgroups}\mathrm{of}{G}_1$$\mathrm{for}\mathrm{order}{w}_1,w_2$$\mathrm{and}{w}_3$
$\varpi$	Safety parameter
$X_1$	$\mathrm{Random}\mathrm{value}\mathrm{of}{G}_{w_1}$
$X_2,Y_2,Z_2$	$\mathrm{Random}\mathrm{values}\mathrm{of}{G}_{w_2}$
$X_3,Y_3$	$\mathrm{Random}\mathrm{values}\mathrm{of}{G}_{w_3}$
$MP$	Public parameters
$MK$	Master private key
$S{K}_{ID,k}$	$\mathrm{Private}\mathrm{key}\mathrm{for}\mathrm{identity}ID$
$S{K}_{ID,k+1}$	Updated private key
$M$	A plaintext
$CT$	A ciphertext
$\mathcal{A}$	An adversary
$ℬ$	A challenger
$L_{SK}$	Bound for private key leakage
${\mathrm{EX}}_{\mathrm{R}}$	Real security game

and give the preliminaries that will be used in the paper.

3.1. Bilinear Group

Definition 1. 

Suppose that $G_1$and $G_2$ are multiplicative cyclic group with order $N$. Suppose that $a$ is a generator of group $G_1$. A map $e:G_1\times G_1\to G_2$ is called as bilinear map, if it satisfies the conditions as follows.

(1) 

Bilinearity:  $\forall a,b\in G_1$ and for $\forall u,v\in Z^{*}$, it holds that $e(a^u,b^v)=e{(a,b)}^{uv}$.

(2) 

Non degeneracy:  $\forall a,b\in G_1$, $e(a,b)\ne 1_{G_2}$.

(3) 

Computability: There is an effective algorithm to calculate  $e(a,b)$.

3.2. Composite Order Bilinear Groups

Ref. [54] put forward the concept of composite order bilinear groups. Let $\Phi$ represent a bilinear group generation algorithm. Taking the safety parameters $\varpi$ as inputs, $\Phi$ can produce a bilinear group with composite order $\Omega =\{N=w_1{w}_2{w}_3,G_1,G_2,e\}$. $w_1$, $w_2$ and $w_3$ are three different primes with $\theta$ bits (that is, ${\log }_2^{w_1}={\log }_2^{w_2}$$={\log }_2^{w_3}=\theta$). $G_1$ is a cyclic group with order $N=w_1{w}_2{w}_3$, so is $G_2$. $e$ is a bilinear map that maps $G_1\times G_1$ to $G_2$. $\theta$ is determined by safety parameter $\varpi$.

Let $G_{w_1},G_{w_2}$ and $G_{w_3}$ denote the subgroups of order $w_1$, $w_2$ and $w_3$, respectively, in the group $G_1$. Let $G_{w_1{w}_2}$ denote the subgroup of order $w_1{w}_2$ in $G_1$. If an element $Y$ can be written as the product of an element in $G_{w_1}$ and an element in $G_{w_2}$, then these two parts are called the part $G_{w_1}$ of $Y$ and the part $G_{w_2}$ of $Y$, respectively. Assuming that $p_i\in G_{w_i}$ and $p_j\in G_{w_j}$ ($i\ne j$), we can acquire $e(p_i,p_j)$ = 1. So, $G_{w_i}$ and $G_{w_j}$ are orthogonal. For example, $G_{w_1}$ and $G_{w_2}$ are orthogonal. Suppose $g$ is a generator of $G_1$, $g^{w_1{w}_2}$ is a generator of $G_{w_3}$, $g^{w_1{w}_3}$ is a generator of $G_{w_2}$, and $g^{w_2{w}_3}$ is a generator of $G_{w_1}$. Then, there are ${\alpha }_1$ and ${\alpha }_2$, such that $p_1={(g^{w_2{w}_3})}^{{\alpha }_1}$ and $p_2={(g^{w_1{w}_3})}^{{\alpha }_2}$. Therefore, $e(p_1,p_2)$ $=e(g^{w_2{w}_3{\alpha }_1},g^{w_1{w}_3{\alpha }_2})$$=e{(g^{{\alpha }_1},g^{w_3{\alpha }_2})}^{w_1{w}_2{w}_3}=1$. So, $G_{w_1}$ and $G_{w_2}$ are orthogonal.

Three assumptions [49,51] are given below. Suppose $g_i$ is the generator of $G_{w_i}$.

Assumption 1. 

Let $\Phi$generate a bilinear group. Given the following distribution:

$\Omega =\{N=w_1{w}_2{w}_3,G_1,G_2,e\}\stackrel{R}{\leftarrow }\Phi$,$g_1\stackrel{R}{\leftarrow }{G}_{w_1},X_3\stackrel{R}{\leftarrow }{G}_{w_3}$,$U=(\Omega ,g_1,X_3)$. No adversary can distinguish$T_1\in G_{w_1{w}_2}$from$T_2\in G_{w_1}$.

The superiority that one adversary destroys Assumption 1 is denoted by $Ad{v}_{\psi ,\mathcal{A}}(\varpi )=|\mathrm{Su}[\mathcal{A}(U,T_1)=1]-\mathrm{Su}[\mathcal{A}(U,T_2)=1]|$.

If $Ad{v}_{\psi ,\mathcal{A}}(\varpi )$ can be ignored, Assumption 1 is considered valid.

Assumption 2. 

Let $\Phi$generate a bilinear group. Given the following distribution:

$\Omega =\{N=w_1{w}_2{w}_3,G_1,G_2,e\}\stackrel{R}{\leftarrow }\Phi$,$X_1,g_1\stackrel{R}{\leftarrow }{G}_{w_1}$,$X_2,Y_2\stackrel{R}{\leftarrow }{G}_{w_2}$,$X_3,Y_3\stackrel{R}{\leftarrow }{G}_{w_3}$,$U=(\Omega ,g_1,X_1{X}_2,X_3,Y_2{Y}_3)$. No adversary can distinguish$T_1\in G$from$T_2\in G_{w_1{w}_3}$.

The superiority that one adversary destroys Assumption 2 is denoted by $Ad{v}_{\psi ,\mathcal{A}}(\varpi )=|\mathrm{Su}[\mathcal{A}(U,T_1)=1]-\mathrm{Su}[\mathcal{A}(U,T_2)=1]|$.

If $Ad{v}_{\psi ,\mathcal{A}}(\varpi )$ can be ignored, Assumption 2 is considered valid.

Assumption 3. 

Let$\Phi$generate a bilinear group. Given the following distribution:

$\Omega =\{N=w_1{w}_2{w}_3,G_1,G_2,e\}\stackrel{R}{\leftarrow }\Phi ,\hspace{1em}\alpha ,s\stackrel{R}{\leftarrow }{Z}_N$,$g_1\stackrel{R}{\leftarrow }{G}_{w_1},X_2,Y_2,Z_2\stackrel{R}{\leftarrow }{G}_{w_2}$,$X_3\stackrel{R}{\leftarrow }{G}_{w_3}$,$U=(\Omega ,g_1,g_1^{\alpha }{X}_2,X_3,g_1^s{Y}_2,Z_2)$. No adversary can distinguish$T_1\stackrel{R}{\leftarrow }e{(g_1,g_1)}^{\alpha s}$from$T_2\stackrel{R}{\leftarrow }{G}^{\prime }$.

The superiority that one adversary destroys Assumption 3 is denoted by $Ad{v}_{\psi ,\mathcal{A}}(\varpi )=|\mathrm{Su}[\mathcal{A}(U,T_1)=1]-\mathrm{Su}[\mathcal{A}(U,T_2)=1]|$.

If $Ad{v}_{\psi ,\mathcal{A}}(\varpi )$ can be ignored, Assumption 3 is considered valid.

4. Syntax and Security Description of CLR-SS-AIBBE

4.1. Syntax of CLR-SS-AIBBE

Inspired by refs. [50,51,53], a formal definition of CLR-SS-AIBBE is given.

Initialization algorithm:$Start(\varpi ,l)\to (MP,MK)$. The algorithm inputs the maximum value $l$ of users and security index $\varpi$ as inputs. It generates the public parameter (or master public key), $MP$, and the master private key, $MK$. $MP$ is open to all users. $MK$ is kept as a secret.

Private key generation algorithm:$KeyGen(MP,MK,ID)\to S{K}_{ID}$. The algorithm inputs $MP$, $MK$ and one user’s identity $ID$. It obtains the user’s private key $S{K}_{ID}=(S{K}_{ID,0,1},S{K}_{ID,0,2})$.

Private key updation algorithm:$KeyUpd(MP,S{K}_{ID,k})\to S{K}_{ID,k+1}$. It inputs $S{K}_{ID,k}$ and $MP$. It obtains a new private key $S{K}_{ID,k+1}$.

Encryption algorithm:$Encrypt(MP,M,S)\to CT$. The algorithm inputs $MP$, the message $M$ and an identity set $S=\{I{D}_1,\dots ,I{D}_d\}$ ($d\le l$) and obtains $(Hdr,CK)$, where $CK$ is a symmetric key, and $Hdr$ is called the header. When the broadcaster is going to send the ciphertext of the message, $M$, to the users in $S$, the broadcaster obtains $C$ by encrypting the $M$ by $CK$, which generates the ciphertext $CT=(C,Hdr)$ and broadcasts $(C,Hdr,S)$.

Decryption algorithm 1:$Decrypt1(MP,S{K}_{I{D}_i,k,1},S,CT)\to C{T}^{\prime }$. The algorithm inputs the master public key $MP$, private key $S{K}_{I{D}_i,k,1}$, users’ identity set $S$ and ciphertext $CT$. First, it divides $CT$ into $(C,Hdr)$. If $I{D}_i\in S$, the algorithm uses $Hdr$ to produce some part related to the plaintext.

Decryption algorithm 2:$Decrypt2(MP,S{K}_{I{D}_i,k,2},S,C{T}^{\prime })\to M$. The algorithm inputs the master public key $MP$, private key $S{K}_{I{D}_i,k,2}$, users’ identity set $S$ and ciphertext $C{T}^{\prime }$. If $I{D}_i\in S$, it first calculates the $CK$. Then, the plaintext message is recovered by decrypting $C$.

Semi-functional private key generation algorithm:$KeyGenSF(MP,MK,ID)\to \widetilde{S{K}_{ID}}$. It inputs $MP$, $MK$ and an identity $ID$. It outputs the semi-functional private key $\widetilde{S{K}_{ID}}$.

Semi-functional encryption algorithm:$EncryptSF(MP,M,S)\to \widetilde{CT}$. The algorithm inputs $MP$, $S$ and $M$. Semi-functional ciphertext $\widetilde{CT}$ is generated.

The first three algorithms are run by the private key generation center, and other algorithms are run by the user. The last two algorithms are only used for the security proof. Both decryption algorithm 1 and decryption algorithm 2 are executed by the data user. They are usually executed on two components and then transmit information through a secure channel. Each component operates independently and suffers from side-channel attacks. In this way, security can be enhanced.

4.2. Security Description of CLR-SS-AIBBE

Our scheme is secure against the chosen ciphertext attack.

The security of the CLR-SS-AIBBE scheme is described by the upcoming game ${\mathrm{EX}}_{\mathrm{R}}$. In ${\mathrm{EX}}_{\mathrm{R}}$, the challenger $ℬ$ holds a list $ℒ=\left\{\right(\mathscr{H},ℐ,\mathcal{S}\mathcal{K},ℒ{\mathcal{K}}_1,ℒ{\mathcal{K}}_2\left)\right\}$, where $\mathscr{H}$, $ℐ$, $\mathcal{S}\mathcal{K}$ and $ℒ{\mathcal{K}}_1,ℒ{\mathcal{K}}_2$ are the handle’s space, the identity’s space, the private key’s space and the leakage space, respectively. Let $\mathscr{H}=\mathbb{N}$ and $ℒ{\mathcal{K}}_1=ℒ{\mathcal{K}}_2=\mathbb{N}$.

The game ${\mathrm{EX}}_{\mathrm{R}}$ is played by an adversary (or attacker), $\mathcal{A}$, and a challenger, $ℬ$.

${\mathrm{EX}}_{\mathrm{R}}$:

Initialization:$ℬ$ calls the initialization algorithm to gain $MP$ and $MK$. $ℬ$ sends $MP$ to $\mathcal{A}$.

Stage 1. 

An attacker can query these upcoming oracles.

$\mathcal{O}\text{-}Generate(ID)$. As for one identity $ID$, $ℬ$ finds its corresponding item in $ℒ$. If one item is found out, the game is over. If no item is found out, $ℬ$ runs $KeyGen$ to obtain one private key $S{K}_{ID}$ and updates the handle $h\leftarrow h+1$. Then, the challenger puts $(h,ID,S{K}_{ID},0,0)$ in $ℒ$.

$\mathcal{O}\text{-}Leak(h,f_1,f_2)$. The attacker inquires the leakage of the private key about the item $h$. The attacker selects two leakage functions, $f_1$ and $f_2$. $f_1$ and $f_2$ input the private keys $S{K}_{I{D}_i,k,1}$ and $S{K}_{I{D}_i,k,2}$, respectively. $ℬ$ sends the outputs of $f_1$ and $f_2$ to the adversary.

Specifically, $ℬ$ looks for one corresponding item about the handle $h$. If one item $(h,ID,S{K}_{ID},L_1,L_2)$ is found out, $ℬ$ determines whether $L_1+|f_1(S{K}_{ID})|\le L_{S{K}_1}$ and $L_2+|f_2(S{K}_{ID})|\le L_{S{K}_2}$, where $L_{S{K}_1}$ and $L_{S{K}_2}$ are the maximum values that allow the leakage of the private key. If $L_1+|f_1(S{K}_{ID})|\le L_{S{K}_1}$, the challenger will send $f_1(S{K}_{ID})$ to the adversary and use $(h,ID,S{K}_{ID},L_1+|f_1(S{K}_{ID})|,L_2)$ to update $(h,ID,S{K}_{ID},L_1,L_2)$. Otherwise, the challenger outputs ⊥. Similarly, if $L_2+|f_2(S{K}_{ID})|\le L_{S{K}_2}$, the challenger will send $f_2(S{K}_{ID})$ to the adversary and use $(h,ID,S{K}_{ID},L_1,L_2+|f_2(S{K}_{ID})|)$ to update $(h,ID,S{K}_{ID},L_1,L_2)$. Otherwise, the challenger outputs ⊥. Set $L_{S{K}_1}=L_{S{K}_2}=L_{SK}$.

$\mathcal{O}\text{-}Reveal(h)$. If $\mathcal{A}$ asks for a private key about one handle $h$, $ℬ$ looks for it in $ℒ$. If the found item is $(h,ID,S{K}_{ID},L_1,L_2)$, the challenger sends $S{K}_{ID}$ to $\mathcal{A}$.

$\mathcal{O}\text{-}Refersh$. If an attacker enquires an updated private key about the handle $h$, the challenger looks for it in $ℒ$. If the found item is $(h,ID,S{K}_{ID},L_1,L_2)$, the challenger invokes $KeyUpd$ to obtain the updated private key $\widehat{S{K}_{ID}}$. $ℬ$ sends $\widehat{S{K}_{ID}}$ to $\mathcal{A}$ and uses $(h,ID,\widehat{S{K}_{ID}},0,0)$ to update $(h,ID,S{K}_{ID},L_1,L_2)$.

$\mathcal{O}\text{-}Decrypt1$. If the attacker asks for the corresponding plaintext of $(ID,CT)$, the challenger looks for $S{K}_{ID}$ in $ℒ$. The challenger runs $Decrypt1(MP,S{K}_{I{D}_i,k,1},S,CT)\to C{T}^{\prime }$. If $I{D}_i\in S$, the challenger calculates some parts $C{T}^{\prime }$ of the plaintext and sends $C{T}^{\prime }$ to $\mathcal{A}$.

$\mathcal{O}\text{-}Decrypt2$. If $\mathcal{A}$ inquires about this plaintext of $(ID,CT)$, the challenger looks for $S{K}_{ID}$ about $ID$ in $ℒ$. This challenger runs $Decrypt2(MP,S{K}_{I{D}_i,k,2},S,C{T}^{\prime })\to M$. First, $CT$ is divided into $(C,Hdr)$. If $I{D}_i\in S$, the challenger uses $Hdr$ to calculate the symmetric key $CK$. Then, it recovers $M$ by decrypting $C$ with $CK$ and sends it to $\mathcal{A}$.

Challenge. $\mathcal{A}$ gives two messages, $M_0$ and $M_1$, of equal size. $ℬ$ selects randomly $\beta \leftarrow \{0,1\}$. Then, $ℬ$ takes $MP$ and the identity set $S^{*}=\{I{D}_1^{*},\dots ,I{D}_d^{*}\}$ ($d\le l$) as input. $ℬ$ outputs $(Hd{r}^{*},C{K}^{*})$. $ℬ$ utilizes $C{K}^{*}$ to encrypt $M_{\beta }$ to get the ciphertext $C^{*}$. $ℬ$ sends $(C^{*},Hd{r}^{*},S^{*})$.

Stage 2. 

$\mathcal{A}$can ask $\mathcal{O}\text{-}Create$, $\mathcal{O}\text{-}Reveal$, $\mathcal{O}\text{-}Decrypt1$and $\mathcal{O}\text{-}Decrypt2$. The basic limitations are the same as stage 1. Other restrictions are that $\mathcal{A}$cannot inquiry the information about $ID\in S^{*}$ and$Hdr=Hd{r}^{\ast }$. In addition, a leakage inquiry cannot be performed. Since, if a leakage inquiry is allowed, $\mathcal{A}$ may take the ciphertext, the decryption algorithm and $M_0$and $M_1$as the input of the leakage function and obtain a bit output, and win the game in an ordinary way.

Guess. The attacker gives one guess, ${\beta }^{\prime }\in \{0,1\}$. If ${\beta }^{\prime }=\beta$, $\mathcal{A}$ wins this game ${\mathrm{EX}}_{\mathrm{R}}$. The superiority, that $\mathcal{A}$ wins this game ${\mathrm{EX}}_{\mathrm{R}}$, is defined as $Ad{v}_{\mathcal{A}}(L_{SK})=\left|\mathrm{Pr}[{\beta }^{\prime }=\beta ]-\frac{1}{2}\right|$.

If any PPT attacker can only win negligible advantages in the game ${\mathrm{EX}}_{\mathrm{R}}$, the CLR-SS-AIBBE scheme is said to be safety against leakage attack.

5. Specific Construction of CLR-SS-AIBBE

Let $\Phi$ to represent a bilinear group generation algorithm. Taking the safety parameters $\varpi$ as inputs, $\Phi$ produces a bilinear group with composite order $\Omega =\{N=w_1{w}_2{w}_3,G_1,G_2,e\}$. $w_1$, $w_2$ and $w_3$ are three different primes with $\theta$ bits (that is, ${\log }_2^{w_1}={\log }_2^{w_2}$$={\log }_2^{w_3}=\theta$). $G_1$ is a cyclic group with order $N=w_1{w}_2{w}_3$, so is $G_2$. $e$ is a bilinear map that maps $G_1\times G_1$ to $G_2$. $\theta$ is determined by safety parameter $\varpi$.

Initialization algorithm. Let $l$ indicate the maximum number of users. The algorithm randomly selects $g_1,h_1\in G_{w_1},$$g_3\in G_{w_3}$, $a_1,a_2,\dots ,a_l,b\in Z_N$ and $\alpha \in Z_N$ and sets $u_1=g_1^{a_1},\dots ,u_l=g_1^{a_l}$ and $h_1=g_1^b$. The master public key is $MP=\{N,g_1,g_3,h_1,u_1,\dots ,u_l,e{(g_1,g_1)}^{\alpha }\}$. The master private key is $MK=\left\{\alpha \right\}$.

Private key generation algorithm. For an identity $I{D}_i\in S$, where $S=(I{D}_1,\dots ,I{D}_d)$ ($d\le l$) is this set of the intended recipients, the algorithm inputs $MP$, $MK$ and one user’s identity, $I{D}_i$. The algorithm randomly selects $a_1,a_2,\dots ,a_d,b\in Z_N$, ${\beta }_{i,0},{\gamma }_{i,0}\in Z_N$, $r_i\in Z_N$$(i=\{1,\dots ,d\})$ and $R_i,Q_i,R_i^{\prime },Q_i^{\prime }\in G_{p_3}$. It sets $u_1=g_1^{a_1},\dots ,u_l=g_1^{a_l}$ and $h_1=g_1^b$. The generated private key is $S{K}_{I{D}_i,0}=(S{K}_{I{D}_i,0,1},S{K}_{I{D}_i,0,2})$, where $S{K}_{I{D}_i,0,1}=(g_1^{r_i}{R}_i{g}_1^{{\beta }_{i,0}},g_1^{\alpha }{(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}})}^{r_i}{Q}_i{g}_1^{{\gamma }_{i,0}})$ and $S{K}_{I{D}_i,0,2}=(R_i^{\prime }{g}_1^{-{\beta }_{i,0}},Q_i^{\prime }{g}_1^{-{\gamma }_{i,0}})$.

Private key update algorithm. It inputs $S{K}_{I{D}_i,k}$ and $MP$. It obtains a new private key $S{K}_{I{D}_i,k+1}$. For the private key $S{K}_{I{D}_i,k}=(S{K}_{I{D}_i,k,1},S{K}_{I{D}_i,k,2})$, where $S{K}_{I{D}_i,k,1}=(S{K}_{I{D}_i,k,1}^1,S{K}_{I{D}_i,k,1}^2)$ $=(g_1^{r_i}{R}_1{g}_1^{{\beta }_{i,1}+\dots +{\beta }_{i,k}},g_1^{\alpha }{(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}})}^{r_i}{Q}_1{g}_1^{{\gamma }_{i,1}+\dots +{\gamma }_{i,k}})$ and $S{K}_{I{D}_i,k,2}=(S{K}_{I{D}_i,k,2}^1,S{K}_{I{D}_i,k,2}^2)=(R_1^{\prime }{g}_1^{-{\beta }_{i,1}-\dots -{\beta }_{i,k}},Q_1^{\prime }{g}_1^{-{\gamma }_{i,1}-\dots -{\gamma }_{i,k}})$. It chooses randomly ${\beta }_{i,k+1},{\lambda }_{i,k+1}\in Z_N$ and calculates a new private key:

$$S{K}_{I{D}_i,k+1}=(S{K}_{I{D}_i,k+1,1},S{K}_{I{D}_i,k+1,2}),$$

where

$$\begin{array}{l}S{K}_{I{D}_i,k+1,1}=(S{K}_{I{D}_i,k,1}^1{g}_1^{{\beta }_{i,k+1}},S{K}_{I{D}_i,k,1}^2{g}_1^{{\gamma }_{i,k+1}})\\ =(g_1^{r_i}{R}_1{g}_1^{{\beta }_{i,1}+\dots +{\beta }_{i,k}}{g}_1^{{\beta }_{i,k+1}},g_1^{\alpha }{(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}})}^{r_i}{Q}_1{g}_1^{{\gamma }_{i,1}+\dots +{\gamma }_{i,k}}{g}_1^{{\gamma }_{i,k+1}})\\ =(g_1^{r_i}{R}_1{g}_1^{{\beta }_{i,1}+\dots +{\beta }_{i,k}+{\beta }_{i,k+1}},g_1^{\alpha }{(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}})}^{r_i}{Q}_1{g}_1^{{\gamma }_{i,1}+\dots +{\gamma }_{i,k}+{\gamma }_{i,k+1}})\end{array}$$

and

$$S{K}_{I{D}_i,k+1,2}=(S{K}_{I{D}_i,k,2}^1{g}_1^{-{\beta }_{i,k+1}},S{K}_{I{D}_i,k,2}^2{g}_1^{-{\gamma }_{i,k+1}})=(R_1^{\prime }{g}_1^{-{\beta }_{i,1}-\dots -{\beta }_{i,k}-{\beta }_{i,k+1}},Q_1^{\prime }{g}_1^{-{\gamma }_{i,1}-\dots -{\gamma }_{i,k}-{\gamma }_{i,k+1}})$$

Since ${\beta }_{i,k+1},{\lambda }_{i,k+1}\in Z_N$ are randomly selected, ${\beta }_{i,1}+\dots +{\beta }_{i,k}+{\beta }_{i,k+1}$ and ${\gamma }_{i,1}+\dots +{\gamma }_{i,k}+{\gamma }_{i,k+1}$ are also random. The private keys $S{K}_{I{D}_i,k+1}$ and $S{K}_{I{D}_i,k}$ have the same distributions. Without losing the generality, if a private key is needed, the original private key $S{K}_{I{D}_i}$ will be used for the convenience.

Encryption algorithm. It takes $M$ and one set $S=(I{D}_1,\dots ,I{D}_d)$ that will receive the ciphertext as the input. It randomly chooses $s\in Z_N$ and $Z,Z^{\prime }\in G_{p_2}$ and computes the ciphertext:

$$CT=(C,Hdr)=(C,C_1,C_2)=(Me{(g_1,g_1)}^{\alpha s},(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}{)}^{s}Z,g_1^s{Z}^{\prime }})$$

The encapsulated key is $e{(g_1,g_1)}^{\alpha s}$. The data owner transmits $(CT,S)$ to the receiver.

Decryption algorithm 1. For one user $I{D}_i$, if $I{D}_i\in S$, it can decrypt the received ciphertext. It divides $CT=(C,Hdr)$. They run the decryption algorithm $Decrypt1(MP,S{K}_{I{D}_i,k,1},S,CT)\to C{T}^{\prime }$. If $I{D}_i\in S$, the algorithm uses $Hdr$ to calculate part of the plaintext, $C{T}^{\prime }$.

First, it uses $S{K}_{I{D}_i,k,1}$ to calculate $C{T}^{\prime }=(C,C_1,C_2,C_1^{\prime },C_2^{\prime })$:

$$\begin{array}{l}{C}_1^{\prime }=e(S{K}_{I{D}_i,k,1}^1,C_1)=e(g_1^{r_i}{R}_1{g}_1^{{\beta }_{i,1}+\dots +{\beta }_{i,k}},(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}{)}^{s}Z}),\\ C_2^{\prime }=e(S{K}_{I{D}_i,k,1}^2,C_2)=e(g_1^{\alpha }{(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}})}^{r_i}{Q}_1{g}_1^{{\gamma }_{i,1}+\dots +{\gamma }_{i,k}},g_1^s{Z}^{\prime }).\end{array}$$

Decryption algorithm 2. The algorithm inputs $MP$, $S{K}_{I{D}_i,k,2}$, the user’s identity set $S$ and the part plaintext $C{T}^{\prime }$. Supposing $I{D}_i\in S$, it first calculates the encapsulated key $CK$. Next, the plaintext message $M$ is recovered by $CK$.

First, it calculates:

$$\begin{array}{l}{C}_1^{\prime }e(S{K}_{I{D}_i,k,2}^1,C_1)=e(S{K}_{I{D}_i,k,1}^1,C_1)e(S{K}_{I{D}_i,k,2}^1,C_1)\\ =e(g_1^{r_i}{R}_1{R}_1^{\prime }{g}_1^{{\beta }_{i,1}+\dots +{\beta }_{i,k}}{g}_1^{-{\beta }_{i,1}-\dots -{\beta }_{i,k}},(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}{)}^{s}Z})\\ =e(g_1^{r_i},(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}{)}^s})\end{array}$$

$$\begin{array}{l}{C}_2^{\prime }.e(S{K}_{I{D}_i,k,2}^2,C_2)=e{(S{K}_{I{D}_i,k,1}^2,C_2)}_2.e(S{K}_{I{D}_i,k,2}^2,C_2)\\ =e(g_1^{\alpha }{(h{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}})}^{r_i}{Q}_1{Q}_1^{\prime }{g}_1^{{\gamma }_{i,1}+\dots +{\gamma }_{i,k}}{g}_1^{-{\gamma }_{i,1}-\dots -{\gamma }_{i,k}},g_1^s{Z}^{\prime })\\ =e(g_1^{\alpha }{(h{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}})}^{r_i},g_1^s)\end{array}$$

Then, it obtains

$$M=C_0\frac{C_1^{\prime }e(S{K}_{I{D}_i,k,2}^1,C_1)}{C_2^{\prime }.e(S{K}_{I{D}_i,k,2}^2,C_2)}=Me{(g_1,g_1)}^{\alpha s}\frac{e(g_1^{r_i},(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}{)}^s})}{e(g_1^{\alpha }{(h{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}})}^{r_i},g_1^s)}=M$$

For the semi-functional private key generation algorithm, given $S{K}_{I{D}_i,k}=(S{K}_{I{D}_i,k,1},S{K}_{I{D}_i,k,2})$, where $S{K}_{I{D}_i,k,1}=(S{K}_{I{D}_i,k,1}^1,S{K}_{I{D}_i,k,1}^2)=(g_1^{r_i}{R}_1{g}_1^{{\beta }_{i,1}+\dots +{\beta }_{i,k}},g_1^{\alpha }{(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}})}^{r_i}{Q}_1{g}_1^{{\gamma }_{i,1}+\dots +{\gamma }_{i.k}})$ and $S{K}_{I{D}_i,k,2}=(S{K}_{I{D}_i,k,2}^1,S{K}_{I{D}_i,k,2}^2)=(R_1^{\prime }{g}_1^{-{\beta }_{i,1}-\dots -{\beta }_{i,k}},Q_1^{\prime }{g}_1^{-{\gamma }_{i,1}-\dots -{\gamma }_{i,k}})$, it randomly selects ${\xi }_1,{\xi }_2,{\zeta }_1,{\zeta }_2\in Z_N$ and generates the semi-functional private key: $\widetilde{S{K}_{I{D}_i}}=(\widetilde{S{K}_{I{D}_i,k,1}},\widetilde{S{K}_{I{D}_i,k,2}})$, where $\widetilde{S{K}_{I{D}_i,k,1}}=(g_1^{r_i}{R}_1{g}_1^{{\beta }_{i,1}+\dots +{\beta }_{i,k}}{g}_2^{{\xi }_1},g_1^{\alpha }{(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}})}^{r_i}{Q}_1{g}_1^{{\gamma }_{i,1}+\dots +{\gamma }_{i,k}}{g}_2^{{\xi }_2})$ and $\widetilde{S{K}_{I{D}_i,k,2}}=(R_1^{\prime }{g}_1^{-{\beta }_{i,1}-\dots -{\beta }_{i,k}}{g}_2^{{\zeta }_1},Q_1^{\prime }{g}_1^{-{\gamma }_{i,1}-\dots -{\gamma }_{i,k}}{g}_2^{{\zeta }_2})$.

The semi-functional encryption algorithm invokes $Encrypt$ to gain normal ciphertext $CT=(C,Hdr)=(C,C_1,C_2)=(Me{(g_1,g_1)}^{\alpha s},(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}{)}^{s}Z,g_1^s{Z}^{\prime }})$.

Then, it randomly selects ${\rho }_1,{\rho }_2,{\rho }_3\in Z_N$ and generates semi-functional ciphertexts:

$$\begin{array}{cc}\hfill \widetilde{CT}& =(\tilde{C},\widetilde{Hdr})=(\tilde{C},\widetilde{C_1},\widetilde{C_2})=(C{g}_2^{{\rho }_1},C_1{g}_2^{{\rho }_2},C_2{g}_2^{{\rho }_3})\hfill \\ & =(Me{(g_1,g_1)}^{\alpha s}{g}_2^{{\rho }_1},(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}{)}^{s}Z{g}_2^{{\rho }_2},g_1^s{Z}^{\prime }}{g}_2^{{\rho }_3})\hfill \end{array}$$

6. Proof of Safety

Theorem 1. 

Suppose that Assumption 1, Assumption 2 and Assumption 3 hold, and the leakage amount of the private key does not exceed $L_{S{K}_1}=L_{S{K}_2}=(1-2\Lambda )\theta$bits, where $\theta ={\log }_2^{w_2}$, and $\Lambda$ is a small constant number; the proposed CLR-SS-AIBBE scheme is CCA secure under the standard model, where $L_{S{K}_1}=L_{S{K}_2}=L_{SK}$.

The main ideal of the proof. The indistinguishability of a series of games expounds its security of the given scheme. ${\mathrm{EX}}_{\mathrm{R}}$ is a real security game, and the rest of the games are gradually changed from ${\mathrm{EX}}_{\mathrm{R}}$. In ${\mathrm{EX}}_{\mathrm{F}}$, any attacker has no advantage. As long as it is proven that the adversary cannot distinguish between two consecutive games, security is achieved. $q$ denotes the maximum number of private key queries.

${\mathrm{EX}}_{\mathrm{R}}$: It is the real security game of CLR-SS-AIBBE.

${\mathrm{EX}}_0$: It is very similar to ${\mathrm{EX}}_{\mathrm{R}}$. The only difference is that ${\mathrm{EX}}_0$ has semi-functional ciphertext.

${\mathrm{EX}}_{\mathrm{i}}$ ($i\in [1,q]$): The challenger responds to $\mathcal{A}$ with a semi-functional ciphertext, responds to $\mathcal{A}$’s previous $i$ private key inquiries with semi-functional ones and responds to the other private key queries with normal ones. Supposing $i=q$ (${\mathrm{EX}}_{\mathrm{q}}$), the challenger generates semi-functional private keys to respond to all private key queries.

${\mathrm{EX}}_{\mathrm{F}}$. The only difference between ${\mathrm{EX}}_{\mathrm{q}}$ and ${\mathrm{EX}}_{\mathrm{F}}$ is that in ${\mathrm{EX}}_{\mathrm{F}}$, $ℬ$ encrypts a message randomly, while in ${\mathrm{EX}}_{\mathrm{q}}$, $ℬ$ only encrypts one of the two given challenge messages.

Table 2. The forms of the ciphertext and the private key for every game (CLR-SS-AIBBE).

Game	Types of Ciphertext and Private Key ${(\mathbf{TY}}_{\mathbf{CT}}{,\mathbf{TY}}_{\mathbf{SK}},\dots {,\mathbf{TY}}_{\mathbf{SK}})$
${\mathrm{EX}}_{\mathrm{R}}$	$(\mathrm{NM},\mathrm{NM},\dots ,\mathrm{NM})$
${\mathrm{EX}}_0$	$(\mathrm{SMF},\mathrm{NM},\dots ,\mathrm{NM})$
$\begin{array}{c}{\mathrm{EX}}_{\mathrm{i}}\\ i\in (1,\dots ,q-1)\end{array}$	$(\mathrm{SMF},\mathrm{SMF},\dots ,\underset{i+1}{\underbrace{\mathrm{SMF}}},\mathrm{NM},\dots ,\mathrm{NM})$
${\mathrm{EX}}_{\mathrm{q}}$	$(\mathrm{SMF},\mathrm{SMF},\dots ,\mathrm{SMF})$
${\mathrm{EX}}_{\mathrm{F}}$	$(\mathrm{SMF},\mathrm{SMF},\dots ,\mathrm{SMF})$

shows the types of the ciphertext and the private key for every game. The ciphertext or the private key represented by SMF is semi-functional. We use NM to indicate that one ciphertext or one private key is normal. The types for the ciphertext and the private key are represented by ${\mathrm{TY}}_{\mathrm{SK}}$ and ${\mathrm{TY}}_{\mathrm{CT}}$, respectively. $(\underset{\mathrm{q}}{\underbrace{{(\mathrm{TY}}_{\mathrm{CT}}{,\mathrm{TY}}_{\mathrm{SK}}),\dots {,(\mathrm{TY}}_{\mathrm{CT}}{,\mathrm{TY}}_{\mathrm{SK}})}})$ indicates the corresponding type of the private keys and the ciphertexts of the $q$ inquiries in one game. Since the ciphertext has the same form in every query, $(\underset{\mathrm{q}}{\underbrace{{(\mathrm{TY}}_{\mathrm{CT}}{,\mathrm{TY}}_{\mathrm{SK}}),\dots {,(\mathrm{TY}}_{\mathrm{CT}}{,\mathrm{TY}}_{\mathrm{SK}})}})$ can be abbreviated as ${(\mathrm{TY}}_{\mathrm{CT}},\underset{\mathrm{q}}{\underbrace{{\mathrm{TY}}_{\mathrm{SK}},\dots {,\mathrm{TY}}_{\mathrm{SK}}}})$.

Proof. 

We will complete the proof through ${\mathrm{EX}}_{\mathrm{R}}$, ${\mathrm{EX}}_{\mathrm{i}}$ ($i\in (0,1,\dots ,q)$) and ${\mathrm{EX}}_{\mathrm{F}}$ and four lemmas. Lemma 1 gives the limit of leakage. The other three lemmas prove the indistinguishability of these games. Moreover, the advantage gained by the attacker in the game ${\mathrm{EX}}_{\mathrm{F}}$ is proven to be negligible.

Table 3. The distinctions for the superiority achieved by the attacker between two consecutive games (CLR-SS-AIBBE).

Two Consecutive Games	Differences of the Advantages	Lemmas
${\mathrm{EX}}_{\mathrm{R}}$$\mathrm{or}{\mathrm{EX}}_0$	$|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{R}}}-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_0}|\le \epsilon$	Lemma 2
$\begin{array}{c}{\mathrm{EX}}_{\mathrm{i}}\mathrm{or}{\mathrm{EX}}_{\mathrm{i}-1}\\ i\in (1,\dots ,q)\end{array}$	$|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{i}-1}}-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{i}}}|\le \epsilon$	Lemma 3
${\mathrm{EX}}_{\mathrm{q}}$$\mathrm{or}{\mathrm{EX}}_{\mathrm{F}}$	$|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}}}-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{F}}}|\le \epsilon$	Lemma 4

illustrates the distinctions for the superiority achieved by the attacker between two consecutive games. Here, we give the conclusions of Lemma 2, Lemma 3 and Lemma 4. Their proofs will be given later. $Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{R}}}$ or $Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{R}}}(L_{SK})$ is used to indicate the superiority achieved by $\mathcal{A}$ in this game ${\mathrm{EX}}_{\mathrm{R}}$. We use $Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{i}}}$ or $Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{i}}}(L_{SK})$ to indicate the superiority achieved by $\mathcal{A}$ in this game ${\mathrm{EX}}_{\mathrm{i}}$ ($i\in (0,\dots ,q)$). We use $Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{F}}}$ or $Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{F}}}(L_{SK})$ to indicate the superiority achieved by $\mathcal{A}$ in this game ${\mathrm{EX}}_{\mathrm{F}}$.

From Table 3, the following fact can be obtained.

$$\begin{array}{l}|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{R}}}-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{F}}}|\\ =|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{R}}}-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_0}+Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_0}-\dots -Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{i}}}+Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{i}}}-\cdots \\ -Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}}}+Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}}}-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{F}}}|\\ \le |Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{R}}}-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_0}|+|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_0}-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_1}|+\dots +|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}}}-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{F}}}|\\ \le (q+2)\epsilon \end{array}$$

So, $|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{R}}}-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{F}}}|\le (q+2)\epsilon$. Furthermore, according to theorem 6.8 given in [50], we obtain that $Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{F}}}\le \epsilon$. Thus, the proof of Theorem 1 is completed.

Lemma 1. 

The maximum amount of one private key leakage can reach $L_{S{K}_1}=L_{S{K}_2}=(1-2\Lambda )\theta$.

Proof. 

We will utilize a result in ref. [26] to complete the proof.

Result 1 

([26]). Given a prime $p$, we select $n_1\ge n_2\ge 2$ ($n_1,n_2\in N$), a matrix $X\leftarrow Z_p^{n_1\times n_2}$ and a matrix $Y\leftarrow R{k}_1(Z_p^{n_2\times 1})$, with rank 1 and $\Theta \leftarrow Z_p^{n_1}$. The leakage function is $f:Z_p^{n_1}\to W$. As long as $\left|W\right|\le 4\cdot (1-\frac{1}{p})\cdot p^{n_2-1}\cdot {\epsilon }^2$, the statistical distance $SD((X,f(X\cdot Y)),(X,f(\Theta ))\le \epsilon$, where $\epsilon$ is a negligible value.

According to Result 1, the following Deduction 1 is obtained easily.

Deduction 1.

Given a prime $p$, we choose $n_1\ge 3$,$\overrightarrow{\delta }\leftarrow Z_p^{n_1},\overrightarrow{\tau }\leftarrow Z_p^{n_1}$ and${\overrightarrow{\tau }}^{\prime }\leftarrow Z_p^{n_1}$ such that the dot product of ${\overrightarrow{\tau }}^{\prime }$ and $\overrightarrow{\delta }$is orthogonal with respect to the module $p$. Suppose that the leakage function is $f:Z_p^{n_1}\to W$. As long as $\left|W\right|\le 4\cdot (1-\frac{1}{p})\cdot p^{n_1-2}\cdot {\epsilon }^2$,$SD((\overrightarrow{\delta },f({\overrightarrow{\tau }}^{\prime })),(\overrightarrow{\delta },f(\overrightarrow{\tau })))\le \epsilon$.

Proof. 

According to the conclusion 1, if $n_2=n_1-1$, $n_1=n_2+1\ge n_2\ge 2$. This basis of the orthogonal space of $\overrightarrow{\delta }$ corresponds to $X$ and $\overrightarrow{\tau }$ corresponds to $\Phi$. So, when $Y\leftarrow R{k}_1(Z_p^{(n_1-1)\times 1})$, the distributions of ${\overrightarrow{\tau }}^{\prime }$ are the same as $X\cdot Y$. Since $\overrightarrow{\delta }$ is randomly selected, $X\leftarrow Z_p^{n_1\times (n_1-1)}$ is uniquely determined by $\overrightarrow{\delta }$. According to Deduction 1, we obtain $SD((\overrightarrow{\delta },f({\overrightarrow{\tau }}^{\prime })),(\overrightarrow{\delta },f(\overrightarrow{\tau })))$$=dist((X,f(X\cdot T)),(X,f(\Phi ))$. □

If we set $n_2=2$, $p_2=p$ and $\epsilon =p_2^{-\Lambda }$, the allowed value of private key leakage is ${\log }_2^{\left|W\right|}$ $\le (2-1){\log }_2^{w_2}-2\Lambda {\log }_2^{w_2}$$=(1-2\Lambda ){\log }_2^{w_2}$ = $(1-2\Lambda )\theta$, where ${\log }_2^{w_2}=\theta$. Thus, the maximum value of private key leakage can reach $L_{S{K}_1}=L_{S{K}_2}=L_{SK}=(1-2\Lambda )\theta$. □

Lemma 2. 

If there is an adversary $\mathcal{A}$, such that $|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{R}}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_0}(L_{SK})|\ge \epsilon$, the challenger $ℬ$can destroy Assumption 1 over advantage $\epsilon$.

Proof. 

Given $D=(\Omega ,g_1,X_3)$, $U,V\in G_{w_2}$ and $T$ ($T\in G_{w_1{w}_2}$ or $T\in G_{w_1}$), $ℬ$ and $\mathcal{A}$ interact as follows.

Initialization. Let $l$ indicate the maximum number of users. The challenger $ℬ$ randomly selects $g_1,h_1\in G_{w_1},$$g_3\in G_{w_3}$, $a_1,a_2,\dots ,a_l,b\in Z_N$ and $\alpha \in Z_N$. $ℬ$ sets $u_1=g_1^{a_1},\dots ,u_l=g_1^{a_l}$ and $h_1=g_1^b$.

The master public key is $MP=\{N,g_1,g_3,h_1,u_1,\dots ,u_l,e{(g_1,g_1)}^{\alpha }\}$, and the master private key is $MK=\left\{\alpha \right\}$. $ℬ$ sends $MP$ to $\mathcal{A}$.

Phase1. $\mathcal{A}$ inquires the private key of $I{D}_i\in S$, where $S=(I{D}_1,\dots ,I{D}_d)$, ($d\le l$) is this set of the intended recipients, $ℬ$ randomly selects ${\beta }_{i,0},{\gamma }_{i,0}\in Z_N$ and $r_i\in Z_N$$(i=\{1,\dots ,d\})$$r_i,q_i,r_i^{\prime },q_i^{\prime }\in Z_N$. $ℬ$ generates private key $S{K}_{I{D}_i,0}=(S{K}_{I{D}_i,0,1},S{K}_{I{D}_i,0,2})$, where $S{K}_{I{D}_i,0,1}=(g_1^{r_i}{X}_3^{r_i}{g}_1^{{\beta }_{i,0}},g_1^{\alpha }{(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}})}^{r_i}{X}_3^{q_i}{g}_1^{{\gamma }_{i,0}})$ and $S{K}_{I{D}_i,0,2}=(g_1^{-{\beta }_{i,0}}{X}_3^{r_i^{\prime }},g_1^{-{\gamma }_{i,0}}{X}_3^{q_i^{\prime }})$. $ℬ$ responds to $\mathcal{A}$ with the private key ${SK}_{D_i}$.

Challenge. $\mathcal{A}$ gives $\mathcal{B}$ one set $S^{*}=\{I{D}_1^{*},\dots ,D_d^{*}\}$ and two messages, $M_0$ and $M_1$, of equal size. $\mathcal{B}$ randomly selects $\beta \in \{0,1\}$ and calculates ciphertext $CT=(C,Hdr)=(C,C_1,C_2)=(Me{(g_1,T)}^{\alpha },T^{{\displaystyle \sum _{j=1}^d{a}_{j}I{D}_j}+b}U,TV)$.

Phase 2. $\mathcal{A}$ may query the private key for $I{D}_i\notin S^{*}$.

Guess. $\mathcal{A}$ output a guess ${\beta }^{\prime }$. If ${\beta }^{\prime }$, $\mathcal{A}$ wins the game.

When $T=g_1^z{g}_2^v\in G_{w_1{w}_2}$ ($z,v$ are randomly selected), $\mathcal{B}$ properly simulates the game ${\mathrm{EX}}_0$. When $T=g_1^z\in G_{w_1}$ ($z$ is randomly selected), $\mathcal{B}$ properly simulates the game ${\mathrm{EX}}_{\mathrm{R}}$. In other words, as long as $\mathcal{A}$ achieves certain advantages in distinguishing ${\mathrm{EX}}_{\mathrm{R}}$ and ${\mathrm{EX}}_0$, the challenger has the same advantages in destroying assumption 1. This is not consistent with Assumption 1. So, $|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{R}}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_0}(L_{SK})|<\epsilon$. □

Lemma 3. 

If there is an adversary $\mathcal{A}$such that $|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{k}-1}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{k}}}(L_{SK})|\ge \epsilon$ ($k\in (1,\dots ,q)$), the challenger $ℬ$can destroy Assumption 2 over advantage $\epsilon$.

Proof. 

Given $D=(\Omega ,g_1,X_1{X}_2,X_3,Y_2{Y}_3)$ and $T$ ($T\in G_{w_1{w}_3}$ or $T\in G_1$), $ℬ$ and $\mathcal{A}$ interact as follows.

Initialization. Let $l$ indicate the maximum number of users. The challenger $ℬ$ randomly selects $g_1,h_1\in G_{w_1},$$g_3\in G_{w_3}$, $a_1,a_2,\dots ,a_l,b\in Z_N$ and $\alpha \in Z_N$. $ℬ$ sets $u_1=g_1^{a_1},\dots ,u_l=g_1^{a_l}$ and $h_1=g_1^b$.

The master public key is $MP=\{N,g_1,g_3,h_1,u_1,\dots ,u_l,e{(g_1,g_1)}^{\alpha }\}$, and the master private key is $MK=\left\{\alpha \right\}$. $ℬ$ sends $MP$ to $\mathcal{A}$.

Phase1. $\mathcal{A}$ inquires a private key, which corresponds to $I{D}_i\in S$, where $S=\{I{D}_1,\dots ,I{D}_d\}$. $ℬ$ responds like this.

(1) In case $i<k$, $ℬ$ responds with one private key with a semi-functional form. $ℬ$ randomly picks ${\xi }_1,{\xi }_2,{\zeta }_1,{\zeta }_2\in Z_N$ and generates one private key with the semi-functional form $\widetilde{S{K}_{I{D}_i}}=(\widetilde{S{K}_{I{D}_i,k,1}},\widetilde{S{K}_{I{D}_i,k,2}})$, where $\widetilde{S{K}_{I{D}_i,k,1}}=(g_1^{r_i}{R}_1{g}_1^{{\beta }_{i,1}+\dots +{\beta }_{i,k}}{(g_2^u{g}_3^{\varsigma })}^{{\xi }_1},g_1^{\alpha }{(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}})}^{r_i}{Q}_1{g}_1^{{\gamma }_{i,1}+\dots +{\gamma }_{i,k}}{(g_2^u{g}_3^{\varsigma })}^{{\xi }_2})$ and $\widetilde{S{K}_{I{D}_i,k,2}}=(R_1^{\prime }{g}_1^{-{\beta }_{i,1}-\dots -{\beta }_{i,k}}{(g_2^u{g}_3^{\varsigma })}^{{\zeta }_1},Q_1^{\prime }{g}_1^{-{\gamma }_{i,1}-\dots -{\gamma }_{i,k}}{(g_2^u{g}_3^{\varsigma })}^{{\zeta }_2})$.

(2) In case $i>k$, $ℬ$ calls the private key generation algorithm to gain one private key with normal form.

(3) In case $i=k$, $ℬ$ randomly picks ${\beta }_{i,k},{\gamma }_{i,k}\in Z_N$, $r_i\in Z_N$$(i=\{1,\dots ,d\})$ and $R_i,Q_i,R_i^{\prime },Q_i^{\prime }\in G_{p_3}$. $ℬ$ generates a private key $S{K}_{I{D}_i,k}=(S{K}_{I{D}_i,k,1},S{K}_{I{D}_i,k,2})$, where $S{K}_{I{D}_i,k,1}=(S{K}_{I{D}_i,k,1}^1,S{K}_{I{D}_i,k,1}^2)=(T^{r_i}{g}_1^{{\beta }_{i,1}+\dots +{\beta }_{i,k}}{R}_1,g_1^{\alpha }{(T^{{\displaystyle \sum _{j=1}^d{a}_{j}I{D}_j}+b})}^{r_i}{g}_1^{{\gamma }_{i,1}+\dots +{\gamma }_{i,k}}{Q}_1)$ and $S{K}_{I{D}_i,k,2}(S{K}_{I{D}_i,k,2}^1,S{K}_{I{D}_i,k,2}^2)=(R_1^{\prime }{g}_1^{-{\beta }_{i,1}-\dots -{\beta }_{i,k}},Q_1^{\prime }{g}_1^{-{\gamma }_{i,1}-\dots -{\gamma }_{i,k}})$.

Provided $T\in G_{w_1{w}_3}$, this private key is normal. $ℬ$ correctly imitates ${\mathrm{EX}}_{\mathrm{k}-1}$.

Provided $T\in G_1$, this private key has a semi-functional form. $ℬ$ correctly imitates ${\mathrm{EX}}_{\mathrm{k}}$.

Challenge.$\mathcal{A}$ gives $\mathcal{B}$ one set $S^{*}=\{I{D}_1^{*},\dots ,D_d^{*}\}$ and two messages, $M_0$ and $M_1$, of equal size. $\mathcal{B}$ randomly selects $\beta \in \{0,1\}$ and calculates ciphertext

$$CT=(C,Hdr)=(C,C_1,C_2)=(M_{\beta }e{(g_1,g_1^z{g}_2^v)}^{\alpha },{(g_1^z{g}_2^v)}^{{\displaystyle \sum _{j=1}^d{a}_{j}I{D}_j^{\ast }+b}},g_1^z{g}_2^v)$$

Phase 2. $\mathcal{A}$ may query the private key for $I{D}_i\notin S^{*}$.

Guess. $\mathcal{A}$ output a guess ${\beta }^{\prime }$. If ${\beta }^{\prime }=\beta$, $\mathcal{A}$ wins the game.

When $T\in G_{w_1{w}_3}$, $\mathcal{B}$ properly simulates the game ${\mathrm{EX}}_{\mathrm{k}-1}$. When $T\in G_1$, $\mathcal{B}$ properly simulates the game ${\mathrm{EX}}_{\mathrm{k}}$. Thus, $|\mathrm{Pr}[ℬ(D,T\in G_{w_1{w}_3})=0]-ℬ(D,T\in G_1)=0]|=|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{k}-1}}-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{k}}}|\ge \epsilon$. In other words, as long as $\mathcal{A}$ achieves certain advantages in distinguishing ${\mathrm{EX}}_{\mathrm{k}-1}$ and ${\mathrm{EX}}_{\mathrm{k}}$, the challenger has the same advantages in destroying Assumption 2. This is not consistent with assumption 2. So, $|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{k}-1}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{k}}}(L_{SK})|<\epsilon$.

For the same reason, as for $i\in [k,q]$, $|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{k}}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{k}+1}}(L_{SK})|<\epsilon$, …, and $|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}-1}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}}}(L_{SK})|<\epsilon$. So,

$$\begin{array}{l}|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{k}}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}}}(L_{SK})|\\ =|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{k}}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{k}+1}}(L_{SK})+\dots +Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}-1}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}}}(L_{SK})|\\ <|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{k}}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{k}+1}}(L_{SK})|+\dots +|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}-1}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}}}(L_{SK})|\\ <(q-k)\epsilon \end{array}$$

In addition, $|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{F}}}(L_{SK})|<\epsilon$ (the proof will be given in Lemma 4). In this way, we can obtain:

$$\begin{array}{l}Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{k}}}(L_{SK})\\ =|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{k}}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}}}(L_{SK})+Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{F}}}(L_{SK})|\\ <|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{k}}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}}}(L_{SK})|+|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{F}}}(L_{SK})|\\ <(q-k+1)\epsilon \end{array}$$

In other words, the advantage gained by $\mathcal{A}$ in ${\mathrm{EX}}_{\mathrm{i}}$ can be ignored. Lemma 3 is finished. □

Lemma 4. 

If there is an adversary $\mathcal{A}$such that $|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{F}}}(L_{SK})|\ge \epsilon$, the challenger $ℬ$can destroy assumption 3 over advantage $\epsilon$.

Proof. 

Given $D=(\Omega ,g_1,g_1^{\alpha }{X}_2,X_3,g_1^s{Y}_2,Z_2)$ and $T$ ($T=e{(g_1,g_1)}^{\alpha s}$ or $T\in G_2$, where $s\in Z_N$ is randomly selected), $ℬ$ and $\mathcal{A}$ interact as follows.

Initialization. Let $l$ indicate the maximum number of users. The challenger $ℬ$ randomly selects $g_1,h_1\in G_{w_1},$$g_3\in G_{w_3}$, $a_1,a_2,\dots ,a_l,b\in Z_N$ and $\alpha \in Z_N$. $ℬ$ sets $u_1=g_1^{a_1},\dots ,u_l=g_1^{a_l}$ and $h_1=g_1^b$.

The master public key is $MP=\{N,g_1,g_3,h_1,u_1,\dots ,u_l,e{(g_1,g_1)}^{\alpha }\}$, and the master private key is $MK=\left\{\alpha \right\}$. $ℬ$ sends $MP$ to $\mathcal{A}$.

Phase1. $\mathcal{A}$ queries the private key that corresponds to the identity $I{D}_i\in S$, where $S=\{I{D}_1,\dots ,I{D}_d\}$. $ℬ$ randomly selects ${\xi }_1,{\xi }_2,{\zeta }_1,{\zeta }_2\in Z_N$ and generates one private key with the semi-functional form $\widetilde{S{K}_{I{D}_i}}=(\widetilde{S{K}_{I{D}_i,k,1}},\widetilde{S{K}_{I{D}_i,k,2}})$, where $\widetilde{S{K}_{I{D}_i,k,1}}=(g_1^{r_i}{R}_1{g}_1^{{\beta }_{i,1}+\dots +{\beta }_{i,k}}{(g_2^u{g}_3^{\varsigma })}^{{\xi }_1},g_1^{\alpha }{(h_1{\displaystyle \prod _{j=1}^d{u}_j^{I{D}_j}})}^{r_i}{Q}_1{g}_1^{{\gamma }_{i,1}+\dots +{\gamma }_{i,k}}{(g_2^u{g}_3^{\varsigma })}^{{\xi }_2})$ and $\widetilde{S{K}_{I{D}_i,k,2}}=(R_1^{\prime }{g}_1^{-{\beta }_{i,1}-\dots -{\beta }_{i,k}}{(g_2^u{g}_3^{\varsigma })}^{{\zeta }_1},Q_1^{\prime }{g}_1^{-{\gamma }_{i,1}-\dots -{\gamma }_{i,k}}{(g_2^u{g}_3^{\varsigma })}^{{\zeta }_2})$.

Challenge. $\mathcal{A}$ gives $\mathcal{B}$ one set $S^{*}=\{I{D}_1^{*},\dots ,D_d^{*}\}$ and two messages, $M_0$ and $M_1$, of equal size. $\mathcal{B}$ randomly selects $\beta \in \{0,1\}$ and calculates ciphertext

$$\widetilde{CT}=(C,Hdr)=(C,C_1,C_2)=(M_{\beta }T,{(g_1^s{g}_2^u)}^{{\displaystyle \sum _{i=1}^d{a}_{i}I{D}_i^{*}+b}}Z,g_1^s{g}_2^u{Z}^{\prime })$$

Phase 2. $\mathcal{A}$ may query the private key for $I{D}_i\notin S^{*}$.

Guess. $\mathcal{A}$ output a guess ${\beta }^{\prime }$. If ${\beta }^{\prime }$, $\mathcal{A}$ wins the game.

When $T=e{(g_1,g_1)}^{\alpha s}$, $\mathcal{B}$ properly simulates the game ${\mathrm{EX}}_{\mathrm{q}}$. When $T\in G_2$, $\mathcal{B}$ properly simulates the game ${\mathrm{EX}}_{\mathrm{F}}$. Thus, $|\mathrm{Pr}[ℬ(D,T=e{(g_1,g_1)}^{\alpha s})=0]-ℬ(D,T\in G_2)=0]|=|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}}}-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{F}}}|\ge \epsilon$. In other words, as long as $\mathcal{A}$ achieves certain advantages in distinguishing ${\mathrm{EX}}_{\mathrm{q}}$ and ${\mathrm{EX}}_{\mathrm{F}}$, the challenger has the same advantages in destroying Assumption 3. This is not consistent with Assumption 3. So, $|Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{q}}}(L_{SK})-Ad{v}_{\mathcal{A}}^{{\mathrm{EX}}_{\mathrm{F}}}(L_{SK})|<\epsilon$. □ □

As time goes on the leakage must exceed a certain limit, which will damage the security of the system. If the scheme keeps secure against continual side-channel attack, its private key should be refreshed periodically. In fact, through the update algorithm for the private key, our scheme has the function of continual-leakage resilience.

Theorem 2. 

The scheme of CLR-SS-AIBBE has continual-leakage resilience.

Proof. 

Similar to [52], the proposed CLR-SS-AIBBE gains continual leakage resilience through the update algorithm for the private key. The private key updation algorithm inputs $S{K}_{ID,k}$ and $MP$ and generates one new private key $S{K}_{ID,k+1}$. For the private key updation, an additional random number is added to the original one of the private key. Since the newly added value is randomly selected, the new private key has the same distribution with the original one. If private key updates periodically, continual-leakage resilience can be obtained. □

7. Relative Leakage Ratio

The relative leakage ratio of one private key refers to the ratio of the leakage amount of one private key to the length of the private key.

In our proposed scheme, $w_1,w_2$ and $w_3$ are primes with length of $\theta$ bits. This private key has $2\times 2\times 3\theta$ bits. The leakage amount of the private key amounts to $2\times 2(1-2\Lambda )\theta$ bits, where $\Lambda$ is a very small constant value. So, the relative leakage ratio about the private key is $\frac{4(1-2\Lambda )\theta }{12\theta }=\frac{4(1-2\Lambda )}{12}\approx \frac{1}{3}$.

Table 4. Some comparisons related to the proposed scheme and some related schemes given in [51,53].

Schemes	IBBE of [53]	CLR-IBBE of [51]	Our Scheme
Private key size	$6\theta$	$3(n+2)\lambda$	$12\theta$
$\mathrm{Leakage}\mathrm{amount}\mathrm{of}SK$	×	$(n-2\Lambda -1)\lambda$	$4(1-2\Lambda )\theta$
Storage requirement	2	$n+2$	$4$
Private updation	×	√	√
$\mathrm{Leakage}\mathrm{rate}\mathrm{of}SK$	0	$\frac{(n-2\Lambda -1)}{3(n+2)}$	$\frac{4(1-2\Lambda )}{12}\approx \frac{1}{3}$
CLR	×	√	√
Split-state	×	×	√
Anonymity	√	×	√

shows some comparisons about the proposed scheme and some related schemes are given in [51,53]. We will consider the private key size, leakage amount, storage requirement and leakage rate. Ref. [53] gives an anonymous IBBE scheme but does not consider leakage. Ref. [51] proposes a continuous-leakage-resilient (CLR) IBBE scheme (CLR-IBBE), which essentially uses the private key extension technology, but does not consider the anonymity. The scheme given in this paper takes account of both key leakage and anonymity.

From Table 4, we see that the leakage resilience of the given scheme is better than that of [51]. In addition, because the scheme of [51] requires $n\ge 2$, the storage requirement of our scheme is better than that of [51]. In fact, for the scheme of [51], when $n$ is a large value, a high leakage rate can be obtained. For example, when $n=2$, the private key leakage ratio in [51] is $\frac{1}{12}$. When $n=4$, the private key leakage ratio of the scheme [51] is $\frac{1}{6}$. The leakage rate of the scheme in [51] increases with the increase in $n$, but the maximum leakage rate is $\frac{1}{3}$. The essence is that the scheme of [51] obtains certain leakage resilience at the expense of storage space and calculation cost. The scheme of this paper divides the private key into two different states through state partition technology, so that the private key can be properly separated to obtain leakage resilience.

8. Comparisons of Calculation Efficiency

Table 5. Comparisons of the calculation efficiency of our scheme and the schemes of [51,53].

Schemes	Initialization	Private Generation	Private Updation	Encryption	Decryption
[53]	$E+P$	$(d+2)E$	×	$(d+3)E$	$2P$
[51]	$(4n+3m+5)E+P$	$(3n+2d+4)E$	$(3n+d+5)E$	$(n+d+2)E$	$(n+2)P$
Our scheme	$E+P$	$(d+4)E$	$4E$	$(d+3)E$	$4P$

shows the comparisons of the calculation efficiency of our scheme and the schemes of [51,53].

The number of main operations (pairing operation and group exponent operation) is listed in Table 5. $P$ indicates pairing operation. $E$ indicates group exponent operation. $m$ is the max value of the users in the system. $d$ denotes the count of those users in some broadcast. The calculation efficiency of each operation of this presented scheme in this paper is better than that of the scheme in [51]. The encryption and decryption calculation efficiency of our scheme is as good as that of [53], and the efficiency is higher than that of the scheme in [51]. Since the private key is divided into two states, the scheme in this paper has two more exponential operations than the scheme in [53] for the private key generation algorithm. In addition, since the decryption is divided into two stages, the scheme in this paper has two more pairing operations than the scheme in [53].

9. Conclusions

This paper gives the syntax and security description of CLR-SS-AIBBE and proposes a concrete CLR-SS-AIBBE scheme. The private key is continuously updated through state division. The proposed scheme can resist the continual leakage about the private key. The relative leakage rate reaches one-third. Based on the general subgroup decision hypothesis, it is proven that our scheme is secure under the standard model. In addition, through the special treatment of a private key, this given scheme also has the characteristics of anonymity. It has three advantages.

First, our scheme has better application value. Since the adversary in the real environment can carry out continuous-leakage attacks, the continuous-leakage model is closer to the application needs of the real environment. In this paper, the leakage-resilient performance of IBBE mechanism is achieved under the continuous-leakage model, so the scheme is more practical.

Second, our scheme has better user-identity privacy protection. In the identity-based broadcast encryption scheme, broadcasters usually encrypt messages by combining the public identity of the receiver and system parameters. This may reveal the identity of the receiver to the public, which causes users to worry about identity privacy. Most identity-based broadcast encryption (IBBE) schemes are not anonymous, which means that attackers can obtain the identities of all recipients from the ciphertext. The paper provides anonymity and has a good role in protecting user identity privacy.

Third, the given scheme is suitable for some intelligent systems. The public parameter size and private key size of the proposed scheme are constant, and the decryption cost is independent of the number of recipients. Therefore, this scheme requires less computing energy consumption and is very suitable for intelligent city information systems.