J.-D. Wu received the BS degree from the Department of Mathematics, National Changhua University of Education, Taiwan, in 2006. He received the MS degree from the Department of Mathematics, National Changhua University of Education, Taiwan, in 2008. He is currently a PhD candidate in the Department of Mathematics, National Changhua University of Education, Taiwan. His research interests include applied cryptography and pairing-based cryptography.
TsengYuh-Minymtseng@cc.ncue.edu.tw∗
Y.-M. Tseng is currently a professor in the Department of Mathematics, National Changhua University of Education, Taiwan. He is a member of IEEE Computer Society, IEEE Communications Society and the Chinese Cryptology and Information Security Association (CCISA). In 2006, his paper received the Wilkes Award from The British Computer Society. He has published over one hundred scientific journals and conference papers on various research areas of cryptography, security and computer network. His research interests include cryptography, network security, computer network and mobile communications. He serves as an editor of several international journals.
HuangSen-Shan
S.-S. Huang is currently a professor in the Department of Mathematics, National Changhua University of Education, Taiwan. His research interests include number theory, cryptography, and network security. He received his PhD from the University of Illinois at Urbana-Champaign in 1997 under the supervision of Professor Bruce C. Berndt.
ChouWei-Chieh
W.-C. Chou received the BS degree from the Department of Mathematics, National Changhua University of Education, Taiwan, in 2015. He received the MS degree from the Department of Mathematics, National Changhua University of Education, Taiwan, in 2017. His research interests include leakage-resilient cryptography and network security.
The previous adversary models of public key cryptography usually have a nature assumption that permanent/temporary secret (private) keys must be kept safely and internal secret states are not leaked to an adversary. However, in practice, it is difficult to keep away from all possible kinds of leakage on these secret data due to a new kind of threat, called “side-channel attacks”. By side-channel attacks, an adversary could obtain partial information of these secret data so that some existing adversary models could be insufficient. Indeed, the study of leakage-resilient cryptography resistant to side-channel attacks has received significant attention recently. Up to date, no work has been done on the design of leakage-resilient certificateless key encapsulation (LR-CL-KE) or public key encryption (LR-CL-PKE) schemes under the continual leakage model. In this article, we propose the first LR-CL-KE scheme under the continual leakage model. Moreover, in the generic bilinear group (GBG) model, we formally prove that the proposed LR-CL-KE scheme is semantically secure against chosen ciphertext attacks for both Type I and Type II adversaries.
certificateless encryptioncontinual leakage modelside-channel attacksleakage resiliencegeneric bilinear group modelIntroduction
To simplify public key management and remove the need of certificates required in the traditional public key cryptography, Shamir (1984) presented the notion of identity (ID)-based public key cryptography (ID-PKC). However, ID-PKC encounters the key escrow problem in the sense that the private key generator (PKG) knows all users’ private keys so that the PKG may decrypt all the ciphertexts or sign the messages on behalf of all the users. In order to solve the key escrow problem in ID-PKC, Al-Riyami and Paterson (2003) proposed the certificateless public key cryptography (CL-PKC), in which there are two players, namely, a key generation centre (KGC) and users. The KGC represents a trusted third party and is responsible to generate each user’s initial key. Each user’s full private key consists of two components, namely, the initial key generated by the KGC and a secret key chosen by the user. Meanwhile, in accordance with the secret key, a user can compute her/his corresponding public key. Obviously, the KGC can’t obtain a user’s full private key due to the lack of the user’s self-chosen secret key. Therefore, CL-PKC overcomes the key escrow problem and retains the advantage of eliminating certificates in ID-PKC. Indeed, the study on CL-PKC has received great attention from researchers and a large number of certificateless cryptographic schemes have been proposed such as certificateless public-key encryption (CL-PKE) (Libert and Quisquater, 2006; Hwang et al., 2008; Tsai et al., 2015; Tsai and Tseng, 2015; Hung et al., 2017) and certificateless signature (CLS) (Huang et al., 2007; Hu et al., 2007; Hung et al., 2015, 2016). The mentioned certificateless encryption/signature schemes above were implemented by employing bilinear pairing groups. However, the operations in bilinear pairing groups are more time-consuming than the exponentiation operator in RSA groups. Recently, several RSA-based certificateless encryption/signature schemes (Zhang and Mao, 2012; Sharma et al., 2016; Lin et al., 2017) were proposed to improve computation performance of pairing-based certificateless encryption/signature schemes.
Nevertheless, the previous adversary models of traditional, ID-based and certificateless public key cryptographies usually have a nature assumption that permanent/temporary secret (private) keys must be kept safely and internal secret states are not leaked to an adversary. However, in practice, it is difficult to keep away from all possible kinds of leakage on these secret data due to a new kind of threat, called “side-channel attacks”, such as timing attacks (Kocher, 1996; Brumley and Boneh, 2005), power analysis (Kocher et al., 1999) and fault attacks (Boneh et al., 1997; Biham et al., 2008). By side-channel attacks, an adversary could obtain partial information of these secret data so that some existing adversary models could be insufficient. More precisely, if a cryptographic scheme was proven secure in an adversary model without addressing side-channel attacks, the cryptographic scheme still could be broken in an environment where an adversary may obtain partial information of secret data. Therefore, the study of leakage-resilient cryptography (LRC) resisting to side-channel attacks has received significant attention recently.
The basic concept of LRC is that a cryptographic scheme remains secure when partial information of the secret data involved in the scheme is visible to the adversary. In order to represent the leakage resilience of cryptographic schemes, an adversary model of LRC must define the adversary’s capabilities of obtaining leakage information. A cryptographic scheme typically includes several calculation rounds. For each calculation round, the adversary has a leakage function f on the secret data τ and may obtain the leakage information f(τ). Also, the output length of f is limited to λ bits. Namely, the adversary can obtain at most λ bits of leakage information for each calculation round. However, the full secret (private) key would be exposed to the adversary if the total leakage information of a cryptographic scheme is unbounded. In such a case, it will compromise the security of the cryptographic scheme. Hence, several leakage-resilient cryptographic schemes (Akavia et al., 2009; Alwen et al., 2009; Katz and Vaikuntanathan, 2009) make a restriction that the total leakage information must be bounded which is called the bounded leakage model. However, this restriction is impractical. Indeed, the continual leakage model is the most accredited model for leakage-invocated ability of an adversary, which provides the overall unbounded leakage property (Brakerski et al., 2010; Dodis and Haralambiev, 2010; Galindo and Virek, 2013; Wu et al., 2016). The properties of the continual leakage model will be reviewed in Section 3.
Related Work
Akavia et al. (2009) presented the first security model of leakage-resilient public key encryption (LR-PKE) in the bounded leakage model. In their security model, an adversary can select arbitrary leakage functions of the secret (private) keys and obtains the outputs of these functions. They also proposed a concrete LR-PKE scheme, which is the first leakage-resilient chosen plaintext attack (LR-CPA) secure scheme. Naor and Segev (2009, 2012) extended Akavia et al.’s security model of LR-PKE scheme to present the settings of both the leakage-resilient chosen ciphertext attacks (LR-CCA1) and the adaptive leakage resilient chosen ciphertext attacks (LR-CCA2). Meanwhile, Naor and Segev also presented a generic construction of LR-PKE scheme from the universal hash proof system. Liu et al. (2013) and Li et al. (2013), respectively, proposed efficient LR-PKE schemes which have less computational cost than Naor and Segev’s scheme (2009, 2012). The schemes mentioned above are all secure in bounded leakage model, but not under the continual leakage model. Moreover, Kiltz and Pietrzak (2010) proposed a leakage-resilient public key encryption under the continual leakage model using the generic bilinear group (GBG) model (Boneh et al., 2005). The properties of the GBG model will be presented in Section 2. Based on the GBG model, Galindo et al. (2016) also presented and implemented a new ElGamal-like leakage-resilient key encapsulation (LR-KE) scheme under the continual leakage model. All the LR-PKE schemes mentioned above are based on traditional public key settings.
In ID-based public key settings, Brakerski et al. (2010) proposed the first leakage-resilient ID-based encryption (LR-IBE) scheme under the continual leakage model. Afterwards, Yuen et al. (2012) proposed an improved LR-IBE scheme to achieve better performance. Their scheme allows an adversary to learn partial information of both the system secret key in the key extract phase and the user’s private key in the decryption phase. Recently, Li et al. (2016) presented a new LR-IBE scheme under composite order groups. By the post-challenge continuous auxiliary input, their scheme is secure against adaptive chosen plaintext attacks under three static assumptions in the standard model.
Indeed, there exists little work on leakage-resilient certificateless cryptographic schemes. Xiong et al. (2013) proposed the first leakage-resilient certificateless public key encryption (LR-CL-PKE) scheme, which is secure against Type I (outsider) and Type II (honest-but-curious KGC) adversaries. Xiong et al.’s scheme possesses the security against LR-CPA and LR-CCA1 attacks, but not against LR-CCA2 attacks. Zhou et al. (2016) improved Xiong et al.’s scheme to propose a LR-CCA2 secure leakage-resilient certificateless signcryption scheme based on bilinear pairings. However, both Xiong et al.’s and Zhou et al.’s schemes are secure under the bounded leakage model, but not under the continual leakage model.
Contributions
Up to date, no existing leakage-resilient certificateless public key encryption (LR-CL-PKE) or leakage-resilient certificateless key encapsulation (LR-CL-KE) schemes are secure under the continual leakage model. In this article, we will propose the first LR-CL-KE scheme under the continual leakage model. We first define the adversary model of LR-CL-KE schemes under the continual leakage model. The adversary model is extended from the adversary model of CL-PKE schemes defined in Hwang et al. (2008), Tsai et al. (2015), Tsai and Tseng (2015). The adversary model also consists of two types of adversaries, namely, Type I adversary (outsider) and Type II adversary (honest-but-curious KGC). By adding the leak queries, the new adversary model of LR-CL-KE schemes allows to leak partial information of the system secret key in the initial key extract phase and leak the partial information of the user’s private key in the decrypt phase. The point is that the adversary model provides the overall unbounded leakage property (Galindo and Virek, 2013; Wu et al., 2016) under the continual leakage model. In the generic bilinear group (GBG) model (Boneh et al., 2005), we formally prove that the proposed LR-CL-KE scheme is semantically secure against chosen ciphertext attacks for both Type I and Type II adversaries. Finally, the performance analysis is given to demonstrate the comparison of the proposed LR-CL-KE scheme and the related schemes.
Organization
The remainder of the article is organized as follows. Preliminaries are given in Section 2. In Section 3, we present the framework and security notions of LR-CL-KE schemes. Then a concrete LR-CL-KE scheme is proposed in Section 4. We analyse the security of the proposed LR-CL-KE scheme in Section 5. Section 6 demonstrates performance comparisons. Conclusions and future work are given in Section 7.
Preliminaries
The notions of bilinear groups (Boneh and Franklin, 2001; Waters, 2005; Scott, 2011), the properties of the generic bilinear group model (Galindo and Virek, 2013; Boneh et al., 2005; Wu et al., 2016) and entropy are briefly introduced here.
Bilinear Pairings
Let G and GT be two cyclic multiplicative groups of large prime order p. Let g be a generator of the group G. An admissible bilinear pairing is a map e: G×G→GT and satisfies the following conditions:
Bilinearity: for all x, y∈Zp∗, e(gx,gy)=e(g,g)xy.
Non-degeneracy: for some g∈G, e(g,g)≠1.
Computability: for all g1, g2∈G, e(g1,g2) can be efficiently computed.
In addition, G is a bilinear group while GT is called the target group of the admissible bilinear map e. A reader can refer to previous literatures such as Boneh and Franklin (2001), Waters (2005), Scott (2011) for more complete descriptions about bilinear groups and admissible bilinear map.
Generic Bilinear Group Model
The notions of the generic group model were first introduced by Shoup (1997), which is viewed as an adversary model for cryptographic schemes. In the generic group model, an adversary can issue a group oracle (query) to a challenger for executing the group operation (Maurer and Wolf, 1998). The group operation takes as input two group elements and outputs third group element. For example, in a multiplicative group, the group operation is multiplication which multiplies two group elements together to obtain third group element. Namely, the group oracle allows an adversary to have access to a randomly chosen encoding (element) of a group controlled by the challenger. Meanwhile, if the used group allows the other pairing operation such as bilinear pairing, an additional oracle must be provided. One of the main usages of the generic group model is to analyse computational hardness assumptions such as the discrete logarithm problem. It is said to solve the computational hardness assumption if an adversary can efficiently find a collision element of a group operation.
Boneh et al. (2005) extended the generic group model above to present the generic bilinear group (GBG) model. In the GBG model, there exist two multiplicative cyclic groups G and GT with three operations, namely, group operations of G and GT, respectively, and a bilinear pairing operation from G×G into GT. The elements of G and GT are respectively encoded by two random injective maps ε:Zp→ϕ and εT:Zp→ϕT, where both ϕ and ϕT are bit strings such that |ϕ∩ϕT|=0 and |ϕ|=|ϕT|=p. Meanwhile, in the GBG model, two queries (oracles) QG and QT are provided to perform the associated group multiplication operations in G and GT while a query QP is used to perform the evaluation of the bilinear map e. For any x, y∈Zp∗, three queries have the following properties respectively.
QG(ε(x), ε(y)) →ε(x+y mod p).
QT(εT(x), εT(y)) →εT(x+y mod p).
QP(ε(x), ε(y)) →εT(xy mod p).
Note that ε(1)=g and e(g,g)=εT(1)=gT, where g and gT are generators of the groups G and GT, respectively.
Entropy
Entropy is a number measure of possible states (or microstates) of a system. In addition, the interpretation of entropy in statistics is viewed as the measure of uncertainty. We assume that X is a finite random variable and Pr is the associated probability distribution. The worst-case predictability of a random variable is measured by using min-entropy. Two kinds of min-entropies are defined as follows:
H∞(X)=−log2(maxxPr[X=x]) denotes the min-entropy of a finite random variable X.
H˜∞(X|Z)=−log2(Ez←Z[maxxPr[X=x|Z=z]]) denotes the average conditional min-entropy of a random variable X under a correlated random variable Z.
Under some condition on the leakage information, Dodis et al. (2008) presented the min-entropy of a finite random variable X by the following Lemma 1.
Assume thatf:X→0,1λis a leakage function on a secret random variable X andf(X)denotes the leakage information while the output length of f is limited to λ bits. We haveH˜∞(X|f(X)) ⩾ H∞(X)−λ.
In addition, Galindo and Virek (2013) proved Lemma 2 below to demonstrate the probability distribution of a polynomial under the leakage information. Their result is an extension of the Schwartz–Zippel lemma (Zippel, 1979; Schwartz, 1980).
Assume thatF∈Zp[X1,X2,…,Xn]denotes a non-zero polynomial of total degree at most d. LetPi(fori=1,2,…,n) be probability distributions onZpsuch thatH∞(Pi)⩾log(p)−λand0⩽λ⩽log(p). Ifxi⟵PiZp (fori=1,2,…,n) are independent, we have the probability Pr[F(x1,x2,…,xn)=0]⩽dp2λ.
The following result follows directly from Lemma 2.
The probability Pr[F(x1,x2,…,xn)=0]is negligible ifλ<logp−ω(log(log(p))).
Framework and Security Notions
In this section, we define the framework (syntax) and security notions (adversary model) of leakage-resilient certificateless key encapsulation (LR-CL-KE) schemes under the continual leakage model. Here, we first introduce the properties of the continual leakage model as follows:
Only computation leakage: This property means that only permanent/temporary secret (private) keys accessed and involved in a current calculation round could be leaked to a side-channel adversary.
Bounded leakage of single observation: The length of leakage information in a single calculation round (observation) is limited to some λ bits. This property indicates that the leakage information of each calculation round is bounded to some fraction of secret information.
Independent leakage: The leakage information of all the calculation rounds is independent with each other.
Overall unbounded leakage: This property means that the total amount of leakage information is unbounded. In such a case, secret (private) keys must be updated (refreshed) before/after each calculation round.
In order to achieve the overall unbounded leakage, a continual leakage model must possess the stateful property (Kiltz and Pietrzak, 2010). Firstly, each secret (private) key must be divided into two parts and stored in different parts of the memory. If secret (private) keys are updated before (or after) executing the calculation round in a cryptographic algorithm while the associated public key remains fixed, we say that the cryptographic scheme under continual leakage model provides stateful property.
Framework of LR-CL-KE Scheme
Here, we present the framework of LR-CL-KE scheme under the continual leakage model.
A LR-CL-KE scheme consists of seven algorithms:
Setup: Taking a security parameter as input, the key generation centre (KGC) runs this algorithm to generate the first system secret key (SK0,1,SK0,2) and the public parameters PP. The KGC then publishes PP and keeps (SK0,1,SK0,2) in secret. The KGC also selects a symmetric cryptosystem with encryption function E() and decryption function D().
Initial key extract: For the i-th user with identity ID, the KGC uses this algorithm to generate the first initial key (DID0,QID) of the user. This algorithm consists of two sub-algorithms Extract-1 and Extract-2 defined below, in which the current system secret key (SKi−1,1,SKi−1,2) is used and is updated to (SKi,1,SKi,2).
Extract-1: Given a random number γ, SKi−1,1 and the user’s identity ID, this sub-algorithm generates QID and temporary information TIIE, and updates SKi−1,1 to SKi,1.
Extract-2: Given TIIE, and SKi−1,2, this sub-algorithm generates DID0 and updates SKi−1,2 to SKi,2.
The KGC then sends the first initial key (DID0,QID) to the user.
Set secret value: This algorithm is performed by a user with identity ID to generate the user’s secret key SID0 and the partial public key RID.
Set private key: This algorithm is performed by a user with identity ID. This algorithm takes the user’s first initial key (DID0,QID) and secret key SID0 as input to set the user’s private key ((DID0,1,DID0,2), (SID0,1,SID0,2)).
Set public key: This algorithm is performed by a user with identity ID. This algorithm takes the initial key (DID0,QID) and the partial public key RID as input, and outputs the user’s public key PID=(QID,RID).
Encrypt: Given a plain-message msg and the public key PID=(QID,RID) of a receiver with identity ID, this algorithm first generates a random value C and the associated encryption key K, and then generates CT=EK(msg) by using the encryption function E() of a symmetric cryptosystem. Finally, (C,CT) is sent to the receiver.
Decrypt: This algorithm consists of two sub-algorithms Decrypt-1 and Decrypt-2, run by a receiver. For the j-th Decrypt round, the user with identity ID adopts her/his current private key ((DIDj−1,1,DIDj−1,2), (SIDj−1,1,SIDj−1,2)) to decrypt the ciphertext (C, CT) by performing two sub-algorithms. In addition, the current private key ((DIDj−1,1,DIDj−1,2), (SIDj−1,1, SIDj−1,2)) is also updated to ((DIDj,1, DIDj,2), (SIDj,1, SIDj,2)).
Decrypt-1: Given DIDj−1,1 and SIDj−1,1, this algorithm outputs DIDj,1, SIDj,1 and the temporary information TID.
Decrypt-2: Given C, CT, TID, DIDj−1,2 and SIDj−1,2, this algorithm generates DIDj,2 and SIDj,2 while obtaining the encryption key K. Finally, the receiver can obtain the plain message msg by DK(CT) using the decryption function D() of a symmetric cryptosystem.
Security Notions of LR-CL-KE Scheme
By the framework of LR-CL-KE scheme under the continual leakage model described in Section 3.1, an adversary A can obtain leakage information in four sub-algorithms: Extract-1, Extract-2, Decrypt-1 and Decrypt-2. To represent the leakage information obtained by the adversary in the i-th Initial key extract round, two leakage functions fIE,i and hIE,i are chosen to model the adversary’s abilities in Extract-1 and Extract-2, respectively. Meanwhile, two leakage functions fD,j and hD,j are, respectively, chosen to model the adversary’s ability in Decrypt-1 and Decrypt-2 of a user’s j-th Decrypt round. It is worth mentioning that four leakage functions fIE,i, hIE,i, fD,j and hD,j can be efficiently computed while the output length of each leakage function is bounded by λ, where λ is the leakage parameter. That is, |fIE,i|, |hIE,i|, |fD,j|, |hD,j|⩽λ, where |f| denotes the output length of leakage function f. We define the outputs of four leakage functions as follows.
Here, params denotes the random values involved in the computation of four sub-algorithms Extract-1, Extract-2, Decrypt-1 and Decrypt-2. Moreover, skeys denotes the symmetric encryption key. Note that TIIE and TID are the outputs of Extract-1 and Decrypt-1, respectively.
The adversary model of LR-CL-KE schemes consists of two types of adversaries, namely, Type I adversary (outsider) and Type II adversary (honest-but-curious KGC). Two types of adversaries are extended from the adversary model of CL-PKE schemes defined in Hwang et al. (2008), Tsai et al. (2015), Tsai and Tseng (2015) by adding the initial key extract leak query and decrypt leak query. This new model of LR-CL-KE schemes allows adversaries to learn partial information of the system secret key in the initial key extract phase and leak partial information of the user’s private key in the decrypt phase. We describe two types of adversaries as follows.
Type I Adversary (Outsider): This kind of adversary simulates the role of an outsider who can replace the public key of any user with another one chosen by herself/himself. That is, a Type I adversary may decide the secret key of any user with her/his choice. In addition, a Type I adversary may obtain the leakage information of a user’s initial key in the decryption phase while leaking partial information of the KGC’s system secret key in the Initial key extract phase.
Type II Adversary (Honest-but-curious KGC): This kind of adversary simulates the role of the honest-but-curious KGC who owns the system’s secret key and is disallowed to perform the public key replacement. In other words, a Type II adversary holds the initial key of any entity. In addition, a Type II adversary may obtain the leakage information of a user’s secret key in the decryption phase.
In the following, a security game is used to model the security notions of the LR-CL-KE scheme under the continual leakage model. The security game below is played by the challenger B and an adversary A. (<italic>LR-CL-IND-CCA</italic>).
We say that a LR-CL-KE scheme is semantically secure against indistinguishability under chosen ciphertext attack (LR-CL-IND-CCA) if no probabilistic polynomial-time (PPT) adversary A (including Types I and II adversaries) has a non-negligible advantage in the following LR-CL-IND-CCA game played with a challenger B.
Setup. The challenger B takes a security parameter l as input, and runs the Setup algorithm to generate the first system secret key (SK0,1,SK0,1) and the public parameters PP. PP is sent to the adversary A. In addition, if A is of Type II adversary, B also sends (SK0,1,SK0,1) to A. If A is of Type I adversary, the first system secret key (SK0,1,SK0,1) is kept secret by B.
Phase 1. In this phase, the adversary A may adaptively issue the following queries:
Initial key extract query (ID). For the i-th Initial key extract query along with a user’s identity ID, the challenger B uses the current system secret key (SKi−1,1,SKi−1,2) to generate the user’s first initial key (DID0, QID) while updating (SKi−1,1, SKi−1,2) to (SKi,1, SKi,2). Finally, B returns (DID0, QID) to A.
Initial key extract leak query (fIE,i,hIE,i,i): By providing two leakage functions fIE,i and hIE,i, A can issue the Initial key extract leak query only once for the i-th Initial key extract query. The challenger B computes the leakage information (ΛfIE,i,ΛhIE,i) and returns it to A.
Public key retrieve query (ID). Upon receiving this query along with an identity ID, B returns the corresponding public key PID=(QID,RID).
Public key replace query (ID, PID′=(QID′,RID′)). Upon receiving this query along with (ID, PID′), B records the replacement. It means that the adversary A has replaced the user’s public key with PID′=(QID′,RID′).
Secret key extract query (ID). When the challenger B receives this query along with an identity ID, B returns the secret key SID0. Moreover, the query is forbidden if Public key replace query (ID) has been previously queried in this game.
Decrypt query (ID, C). For the j-th Decrypt round, upon receiving this query along with an identity ID and a ciphertext C, the challenger B uses the user’s current private key (DIDj−1=(DIDj−1,1,DIDj−1,2), SIDj=(SIDj−1,1,SIDj−1,2)) to generate the encryption key K by running two sub-algorithms Decrypt-1 and Decrypt-2. The challenger B then returns K to A. It is worth mentioning that the current private key (DIDj−1=(DIDj−1,1,DIDj−1,2), SIDj=(SIDj−1,1, SIDj−1,2)) is also updated to (DIDj=(DIDj,1,DIDj,2), SIDj=(SIDj,1,SIDj,2)).
Decrypt leak query (fD,j, hD,j, j): By providing two leakage functions fD,j and hD,j, A can issue the Decrypt leak query only once for the j-th Decrypt query. B computes the leakage information (ΛfD,j, ΛhD,j) and returns it to A. In addition, if A is of Type II adversary (honest-but-curious KGC), (ΛfD,j, ΛhD,j) includes only the leakage information of a user’s secret key (SIDj−1,1, SIDj−1,2) since A knows the initial key of any entity. If A is of Type I adversary (outsider), the adversary may obtain the leakage information of a user’s initial key (DIDj−1,1,DIDj−1,2) since an outsider owns the secret key of any entity.
Challenge. The adversary A chooses a target identity ID∗ and a plaintext pair (msg0∗, msg1∗) to the challenger B. Two restrictions are described as follows.
If A is of Type I adversary (outsider), the Initial key extract query (ID∗) is not queried in Phase 1.
If A is of Type II adversary (honest-but-curious KGC), it is disallowed to issue the queries on the Secret value extract query and Public key replace query on ID∗ in Phase 1.
The challenger B chooses a random β∈{0,1} and computes C∗=E(PP, ID∗, msgβ∗, PKID∗) by running the Encrypt algorithm. Then B sends C∗ to A. Here PKID∗ is the public key of the identity ID∗.
Guess. The adversary A outputs β′∈{0,1} and wins this game if β′=β.
In the LR-CL-IND-CCA game above, we call the adversary A as a LR-CL-IND-CCA adversary. We define the adversary A’s advantage in attacking the LR-CL-KE scheme as AdvA(l)=|Pr[β=β′]−12|.
The LR-CL-IND-CCA game defined above models the security notion of LR-CL-KE scheme against non-adaptive chosen ciphertext attacks (CCA1). For the security notion against adaptive chosen ciphertext attack (CCA2), a new Phase 2 is inserted between the Challenge phase and Guess phase. In the Phase 2, A may issue further queries as in Phase 1 while a restriction is that A cannot make a Decrypt query on the challenge ciphertext C∗=E(Parms, ID∗, msgβ∗, PKID∗). It is worth mentioning that our LR-CL-KE scheme is secure against CCA1 under the continual leakage model, but it can’t achieve CCA2 security. The reason will be discussed in Section 5.
The Proposed LR-CL-KE Scheme
In the following, we propose the first LR-CL-KE scheme, denoted by Π. As the framework defined in Section 3.1, the LR-CL-KE scheme consists of seven algorithms as follows:
Setup: Given a security parameter l, the KGC first generates two multiplicative groups G and GT of prime order p and then randomly picks a generator g of G. Let e:G×G→GT be an admissible bilinear pairing. The KGC also selects a symmetric cryptosystem with encryption function E() and decryption function D(). The KGC runs the following steps to generate the first system secret key (SK0,1,SK0,1) and the public parameters PP:
Randomly pick x∈Zp∗ and compute X=gx and XT=e(gx,g).
Randomly pick α∈Zp∗ and set the first system secret key (SK0,1,SK0,1)=(gα,X·gα).
Randomly pick ui0, ui1∈Zq∗ and compute U0= gui0 and U1= gui1.
Publish PP=(G,GT,e,p,g,XT,U0,U1,E,D).
Initial key extract: For the i-th Initial key extract round, upon receiving a user’s identity ID, the KGC generates the first initial key (DID0,QID) of the user by running two sub-algorithms Extract-1 and Extract-2 as follows. In addition, the current system secret key (SKi−1,1,SKi−1,2) is also updated to (SKi,1,SKi,2).
Extract-1: The KGC uses (ID, SKi−1,1) to compute the temporary information TIE and QID as follows.
Choose two random numbers γ, a∈Zp∗.
Compute QID=gγ and SKi,1=SKi−1,1·ga.
Compute the temporary information TIE=SKi,1·(U0·U1ID)γ.
Extract-2: The KGC uses (TIE,SKi−1,2) to generate DID0 as follows.
Compute SKi,2=SKi−1,2·g−a.
Compute DID0 =SKi,2·TIE.
Finally, the KGC sends the first initial key (DID0,QID)=(X·(U0·U1ID)γ,gγ) to the user via a secure channel. Note that the user may validate the correctness of (DID0,QID) by checking the equality e(g,DID0)=XT·e(QID,U0·U1ID).
Set secret value: A user with identity ID chooses a random number z∈Zp∗ and computes the first secret key SID0 and the partial public key RID, where (SID0,RID)=(gz,e(gz,g)).
Set private key: Given the initial key (DID0,QID) and the secret key SID0, the user sets her/his private key by the steps below:
Select two random numbers β, ω∈Zp∗.
Compute the first private key ((DID0,1,DID0,2)=(gβ,DID0·g−β),(SID0,1,SID0,2)=(gω,SID0·g−ω)).
Set public key: Given the initial key (DID0,QID) and the partial public key RID, the user with identity ID sets her/his public key PID=(QID,RID)=(gγ,e(gz,g)).
Encrypt: Given the public key PID=(QID,RID) of a receiver with identity ID, the sender runs the following steps to encrypt the plaintext msg:
Randomly choose k∈Zp∗.
Compute C=gk, K1=(RID)k=e(gz,g)k and K2=(XT·e(QID,U0·U1ID))k.
Set the encryption key K=K1⊕K2.
Generate CT=EK(msg).
Finally, the sender returns the ciphertext (C,CT) to the receiver.
Decrypt: For the j-th Decrypt round, given the ciphertext (C,CT), the receiver with identity ID uses the current private key ((DIDj−1,1,DIDj−1,2), (SIDj−1,1, SIDj−1,2)) to recover the plaintext msg by performing two sub-algorithms as follows. In addition, the current private key ((DIDj−1,1,DIDj−1,2), (SIDj−1,1, SIDj−1,2)) is also updated to ((DIDj,1, DIDj,2), (SIDj,1, SIDj,2)).
Decrypt-1: The receiver uses DIDj−1,1 and SIDj−1,1 to compute the temporary information TI1 and TI2 by the following steps:
Choose two random numbers b,c∈Zp∗.
Update DIDj,1=DIDj−1,1·gb and SIDj,1=SIDj−1,1·gc.
Compute TI1=e(C,SIDj,1) and TI2=e(C,DIDj,1).
Decrypt-2: Given C, CT, TI1 and TI2, the receiver uses DIDj−1,2 and SIDj−1,2 to return plaintext msg by the following steps:
Compute DIDj,2=DIDj−1,2·g−b and SIDj,2=SIDj−1,2·g−c.
Compute K1′=TI1·e(C,SIDj,2) and K2′=TI2·e(C,DIDj,2).
The encryption key is computed by K′=K1′⊕K2′.
Obtain the plaintext msg=DK′(CT) by using a symmetric cryptosystem.
In the following, we show the correctness of recovering the encryption key.
K=K1⊕K2=(RID)k⊕(XT·e(QID,U0·U1ID))k=e(gz,g)k⊕(XT·e(gγ,U0·U1ID))k=e(gk,gz)⊕(e(gx,g)·e(gγ,U0·U1ID))k=e(gk,SID0)⊕(e(g,gx)·e(g,(U0·U1ID)γ)k=e(gk,SID0)⊕(e(g,gx·(U0·U1ID)γ)k=e(gk,SID0)⊕e(gk,X·(U0·U1ID)γ)=e(C,SID0)⊕e(C,DID0)=e(C,SID0·g−ω·gω)⊕e(C,DID0·g−β·gβ)=e(C,gω)·e(C,SID0·g−ω)⊕e(C,gβ)·e(C,DID0·g−β)=e(C,SID0,1)·e(C,SID0,2)⊕e(C,DID0,1)·e(C,DID0,2)=TI1·e(C,SID0,2)⊕TI2·e(C,DID0,2)=K1′⊕K2′=K′.
Security Analysis
As the aforementioned LR-CL-IND-CCA game in Definition 2, there are two types of adversaries, Type I (outsider) and Type II (honest-but-curious KGC). In the section, we present the security analysis of the proposed LR-CL-KE scheme under the continual leakage model for both Type I and Type II adversaries. Indeed, our proposed LR-CL-KE scheme achieves only the CCA1 security (See *Remark in Section 3), but it can’t achieve the CCA2 security. The reason is that an adversary, given the challenge ciphertext C∗ with encryption key K=K1⊕K2, can obtain the entire K via the leakage information. That is, the adversary may ask the Decrypt query with input (C∗)2≠C∗ repeatedly to collect the leakage information about K12 and K22 by Decrypt leak query. Then the adversary can reconstruct K1 and K2 from K12 and K22, respectively. Finally, an adversary may compute the encryption key K=K1⊕K2. To our best knowledge, no LR-CL-KE scheme under continual leakage model can achieve the CCA2 security.
In the following, we first introduce the non-leakage version of our LR-CL-KE scheme, denoted by ΠNL. Then we prove that the non-leakage version ΠNL is CL-IND-CCA secure in the generic bilinear group model. Next, based on the security of the non-leakage version ΠNL, we prove that the proposed LR-CL-KE scheme is LR-CL-IND-CCA secure under the continual leakage model.
The non-leakage version ΠNL of our LR-CL-KE scheme consists of seven algorithms as follows:
SetupNL: In this algorithm, the KGC generates the system secret key X=gx, where x is a random number picked from Zp∗. Moreover, the public parameters PP=(G,GT,e,p,g,XT,U0,U1) are identical to those in the proposed LR-CL-KE scheme. Finally, the KGC publishes the public parameters PP.
Initial key extractNL: The KGC generates the initial key (DID,QID)=(X·(U0·U1ID)γ,gγ) of a user with identity ID, where γ is picked from Zp∗ randomly. The KGC then sends the initial key (DID,QID) to the user via a secure channel.
Set secret valueNL: A user chooses a random number z in Zp∗, and computes the user’s secret key SID=gz and the associated partial public key RID=e(gz,g).
Set private keyNL: A user sets her/his private key (DID,SID)=(X·(U0·U1ID)γ,gz).
Set public keyNL: A user sets her/his public key PID=(QID,RID).
EncryptNL: Given the public key PID=(QID,RID) of a user with identity ID, the sender randomly chooses k∈Zp∗, and then computes C=gk, K1=(RID)k and K2=(XT·e(QID,U0·U1ID))k. The encryption key is K=K1⊕K2. The ciphertext (C,CT=EK(msg)) is sent to the receiver, where msg is the plaintext.
DecryptNL: Upon receiving a user’s identity ID and the ciphertext (C,CT), the receiver uses the private key (DID,SID) to get the encryption key K=K1⊕K2 by computing K1=e(C,SID) and K2=e(C,DID). Then she/he can decrypt the plaintext msg=DK(CT).
In Theorems 1 and 2, we prove that the non-leakage version ΠNL of our LR-CL-KE scheme is CL-IND-CCA secure against Types I and II adversaries, respectively. Moreover, in Theorems 3 and 4, we prove that our LR-CL-KE scheme is LR-CL-IND-CCA secure against Types I and II adversaries, respectively.
In the generic bilinear group model, the non-leakage versionΠNLof our LR-CL-KE scheme is CL-IND-CCA secure against Type I adversary (outsider).
Let ANL−I be Type I adversary (outsider) who can break the non-leakage version ΠNL. The adversary ANL−I can adaptively issue all the queries at most q times in total. The advantage that ANL−I breaks ΠNL is bounded by the success probability of ANL−I in the game gNL−I which is played by a challenger B and the adversary ANL−I as follows:
*GamegNL−I: In the game gNL−I, there are four phases, namely, Setup, Phase 1, Challenge and Guess, which are described as follows.
Setup: The challenger B constructs two lists LG and LT to record the elements in the groups G and GT, respectively.
The list LG consists of elements of the form (PG,m,n,r, ϕG,m,n,r). Each PG,m,n,r is a multivariate polynomial consists of a finite numbers of variates in G with coefficients in Zp. For a multivariate polynomial PG,m,n,r, the challenger B uses a bit string ϕG,m,n,r to communicate with ANL−I. The first index “G” in PG,m,n,r or ϕG,m,n,r indicates that PG,m,n,r or ϕG,m,n,r is an element in G and is an element in GT if the index G is replaced by T. Moreover, the second index “m” indicates the type of query. The third and fourth indices “n” and “r” indicate the r-th element in G/GT which appeared in the n-th query. Four tuples (g,ϕG,I,1,1), (X,ϕG,I,1,2), (U0,ϕG,I,1,3) and (U1,ϕG,I,1,4) are initially added in the list LG.
The list LT is used to record the elements with the form of (PT,m,n,r,ϕT,m,n,r). The meanings of all indexes of PT,m,n,r are the same with the descriptions of PG,m,n,r earlier. PT,m,n,r is a multivariate polynomial with coefficients in Zp and variates in G or GT. For each multivariate polynomial PT,m,n,r, the challenger B uses the bit string ϕT,m,n,r to communicate with ANL−I. The tuple (XT,ϕT,I,1,1) is initially added into LT.
Moreover, two additional lists LIK and LSK are constructed to record the user’s initial key and the user’s secret key, respectively. More precisely, the elements in LIK are of the form (ID,DID,QID) and the elements in LSK are of the form (ID, SID, RID), where ID is in Zp, and DID, QID, SID and RID are multivariate polynomials. At the end of this phase, the challenger B sends the public parameters PP to ANL−I (using the form of bit strings).
Phase 1: In this phase, ANL−I can adaptively issue the following queries at most q times totally.
Group G queryQG (ϕG,Q,i,1, ϕG,Q,i,2, operation): For the i-th group query QG, ANL−I queries B along with two bit strings (ϕG,Q,i,1,ϕG,Q,i,2) and an operation (multiplication or division). The challenger B performs the following steps.
B first translates two bit strings ϕG,Q,i,1 and ϕG,Q,i,2 into two polynomials PG,Q,i,1 and PG,Q,i,2, respectively, in the following way. B tries to find a pair (PG,m,n,r, ϕG,m,n,r) in LG such that ϕG,m,n,r=ϕG,Q,i,1. If so, B sets PG,Q,i,1=PG,m,n,r. Otherwise, B defines a new variate SG,Q,i,1 in G, sets PG,Q,i,1=SG,Q,i,1, and records (PG,Q,i,1,ϕG,Q,i,1) in LG. Similarly, B also translates the bit string ϕG,Q,i,2 to PG,Q,i,2.
B computes the polynomial PG,Q,i,3=PG,Q,i,1+PG,Q,i,2 if the operation is multiplication, or PG,Q,i,3=PG,Q,i,1−PG,Q,i,2 if the operation is division.
B uses PG,Q,i,3 to find an element (PG,m,n,r,ϕG,m,n,r) in LG such that PG,m,n,r=PG,Q,i,3. If so, B returns ϕG,m,n,r to ANL−I. Otherwise, B randomly chooses a bit string, denoted by ϕG,Q,i,3, which is distinct from all bit strings recorded in LG and LT. Finally, B records (PG,Q,i,3,ϕG,Q,i,3) in LG and returns ϕG,Q,i,3 to ANL−I.
Note that the polynomials PG,Q,i,1, PG,Q,i,2 and PG,Q,i,3 mentioned above are recorded in the list LG.
GroupGTqueryQT(ϕT,Q,i,1, ϕT,Q,i,2, operation): For the i-th group query QT, ANL−I queries B along with two bit strings (ϕT,Q,i,1, ϕT,Q,i,2) and an operation (multiplication or division). The process of this query is similar to that of the Group G query QG. B finally returns ϕT,Q,i,3 to ANL−I. After this query, the polynomials PT,Q,i,1, PT,Q,i,2 and PT,Q,i,3 are recorded in LT.
Pairing queryQP(ϕG,P,i,1,ϕG,P,i,2): For the i-th pairing query QP, ANL−I takes as input two bit strings ϕG,P,i,1 and ϕG,P,i,2. B performs the following steps:
B first translates two bit strings ϕG,P,i,1 and ϕG,P,i,2 to two polynomials PG,P,i,1 and PG,P,i,2, respectively. This step is similar to the Step 1 of the Group G queryQG.
B computes the polynomial PT,P,i,1=PG,P,i,1·PG,P,i,2.
B uses PT,P,i,1 to find (PT,m,n,r,ϕT,m,n,r) in LT such that PT,m,n,r=PT,P,i,1. If so, B returns ϕT,m,n,r to ANL−I. Otherwise, B randomly chooses a bit string, denoted by ϕT,P,i,1, which is distinct from all bit strings recorded in LG and LT. Then B records (PT,P,i,1,ϕT,P,i,1) in LT and returns ϕT,P,i,1 to ANL−I.
Note that the polynomials PG,P,i,1, PG,P,i,2 and PT,P,i,1 are recorded in the list LG or LT after this query.
Initial key extract queryQIE(IDIE,i): For the i-th Initial key extract query, ANL−I queries B along with a user’s identity IDIE,i∈Zp∗. B tries to find IDIE,i in LIK. If so, B obtains the corresponding multivariate polynomials PG,IE,i,1 and PG,IE,i,2 of the user’s initial key DID and QID. B then returns two corresponding bit strings ϕG,IE,i,1 and ϕG,IE,i,2 to ANL−I. Otherwise, B performs three steps as follows:
B selects one variate TG,IE,i,2 in G (which denotes the QID of IDIE,i) and sets PG,IE,i,2=TG,IE,i,2. Moreover, B randomly chooses a bit string, denoted by ϕG,IE,i,2, which is distinct from all bit strings recorded in LG and LT. Then B records (PG,IE,i,2, ϕG,IE,i,2) in LG.
B computes the polynomial PG,IE,i,1=X+(U0+IDIE,i·U1)·TG,IE,i,2, which represents the DID of IDIE,i.
Finally, B chooses a bit string ϕG,IE,i,1, which is distinct from all bit strings recorded in LG and LT. Then B records (PG,IE,i,1, ϕG,IE,i,1) in LG and returns (ϕG,IE,i,1, ϕG,IE,i,2 ) to ANL−I.
The challenger B also records a tuple (IDIE,i, PG,IE,i,1, PG,IE,i,2) in the list LIK.
Secret key extract queryQSE(IDSE,i): For the i-th Secret key extract query, ANL−I queries the challenger B along with an identity IDSE,i. B performs the following steps and finally outputs the bit strings (ϕT,SE,i,1, ϕT,SE,i,2), which represent the secret key (SID, RID) to ANL−I:
The challenger B checks whether the secret key of identity IDSE,i has been recorded in LSK. If so, B returns the bit strings (ϕT,SE,i,1, ϕT,SE,i,2), which represents the secret key (SID,RID) to ANL−I. Otherwise, B defines a new variate TG,SE,i,2 in G and sets PG,SE,i,1=TG,SE,i,1, which represents the SID of IDSE,i. Moreover, B randomly chooses a new bit string, denoted by ϕG,SE,i,1, which is distinct from all bit strings recorded in LG and LT. Then B records (PG,SE,i,1, ϕG,SE,i,1) in LG.
B sets the polynomial PT,SE,i,2=TG,SE,i,1·g, which represents the RID for IDSE,i.
Finally, B first randomly chooses a new bit string, denoted by ϕT,SE,i,2, which is distinct from all bit strings recorded in LG and LT. Then B records (PT,SE,i,2, ϕT,SE,i,2) in LT and returns (ϕG,SE,i,1, ϕT,SE,i,2) to ANL−I.
The challenger B also records (IDSE,i, PG,SE,i,1, PT,SE,i,2) in the list LSK.
Public key retrieve queryQPK(IDPK,i): Upon receiving the i-th Public key retrieve query with an identity IDPK,i∈Zp∗ as input, the challenger B performs the following three steps:
B checks whether IDPK,i has been recorded in LIK. If so, B obtains the corresponding polynomial of QID for IDPK,i in LIK. Otherwise, B performs the Initial key extract query along with identity IDPK,i to generate the polynomial of QID.
B also checks whether IDPK,i has been recorded in LSK. If so, B obtains the corresponding polynomial of RID for IDPK,i in LSK. Otherwise, B performs the Secret key extract query with identity IDPK,i to generate the polynomial of RID for IDPK,i.
Finally, C returns two bit strings of polynomials representing QID and RID by searching LG and LT, respectively.
Public key replace queryQPR(IDPR,i,ϕT,PR,i,2): By this query, the adversary ANL−I is allowed to use the bit string ϕT,PR,i,2 to replace the partial public key RID of a user with identity IDPR,i. That is, ANL−I can select a valid secret key SID (i.e. bit string ϕT,PR,i,2) by herself/himself and set the corresponding RID. B then records this replacement. More precisely, upon receiving this query, B first translates ϕT,PR,i,2 into the corresponding polynomial PT,PR,i,2 by the list LT. Since ANL−I has the ability to generate the user’s secret key by asking the group oracles, B can obtain the polynomial PG,PR,i,1 by searching PT,PR,i,2=PG,PR,i,1·g in the list LG. The challenger B then updates the user’s secret key (IDPR,i, SIDPR,i, RIDPR,i)=(IDPR,i, PG,PR,i,1, PT,PR,i,2) in LSK.
Decrypt queryQD(IDD,i,Ci,CTi): For the i-th Decrypt round, when ANL−I queries B along with a user’s identity IDD,i and a ciphertext pair (Ci,CTi), B performs the following two parts to obtain the encryption key K:
When B receives the query, B first obtains the user’s initial key DID and secret key SID from the lists LIK and LSK, respectively, by the following procedures:
B uses IDD,i to find the user’s initial key DID in the list LIK. If so, B obtains DID in LIK. Otherwise, B issues the query QIE(IDD,i) to obtain DID.
B uses IDD,i to find the user’s secret key SID in the list LSK. If so, B obtains SID in LSK. Otherwise, B issues the query QSE(IDD,i) to obtain SID.
Hence, B has obtained the polynomials PG,IE,k,1 and PG,SE,l,1, which represent DID and SID, respectively.
The challenger B obtains the encryption key K by performing the following steps:
B checks whether the corresponding polynomial of the ciphertext Ci has been recorded in the list LG. If so, B obtains the polynomial PG,D,i,3. Otherwise, B defines a new variate TG,D,i,3 in G and sets PG,D,i,3=TG,D,i,3. Moreover, B randomly chooses a bit string, denoted by ϕG,D,i,3, which is distinct from all bit strings in LG and LT.
B computes the polynomial PT,D,i,1=PG,SE,l,1·TG,D,i,1 (which denotes K1) and the polynomial PT,D,i,2=PG,IE,l,1·TG,D,i,1 (which denotes K2). B uses PT,D,i,1 and PT,D,i,2 to respectively find (PT,m,j,r,ϕT,m,j,r) and (PT,m,j,2,ϕT,m,j,2) in LT (i.e. PT,m,j,r=PT,D,i,1 and PT,m,j,2=PT,D,i,2). If so, B then sets the ϕT,D,i,1=ϕT,m,j,r and ϕT,D,i,2=ϕT,m,j,2. Otherwise, B randomly chooses two bit strings, denoted by ϕT,D,i,1 and ϕT,D,i,2, which represent the bit strings of K1 and K2, respectively. Then B records (PT,D,i,1, ϕT,D,i,1) and (PT,D,i,2, ϕT,D,i,2) in LT.
Finally, B computes the bit string ϕT,D,i,4=ϕT,D,i,1⊕ϕT,D,i,2 (which denotes K). At the end of this query, the challenger B obtains the plaintext msgi=DK(CTi) by using the decryption key K. Finally, B returns msgi to ANL−I.
Challenge: The adversary ANL−I gives a target identity ID∗ and a plaintext pair (msg0∗,msg1∗) to B. Because ANL−I is an outsider, ID∗ is disallowed to be queried in the Initial key extract query of Phase 1. The challenger B first chooses a random bit β∈{0,1}, then B defines a new variate TG,C,1,3 in G and sets PG,C,1,3=TG,C,1,3 (which denotes C∗). Moreover, B randomly chooses a bit string, denoted by ϕG,C,i,3. Afterwards, B obtains K by the same steps described in the second part of the Decrypt query. At the end of this phase, the challenger B computes the ciphertext CT∗=EK(msgβ∗). Finally, B returns C∗ and CT∗ to ANL−I.
Guess: The adversary ANL−I outputs β′∈{0,1}. If β′=β, we say that the adversary ANL−I wins the game gNL−I.
Here, both the adversary ANL−I and the challenger B have completed the game gNL−I. Before evaluating the probability of ANL−I winning the game gNL−I, we first define several notations and restrictions as follows.
In the Phase 1, ANL−I may issue eight kinds of queries QG, QT, QP, QIE, QSE, QPK, QPR, QD. We define several collections (sets) as follows:
{S}: The collection of all used variates SG,Q,i,j in the query QG and SG,P,i,j in the query QP.
{V}: The collection of all used variates VT,Q,i,j in the query QT.
{T}: The collection of all used variates TG,IE,i,2 in the query QIE, TG,D,i,3 in the query QD and TG,SE,i,1 in the query QSE.
{PG}: The collection of all used polynomials PG,Q,i,k , PG,IE,i,k and PG,D,i,k in the Phase 1.
{PT}: The collection of all used polynomials PT,Q,i,k and PT,P,i,k in the Phase 1.
Let qO denote the total number of three queries QG, QT and QP while qIE, qSE, qPK, qPR and qD, respectively, represent the numbers of QIE, QSE, QPK, QPR and QD. Note that ANL−I can issue all kinds of queries at most q times in total. Hence, we have q⩾qO+qIE+qSE+qPK+qPR+qD. Let |LG| and |LT| be the total numbers of elements in LG and LT, respectively. Therefore, |LG|+ |LT| is bounded by 6q due to the following reasons:
For each query of QG, QT or QP, at most 3 elements are recorded in LG or LT.
For each query of QIE or QSE, at most 2 new elements are recorded in LG or LT.
For each query of QPK, at most 4 new elements are recorded in LG or LT.
For each query of QPR, at most 2 new elements are recorded in LG or LT.
For each query of QD, at most 6 new elements are recorded in LG or LT.
Hence, we have
|LG|+|LT|⩽5+3qO+2qIE+2qSE+4qPK+2qPR+6qD+1.
Let 6⩽3qO+4qIE+4qSE+2qPK+4qPR, we have
|LG|+|LT|⩽3qO+2qIE+2qSE+4qPK+2qPR+6qD+6⩽6q.
In the following, we discuss the degrees of all multivariate polynomials in {PG}.
All polynomials in {S} and {T} are of degree 1.
In QIE, each polynomial PG,IE,i,k has degree at most 2.
In QSE, each polynomial PG,SE,i,1 has degree 1.
In QD, each polynomial PG,D,i,k has degree at most 2.
In QG, the polynomial PG,Q,i,3 is generated by PG,Q,i,3=PG,Q,i,1+PG,Q,i,2. Hence the degree of PG,Q,i,3 is less than or equal to the maximal degree of PG,Q,i,1 and PG,Q,i,2.
Therefore, the degrees of all multivariate polynomials in {PG} are at most 2.
In the following, we obtain that the degrees of all multivariate polynomials in {PT} are at most 4:
All polynomials in {V} are of degree 1.
In QP, the degree of each polynomial PT,P,i,k is at most 4 since each polynomial PG has degree at most 2.
In QSE, the degree of each polynomial PT,SE,i,2 is 2.
In QT, the polynomial PT,Q,i,3 is generated by PT,Q,i,3=PT,Q,i,1+PT,Q,i,2. Hence, the degree of PG,Q,i,3 is less than or equal to the maximal degree of PT,Q,i,1 and PT,Q,i,2.
In the following, let us discuss the probability that ANL−I wins the game gNL−I. After completing the game gNL−I, the challenger B chooses random values x, u0, u1, {s1,s2,…,}, t1,t2,…, in Zq∗, which represent the values X, U0, U1, {S}, {T} in the group G. B also chooses random values {v1,v2,…,} in Zq∗, which represent the values {V} in the group GT. ANL−I is said to win the game gNL−I if one of the following cases happens:
Case 1. There is a collision in G or GT which can be described as follows:
In the list LG, there exist two polynomials PG,i and PG,j such that PG,i(x , u0, u1, {s}, {t})=PG,j(x,u0,u1,{s},{t}).
In the list LT, there exist two polynomials PT,i and PT,j such that PT,i(x,u0,u1,s,{t},{v})=PT,j(x,u0,u1,s,{t},{v}) .
Case 2. The adversary ANL−I outputs β′=β in the Guess phase.
In the real CL-IND-CCA game, the success probability in the simulated game gNL−I is an upper bound of the success probability of ANL−I. Let us discuss the probabilities of two cases as follows.
Case 1. If ANL−I can find any collisions within G or GT, one can solve the discrete logarithm problem in G or GT. Let PG,i and PG,j denote two distinct polynomials in LG. Then we obtain the polynomials PG,C=PG,i−PG,j is a non-zero polynomial of degree at most 2. By applying Lemma 2 in Section 2 with λ=0, the probability that PG,C(x,u0,u1,{s},{t})=0 in Zq is at most 2p. Since there are |LG|2 different pairs (PG,i,PG,j), the probability that Case 1 occurs is at most 2p|LG|2. Similarly, the collision probability in LT is at most 4p|LT|2 since the polynomials in LT have degree at most 4.
Case 2. If ANL−I can’t find any collision in G or GT, the view of ANL−I in the game gNL−I is identical to that in the real CL-IND-CCA game. If the adversary ANL−I doesn’t obtain any useful information in the game gNL−I, she/he still has the probability 12 on average to output a correct β′=β.
Now we evaluate the probability that ANL−I wins the game gNL−I, denoted by PrNL−I. Firstly, we define two events of PrNL−I as follows.
The event FAC denotes that ANL−I can find a collision in G or GT.
The event GBC denotes that ANL−I can output β′=β.
Meanwhile, let FAC‾ and GBC‾ denote the complement events of FAC and GBC, respectively. The probability that ANL−I wins gNL−I can be bounded by
PrNL−I⩽Pr[FAC]+Pr[FAC‾∧GBC].
Here, as discussed in Case 1, the probabilities that ANL−I can find a collision in G and GT are 2p|LG|2 and 4p|LT|2, respectively. Hence, we have
Pr[FAC]⩽[2p|LG|2+4p|LT|2]⩽2p(|LG|+|LT|)2⩽72q2p.
On the other hand, in case ANL−I can’t find collisions in G or GT, ANL−I still has probability 12 on average to make a correct guess of β′. Therefore, we have
PrNL−I⩽Pr[FAC]+Pr[FAC‾∧GBC]⩽72q2p+(1−72q2p)·12.
The advantage of ANL−I is
AdvA⩽|72q2p+12·(1−72q2p)−12|=36q2p,
which is negligible if q=poly(logp). □
In the generic bilinear group model, the non-leakage versionΠNLof our LR-CL-KE scheme is CL-IND-CCA secure against Type II adversary (honest-but-curious KGC).
Let ANL−II be a Type II adversary who can break the non-leakage CL-KE scheme ΠNL. Meanwhile, the adversary ANL−II is allowed to issue all queries at most q times. The advantage that ANL−II breaks ΠNL is bounded by the success probability of ANL−II in the game gNL−II which is played by both the adversary ANL−II and a challenger B as follows:
GamegNL−II: In the game gNL−II, there are four phases, namely, Setup, Phase 1, Challenge and Guess.
Setup: In this phase, the challenger B constructs two lists LG and LT to record the elements in G and GT, respectively. B also maintains two lists LIK and LSK to record the user’s initial key and the user’s secret key, respectively. The forms of LG, LT, LIK and LSK are the same with those described in the game gNL−I. At the end of this phase, the challenger B sends the bit strings of the public parameters PP to ANL−II. Since ANL−II represents an honest-but-curious KGC, B also sends the system secret key X (using the form of bit string) to ANL−II.
Phase 1: Since ANL−II models the honest-but-curious KGC, ANL−II can obtain the user’s initial key by issuing the queries QG, QT and QP. Meanwhile, ANL−II is not allowed to perform the Public key replacement query. In this phase, ANL−II can adaptively issue the queries as follows:
Group G queryQG(ϕG,Q,i,1, ϕG,Q,i,2, operation): The query is identical to QG presented in the game gNL−I.
GroupGTqueryQT(ϕT,Q,i,1, ϕT,Q,i,2, operation): The query is identical to QT presented in the game gNL−I.
Pairing queryQP(ϕG,P,i,1, ϕG,P,i,2 ): The query is identical to QP presented in the game gNL−I.
Secret key extract queryQSE(IDSE,i): The query is identical to QSE presented in the game gNL−I.
Public key retrieve queryQPK(IDPK,i): For the i-th Public key retrieve query with an identity IDPK,i, B runs three steps as follows:
B checks whether IDPK,i was recorded in LIK. If so, B may obtain the corresponding polynomial of QID for IDPK,i. Otherwise, B uses the records of the queries QG, QT and QP to obtain the corresponding polynomials of DID and QID for IDPK,i while updating the list LIK for IDPK,i.
B checks whether IDPK,i was recorded in LSK. If so, B may obtain the corresponding polynomial of RID for IDPK,i. Otherwise, B may issue the Secret key extract queryQSE(IDPK,i) to obtain the corresponding polynomial of RID for IDPK,i.
Finally, B returns QID and RID (with the form of bit strings) by searching the lists LG and LT, respectively.
Decrypt queryQD(IDD,i,Ci,CTi): For the i-th Decrypt round, when ANL−II queries B along with a user’s identity IDD,i and a ciphertext pair (Ci,CTi), B performs the following two parts to obtain the encryption key K:
B first obtains the user’s initial key DID and secret key SID from the lists LIK and LSK as follows:
B checks whether the user’s initial key DID of IDD,i has been recorded in LIK. If so, B obtains the corresponding polynomial of DID for IDD,i in LIK. Otherwise, B uses the records of the queries QG, QT and QP to obtain the corresponding polynomials of DID and QID for IDD,i while updating the list LIK for IDD,i.
B uses IDD,i to find the user’s secret key SID in the list LSK. If so, B obtains SID in LSK. Otherwise, B issues the query QSE(IDD,i) to obtain SID.
Hence, B have obtained the corresponding polynomials PG,IE,k,1 and PG,SE,l,1, which represent DID and SID, respectively.
B can obtain the encryption key K by using the same steps in the Decrypt query of the game gNL−I.
Finally, B computes the bit string ϕT,D,i,4=ϕT,D,i,1⊕ϕT,D,i,2 (which denotes K). At the end of this query, B obtains the plaintext msgi=DK(CTi) by using the decryption key K. Finally, B returns msgi to ANL−II.
Challenge: This phase is similar to the Challenge phase described in gNL−I. The only difference is that ID∗ is not allowed to be queried in the Secret key extract query of Phase 1 since ANL−II is the honest-but-curious KGC.
Guess: The adversary ANL−II outputs β′∈{0,1}. If β′=β, we say that the adversary ANL−II wins the game gNL−II.
As the same arguments in Theorem 1, we can compute the success probability of ANL−II in the game gNL−II. We first compute the number of |LG|+|LT|. We have |LG|+|LT|⩽5+3qO+2qSE+4qPK+4qD+1=3qO+2qSE+4qPK+4qD+6⩽4q by letting 6⩽qO+2qSE. And we may obtain Pr[FAC]⩽32q2p, where the event FAC denotes that ANL−II can find a collision in G or GT. So, the success probability of ANL−II is
PrNL−II⩽Pr[FAC]+Pr[FAC‾∧GBC]⩽32q2p+12·(1−32q2p).
Hence, the adversary ANL−II’s advantage is
AdvA⩽|32q2p+12·(1−32q2p)−1/2|=16q2p,
which is negligible if q=poly(logp). □
In the generic bilinear group model, the proposed LR-CL-KE scheme Π is LR-CL-IND-CCA secure against Type I adversary (outsider) under the continual leakage model.
In Theorem 1, we have shown that the non-leakage version ΠNL of the proposed LR-CL-KE scheme is CL-IND-CCA secure against Type I adversary. Under the continual leakage model, an adversary is allowed to issue two additional leakage queries, Initial key extract leak query and Decrypt leak query. Let ALR−I be a Type I adversary who may break the proposed LR-CL-KE scheme ΠLR. ALR−I can adaptively issue the queries at most q times in total. In the following, we present a game gLR−I extended from the game gNL−I in Theorem 1 as follows. GamegLR−I: In the game gLR−I, there are four phases that include Setup, Phase 1, Challenge and Guess. Four phases are presented as follows:
Setup: The phase is identical to that of the game gNL−I.
Phase 1: In this phase, the adversary ALR−I can issue two additional leakage queries than the adversary ANL−I in the game gNL−I, namely, Initial key extract leak query and Decrypt leak query. In order to record the leakage information for two kinds of leak queries, we build four initial-empty lists Lf,IE, Lh,IE, Lf,D and Lh,D as follows:
Lf,IE={(fIE,i,ΛfIE,i),1⩽i⩽qIE},Lh,IE={(hIE,i,ΛhIE,i),1⩽i⩽qIE},Lf,D={(fD,j,ΛfD,j),1⩽j⩽qD},Lh,D={(hD,j,ΛhD,j),1⩽j⩽qD}.
Two leakage functions fIE,i and hIE,i are, respectively, used to model the adversary’s leak ability for two sub-algorithms Extract-1 and Extract-2 of the i-th Initial key extract round. Also, two leakage functions fS,j and hS,j are, respectively, used to model the adversary’s leak ability for two sub-algorithms Decrypt-1 and Decrypt-2 of a user’s j-th Decrypt round. Moreover, the leakage information ΛfIE,i, ΛhIE,i, ΛfD,j and ΛhD,j denote the outputs of four leakage functions fIE,i , hIE,i, fD,j and hD,j, respectively. In the following, we describe two additional leakage queries as follows:
Initial key extract leak query(fIE,i,hIE,i,i): For the i-th Initial key extract query, ALR−I can issue the Initial key extract leak query only once by providing two leakage functions fIE,i and hIE,i such that |fIE,i|⩽λ and |hIE,i|⩽λ. B computes and sends the leakage information (ΛfIE,i,ΛhIE,i) to ALR−I, where ΛfIE,i=fIE,i(SKi−1,1,γi,ai) and ΛhIE,i=hIE,i(SKi−1,2,TIIE,ai). Meanwhile, B records (fIE,i,ΛfIE,i) in the list Lf,IE and (hIE,i,ΛhIE,i) in the list Lh,IE.
Decrypt leak query(fD,j,hD,j,j): For the j-th Decrypt query, ALR−I can issue the Decrypt leak query only once by providing two leakage functions fD,j and hD,j such that |fD,i|⩽λ and |hD,i|⩽λ. B computes and sends the leakage information (ΛfD,j,ΛhD,j) to ALR−I, where ΛfD,j=fD,j(DIDj−1,1,bj,cj) and ΛhD,j=hD,j(DIDj−1,2,TI1,j,TI2,j,bj,cj,K1,j,K2,j,Kj). Meanwhile, B records (fD,j,ΛfD,j) in the list Lf,D and (hD,j, ΛhD,j) in the list Lh,D.
Challenge: The adversary ALR−I gives a target identity ID∗ and a plaintext pair (msg0∗, msg1∗) to B. This phase is identical to the Challenge phase in gNL−I. Finally, B sends C∗ and CT∗ to ALR−I.
Guess: The adversary ALR−I outputs β′∈{0,1}. If β′=β, we say that the adversary ALR−I wins the game gLR−I.
In the game gLR−I, ALR−I has higher probability to cause collisions by making use of the leakage functions. Two leakage information ΛfIE,i and ΛhIE,i, respectively, respresent the ouputs of two leakage functions fIE,i and hIE,i in the i-th Initial key extract query. By ΛfIE,i and ΛhIE,i, the leaked information about (SKi−1,1,γi,ai) and (SKi−1,2,TIIE,ai) are discussed below:
γi: The value γi is used to generate the initial key (DID0,QID) for IDIE,i in the Initial key extract query. By Definition 2 in Section 3.2, if IDIE,i has been queried in the Initial key extract query, it is not allowed to be a target identity in the Challenge phase. Hence, the leakage of γi is useless for ALR−I.
(SKi−1,1,SKi−1,2): Since the system secret key X=SKi−1,1·SKi−1,2, obtaining some leakage information of SKi,1 and SKi,2 is contributive to learn partial information of X for ALR−I. Indeed, ALR−I can learn at most 2λ bits of the system secret key X.
ai: The parameter ai is used to generate the next system secret key (SKi,1,SKi,2) from (SKi−1,1,SKi−1,2). Hence, ALR−I may obtain at most λ bits of SKi,1 and SKi,2, respectively.
TIIE: The temporary information TIIE is only used to generate the initial key DID0 for IDIE,i. TIIE is helpless in this game gLR−I since IDIE,i is not allowed to be a target identity in the Challenge phase.
On the other hand, two leakage information ΛfD,j and ΛhD,j, respectively, respresent the ouputs of two leakage functions fD,j and hD,j in the j-th Decrypt leak query. By ΛfD,j and ΛhD,j, the leaked information about (DIDj−1,1,bj,cj) and (DIDj−1,2,TI1,j,TI2,j,bj,cj,K1,j,K2,j,Kj) are discussed below:
(DIDj−1,1,DIDj−1,2): Since the user’s first initial key DID0=DIDj−1,1,DIDj−1,2, obtaining some leakage information of DIDj−1,1 and DIDj−1,2 is contributive to learn partial information of DID0 for ALR−I. Indeed, ALR−I can learn at most 2λ bits of the user’s initial key DID0.
(TI1,j,TI2,j): The temporary information TI1,j and TI2,j are used to compute K1,j and K2,j, respectively. Since each encryption key Kj=K1,j⊕K2,j is independent with each other, obtaining TI1,j and TI2,j is helpless in the Guess phase.
bj: The parameter bj is used to compute the user’s initial key (DIDj,1,DIDj,2) from (DIDj−1,1,DIDj−1,2). Therefore, ALR−I can learn at most λ bits of DIDj,1 and DIDj,2, respectively.
cj: The parameter cj is used to compute the user secret key (SIDj,1,SIDj,2) from (SIDj−1,1,SIDj−1,2). Therefore, ALR−I can learn at most λ bits of SIDj,1 and SIDj,2, respectively.
(K1,j,K2,j,Kj): For the j-th Decrypt query, ALR−I can use the leakage function hD,j to obtain the leakage information about (K1,j,K2,j,Kj) once for totally at most λ bits. Since K1,j and K2,j can only be used to generate Kj, adversary ALR−I can learn at most λ bits information about Kj in the game gL−IR.
Now, let us discuss the success probability PrLR−I that ALR−I wins the game gLR−I. Since ALR−I can get the secret key of any entity, ALR−I always outputs a correct β′ when she/he gets the target user’s initial key DID0 or the system secret key X. Firstly, we define three events of PrLR−I as follows.
The event EI denotes that the adversary ALR−I may obtain DID0 completely from the leakage information ΛfD,j and ΛhD,j.
The event ES denotes that the adversary ALR−I may obtain the system secret key X completely from the leakage information ΛfIE,i and ΛhIE,i.
The event EC denotes that the adversary ALR−I may output a correct β′.
In addition, let ES‾ and EI‾, respectively, denote the complement events of ES and EI. The success probability PrLR−I that the adversary ALR−I wins the game gLR−I is bounded as follows.
PrLR−I=Pr[EC]=Pr[EC∧ES]+Pr[EC∧ES‾]=Pr[EC∧ES]+Pr[EC∧ES‾∧EI]+Pr[EC∧ES‾∧EI‾]=Pr[EC∧ES]+Pr[EC∧ES‾∧EI]+Pr[EC|ES‾∧EI‾]·(Pr[ES‾∧EI‾].
Since Pr[EC∧ES]⩽Pr[ES] and Pr[EC∧ES‾∧EI]⩽Pr[ES‾∧EI], we obtain
PrLR−I⩽Pr[ES]+Pr[ES‾∧EI]+Pr[OBC|ES‾∧EI‾]·Pr[ES‾∧EI‾].
Let us focus on Pr[EC|ES‾∧EI‾]. Under the condition ES‾∧EI‾, ALR−I can’t obtain the useful information to output β′ correctly. Hence, Pr[EC|ES‾∧EI‾] is 12 on average. Thus, we obtain
Pr[EC|ES‾∧EI‾]·Pr[ES‾∧EI‾]=(1/2)(1−Pr[ES]−Pr[ES‾∧EI]).
Hence, we have
PrLR−I⩽1/2+(1/2)(Pr[ES]+Pr[ES‾∧EI]).
Lemmas 3 and 4 below offer upper bounds for Pr[ES] and Pr[ES‾∧EI], respectively. By assuming these results, the adversary ALR−I’s advantage is
AdvA⩽|PrLR−I−12|=|12(Pr[ES]+Pr[ES‾∧EI])|=|12(O(q2p·22λ)+O(q2p·22λ))|⩽O(q2p·22λ).
Hence, the advantage of the adversary ALR−I breaking our LR-CL-KE scheme is O(q2p·22λ). By Corollary 1, if λ≪log(p)2, we say that the proposed scheme ΠLR is LR-CL-IND-CCA secure against Type I adversary (outsider) under the continual leakage model. □
Pr[ES]⩽O(q2p·22λ).
In the Initial key extract algorithm of our LR-CL-KE scheme, the initial key of a user is a signature on her/his identity ID, which is generated by the signature scheme proposed by Galindo and Virek (2013). Hence, the probability Pr[ES] is then bounded by the probability that the adversary can compute the secret key in Galindo and Vivek’s scheme. By applying the Lemma 5 in Galindo and Virek (2013), we have Pr[ES]⩽O(q2p·22λ). □
Pr[ES‾∧EI]⩽O(q2p·22λ).
Under the condition ES‾, ALR−I can’t obtain the system secret key X. We focus on the probability that ALR−I can obtain DID0 completely under the condition ES‾. As described earlier, no useful information of DID0 can be obtained from the leakage information ΛfIE,i and ΛhIE,i in the Initial key extract leak query. However, ALR−I may obtain some useful information of DID0 by the Decrypt leak query. In such a case, Pr[ES‾∧EI] denotes that ALR−I can obtain the user’s initial key without using the leakage functions fIE,i and hIE,i. As described earlier, the useful information to generate the user’s initial key DID0 from the leakage functions fD,j and hD,j are (DIDj−1,1,DIDj−1,2) and bj. In our scheme, the user’s initial key is updated in the beginning of two sub-algorithms Decrypt-1 and Decrypt-2. Hence, the adversary can learn at most 2λ bits about DID0. Considering the advantage that ANL−I obtains in Theorem 1, the probability that the adversary ANL−I can find a collision is Pr[FAC]⩽72q2p. By applying Lemma 2, we have Pr[ES‾∧EI] is bounded by 72q2p·22λ. Hence, we obtain Pr[ES‾∧EI]⩽O(q2p·22λ). □
In the generic bilinear group model, the proposed LR-CL-KE scheme Π is LR-CL-IND-CCA secure against Type II adversary (honest-but-curious KGC) under the continual leakage model.
In Theorem 2, we have shown that the non-leakage version ΠNL of the proposed LR-CL-KE scheme is CL-IND-CCA secure against Type II adversary. Under the continual leakage model, an adversary is allowed to issue two additional leakage queries, Initial key extract leak query and Decrypt leak query. Let ALR−II be a Type II adversary who may break the proposed LR-CL-KE scheme ΠLR. ALR−II can adaptively issue the queries at most q times in total. In the following, we present a game gLR−II extended from the game gNL−II in Theorem 2 as follows. GamegLR−II. In the game gLR−II, there are four phases, Setup, Phase 1, Challenge and Guess.
Setup: The phase is identical to that of gNL−II.
Phase 1: In this phase, ALR−II can issue an extra leakage query (i.e. Decrypt leak query) than the adversary ANL−II in the game gNL−II. In order to record the leakage information for the Decrypt leak query, we build two initial-empty lists Lf,D and Lh,D, which are identical to those in the game gLR−I.
Decrypt leak query(fD,j,hD,j,j): This query is identical to the Decrypt leak query described in gLR−I.
Challenge: The adversary ALR−II gives a target identity ID∗ and a plaintext pair (msg0∗, msg1∗) to B. This phase is identical to the Challenge phase in gNL−II. Finally, B sends C∗ and CT* to ALR−II.
Guess: The adversary ALR−II outputs β′∈{0,1}. If β′=β, we say that the adversary ALR−II wins the game gLR−II.
In gLR−II, ALR−II has higher probability to cause collisions by making use of the leakage functions. In the j-th Decrypt leak query, two leakage information ΛfD,j and ΛhD,j, respectively, respresent the ouputs of two leakage functions fD,j and hD,j. By ΛfD,j and ΛhD,j, the adversary ALR−II can obtain the partial information of both (SIDj−1,1,bj,cj) and (SIDj−1,2,TI1,i,TI2,i,bj,cj,K1,i,K2,i,Ki). The discussions on the partial leakage information of (TI1,i, TI2,i, bj, cj, K1,i, K2,i, Ki) are the same with those in Theorem 3. In addition, the leaked information about (SIDj−1,1,SIDj−1,2) is discussed below:
(SIDj−1,1,SIDj−1,2): Since the user’s secret key SID0=SIDj−1,1·SIDj−1,2, obtaining some leakage information of SIDj−1,1 and SIDj−1,2 is contributive to learn the partial information of SID0 for ALR−II. Indeed, ALR−II can learn at most 2λ bits of the user’s secret key SID0.
Now, let us discuss the success probability PrLR−II that the adversary ALR−II wins the game gLR−II. Since ALR−II holds the system secret key X, ALR−II can obtain each user’s initial key DID0. If ALR−II can obtain the user’s secret key SID, ALR−II always outputs a correct β′. Here we define two events of PrLR−II as follows.
The event EU denotes that the user’s secret key SID0 can be obtained completely by ALR−II from the leakage information ΛfD,j and ΛhD,j.
The event EC denotes that ALR−II can guess β′ correctly.
In addition, the event EU‾ is the complement event of EU. The success probability PrLR−II that the adversary ALR−II wins the game gLR−II is bounded as follows.
PrLR−II=Pr[EC]=Pr[EC∧EU]+Pr[EC∧EU‾]=Pr[EC∧EU]+Pr[EC|EU‾]·Pr[EU‾].
Since Pr[EC∧EU]⩽Pr[EU], we have
PrLR−II⩽Pr[EU]+Pr[EC|EU‾]·Pr[EU‾].
Let us focus on Pr[EC|EU‾]. Under the condition EU‾, ALR−II can’t obtain useful information to output β′ correctly. Hence, Pr[EC|EU‾] is equal to 12 plus the advantage O(q2p) of the adversary ANL−II in Theorem 2. Thus, we obtain
Pr[EC|EU‾]·Pr[EU‾]=12(1−Pr[EC∧EU]).
Hence, we have PrLR−I⩽12+12Pr[EU]. By assuming Lemma 5 below, we obtain an upper bound for ALR−II’s advantage as
AdvA⩽|PrLR−I−12|=|12Pr[EU]|⩽O(q2p22λ).
Thus, the advantage of the adversary ALR−II breaking our LR-CL-KE scheme is O(1p22λ). By Corollary 1, if λ≪log(p)2, we say that the proposed scheme ΠLR is LR-CL-IND-CCA secure against Type II adversary (honest-but-curious KGC) under the continual leakage model. □
Pr[EU]⩽O(q2p22λ).
Considering the advantage that ANL−II obtains in Theorem 2, the probability that ANL−II can find a collision is Pr[FAC]⩽32q2p. Since ALR−II can learn at most 2λ bits information for the user current secret key in the Decrypt leak query, by applying Lemma 2, we have Pr[EU] is bounded by 32q2p22λ. Hence, we obtain Pr[EU]⩽O(q2p)22λ). □
Performance Analysis
In this section, we compare the proposed LR-CL-KE scheme with the leakage-resilient certificateless public key encryption (LR-CL-PKE) scheme proposed by Xiong et al. (2013). In the following, we define several notations to analyse the computational costs.
Te: The time of executing an exponentiation operation in G or GT.
Tp: The time of executing a bilinear pairing operation e: G×G→GT.
When compared to Te and Tp, the multiplication operation in the multiplicative group G or GT is trivial and negligible (Scott, 2011). Table 1 lists the comparisons between the proposed LR-CL-KE scheme and Xiong et al.’s LR-CL-PKE scheme (Xiong et al., 2013) in terms of the size of encryption cost, decryption cost, security model, security property and leakage model. Note that a user’s private key in Xiong et al.’s LR-CL-PKE scheme is a vector with n elements. For the costs of encryption and decryption, Xiong et al.’s scheme requires (n+4)Te and (n+2)Tp, respectively. In the proposed LR-CL-KE scheme, 4Te+Tp and 4Te+4Tp are required for encryption and decryption, respectively.
For the security model and security property, Xiong et al. employed the dual system encryption technique (Lewko et al., 2011) to define semi-functional (SF) keys and ciphertexts. In the standard model, they then proved that their scheme possesses the LR-CCA1 security under the bounded leakage model. As mentioned earlier, we formally proved that, in the GBG model, our LR-CL-KE scheme is LR-CCA1 secure against both Type I and Type II adversaries under continual leakage model.
Comparisons between our LR-CL-KE scheme and the previously proposed schemes.
The LR-CL-PKE scheme (Xiong et al., 2013)
The proposed LR-CL-KE scheme
Encryption cost
(n+4)Te
4Te+4Tp
Decryption cost
(n+2)Tp
4Te+4Tp
Security model
Standard model (Dual system)
GBG model
Security property
LR-CCA1
LR-CCA1
Leakage model
Bounded leakage
Continue leakage
Conclusions and Future Work
The first LR-CL-KE scheme under the continual leakage model was proposed in the article. We defined a new adversary model for LR-CL-KE schemes under the continual leakage model. The adversary model also consists of two types of adversaries. Type I adversary can obtain partial information of a user’s initial key in the Decrypt phase and KGC’s system secret key in the Initial key extract phase. Type II adversary can obtain partial information of a user’s secret key in the Decrypt phase since she/he already knows the initial key of any user. In the GBG model, we formally proved that our LR-CL-KE scheme is semantically secure against chosen ciphertext attacks for both Type I and Type II adversaries. It is worth mentioning that the proposed LR-CL-KE scheme achieves only the LR-CCA1 security, but not the LR-CCA2 security. Indeed, it is an interesting and open problem to propose a LR-CCA2 secure LR-CL-PKE or LR-CL-KE scheme under the continual leakage model. Furthermore, up to date, there does not exist leakage-resilient RSA-based certificateless encryption/signature schemes under continual leakage model. Indeed, it is also an interesting issue to design efficient leakage-resilient RSA-based certificateless encryption/signature schemes.
Acknowledgements
The authors would like to appreciate anonymous referees for their valuable comments and constructive suggestions. This research was partially supported by Ministry of Science and Technology, Taiwan, under contract no. MOST106-2221-E-018-007-MY2.
ReferencesAkavia, A., Goldwasser, S., Vaikuntanathan, V. (2009). Simultaneous hardcore bits and cryptography against memory attacks. In: TCC’09, LNCS, Vol. 5444, pp. 474–495.Al-Riyami, S.S., Paterson, K.G. (2003). Certificateless public key cryptography. In: ASIACRYPT’03, LNCS, Vol. 2894, pp. 452–473.Alwen, J., Dodis, Y., Wichs, D. (2009). Leakage-resilient public-key cryptography in the bounded-retrieval model. In: CRYPTO’09, LNCS, Vol. 5677, pp. 36–54.Biham, E., Carmeli, Y., Shamir, A. (2008). Bug attacks. In: CRYPTO’08, LNCS, Vol. 5157, pp. 221–240.Boneh, D., Franklin, M. (2001). Identity-based encryption from the Weil pairing. In: CRYPTO’01, LNCS, Vol. 2139, pp. 213–229.Boneh, D., Demillo, R.A., Lipton, R.J. (1997). On the importance of checking cryptographic protocols for faults. In: EUROCRYPT’97, LNCS, Vol. 1233, pp. 37–51.Boneh, D., Boyen, X., Goh, E.J. (2005). Hierarchical identity-based encryption with constant size ciphertext. In: EUROCRYPT’05, LNCS, Vol. 3494, pp. 440–456.Brakerski, Z., Kalai, Y.T., Katz, J., Vaikuntanathan, V. (2010). Cryptography resilient to continual memory leakage. In: 51st Annual IEEE Symposium on Foundations of Computer Science. IEEE Press, pp. 501–510.Brumley, D., Boneh, D. (2005). Remote timing attacks are practical. Computer Networks, 48(5), 701–716.Dodis, Y., Haralambiev, K. (2010). Cryptography against continuous memory attacks. In: 51st Annual IEEE Symposium on Foundations of Computer Science. IEEE Press, pp. 511–520.Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A. (2008). Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM Journal on Computing, 38(1), 97–139.Galindo, D., Virek, S. (2013). A practical leakage-resilient signature scheme in the generic group model. In: SAC’12, LNCS, Vol. 7707, pp. 50–65.Galindo, D., Grobschadl, J., Liu, Z., Vadnala, P.K., Vivek, S. (2016). Implementation of a leakage-resilient ElGamal key encapsulation mechanism. Journal of Cryptographic Engineering, 6(3), 229–238.Hu, B., Wong, D., Zhang, Z., Deng, X. (2007). Certificateless signature: a new security model and an improved generic construction. Designs, Codes and Cryptography, 42(2), 109–126.Huang, X., Mu, Y., Susilo, W., Wong, D., Wu, W. (2007). Certificateless signature revisited. In: ACISP’06, LNCS, Vol. 4586, pp. 308–322.Hung, Y.H., Huang, S.S., Tseng, Y.M., Tsai, T.T. (2015). Certificateless signature with strong unforgeability in the standard model. Informatica, 26(4), 663–684.Hung, Y.H., Tseng, Y.M., Huang, S.S. (2016). A revocable certificateless short signature scheme and its authentication application. Informatica, 27(3), 549–572.Hung, Y.H., Huang, S.S., Tseng, Y.M., Tsai, T.T. (2017). Efficient anonymous multireceiver certificateless encryption. IEEE Systems Journal, 11(4), 2602–2613.Hwang, Y.H., Liu, J.K., Chow, S.S.M. (2008). Certificateless public key encryption secure against malicious KGC attacks in the standard model. Journal of Universal Computer Science, 14(3), 463–480.Katz, J., Vaikuntanathan, V. (2009). Signature schemes with bounded leakage resilience. In: ASIACRYPT’09, LNCS, Vol. 5912, pp. 703–720.Kiltz, E., Pietrzak, K. (2010). Leakage resilient elgamal encryption. In: ASIACRYPT’10, LNCS, Vol. 6477, pp. 595–612.Kocher, P.C. (1996). Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: CRYPTO’96, LNCS, Vol. 1163, pp. 104–113.Kocher, P., Jaffe, J., Jun, B. (1999). Differential power analysis. In: CRYPTO’99, LNCS, Vol. 1666, pp. 388–397.Lewko, A.B., Rouselakis, Y., Waters, B. (2011). Achieving leakage resilience through dual system encryption. In: TCC’11, LNCS, Vol. 6597, pp. 70–88.Li, S., Zhang, F., Sun, Y., Shen, L. (2013). Efficient leakage-resilient public key encryption from DDH assumption. Cluster Computing, 16(4), 797–806.Li, J., Guo, Y., Yu, Q., Lu, Y., Zhang, Y. (2016). Provably secure identity based encryption resilient to post challenge continuous auxiliary input leakage. Security and Communication Network, 9(10), 1016–1024.Libert, B., Quisquater, J.J. (2006). On constructing certificateless cryptosystems from identity based encryption. In: PKC’06, LNCS, Vol. 3958, pp. 474–490.Lin, X.J., Sun, L., Qu, H. (2017). An efficient RSA-based certificateless public key encryption scheme. Discrete Applied Mathematics. https://doi.org/10.1016/j.dam.2017.02.019.Liu, S., Weng, J., Zhao, Y. (2013). Efficient public key cryptosystem resilient to key leakage chosen ciphertext attacks. In: CTRSA’13, LNCS, Vol. 7779, pp. 84–100.Maurer, U., Wolf, S. (1998). Lower bounds on generic algorithms in groups. In: EUROCRYPT’98, LNCS, Vol. 1403, pp. 72–84.Naor, M., Segev, G. (2009). Public-key cryptosystems resilient to key leakage. In: CRYPTO’09, LNCS, Vol. 5677, pp. 18–35.Naor, M., Segev, G. (2012). Public-key cryptosystems resilient to key leakage. SIAM Journal on Computing, 41(4), 772–814.Schwartz, J.T. (1980). Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4), 701–717.Scott, M. (2011). On the efficient implementation of pairing-based protocols. In: Cryptography and Coding, LNCS, Vol. 7089, pp. 296–308.Shamir, A. (1984). Identity-based cryptosystems and signature schemes. In: CRYPTO’84, LNCS, Vol. 196, pp. 47–53.Sharma, G., Bala, S., Verma, A. (2016). An improved RSA-based certificateless signature scheme for wireless sensor networks. International Journal of Network Security, 18(1), 82–89.Shoup, V. (1997). Lower bounds for discrete logarithms and related problems. In: EUROCRYPT’97, LNCS, Vol. 1233, pp. 256–266.Tsai, T.T., Tseng, Y.M. (2015). Revocable certificateless public key encryption. IEEE Systems Journal, 9(3), 824–833.Tsai, T.T., Tseng, Y.M., Huang, S.S. (2015). Efficient revocable certificateless public key encryption with a delegated revocation authority. Security and Communication Networks, 8(18), 3713–3725.Waters, B. (2005). Efficient identity-based encryption without random oracles. In: EUROCRYPT’05, LNCS, Vol. 3494, pp. 114–127.Wu, J.D., Tseng, Y.M., Huang, S.S. (2016). Leakage-resilient ID-based signature scheme in the generic bilinear group model. Security and Communication Networks, 9(17), 3987–4001.Xiong, H., Yuen, T.H., Zhang, C., Yiu, S.M., He, Y.J. (2013). Leakage-resilient certificateless public key encryption. In: The first ACM workshop on Asia Public-Key Cryptography. ACM Press, pp. 13–22.Yuen, T.H., Chow, S.S.M., Zhang, Y., Yiu, S.M. (2012). Identity-based encryption resilient to continual auxiliary leakage. In: EUROCRYPT’12, LNCS, Vol. 7237, pp. 117–134.Zhang, J., Mao, J. (2012). An efficient RSA-based certificateless signature scheme. Journal of Systems and Software, 85(3), 638–642.Zhou, Y., Yang, B., Zhang, W. (2016). Provably secure and efficient leakage-resilient certificateless signcryption scheme without bilinear pairing. Discrete Applied Mathematics, 204, 185–202.Zippel, R. (1979). Probabilistic algorithms for sparse polynomials. In: EUROSAM’79, LNCS, Vol. 72, pp. 216–226.