Introduction

INFORMATICA

Informatica

1822-88440868-4952

0868-4952

Vilnius University

INFOR474

10.15388/22-INFOR474

Research Article

Leakage-Resilient Revocable Certificateless Encryption with an Outsourced Revocation Authority

Tseng

Yuh-Min

ymtseng@cc.ncue.edu.tw1∗

Y.-M. Tseng is currently the vice president and 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). He has published over one hundred scientific journal papers on various research areas of cryptography, security and computer network. His research interests include cryptography, network security, computer network and leakage-resilient cryptography. He serves as an editor of several international journals.

Huang

Sen-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 leakage-resilient cryptography. He received his PhD from the University of Illinois at Urbana-Champaign in 1997 under the supervision of Professor Bruce C. Berndt.

Tsai

Tung-Tso

T.-T. Tsai is currently an assistant professor in the Department of Computer Science and Engineering, National Taiwan Ocean University, Taiwan. His research interests include applied cryptography, pairing-based cryptography and leakage-resilient cryptography. He received the PhD degree from the Department of Mathematics, National Changhua University of Education, Taiwan, in 2014, under the supervision of Professor Yuh-Min Tseng.

Chuang

Yun-Hsin

Y.-H. Chuang received the PhD degree from the Department of Computer Science and Engineering, National Taiwan University, Taiwan, in 2020. His research interests include information security, cryptography and leakage-resilient cryptography.

Hung

Ying-Hao

Y.-H. Hung received the PhD degree from the Department of Mathematics, National Changhua University of Education, Taiwan, in 2017 under the supervision of Professor Yuh-Min Tseng. His research interests include applied cryptography and pairing-based cryptography.

1Department of Mathematics, National Changhua University of Education, Changhua 500, Taiwan 2Department of Computer Science and Engineering, National Taiwan Ocean University, Keelung 202, Taiwan

∗Corresponding author.

2022

2412022

3311511793202112022

2022

Open access article under the CC BY license.

To resolve both certificate management and key escrow problems, a certificateless public-key system (CLPKS) has been proposed. However, a CLPKS setting must provide a revocation mechanism to revoke compromised users. Thus, a revocable certificateless public-key system (RCLPKS) was presented to address the revocation issue and, in such a system, the key generation centre (KGC) is responsible to run this revocation functionality. Furthermore, a RCLPKS setting with an outsourced revocation authority (ORA), named RCLPKS-ORA setting, was proposed to employ the ORA to alleviate the KGC’s computational burden. Very recently it was noticed that adversaries may adopt side-channel attacks to threaten these existing conventional public-key systems (including CLPKS, RCLPKS and RCLPKS-ORA). Fortunately, leakage-resilient cryptography offers a solution to resist such attacks. In this article, the first leakage-resilient revocable certificateless encryption scheme with an ORA, termed LR-RCLE-ORA scheme, is proposed. The proposed scheme is formally shown to be semantically secure against three types of adversaries in the RCLPKS and RCLPKS-ORA settings while resisting side-channel attacks. In the proposed scheme, adversaries are allowed to continually extract partial ingredients of secret keys participated in various computational algorithms of the proposed scheme while retaining its security.

Key words leakage-resilience certificateless encryption revocation key encapsulation

This research was partially supported by Ministry of Science and Technology, Taiwan, under contract no. MOST110-2221-E-018-006-MY2, MOST110-2221-E-018-007-MY2 and MOST110-2222-E-019-001-MY2.

1 Introduction

To eliminate the management of both public keys and their associated certificates in the traditional public-key systems (PKS), an identity (ID)-based public-key system (IDPKS) was proposed (Boneh and Franklin, 2001). In an IDPKS setting, a private key generator (PKG) is responsible to generate all participants’ secret keys. Hence, the IDPKS setting has an inborn disadvantage, namely, the key escrow problem in the sense that the PKG can decrypt any ciphertexts of all participants and sign any messages on behalf of all participants. To resolve both certificate management and key escrow problems, Al-Riyami and Paterson (2003) proposed the certificateless public-key system (CLPKS). In which, there are two kinds of participants, namely, a key generation center (KGC) and users. The KGC is responsible to generate all users’ identity secret keys. In the meantime, each user chooses a personal secret key and sets the associated public key. Therefore, each user has two secret keys, namely, identity secret key and personal secret key. Obviously, the CLPKS setting can solve both the key escrow and certificate management problems.

Under some situations, a user’s ID or public key has to be revoked before expiration. Although the certificate revocation list (CRL) (Housley et al., 2002) is a well-known revocation method, it is unsuitable for IDPKS and CLPKS settings because no certificate is required. Therefore, an IDPKS or CLPKS setting must provide a revocation mechanism to revoke compromised users. Tseng and Tsai (2012) has presented a revocable IDPKS setting. By this revocable concept of Tseng and Tsai, revocable CLPKS (RCLPKS) settings (Shen et al., 2014; Tsai and Tseng, 2015; Hung et al., 2016) were presented to address the revocation issue and the key generation center (KGC) is also responsible to run this revocation functionality. Furthermore, a RCLPKS setting with an outsourced revocation authority (ORA), named RCLPKS-ORA setting (Tsai et al., 2015; Du et al., 2018), was presented to employ the ORA to alleviate the KGC’s computational burden.

Typically, all public-key systems mentioned above have a nature assumption that secret (or private) keys are completely hidden to adversaries. However, a new type of attacks, called “side-channel attacks”, has threatened these existing public-key systems. An adversary may employ side-channel attacks, such as power analysis (Kocher et al., 1999) and timing attack (Kocher, 1996; Brumley and Boneh, 2005) to continually obtain partial ingredients of a participant’s secret (or private) keys so that the associated cryptographic schemes/protocols could be broken. Ways to withstand side-channel attacks on cryptographic schemes/protocols have received significant attention of researchers. Fortunately, leakage-resilient cryptography offers a solution to resist such attacks. Up to date, little research addresses leakage-resilient certificateless public-key systems. In this paper, our aim is to propose the first leakage-resilient revocable certificateless encryption (LR-RCLE) scheme with an outsourced revocation authority (ORA), termed LR-RCLE-ORA scheme.

1.1 Related Work

In leakage-resilient cryptography, a cryptographic scheme/protocol remains secure even though partial ingredients of a participant’s secret (or private) keys in this scheme/protocol is leaked to adversaries. For leakage property, there are two leakage models, namely, bounded and continual. In the bounded leakage model (Katz and Vaikuntanathan, 2009; Alwen et al., 2009), total leaked bit sizes of secret keys for a cryptographic scheme/protocol are limited during its life cycle. Obviously, this limitation is impractical. In contrast, in the continual leakage model, adversaries may continually get leaked information of secret keys for each invocation of cryptographic scheme/protocol. Indeed, the continual leakage model is more accredited (Galindo and Virek, 2013; Wu et al., 2019, 2020; Tseng et al., 2020; Hsieh et al., 2020; Tsai et al., 2021) and it consists of four properties as follows:

•

Only computation leakage: An adversary can extract partial ingredients of secret keys involved in the current computation round.

•

Bounded leakage of single computational algorithm: A cryptographic scheme/protocol typically includes several computation rounds. In each computation round, an adversary can extract partial ingredients of secret keys. Namely, an adversary can select a leakage function f for each computation round and obtain the leaked information f ( SK ), where SK denotes the involved secret keys and f ( SK ) is bounded to λ bits.

•

Independent leakage: Any two leaked partial ingredients of secret keys in various computation rounds are mutually independent. For achieving this property, a secret key must be updated before (or after) running each computation round.

•

Overall unbounded leakage: The total amount of leaked information is overall unbounded. Indeed, by the independent leakage property, the total leakage amount of secret keys is unlimited.

According to the usage of secret key or public key, there are two kinds of encryption schemes, namely, symmetric encryption and asymmetric encryption based on various public-key systems. For a symmetric encryption scheme, a pre-shared secret key between a sender and a receiver is used to encrypt and decrypt procedures. A symmetric encryption scheme is typically employed to encrypt a large size of message and have high-throughput efficiency. On the contrary, for an asymmetric encryption scheme, a sender uses a designated receiver’s public key to encrypt message while the receiver uses her/his private key to decrypt it. Generally, an asymmetric encryption scheme is employed to encrypt a short size of message (e.g. a session key) or authenticate identity/message so that the throughput of encryption/decryption procedure is not their priority. Also, for considering leakage-resilient property, there are two kinds of leakage-resilient encryption schemes, namely, leakage-resilient symmetric encryption and leakage-resilient asymmetric encryption based on various public-key systems.

Here, let’s introduce the evolution of leakage-resilient symmetric encryption schemes. The first generic construction of leakage-resilient symmetric encryption based on minimal assumptions has been proposed by Hazay et al. (2013). However, the efficiency of Hazay et al.’s scheme is not good so that Abdalla et al. (2013) improved their scheme to propose an efficient leakage-resilient symmetric encryption scheme using the AES block cipher without constructing a leakage resilient block cipher. Recently, for enhancing the efficiency, several leakage-resilient authenticated symmetric encryption schemes based on hardware AES coprocessors (Unterstein et al., 2020; Bronchain et al., 2021) have been proposed.

In the following, several leakage-resilient asymmetric encryption (or key encapsulation) schemes based on traditional PKS, IDPKS and CLPKS settings are reviewed. Based on a traditional PKS setting, the first leakage-resilient encryption (LRE) scheme was presented by Akavia et al. (2009). Subsequently, several LRE schemes (Naor and Segev, 2009, 2012; Liu et al., 2013; Li et al., 2013) were proposed to improve security and performance of Akavia et al.’s scheme. However, all these LRE schemes above are secure only in the bounded leakage model. Moreover, Kiltz and Pietrzak (2010) presented the first LRE scheme under the continual leakage model. Furthermore, Galindo et al. (2016) presented an efficient ElGamal-like LRE scheme under the continual leakage model. Based on an IDPKS setting, Brakerski et al. (2010) proposed the first leakage-resilient ID-based encryption (LR-IBE) scheme under the continual leakage model. Subsequently, several LR-IBE schemes (Yuen et al., 2012; Li et al., 2016) were also proposed to improve security and performance of Brakerski et al.’s scheme.

Up to date, little research addresses leakage-resilient certificateless public-key systems. In 2013, the first leakage-resilient certificateless encryption (LR-CLE) scheme was presented by Xiong et al. (2013). To improve the security and performance of Xiong et al.’s scheme, Zhou et al. (2016) proposed a new leakage-resilient certificateless signcryption scheme. However, both Zhou et al.’s and Xiong et al.’s schemes are secure only under the bounded leakage model. In 2018, Wu et al. (2018) proposed the first LR-CLE scheme under the continual leakage model. In the generic bilinear group (GBG) model (Boneh et al.), Wu et al.’s LR-CLE scheme is semantically secure against chosen ciphertext attacks for two adversaries, namely, outsider and honest-but-curious KGC.

1.2 Contribution and Organization

As mentioned earlier, a RCLPKS setting with an outsourced revocation authority (ORA), named RCLPKS-ORA setting, can revoke compromised users and alleviate the KGC’s revocation computation burden. However, up to date, there are no leakage-resilient revocable certificateless encryption (LR-RCLE) or leakage-resilient revocable certificateless key encapsulation scheme. In this article, the first leakage-resilient revocable certificateless encryption scheme with an ORA, termed LR-RCLE-ORA scheme, is proposed. By extending the adversary models of the revocable certificateless encryption (RCLE) (Tsai and Tseng, 2015) and leakage resilience certificateless encryption (LR-CLE) schemes (Xiong et al., 2013; Wu et al., 2018), a new adversary model of LR-RCLE-ORA schemes is presented. Under this new adversary model, the proposed scheme is formally shown to be semantically secure against three types of adversaries, namely, outsider, revoked user and honest-but-curious KGC. Finally, comparisons with previously proposed schemes (Tsai and Tseng, 2015; Xiong et al., 2013; Wu et al., 2018), the proposed scheme has the following merits. (1) It can resist side-channel attacks and has leakage resilience properties. (2) The revocation functionality is outsourced to an ORA to alleviate the computational load of the KGC. (3) It permits adversaries to continually extract partial ingredient of secret keys and offers the overall unbounded leakage property.

The remaining paper is organized as below. Several preliminaries are presented in Section 2. In Section 3, the syntax (framework) and adversary model (security notions) of LR-RCLE-ORA schemes are defined. The proposed LR-RCLE-ORA scheme is presented in Section 4. In Section 5, the security of the proposed scheme is formally established. The comparisons of the proposed scheme with some RCLE and LR-CLE schemes are given in Section 6. Conclusions are drawn in Section 7.

2 Preliminaries 2.1 Bilinear Groups

Let G 1 be an additive group of a prime order p and Q be a generator of G 1 . Let G 2 be a multiplicative group of the same order p. A bilinear admissible pairing e ˆ : G 1 × G 1 → G 2 possesses the following properties:

–

Bilinear: for r , s ∈ Z p ∗ , e ˆ ( r · Q , s · Q ) = e ˆ ( Q , Q ) r s ;

–

Non-degenerate: e ˆ ( Q , Q ) ≠ 1;

–

Efficiently computable: for R , S ∈ G 1 , e ˆ ( R , S ) is efficiently computed.

We say that { G 1 , G 2 , p , Q , e ˆ } are the bilinear group parameters. A reader may refer to Boneh and Franklin (2001), Scott (2011) for detailed definitions of bilinear groups.

2.2 Generic Bilinear Group Model

In 2005, Boneh et al. (2005) defined the generic bilinear group (GBG) model, which is a technique of proving the security of some cryptographic schemes. In the GBG model, the discrete logarithm problems on groups of a large order would be solved if collisions of the groups were found by adversaries after finishing the security games of the cryptographic scheme.

In the GBG model, as mentioned in Section 2.1, let { G 1 , G 2 , p , Q , e ˆ } be the bilinear group parameters and let each element in two groups G 1 and G 2 be represented by distinct bit-strings. In such a case, a random injective mapping Φ 1 : Z p ∗ → ξ G 1 is used to encode all elements of G 1 , where ξ G 1 denotes the set of the encoded bit-strings of G 1 . By the same reason, the other random injective mapping Φ 2 : Z p ∗ → ξ G 2 is employed to encode all elements of G 2 , where ξ G 2 denotes the set of the encoded bit-strings of G 2 . Two sets ξ G 1 and ξ G 2 satisfy | ξ G 1 | = | ξ G 2 | = p and ξ G 1 ∩ ξ G 2 = ϕ. In addition, let three operations O 1 , O 2 and O p , respectively, denote the addition of G 1 , the multiplication of G 2 and the bilinear pairing e ˆ. To perform these group operations, an adversary must request the associated operations (oracles) O 1 , O 2 and O p which are defined as below: –

O 1 ( Φ 1 ( r ) , Φ 1 ( s ) ) → Φ 1 ( r + s mod p );

–

O 2 ( Φ 2 ( r ) , Φ 2 ( s ) ) → Φ 2 ( r + s mod p );

–

O p ( Φ 1 ( r ) , Φ 1 ( s ) ) → Φ 2 ( r s mod p ).

Note that r , s ∈ Z p ∗

, Q = Φ 1 ( 1 )

and e ˆ ( Q , Q ) = Φ 2 ( 1 )

After finishing the security games in the GBG model of a cryptographic scheme, the discrete logarithm problem on G 1 or G 2 would be resolved if adversaries discovered a collision on G 1 or G 2 . The discrete logarithm problem and assumption are presented as below: –

Discrete logarithm (DL) problem and assumption: Let { G 1 , G 2 , p , Q , e ˆ } be the bilinear group parameters. Given a group element r · Q ∈ G 1 or e ˆ ( Q , Q ) r ∈ G 2 for unknown r ∈ Z p ∗ , the DL problem is to find r from r · Q or e ˆ ( Q , Q ) r . The DL assumption is that no polynomial time algorithm A with non-negligible probability can discover r.

2.3 The Security Measure of Leaked Information

To measure the security influence incurred by leaked information of secret keys (finite random variables) involved in a cryptographic scheme, we first introduce the concept of entropy. The entropy of a random variable is employed to denote its uncertainty for guessing this random variable. Let R be a finite random variable and let Pr [ R = r ] denote the associated probability of R = r. In the following, we present two kinds of min-entropies:

Min-entropy of R: H ∞ ( R ) = − log 2 ( max r Pr [ R = r ] ) ;

Average conditional min-entropy of R under the condition S = s: H ˜ ∞ ( R | S = s ) = − log 2 ( E s ← S [ max r Pr [ R = r | S = s ] ] ) .

In 2008, Dodis et al. (2008) inferred the following consequence related to the security influence incurred by leaked information of a secret key (finite random variable).

Lemma 1.

Let λ denote the maximal bit-length of leaked information of a secret key (a finite random variable) R. Let f : R → { 0 , 1 } λ denote the associated leakage function of R. Under the condition f ( R ), the average conditional min-entropy on R is H ˜ ∞ ( R | f ( R ) ) ≧ H ∞ ( R ) − λ.

Galindo and Virek (2013) further presented the following consequences related to multiple secret keys (finite random variables). Lemma 2.

Let R 1 , R 2 , … , R n be n random variables. Let F ∈ Z p [ R 1 , R 2 , … , R n ] be a polynomial with at most degree d. Let P k denote a probability distribution on Z p such that H ∞ ( P k ) ≧ log p − λ and 0 ≦ λ ≦ log p, for k = 1 , 2 , … , n. If all R k = r k ← Z p with probability distribution P k are mutually independent, we have Pr [ F ( R 1 = r 1 , R 2 = r 2 , … , R n = r n ) = 0 ] ≦ ( d / p ) 2 λ .

Corollary 1.

Pr [ F ( R 1 = r 1 , R 2 = r 2 , … , R n = r n ) = 0 ] is negligible if λ < ( 1 − ϵ ) log p, where ϵ is a positive value.

3 Syntax and Adversary Model Fig. 1

The system architecture of a LR-RCLE-ORA scheme.

The syntax (framework) and adversary model (security notions) of LR-RCLE-ORA schemes are presented as follows.

3.1 Syntax of LR-RCLE-ORA schemes

Here, let us present the system architecture of an LR-RCLE-ORA scheme as depicted in Fig. 1. An LR-RCLE-ORA scheme consists of three roles, namely, a key generation centre (KGC), an outsourced revocation authority (ORA) and users (senders and receivers). Each user with an identity ID randomly selects a personal secret key PSK ID by herself/himself. For each user with ID, the KGC with a secret key KSK is responsible to generate and securely send an identity secret key ISK ID to the user. For each non-revoked user with ID at each period T s , the ORA with a time secret key TSK is responsible to generate and publicly send a time update key TUK ID , s to the user. For compromised or revoked users, the ORA will not generate any associated time update keys. At period T s , when a sender would like to encrypt a plaintext msg to a receiver with ID, the sender uses the receiver’s ID and associated public keys to encrypt msg to generate a ciphertext tuple ( ID , T s , θ ) while sending ( ID , T s , θ ) to the receiver. The receiver then uses her/his PSK ID , ISK ID and TUK ID , s to decrypt ( ID , T s , θ ) to obtain msg.

In the following, we summarize some notations used in the whole paper:

•

KSK: the KGC’s secret key;

•

KPK: the KGC’s public key;

•

TSK: the time secret key;

•

TPK: the time public key;

•

ID: a user’s identity;

•

PSK ID : a user ID’s personal secret key;

•

PPK ID : a user ID’s personal public key;

•

ISK ID : a user ID’s identity secret key;

•

IPK ID : a user ID’s identity public key;

•

T s : a period T s ∈ { 0 , 1 } ∗ , for s = 1 , … , t, where t denotes the period length;

•

TUK ID , s : a user ID’s time update key at period T s ;

•

TUPK ID , s : a user ID’s time update public key at period T s ;

•

msg: a message;

•

θ: a ciphertext.

Fig. 2

The algorithm architecture of the proposed LR-RCLE-ORA scheme.

Based on the syntax (framework) in (Tsai and Tseng, 2015; Xiong et al., 2013; Wu et al., 2018), the syntax of LR-RCLE-ORA schemes is defined as follows. An LR-RCLE-ORA scheme consists of three roles, namely, a key generation centre (KGC), an outsourced revocation authority (ORA) and users (senders and receivers) while including eight algorithms: (1) System setup; (2) Personal secret key setting; (3) Identity secret key extract; (4) Time update key extract; (5) Private key setting; (6) Public key setting; (7) Encrypting; (8) Decrypting. Fig. 2 depicts the algorithm architecture, interactions and their inputs/outputs of the proposed LR-RCLE-ORA scheme. Eight algorithms of the LR-RCLE-ORA scheme are presented in Definition 1 as below:

Definition 1.

An LR-RCLE-ORA scheme consists of three roles, namely, a key generation centre (KGC), an outsourced revocation authority (ORA) and users (senders and receivers). Eight algorithms of the LR-RCLE-ORA scheme are presented as below: –

System setup: By taking as input a security parameter κ and a period number t, the KGC generates the KGC’s secret key KSK = ( KSK 0 , 1 , KSK 0 , 2 ) and associated public key KPK, the time secret key TSK = ( TSK 0 , 1 , TSK 0 , 2 ), and time public key TPK. The KGC then securely sends TSK to the ORA. Finally, the KGC publishes t periods T 1 , T 2 , … , T t and public system parameters PSP.

–

Personal secret key setting: Each user with an identity ID randomly selects a personal secret key PSK ID = ( PSK ID , 0 , 1 , PSK ID , 0 , 2 ) and generates the associated personal public key PPK ID .

–

Identity secret key extract: In this algorithm’s i-th round, by taking as input a user ID and ( KSK i − 1 , 1 , KSK i − 1 , 2 ), the KGC first carries out two sub-algorithms ISKExtract-1 ( ID , KSK i − 1 , 1 ) and ISKExtract-2 ( KSK i − 1 , 2 ) to set the new KGC’s secret key ( KSK i , 1 , KSK i , 2 ), and generate the user’s identity secret key ISK ID and associated identity public key IPK ID . Finally, the KGC securely sends IPK ID and ISK ID to the user.

–

Time update key extract: In this algorithm’s j-th round, by taking as input a user ID, a period T s and ( TSK j − 1 , 1 , TSK j − 1 , 2 ), the ORA carries out two sub-algorithms TUKExtract-1 ( ID , T s , TSK j − 1 , 1 ) and TUKExtract-2 ( TSK j − 1 , 2 ) to set the new time secret key ( TSK j , 1 , TSK j , 2 ), and generate the user’s time update key TUK ID , s and associated time update public key TUPK ID , s at period T s . Finally, the ORA sends TUK ID , s and TUPK ID , s to the user.

–

Private key setting: At period T s , a user ID’s private key tuple includes three parts, namely, PSK ID , ISK ID , and TUK ID , s . The user also sets PSK ID = ( PSK ID , 0 , 1 , PSK ID , 0 , 2 ) and ISK ID = ( ISK ID , 0 , 1 , ISK ID , 0 , 2 ).

–

Public key setting: At period T s , a user ID’s public key tuple includes three parts, namely, PPK ID , IPK ID , and TUPK ID , s .

–

Encrypting: At period T s , by taking as input a plaintext msg and a receiver ID with public key tuple ( PPK ID , IPK ID , TUPK ID , s ), the sender generates a ciphertext tuple ( ID , T s , θ = ( C , CT = E EK ( m s g ) ) ), where E EK ( · ) is a symmetric encryption function and EK is an encryption key encrypted to generate C. Finally, the sender returns the ciphertext tuple ( ID , T s , θ = ( C , CT ) ).

–

Decrypting: In this algorithm’s k-th round, by taking as input ( ID , T s , θ = ( C , CT ) ), a receiver with ID uses her/his private key tuple ( PSK ID = ( PSK ID , k − 1 , 1 , PSK ID , k − 1 , 2 ), ISK ID = ( ISK ID , k − 1 , 1 , ISK ID , k − 1 , 2 ), TUK ID , s ) to carry out two sub-algorithms DEC-1 ( PSK ID , k − 1 , 1 , ISK ID , k − 1 , 1 ) and DEC-2 ( PSK ID , k − 1 , 2 , ISK ID , k − 1 , 2 , TUK ID , s , T s , θ = ( C , CT ) ) to set new private key tuple ( PSK ID = ( PSK ID , k , 1 , PSK ID , k , 2 ) , ISK ID = ( ISK ID , k , 1 , ISK ID , k , 2 ) , TUK ID , s ), compute the encryption key EK from C, and decrypt m s g = D EK ( CT ), where D EK ( · ) is the corresponding symmetric decryption function of E EK ( · ).

3.2 Adversary Model of LR-RCLE-ORA Schemes

By the entropy concept of secret keys mentioned in Section 2.3, six leakage functions f ISKE , i , h ISKE , i , f TUKE , j , h TUKE , j , f DEC , k and h DEC , k are employed to present capabilities of adversaries obtaining leaked information of secrets keys. Both f ISKE , i and h ISKE , i are employed to obtain leaked information of the KGC’s secret key ( KSK i , 1 , KSK i , 2 ) used in the Identity secret key extract algorithm’s i-th round. Both f TUKE , j and h TUKE , j are employed to obtain leaked information of the time secret key ( TSK j , 1 , TSK j , 2 ) used in the Time update key extract algorithm’s j-th round. Furthermore, both f DEC , k and h DEC , k are employed to obtain leaked information of a receiver’s private key tuple ( PSK ID = ( PSK ID , k , 1 , PSK ID , k , 2 ) , ISK ID = ( ISK ID , k , 1 , ISK ID , k , 2 ) , TUK ID , s ) used in the Decrypting algorithm’s k-th round of a user ID. An adversary can obtain at most λ bits of secret keys used in each associated algorithm, where λ is related to the security parameter selected in the System setup algorithm. Namely, | f ISKE , i |, | h ISKE , i |, | f TUKE , j |, | h TUKE , j |, | f DEC , k |, | h DEC , k | ≦ λ, where | · | denotes the output bit-length of a function. The leaked information of a leakage function f is denoted by Λ f. In the sequel, leaked information of the six leakage functions are denoted as below:

–

Λ f ISKE , i = f ISKE , i ( KSK i , 1 );

–

Λ h ISKE , i = h ISKE , i ( KSK i , 2 );

–

Λ f TUKE , j = f TUKE , j ( TSK j , 1 );

–

Λ h TUKE , j = h TUKE , j ( TSK j , 2 );

–

Λ f DEC , k = f DEC , k ( PSK ID , k , 1 , ISK ID , k , 1 );

–

Λ h DEC , k = h DEC , k ( PSK ID , k , 2 , ISK ID , k , 2 , TUK ID , k , 2 ).

By extending the adversary model (security notions) in Tsai and Tseng (2015), Xiong et al. (2013), Wu et al. (2018), the adversary model of LR-RCLE-ORA schemes consists of three types of adversaries, namely, outsider (Type I, A I ), revoked user (Type II, A II ) and honest-but-curious KGC (Type III, A III ).

–

Outsider ( A I ): Although A I is not a legal user of the LR-RCLE-ORA scheme, it may obtain the time update key TUK ID , s of any user ID at any period T s from public channels. Also, A I may get the personal secret key PSK ID and the identity secret key ISK ID of any user ID, but it is disallowed to get the identity secret key ISK ID ∗ of the target user ID ∗ . For leakage resilient property, A I can obtain leaked information of both the target user’s ISK ID ∗ = ( ISK ID ∗ , k , 1 , ISK ID ∗ , k , 2 ) used in the Decrypting algorithm’s k-th round of the target user and the KGC’s secret key ( KSK i , 1 , KSK i , 2 ) used in the Identity secret key extract algorithm’s i-th round.

–

Revoked user ( A II ): When A II is a legal user of the LR-RCLE-ORA scheme who has been revoked, it knows the personal secret key PSK ID and the identity secret key ISK ID of any user ID. Also, A II may get the time update key TUK ID , s of any user ID at any period T s , except TUK ID ∗ , s ∗ of the target user ID ∗ at target period T s ∗ . For leakage resilient property, A II can obtain leaked information of the time secret key ( TSK j , 1 , TSK j , 2 ) used in the Time update key extract algorithm’s j-th round.

–

Honest-but-curious KGC ( A III ): Since A III knows the KGC’s secret key KSK and time secret key TSK, it can get the identity secret key ISK ID and time update key TUK ID , s of any user ID at any period T s . Also, A III may get the personal secret key PSK ID of any user ID, except PSK ID ∗ of the target user ID ∗ . For leakage resilient property, A III can obtain leaked information of the target user’s PSK ID ∗ = ( PSK ID ∗ , k , 1 , PSK ID ∗ , k , 2 ) used in the Decrypting algorithm’s k-th round of the target user.

In the continual model of leakage resilient property, the adversary model of LR-RCLE-ORA schemes is defined by the following security game G LR-RCLE-ORA played by both an adversary ( A I , A II or A III ) and a challenger B. Definition 2.

In the continual leakage model, an LR-RCLE-ORA scheme is semantically secure against chosen cipher-text attacks if no adversary ( A I , A II or A III ) with non-negligible advantage wins the security game G LR-RCLE-ORA in polynomial time. This security game G LR-RCLE-ORA consists of three phases: –

Setup phase: By taking as input a security parameter κ and a period number t, a challenger B carries out the System setup algorithm of the LR-RCLE-ORA scheme to generate the KGC’s secret key KSK = ( KSK 0 , 1 , KSK 0 , 2 ), the KGC’s public key KPK, the time secret key TSK = ( TSK 0 , 1 , TSK 0 , 2 ), and the time public key TPK. Also, B sets t periods T 1 , T 2 , … , T t and publishes public system parameters PSP. Additionally, B sends messages to the adversary of various types by the following rules:

•

If the adversary is of A I , B sends out TSK;

•

If the adversary is of A II , B sends out KSK;

•

If the adversary is of A III , B sends out KSK and TSK.

–

Query phase: In the phase, the adversary may request the following queries to B adaptively.

•

Identity secret key query ( ID ): For this query’s i-th round, B sets the new KGC’s secret key ( KSK i , 1 , KSK i , 2 ) by using ( KSK i − 1 , 1 , KSK i − 1 , 2 ). Also, B uses ( KSK i , 1 , KSK i , 2 ) to generate and return the associated identity secret key ISK ID and identity public key IPK ID .

•

Identity secret key leak query ( f ISKE , i , h ISKE , i , i ): In the Identity secret key query’s i-th round, this query is allowed to be requested only once. B returns leaked information ( Λ f ISKE , i , Λ h ISKE , i ).

•

Time update key query ( ID , T s ): In this query’s j-th round, B sets the new time secret key ( TSK j , 1 , TSK j , 2 ) by using ( TSK j − 1 , 1 , TSK j − 1 , 2 ). Also, B uses ( TSK j , 1 , TSK j , 2 ), ID and T s to generate and return the associated time update key TUK ID , s and the time update public key TUPK ID , s .

•

Time update key leak query ( f TUKE , j , h TUKE , j , j ): In the Time update key query’s j-th round, this query is allowed to be requested only once. B returns leaked information ( Λ f TUKE , j , Λ h TUKE , j ).

•

Public key retrieve query ( ID , T s ): B returns the associated public key tuple ( PPK ID , IPK ID , TUPK ID , s ).

•

Public key replace query ( ID , T s , ( PPK ID ′ , IPK ID ′ , TUPK ID , s ′ ) ): B sets the new public key tuple ( PPK ID ′ , IPK ID ′ , TUPK ID , s ′ ) of the user ID at period T s .

•

Personal secret key corrupt query ( ID ): If the Public key replace query ( ID ) has never been requested, B returns the associated personal secret key PSK ID .

•

Decrypting query ( ID , T s , θ = ( C , CT ) ): In this query’s k-th round, B sets the user ID’s new private key tuple ( PSK ID = ( PSK ID , k , 1 , PSK ID , k , 2 ) , ISK ID = ( ISK ID , k , 1 , ISK ID , k , 2 ) , TUK ID , s ) by using ( PSK ID = ( PSK ID , k − 1 , 1 , PSK ID , k − 1 , 2 ) , ISKID = ( ISK ID , k − 1 , 1 , ISK ID , k − 1 , 2 ), TUK ID , s ). Also, B uses the new private key tuple to compute the encryption key EK from C, and decrypt m s g = D EK ( CT ). B returns msg.

•

–

Challenge phase. The adversary sends a target identity ID ∗ , a target period T s ∗ and a plaintext pair ( m s g 0 ∗ , m s g 1 ∗ ) to B. B chooses an unbiased random bit b ∈ { 0 , 1 } and carries out the Encrypting algorithm with ( ID ∗ , T s ∗ , ( PPK ID ∗ , IPK ID ∗ , TUPK ID ∗ , s ∗ ) , m s g b ∗ ) to generate C ∗ , EK ∗ and CT ∗ = E EK ∗ ( m s g b ∗ ). Finally, B returns the ciphertext tuple ( ID ∗ , T s ∗ , θ = ( C ∗ , CT ∗ ) ) to the adversary. Additionally, the associated conditions must be satisfied according to various types of adversaries:

If the adversary is of A I , the Identity secret key query ( ID ∗ ) has never been requested;

If the adversary is of A II , the Time update key query ( ID ∗ , T s ∗ ) has never been requested;

If the adversary is of A III , both the Personal secret key corrupt query ( ID ∗ ) and the Public key replace query ( ID ∗ , T s ∗ , ( PPK ID ∗ ′ , IPK ID ∗ ′ , TUPK ID ∗ , s ∗ ′ ) ) has never been requested.

–

Guess phase. In this phase, the adversary must output a bit b ′ ∈ { 0 , 1 }. If b ′ = b, we say that it wins the game G LR-RCLE-ORA and its advantage is | Pr [ b ′ = b ] − 1 / 2 |.

4 The Proposed LR-RCLE-ORA Scheme

The proposed LR-RCLE-ORA scheme consists of eight algorithms as follows:

–

System setup: By taking as input a security parameter κ and a period number t, the KGC chooses the bilinear group parameters { G 1 , G 2 , p , Q , e ˆ }, picks a symmetric encryption function E ( · ) and its associated decryption function D ( · ), and sets a period set T = { T 0 , T 1 , T 2 , … , T t }. The KGC carries out the following procedures:

(1)

Randomly select an integer α ∈ Z p ∗ , and generate the KGC’s secret key KSK = α · Q and public key KPK = e ˆ ( Q , KSK ). Additionally, the KGC randomly selects an integer x 0 ∈ Z p ∗ and generates the KGC’s current secret key ( KSK 0 , 1 , KSK 0 , 2 ) = ( x 0 · Q , KSK + ( − x 0 ) · Q ).

(2)

Randomly select an integer β ∈ Z p ∗ , and generate the time secret key TSK = β · Q and time public key TPK = e ˆ ( Q , TSK ). Additionally, the KGC securely sends TSK to the ORA. The ORA then selects a random integer y 0 ∈ Z p ∗ and generates the current time secret key ( TSK 0 , 1 , TSK 0 , 2 ) = ( y 0 · Q , TSK + ( − y 0 ) · Q ).

(3)

Randomly select four integers m , n , r , s ∈ Z p ∗ , and compute M = m · Q, N = n · Q, R = r · Q and S = s · Q.

(4)

Publish public system parameters PSP = { G 1 , G 2 , p , Q , e ˆ , KPK , TPK , T , D ( ) , E ( ) , M , N , R , S }.

–

Personal secret key setting: Each user with an identity ID randomly selects an integer γ ∈ Z p ∗ and generates personal secret key PSK ID = γ · Q and the associated personal public key PPK ID = e ˆ ( Q , PSK ID ).

–

Identity secret key extract: In this algorithm’s i-th round, by taking as input a user’s ID and ( KSK i − 1 , 1 , KSK i − 1 , 2 ), the KGC carries out two sub-algorithms ISKExtract-1 ( ID , KSK i − 1 , 1 ) and ISKExtract-2 ( KSK i − 1 , 2 ) as below:

•

ISKExtract-1 ( ID , KSK i − 1 , 1 ):

(1)

Randomly select an integer x i ∈ Z p ∗ , and compute KSK i , 1 = KSK i − 1 , 1 + x i · Q.

(2)

Randomly select an integer u ∈ Z p ∗ , and compute IPK ID = u · Q and temporary value TV ISKE = KSK i , 1 + u · ( M + ID · N ).

•

ISKExtract-2 ( KSK i − 1 , 2 ):

(1)

Compute KSK i , 2 = KSK i − 1 , 2 + ( − x i ) · Q and ISK ID = KSK i , 2 + TV ISKE .

(2)

Send the user’s identity secret key ISK ID and associated identity public key IPK ID to the user using a secure channel.

–

Time update key extract: In this algorithm’s j-th round, by taking as input a user’s ID, a period T s and ( TSK j − 1 , 1 , TSK j − 1 , 2 ), the ORA carries out two sub-algorithms TUKExtract-1 ( ID , T s , TSK j − 1 , 1 ) and TUKExtract-2 ( TSK j − 1 , 2 ) as below:

•

TUKExtract-1 ( ID , T s , TSK j − 1 , 1 ):

(1)

Randomly select an integer y j ∈ Z p ∗ , and compute TSK j , 1 = TSK j − 1 , 1 + y j · Q.

(2)

Randomly select an integer v ∈ Z p ∗ , and compute TUPK ID , s = v · Q and temporary value TV TUKE = TSK j , 1 + v · ( R + ( ID | | T s ) · S ).

•

TUKExtract-2 ( TSK j − 1 , 2 ):

(1)

Compute TSK j , 2 = TSK j − 1 , 2 + ( − y j ) · Q and TUK ID , s = TSK j , 2 + TV TUKE .

(2)

Send the user’s time update key TUK ID , s and associated time update public key TUPK ID , s to the user.

–

Private key setting: At period T s , a user ID’s private key tuple includes three parts, namely, PSK ID , ISK ID , and TUK ID , s . The user carries out the following procedures:

(1)

Randomly select an integer z 0 ∈ Z p ∗ and compute the current personal secret key ( PSK ID , 0 , 1 , PSK ID , 0 , 2 ) = ( z 0 · Q , PSK ID + ( − z 0 ) · Q ).

(2)

Randomly select an integer w 0 ∈ Z p ∗ and compute the current identity secret key ( ISK ID , 0 , 1 , ISK ID , 0 , 2 ) = ( w 0 · Q , ISK ID + ( − w 0 ) · Q ).

(3)

Set the user’s private key tuple ( PSK ID = ( SK ID , 0 , 1 , SK ID , 0 , 2 ) , ISK ID = ( ISK ID , 0 , 1 , ISK ID , 0 , 2 ) , TUK ID , s ).

–

Public key setting: At period T s , a user ID sets her/his public key tuple ( PPK ID , IPK ID , TUPK ID , s ).

–

Encrypting: At period T s , by taking as input a plaintext msg and a receiver ID with public key tuple ( PPK ID , IPK ID , TUPK ID , s ), the sender carries out the following procedures:

(1)

Randomly select an integer e k ∈ Z p ∗ .

(2)

Compute C = e k · Q, K 1 = ( PPK ID ) e k , K 2 = ( KPK · e ˆ ( IPK ID , M + ID · N ) ) e k and K 3 = ( TPK · e ˆ ( TUPK ID , s , R + ( ID | | T s ) · S ) ) e k .

(3)

Set the encryption key EK = K 1 ⊕ K 2 ⊕ K 3 .

(4)

Compute CT = E EK ( m s g ) and return the ciphertext tuple ( ID , T s , θ = ( C , CT ) ).

–

Decrypting: In this algorithm’s k-th round, by taking as input ( ID , T s , θ = ( C , CT ) ), a receiver ID uses her/his private key tuple ( PSK ID = ( PSK ID , k − 1 , 1 , PSK ID , k − 1 , 2 ) , ISK ID = ( ISK ID , k − 1 , 1 , ISK ID , k − 1 , 2 ) , TUK ID , s ) to carry out two sub-algorithms DEC-1 ( PSK ID , k − 1 , 1 , ISK ID , k − 1 , 1 ) and DEC-2 ( PSK ID , k − 1 , 2 , ISK ID , k − 1 , 2 , TUK ID , s , T s , θ = ( C , CT ) ) as below:

•

DEC-1 ( PSK ID , k − 1 , 1 , ISK ID , k − 1 , 1 )

(1)

Randomly select an integer z k ∈ Z p ∗ , and compute PSK ID , k , 1 = PSK ID , k − 1 , 1 + z k · Q.

(2)

Randomly select an integer w k ∈ Z p ∗ , and compute ISK ID , k , 1 = ISK ID , k − 1 , 1 + w k · Q.

(3)

Compute two temporary values TV 1 = e ˆ ( C , PSK ID , k , 1 ) and TV 2 = e ˆ ( C , ISK ID , k , 1 ).

•

DEC-2 ( PSK ID , k − 1 , 2 , ISK ID , k − 1 , 2 , TUK ID , s , T s , θ = ( C , CT ) ) (1)

Compute PSK ID , k , 2 = PSK ID , k − 1 , 2 + ( − z k ) · Q and ISK ID , k , 2 = ISK ID , k − 1 , 2 + ( − w k ) · Q.

(2)

Compute K 1 ′ = TV 1 · e ˆ ( C , PSK ID , k , 2 ), K 2 ′ = TV 2 · e ˆ ( C , ISK ID , k , 2 ) and K 3 ′ = e ˆ ( C , TUK ID , s ).

(3)

Compute the encryption key EK ′ = K 1 ′ ⊕ K 2 ′ ⊕ K 3 ′ .

(4)

Decrypt the plaintext m s g = D EK ′ ( CT ).

In the following, by the key refreshing technique, we have KSK = KSK 0 , 1 + KSK 0 , 2 = KSK 1 , 1 + KSK 1 , 2 = ⋯ = KSK i , 1 + KSK i , 2 ; TSK = TSK 0 , 1 + TSK 0 , 2 = TSK 1 , 1 + TSK 1 , 2 = ⋯ = TSK j , 1 + TSK j , 2 ; PSK ID = PSK ID , 0 , 1 + PSK ID , 0 , 2 = PSK ID , 1 , 1 + PSK ID , 1 , 2 PSK ID = ⋯ = PSK ID , k , 1 + PSK ID , k , 2 ; ISK ID = ISK ID , 0 , 1 + ISK ID , 0 , 2 = ISK ID , 1 , 1 + ISK ID , 1 , 2 ISK ID = ⋯ = ISK ID , k , 1 + ISK ID , k , 2 .

In the following, we show the correctness of EK = K 1 ⊕ K 2 ⊕ K 3 = K 1 ′ ⊕ K 2 ′ ⊕ K 3 ′ = EK ′ . EK = K 1 ⊕ K 2 ⊕ K 3 = ( PPK ID ) e k ⊕ ( KPK · e ˆ ( IPK ID , M + ID · N ) ) e k ⊕ ( TPK · e ˆ ( TUPK ID , s , R + ( ID | | T s ) · S ) ) e k = e ˆ ( Q , PSK ID ) e k ⊕ ( e ˆ ( Q , KSK ) · e ˆ ( u · Q , M + ID · N ) ) e k ⊕ ( e ˆ ( Q , TSK ) · e ˆ ( v · Q , R + ( ID | | T s ) · S ) ) e k = e ˆ ( Q , PSK ID ) e k ⊕ ( e ˆ ( Q , KSK ) · e ˆ ( Q , u · ( M + ID · N ) ) ) e k ⊕ ( e ˆ ( Q , TSK ) · e ˆ ( Q , v · ( R + ( ID | | T s ) · S ) ) ) e k = e ˆ ( Q , PSK ID ) e k ⊕ ( e ˆ ( Q , KSK + u · ( M + ID · N ) ) ) e k ⊕ ( e ˆ ( Q , TSK + v · ( R + ( ID | | T s ) · S ) ) ) e k = e ˆ ( e k · Q , PSK ID ) ⊕ e ˆ ( e k · Q , KSK + u · ( M + ID · N ) ) ⊕ e ˆ ( e k · Q , TSK + v · ( R + ( ID | | T s ) · S ) ) = e ˆ ( C , PSK ID ) ⊕ e ˆ ( C , KSK + u · ( M + ID · N ) ) ⊕ e ˆ ( C , TSK + v · ( R + ( ID | | T s ) · S ) ) = e ˆ ( C , PSK ID ) ⊕ e ˆ ( C , KSK i , 1 + KSK i , 2 + u · ( M + ID · N ) ) ⊕ e ˆ ( C , TSK j , 1 + TSK j , 2 + v · ( R + ( ID | | T s ) · S ) ) = e ˆ ( C , PSK ID ) ⊕ e ˆ ( C , KSK i , 2 + TV ISKE ) ⊕ e ˆ ( C , TSK j , 2 + TV TUKE ) = e ˆ ( C , PSK ID ) ⊕ e ˆ ( C , ISK ID ) ⊕ e ˆ ( C , TUK ID , s ) = e ˆ ( C , PSK ID , k , 1 + PSK ID , k , 2 ) ⊕ e ˆ ( C , ISK ID , k , 1 + ISK ID , k , 2 ) ⊕ e ˆ ( C , TUK ID , s ) = ( e ˆ ( C , PSK ID , k , 1 ) · e ˆ ( C , PSK ID , k , 2 ) ) ⊕ ( e ˆ ( C , ISK ID , k , 1 ) · e ˆ ( C , ISK ID , k , 2 ) ) ⊕ e ˆ ( C , TUK ID , s ) = ( TV 1 · e ˆ ( C , PSK ID , k , 2 ) ) ⊕ ( TV 2 · e ˆ ( C , ISK ID , k , 2 ) ) ⊕ e ˆ ( C , TUK ID , s ) = K 1 ′ ⊕ K 2 ′ ⊕ K 3 ′ = EK ′ .

5 Security Analysis

As the security game G LR-RCLE-ORA presented in Definition 2, the adversary model consists of three types of adversaries, namely, outsider (Type I, A I ), revoked user (Type II, A II ) and honest-but-curious KGC (Type III, A III ). Under the GBG model presented in Section 2, we employ three theorems to demonstrate that the proposed LR-RCLE-ORA scheme is semantically secure against chosen cipher-text attacks against three types of adversaries, respectively. The relationship and robustness of security analysis are depicted in Fig. 3. In Theorem 1, we first discuss the advantage (denoted by Adv A − I − W ) of an outsider ( A I ) without requesting any leak queries and then evaluate the advantage (denoted by Adv A − I ) of an outsider ( A I ) with requesting Identity secret key leak and Decrypting leak queries. Indeed, by Corollary 1, Adv A − I is negligible based on the DL assumption. For Theorems 2 and 3, by similar arguments as in Theorem 1, the advantages (denoted by Adv A − II and Adv A − III ) of a revoked user ( A II ) and an honest-but-curious KGC ( A III ) are also negligible based on the DL assumption.

Fig. 3

The relationship and robustness of security analysis for the proposed scheme.

Theorem 1.

In the GBG model, the proposed LR-RCLE-ORA scheme is semantically secure against chosen cipher-text attacks against an outsider ( A I ) in the security game G LR-RCLE-ORA .

Proof.

Let A I be an outsider of the security game G LR-RCLE-ORA played with a challenger B. In the GBG model, A I may request three queries (oracles) O 1 , O 2 and O p to perform three corresponding group operations. In the security game G LR-RCLE-ORA , four phases are presented as below: –

Setup phase: By taking as input a security parameter κ and a period number t, B carries out the System setup algorithm of the LR-RCLE-ORA scheme to generate the KGC’s secret key KSK = ( KSK 0 , 1 , KSK 0 , 2 ), the KGC’s public key KPK, the time secret key TSK, and the time pubic key TPK. Also, B sets a period set T = { T 0 , T 1 , T 2 , … , T t } and publishes public system parameters PSP = { G 1 , G 2 , p , Q , e ˆ , KPK , TPK , T , D ( ) , E ( ) , M , N , R , S }. Additionally, B sends TSK to A I since A I is an outsider. To respond the queries requested by A I , five initially empty lists L 1 , L 2 , L ISK , L TUK and L PSK are constructed as below: •

L 1 and L 2 are used to encode elements of groups G 1 and G 2 , respectively. (1)

L 1 includes pairs of ( Ξ G 1 , t , u , v , Θ G 1 , t , u , v ). An element in G 1 is represented by a multivariate polynomial Ξ G 1 , t , u , v and Θ G 1 , t , u , v is the corresponding encoded bit-string, where t, u and v, respectively, denote the query type t, the u-th query and the v-th element in G 1 . B initially adds seven pairs ( Ξ Q , Θ G 1 , I , 0 , 1 ), ( Ξ KSK , Θ G 1 , I , 0 , 2 ), ( Ξ TSK , Θ G 1 , I , 0 , 3 ), ( Ξ M , Θ G 1 , I , 0 , 4 ), ( Ξ N , Θ G 1 , I , 0 , 5 ), ( Ξ R , Θ G 1 , I , 0 , 6 ) and ( Ξ S , Θ G 1 , I , 0 , 7 ) in L 1 .

(2)

L 2 includes pairs of ( Ξ G 2 , t , u , v , Θ G 2 , t , u , v ). An element in G 2 is represented by a multivariate polynomial Ξ G 2 , t , u , v and Θ G 2 , t , u , v is the corresponding encoded bit-string, where t, u and v have the same meanings with those indices in L 1 . B initially adds two pairs ( Ξ KPK , Θ G 2 , I , 0 , 1 ) and ( Ξ TPK , Θ G 2 , I , 0 , 2 ) in L 2 , where Ξ KPK = Ξ Q · Ξ KSK and Ξ TPK = Ξ Q · Ξ TSK.

It is worth mentioning the two transforming rules defined below.

(1)

By taking as input a polynomial Ξ G 1 , t , u , v / Ξ G 2 , t , u , v , B looks for ( Ξ G 1 , t , u , v , Θ G 1 , t , u , v ) / ( Ξ G 2 , t , u , v , Θ G 2 , t , u , v ) in L 1 / L 2 . If it is found, B returns the encoded bit-string Θ G 1 , t , u , v / Θ G 2 , t , u , v . Otherwise, B randomly chooses and returns a distinct encoded bit-string Θ G 1 , t , u , v / Θ G 2 , t , u , v . In addition, B adds ( Ξ G 1 , t , u , v , Θ G 1 , t , u , v ) / ( Ξ G 2 , t , u , v , Θ G 2 , t , u , v ) in L 1 / L 2 .

(2)

By taking as input an encoded bit-string Θ G 1 , t , u , v / Θ G 2 , t , u , v , B looks for ( Ξ G 1 , t , u , v , Θ G 1 , t , u , v ) / ( Ξ G 2 , t , u , v , Θ G 2 , t , u , v ) in L 1 / L 2 . If it is found, B returns the associated multivariate polynomial Ξ G 1 , t , u , v / Ξ G 2 , t , u , v . Otherwise, B terminates the game.

•

L ISK includes tuples of ( ID , Ξ ISK ID , Ξ IPK ID ), where Ξ ISK ID and Ξ IPK ID , respectively, represent the user’s ISK ID and IPK ID .

•

L PSK includes tuples of ( ID , Ξ PSK ID , Ξ PPK ID ), where Ξ PSK ID and Ξ PPK ID , respectively, denote the user’s PSK ID and PPK ID .

•

L TUK includes tuples of ( ID , T s , Ξ TUK ID , s , Ξ TUPK ID , s ), where Ξ TUK ID , s and Ξ TUPK ID , s , respectively, denote the user’s TUK ID , s and TUPK ID , s .

Finally, these public system parameters Ξ Q

, Ξ M

, Ξ N

, Ξ R

, Ξ S

, Ξ KPK

and Ξ TPK

are sent to A I

. Also, B sends the time secret key Ξ TSK

to A I

–

Query phase: A I can adaptively request various queries to B at most q times. Note that A I does not need to request the Time update key leak query and Public key replace query, since A I may get the time update key TUK ID , s of any user ID at any period T s from public channels.

•

O 1 query ( Θ G 1 , Q , l , 1 , Θ G 1 , Q , l , 2 , OP ): In this query’s l-th round, B carries out the following steps:

(1)

Get a pair of polynomials ( Ξ G 1 , Q , l , 1 , Ξ G 1 , Q , l , 2 ) by transforming a pair of bit-strings ( Θ G 1 , Q , l , 1 , Θ G 1 , Q , l , 2 ) in L 1 .

(2)

Compute the polynomial Ξ G 1 , Q , l , 3 = Ξ G 1 , Q , l , 1 + Ξ G 1 , Q , l , 2 if OP = “addition”, and Ξ G 1 , Q , l , 3 = Ξ G 1 , Q , l , 1 − Ξ G 1 , Q , l , 2 if OP = “subtraction”.

(3)

Return the encoded bit-string Θ G 1 , Q , l , 3 by transforming Ξ G 1 , Q , l , 3 in L 1 .

•

O 2 query ( Θ G 2 , Q , l , 1 , Θ G 2 , Q , l , 2 , OP ): In this query’s l-th round, B carries out the following steps:

(1)

Get a pair of polynomials ( Ξ G 2 , Q , l , 1 , Ξ G 2 , Q , l , 2 ) by transforming a pair of bit-strings ( Θ G 2 , Q , l , 1 , Θ G 2 , Q , l , 2 ) in L 2 .

(2)

Compute the polynomial Ξ G 2 , Q , l , 3 = Ξ G 2 , Q , l , 1 + Ξ G 2 , Q , l , 2 if OP = “multiplication”, and Ξ G 2 , Q , l , 3 = Ξ G 2 , Q , l , 1 − Ξ G 2 , Q , l , 2 if OP = “division”.

(3)

Return the encoded bit-string Θ G 2 , Q , l , 3 by transforming Ξ G 2 , Q , l , 3 in L 2 .

•

O p query ( Θ G 1 , P , l , 1 , Θ G 1 , P , l , 2 ): In this query’s l-th round, B carries out the following steps:

(1)

Get a pair of polynomials ( Ξ G 1 , P , l , 1 , Ξ G 1 , P , l , 2 ) by transforming a pair of bit-strings ( Θ G 1 , P , l , 1 , Θ G 1 , P , l , 2 ) in L 1 .

(2)

Compute the polynomial Ξ G 2 , P , l , 1 = Ξ G 1 , P , l , 1 · Ξ G 1 , P , l , 2 .

(3)

Return the encoded bit-string Θ G 2 , P , l , 1 by transforming Ξ G 2 , P , l , 1 in L 2 .

•

Identity secret key query ( ID ): In this query’s i-th round, B searches ( ID, Ξ ISK ID , Ξ IPK ID ) in L ISK . If it is found, B transforms ( Ξ ISK ID , Ξ IPK ID ) to send two encoded bit-strings ( Θ ISK ID , Θ IPK ID ) to A I . Otherwise, B carries out the following steps:

(1)

Choose a new variate Ξ TG I S K , i , 1 in G 1 .

(2)

Set two polynomials Ξ IPK ID = Ξ TG ISK , i , 1 and Ξ TID = ID.

(3)

Set the user’s identity secret key Ξ ISK ID = Ξ KSK + Ξ TG ISK , i , 1 · ( Ξ M + Ξ N · Ξ TID ) while adding ( ID , Ξ ISK ID , Ξ IPK ID ) in L ISK .

(4)

Transform ( Ξ ISK ID , Ξ IPK ID ) to send two encoded bit-strings ( Θ ISK ID , Θ IPK ID ) to A I .

•

Time update key query ( ID , T s ): In this query’s j-th round, B searches ( ID, T s , Ξ TUK ID , s , Ξ TUPK ID , s ) in L TUK . If it is found, B transforms ( Ξ TUK ID , s , Ξ TUPK ID , s ) to return two encoded bit-strings ( Θ TUK ID , s , Θ TUPK ID , s ). Otherwise, B carries out the following steps:

(1)

Choose a new variate Ξ TG TUK , ID , j , 1 in G 1 .

(2)

Set a polynomial Ξ TUPK ID , s = Ξ TG TUK , ID , j , 1 and Ξ TTD = ID | | T s .

(3)

Set the user’s time update key Ξ TUK ID , t = Ξ TSK + Ξ TG TUK , ID , j , 1 · ( Ξ R + Ξ S · Ξ TTD ) while adding ( ID , T s , Ξ TUK ID , s , Ξ TUPK ID , s ) in L TUK .

(4)

Transform ( Ξ TUK ID , s , Ξ TUPK ID , s ) to return two encoded bit-strings ( Θ TUK ID , s , Θ TUPK ID , s ).

•

Public key retrieve query ( ID , T s ): B applies ID and T s to search L ISK , L PSK and L TUK to get the associated public key tuple ( Ξ PPK ID , Ξ IPK ID , Ξ TUPK ID , s ). B returns the corresponding tuple ( Θ PPK ID , Θ IPK ID , Θ TUPK ID , s ).

•

Public key replace query ( ID , T s , ( Θ PPK ID ′ , Θ IPK ID ′ , Θ TUPK ID , s ′ ) ): B first transforms a tuple of bit-strings ( Θ PPK ID ′ , Θ IPK ID ′ , Θ TUPK ID , s ′ ) to get the corresponding tuple of polynomials ( Ξ PPK ID ′ , Ξ IPK ID ′ , Ξ TUPK ID , s ′ ). B replaces the related tuples with ( ID , − , Ξ PPK ID ′ ) in L PSK , ( ID , − , IPK ID ′ ) in L ISK , and ( ID , T s , − , Ξ TUPK ID , s ′ ) in L TUK .

•

Personal secret key corrupt query ( ID ): If the Public key replace query ( ID ) has never been requested, B uses ID to search ( ID, Ξ PSK ID , Ξ PPK ID ) in L PSK . If it is found, B transforms ( Ξ PSK ID , Ξ PPK ID ) to return two encoded bit-strings ( Θ PSK ID , Θ PPK ID ). Otherwise, B carries out the following steps:

(1)

Choose a new variate Ξ T G PSK , ID , 1 in G 1 .

(2)

Set two polynomials Ξ PSK ID = Ξ T G PSK , ID , 1 and Ξ PPK ID = Ξ Q · Ξ PSK ID , and add ( ID , Ξ PSK ID , Ξ PPK ID ) in L PSK .

(3)

Transform ( Ξ PSK ID , Ξ PPK ID ) to return two encoded bit-strings ( Θ PSK ID , Θ PPK ID ).

•

Decrypting query ( ID , T s , θ = ( C , CT ) ): In this query’s k-th round, B carries out the following steps:

(1)

By ID and T s , B finds the associated private key tuple ( Ξ PSK ID , Ξ ISK ID , Ξ TUK ID , s ) in L PSK , L ISK and L TUK .

(2)

B transforms the ciphertext C to the polynomial Ξ C in L 1 and sets three polynomials Ξ K 1 = Ξ PSK ID · Ξ C, Ξ K 2 = Ξ ISK ID · Ξ C and Ξ K 3 = Ξ TUK ID , s · Ξ C. Moreover, B transforms Ξ K 1 , Ξ K 2 and Ξ K 3 to obtain bit-strings Θ K 1 , Θ K 2 and Θ K 3 , respectively. Hence, B can gain the encryption key Θ EK = Θ K 1 ⊕ Θ K 2 ⊕ Θ K 3 . Finally, B returns the encryption key Θ EK and the plaintext m s g = D Θ E K ( CT ).

•

Decrypting leak query ( ID , T s , f DEC , k , h DEC , k , k ): In the Decrypting query’s k-th round of the user ID at period T s , this query is allowed to be requested only once. B returns leaked information ( Λ f DEC , k , Λ h DEC , k ), where Λ f DEC , k = f DEC , k ( PSK ID , k , 1 , ISK ID , k , 1 ) and Λ h DEC , k = h DEC , k ( PSK ID , k , 2 , ISK ID , k , 2 , TUK ID , s ).

–

Challenge phase. A I sends a target identity ID ∗ , a target period T s ∗ and a plaintext pair ( m s g 0 ∗ , m s g 1 ∗ ) to B. Here the Identity secret key query ( ID ∗ ) must have never been requested by A I . B chooses an unbiased random bit b ∈ { 0 , 1 } and carries out the E n c r y p t i n g algorithm with ( ID ∗ , T s ∗ , ( PPK ID ∗ , IPK ID ∗ , TUPK ID ∗ , s ∗ ) , m s g b ∗ ) to generate C ∗ , EK ∗ and CT ∗ = E EK ∗ ( m s g b ∗ ). Finally, B returns the ciphertext tuple ( ID ∗ , T s ∗ , θ = ( C ∗ , CT ∗ ) ) to the adversary.

–

Guess phase. In this phase, A I must output a bit b ′ ∈ { 0 , 1 }. If b ′ = b, we say that it wins the game G LR-RCLE-ORA and its advantage is | Pr [ b ′ = b ] − 1 / 2 |.

To evaluate the advantage that A I wins the game G LR-RCLE-ORA , we count the total number of elements in both L 1 and L 2 . Subsequently, we count the maximal degrees of polynomials in L 1 and L 2 , respectively. ■

The total number of elements in both L₁ and L₂: •

7 and 2 elements are increased in L 1 and L 2 , respectively, in the Setup phase.

•

For each O 1 , O 2 or O p query, at most 3 elements are increased in L 1 or L 2 .

•

For each Identity secret key query, at most 3 elements are increased in L 1 .

•

For each Time update key query, at most 3 elements are increased in L 1 .

•

For each Decrypting query, at most 4 elements are increased in L 1 .

Let q O

denote the total number of O 1

, O 2

and O p

queries. Let q I

, q T

and q D

, respectively, be the query numbers of the Identity secret key query, Time update key query and Decrypting query. Since A I

is allowed to request all queries at most q times, we have | L 1 | + | L 2 | ≦ 9 + 3 q O + 3 q I + 3 q T + 4 q D ≦ 4 q .

■

The maximal degrees of polynomials in L₁ and L₂:

(1)

The maximal degree of polynomials in L 1 is 3 due to the following facts:

•

In the Setup phase, 7 new variates (polynomials) Ξ Q, Ξ KSK, Ξ TSK, Ξ M, Ξ N, Ξ R and Ξ S are initially increased in L 1 . All these polynomials have degree 1.

•

For the O 1 query, Ξ G 1 , Q , l , 3 has the maximal degree of Ξ G 1 , Q , l , 1 and Ξ G 1 , Q , l , 2 .

•

For the Identity secret key query, Ξ TG ISK , i , 1 , Ξ TID and Ξ ISK ID have degrees 1, 1 and 3, respectively.

•

For the Time update key query, Ξ TG TUK , ID , j , 1 , Ξ TTD and Ξ TUK ID , t have degrees 1, 1 and 3, respectively.

(2)

The maximal degree of polynomials in L 2 is 6 by the following facts:

•

In the Setup phase, Ξ KPK and Ξ TPK have degree 2.

•

For the O 2 query, Ξ G 2 , Q , l , 3 has the maximal degree of Ξ G 2 , Q , l , 1 and Ξ G 2 , Q , l , 2 .

•

For the O p query, Ξ G 2 , P , l , 1 has degree at most 6 because Ξ G 2 , P , l , 1 = Ξ G 1 , P , l , 1 · Ξ G 1 , P , l , 2 , and both Ξ G 1 , P , l , 1 and Ξ G 1 , P , l , 2 belong to L 1 .

•

For the Decrypting query, all Ξ K 1 , Ξ K 2 and Ξ K 3 have degrees 2.

In the following, let us first evaluate the advantage that A I wins G LR-RCLE-ORA without requesting any leak query. Subsequently, the advantage of A I is evaluated when it is allowed to request two kinds of leak queries (Identity secret key leak query and Decrypting leak query). ■

The advantage of A I without requesting any leak query: If either of the following two cases occurs, A I wins the game. Case 1:

A I discovers a collision of two elements in L 1 or L 2 . Let us first evaluate the collision probability in L 1 . Let n be the number of all variates in L 1 and B selects n random values v l ∈ Z p ∗ for l = 1 , 2 , … , n. Let Ξ G 1 , i and Ξ G 1 , j be any two distinct polynomials in L 1 . B then computes Ξ G 1 , C ( v 1 , v 2 , … , v n ) = Ξ G 1 , i − Ξ G 1 , j . If Ξ G 1 , C ( v 1 , v 2 , … , v n ) = 0, it is said that the collision occurs. By Lemma 2, the probability of Ξ G 1 , C ( v 1 , v 2 , … , v n ) = 0 is at most 3 / p because the maximal polynomial degree in L 1 is 3 and no information ( λ = 0 ) is leaked. Since there are | L 1 | 2 distinct pairs ( Ξ G 1 , i , Ξ G 1 , j ) in L 1 , the collision probability is ( 3 / p ) | L 1 | 2 . Similarly, the collision probability in L 2 is ( 6 / p ) | L 2 | 2 . As mentioned earlier, we have | L 1 | + | L 2 | ≦ 4 q. Let the probability of Case 1 be denoted by Pr[Case 1]. Then we have Pr [ Case 1 ] ≦ ( 3 / p ) | L 1 | 2 + ( 6 / p ) | L 2 | 2 ≦ ( 6 / p ) ( | L 1 | + | L 2 | ) 2 ≦ 96 q 2 / p .

Case 2:

If Case 1 does not occur and A I gets no leaked information, the success probability of b ′ = b is 1 / 2 in the Guess phase. Let Pr[Case 2] denote the success probability that Case 2 occurs. Then we have Pr [ Case 2 ] ≦ 1 / 2.

Let Pr A − I − W

and Adv A − I − W

be the probability and advantage, respectively, that A I

wins the game without requesting any leak query. By Pr[Case 1] and Pr[Case 2], we have Pr A − I − W ≦ Pr [ Case 1 ] + Pr [ Case 2 ] ≦ 96 q 2 / p + ( 1 / 2 ) , Adv A − I − W ≦ | 96 q 2 / p + ( 1 / 2 ) − ( 1 / 2 ) | = 96 q 2 / p = O ( q 2 / p ) .

Hence, Adv A − I − W

is negligible if q = poly ( log p )

■

The advantage of A I with requesting two kinds of leak queries: A I can obtain leaked information of related secret keys by the Identity secret key leak query and Decrypting leak query. ( 1 )

Identity secret key leak query ( f ISKE , i , h ISKE , i , i ): By this query, A I may derive leaked information ( Λ f ISKE , i , Λ h ISKE , i ) such that | f ISKE , i |, | h ISKE , i | ≦ λ, where Λ f ISKE , i = f ISKE , i ( KSK i , 1 ) and Λ h ISKE , i = h ISKE , i ( KSK i , 2 ) that are discussed as below:

•

( KSK i , 1 , KSK i , 2 ): Indeed, the KGC’s secret key KSK has the property in the sense that KSK = KSK 0 , 1 + KSK 0 , 2 = KSK 1 , 1 + KSK 1 , 2 = ⋯ = KSK i , 1 + KSK i , 2 . By the refreshing technique, leaked information of KSK i − 1 , 1 / KSK i − 1 , 2 is independent of that of KSK i , 1 / KSK i , 2 . Thus, A I may derive at most 2 λ bits of KSK.

(2)

Decrypting leak query ( ID , T s , f DEC , k , h DEC , k , k ): As mentioned earlier, A I is not a legal user of the LR-RCLE-ORA scheme, but it may get the time update key TUK ID , s of any user ID at any period T s from public channels. Also, A I may get the personal secret key PSK ID and the identity secret key ISK ID of any user ID, but it is disallowed to get the identity secret key ISK ID ∗ of the target user ID ∗ . Therefore, by this query, A I may derive leaked information ( Λ f DEC , k , Λ h DEC , k ), where Λ f DEC , k = f DEC , k ( ISK ID ∗ , k , 1 ) and Λ h DEC , k = h DEC , k ( ISK ID ∗ , k , 2 ) that are discussed as below:

•

( ISK ID ∗ , k , 1 , ISK ID ∗ , k − 1 , 2 ): Indeed, the identity secret key ISK ID ∗ satisfies ISK ID ∗ = ISK ID ∗ , 0 , 1 + ISK ID ∗ , 0 , 2 = ISK ID ∗ , 1 , 1 + ISK ID ∗ , 1 , 2 = ⋯ = ISK ID ∗ , k , 1 + ISK ID ∗ , k , 2 . Bythe refreshing technique, leaked information of ISK ID ∗ , k − 1 , 1 / ISK ID ∗ , k − 1 , 2 is independent of that of ISK ID ∗ , k , 1 / ISK ID ∗ , k , 2 . Thus, A I may derive at most 2 λ bits of ISK ID ∗ .

Let Pr A − I

and Adv A − I

be the probability and advantage, respectively, that A I

wins G LR-RCLE-ORA

with requesting the Identity secret key leak query and Decrypting leak query. If A I

can obtain the KGC’s secret key KSK

or the target user’s identity key ISK ID ∗

, A I

may decrypt the message. Three events are defined as below:

(1)

Let EKSK denote the event that A I gets the KSK by Λ f ISKE , i and Λ h ISKE , i . Additionally, EKSK ‾ is the complement event of EKSK.

(2)

Let EISK that A I gets the ISK ID ∗ by Λ f DEC , k and Λ h DEC , k . Additionally, EISK ‾ is the complement event of EISK.

(3)

Let ECB denote the event that A I outputs a correct b ′ .

Hence, the advantage Pr A − I

is Pr[ ECB

] and the following inequality holds: Pr A − I = Pr [ ECB ] = Pr [ ECB ∧ ( EKSK ∨ EISK ) ] + Pr [ ECB ∧ ( EKSK ‾ ∧ EISK ‾ ) ] ≦ Pr [ ( EKSK ∨ EISK ) ] + Pr [ ECB ∧ ( EKSK ‾ ∧ EISK ‾ ) ] .

For the event ( EKSK ‾ ∧ EISK ‾ )

, A I

can’t obtain the useful information to output a correct bit b ′

. A I

has probability 1/2 to guess the correct bit, so Pr [ ECB ∧ ( EKSK ‾ ∧ EISK ‾ ) ]

is still 1/2 on average. Thus, we have: Pr A − I ≦ Pr [ ( EKSK ∨ EISK ) ] + 1 / 2 , Adv A − I ≦ | Pr A − I − 1 / 2 | = Pr [ ( EKSK ∨ EISK ) ] .

Because Adv A − I − W ≦ O ( q 2 / p )

and A I

can learn at most 2 λ

bits of KSK

and ISK ID ∗

by the Identity secret key leak query and Decrypting leak query, we have Adv A − I ≦ Adv A − I − W · 2 2 λ ≦ O ( ( q 2 / p ) · 2 2 λ ) .

By Corollary 1, Adv A − I

is negligible if λ < ( 1 − ε ) log p

. □

Theorem 2.

In the GBG model, the proposed LR-RCLE-ORA scheme is semantically secure against chosen cipher-text attacks against a revoked user ( A II ) in the security game G LR-RCLE-ORA .

Proof.

Let A II be a revoked user of the security game G LR-RCLE-ORA played with a challenger B. A II may issue various queries to B at most q times in the game. This game consists of four phases as follows: –

Setup phase: The phase is the same as that in the proof in Theorem 1. Additionally, B sends the time secret key TSK to A II since it is a revoked user.

–

Query phase: In this phase, A II can adaptively issue various queries to B at most q times. A l l queries are identical to those queries in the proof of Theorem 1. Note that A II knows the personal secret key PSK ID and the identity secret key ISK ID of any user ID. Also, A II may get the time update key TUK ID , s of any user ID at any period T s , except TUK ID ∗ , s ∗ of the target user ID ∗ at target period T s ∗ .

–

Challenge phase: A II sends a target identity ID ∗ , a target period T s ∗ and a plaintext pair ( m s g 0 ∗ , m s g 1 ∗ ) to B. Here the Time update key query ( ID ∗ , T s ∗ ) must have never been requested by A II . B chooses a unbiased random bit b ∈ { 0 , 1 } and carries out the Encrypting algorithm with ( ID ∗ , T s ∗ , ( PPK ID ∗ , IPK ID ∗ , TUPK ID ∗ , s ∗ ) , m s g b ∗ ) to generate C ∗ , EK ∗ and CT ∗ = E EK ∗ ( m s g b ∗ ). Finally, B returns the ciphertext tuple ( ID ∗ , T s ∗ , θ = ( C ∗ , CT ∗ ) ) to A II .

–

Guess phase: In this phase, A II must output a bit b ′ ∈ { 0 , 1 }. If b ′ = b, we say that it wins the game G LR-RCLE-ORA and its advantage is | Pr [ b ′ = b ] − 1 / 2 |.

In the following, let us first evaluate the advantage that A II wins G LR-RCLE-ORA without requesting any leak query. Subsequently, the advantage of A II is evaluated when it is allowed to request the Time update key leak query. ■

The advantage of A II without requesting any leak query: Let Adv A − II − W be the advantage that A II wins the game without requesting the Time update key leak query. By the similar evaluations as in the proof of Theorem 1, we have Adv A − II − W = O ( q 2 / p ).

■

The advantage of A II with requesting the Time update key leak query: By the Time update key leak query ( f TUKE , j , h TUKE , j , j), A II may derive leaked information ( Λ f TUKE , j , Λ h TUKE , j ) such that | f TUKE , j |, | h TUKE , j | ≦ λ, where Λ f TUKE , j = f TUKE , j ( TSK j , 1 ) and Λ h TUKE , j = h TUKE , j ( TSK j , 2 ). Indeed, the time secret key TSK has the property in the sense that TSK = TSK 0 , 1 + TSK 0 , 2 = TSK 1 , 1 + TSK 1 , 2 = ⋯ = TSK i , 1 + TSK i , 2 . By the refreshing technique, leaked information of TSK i − 1 , 1 / TSK i − 1 , 2 is independent of that of TSK i , 1 / TSK i , 2 . Thus, A II may derive at most 2 λ bits of TSK.

Let Pr A − II and Adv A − II be the probability and advantage, respectively, that A II wins G LR-RCLE-ORA with requesting the Time update key leak query. Two events are defined as below: (1)

Let ETSK denote the event that A II gets the time secret key TSK by f TUKE , j and h TUKE , j . Additionally, ETSK ‾ is the complement event of ETSK.

(2)

Let ECB denote the event that A II outputs a correct b ′ .

Hence, the advantage Pr A − II

is Pr[ ECB

] and the following inequality holds: Pr A − II = Pr [ ECB ] = Pr [ ECB ∧ ETSK ] + Pr [ ECB ∧ ETSK ‾ ] ≦ Pr [ ETSK ] + Pr [ ECB ∧ ETSK ‾ ] .

For the event ETSK ‾

, A II

can’t obtain the useful information to output a correct bit b ′

. A II

has probability 1 / 2

to guess the correct bit, so Pr [ ECB ∧ ETSK ‾ ]

is still 1 / 2

on average. Thus, we have Pr A − II ≦ Pr [ ETSK ] + 1 / 2 , Adv A − II ≦ | Pr A − II − 1 / 2 | = Pr [ ETSK ] .

Because Adv A − II − W ≦ O ( q 2 / p )

and A II

can learn at most 2 λ

bits of TSK

by the Time update key leak query, we have Adv A − II ≦ Adv A − II − W · 2 2 λ ≦ O ( ( q 2 / p ) · 2 2 λ ) .

By Corollary 1, Adv A − II

is negligible if λ < ( 1 − ε ) log p

. □

Theorem 3.

In the GBG model, the proposed LR-RCLE-ORA scheme is semantically secure against chosen cipher-text attacks against an honest-but-curious KGC ( A III ) in the security game G LR-RCLE-ORA .

Proof.

Let A III be an honest-but-curious KGC of the security game G LR-RCLE-ORA played with a challenger B. A III may issue various queries to B at most q times in the game. This game consists of four phases as follows: –

Setup phase: The phase is the same as that in the proof in Theorem 1. Additionally, B sends the KGC’s secret key KSK and time secret key TSK to A III since it is an honest-but-curious KGC.

–

Query phase: In this phase, A III can adaptively issue various queries to B at most q times. All queries are identical to those queries in the proof of Theorem 1. Note that A III knows the KGC’s secret key KSK and time secret key TSK so that it can get the identity secret key ISK ID and time update key TUK ID , s of any user ID for any period T s . Also, A III may get the personal secret key PSK ID of any user ID, except PSK ID ∗ of the target user ID ∗ .

–

Challenge phase: A III sends a target identity ID ∗ , a target period T s ∗ and a plaintext pair ( m s g 0 ∗ , m s g 1 ∗ ) to B. Here both the Personal secret key corrupt query ( ID ∗ ) and the Public key replace query ( ID ∗ , T s ∗ , ( PPK ID ∗ ′ , IPK ID ∗ ′ , TUPK ID ∗ , s ∗ ′ ) ) must have never been requested by A III . B chooses an unbiased random bit b ∈ { 0 , 1 } and carries out the Encrypting algorithm with ( ID ∗ , T s ∗ , ( PPK ID ∗ , IPK ID ∗ , TUPK ID ∗ , s ∗ ) , m s g b ∗ ) to generate C ∗ , EK ∗ and CT ∗ = E EK ∗ ( m s g b ∗ ). Finally, B returns the ciphertext tuple ( ID ∗ , T s ∗ , θ = ( C ∗ , CT ∗ ) ) to A III .

–

Guess phase: In this phase, A III must output a bit b ′ ∈ { 0 , 1 }. If b ′ = b, we say that it wins the game G LR-RCLE-ORA and its advantage is | Pr [ b ′ = b ] − 1 / 2 |.

In the following, let us first evaluate the advantage that A III

wins G LR-RCLE-ORA

without requesting any leak query. Subsequently, the advantage of A III

is evaluated when it is allowed to request the Decrypting leak query ( ID , T s , f DEC , k , h DEC , k , k )

■

The advantage of A III without requesting any leak query: Let Adv A − III − W be the advantage that A III wins the game without requesting the Decrypting leak query. By the similar evaluations as in the proof of Theorem 1, we have Adv A − III − W = O ( q 2 / p ).

■

The advantage of A III with requesting the Decrypting leak query: By the Decrypting leak query ( ID , T s , f DEC , k , h DEC , k , k ), A III may derive leaked information ( Λ f DEC , k , Λ h DEC , k ) such that | f DEC , k | , | h DEC , k | ≦ λ, where Λ f DEC , k = f DEC , k ( PSK ID , k , 1 ) and Λ h DEC , k = h DEC , k ( PSK ID , k , 2 ). Note that A III may get the personal secret key PSK ID of any user ID, except PSK ID ∗ of the target user ID ∗ . For leakage resilient property, A III can obtain leaked information of the target user’s PSK ID ∗ = ( PSK ID ∗ , k , 1 , PSK ID ∗ , k , 2 ) used in the Decrypting algorithm’s k-th round of the target user. Indeed, the personal secret key PSK ID has the property in the sense that PSK ID ∗ = PSK ID ∗ , 0 , 1 + PSK ID ∗ , 0 , 2 = PSK ID ∗ , 1 , 1 + PSK ID ∗ , 1 , 2 = ⋯ = PSK ID ∗ , k , 1 + PSK ID ∗ , k , 2 . By the refreshing technique, leaked information of PSK ID ∗ , k − 1 , 1 / PSK ID ∗ , k − 1 , 2 is independent of that of PSK ID ∗ , k , 1 / PSK ID ∗ , k , 2 . Thus, A III may derive at most 2 λ bits of PSK ID ∗ .

Let Pr A − III and Adv A − III be the probability and advantage, respectively, that A III wins G LR-RCLE-ORA with requesting the Decrypting leak query. Two events are defined as below: (1)

Let EPSK denote the event that A III gets the personal secret key PSK ID ∗ by f DEC , k and h DEC , k . Additionally, EPSK ‾ is the complement event of EPSK.

(2)

Let ECB denote the event that A III outputs a correct b ′ .

Hence, the advantage Pr A − III

is Pr[ ECB

] and the following inequality holds. Pr A − III = Pr [ ECB ] = Pr [ ECB ∧ EPSK ] + Pr [ ECB ∧ EPSK ‾ ] ≦ Pr [ EPSK ] + Pr [ ECB ∧ EPSK ‾ ] .

For the event EPSK ‾

, A III

can’t obtain the useful information to output a correct bit b ′

. A III

has probability 1/2 to guess the correct bit, so Pr [ ECB ∧ EPSK ‾ ]

is still 1/2 on average. Thus, we have Pr A − III ≦ Pr [ EPSK ] + 1 / 2 , Adv A − III ≦ | Pr A − III − 1 / 2 | = Pr [ EPSK ] .

Because Adv A − III − W ≦ O ( q 2 / p )

and A III

can learn at most 2 λ

bits of PSK

by the Decrypting leak query, we have Adv A − III ≦ Adv A − III − W · 2 2 λ ≦ O ( ( q 2 / p ) · 2 2 λ ) .

By Corollary 1, Adv A − III

is negligible if λ < ( 1 − ε ) log p

. □

6 Comparisons

Here, let’s first present the computation notations of several operations in bilinear groups. By employing the simulation experiences in Li et al. (2021), Table 1 lists two kinds of time-consuming operations and their computational time (in milliseconds). The environment of simulation experiences is a platform with the Intel Core i7-8550U CPU 1.80 GHz processor. The selection of security parameters are F p , G 1 and G 2 . Here, F p is a finite field which consists of the set of integers { 0 , 1 , … , p − 1 }, where p is a 256-bit prime number. And, G 1 and G 2 are groups with 224-bit prime order over the finite field F p . It is worth mentioning that the computation of a one-way hash function, an addition on an additive group G 1 and a multiplication on a multiplicative group G 2 are omitted because their computational costs are small and negligible.

Table 1

Computational time (in millisecond) of two time-consuming operations.

Notation	Operation	Computational time
T p	a bilinear pairing e ˆ : G 1 × G 1 → G 2	7.84 ms
	a scalar multiplication on an additive group G 1
T m e	or	0.48 ms
	an exponentiation on a multiplicative group G 2

Table 2 lists the comparisons of our LR-RCLE-ORA scheme with several RCLE and LR-CLE schemes (Tsai and Tseng, 2015; Xiong et al., 2013; Wu et al., 2018) in terms of encryption cost (time), decryption cost (time), security proof model, revocation property, outsourced revocation, resisting side-channel attacks and leakage resilience model. Note that a user’s private key in Xiong et al.’s LR-CLE scheme (2013) is a vector with n ≧ 2 elements (here, let n = 2). As compared to the bounded leakage property of Xiong et al.’s LR-CLE scheme (2013), Wu et al.’s scheme and ours possess continual leakage property and are practical for applications. To resist side-channel attacks, our scheme requires some extra computation costs than the RCLE scheme in Tsai and Tseng (2015). As compared with the LR-CLE scheme (Wu et al., 2018), our scheme requires one T p for encryption cost and decryption cost, respectively, but our scheme offers outsourced revocation functionality to reduce the computational burden of the KGC for generating all non-revoked users’ time update keys. By Table 2, even though the computational cost of our scheme is worse than the other schemes, our scheme possesses four complete properties, namely, revocation property, outsourced revocation, resisting side-channel attacks and continual leakage property. We emphasize that our scheme is the first LR-RCLE-ORA scheme resisting side-channel attacks while possessing continual leakage property.

Table 2

Comparisons between our scheme and the previously proposed schemes.

	Tsai and Tseng’s RCLE scheme (Tsai and Tseng, 2015)	Xiong et al.’s LR-CLE scheme (Xiong et al., 2013)	Wu et al.’s LR-CLE scheme (Wu et al., 2018)	Our LR-RCLE-ORA scheme
Encryption cost	3 T m e + T p	6 T m e	4 T m e + T p	4 T m e + 2 T p
	(9.28 ms)	(2.88 ms)	(9.76 ms)	(17.6 ms)
Decryption cost	2 T m e + T p	4 T p	4 T m e + 4 T p	4 T m e + 5 T p
	(8.8 ms)	(31.36 ms)	(33.28 ms)	(41.12 ms)
Security proof model	Random oracle model	Standard model (Dual system)	GBG model	GBG model
Revocation property	Yes	No	No	Yes
Outsourced revocation	No	No	No	Yes
Resisting side-channel attacks	No	Yes	Yes	Yes
Leakage resilience model	No	Bounded	Continual	Continual

7 Conclusions

In this paper, the first leakage-resilient revocable certificateless encryption scheme with an outsourced revocation authority (LR-RCLE-ORA) was proposed. As compared to previous RCLE and LR-CLE schemes, our scheme possesses several merits. (1) It can resist side-channel attacks and has leakage resilience properties. (2) The revocation functionality is outsourced to the ORA to alleviate the computational load of the KGC. (3) It permits adversaries to continually extract partial ingredients of secret keys and offers the overall unbounded leakage property. By extending the adversary models of RCLE and LR-CLE schemes, a new adversary model was defined while three kinds of leak queries are added, namely, Identity secret key leak query, Time update key leak query and decrypting leak query. In the GBG model, the security of the proposed scheme is shown to be semantically secure against chosen cipher-text attacks for three kinds of adversaries, namely, outsider, revoked user and honest-but-curious KGC.

References

Abdalla, M., Belaid, S., Fouque, P. (2013). Leakage-resilient symmetric encryption via re-keying. In: CHES’13, LNCS, Vol. 8086, pp. 471–488.

Akavia, 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.

Boneh, D., Franklin, M. (2001). Identity-based encryption from the Weil pairing. In: CRYPTO’01, LNCS, Vol. 2139, pp. 213–229.

Boneh, D., Boyen, X., Goh, E.J. (2005). Hierarchical identity-based encryption with constant size ciphertext. In: EUROCRYPT, 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.

Bronchain, O., Momin, C., Peters, T., Standaert, F. (2021). Improved leakage-resistant authenticated encryption based on hardware AES coprocessors. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021(3), 641–676.

Brumley, D., Boneh, D. (2005). Remote timing attacks are practical. Computer Networks, 48(5), 701–716.

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.

Du, H., Wen, Q., Zhang, S. (2018). A provably-secure outsourced revocable certificateless signature scheme without bilinear pairings. IEEE Access, 6, 73846–73855.

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.

Hazay, C., López-Alt, A., Wee, H., Wichs, D. (2013). Leakage-resilient cryptography from minimal assumptions. In: EUROCRYPT’13, LNCS, Vol. 7881, pp. 160–176.

Housley, R., Polk, W., Ford, W., Solo, D. (2002). Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile. IETF, RFC 3280.

Hsieh, T.-C., Tseng, Y.-M., Huang, S.-S. (2020). A leakage-resilient certificateless authenticated key exchange protocol withstanding side-channel attacks. IEEE Access, 8, 121795–121810.

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.

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.

Li, Y., Cheng, Q., Liu, X., Li, X. (2021). A secure anonymous identity-based scheme in new authentication architecture for mobile edge computing. IEEE Systems Journal, 15(1), 935–946.

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.

Li, S., Zhang, F., Sun, Y., Shen, L. (2013). Efficient leakage-resilient public key encryption from DDH assumption. Cluster Computing, 16(4), 797–806.

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.

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.

Scott, M. (2011). On the efficient implementation of pairing-based protocols. In: Cryptography and Coding, LNCS, Vol. 7089, pp. 296–308.

Shen, L., Zhang, F., Sun, Y. (2014). Efficient revocable certificateless encryption secure in the standard model. Computer Journal, 57(4), 592–601.

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.

Tsai, T.-T., Chuang, Y.-H., Tseng, Y.-M., Huang, S.-S., Hung, Y.-H. (2021). A leakage-resilient ID-based authenticated key exchange protocol with a revocation mechanism. IEEE Access, 9, 128633–128647.

Tseng, Y.-M., Tsai, T.-T. (2012). Efficient revocable ID-based encryption with a public channel. Computer Journal, 55(4), 475–486.

Tseng, Y.-M., Wu, J.-D., Huang, S.-S., Tsai, T.-T. (2020). Leakage-resilient outsourced revocable certificateless signature with a cloud revocation server. Information Technology and Control, 49(4), 464–481.

Unterstein, F., Schink, M., Schamberger, T., Tebelmann, L., Ilg, M., Heyszl, J. (2020). Retrofitting leakage resilient authenticated encryption to microcontrollers. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020(4), 365–388.

Wu, J.-D., Tseng, Y.-M., Huang, S.-S., Chou, W.-C. (2018). Leakage-resilient certificateless key encapsulation scheme. Informatica, 29(1), 125–155.

Wu, J.-D., Tseng, Y.-M., Huang, S.-S. (2019). An identity-based authenticated key exchange protocol resilient to continuous key leakage. IEEE Systems Journal, 13(4), 3968–3979.

Wu, J.-D., Tseng, Y.-M., Huang, S.-S., Tsai, T.-T. (2020). Leakage-resilient revocable identity-based signature with cloud revocation authority. Informatica, 31(3), 597–620.

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.

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.