# Certificate-Based Encryption Resilient to Continual Leakage in the Standard Model

Authors: Yuyan Guo; Jiguo Li; Mingming Jiang; Lei Yu; Shimin Wei
Journal: Security and Communication Networks
 (2020)

---

## Abstract

The security for many certificate-based encryption schemes was considered under the ideal condition, where the attackers rarely have the secret state for the solutions. However, with a side-channel attack, attackers can obtain partial secret values of the schemes. In order to make the scheme more practical, the security model for the certificate-based encryption which is resilient to continual leakage is first formalized. The attackers in the security model are permitted to get some secret information continuously through the side-channel attack. Based on the certificate-based key encapsulation scheme, a novel certificate-based encryption scheme is proposed, which is resilient to the continual leakage. In the standard model, the new scheme we propose is proved to be secure under the decisional truncatedq-augmented bilinear Diffie–Hellman exponent hard problem and the decisional 1-bilinear Diffie–Hellman inversion hard problem. Additionally, the new scheme can resist the chosen-ciphertext attack. Moreover, a comparison is performed with other related schemes, where the proposed solution further considers the continual leakage-resilient property and exhibits less computation cost.


---

## Body

## 1. Introduction

The certificate-based cryptography (CBC) is a novel public key cryptosystem (PKC) which is proposed by Gentry [1]. CBC combines the traditional PKC and the identity-based cryptosystem to overcome the key escrow and key distribution issues existing in the identity-based cryptosystem, such that the management complexity of the public key certificate can be reduced for the conventional public key infrastructure. In CBC, a public-private key pair will be first generated for every client and applied for a certificate to the trusted certificate authority (CA). Different from the traditional PKC, the CBC provides a hidden certificate mechanism. The certificate of CBC has the function of the traditional public key certificate, and hence it can also be regarded as a part of the secret key for the users [1]. Any user needs to combine his own secret key and certificate to perform decryption or signature operation, and the sender of the message or the signature verifier does not need to pay attention to the certificate status of the communicating party. The implicit certificate mechanism in the CBC eliminates third party inquiries; therefore, CBC offers an efficient method for constructing an efficient and secure public key infrastructure. Due to its good nature, the CBC has been intensively focused on in recent years, and a series of certificate-based encryption (CBE) schemes [2–10] have been proposed. Many certificate-based signature (CBS) proposals [11–14] have also been constructed.Typically, cryptography is considered to be secure ideally, in which the adversaries do not steal the secret values for the cryptographic system. However, the adversaries are able to access partial secret key by side-channel attack. Therefore, a number of approaches are proposed to model the leakage for such side-channel attacks. Micali and Reyzin [15] constructed the “only computation leaks information” model in 2004. Although this model examines a large type of leak attacks, the disadvantage is that it does not consider the case where the information is leaked from the inactive memory parts, e.g., the cold boot attack [16]. To capture more leaks, Halderman et al. [16] proposed a model named “relative leakage.” However, the major disadvantages are obvious; i.e., the secret key does not have sufficient length, and the allowed leakage number is limited. Akavia et al. [17] proposed a “bounded retrieval” model to make the size of the secret key more flexible without increasing the size of the public key and encryption and decryption time. This model is verified to be more powerful than the one with “only computation leaks information.” For the “bounded retrieval” model, the leakage from inactive parts of memory is also taken into account. To further relax the limitations of the secret key-leakage constraint, Dodis et al. [18] and Yang et al. [19] considered the “auxiliary input” model and more kinds of one-way leakage functions. However, the above-mentioned three models do not involve continual leakage attacks. The “continual leakage” model [20–22] was designed to examine attacks where bounded information of the secret internal state is available at the attacker when the cryptographic primitive is invoked.Researchers have been dedicated to finding a provably secure cryptographic solution to deal with the leakage attack problem, with various proposals. In addition, the “continual leakage” model was applied in many encryption schemes, for example, attribute-based encryption (ABE), public key encryption, and identity-based encryption (IBE). A public key encryption approach was made by Agrawal et al. in [23] aiming to cope with the continual leakage. Yuen et al. [24] proposed an IBE system with the aim of being resilient to continual auxiliary input leakage. Zhou et al. [25] constructed an IBE method with tight security which is resilient to the continuous leakage attacks in the standard model. Then, three continuous leakage-resilient IBE methods [26–28] have been put forward. Leakage amplification was proposed in [26] which constructs continuous leakage-resilient secure IBE scheme, which is considered an arbitrary length of the leakage parameter. The authors in [27] offered a new updatable identity-based hash proof system which is adopted to construct the continuous leakage-resilience identity-based cryptosystem. Zhou et al. [28] designed an improved continuous leakage-resilient IBE scheme with arbitrary length of the parameter leakage. Furthermore, Zhou et al. [29] presented an IBE scheme with leakage-amplified chosen-ciphertext attacks security. Li et al. [30–34] extended IBE to present some attribute-based encryption scheme, which can achieve fine-grained access control in cloud storage and can be applied in social network [35]. However, the above attribute-based encryption schemes did not consider key-leakage problem. In order to solve this problem, Zhang [36] delivered a concrete construction for resilient-leakage ciphertext-policy attribute-based encryption (CP-ABE) and provided a key update procedure to support continual leakage tolerance. Zhang et al. [37] proposed a new notion and construction for attribute-based hash proof system (AB-HPS) in the bounded key-leakage model. They also provided the general leakage-resilient attribute-based encryption construction using the AB-HPS as the primitive without indistinguishable obfuscator. Furthermore, Zhang et al. [38] designed the concrete ABE constructions in the bilinear groups with prime order and the security has been shown in the continual memory leakage model. A key-policy attribute-based encryption was defined and modeled by Li et al. [39], which is resilient to the problem of continual auxiliary input leakage. The proposed approach is also shown to have high security under the static assumptions. Li et al. [40] proposed an efficient extended file hierarchy attribute-based encryption scheme, which is very practical and greatly saves storage space and computation cost for those large institutions or companies. Moreover, Li et al. [41] presented a continuous leakage-resilient hierarchical attribute-based encryption scheme, which is shown to be resilient to the master and secret keys leakage. Zhou and Yang [42] presented a continual leakage-resilient certificateless public key encryption scheme which not only tolerates continual leakage attacks, but also achieves better performances. Li et al. [43] provided a continuous leakage-resilient CBE scheme which is proved secure against adaptive chosen-ciphertext attack in the random oracle model. Authenticated key exchange protocol is used to establish a secure communication channel over a public network. However, it has been demonstrated that some standardized AKE protocols suffer from side-channel and key-leakage attacks. In order to defend against these attacks, Chen et al. [44–46] and Yang et al. [47] presented several leakage-resilient authenticated key exchange protocols.


### 1.1. Motivations and Contributions

Currently, there are few researches for the certificate-based encryption resilient to continual leakage. Actually, some previous CBE schemes which have been constructed in the ideal setting may be insecure under the continuous leakage attacks. The main reason is that the adversary can recover the complete secret key via continuously accessing the partial information of the secret key. Therefore, it is meaningful for us to construct a CBE scheme to resist the continual leakage attack.The primary objective of our work is to establish a secure certificate-based encryption scheme which is resilient to continual leakage. Referring to [3–8, 21–25], we design the outline and the security model of CBE resilient to continual leakage. On the basis of the certificate-based key encapsulation method, a CBE scheme is proposed which is shown to be secure in the standard model and can resist the continual leakage attack. The encapsulated symmetric key is randomized using the strong extractor. Furthermore, the encapsulated symmetric key allowing leakage is employed to encrypt the message.The CBE schemes created in [6, 8] only tolerate the leakage. Further, our CBE scheme added the secret key update algorithm to obtain the continuous leakage-resilience. Our approach can resist a larger leakage by performing the secret key updating algorithm, where the keys are periodically updated and the leakage will not be allowed during updates, but only between the updates. We further consider the leakage limit of the encapsulated symmetric key, and the leakage ratio of our scheme is approximately equal to 1.We provide a proof to show that our CBE scheme is secure against chosen-ciphertext attack under the hardness of the decisional truncatedq-augmented bilinear Diffie–Hellman exponent (q-ABDHE) problem and the decisional 1-bilinear Diffie–Hellman inversion (1-BDHI) problem.Compared with the existing CBE schemes, our proposed scheme enhances the continual leakage-resilient property and has a lower communication cost. Therefore, our CBE scheme has obvious advantage. We implement the proposed CBE scheme and the relevant schemes using C++ programming language with the PBC library, and the simulation results show that our scheme has better performance.


### 1.2. Paper Organization

The required preliminary knowledge is presented in Section2. In Section 3, we demonstrate the outline and the security model of CBE resilient to continual leakage. In Section 4, a CBE scheme resilient to continual leakage is proposed. Section 5 provides the proof of our CBE scheme. Then, the comparison in terms of the efficiency is shown in Section 6. Finally, we conclude this work in Section 7.


## 1.1. Motivations and Contributions

Currently, there are few researches for the certificate-based encryption resilient to continual leakage. Actually, some previous CBE schemes which have been constructed in the ideal setting may be insecure under the continuous leakage attacks. The main reason is that the adversary can recover the complete secret key via continuously accessing the partial information of the secret key. Therefore, it is meaningful for us to construct a CBE scheme to resist the continual leakage attack.The primary objective of our work is to establish a secure certificate-based encryption scheme which is resilient to continual leakage. Referring to [3–8, 21–25], we design the outline and the security model of CBE resilient to continual leakage. On the basis of the certificate-based key encapsulation method, a CBE scheme is proposed which is shown to be secure in the standard model and can resist the continual leakage attack. The encapsulated symmetric key is randomized using the strong extractor. Furthermore, the encapsulated symmetric key allowing leakage is employed to encrypt the message.The CBE schemes created in [6, 8] only tolerate the leakage. Further, our CBE scheme added the secret key update algorithm to obtain the continuous leakage-resilience. Our approach can resist a larger leakage by performing the secret key updating algorithm, where the keys are periodically updated and the leakage will not be allowed during updates, but only between the updates. We further consider the leakage limit of the encapsulated symmetric key, and the leakage ratio of our scheme is approximately equal to 1.We provide a proof to show that our CBE scheme is secure against chosen-ciphertext attack under the hardness of the decisional truncatedq-augmented bilinear Diffie–Hellman exponent (q-ABDHE) problem and the decisional 1-bilinear Diffie–Hellman inversion (1-BDHI) problem.Compared with the existing CBE schemes, our proposed scheme enhances the continual leakage-resilient property and has a lower communication cost. Therefore, our CBE scheme has obvious advantage. We implement the proposed CBE scheme and the relevant schemes using C++ programming language with the PBC library, and the simulation results show that our scheme has better performance.


## 1.2. Paper Organization

The required preliminary knowledge is presented in Section2. In Section 3, we demonstrate the outline and the security model of CBE resilient to continual leakage. In Section 4, a CBE scheme resilient to continual leakage is proposed. Section 5 provides the proof of our CBE scheme. Then, the comparison in terms of the efficiency is shown in Section 6. Finally, we conclude this work in Section 7.


## 2. Preliminaries

Definition 1.
LetG and GT denote multiplicative cyclic groups of the prime order p, respectively. A generator of G is represented by g. A bilinear map e if e:G×G⟶GT has the following properties, as(i)
Bilinear:ePa,Qb=eP,Qab for all P,Q∈G and a,b∈ℤp∗(ii)
Nondegenerate:eg,g≠1∈GT(iii)
Computable: the mape is efficiently computable
The security of our CBE scheme is resilient to continual leakage depending on the following problems.Definition 2.
The decisional truncatedq-ABDHE problem is described as follows: given D = g,gα,…,gαq,g′,g′αq+2∈Gq+3, where α,q∈ℤp∗ and T∈GT, output 1 if T=eg,g′αq+1 and 0 otherwise.
The advantage of a probabilistic polynomial time (PPT) adversaryA deciding whether T=eg,g′αq+1 is given as AdvAq−ABDHE = PrAD,eg,g′αq+1=1−PrAD,T=1.
It is said that the decisional truncatedq-ABDHE problem is hard if AdvAq−ABDHE is arbitrarily small for all PPT adversaries A.Definition 3.
We define the decisional 1 − BDHI problem as follows: givenD = g,gα∈G2, where α∈ℤp∗ and T∈GT, output 1 if T=eg,g1/α and 0 otherwise.
The advantage thatA decides whether T=eg,g1/α is given as AdvA1−BDHI = PrAD,eg,g1/α=1−PrAD,T=1.
We say that the decisional 1 − BDHI problem is hard ifAdvA1−BDHI is ignorable for all PPT adversaries A.Definition 4.
The min-entropy of a random variable (RV)X is H∞X=−logmaxxPrX=x.Definition 5.
For RV’sX and Y, the averaged conditional min-entropy is represented by H˜∞XY=−logEy⟵YmaxxPrX=xY=y=−logEy⟵Y2−H∞XY=y with Ey⟵Y denoting the expectation of Y.Lemma 1.
IfX, Y, and Z are random variables such that Y contains 2l (l∈ℕ) potential elements, it has that H∞XY,Z≥H∞XZ−l [48].Definition 6.
The statistical distance between random variablesX and Y is given by SDX,Y=1/2∑xPrX=x−PrY=x, with x∈F, where F denotes a finite field.Definition 7.
A random functionExt :G×0,1μ⟶0,1η is regarded as an average-case m,ε-strong extractor if μ,η∈ℕ, X∈G, m∈ℕ and H˜∞XY≥m for all X, Y, we obtain SDExtX,Uμ,Uμ,Y,Uη,Uμ,Y≤ε, with two variables Uμ and Uη having uniform distributions over 0,1μ,0,1η respectively, and ε being negligible.


## 3. The Outline and Security Model of CBE Resilient to Continual Leakage

### 3.1. The Outline of CBE Resilient to Continual Leakage

The definition of CBE resilient to continual leakage which is referred in references [3–8] includes a group of algorithms, i.e., Setup, UserKeyGen, CertGen, SymmetricKeyGen, Encrypt, Decrypt, and UpdateSK, which are described as follows:Setup: for a security parameter1n (n∈ℕ), the setup process generates a collection of public parameters params and a corresponding master secret key MSKUserKeyGen: for the input identityID, a secret key skID and a public key PKID are produced by the algorithmCertGen: for the inputs params, an identityID, MSK, and PKID, the algorithm generates a certificate CertID, which is transmitted to the userSymmetricKeyGen: taking params,ID, PKID as its input, the algorithm generates the secret symmetric key K and the intermediate state πEncrypt: for the inputs params,ID, PKID, K, π, and the message M, the algorithm returns a ciphertext C=φ,CM on the message M, where φ is the encapsulation of K and CM is the ciphertext of the message M which is encrypted with KDecrypt: for the inputs params,CertID, skID, and C, the algorithm generates K and returns either M via K or ⊥ if C is an invalid ciphertextUpdateSK: for the inputsskID and params, the algorithm produces an updated secret key skID′ where skID′=skID


### 3.2. Security Model for CBE Resilient to Continual Leakage

Inspired by the schemes in references [3–8, 21–25], we propose a security model for the CBE which is resilient to the continual leakage. The model is described through Game-1 and Game-2. We evaluate the security based on these two games resilient to continual leakage and the adaptive chosen-ciphertext attacks (IND-RCL-CCA). In Game-1, an adversary A1 which simulates the uncertified client is able to substitute the public key and obtain the secret key of any client, but A1 does not access the MSK. In Game-2, another adversary A2 which plays an honest-but-curious certifier owns the master key. Such adversary is able to obtain the certificate of any client, but cannot substitute the public keys of any user. The challenger C interacts with A1 and A2 by the following games.


#### 3.2.1. IND-RCL-CCA Game-1

Setup: the challengerC performs the Setup algorithm, keeps the master secret key MSK, and returns params to A1Phase 1:A1 creates the queries adaptively as follows:Public key queries:C holds a list ℒ1=ID,skID,PKID,γ to record both the secret and public keys, where γ∈0,1, γ=0 denotes that PKID has not been substituted, and γ=1 denotes that PKID has been replaced. ℒ1 is initially empty. A1 generates the query for ID, and C seeks ID,skID,PKID,γ from ℒ1. If ID,skID,PKID,γ exists, C returns PKID. Otherwise, UserKeyGen will be used to produce skID,PKID, ID,skID,PKID,0 is inserted into ℒ1 and PKID is returned. For simplicity, for any ID, it is stipulated that A1 must first make the public key query before making any other queries as follows.Public key replacing queries:A1 produces the replace query for ID,PKID′. C looks for ID,•,PKID,· from the list ℒ1. If it is not found, C will insert ID,•,PKID′,1 into ℒ1. Otherwise, C updates the item ID,•,PKID,• to ID,•,PKID′,1.Secret key queries:A1 inputs ID; C checks ID,skID,PKID,γ from ℒ1. If γ=0, C returns skID to A1. Otherwise C outputs ⊥ to A1.Certificate queries:A1 makes the certificate query of ID and gets ID,skID,PKID,γ from ℒ1, and then C runs algorithm CertGen and outputs CertID to A1.Leakage queries:C generates a list ℒ2 in which the form of the item is ID,K,cnt, where cnt∈ℕ and K is utilized for encrypting the message as the symmetric key. ℒ2 is initially empty. C finds ID,K,cnt in the list ℒ2. If the item does not exist, C will add ID,K,0 into ℒ2. If ID,K,cnt is found or after this step, C will check the condition cnt+li≤l, where l,i∈ℕ. If not, C returns ⊥. Otherwise, C selects a leakage function fi:GT⟶0,1li, sets cnt⟵cnt+li for ID,K,cnt, and outputs fiK to A1.Decryption queries: For queries onID and the ciphertext C, C obtains ID,skID,PKID,γ from ℒ1; if γ=1, A1 has to provide the corresponding secret key; otherwise, C gets skID from ℒ1. C makes the certificate queries to get CertID and applies Decrypt algorithm to obtain the symmetric key K and uses K to decrypt C. The challenger C returns either M or ⊥ to A1.Challenge:A1 gives two messages M0, M1 of equal length and a target identity ID∗ to C with the following restriction: A1 is prohibited from issuing the certificate query for ID∗ and does not replace the public key of ID∗. C executes the SymmetricKeyGen algorithm to get a symmetric key K1∗ and randomly chooses K0∗∈GT. C chooses β∈0,1 and σ∗∈0,1μ uniformly at random, runs the Encrypt algorithm to encrypt Mβ for ID∗, and yields the encapsulation φ∗ of Kβ∗ and the challenge ciphertext C∗=φ∗,CMβ∗,σ∗ to A1, where CMβ∗=ExtKβ∗,σ∗⊕Mβ.Phase 2:A1 continually makes the queries similar to Phase 1 with the following constraints: A1 is prohibited from making the certificate queries for ID∗, as well as the decryption queries on ID∗,C∗.Guess:A1 returns a bit β′∈0,1. We say that A1 wins the game if β′=β.The advantage ofA1 winning the IND-RCL-CCA Game-1 is described as AdvA1IND−RCL−CCA=2PrA1wins−1.


#### 3.2.2. IND-RCL-CCA Game-2

Setup: the challengerC performs the Setup algorithm and returns the master secret key MSK and params to A2.Phase 1:A2 adaptively inquires C for the following queries.Public key queries:C holds a list ℒ1=ID,skID,PKID to record the secret keys and the public keys. ℒ1 is empty in the initial step of the game. For the queries about ID, C finds a tuple ID,skID,PKID from ℒ1. If it exists, C returns PKID to A2. Otherwise, C uses UserKeyGen to produce skID and PKID, inserts ID,skID,PKID into ℒ1, and returns PKID to A2. For simplicity, for any ID, it is stipulated that A2 must first make the public key query before making any other queries as follows.Secret key queries: For a secret key query underID, C seeks ID,skID,PKID from the list ℒ1 and returns skID to A2.Leakage queries:C generates a list ℒ2 in which the form of the item is ID,K,cnt, where cnt∈ℕ and K represents the symmetric key which is adopted to encrypt the message. ℒ2 is initially empty. C finds ID,K,cnt from the list ℒ2. If the item does not exist, C inserts an item ID,K,0 into the list ℒ2. Following this step or if the item exists, C decides whether cnt+li≤l where l,i∈ℕ. If not, C returns ⊥. Otherwise, C selects a leakage function fi:GT⟶0,1li, sets cnt⟵cnt+li for ID,K,cnt, and outputs fiK to A2.Decryption queries: for queries onID and ciphertext C, C obtains ID,skID,PKID,γ from ℒ1. C conducts the CertGen algorithm to obtain CertID, then performs Decrypt algorithm to obtain the symmetric key K, and adopts K to decrypt C. The challenger C returns either M or ⊥ to A2.Challenge:A2 gives two messages M0 and M1 with an equal length and a target identity ID∗ to C with the following restrictions: A2 is not allowed to issue the secret key query for ID∗. C runs the SymmetricKeyGen algorithm to get a symmetric key K1∗ and randomly chooses K0∗∈GT. C randomly selects β∈0,1 and σ∗∈0,1μ from the uniform distribution, runs the Encrypt algorithm to encrypt Mβ for ID∗, and produces the encapsulation φ∗ of Kβ∗ and the challenge ciphertext C∗=φ∗,CMβ∗,σ∗ to A2, where CMβ∗=ExtKβ∗,σ∗⊕Mβ.Phase 2: similar to Phase 1, the queries will be continuously made byA2 under the following constraints: A2 is prohibited from making the secret key queries for ID∗ and the decryption queries on ID∗,C∗.Guess:A2 returns a bit β′∈0,1. We say that A2 wins the game if β′=β.The advantage ofA2 winning the IND-RCL-CCA Game-2 is defined to be AdvA2IND−RCL−CCA=2PrA2wins−1.Definition 8.
A CBE scheme resilient to continual leakage is regarded to be secure under the adaptive chosen-ciphertext attacks, if no PPT adversary has non-negligible advantage in the IND-RCL-CCA Game-1 and IND-RCL-CCA Game-2.


## 3.1. The Outline of CBE Resilient to Continual Leakage

The definition of CBE resilient to continual leakage which is referred in references [3–8] includes a group of algorithms, i.e., Setup, UserKeyGen, CertGen, SymmetricKeyGen, Encrypt, Decrypt, and UpdateSK, which are described as follows:Setup: for a security parameter1n (n∈ℕ), the setup process generates a collection of public parameters params and a corresponding master secret key MSKUserKeyGen: for the input identityID, a secret key skID and a public key PKID are produced by the algorithmCertGen: for the inputs params, an identityID, MSK, and PKID, the algorithm generates a certificate CertID, which is transmitted to the userSymmetricKeyGen: taking params,ID, PKID as its input, the algorithm generates the secret symmetric key K and the intermediate state πEncrypt: for the inputs params,ID, PKID, K, π, and the message M, the algorithm returns a ciphertext C=φ,CM on the message M, where φ is the encapsulation of K and CM is the ciphertext of the message M which is encrypted with KDecrypt: for the inputs params,CertID, skID, and C, the algorithm generates K and returns either M via K or ⊥ if C is an invalid ciphertextUpdateSK: for the inputsskID and params, the algorithm produces an updated secret key skID′ where skID′=skID


## 3.2. Security Model for CBE Resilient to Continual Leakage

Inspired by the schemes in references [3–8, 21–25], we propose a security model for the CBE which is resilient to the continual leakage. The model is described through Game-1 and Game-2. We evaluate the security based on these two games resilient to continual leakage and the adaptive chosen-ciphertext attacks (IND-RCL-CCA). In Game-1, an adversary A1 which simulates the uncertified client is able to substitute the public key and obtain the secret key of any client, but A1 does not access the MSK. In Game-2, another adversary A2 which plays an honest-but-curious certifier owns the master key. Such adversary is able to obtain the certificate of any client, but cannot substitute the public keys of any user. The challenger C interacts with A1 and A2 by the following games.


### 3.2.1. IND-RCL-CCA Game-1

Setup: the challengerC performs the Setup algorithm, keeps the master secret key MSK, and returns params to A1Phase 1:A1 creates the queries adaptively as follows:Public key queries:C holds a list ℒ1=ID,skID,PKID,γ to record both the secret and public keys, where γ∈0,1, γ=0 denotes that PKID has not been substituted, and γ=1 denotes that PKID has been replaced. ℒ1 is initially empty. A1 generates the query for ID, and C seeks ID,skID,PKID,γ from ℒ1. If ID,skID,PKID,γ exists, C returns PKID. Otherwise, UserKeyGen will be used to produce skID,PKID, ID,skID,PKID,0 is inserted into ℒ1 and PKID is returned. For simplicity, for any ID, it is stipulated that A1 must first make the public key query before making any other queries as follows.Public key replacing queries:A1 produces the replace query for ID,PKID′. C looks for ID,•,PKID,· from the list ℒ1. If it is not found, C will insert ID,•,PKID′,1 into ℒ1. Otherwise, C updates the item ID,•,PKID,• to ID,•,PKID′,1.Secret key queries:A1 inputs ID; C checks ID,skID,PKID,γ from ℒ1. If γ=0, C returns skID to A1. Otherwise C outputs ⊥ to A1.Certificate queries:A1 makes the certificate query of ID and gets ID,skID,PKID,γ from ℒ1, and then C runs algorithm CertGen and outputs CertID to A1.Leakage queries:C generates a list ℒ2 in which the form of the item is ID,K,cnt, where cnt∈ℕ and K is utilized for encrypting the message as the symmetric key. ℒ2 is initially empty. C finds ID,K,cnt in the list ℒ2. If the item does not exist, C will add ID,K,0 into ℒ2. If ID,K,cnt is found or after this step, C will check the condition cnt+li≤l, where l,i∈ℕ. If not, C returns ⊥. Otherwise, C selects a leakage function fi:GT⟶0,1li, sets cnt⟵cnt+li for ID,K,cnt, and outputs fiK to A1.Decryption queries: For queries onID and the ciphertext C, C obtains ID,skID,PKID,γ from ℒ1; if γ=1, A1 has to provide the corresponding secret key; otherwise, C gets skID from ℒ1. C makes the certificate queries to get CertID and applies Decrypt algorithm to obtain the symmetric key K and uses K to decrypt C. The challenger C returns either M or ⊥ to A1.Challenge:A1 gives two messages M0, M1 of equal length and a target identity ID∗ to C with the following restriction: A1 is prohibited from issuing the certificate query for ID∗ and does not replace the public key of ID∗. C executes the SymmetricKeyGen algorithm to get a symmetric key K1∗ and randomly chooses K0∗∈GT. C chooses β∈0,1 and σ∗∈0,1μ uniformly at random, runs the Encrypt algorithm to encrypt Mβ for ID∗, and yields the encapsulation φ∗ of Kβ∗ and the challenge ciphertext C∗=φ∗,CMβ∗,σ∗ to A1, where CMβ∗=ExtKβ∗,σ∗⊕Mβ.Phase 2:A1 continually makes the queries similar to Phase 1 with the following constraints: A1 is prohibited from making the certificate queries for ID∗, as well as the decryption queries on ID∗,C∗.Guess:A1 returns a bit β′∈0,1. We say that A1 wins the game if β′=β.The advantage ofA1 winning the IND-RCL-CCA Game-1 is described as AdvA1IND−RCL−CCA=2PrA1wins−1.


### 3.2.2. IND-RCL-CCA Game-2

Setup: the challengerC performs the Setup algorithm and returns the master secret key MSK and params to A2.Phase 1:A2 adaptively inquires C for the following queries.Public key queries:C holds a list ℒ1=ID,skID,PKID to record the secret keys and the public keys. ℒ1 is empty in the initial step of the game. For the queries about ID, C finds a tuple ID,skID,PKID from ℒ1. If it exists, C returns PKID to A2. Otherwise, C uses UserKeyGen to produce skID and PKID, inserts ID,skID,PKID into ℒ1, and returns PKID to A2. For simplicity, for any ID, it is stipulated that A2 must first make the public key query before making any other queries as follows.Secret key queries: For a secret key query underID, C seeks ID,skID,PKID from the list ℒ1 and returns skID to A2.Leakage queries:C generates a list ℒ2 in which the form of the item is ID,K,cnt, where cnt∈ℕ and K represents the symmetric key which is adopted to encrypt the message. ℒ2 is initially empty. C finds ID,K,cnt from the list ℒ2. If the item does not exist, C inserts an item ID,K,0 into the list ℒ2. Following this step or if the item exists, C decides whether cnt+li≤l where l,i∈ℕ. If not, C returns ⊥. Otherwise, C selects a leakage function fi:GT⟶0,1li, sets cnt⟵cnt+li for ID,K,cnt, and outputs fiK to A2.Decryption queries: for queries onID and ciphertext C, C obtains ID,skID,PKID,γ from ℒ1. C conducts the CertGen algorithm to obtain CertID, then performs Decrypt algorithm to obtain the symmetric key K, and adopts K to decrypt C. The challenger C returns either M or ⊥ to A2.Challenge:A2 gives two messages M0 and M1 with an equal length and a target identity ID∗ to C with the following restrictions: A2 is not allowed to issue the secret key query for ID∗. C runs the SymmetricKeyGen algorithm to get a symmetric key K1∗ and randomly chooses K0∗∈GT. C randomly selects β∈0,1 and σ∗∈0,1μ from the uniform distribution, runs the Encrypt algorithm to encrypt Mβ for ID∗, and produces the encapsulation φ∗ of Kβ∗ and the challenge ciphertext C∗=φ∗,CMβ∗,σ∗ to A2, where CMβ∗=ExtKβ∗,σ∗⊕Mβ.Phase 2: similar to Phase 1, the queries will be continuously made byA2 under the following constraints: A2 is prohibited from making the secret key queries for ID∗ and the decryption queries on ID∗,C∗.Guess:A2 returns a bit β′∈0,1. We say that A2 wins the game if β′=β.The advantage ofA2 winning the IND-RCL-CCA Game-2 is defined to be AdvA2IND−RCL−CCA=2PrA2wins−1.Definition 8.
A CBE scheme resilient to continual leakage is regarded to be secure under the adaptive chosen-ciphertext attacks, if no PPT adversary has non-negligible advantage in the IND-RCL-CCA Game-1 and IND-RCL-CCA Game-2.


## 3.2.1. IND-RCL-CCA Game-1

Setup: the challengerC performs the Setup algorithm, keeps the master secret key MSK, and returns params to A1Phase 1:A1 creates the queries adaptively as follows:Public key queries:C holds a list ℒ1=ID,skID,PKID,γ to record both the secret and public keys, where γ∈0,1, γ=0 denotes that PKID has not been substituted, and γ=1 denotes that PKID has been replaced. ℒ1 is initially empty. A1 generates the query for ID, and C seeks ID,skID,PKID,γ from ℒ1. If ID,skID,PKID,γ exists, C returns PKID. Otherwise, UserKeyGen will be used to produce skID,PKID, ID,skID,PKID,0 is inserted into ℒ1 and PKID is returned. For simplicity, for any ID, it is stipulated that A1 must first make the public key query before making any other queries as follows.Public key replacing queries:A1 produces the replace query for ID,PKID′. C looks for ID,•,PKID,· from the list ℒ1. If it is not found, C will insert ID,•,PKID′,1 into ℒ1. Otherwise, C updates the item ID,•,PKID,• to ID,•,PKID′,1.Secret key queries:A1 inputs ID; C checks ID,skID,PKID,γ from ℒ1. If γ=0, C returns skID to A1. Otherwise C outputs ⊥ to A1.Certificate queries:A1 makes the certificate query of ID and gets ID,skID,PKID,γ from ℒ1, and then C runs algorithm CertGen and outputs CertID to A1.Leakage queries:C generates a list ℒ2 in which the form of the item is ID,K,cnt, where cnt∈ℕ and K is utilized for encrypting the message as the symmetric key. ℒ2 is initially empty. C finds ID,K,cnt in the list ℒ2. If the item does not exist, C will add ID,K,0 into ℒ2. If ID,K,cnt is found or after this step, C will check the condition cnt+li≤l, where l,i∈ℕ. If not, C returns ⊥. Otherwise, C selects a leakage function fi:GT⟶0,1li, sets cnt⟵cnt+li for ID,K,cnt, and outputs fiK to A1.Decryption queries: For queries onID and the ciphertext C, C obtains ID,skID,PKID,γ from ℒ1; if γ=1, A1 has to provide the corresponding secret key; otherwise, C gets skID from ℒ1. C makes the certificate queries to get CertID and applies Decrypt algorithm to obtain the symmetric key K and uses K to decrypt C. The challenger C returns either M or ⊥ to A1.Challenge:A1 gives two messages M0, M1 of equal length and a target identity ID∗ to C with the following restriction: A1 is prohibited from issuing the certificate query for ID∗ and does not replace the public key of ID∗. C executes the SymmetricKeyGen algorithm to get a symmetric key K1∗ and randomly chooses K0∗∈GT. C chooses β∈0,1 and σ∗∈0,1μ uniformly at random, runs the Encrypt algorithm to encrypt Mβ for ID∗, and yields the encapsulation φ∗ of Kβ∗ and the challenge ciphertext C∗=φ∗,CMβ∗,σ∗ to A1, where CMβ∗=ExtKβ∗,σ∗⊕Mβ.Phase 2:A1 continually makes the queries similar to Phase 1 with the following constraints: A1 is prohibited from making the certificate queries for ID∗, as well as the decryption queries on ID∗,C∗.Guess:A1 returns a bit β′∈0,1. We say that A1 wins the game if β′=β.The advantage ofA1 winning the IND-RCL-CCA Game-1 is described as AdvA1IND−RCL−CCA=2PrA1wins−1.


## 3.2.2. IND-RCL-CCA Game-2

Setup: the challengerC performs the Setup algorithm and returns the master secret key MSK and params to A2.Phase 1:A2 adaptively inquires C for the following queries.Public key queries:C holds a list ℒ1=ID,skID,PKID to record the secret keys and the public keys. ℒ1 is empty in the initial step of the game. For the queries about ID, C finds a tuple ID,skID,PKID from ℒ1. If it exists, C returns PKID to A2. Otherwise, C uses UserKeyGen to produce skID and PKID, inserts ID,skID,PKID into ℒ1, and returns PKID to A2. For simplicity, for any ID, it is stipulated that A2 must first make the public key query before making any other queries as follows.Secret key queries: For a secret key query underID, C seeks ID,skID,PKID from the list ℒ1 and returns skID to A2.Leakage queries:C generates a list ℒ2 in which the form of the item is ID,K,cnt, where cnt∈ℕ and K represents the symmetric key which is adopted to encrypt the message. ℒ2 is initially empty. C finds ID,K,cnt from the list ℒ2. If the item does not exist, C inserts an item ID,K,0 into the list ℒ2. Following this step or if the item exists, C decides whether cnt+li≤l where l,i∈ℕ. If not, C returns ⊥. Otherwise, C selects a leakage function fi:GT⟶0,1li, sets cnt⟵cnt+li for ID,K,cnt, and outputs fiK to A2.Decryption queries: for queries onID and ciphertext C, C obtains ID,skID,PKID,γ from ℒ1. C conducts the CertGen algorithm to obtain CertID, then performs Decrypt algorithm to obtain the symmetric key K, and adopts K to decrypt C. The challenger C returns either M or ⊥ to A2.Challenge:A2 gives two messages M0 and M1 with an equal length and a target identity ID∗ to C with the following restrictions: A2 is not allowed to issue the secret key query for ID∗. C runs the SymmetricKeyGen algorithm to get a symmetric key K1∗ and randomly chooses K0∗∈GT. C randomly selects β∈0,1 and σ∗∈0,1μ from the uniform distribution, runs the Encrypt algorithm to encrypt Mβ for ID∗, and produces the encapsulation φ∗ of Kβ∗ and the challenge ciphertext C∗=φ∗,CMβ∗,σ∗ to A2, where CMβ∗=ExtKβ∗,σ∗⊕Mβ.Phase 2: similar to Phase 1, the queries will be continuously made byA2 under the following constraints: A2 is prohibited from making the secret key queries for ID∗ and the decryption queries on ID∗,C∗.Guess:A2 returns a bit β′∈0,1. We say that A2 wins the game if β′=β.The advantage ofA2 winning the IND-RCL-CCA Game-2 is defined to be AdvA2IND−RCL−CCA=2PrA2wins−1.Definition 8.
A CBE scheme resilient to continual leakage is regarded to be secure under the adaptive chosen-ciphertext attacks, if no PPT adversary has non-negligible advantage in the IND-RCL-CCA Game-1 and IND-RCL-CCA Game-2.


## 4. Our CBE Scheme Resilient to Continual Leakage

Inspired by the schemes in [3–8, 22, 49], a strong extractor technology is proposed in [48] with a CBE scheme which is resilient to the continual leakage. Seven related algorithms are introduced as follows:Setup: Define two groupsG and GT with prime order p. A bilinear mapping is given by e:G×G⟶GT. Let l=ln be a bound of all leakages. In this procedure, an average scenario is selected with logGT−l,εExt-strong extractor Ext:GT×0,1μ⟶0,1η where μ,η∈ℕ, and two collision resistant hash functions H1:0,1∗×G3⟶ℤp∗ and H2:G×GT⟶ℤp∗ are chosen. The message space is ℳ=0,1η. The algorithm uses random value α∈ℤp∗, h1,h2∈G, and computes g1=gα and gT=eg,g, with g being a generator of G. It outputs the master secret key MSK=α and a tuple of public parameter params=p,G,GT,g,g1,gT,h1,h2,e,H1,H2,Ext.UserKeyGen: given params, the algorithm picks random numberss1,s2∈ℤp∗, and sets the secret key skID=s1,s2 for the user ID; then it computes the public key PKID=PKID1,PKID2,PKID3=g1s1,gs1,gs2.CertGen: given params, MSK,ID, and PKID, the CertGen algorithm computes ρ=H1ID,PKID, selects random numbers x1,x2∈ℤp∗, computes d1=h1g−x11/α−ρ and d2=h2g−x21/α−ρ, and outputs CertID=CertID1,CertID2,CertID3,CertID4=x1,d1,x2,d2.SymmetricKeyGen: Given params,ID, PKID, the SymmetricKeyGen algorithm computes ρ=H1ID,PKID, selects random number r∈ℤp∗, and computes C1=PKID1⋅PKID2−ρr and C2=gTr. Then, it outputs the secret symmetric key K=eg,h1⋅PKID2φ⋅eg,h2⋅PKID3r where φ=H2C1,C2 and the intermediate state π=C1,C2.Encrypt: Given params,ID, PKID, K, π=C1,C2, and the message M, the algorithm selects a random value σ∈0,1μ and calculates C3=ExtK,σ⊕M. It sets C4=σ and returns the ciphertext C=C1,C2,C3,C4.Decrypt: Given params,CertID, skID=s1,s2, and C=C1,C2,C3,C4, the algorithm computes φ=H2C1,C2, generates K=eC1,CertID2φ⋅CertID41/s1⋅C2φ⋅CertID1+CertID3+φ⋅s1+s2, and returns M=C3⊕ExtK,C4.UpdateSK: GivenskID=s1,s2, the secret key updating algorithm randomly selects s1′∈ℤp∗ and s2′∈ℤp∗. It then generates a new secret key skID′=s1⋅s1′,s2⋅s2′.Correctness of our scheme.K=eC1,CertID2φ⋅CertID41/s1⋅C2φ⋅CertID1+CertID3+φ⋅s1+s2=eg1s1⋅g−ρs1r,h1g−x11/α−ρφ⋅h2g−x21/α−ρ1/s1⋅eg,grφx1+x2+φs1+s2=eg,h1g−x1φ⋅h2g−x2r⋅eg,grφx1+x2+φs1+s2=eg,h1⋅PKID2φeg,h2⋅PKID3rWe haveC3⊕ExtK,C4=ExtK,σ⊕M⊕ExtK,σ=M.


## 5. Security Analysis

Our CBE approaches resilient to continual leakage are proved to be secure under the standard model as follows.Theorem 1.
If there is a PPT adversaryA1 against the CBE scheme resilient to continual leakage with advantage ε that makes at most qc certificate queries, qd decryption queries in the case of l bits entropy leakage for the symmetric key, then there exists a PPT algorithm B against the q-ABDHE problem with an advantage ε, where q=qc+qd+1.Proof.
GivenGT,G,p,e,g,gα,…,gαq,g′,g′αq+2,T, the algorithm B can be regarded as the challenger C of IND-RCL-CCA Game-1 to interact with A1; the target of B is to decide whether T=eg,g′αq+1.Setup: The algorithmB sets g1=gα and computes gT=eg,g; B randomly chooses two q-degree unary polynomials f1x,f2x∈Zpx, and computes h1=gf1α and h2=gf2α (B can compute h1,h2 based g,gα,…,gαq). Two collision resistant hash functions are chosen by B, i.e., H1:0,1∗×G3⟶ℤp∗, H2:G×GT⟶ℤp∗ and an average-case logGT−l,εExt-strong extractor Ext:GT×0,1μ⟶0,1η, μ,η∈ℕ, and sends params=p,G,GT,g,g1,gT,h1,h2,e,H1,H2,Ext to A1.Phase 1:A1 makes the following queries adaptively:Public key queries:A1 inputs ID; B seeks ID,skID,PKID,γ from ℒ1. If it exists, B returns PKID. Otherwise, B randomly picks skID=s1,s2∈ℤp∗×ℤp∗, computes PKID=g1s1,gs1,gs2, inserts ID,skID,PKID,0 into ℒ1, and returns PKID.Public key replace queries:A1 makes the query for ID,PKID′ where PKID′=PKID′1,PKID′2,PKID′3. B checks whether eg,PKID′1=ePKID′2,g1. If it is not true, B outputs ⊥, which denotes that this replace query is invalid. Otherwise, B seeks ID,•,PKID,• from ℒ1; if it is not found, B inserts ID,•,PKID′,1 into ℒ1; otherwise, B updates ID,•,PKID,• to ID,•,PKID′,1.Secret key queries:A1 inputs ID; B checks ID,skID,PKID,γ from ℒ1. If γ=0, B returns skID to A1. Otherwise, B outputs ⊥ to A1.Certificate queries:A1 inputs ID; B gets ID,skID,PKID,γ from ℒ1 and defines two polynomials F1IDx=f1x−f1ρ/x−ρ and F2IDx=f2x−f2ρ/x−ρ, where ρ=H1ID,PKID. B computes CertID=f1ρ,gF1IDα,f2ρ,gF2IDα and outputs CertID to A1 (obviously, B can compute gF1IDα,gF2IDα based g,gα,…,gαq. Due to gF1IDα=h1g−f1ρ1/α−ρ and gF2IDα=h2g−f2ρ1/α−ρ, therefore CertID is a valid certificate).Leakage queries:A1 inputs ID; B finds ID,K,cnt from ℒ2. B adds ID,K,0 into ℒ2 if the item does not exist. If it exists, or in the next step, B decides whether cnt+li≤l, where l∈ℕ is the upper bound of the allowed leak. If not, B returns ⊥. Otherwise, B selects a leakage function fi:GT⟶0,1li, sets cnt⟵cnt+li for ID,K,cnt, and outputs fiK to A1.Decryption queries: For queries onID and the ciphertext C=C1,C2,C3,C4, B obtains ID,skID,PKID,γ from ℒ1; if γ=1, A1 has to provide the corresponding secret key; otherwise, B gets the secret key skID=s1,s2 from ℒ1. B makes the certificate queries to gain the certificate CertID=CertID1,CertID2,CertID3,CertID4; then he computes the symmetric key K=eC1,CertID2γ⋅CertID41/s1⋅C2φγ⋅CertID1+CertID3+φ⋅s1+s2 where φ=H2C1,C2 and M=C3⊕ExtK,C4. Finally, B returns either M or ⊥ to A1.Challenge:A1 provides B with two identical-length messages M0 and M1, and a target identity ID∗ with the following restrictions: A1 is prohibited from issuing certificate queries for ID∗ and does not replace the public key of ID∗. B defines a q + 1-degree polynomial F∗x=xq+2−ρ∗q+2/x−ρ∗=∑i=0q+1Fi∗⋅xi, where Fi∗ is the i-term coefficient of F∗x. B computes C1∗=g′αq+2⋅g′−ρ∗q+2s1∗, C2∗=TFq+1∗⋅e∏i=0qgαiFi∗,g′, where ρ∗=H1ID∗,PKID∗ and skID∗=s1∗,s2∗. B then computes K1∗=eC1∗,CertID∗2φ∗⋅CertID∗41/s1∗⋅C2∗φ∗⋅CertID∗1+CertID∗3+φ⋅∗s1∗+s2∗ where φ∗=H2C1∗,C2∗. B randomly selects K0∗∈GT, β∈0,1 and σ∗∈0,1μ, sets CMβ∗=ExtKβ∗,σ∗⊕Mβ, C4∗=σ∗, and produces the challenge ciphertext Cβ∗=C1∗,C2∗,CMβ∗,C4∗ to A1.Phase 2:A1 continues making the queries as in Phase 1 with the following restriction: A1 has no permission to issue certificate queries for ID∗, as well as the decryption queries on ID∗,C∗.Guess:A1 returns the guess β′∈0,1. If β′=β holds, B will output 1, indicating that T=eg,g′αq+1. Otherwise, B outputs 0, indicating that T≠eg,g′αq+1.


### 5.1. Probability analysis

IfT=eg,g′αq+1, we set r∗=loggg′⋅F∗α, and we have C1∗=g′αq+2⋅g′−ρ∗q+2s1∗=gs1∗⋅loggg′⋅αq+2−ρ∗q+2=gs1∗⋅r∗⋅α−ρ∗=PKID∗1⋅PKID∗2−ρ∗r∗, C2∗=TFq+1∗⋅e∏i=0qgαiFi∗,g′=eg,g′αq+1Fq+1∗⋅e∏i=0qgαiFi∗,g′=eg,gloggg′⋅∑i=0q+1αiFi∗=gTr∗. Thus, Cβ∗=C1∗,C2∗,CMβ∗,C4∗ is a valid ciphertext, A1 outputs correct β′=β with the advantage 2PrA1wins−1≥ε. If T∈GT is a random value, Cβ∗=C1∗,C2∗,CMβ∗,C4∗ is not a valid ciphertext; it cannot provide useful information for the guess of A1. Thus, A1 outputs correct β′=β with the advantage PrA1wins=1/2.Thus,B breaks the q-ABDHE problem with advantage PrBg,gα,…,gαq,g′,g′αq+2,eg,g′αq+1=1−PrBg,gα,…,gαq,g′,g′αq+2,T=1≥1/2±ε−1/2=ε.Theorem 2.
If there is a PPT adversaryA2 against the CBE scheme resilient to continual leakage with advantage ε that makes at most qsk secret key queries, qd decryption queries with l bits entropy leakage for the symmetric key, then there exists a PPT algorithm B against the 1-BDHI problem with advantage ε′≥ε/qsk.Proof.
GivenGT,G,p,e,g,gα,T, the algorithm B performs as the challenger C of IND-RCL-CCA Game-2 to interact with A2; the target of B is to decide whether T=eg,g1/α.Setup: the algorithmB randomly picks x,z,x1,x2∈ℤp∗ and computes g1=gx, gT=eg,g, h1=gx1 and h2=gx2. B chooses two collision resistant hash functions H1:0,1∗×G3⟶ℤp∗, H2:G×GT⟶ℤp∗, and an average-case logGT−l,εExt-strong extractor Ext:GT×0,1μ⟶0,1η, μ,η∈ℕ, and sends params=p,G,GT,g,g1,gT,h1,h2,e,H1,H2,Ext and MSK = x to A2.Phase 1:A2 asks B for queries adaptively as follows:Public key queries:A2 inputs IDi; B randomly chooses I∈1,qsk. B checks the tuple IDi,skIDi,PKIDi from the ℒ1. If it exists, B returns PKIDi to A2. Otherwise, if IDi≠IDI, B randomly picks skIDi=s1,s2∈ℤp∗×ℤp∗, computes PKIDi=g1s1,gs1,gs2, inserts the tuple IDi,skIDi,PKIDi into ℒ1, and returns PKIDi; if IDi=IDI, B sets PKIDI=gαx,gα,gz, inserts the tuple IDI,skIDI,• into ℒ1, and outputs PKIDI to A2.Secret key queries: For a secret key query underIDi, if IDi≠IDI, B seeks IDi,skIDi,PKIDi from the list ℒ1 and returns skIDi to A2; otherwise, B ends the game and outputs a failure information.Leakage queries:A2 inputs ID; B finds ID,K,cnt from ℒ2. If the item does not exist, B adds ID,K,0 into ℒ2. If the item exists, or in the next step, B decides whether cnt+li≤l where l,i∈ℕ. If not, B returns ⊥. Otherwise, B sets cnt⟵cnt+li for ID,K,cnt and returns fiK to A2, where fi is a leakage function and fi:GT⟶0,1li.Decryption queries: For queries onIDi and ciphertext C=C1,C2,C3,C4. If IDi≠IDI, B obtains the secret key skIDi and certificate CertIDi of IDi; then B obtains the symmetric key K and uses K to decrypt C. Otherwise, B computes the symmetric key K=eC1,gφ/x−ρI⋅C2φ⋅x1+x2+z where φ=H2C1,C2 and ρI=H1IDI,PKIDI and computes M=C3⊕ExtK,C4. B returns either M or ⊥ to A2.Challenge:M0 provides B with two identical-length messages M1 and ID∗ and a target identity A2 with the following restriction: ID∗ is not allowed to issue the secret key queries for ID∗≠IDI. If r∈ℤp∗, B ends the game and outputs failure. Otherwise, B will randomly select C1∗=g1⋅g−ρ∗r and compute C2∗=Tr, ρ∗=H1IDI,PKIDI, where T=eg,g1/α and β∈0,1. B randomly selects σ∗∈0,1μ and K1∗=Trφ∗x1+x2+z⋅eg,gφ∗r and computes φ∗=H2C1∗,C2∗ where K0∗∈GT. B randomly chooses β∈0,1, σ∗∈0,1μ, and CMβ∗=ExtKβ∗,σ∗⊕Mβ, sets C4∗=σ∗, Cβ∗=C1∗,C2∗,CMβ∗,C4∗, and outputs the challenge ciphertext A2 to A2.Phase 2:A2 continues making the queries which is similar to Phase 1 under the following restriction: ID∗ has no permission to perform secret key queries for ID∗,C∗, as well as the decryption queries on A2.Guess:β′∈0,1 returns the guess β′=β. If T=eg,g1/α holds, B outputs 1, indicating that T≠eg,g1/α. Otherwise, B outputs 0, which indicates T=eg,g1/α.


### 5.2. Probability analysis

Ifr∗=r/α, we set , and we have C1∗=g1⋅g−ρ∗r=g1⋅g−ρ∗αr∗=PKIDI1⋅PKIDI2−ρ∗r∗, C2∗=Tr=eg,g1/ααr∗=gTr∗. K1∗=Trφ∗x1+x2+z⋅eg,gφ∗r=eg,gφ∗x1+x2+zr∗⋅eg,gφ∗αr∗=eg,h1⋅PKID∗2φ∗⋅eg,h2⋅PKID∗3r∗. Thus, Cβ∗=C1∗,C2∗,CMβ∗,C4∗ is a valid ciphertext; A2 outputs correct β′=β with the advantage 2PrA2wins−1≥ε. If T∈GT is a random value, Cβ∗=C1∗,C2∗,CMβ∗,C4∗ is an invalid ciphertext; it cannot provide useful information for the guess of A2. Thus, A2 outputs correct β′=β with the advantage PrA2wins=1/2.Thus,B breaks the 1-BDHI problem with advantage PrBg,gα,eg,g1/α=1−PrBg,gα,T=1≥1/2±ε−1/2=ε. Furthermore, the probability that A2 chooses IDI as the target identity is 1/qsk. Therefore B breaks the 1-BDHI problem with advantage ε′≥ε/qsk.


### 5.3. Leakage Ratio Analysis

We mainly consider the leakage of the symmetric keyK. Firstly, a set Z is defined which consists of public parameters, secret keys, and certificates. As an adversary, A acquires at most l bits for leakage of the symmetric key K. Based on Lemma 1, we have H˜∞ALeak,Z≥H˜∞AZ−l=logGT−l, where Leak has 2l possible values and l∈ℕ is the leakage length. If we pick the average-case logGT−l,εExt-strong extractor where εExt is negligible, we know that SDExtX,Uμ,Uμ,Y,Uη,Uμ,Y≤ε, where Uμ and Uη have uniform distributions over 0,1μ,0,1η, respectively. Thus, the ciphertext C3=ExtK,σ⊕M and the uniform distribution cannot be distinguished. Moreover, logGT−l can be close to zero, the leakage bound l is roughly equal to logGT, and the leakage ratio of K is l/logGT≈logGT/logGT=1.


## 5.1. Probability analysis

IfT=eg,g′αq+1, we set r∗=loggg′⋅F∗α, and we have C1∗=g′αq+2⋅g′−ρ∗q+2s1∗=gs1∗⋅loggg′⋅αq+2−ρ∗q+2=gs1∗⋅r∗⋅α−ρ∗=PKID∗1⋅PKID∗2−ρ∗r∗, C2∗=TFq+1∗⋅e∏i=0qgαiFi∗,g′=eg,g′αq+1Fq+1∗⋅e∏i=0qgαiFi∗,g′=eg,gloggg′⋅∑i=0q+1αiFi∗=gTr∗. Thus, Cβ∗=C1∗,C2∗,CMβ∗,C4∗ is a valid ciphertext, A1 outputs correct β′=β with the advantage 2PrA1wins−1≥ε. If T∈GT is a random value, Cβ∗=C1∗,C2∗,CMβ∗,C4∗ is not a valid ciphertext; it cannot provide useful information for the guess of A1. Thus, A1 outputs correct β′=β with the advantage PrA1wins=1/2.Thus,B breaks the q-ABDHE problem with advantage PrBg,gα,…,gαq,g′,g′αq+2,eg,g′αq+1=1−PrBg,gα,…,gαq,g′,g′αq+2,T=1≥1/2±ε−1/2=ε.Theorem 2.
If there is a PPT adversaryA2 against the CBE scheme resilient to continual leakage with advantage ε that makes at most qsk secret key queries, qd decryption queries with l bits entropy leakage for the symmetric key, then there exists a PPT algorithm B against the 1-BDHI problem with advantage ε′≥ε/qsk.Proof.
GivenGT,G,p,e,g,gα,T, the algorithm B performs as the challenger C of IND-RCL-CCA Game-2 to interact with A2; the target of B is to decide whether T=eg,g1/α.Setup: the algorithmB randomly picks x,z,x1,x2∈ℤp∗ and computes g1=gx, gT=eg,g, h1=gx1 and h2=gx2. B chooses two collision resistant hash functions H1:0,1∗×G3⟶ℤp∗, H2:G×GT⟶ℤp∗, and an average-case logGT−l,εExt-strong extractor Ext:GT×0,1μ⟶0,1η, μ,η∈ℕ, and sends params=p,G,GT,g,g1,gT,h1,h2,e,H1,H2,Ext and MSK = x to A2.Phase 1:A2 asks B for queries adaptively as follows:Public key queries:A2 inputs IDi; B randomly chooses I∈1,qsk. B checks the tuple IDi,skIDi,PKIDi from the ℒ1. If it exists, B returns PKIDi to A2. Otherwise, if IDi≠IDI, B randomly picks skIDi=s1,s2∈ℤp∗×ℤp∗, computes PKIDi=g1s1,gs1,gs2, inserts the tuple IDi,skIDi,PKIDi into ℒ1, and returns PKIDi; if IDi=IDI, B sets PKIDI=gαx,gα,gz, inserts the tuple IDI,skIDI,• into ℒ1, and outputs PKIDI to A2.Secret key queries: For a secret key query underIDi, if IDi≠IDI, B seeks IDi,skIDi,PKIDi from the list ℒ1 and returns skIDi to A2; otherwise, B ends the game and outputs a failure information.Leakage queries:A2 inputs ID; B finds ID,K,cnt from ℒ2. If the item does not exist, B adds ID,K,0 into ℒ2. If the item exists, or in the next step, B decides whether cnt+li≤l where l,i∈ℕ. If not, B returns ⊥. Otherwise, B sets cnt⟵cnt+li for ID,K,cnt and returns fiK to A2, where fi is a leakage function and fi:GT⟶0,1li.Decryption queries: For queries onIDi and ciphertext C=C1,C2,C3,C4. If IDi≠IDI, B obtains the secret key skIDi and certificate CertIDi of IDi; then B obtains the symmetric key K and uses K to decrypt C. Otherwise, B computes the symmetric key K=eC1,gφ/x−ρI⋅C2φ⋅x1+x2+z where φ=H2C1,C2 and ρI=H1IDI,PKIDI and computes M=C3⊕ExtK,C4. B returns either M or ⊥ to A2.Challenge:M0 provides B with two identical-length messages M1 and ID∗ and a target identity A2 with the following restriction: ID∗ is not allowed to issue the secret key queries for ID∗≠IDI. If r∈ℤp∗, B ends the game and outputs failure. Otherwise, B will randomly select C1∗=g1⋅g−ρ∗r and compute C2∗=Tr, ρ∗=H1IDI,PKIDI, where T=eg,g1/α and β∈0,1. B randomly selects σ∗∈0,1μ and K1∗=Trφ∗x1+x2+z⋅eg,gφ∗r and computes φ∗=H2C1∗,C2∗ where K0∗∈GT. B randomly chooses β∈0,1, σ∗∈0,1μ, and CMβ∗=ExtKβ∗,σ∗⊕Mβ, sets C4∗=σ∗, Cβ∗=C1∗,C2∗,CMβ∗,C4∗, and outputs the challenge ciphertext A2 to A2.Phase 2:A2 continues making the queries which is similar to Phase 1 under the following restriction: ID∗ has no permission to perform secret key queries for ID∗,C∗, as well as the decryption queries on A2.Guess:β′∈0,1 returns the guess β′=β. If T=eg,g1/α holds, B outputs 1, indicating that T≠eg,g1/α. Otherwise, B outputs 0, which indicates T=eg,g1/α.


## 5.2. Probability analysis

Ifr∗=r/α, we set , and we have C1∗=g1⋅g−ρ∗r=g1⋅g−ρ∗αr∗=PKIDI1⋅PKIDI2−ρ∗r∗, C2∗=Tr=eg,g1/ααr∗=gTr∗. K1∗=Trφ∗x1+x2+z⋅eg,gφ∗r=eg,gφ∗x1+x2+zr∗⋅eg,gφ∗αr∗=eg,h1⋅PKID∗2φ∗⋅eg,h2⋅PKID∗3r∗. Thus, Cβ∗=C1∗,C2∗,CMβ∗,C4∗ is a valid ciphertext; A2 outputs correct β′=β with the advantage 2PrA2wins−1≥ε. If T∈GT is a random value, Cβ∗=C1∗,C2∗,CMβ∗,C4∗ is an invalid ciphertext; it cannot provide useful information for the guess of A2. Thus, A2 outputs correct β′=β with the advantage PrA2wins=1/2.Thus,B breaks the 1-BDHI problem with advantage PrBg,gα,eg,g1/α=1−PrBg,gα,T=1≥1/2±ε−1/2=ε. Furthermore, the probability that A2 chooses IDI as the target identity is 1/qsk. Therefore B breaks the 1-BDHI problem with advantage ε′≥ε/qsk.


## 5.3. Leakage Ratio Analysis

We mainly consider the leakage of the symmetric keyK. Firstly, a set Z is defined which consists of public parameters, secret keys, and certificates. As an adversary, A acquires at most l bits for leakage of the symmetric key K. Based on Lemma 1, we have H˜∞ALeak,Z≥H˜∞AZ−l=logGT−l, where Leak has 2l possible values and l∈ℕ is the leakage length. If we pick the average-case logGT−l,εExt-strong extractor where εExt is negligible, we know that SDExtX,Uμ,Uμ,Y,Uη,Uμ,Y≤ε, where Uμ and Uη have uniform distributions over 0,1μ,0,1η, respectively. Thus, the ciphertext C3=ExtK,σ⊕M and the uniform distribution cannot be distinguished. Moreover, logGT−l can be close to zero, the leakage bound l is roughly equal to logGT, and the leakage ratio of K is l/logGT≈logGT/logGT=1.


## 6. Efficiency Comparison

Three CBE schemes [3, 6, 8] are compared with our proposed approach, to evaluate their security and efficiency. The security properties and leakage ratio comparison for four CBE schemes are shown in Table 1.Table 1
Security properties and leakage ratio comparison.
SchemesModelHard assumptionLeakage-resilienceContinual leakage-resilienceLeakage ratioScheme [3]Standardq-ABDHE and DBDH××—Scheme [6]StandardDecisional 3-party Diffie–Hellman√×≈1Scheme [8]StandardThree assumptions in composite order bilinear groups√×1/3Our schemeStandardDecisional truncatedq-ABDHE and decisional 1-BDHI√√≈1Table1 demonstrates that the schemes in [6, 8] and our CBE scheme are leakage-resilient while the scheme in [3] is not. The key-leakage ratio of the scheme [8] is up to 1/3. However, the symmetric key-leakage ratio of scheme [6] and our scheme is close to 1. In addition, our scheme is resistant to continual leakage. In conclusion, our CBE scheme has obvious advantage.LetGp1 and Gp3 denote the subgroups of orders p1 and p3 in G, respectively, where p1 and p3 are distinct primes. An NIZK proof is represented by π in [8], and n is an integer. We analyze the communication cost for the four schemes as follows.From Table2, the difference of communication performance between the scheme in [6] and our scheme is not obvious. The length of the public/secret key, the certificate, and the ciphertext in the proposed approach is less than that required in [3]. Moreover, the length of the certificate and ciphertext in our proposed approach is also less than that required in [8]. Therefore, our CBE scheme achieves a lower communication cost, compared with the two schemes in [3, 8].Table 2
Comparison of the required communication cost.
SchemesPublic key lengthSecret key lengthCertificate lengthCipher text lengthScheme [3]6G6ℤp3ℤp+3G3GT+GScheme [6]2Gℤp3G2G+η+μScheme [8]GT+πℤpn+2Gp1⋅Gp3GT+n+2Gp1Our scheme3G2ℤp2ℤp+2GG+GT+μ+ηWe also implement these schemes in a Windows 10 environment (Intel (R) Core (TM) i7-6500U CPU, 8.00 GB RAM) using C++ language and PBC [50] library, where a.param is used as the configuration file, and the message length is fixed at 1024 bits. Note that every comparative scheme is separately run ten times, in order to obtain the average running time. The required running times of the four schemes are listed below.From both Table3 and Figure 1, it can be found that although our scheme was added with the secret key update algorithm, the total operating time is shorter than that of the other three schemes in [3, 6, 8]. This indicates that our proposed method outperforms the other approaches with higher efficiency.Table 3
Running time in microsecond.
SchemesSetupUserKeyGenCertGenEncryptDecryptUpdateSKTotalScheme [3]283327505—143Scheme [6]2310252718—105Scheme [8]1043341142—195Our scheme151429239396Figure 1
Run time comparison.The message space in scheme [6] and our scheme is ℳ=0,1η; we therefore analyze these two schemes based on the relationship between different lengths of the messages and encryption/decryption running times. Figure 2 shows the relation between encryption running times and the message lengths for scheme [6] and our scheme. The relation between decryption running times and message sizes for both schemes is shown in Figure 3.Figure 2
Relation between encryption times and message sizes.Figure 3
Relation between decryption times and message sizes.According to Figure2, it can be seen that the required time for encryption in the two approaches and the message sizes are linearly increased. Although the longer the message, the longer the encryption time, the growth of our scheme has a relatively lower amplitude than scheme [6]. From Figure 3, the decryption times for two schemes are not greatly affected by the lengths of the messages. In addition, it can be seen that, for different message lengths, the required time for decryption in our scheme is shown to be less than that of the scheme in [6]. Hence, our proposed scheme has certain advantages from this perspective.


## 7. Conclusions

In this work, we give a formal definition and the security model for CBE resilient to continual leakage. Besides, we construct a CBE scheme which is resilient to continual leakage. The security of our scheme is reduced to the hardness of the decisional truncatedq-augmented bilinear Diffie–Hellman exponent problem and the decisional 1-bilinear Diffie–Hellman inversion problem. Moreover, comparative studies are provided with other existing solutions, in terms of their performance analyses. Our scheme is proved secure against the chosen-ciphertext attack in the standard model. To construct CBE scheme with stronger leakage-resilient property (such as auxiliary inputs, post-challenge leakage, etc.) and leakage-resilient certificateless encryption scheme with keyword search [51], leakage-resilient location determination scheme [52] is left as our future study.



---

*Source: 1492681-2020-06-28.xml*