# Certificateless Key-Insulated Generalized Signcryption Scheme without Bilinear Pairings

Authors: Caixue Zhou; Zhiqiang Zhao; Wan Zhou; Yuan Mei
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Generalized signcryption (GSC) can be applied as an encryption scheme, a signature scheme, or a signcryption scheme with only one algorithm and one key pair. A key-insulated mechanism can resolve the private key exposure problem. To ensure the security of cloud storage, we introduce the key-insulated mechanism into GSC and propose a concrete scheme without bilinear pairings in the certificateless cryptosystem setting. We provide a formal definition and a security model of certificateless key-insulated GSC. Then, we prove that our scheme is confidential under the computational Diffie-Hellman (CDH) assumption and unforgeable under the elliptic curve discrete logarithm (EC-DL) assumption. Our scheme also supports both random-access key update and secure key update. Finally, we evaluate the efficiency of our scheme and demonstrate that it is highly efficient. Thus, our scheme is more suitable for users who communicate with the cloud using mobile devices.


---

## Body

## 1. Introduction

With the rapid development of cloud storage technology, its security has become increasingly important. For cloud storage, confidentiality and authentication are the two main aspects of security that must be addressed. In general, confidentiality can be realized by encryption and authentication via signature. When both methods are needed simultaneously, the sign-then-encrypt approach is traditionally utilized. However, in this traditional method, the computational costs and communication overhead are the sum of those of signature and encryption, being very high. Signcryption [1] can realize both confidentiality and authentication simultaneously in a single logic step, and the cost is much lower than that of the traditional approach.Zheng’s original signcryption scheme [1] is based on the public key infrastructure (PKI), whose drawback is the high management cost of the public key certificate. An identity-based cryptosystem [2] can greatly reduce the cost of public key management, but it suffers from the private key escrow problem (i.e., the trusted third-party private key generator [PKG] knows all users’ private keys).In 2003, Al-Riyami and Paterson [3] proposed the certificateless cryptosystem, for which a user’s private key is composed of two parts: the partial-private key produced by the trusted third-party key generation center (KGC) and a secret value chosen by the user. Accordingly, a user’s public key is also composed of two parts: the user’s identity information and the public key corresponding to the secret value. Because the public key does not require a certificate, the cost of public key management is greatly reduced. Meanwhile, the KGC does not know the user’s secret value, and thus, there is no private key escrow problem. Certificateless cryptosystems have attracted widespread attention since their introduction.Returning to cloud storage, we sometimes need confidentiality and authentication separately, whereas, at other times, both are needed simultaneously. For example, an announcement needs only authentication, private information requires only confidentiality, and information sent to others needs both. To meet this requirement, we can use three algorithms (i.e., encryption, signature, and signcryption). However, three algorithms require three pairs of keys, and hence, the key management cost is high. To reduce the complexity of key management and increase the flexibility of implementation, Han et al. [4] proposed the concept of generalized signcryption (GSC) in 2006, which is the natural extension of signcryption. GSC can realize encryption, signature, and signcryption with only one algorithm and one key pair. Because it can adaptively switch between encryption mode, signature mode, and signcryption mode, GSC can realize confidentiality and authentication separately/simultaneously in an efficient manner. Therefore, we can use GSC to achieve confidentiality and authentication separately/simultaneously in a cloud storage scenario.In Han et al.’s original GSC scheme [4], however, the private key exposure problem was not considered. With the widespread use of mobile devices, key exposure has become a serious and realistic threat. If an attacker can obtain a victim’s private key, he/she does not need to solve the hard problems on which the cryptosystem is based. To minimize the damage caused by private key exposure, forward-secure [5], key-insulated [6], and intrusion-resilient [7] technologies have been introduced. In forward-secure technology, the lifetime of a system is divided into separate time periods. At the beginning of each time period, a user’s private key must be updated, whileas the public key remains unchanged throughout the lifetime. Thus, the private key exposure of a given time period affects only the security of the current and later time periods, while the previous time periods are protected. Thus, the attacker cannot decrypt the encryption and signcryption ciphertexts in the previous time periods and also cannot forge the signature and signcryption ciphertexts in the previous time periods. As forward-secure technology does not provide backward security, key-insulated technology has been introduced. In this technology, a physically secure but computationally limited device (the helper) is introduced and stores a helper private key. The lifetime of a system is divided into separate time periods, as in forward-security technology. When a user’s private key is updated at the beginning of a time period, the helper is needed to produce an update key. The user updates his/her private key by combining the update key and his/her old time period private key. The public key remains unchanged throughout the lifetime, as in the forward-secure technology. The signature, signcryption, decryption, and un-signcryption computations need only the user’s current time period private key, and the helper is not involved. Thus, a user’s private key being compromised in some given time periods does not affect the security of other time periods. Therefore, both forward and backward security are achieved. In addition, if the helper’s private key is exposed, as long as the user’s period private key in each time period is not exposed, security will be guaranteed. However, if the helper’s private key is exposed at the same time that the user’s private key in any time period is exposed, both forward and backward security will be breached. In intrusion-resilient technology, at the beginning of each time period, both the user’s private key and the helper’s private key must be updated. Thus, it retains the advantage of a key-insulated system while gaining the following advantages. If the helper’s private key is exposed in a given time period, both forward and backward security will still hold as long as the user’s private key is not exposed within the same time period. If the helper’s private key and the user’s private key are exposed in the same time period, forward security will be maintained. Obviously, key-insulated technology is more secure than forward-security technology, and intrusion-resilient technology is more secure than key-insulated technology. Due to the complexity and low efficiency of the current intrusion-resilient technology, here, we consider only key-insulated technology.In this paper, we introduce key-insulated technology into GSC for the first time and propose a certificateless key-insulated GSC scheme to meet the security requirements of cloud storage. Our scheme has the following advantages. First, we use only one algorithm and one key pair to realize the key-insulated encryption, key-insulated signature, and key-insulated signcryption functions. The algorithm can switch between the encryption, signature, and signcryption modes adaptively. Therefore, it can realize confidentiality and authentication separately or simultaneously, and the total number of keys in the system is greatly reduced. Second, the user’s private keys may be exposed during some time periods, whereas they are not affected in other time periods. Third, our scheme possesses the advantages of a certificateless cryptosystem: low public key management costs and no private key escrow problem. Fourth, our scheme does not rely on costly bilinear pairings. Bilinear pairing is a useful tool in the design of cryptography schemes, but the computational cost of a pairing can be almost 20 times that of elliptic curve point multiplication [8]. Therefore, the computational efficiency of our scheme is high. Fifth, our scheme supports unbounded time periods. In comparison, in the first key-insulated scheme [6], the total number of time periods must be given in advance. Sixth, our scheme supports random-access key update; that is, for any current time period i and any desired time period j, the private key can be updated from ski to skj in one step. Seventh, our scheme supports secure key update. We considered the possibility that an adversary may break into the user’s storage while a key update is occurring. In this scenario, a key update exposure from time period i to j is equivalent to key exposures in time periods i and j. Other time periods remain secure.We give a formal definition and the security concept of certificateless key-insulated GSC. Based on the CDH hard problem, we prove that our scheme is confidential in both encryption and signcryption modes. Based on the EC-DL hard problem, we prove that our scheme is unforgeable in both signature and signcryption modes. Finally, we evaluate the efficiency of our scheme and demonstrate that it is highly efficient.The remainder of this paper is organized as follows. In Section2, various related works are described. Section 3 addresses various hard problems. In Section 4, the formal definition and security model are introduced. Section 5 presents the concrete certificateless key-insulated GSC scheme without bilinear pairings. In Section 6, we analyze the security of our scheme. In Section 7, we evaluate the efficiency of our scheme. We conclude the paper in Section 8.


## 2. Related Work

Han et al. [4] first introduced the notion of GSC in 2006. Subsequently, Han and Gui [9] described a multireceiver GSC scheme and applied it to wireless multicast communication in 2009. Wang et al. [10] gave a formal definition and security model of GSC in the PKI setting for the first time and improved the scheme [4] in 2010. Later, Yu et al. [11] proposed an identity-based GSC scheme and a security model in the same year. Kushwah and Lal [12] simplified the security model of scheme [11] and proposed a more efficient identity-based GSC scheme in 2011. Zhou et al. [13] proposed a certificateless GSC scheme that can resist a malicious-but-passive KGC attack [14] in 2014. Wei et al. [15] proposed an identity-based GSC scheme in the standard model and applied it to big data security in 2015. Zhou [16] described an attack on scheme [9] and improved it in the same year. Subsequently, Han and Lu [17] proposed an attribute-based GSC scheme in the standard model and applied it to online social networks. Zhou et al. [18, 19] extended GSC, introduced two new concepts (generalized proxy signcryption and generalized ring signcryption), and proposed a concrete scheme in 2016. Zhang et al. [20] proposed a lightweight certificateless GSC scheme and applied it to a mobile health system in 2017.Key-insulated encryption was first introduced by Dodis et al. [6] in 2002. Dodis et al. [21] extended the key-insulated encryption to a key-insulated signature and proposed a concrete scheme in 2003. However, in the two schemes, the total number of time periods must be given in advance. Hanaoka et al. [22] introduced key-insulated encryption into the identity-based setting and proposed an identity-based hierarchical key-insulated encryption scheme in 2005. Zhou et al. [23] proposed the first identity-based key-insulated signature in 2006. Weng et al. [24] developed an identity-based key-insulated signature in the standard model in the same year. Subsequently, Hanaoka et al. [25] introduced parallel key-insulated encryption and proposed some concrete schemes. Later, Bellare and Palacio [26] proposed a key-insulated encryption scheme in which the total number of time periods does not need to be determined in advance in the PKI setting. Li et al. [27] introduced the key-insulated mechanism into the group signature and proposed a concrete scheme in 2007. Liu and Wong [28] introduced the key-insulated mechanism into the ring signature and proposed a concrete scheme in 2008. Wan et al. [29] proposed the first certificateless key-insulated signature in 2009; their scheme was designed in the standard model. In the same year, Liu and Cao [30] noted that scheme [24] is insecure. Later, Wan et al. [31] introduced a key-insulated mechanism into the proxy signature and proposed a concrete scheme. Du et al. [32] proposed the first certificate-based key-insulated signature in 2012. Chen et al. [33] proposed the first key-insulated signcryption in the same year and proved their scheme in the standard model. Fan et al. [34] proposed a PKI-based key-insulated signcryption scheme, and Wang et al. [35] suggested an identity-based key-insulated signcryption scheme in 2013. Zhao et al. [36] introduced the key-insulated mechanism into the aggregate signature and proposed a concrete scheme in 2014. Chen et al. [37] proposed the first attribute-based key-insulated signature and applied it to anonymous authentication for a bidirectional broadcasting service in the same year. Subsequently, Zhu et al. [38] determined that scheme [33] is insecure and reported an improvement. Li et al. [39] proposed a certificate-based key-insulated signature scheme in the same year. Xiong et al. [40] proposed a pairing-free certificate-based key-insulated signature scheme for low-power devices, and Lu et al. [41] proposed a certificateless strong key-insulated signature in the standard model in 2015. Li et al. [42] proposed a certificate-based key-insulated signature in the standard model in 2016. Hong and Sun [43] proposed an attribute-based key-insulated signcryption without bilinear pairings and applied it to mobile networks during the same year.


## 3. Preliminaries

(1)
Elliptic curve discrete logarithm (EC-DL) problem: letE be an elliptic curve over the finite field Fp, where p is a prime number, and let G1 be an additive group of prime order q on E(Fp). Given (P,aP)∈G12 for unknown randomly chosen a∈Zq, one must compute a.
(2)
Computational Diffie-Hellman (CDH) problem: given(P,aP,bP)∈G13 for unknown randomly chosen a,b∈Zq, one must compute abP.


## 4. Formal Definition and Security Model of Certificateless Key-Insulated GSC

### 4.1. Formal Definition

A certificateless key-insulated GSC scheme consists of the following eight algorithms.(
1) Setup. Given a security parameter 1k, it produces a master private key s and a global public parameter Params. It is usually run by the KGC.(
2) Partial-Private-Key-Gen. Given a user’s identity ID, the Params, and the master private key s, it produces a partial private key DID for the user. It is also usually run by the KGC, and the KGC sends DID to the user securely.(
3) User-Key-Gen. Given a user’s identity ID and the Params, it produces a secret value xID and the corresponding public key PKID for the user. It is usually run by the user.(
4) Set-Initial-Key. Given a user’s identity ID, the Params, his/her partial private key DID, and his/her secret value xID, it produces a helper private key hkID for the helper and a period private key SID,0 in time period 0 for the user. It is usually run by the user. Then, the user sends the helper private key hkID to the helper and deletes it from the user.(
5) Key-Update-H. Given a user’s identity ID, the Params, the helper private key hkID, the old time period t, and the new time period t′, it produces an update key UKID,t,t′. It is usually run in the helper device.(
6) Key-Update-U. Given a user’s identity ID, the Params, the update key UKID,t,t′, and a user’s period private key SID,t, it produces the user’s period private key SID,t′. It is usually run by the user.(
7) GSC. Given a sender’s identity IDs, a receiver’s identity IDr, the Params, a message m, a time period t, and the sender’s period private key SIDs,t, it produces a GSC ciphertext σ. It is usually run by the sender IDs or anyone in encryption mode.This algorithm can be run in three modes.(a)
Encryption mode: if IDs is null and IDr is not, then the GSC ciphertext σ is an encryption ciphertext.(b)
Signature mode: if IDr is null and IDs is not, then the GSC ciphertext σ is a signature.(c)
Signcryption mode: if neither IDs nor IDr is null, then the GSC ciphertext σ is a signcryption ciphertext.(
8) Un-GSC. Given a sender’s identity IDs, a receiver’s identity IDr, the Params, a GSC ciphertext σ, a time period t, and the receiver’s period private key SIDr,t, it recovers the message m in encryption or signcryption mode or returns true in signature mode; otherwise, it returns ⊥, indicating decryption failure or an invalid signature. It is usually run by the receiver IDr or anyone in signature mode.This algorithm can also be run in three modes.(a)
Decryption mode: if IDs is null and IDr is not, it runs in this mode.(b)
Signature verification mode: if IDr is null and IDs is not, it runs in this mode. Any person can verify the signature σ.(c)
Un-signcryption mode: if neither IDs nor IDr is null, it runs in this mode.Note. The scheme can switch between different modes automatically. If the input of the sender’s identity IDs is null and the receiver’s identity IDr is not, it automatically runs in encryption mode. If the input of IDs is not null and IDr is, it automatically runs in signature mode. If the input of neither IDs nor IDr is null, it automatically runs in signcryption mode. Both IDs and IDr being null is disallowed.


### 4.2. Security Model

There are two types of attackers in the certificateless cryptosystem [3]. A type I attacker AI does not know the system master private key, but he/she can replace the public key of any user. This considers an attack by any user other than the KGC. A type II attacker AII knows the system master private key, but he/she cannot replace anyone’s public key. This considers the attack launched by the KGC, but the KGC is honest-but-curious. Thus, the KGC generates the system parameters honestly according to the Setup algorithm. Then, he/she attempts to attack the system. In 2007, Au et al. [14] introduced a new type of KGC attack: the malicious-but-passive KGC attack. This type of KGC attack assumes that the KGC may imbed some trapdoors in the system parameters when he/she runs the Setup stage. We consider this type of KGC attack in our security model.In terms of key-insulated security, there are three types of key exposures [6]: (1) ordinary key exposure, which involves the user-period-private key being compromised; (2) key-update exposure, which involves the user’s device being compromised during the key-updating step; and (3) helper-key exposure, which involves the physically secure device being compromised. Security against the first type of exposure is called basic key-insulated security, security against the second type of exposure is called secure key update, and security against the last type of exposure is called strong key-insulated security. Compromising both the user-period-private key and helper key is not allowed because, in this case, the adversary can compute the user-period-private key in any time period.The security of GSC includes confidentiality and unforgeability. Specifically, the scheme must possess indistinguishability under an adaptively chosen ciphertext attack in encryption and signcryption modes and unforgeability under an adaptively chosen message attack in signature and signcryption modes.By referring to the security models of schemes [6, 13, 33, 34, 39, 41], we have the following nine definitions. The first four definitions focus on the first type of exposure, Definitions 5–8 focus on the last type of exposure, and Definition 9 focuses on the second type of exposure.There are nine oracles that can be accessed by adversaryA as follows.(a) User-Creation Query. Adversary A provides an identity ID. If it has been created, B returns the public key PKID to A. Otherwise, B runs the partial-key-gen and user-key-gen algorithms to produce the partial private key DID and the user’s secret-value/public key pair (xID,PKID). B runs the set-initial-key algorithm to produce the helper private key hkID. Then, B returns the public key PKID to A.(b) Partial-Private-Key Query.
A provides a created identity ID, and B returns the partial private key DID to A.(c) Secret-Value Query.
A provides a created identity ID, and B returns the secret value xID to A.(d) Public-Key Query.
A provides a created identity ID, and B returns the public key PKID to A.(e) Public-Key-Replacement Query.
A provides a created identity ID and a new public/secret-value pair (PKID′,xID′), and B replaces the old public/secret-value pair (PKID,xID) with the new one (PKID′,xID′).(f) User-Period-Private-Key Query.
A provides a created identity ID and a time period t, and B returns the user’s period private key SID,t to A (first running the key-update-h and key-update-u algorithms, if necessary).(g) Helper-Key Query.
A provides a created identity ID. B returns the user’s helper key hkID to A.(h) GSC Query.
A provides two created identities IDs,IDr (one of them may be null), a message m, and a time period t. B runs the GSC algorithm and returns its output σ to A.(i) Un-GSC Query.
A provides two created identities IDs,IDr (one of them may be null), a ciphertext σ, and a time period t. B runs the Un-GSC algorithm and returns its results to A.


#### 4.2.1. Basic Key-Insulated Security

Definition 1 (type I confidentiality, encryption, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be indistinguishability-certificateless-basic key-insulated-GSC-adaptive chosen ciphertext attack-type I (IND-CL-Basic-KI-GSC-CCA2-I) secure if no probabilistic polynomial time (PPT) adversaryAI has a nonnegligible advantage in the following game.
(
1) Setup. Given a security parameter 1k, challenger B runs the setup algorithm to produce the system public parameter Params and a master private key s. He/she returns Params to adversary AI and keeps s secret.
(
2) Find Stage.
A
I can adaptively ask all the above oracles, except the helper-key oracle.
(
3) Challenge Stage.
A
I provides two distinct messages {m0,m1} with equal length, a created sender’s identity IDs∗ (IDs∗ may be null), a created receiver’s identity IDr∗, and a time period t∗. B randomly chooses b∈{0,1} and computes σ∗=GSC(mb,Params,SIDs∗,t∗,PKIDr∗). Then, B returns σ∗ to AI.
(
4) Guess Stage.
A
I can ask the same queries as in the Find stage adaptively. Finally, AI gives his/her guess b′. If b′=b, he/she wins the game. The restrictions on AI are as follows:(a)
The receiver’s identityIDr∗ cannot be null.(b)
AI cannot ask for IDr∗’s period private key SIDr∗,t∗ in time period t∗.(c)
AI cannot ask for the partial private key DIDr∗ of IDr∗.(d)
In the Guess stage,AI cannot make an Un-GSC query on the challenge ciphertext σ∗ under IDs∗, IDr∗, and t∗ unless the public key of IDs∗ or IDr∗ has been replaced after the Challenge stage.
A
I’s advantage is defined as AdvAIIND-CLKI-GSC-CCA2=2Pr⁡[b′=b]-1.Note. In the above Challenge stage, the sender’s identity IDs∗ may be null. In this case, it runs in encryption mode; otherwise it runs in signcryption mode. Thus, the encryption and signcryption modes share the same game, as described above.Definition 2 (type II confidentiality, encryption, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be IND-CL-Basic-KI-GSC-CCA2-II secure if no PPT adversaryAII has a nonnegligible advantage in the following game.
(
1) Setup. Given a security parameter 1k, adversary AII runs the setup algorithm to produce the system public parameter Params and a master private key s. He/she returns Params and s to challenger B.
(
2) Find Stage.
A
I
I can adaptively ask all the above oracles except the helper-key, partial-private-key, and public-key-replacement oracles. AII holds the master private key and thus he/she can compute the partial private key by himself/herself. AII is not allowed to replace anyone’s public key in the certificateless cryptographic system.
(
3) Challenge Stage.
A
I
I provides two distinct messages m0,m1 with equal length, a created sender’s identity IDs∗ (IDs∗ may be null), a created receiver’s identity IDr∗, and a time period t∗. B randomly chooses b∈0,1 and computes σ∗=GSC(mb,Params,SIDs∗,t∗,PKIDr∗). Then, B returns σ∗ to AII.
(
4) Guess Stage.
A
I
I can ask the same queries adaptively as in the Find stage. Finally, AII gives his/her guess b′. If b′=b, he/she wins the game. The restrictions on AII are as follows:(a)
The receiver’s identityIDr∗ cannot be null.(b)
AII cannot ask for IDr∗’s period private key SIDr∗,t∗ in time period t∗.(c)
AII cannot ask for IDr∗’s secret value xIDr∗(d)
In the Guess stage,AII cannot make an Un-GSC query on the challenge ciphertext σ∗ under IDs∗, IDr∗, and t∗.
A
I
I’s advantage is defined as AdvAIIIND-CLKI-GSC-CCA2=2Pr⁡[b′=b]-1.Note  1. In the above Challenge stage, the sender’s identity IDs∗ may be null. In this case, it runs in encryption mode; otherwise, it runs in signcryption mode. Thus, the encryption and signcryption modes share the same game, as described above.Note  2. To resist the malicious-but-passive KGC attack, it must let adversary AII produce the system parameters Params and master private key s in the Setup stage.Definition 3 (type I unforgeability, signature, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be existentially unforgeable-certificateless-basic key-insulated-GSC-adaptive chosen message attack-type I (EUF-CL-Basic-KI-GSC-CMA-I) secure if no PPT adversaryAI has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 1.
(
2) Queries. The same as in Definition 1.
(
3) Forgery. Finally, AI outputs a forged GSC ciphertext σ∗ in time period t∗ with IDs∗ as the sender and IDr∗ as the receiver. AI wins the game if the output of the Un-GSC algorithm is not the symbol ⊥ and if the following conditions hold:(a)
The sender’s identityIDs∗ cannot be null.(b)
AI cannot ask for IDs∗’s period private key SIDs∗,t∗ in time period t∗.(c)
AI cannot ask for IDs∗’s partial private key DIDr∗.(d)
(σ∗,t∗,IDs∗,IDr∗) is not the output of the GSC query.
A
I’s advantage is its probability of victory.Note. In the above Forgery stage, the receiver’s identity IDr∗ may be null. In this case, it runs in signature mode; otherwise, it runs in signcryption mode. Thus, the signature and signcryption modes share the same game, as described above.Definition 4 (type II unforgeability, signature, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be EUF-CL-Basic-KI-GSC-CMA-II secure if no PPT adversaryAII has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 2.
(
2) Queries. The same as in Definition 2.
(
3) Forgery. Finally, AII outputs a forged GSC ciphertext σ∗ in time period t∗ with IDs∗ as the sender and IDr∗ as the receiver. AII wins the game if the output of the Un-GSC algorithm is not the symbol ⊥ and if the following conditions hold:(a)
The sender’s identityIDs∗ cannot be null.(b)
AII cannot ask for IDs∗’s period private key SIDs∗,t∗ in time period t∗.(c)
AII cannot ask for IDs∗’s secret value xIDs∗.(d)
(σ∗,t∗,IDs∗,IDr∗) is not the output of the GSC query.
A
I
I’s advantage is its probability of victory.Note. In the above Forgery stage, the receiver’s identity IDr∗ may be null. In this case, it runs in signature mode; otherwise, it runs in signcryption mode. Thus, the signature and signcryption modes share the same game, as described above.


#### 4.2.2. Strong Key-Insulated Security

Definition 5 (type I confidentiality, encryption, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be IND-CL-Strong-KI-GSC-CCA2-I secure if no PPT adversaryAI has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 1.
(
2) Find Stage.
A
I can adaptively ask all the above oracles except the user-period-private-key oracle.
(
3) Challenge Stage. The same as in Definition 1.
(
4) Guess Stage.
A
I can adaptively make the same queries as in the Find stage. Finally, AI gives his/her guess b′. If b′=b, he/she wins the game. The restrictions on AI are as follows:(a)
The receiver’s identityIDr∗ cannot be null.(b)
AI cannot ask for the partial private key DIDr∗ of IDr∗.(c)
In the Guess stage,AI cannot make an Un-GSC query on the challenge ciphertext σ∗ under IDs∗, IDr∗, and t∗ unless the public key of IDs∗ or IDr∗ has been replaced after the challenge stage.
A
I’s advantage is defined as AdvAIIND-CLKI-GSC-CCA2=2Pr⁡[b′=b]-1.Note. In the above Challenge stage, the sender’s identity IDs∗ may be null. In this case, it runs in encryption mode; otherwise, it runs in signcryption mode. Thus, the encryption and signcryption modes share the same game, as described above.Definition 6 (type II confidentiality, encryption, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be IND-CL-Strong-KI-GSC-CCA2-II secure if no PPT adversaryAII has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 2.
(
2) Find Stage.
A
I
I can adaptively ask all the above oracles except the user-period-private-key, partial-private-key, and public-key-replacement oracles.
(
3) Challenge Stage. The same as in Definition 2.
(
4) Guess Stage.
A
I
I can make the same queries adaptively as in the Find stage. Finally, AII gives his/her guess b′. If b′=b, he/she wins the game. The restrictions on AII are as follows:(a)
The receiver’s identityIDr∗ cannot be null.(b)
AII cannot ask for IDr∗’s secret value xIDr∗.(c)
In the Guess stage,AII cannot make an Un-GSC query on the challenge ciphertext σ∗ under IDs∗, IDr∗, and t∗.
A
I
I’s advantage is defined as AdvAIIIND-CLKI-GSC-CCA2=2Pr⁡[b′=b]-1.Note  1. In the above Challenge stage, the sender’s identity IDs∗ may be null. In this case, it runs in encryption mode; otherwise, it runs in signcryption mode. Thus, the encryption and signcryption modes share the same game, as described above.Note  2. To resist the malicious-but-passive KGC attack, it must let adversary AII produce the system parameters Params and master private key s in the Setup stage.Definition 7 (type I unforgeability, signature, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be EUF-CL-Strong-KI-GSC-CMA-I secure if no PPT adversaryAI has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 5.
(
2) Queries. The same as in Definition 5.
(
3) Forgery. Finally, AI outputs a forged GSC ciphertext σ∗ in time period t∗ with IDs∗ as the sender and IDr∗ as the receiver. AI wins the game if the output of the Un-GSC algorithm is not the symbol ⊥ and if the following conditions hold:(a)
The sender’s identityIDs∗ cannot be null.(b)
AI cannot ask for IDs∗’s partial private key DIDr∗.(c)
(σ∗,t∗,IDs∗,IDr∗) is not the output of the GSC query.
A
I’s advantage is its probability of victory.Note. In the above Forgery stage, the receiver’s identity IDr∗ may be null. In this case, it runs in signature mode; otherwise, it runs in signcryption mode. Thus, the signature and signcryption modes share the same game, as described above.Definition 8 (type II unforgeability, signature, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be EUF-CL-Strong-KI-GSC-CMA-II secure if no PPT adversaryAII has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 6.
(
2) Queries. The same as in Definition 6.
(
3) Forgery. Finally, AII outputs a forged GSC ciphertext σ∗ in time period t∗ with IDs∗ as the sender and IDr∗ as the receiver. AII wins the game if the output of the Un-GSC algorithm is not the symbol ⊥ and if the following conditions hold:(a)
The sender’s identityIDs∗ cannot be null.(b)
AII cannot ask for IDs∗’s secret value xIDs∗.(c)
(σ∗,t∗,IDs∗,IDr∗) is not the output of the GSC query.
A
I
I’s advantage is its probability of victory.Note. In the above Forgery stage, the receiver’s identity IDr∗ may be null. In this case, it runs in signature mode; otherwise, it runs in signcryption mode. Thus, the signature and signcryption modes share the same game, as described above.


#### 4.2.3. Secure Key Update

Definition 9.
A certificateless key-insulated GSC scheme is said to support secure key update if a key update exposure from time periodt to t′ is equivalent to user-period-private-key exposures in both time periods t and t′.


## 4.1. Formal Definition

A certificateless key-insulated GSC scheme consists of the following eight algorithms.(
1) Setup. Given a security parameter 1k, it produces a master private key s and a global public parameter Params. It is usually run by the KGC.(
2) Partial-Private-Key-Gen. Given a user’s identity ID, the Params, and the master private key s, it produces a partial private key DID for the user. It is also usually run by the KGC, and the KGC sends DID to the user securely.(
3) User-Key-Gen. Given a user’s identity ID and the Params, it produces a secret value xID and the corresponding public key PKID for the user. It is usually run by the user.(
4) Set-Initial-Key. Given a user’s identity ID, the Params, his/her partial private key DID, and his/her secret value xID, it produces a helper private key hkID for the helper and a period private key SID,0 in time period 0 for the user. It is usually run by the user. Then, the user sends the helper private key hkID to the helper and deletes it from the user.(
5) Key-Update-H. Given a user’s identity ID, the Params, the helper private key hkID, the old time period t, and the new time period t′, it produces an update key UKID,t,t′. It is usually run in the helper device.(
6) Key-Update-U. Given a user’s identity ID, the Params, the update key UKID,t,t′, and a user’s period private key SID,t, it produces the user’s period private key SID,t′. It is usually run by the user.(
7) GSC. Given a sender’s identity IDs, a receiver’s identity IDr, the Params, a message m, a time period t, and the sender’s period private key SIDs,t, it produces a GSC ciphertext σ. It is usually run by the sender IDs or anyone in encryption mode.This algorithm can be run in three modes.(a)
Encryption mode: if IDs is null and IDr is not, then the GSC ciphertext σ is an encryption ciphertext.(b)
Signature mode: if IDr is null and IDs is not, then the GSC ciphertext σ is a signature.(c)
Signcryption mode: if neither IDs nor IDr is null, then the GSC ciphertext σ is a signcryption ciphertext.(
8) Un-GSC. Given a sender’s identity IDs, a receiver’s identity IDr, the Params, a GSC ciphertext σ, a time period t, and the receiver’s period private key SIDr,t, it recovers the message m in encryption or signcryption mode or returns true in signature mode; otherwise, it returns ⊥, indicating decryption failure or an invalid signature. It is usually run by the receiver IDr or anyone in signature mode.This algorithm can also be run in three modes.(a)
Decryption mode: if IDs is null and IDr is not, it runs in this mode.(b)
Signature verification mode: if IDr is null and IDs is not, it runs in this mode. Any person can verify the signature σ.(c)
Un-signcryption mode: if neither IDs nor IDr is null, it runs in this mode.Note. The scheme can switch between different modes automatically. If the input of the sender’s identity IDs is null and the receiver’s identity IDr is not, it automatically runs in encryption mode. If the input of IDs is not null and IDr is, it automatically runs in signature mode. If the input of neither IDs nor IDr is null, it automatically runs in signcryption mode. Both IDs and IDr being null is disallowed.


## 4.2. Security Model

There are two types of attackers in the certificateless cryptosystem [3]. A type I attacker AI does not know the system master private key, but he/she can replace the public key of any user. This considers an attack by any user other than the KGC. A type II attacker AII knows the system master private key, but he/she cannot replace anyone’s public key. This considers the attack launched by the KGC, but the KGC is honest-but-curious. Thus, the KGC generates the system parameters honestly according to the Setup algorithm. Then, he/she attempts to attack the system. In 2007, Au et al. [14] introduced a new type of KGC attack: the malicious-but-passive KGC attack. This type of KGC attack assumes that the KGC may imbed some trapdoors in the system parameters when he/she runs the Setup stage. We consider this type of KGC attack in our security model.In terms of key-insulated security, there are three types of key exposures [6]: (1) ordinary key exposure, which involves the user-period-private key being compromised; (2) key-update exposure, which involves the user’s device being compromised during the key-updating step; and (3) helper-key exposure, which involves the physically secure device being compromised. Security against the first type of exposure is called basic key-insulated security, security against the second type of exposure is called secure key update, and security against the last type of exposure is called strong key-insulated security. Compromising both the user-period-private key and helper key is not allowed because, in this case, the adversary can compute the user-period-private key in any time period.The security of GSC includes confidentiality and unforgeability. Specifically, the scheme must possess indistinguishability under an adaptively chosen ciphertext attack in encryption and signcryption modes and unforgeability under an adaptively chosen message attack in signature and signcryption modes.By referring to the security models of schemes [6, 13, 33, 34, 39, 41], we have the following nine definitions. The first four definitions focus on the first type of exposure, Definitions 5–8 focus on the last type of exposure, and Definition 9 focuses on the second type of exposure.There are nine oracles that can be accessed by adversaryA as follows.(a) User-Creation Query. Adversary A provides an identity ID. If it has been created, B returns the public key PKID to A. Otherwise, B runs the partial-key-gen and user-key-gen algorithms to produce the partial private key DID and the user’s secret-value/public key pair (xID,PKID). B runs the set-initial-key algorithm to produce the helper private key hkID. Then, B returns the public key PKID to A.(b) Partial-Private-Key Query.
A provides a created identity ID, and B returns the partial private key DID to A.(c) Secret-Value Query.
A provides a created identity ID, and B returns the secret value xID to A.(d) Public-Key Query.
A provides a created identity ID, and B returns the public key PKID to A.(e) Public-Key-Replacement Query.
A provides a created identity ID and a new public/secret-value pair (PKID′,xID′), and B replaces the old public/secret-value pair (PKID,xID) with the new one (PKID′,xID′).(f) User-Period-Private-Key Query.
A provides a created identity ID and a time period t, and B returns the user’s period private key SID,t to A (first running the key-update-h and key-update-u algorithms, if necessary).(g) Helper-Key Query.
A provides a created identity ID. B returns the user’s helper key hkID to A.(h) GSC Query.
A provides two created identities IDs,IDr (one of them may be null), a message m, and a time period t. B runs the GSC algorithm and returns its output σ to A.(i) Un-GSC Query.
A provides two created identities IDs,IDr (one of them may be null), a ciphertext σ, and a time period t. B runs the Un-GSC algorithm and returns its results to A.


### 4.2.1. Basic Key-Insulated Security

Definition 1 (type I confidentiality, encryption, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be indistinguishability-certificateless-basic key-insulated-GSC-adaptive chosen ciphertext attack-type I (IND-CL-Basic-KI-GSC-CCA2-I) secure if no probabilistic polynomial time (PPT) adversaryAI has a nonnegligible advantage in the following game.
(
1) Setup. Given a security parameter 1k, challenger B runs the setup algorithm to produce the system public parameter Params and a master private key s. He/she returns Params to adversary AI and keeps s secret.
(
2) Find Stage.
A
I can adaptively ask all the above oracles, except the helper-key oracle.
(
3) Challenge Stage.
A
I provides two distinct messages {m0,m1} with equal length, a created sender’s identity IDs∗ (IDs∗ may be null), a created receiver’s identity IDr∗, and a time period t∗. B randomly chooses b∈{0,1} and computes σ∗=GSC(mb,Params,SIDs∗,t∗,PKIDr∗). Then, B returns σ∗ to AI.
(
4) Guess Stage.
A
I can ask the same queries as in the Find stage adaptively. Finally, AI gives his/her guess b′. If b′=b, he/she wins the game. The restrictions on AI are as follows:(a)
The receiver’s identityIDr∗ cannot be null.(b)
AI cannot ask for IDr∗’s period private key SIDr∗,t∗ in time period t∗.(c)
AI cannot ask for the partial private key DIDr∗ of IDr∗.(d)
In the Guess stage,AI cannot make an Un-GSC query on the challenge ciphertext σ∗ under IDs∗, IDr∗, and t∗ unless the public key of IDs∗ or IDr∗ has been replaced after the Challenge stage.
A
I’s advantage is defined as AdvAIIND-CLKI-GSC-CCA2=2Pr⁡[b′=b]-1.Note. In the above Challenge stage, the sender’s identity IDs∗ may be null. In this case, it runs in encryption mode; otherwise it runs in signcryption mode. Thus, the encryption and signcryption modes share the same game, as described above.Definition 2 (type II confidentiality, encryption, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be IND-CL-Basic-KI-GSC-CCA2-II secure if no PPT adversaryAII has a nonnegligible advantage in the following game.
(
1) Setup. Given a security parameter 1k, adversary AII runs the setup algorithm to produce the system public parameter Params and a master private key s. He/she returns Params and s to challenger B.
(
2) Find Stage.
A
I
I can adaptively ask all the above oracles except the helper-key, partial-private-key, and public-key-replacement oracles. AII holds the master private key and thus he/she can compute the partial private key by himself/herself. AII is not allowed to replace anyone’s public key in the certificateless cryptographic system.
(
3) Challenge Stage.
A
I
I provides two distinct messages m0,m1 with equal length, a created sender’s identity IDs∗ (IDs∗ may be null), a created receiver’s identity IDr∗, and a time period t∗. B randomly chooses b∈0,1 and computes σ∗=GSC(mb,Params,SIDs∗,t∗,PKIDr∗). Then, B returns σ∗ to AII.
(
4) Guess Stage.
A
I
I can ask the same queries adaptively as in the Find stage. Finally, AII gives his/her guess b′. If b′=b, he/she wins the game. The restrictions on AII are as follows:(a)
The receiver’s identityIDr∗ cannot be null.(b)
AII cannot ask for IDr∗’s period private key SIDr∗,t∗ in time period t∗.(c)
AII cannot ask for IDr∗’s secret value xIDr∗(d)
In the Guess stage,AII cannot make an Un-GSC query on the challenge ciphertext σ∗ under IDs∗, IDr∗, and t∗.
A
I
I’s advantage is defined as AdvAIIIND-CLKI-GSC-CCA2=2Pr⁡[b′=b]-1.Note  1. In the above Challenge stage, the sender’s identity IDs∗ may be null. In this case, it runs in encryption mode; otherwise, it runs in signcryption mode. Thus, the encryption and signcryption modes share the same game, as described above.Note  2. To resist the malicious-but-passive KGC attack, it must let adversary AII produce the system parameters Params and master private key s in the Setup stage.Definition 3 (type I unforgeability, signature, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be existentially unforgeable-certificateless-basic key-insulated-GSC-adaptive chosen message attack-type I (EUF-CL-Basic-KI-GSC-CMA-I) secure if no PPT adversaryAI has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 1.
(
2) Queries. The same as in Definition 1.
(
3) Forgery. Finally, AI outputs a forged GSC ciphertext σ∗ in time period t∗ with IDs∗ as the sender and IDr∗ as the receiver. AI wins the game if the output of the Un-GSC algorithm is not the symbol ⊥ and if the following conditions hold:(a)
The sender’s identityIDs∗ cannot be null.(b)
AI cannot ask for IDs∗’s period private key SIDs∗,t∗ in time period t∗.(c)
AI cannot ask for IDs∗’s partial private key DIDr∗.(d)
(σ∗,t∗,IDs∗,IDr∗) is not the output of the GSC query.
A
I’s advantage is its probability of victory.Note. In the above Forgery stage, the receiver’s identity IDr∗ may be null. In this case, it runs in signature mode; otherwise, it runs in signcryption mode. Thus, the signature and signcryption modes share the same game, as described above.Definition 4 (type II unforgeability, signature, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be EUF-CL-Basic-KI-GSC-CMA-II secure if no PPT adversaryAII has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 2.
(
2) Queries. The same as in Definition 2.
(
3) Forgery. Finally, AII outputs a forged GSC ciphertext σ∗ in time period t∗ with IDs∗ as the sender and IDr∗ as the receiver. AII wins the game if the output of the Un-GSC algorithm is not the symbol ⊥ and if the following conditions hold:(a)
The sender’s identityIDs∗ cannot be null.(b)
AII cannot ask for IDs∗’s period private key SIDs∗,t∗ in time period t∗.(c)
AII cannot ask for IDs∗’s secret value xIDs∗.(d)
(σ∗,t∗,IDs∗,IDr∗) is not the output of the GSC query.
A
I
I’s advantage is its probability of victory.Note. In the above Forgery stage, the receiver’s identity IDr∗ may be null. In this case, it runs in signature mode; otherwise, it runs in signcryption mode. Thus, the signature and signcryption modes share the same game, as described above.


### 4.2.2. Strong Key-Insulated Security

Definition 5 (type I confidentiality, encryption, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be IND-CL-Strong-KI-GSC-CCA2-I secure if no PPT adversaryAI has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 1.
(
2) Find Stage.
A
I can adaptively ask all the above oracles except the user-period-private-key oracle.
(
3) Challenge Stage. The same as in Definition 1.
(
4) Guess Stage.
A
I can adaptively make the same queries as in the Find stage. Finally, AI gives his/her guess b′. If b′=b, he/she wins the game. The restrictions on AI are as follows:(a)
The receiver’s identityIDr∗ cannot be null.(b)
AI cannot ask for the partial private key DIDr∗ of IDr∗.(c)
In the Guess stage,AI cannot make an Un-GSC query on the challenge ciphertext σ∗ under IDs∗, IDr∗, and t∗ unless the public key of IDs∗ or IDr∗ has been replaced after the challenge stage.
A
I’s advantage is defined as AdvAIIND-CLKI-GSC-CCA2=2Pr⁡[b′=b]-1.Note. In the above Challenge stage, the sender’s identity IDs∗ may be null. In this case, it runs in encryption mode; otherwise, it runs in signcryption mode. Thus, the encryption and signcryption modes share the same game, as described above.Definition 6 (type II confidentiality, encryption, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be IND-CL-Strong-KI-GSC-CCA2-II secure if no PPT adversaryAII has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 2.
(
2) Find Stage.
A
I
I can adaptively ask all the above oracles except the user-period-private-key, partial-private-key, and public-key-replacement oracles.
(
3) Challenge Stage. The same as in Definition 2.
(
4) Guess Stage.
A
I
I can make the same queries adaptively as in the Find stage. Finally, AII gives his/her guess b′. If b′=b, he/she wins the game. The restrictions on AII are as follows:(a)
The receiver’s identityIDr∗ cannot be null.(b)
AII cannot ask for IDr∗’s secret value xIDr∗.(c)
In the Guess stage,AII cannot make an Un-GSC query on the challenge ciphertext σ∗ under IDs∗, IDr∗, and t∗.
A
I
I’s advantage is defined as AdvAIIIND-CLKI-GSC-CCA2=2Pr⁡[b′=b]-1.Note  1. In the above Challenge stage, the sender’s identity IDs∗ may be null. In this case, it runs in encryption mode; otherwise, it runs in signcryption mode. Thus, the encryption and signcryption modes share the same game, as described above.Note  2. To resist the malicious-but-passive KGC attack, it must let adversary AII produce the system parameters Params and master private key s in the Setup stage.Definition 7 (type I unforgeability, signature, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be EUF-CL-Strong-KI-GSC-CMA-I secure if no PPT adversaryAI has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 5.
(
2) Queries. The same as in Definition 5.
(
3) Forgery. Finally, AI outputs a forged GSC ciphertext σ∗ in time period t∗ with IDs∗ as the sender and IDr∗ as the receiver. AI wins the game if the output of the Un-GSC algorithm is not the symbol ⊥ and if the following conditions hold:(a)
The sender’s identityIDs∗ cannot be null.(b)
AI cannot ask for IDs∗’s partial private key DIDr∗.(c)
(σ∗,t∗,IDs∗,IDr∗) is not the output of the GSC query.
A
I’s advantage is its probability of victory.Note. In the above Forgery stage, the receiver’s identity IDr∗ may be null. In this case, it runs in signature mode; otherwise, it runs in signcryption mode. Thus, the signature and signcryption modes share the same game, as described above.Definition 8 (type II unforgeability, signature, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be EUF-CL-Strong-KI-GSC-CMA-II secure if no PPT adversaryAII has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 6.
(
2) Queries. The same as in Definition 6.
(
3) Forgery. Finally, AII outputs a forged GSC ciphertext σ∗ in time period t∗ with IDs∗ as the sender and IDr∗ as the receiver. AII wins the game if the output of the Un-GSC algorithm is not the symbol ⊥ and if the following conditions hold:(a)
The sender’s identityIDs∗ cannot be null.(b)
AII cannot ask for IDs∗’s secret value xIDs∗.(c)
(σ∗,t∗,IDs∗,IDr∗) is not the output of the GSC query.
A
I
I’s advantage is its probability of victory.Note. In the above Forgery stage, the receiver’s identity IDr∗ may be null. In this case, it runs in signature mode; otherwise, it runs in signcryption mode. Thus, the signature and signcryption modes share the same game, as described above.


### 4.2.3. Secure Key Update

Definition 9.
A certificateless key-insulated GSC scheme is said to support secure key update if a key update exposure from time periodt to t′ is equivalent to user-period-private-key exposures in both time periods t and t′.


## 4.2.1. Basic Key-Insulated Security

Definition 1 (type I confidentiality, encryption, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be indistinguishability-certificateless-basic key-insulated-GSC-adaptive chosen ciphertext attack-type I (IND-CL-Basic-KI-GSC-CCA2-I) secure if no probabilistic polynomial time (PPT) adversaryAI has a nonnegligible advantage in the following game.
(
1) Setup. Given a security parameter 1k, challenger B runs the setup algorithm to produce the system public parameter Params and a master private key s. He/she returns Params to adversary AI and keeps s secret.
(
2) Find Stage.
A
I can adaptively ask all the above oracles, except the helper-key oracle.
(
3) Challenge Stage.
A
I provides two distinct messages {m0,m1} with equal length, a created sender’s identity IDs∗ (IDs∗ may be null), a created receiver’s identity IDr∗, and a time period t∗. B randomly chooses b∈{0,1} and computes σ∗=GSC(mb,Params,SIDs∗,t∗,PKIDr∗). Then, B returns σ∗ to AI.
(
4) Guess Stage.
A
I can ask the same queries as in the Find stage adaptively. Finally, AI gives his/her guess b′. If b′=b, he/she wins the game. The restrictions on AI are as follows:(a)
The receiver’s identityIDr∗ cannot be null.(b)
AI cannot ask for IDr∗’s period private key SIDr∗,t∗ in time period t∗.(c)
AI cannot ask for the partial private key DIDr∗ of IDr∗.(d)
In the Guess stage,AI cannot make an Un-GSC query on the challenge ciphertext σ∗ under IDs∗, IDr∗, and t∗ unless the public key of IDs∗ or IDr∗ has been replaced after the Challenge stage.
A
I’s advantage is defined as AdvAIIND-CLKI-GSC-CCA2=2Pr⁡[b′=b]-1.Note. In the above Challenge stage, the sender’s identity IDs∗ may be null. In this case, it runs in encryption mode; otherwise it runs in signcryption mode. Thus, the encryption and signcryption modes share the same game, as described above.Definition 2 (type II confidentiality, encryption, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be IND-CL-Basic-KI-GSC-CCA2-II secure if no PPT adversaryAII has a nonnegligible advantage in the following game.
(
1) Setup. Given a security parameter 1k, adversary AII runs the setup algorithm to produce the system public parameter Params and a master private key s. He/she returns Params and s to challenger B.
(
2) Find Stage.
A
I
I can adaptively ask all the above oracles except the helper-key, partial-private-key, and public-key-replacement oracles. AII holds the master private key and thus he/she can compute the partial private key by himself/herself. AII is not allowed to replace anyone’s public key in the certificateless cryptographic system.
(
3) Challenge Stage.
A
I
I provides two distinct messages m0,m1 with equal length, a created sender’s identity IDs∗ (IDs∗ may be null), a created receiver’s identity IDr∗, and a time period t∗. B randomly chooses b∈0,1 and computes σ∗=GSC(mb,Params,SIDs∗,t∗,PKIDr∗). Then, B returns σ∗ to AII.
(
4) Guess Stage.
A
I
I can ask the same queries adaptively as in the Find stage. Finally, AII gives his/her guess b′. If b′=b, he/she wins the game. The restrictions on AII are as follows:(a)
The receiver’s identityIDr∗ cannot be null.(b)
AII cannot ask for IDr∗’s period private key SIDr∗,t∗ in time period t∗.(c)
AII cannot ask for IDr∗’s secret value xIDr∗(d)
In the Guess stage,AII cannot make an Un-GSC query on the challenge ciphertext σ∗ under IDs∗, IDr∗, and t∗.
A
I
I’s advantage is defined as AdvAIIIND-CLKI-GSC-CCA2=2Pr⁡[b′=b]-1.Note  1. In the above Challenge stage, the sender’s identity IDs∗ may be null. In this case, it runs in encryption mode; otherwise, it runs in signcryption mode. Thus, the encryption and signcryption modes share the same game, as described above.Note  2. To resist the malicious-but-passive KGC attack, it must let adversary AII produce the system parameters Params and master private key s in the Setup stage.Definition 3 (type I unforgeability, signature, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be existentially unforgeable-certificateless-basic key-insulated-GSC-adaptive chosen message attack-type I (EUF-CL-Basic-KI-GSC-CMA-I) secure if no PPT adversaryAI has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 1.
(
2) Queries. The same as in Definition 1.
(
3) Forgery. Finally, AI outputs a forged GSC ciphertext σ∗ in time period t∗ with IDs∗ as the sender and IDr∗ as the receiver. AI wins the game if the output of the Un-GSC algorithm is not the symbol ⊥ and if the following conditions hold:(a)
The sender’s identityIDs∗ cannot be null.(b)
AI cannot ask for IDs∗’s period private key SIDs∗,t∗ in time period t∗.(c)
AI cannot ask for IDs∗’s partial private key DIDr∗.(d)
(σ∗,t∗,IDs∗,IDr∗) is not the output of the GSC query.
A
I’s advantage is its probability of victory.Note. In the above Forgery stage, the receiver’s identity IDr∗ may be null. In this case, it runs in signature mode; otherwise, it runs in signcryption mode. Thus, the signature and signcryption modes share the same game, as described above.Definition 4 (type II unforgeability, signature, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be EUF-CL-Basic-KI-GSC-CMA-II secure if no PPT adversaryAII has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 2.
(
2) Queries. The same as in Definition 2.
(
3) Forgery. Finally, AII outputs a forged GSC ciphertext σ∗ in time period t∗ with IDs∗ as the sender and IDr∗ as the receiver. AII wins the game if the output of the Un-GSC algorithm is not the symbol ⊥ and if the following conditions hold:(a)
The sender’s identityIDs∗ cannot be null.(b)
AII cannot ask for IDs∗’s period private key SIDs∗,t∗ in time period t∗.(c)
AII cannot ask for IDs∗’s secret value xIDs∗.(d)
(σ∗,t∗,IDs∗,IDr∗) is not the output of the GSC query.
A
I
I’s advantage is its probability of victory.Note. In the above Forgery stage, the receiver’s identity IDr∗ may be null. In this case, it runs in signature mode; otherwise, it runs in signcryption mode. Thus, the signature and signcryption modes share the same game, as described above.


## 4.2.2. Strong Key-Insulated Security

Definition 5 (type I confidentiality, encryption, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be IND-CL-Strong-KI-GSC-CCA2-I secure if no PPT adversaryAI has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 1.
(
2) Find Stage.
A
I can adaptively ask all the above oracles except the user-period-private-key oracle.
(
3) Challenge Stage. The same as in Definition 1.
(
4) Guess Stage.
A
I can adaptively make the same queries as in the Find stage. Finally, AI gives his/her guess b′. If b′=b, he/she wins the game. The restrictions on AI are as follows:(a)
The receiver’s identityIDr∗ cannot be null.(b)
AI cannot ask for the partial private key DIDr∗ of IDr∗.(c)
In the Guess stage,AI cannot make an Un-GSC query on the challenge ciphertext σ∗ under IDs∗, IDr∗, and t∗ unless the public key of IDs∗ or IDr∗ has been replaced after the challenge stage.
A
I’s advantage is defined as AdvAIIND-CLKI-GSC-CCA2=2Pr⁡[b′=b]-1.Note. In the above Challenge stage, the sender’s identity IDs∗ may be null. In this case, it runs in encryption mode; otherwise, it runs in signcryption mode. Thus, the encryption and signcryption modes share the same game, as described above.Definition 6 (type II confidentiality, encryption, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be IND-CL-Strong-KI-GSC-CCA2-II secure if no PPT adversaryAII has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 2.
(
2) Find Stage.
A
I
I can adaptively ask all the above oracles except the user-period-private-key, partial-private-key, and public-key-replacement oracles.
(
3) Challenge Stage. The same as in Definition 2.
(
4) Guess Stage.
A
I
I can make the same queries adaptively as in the Find stage. Finally, AII gives his/her guess b′. If b′=b, he/she wins the game. The restrictions on AII are as follows:(a)
The receiver’s identityIDr∗ cannot be null.(b)
AII cannot ask for IDr∗’s secret value xIDr∗.(c)
In the Guess stage,AII cannot make an Un-GSC query on the challenge ciphertext σ∗ under IDs∗, IDr∗, and t∗.
A
I
I’s advantage is defined as AdvAIIIND-CLKI-GSC-CCA2=2Pr⁡[b′=b]-1.Note  1. In the above Challenge stage, the sender’s identity IDs∗ may be null. In this case, it runs in encryption mode; otherwise, it runs in signcryption mode. Thus, the encryption and signcryption modes share the same game, as described above.Note  2. To resist the malicious-but-passive KGC attack, it must let adversary AII produce the system parameters Params and master private key s in the Setup stage.Definition 7 (type I unforgeability, signature, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be EUF-CL-Strong-KI-GSC-CMA-I secure if no PPT adversaryAI has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 5.
(
2) Queries. The same as in Definition 5.
(
3) Forgery. Finally, AI outputs a forged GSC ciphertext σ∗ in time period t∗ with IDs∗ as the sender and IDr∗ as the receiver. AI wins the game if the output of the Un-GSC algorithm is not the symbol ⊥ and if the following conditions hold:(a)
The sender’s identityIDs∗ cannot be null.(b)
AI cannot ask for IDs∗’s partial private key DIDr∗.(c)
(σ∗,t∗,IDs∗,IDr∗) is not the output of the GSC query.
A
I’s advantage is its probability of victory.Note. In the above Forgery stage, the receiver’s identity IDr∗ may be null. In this case, it runs in signature mode; otherwise, it runs in signcryption mode. Thus, the signature and signcryption modes share the same game, as described above.Definition 8 (type II unforgeability, signature, and signcryption modes).
A certificateless key-insulated GSC scheme is said to be EUF-CL-Strong-KI-GSC-CMA-II secure if no PPT adversaryAII has a nonnegligible advantage in the following game.
(
1) Setup. The same as in Definition 6.
(
2) Queries. The same as in Definition 6.
(
3) Forgery. Finally, AII outputs a forged GSC ciphertext σ∗ in time period t∗ with IDs∗ as the sender and IDr∗ as the receiver. AII wins the game if the output of the Un-GSC algorithm is not the symbol ⊥ and if the following conditions hold:(a)
The sender’s identityIDs∗ cannot be null.(b)
AII cannot ask for IDs∗’s secret value xIDs∗.(c)
(σ∗,t∗,IDs∗,IDr∗) is not the output of the GSC query.
A
I
I’s advantage is its probability of victory.Note. In the above Forgery stage, the receiver’s identity IDr∗ may be null. In this case, it runs in signature mode; otherwise, it runs in signcryption mode. Thus, the signature and signcryption modes share the same game, as described above.


## 4.2.3. Secure Key Update

Definition 9.
A certificateless key-insulated GSC scheme is said to support secure key update if a key update exposure from time periodt to t′ is equivalent to user-period-private-key exposures in both time periods t and t′.


## 5. A Concrete Certificateless Key-Insulated GSC Scheme

### 5.1. Concrete Scheme

By referring to Seo et al.’s [44] pairing-free certificateless signcryption tag key encapsulation mechanism, we propose an efficient pairing-free certificateless key-insulated GSC scheme.Setup. Given a security parameter 1k, the KGC produces two large prime numbers p and q. Then, he/she defines a secure elliptic curve E(Fp) on the finite field Fp. Let G1 be a cyclic group of order qon E(Fp), and let P be a generator of G1. He/she randomly chooses s∈Zq∗ as the master private key and computes Ppub=s·P as the master public key. He/she chooses seven hash functions: H0,H1,H2,H3,H4,H5:{0,1}∗→Zq∗, and H6:{0,1}∗→{0,1}L×zq∗, where L is the bit length of message m. He/she defines a special function f(ID): if the identity ID is null, then f(ID)=0; otherwise, f(ID)=1. The system public parameters are Params={p,q,E(Fp),G1,P,Ppub,f,H0,H1,H2,H3,H4,H5,H6}. He/she keeps the master private key s secret.Partial-Private-Key-Gen. Given a user’s identity ID, the KGC randomly chooses rID∈Zq∗ and computes YID=rID·P and yID=rID+s·h0,IDmodq, where h0,ID=H0(ID,YID). KGC sends yID to ID securely.User-Key-Gen. The user with identity ID randomly chooses xID∈Zq∗ as his/her secret value. He/she computes the public key as XID=xID·P.Set-Initial-Key. The user with identity ID randomly chooses uID,0,hkID∈Zq∗ and computes UID,0=uID,0·P, TID=hkID·P, h1,ID,0=H1(ID,YID,TID,0), h2,ID=H2(ID,YID,XID,TID), h3,ID,0=H3(ID,YID,UID,0,0), and sID,0=yID+xID·h2,ID+uID,0·h3,ID,0+hkID·h1,ID,0modq. Finally, the helper private key is hkID, and the user’s period private key in time period 0 is sID,0. The user broadcasts (UID,0,YID,TID). Then, the user sends the helper key hkID and the ephemeral variable uID,0 in time period 0 to the helper and deletes them from the user.Key-Update-H. Given a user’s identity ID and YID, the old time period t, and the new time period t′, the helper chooses uID,t′∈Zq∗ and computes UID,t′=uID,t′·P,UID,t=uID,t·P, TID=hkID·P, h1,ID,t′=H1(ID,YID,TID,t′), h1,ID,t=H1(ID,YID,TID,t), h3,ID,t′=H3(ID,YID,UID,t′,t′),h3,ID,t=H3(ID,YID,UID,t,t), and ukID,t,t′=uID,t′·h3,ID,t′-uID,t·h3,ID,t+hkID·h1,ID,t′-h1,ID,tmodq. Then, the update key is (ukID,t,t′,UID,t′). The helper saves uID,t′ and deletes uID,t.Key-Update-U. Given the update key (ukID,t,t′,UID,t′), the user ID updates his/her period private key from time period t to t′ as sID,t′=sID,t+ukID,t,t′. Then, he/she broadcasts UID,t′.GSC. Let m∈{0,1}L, let the sender’s identity be IDs, let the receiver’s identity be IDr, and let the time period be t. The sender randomly chooses a1,a2∈Zq∗ and computes R1=a1·P,R2=a2·P, h4=H4(m,R1,R2,IDs,YIDs,IDr,UIDr,t,XIDr,YIDr,TIDr), h5=H5(m,R1,R2,IDr,UIDr,t,XIDr,YIDr,TIDr), and u=f(IDs)·sIDs,t·h4+a1·h5+a2modq. Then, he/she computes h0,IDr=H0(IDr,YIDr), h1,IDr,t=H1(IDr,YIDr,TIDr,t),  h2,IDr=H2(IDr,YIDr,XIDr,TIDr),   h3,IDr,t=H3(IDr,YIDr,UIDr,t,t), V=a1·(YIDr+Ppub·h0,IDr+XIDr·h2,IDr+UIDr,t·h3,IDr,t+TIDr·h1,IDr,t), h6=f(IDr)·H6(IDs,IDr,UIDs,t,XIDs,YIDs,TIDs,R1,V,t), and c=(m∥u)⊕h6. Finally, the output is (t,σ)=(t,(R1,R2,c)).This algorithm can be run in three modes. We add atag in the ciphertext.(
1) Encryption Mode. If IDs is null and IDr is not, then f(IDs)=0 and f(IDr)=1. The ciphertext (t,σ)=(t,(R1,R2,c,tag=1)) is an encryption ciphertext. In this case, UIDs,t, XIDs, YIDs, and TIDs are all set to the infinite point ∞ on E(Fp), and sIDs,t is set to zero. Additionally, in this case, u=a1·h5+a2modq.(
2) Signature Mode. If IDr is null and IDs is not, then f(IDr)=0 and f(IDs)=1. The ciphertext (t,σ)=(t,(R1,R2,c,tag=2)) is a signature. In this case, UIDr,t, XIDr, YIDr, and TIDr are all set to the infinite point ∞ on E(Fp). Additionally, in this case, h6=0 and c=m∥u.(
3) Signcryption Mode. If neither IDs nor IDr is null, then f(IDs)=1 and f(IDr)=1. The ciphertext (t,σ)=(t,(R1,R2,c,tag=3)) is a signcryption ciphertext.Un-GSC. The ciphertext is (t,σ)=(t,(R1,R2,c,tag)).(a)
tag=1. σ=(R1,R2,c) is an encryption ciphertext. The receiver IDr computes V=sIDr,t·R1 and h6=H6(null,IDr,∞,∞,∞,∞,R1,V,t) and recovers the message m∥u=c⊕h6. Then, he/she computes h5=H5(m,R1,R2,IDr,UIDr,t,XIDr,YIDr,TIDr) and verifies whether u·P=R1·h5+R2 holds true or not. If it does, he/she accepts it.(b)
tag=2. σ=(R1,R2,c) is a signature. In this case, c=m∥u. The verifier computes h0,IDs=H0(IDs,YIDs), h1,IDs,t=H1(IDs,YIDs,TIDs,t), h2,IDs=H2(IDs,YIDs,XIDs,TIDs), h3,IDs,t=H3(IDs,YIDs,UIDs,t,t), h4=H4(m,R1,R2,IDs,YIDs,null,∞,∞,∞,∞), and h5=H5(m,R1,R2,null,∞,∞,∞,∞). Then, he/she verifies whether u·P=(YIDs+Ppub·h0,IDs+XIDs·h2,IDs+UIDs,t·h3,IDs,t+TIDs·h1,IDs,t)·h4+R1·h5+R2 holds true or not. If it does, he/she accepts the signature.(c)
tag=3. σ=(R1,R2,c) is a signcryption ciphertext. The receiver IDr computes V=sIDr,t·R1 and h6=H6(IDs,IDr,UIDs,t,XIDs,YIDs,TIDs,R1,V,t) and recovers the message m∥u=c⊕h6. Then, he/she computes h0,IDs=H0(IDs,YIDs), h1,IDs,t=H1(IDs,YIDs,TIDs,t),   h2,IDs=H2(IDs,YIDs,XIDs,TIDs), h3,IDs,t=H3(IDs,YIDs,UIDs,t,t), h4=H4(m,R1,R2,IDs,YIDs,IDr,UIDr,t,XIDr,YIDr,TIDr), and h5=H5(m,R1,R2,IDr,UIDr,t,XIDr,YIDr,TIDr) and verifies whether u·P=(YIDs+Ppub·h0,IDs+XIDs·h2,IDs+UIDs,t·h3,IDs,t+TIDs·h1,IDs,t)·h4+R1·h5+R2 holds true or not. If it does, he/she accepts it.


### 5.2. Correctness

①(1)u·P=sIDs,t·h4+a1·h5+a2·P=yIDs+xIDs·h2,IDs+uIDs,t·h3,IDs,t+hkIDs·h1,IDs,t·h4+a1·h5+a2·P=rIDs+s·h0,IDs+xIDs·h2,IDs+uIDs,t·h3,IDs,t+hkIDs·h1,IDs,t·h4+a1·h5+a2·P=YIDs+Ppub·h0,IDs+XIDs·h2,IDs+UIDs,t·h3,IDs,t+TIDs·h1,IDs,t·h4+R1·h5+R2.②(2)V=a1·YIDr+Ppub·h0,IDr+XIDr·h2,IDr+UIDr,t·h3,IDr,t+TIDr·h1,IDr,t=a1·P·rIDr+s·h0,IDr+xIDr·h2,IDr+uIDr,t·h3,IDr,t+hkIDr·h1,IDr,t=yIDr+xIDr·h2,IDr+uIDr,t·h3,IDr,t+hkIDr·h1,IDr,t·R1=sIDr,t·R1.


### 5.3. Random-Access Key Update

Obviously, our scheme supports random-access key update; thus, for any current time periodi and any desired time period j, the private key can be updated from ski to skj in one step.


## 5.1. Concrete Scheme

By referring to Seo et al.’s [44] pairing-free certificateless signcryption tag key encapsulation mechanism, we propose an efficient pairing-free certificateless key-insulated GSC scheme.Setup. Given a security parameter 1k, the KGC produces two large prime numbers p and q. Then, he/she defines a secure elliptic curve E(Fp) on the finite field Fp. Let G1 be a cyclic group of order qon E(Fp), and let P be a generator of G1. He/she randomly chooses s∈Zq∗ as the master private key and computes Ppub=s·P as the master public key. He/she chooses seven hash functions: H0,H1,H2,H3,H4,H5:{0,1}∗→Zq∗, and H6:{0,1}∗→{0,1}L×zq∗, where L is the bit length of message m. He/she defines a special function f(ID): if the identity ID is null, then f(ID)=0; otherwise, f(ID)=1. The system public parameters are Params={p,q,E(Fp),G1,P,Ppub,f,H0,H1,H2,H3,H4,H5,H6}. He/she keeps the master private key s secret.Partial-Private-Key-Gen. Given a user’s identity ID, the KGC randomly chooses rID∈Zq∗ and computes YID=rID·P and yID=rID+s·h0,IDmodq, where h0,ID=H0(ID,YID). KGC sends yID to ID securely.User-Key-Gen. The user with identity ID randomly chooses xID∈Zq∗ as his/her secret value. He/she computes the public key as XID=xID·P.Set-Initial-Key. The user with identity ID randomly chooses uID,0,hkID∈Zq∗ and computes UID,0=uID,0·P, TID=hkID·P, h1,ID,0=H1(ID,YID,TID,0), h2,ID=H2(ID,YID,XID,TID), h3,ID,0=H3(ID,YID,UID,0,0), and sID,0=yID+xID·h2,ID+uID,0·h3,ID,0+hkID·h1,ID,0modq. Finally, the helper private key is hkID, and the user’s period private key in time period 0 is sID,0. The user broadcasts (UID,0,YID,TID). Then, the user sends the helper key hkID and the ephemeral variable uID,0 in time period 0 to the helper and deletes them from the user.Key-Update-H. Given a user’s identity ID and YID, the old time period t, and the new time period t′, the helper chooses uID,t′∈Zq∗ and computes UID,t′=uID,t′·P,UID,t=uID,t·P, TID=hkID·P, h1,ID,t′=H1(ID,YID,TID,t′), h1,ID,t=H1(ID,YID,TID,t), h3,ID,t′=H3(ID,YID,UID,t′,t′),h3,ID,t=H3(ID,YID,UID,t,t), and ukID,t,t′=uID,t′·h3,ID,t′-uID,t·h3,ID,t+hkID·h1,ID,t′-h1,ID,tmodq. Then, the update key is (ukID,t,t′,UID,t′). The helper saves uID,t′ and deletes uID,t.Key-Update-U. Given the update key (ukID,t,t′,UID,t′), the user ID updates his/her period private key from time period t to t′ as sID,t′=sID,t+ukID,t,t′. Then, he/she broadcasts UID,t′.GSC. Let m∈{0,1}L, let the sender’s identity be IDs, let the receiver’s identity be IDr, and let the time period be t. The sender randomly chooses a1,a2∈Zq∗ and computes R1=a1·P,R2=a2·P, h4=H4(m,R1,R2,IDs,YIDs,IDr,UIDr,t,XIDr,YIDr,TIDr), h5=H5(m,R1,R2,IDr,UIDr,t,XIDr,YIDr,TIDr), and u=f(IDs)·sIDs,t·h4+a1·h5+a2modq. Then, he/she computes h0,IDr=H0(IDr,YIDr), h1,IDr,t=H1(IDr,YIDr,TIDr,t),  h2,IDr=H2(IDr,YIDr,XIDr,TIDr),   h3,IDr,t=H3(IDr,YIDr,UIDr,t,t), V=a1·(YIDr+Ppub·h0,IDr+XIDr·h2,IDr+UIDr,t·h3,IDr,t+TIDr·h1,IDr,t), h6=f(IDr)·H6(IDs,IDr,UIDs,t,XIDs,YIDs,TIDs,R1,V,t), and c=(m∥u)⊕h6. Finally, the output is (t,σ)=(t,(R1,R2,c)).This algorithm can be run in three modes. We add atag in the ciphertext.(
1) Encryption Mode. If IDs is null and IDr is not, then f(IDs)=0 and f(IDr)=1. The ciphertext (t,σ)=(t,(R1,R2,c,tag=1)) is an encryption ciphertext. In this case, UIDs,t, XIDs, YIDs, and TIDs are all set to the infinite point ∞ on E(Fp), and sIDs,t is set to zero. Additionally, in this case, u=a1·h5+a2modq.(
2) Signature Mode. If IDr is null and IDs is not, then f(IDr)=0 and f(IDs)=1. The ciphertext (t,σ)=(t,(R1,R2,c,tag=2)) is a signature. In this case, UIDr,t, XIDr, YIDr, and TIDr are all set to the infinite point ∞ on E(Fp). Additionally, in this case, h6=0 and c=m∥u.(
3) Signcryption Mode. If neither IDs nor IDr is null, then f(IDs)=1 and f(IDr)=1. The ciphertext (t,σ)=(t,(R1,R2,c,tag=3)) is a signcryption ciphertext.Un-GSC. The ciphertext is (t,σ)=(t,(R1,R2,c,tag)).(a)
tag=1. σ=(R1,R2,c) is an encryption ciphertext. The receiver IDr computes V=sIDr,t·R1 and h6=H6(null,IDr,∞,∞,∞,∞,R1,V,t) and recovers the message m∥u=c⊕h6. Then, he/she computes h5=H5(m,R1,R2,IDr,UIDr,t,XIDr,YIDr,TIDr) and verifies whether u·P=R1·h5+R2 holds true or not. If it does, he/she accepts it.(b)
tag=2. σ=(R1,R2,c) is a signature. In this case, c=m∥u. The verifier computes h0,IDs=H0(IDs,YIDs), h1,IDs,t=H1(IDs,YIDs,TIDs,t), h2,IDs=H2(IDs,YIDs,XIDs,TIDs), h3,IDs,t=H3(IDs,YIDs,UIDs,t,t), h4=H4(m,R1,R2,IDs,YIDs,null,∞,∞,∞,∞), and h5=H5(m,R1,R2,null,∞,∞,∞,∞). Then, he/she verifies whether u·P=(YIDs+Ppub·h0,IDs+XIDs·h2,IDs+UIDs,t·h3,IDs,t+TIDs·h1,IDs,t)·h4+R1·h5+R2 holds true or not. If it does, he/she accepts the signature.(c)
tag=3. σ=(R1,R2,c) is a signcryption ciphertext. The receiver IDr computes V=sIDr,t·R1 and h6=H6(IDs,IDr,UIDs,t,XIDs,YIDs,TIDs,R1,V,t) and recovers the message m∥u=c⊕h6. Then, he/she computes h0,IDs=H0(IDs,YIDs), h1,IDs,t=H1(IDs,YIDs,TIDs,t),   h2,IDs=H2(IDs,YIDs,XIDs,TIDs), h3,IDs,t=H3(IDs,YIDs,UIDs,t,t), h4=H4(m,R1,R2,IDs,YIDs,IDr,UIDr,t,XIDr,YIDr,TIDr), and h5=H5(m,R1,R2,IDr,UIDr,t,XIDr,YIDr,TIDr) and verifies whether u·P=(YIDs+Ppub·h0,IDs+XIDs·h2,IDs+UIDs,t·h3,IDs,t+TIDs·h1,IDs,t)·h4+R1·h5+R2 holds true or not. If it does, he/she accepts it.


## 5.2. Correctness

①(1)u·P=sIDs,t·h4+a1·h5+a2·P=yIDs+xIDs·h2,IDs+uIDs,t·h3,IDs,t+hkIDs·h1,IDs,t·h4+a1·h5+a2·P=rIDs+s·h0,IDs+xIDs·h2,IDs+uIDs,t·h3,IDs,t+hkIDs·h1,IDs,t·h4+a1·h5+a2·P=YIDs+Ppub·h0,IDs+XIDs·h2,IDs+UIDs,t·h3,IDs,t+TIDs·h1,IDs,t·h4+R1·h5+R2.②(2)V=a1·YIDr+Ppub·h0,IDr+XIDr·h2,IDr+UIDr,t·h3,IDr,t+TIDr·h1,IDr,t=a1·P·rIDr+s·h0,IDr+xIDr·h2,IDr+uIDr,t·h3,IDr,t+hkIDr·h1,IDr,t=yIDr+xIDr·h2,IDr+uIDr,t·h3,IDr,t+hkIDr·h1,IDr,t·R1=sIDr,t·R1.


## 5.3. Random-Access Key Update

Obviously, our scheme supports random-access key update; thus, for any current time periodi and any desired time period j, the private key can be updated from ski to skj in one step.


## 6. Security Analysis of the Proposed Scheme

### 6.1. Confidentiality of Basic Key Insulation

Theorem 10 (type I confidentiality).
In the random oracle model, if there is a PPT adversaryAI with a nonnegligible advantage ε against the IND-CL-Basic-KI-GSC-CCA2-I security of the scheme running in encryption or signcryption mode in time t and performing at most qHiHi(i=0,1,2,…,6) queries, qU-C user-creation queries, qPa-p-k partial-private-key queries, qPe-p-k period-private-key queries, qGSC GSC queries, and qUn-GSC Un-GSC queries, then the CDH problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qPa-p-k·(1-1/qU-C)qPe-p-k·(qUn-GSC/2k) in time t′<t+(7·qGSC+8·qUn-GSC)·tm, where tm denotes the time for a scalar multiplication on G1.Proof.
Suppose challengerC is given (P,aP,bP)∈G13 for random a,b∈Zq∗. C does not know the values of a and b and is asked to compute abP. To utilize adversary AI, challenger C will simulate all the oracles defined in Definition 1.
Setup.
C sets Ppub=aP. Other public parameters are produced normally. C gives the system public parameters Params={p,q,E(Fp),G1,P,Ppub,f,H0,H1,H2,H3,H4,H5,H6} to AI. C maintains nine lists, L0,L1,L2,L3,L4,L5,L6,Lk, and LPe-k, which are initially empty. C randomly selects λ∈{1,2,…,qU-C}.
Find Stage.
A
I makes queries to the following oracles adaptively.
User-Creation Query.
A
I provides an identity ID. C looks up list Lk to determine whether it contains the item. If it does, C returns ID’s public key XID and public parameters (YID,TID) to AI. Otherwise, C proceeds as follows and returns public key XID and public parameters (YID,TID) to AI.
C randomly selects xID∈Zq∗ as the secret value and computes the public key as XID=xID·P. C randomly selects hkID∈Zq∗ as the helper private key and computes TID=hkID·P. (1)
ID=IDλ. C randomly selects rIDλ∈Zq∗ and computes YIDλ=rIDλ·P. C inserts the tuple (IDλ,XIDλ,YIDλ,xIDλ,rIDλ,-,hkIDλ,TIDλ) into list Lk.(2)
ID≠IDλ. C randomly selects yID,h0,ID∈Zq∗ and computes YID=yID·P-h0,ID·Ppub. C inserts the tuple (ID,YID,h0,ID) into list L0. If there is a collision in list L0, C rechooses yID,h0,ID∈Zq∗ and repeats the process. C inserts the tuple (ID,XID,YID,xID,-,yID,hkID,TID) into list Lk.
H
0
Q
u
e
r
y. AI supplies a tuple (ID,YID). C first checks list L0 to determine whether it contains the item (ID,YID,h0,ID). If it does, C returns h0,ID. Otherwise, C randomly selects h0,ID∈Zq∗ and repeats the process until h0,ID is not in list L0. C stores the tuple (ID,YID,h0,ID) in list L0 and returns h0,ID to AI.
H
1
Q
u
e
r
y. AI supplies a tuple (ID,YID,TID,t). C first checks list L1 to determine whether it contains the item (ID,YID,TID,t,h1,ID,t). If it does, C returns h1,ID,t. Otherwise, C randomly selects h1,ID,t∈Zq∗ and repeats the process until h1,ID,t is not in list L1. C stores the tuple (ID,YID,TID,t,h1,ID,t) in list L1 and returns h1,ID,t to AI.
H
2
Q
u
e
r
y. AI supplies a tuple (ID,YID,XID,TID). C first checks list L2 to determine whether it contains the item (ID,YID,XID,TID,h2,ID). If it does, C returns h2,ID. Otherwise, C randomly selects h2,ID∈Zq∗ and repeats the process until h2,ID is not in list L2. C stores the tuple (ID,YID,XID,TID,h2,ID) in list L2 and returns h2,ID to AI.
H
3
Q
u
e
r
y. AI supplies a tuple (ID,YID,UID,t,t). C first checks list L3 to determine whether it contains the item (ID,YID,UID,t,t,h3,ID,t). If it does, C returns h3,ID,t. Otherwise, C randomly selects h3,ID,t∈Zq∗ and repeats the process until h3,ID,t is not in list L3. C stores the tuple (ID,YID,UID,t,t,h3,ID,t) in list L3 and returns h3,ID,t to AI.
H
4
Query.
A
I supplies a tuple (m,R1,R2,IDs,YIDs,IDr,UIDr,t,XIDr,YIDr,TIDr). C first checks list L4 to determine whether it contains the item (m,R1,R2,IDs,YIDs,IDr,UIDr,t,XIDr,YIDr,TIDr,h4). If it does, C returns h4. Otherwise, C randomly selects h4∈Zq∗ and repeats the process until h4 is not in list L4. C stores the tuple (m,R1,R2,IDs,YIDs,IDr,UIDr,t,XIDr,YIDr,TIDr,h4) in list L4 and returns h4 to AI.
H
5
Query.
A
I supplies a tuple (m,R1,R2,IDr,UIDr,t,XIDr,YIDr,TIDr). C first checks list L5 to determine whether it contains the item (m,R1,R2,IDr,UIDr,t,XIDr,YIDr,TIDr,h5). If it does, C returns h5. Otherwise, C randomly selects h5∈Zq∗ and repeats the process until h5 is not in list L5. C stores the tuple (m,R1,R2,IDr,UIDr,t,XIDr,YIDr,TIDr,h5) in list L5 and returns h5 to AI.
H
6
Query.
A
I supplies a tuple (IDs,IDr,UIDs,t,XIDs,YIDs,TIDs,R1,V,t). C first checks list L6 to determine whether it contains the item (IDs,IDr,UIDs,t,XIDs,YIDs,TIDs,R1,V,t,h6). If it does, C returns h6. Otherwise, C randomly selects h6∈{0,1}L×zq∗ and repeats the process until h6 is not in list L6. C stores the tuple (IDs,IDr,UIDs,t,XIDs,YIDs,TIDs,R1,V,t,h6) in list L6 and returns h6 to AI.
Partial-Private-Key Query.
A
I provides a created identity ID. (1)
ID≠IDλ. C retrieves yID from list Lk and returns it to AI.(2)
ID=IDλ. C aborts.
Secret-Value Query.
A
I provides a created identity ID. C retrieves xID from list Lk and returns it to AI.
Public-Key Query. AI provides a created identity ID. C retrieves the public key XID and public parameters (YID,TID) from list Lk and returns them to AI.
Public-Key-Replacement Query.
A
I provides a created identity ID and a new public/secret-value pair (XID′,xID′). C replaces the old public/secret-value pair (XID,xID) with the new one (XID′,xID′) and updates list Lk.
User-Period-Private-Key Query.
A
I provides a created identity ID and a time period t. C first checks list LPe-k to determine whether it contains the item (ID,t,uID,t,UID,t,sID,t). If it does, C returns (UID,t,sID,t). Otherwise, we consider two cases.(1)
ID≠IDλ. C randomly chooses uID,t∈Zq∗ and computes UID,t=uID,t·P. C retrieves (XID,YID,TID) from list Lk. Then C makes an H1 query with the tuple (ID,YID,TID,t) and obtains a response h1,ID,t. C makes an H2 query with the tuple (ID,YID,XID,TID) and obtains a response h2,ID. C makes an H3 query with the tuple (ID,YID,UID,t,t) and obtains a response h3,ID,t. C retrieves (xID,yID,hkID) from list Lk and computes the period private key SID,t in time period t as sID,t=yID+xID·h2,ID+uID,t·h3,ID,t+hkID·h1,ID,tmodq. C inserts the tuple (ID,t,uID,t,UID,t,sID,t) into list LPe-k and returns (UID,t,sID,t).(2)
ID=IDλ. C aborts.
GSC Query.
A
I provides two created identities IDs,IDr (one of them may be null), a message m, and a time period t. If IDs is null, it is equal to an encryption oracle, which only requires the public parameters. Otherwise, we consider two cases. (1)
IDs≠IDλ. C runs the GSC algorithm as normal because C can obtain the private key sIDs,t of IDs in time period t.(2)
IDs=IDλ. C first checks list LPe-k to determine whether it contains the item (IDλ,t,uIDλ,t,UIDλ,t,-). If it does, C retrieves (uIDλ,t,UIDλ,t); otherwise, C randomly chooses uIDλ,t∈Zq∗, computes UIDλ,t=uIDλ,t·P, and inserts the tuple (IDλ,t,uIDλ,t,UIDλ,t,-) into list LPe-k.
C randomly chooses a1,r2,h4∈Zq∗ and computes R1=a1·P, R2=r2·P-(YIDλ+Ppub·h0,IDλ+XIDλ·h2,IDλ+UIDλ,t·h3,IDλ,t+TIDλ·h1,IDλ,t)·h4, h5=H5(m,R1,R2,IDr,UIDr,t,XIDr,YIDr,TIDr), and u=a1·h5+r2modq. Then, he/she computes V=a1·(YIDr+Ppub·h0,IDr+XIDr·h2,IDr+UIDr,t·h3,IDr,t+TIDr·h1,IDr,t), h6=f(IDr)·H6(IDλ,IDr,UIDλ,t,XIDλ,YIDλ,TIDλ,R1,V,t), and c=m∥u⊕h6. The values needed for the above computations can be obtained by querying associated oracles. C inserts the tuple (m,R1,R2,IDλ,YIDλ,IDr,UIDr,t,XIDr,YIDr,TIDr,h4) into list L4. If there is a collision, C rechooses a1,r2,h4∈Zq∗ and repeats the process. Finally, C returns σ=(R1,R2,c) to AI.
Un-GSC Query.
A
I provides two created identities {IDs,IDr} (one of them may be null), a ciphertext σ, and a time period t. If IDr is null, it is equal to a signature verification oracle, which needs only the public parameters. Otherwise, we consider two cases.(1)
IDr≠IDλ. C runs the Un-GSC algorithm as normal because C can obtain the private key sIDr,t of IDr in time period t.(2)
IDr=IDλ. C does not know the period private key of IDr in time period t. C retrieves UIDs,t and UIDλ,t from list LPe-k (if UIDs,t or UIDλ,t does not exist in list LPe-k, then C makes a period-private-key or GSC query to ensure that they are produced). C starts from the first item of list L6 to compute m∥u=c⊕h6 and verifies whether the equation u·P=(YIDs+Ppub·h0,IDs+XIDs·h2,IDs+UIDs,t·h3,IDs,t+TIDs·h1,IDs,t)·h4+R1·h5+R2 holds true, where h0,IDs=H0(IDs,YIDs), h1,IDs,t=H1(IDs,YIDs,TIDs,t), h2,IDs=H2(IDs,YIDs,XIDs,TIDs), h3,IDs,t=H3(IDs,YIDs,UIDs,t,t), h4=H4(m,R1,R2,IDs,YIDs,IDλ,UIDλ,t,XIDλ,YIDλ,TIDλ), and h5=H5(m,R1,R2,IDλ,UIDλ,t,XIDλ,YIDλ,TIDλ). The values needed for the above computations can be obtained by querying associated oracles. If the equation holds true, C returns the message m; else C moves to the next item of list L6 and repeats the process. If no message returns when C traverses all the items of list L6, C returns ⊥.
Challenge Stage.
A
I chooses two different messages (m0,m1) with equal length, two created challenge identities (IDs∗,IDr∗) (IDs∗ may be null), and a time period t∗. If IDr∗≠IDλ, C aborts. Otherwise, C randomly chooses η∈0,1 and randomly chooses r2,h5∗∈Zq∗. C retrieves UIDs∗,t∗ and UIDλ,t∗ from list LPe-k (if UIDs∗,t∗ or UIDλ,t∗ does not exist in list LPe-k, then C makes a period-private-key or GSC query to ensure that they are produced). C sets R1∗=bP. C randomly chooses V∗∈G. C computes R2∗=r2·P-(bP)·h5∗,h4∗=H4(mη,R1∗,R2∗,IDs∗,YIDs∗,IDλ,UIDλ,t∗,XIDλ,YIDλ,TIDλ) and u∗=f(IDs∗)·sIDs∗,t∗·h4∗+r2modq. Then, C computes h6∗=H6(IDs∗,IDλ,UIDs∗,t∗,XIDs∗,YIDs∗,TIDs∗,R1∗,V∗,t∗) and c∗=(mη∥u∗)⊕h6∗. The values needed for the above computations can be obtained by querying associated oracles. C inserts the tuple (mη,R1∗,R2∗,IDλ,UIDλ,t∗,XIDλ,YIDλ,TIDλ,h5∗) into list L5. If there is a collision, C rechooses r2,h5∗∈Zq∗ and repeats the process. C returns the challenge ciphertext σ∗=(R1∗,R2∗,c∗) to AI.
Guess Stage.
A
I can make the same queries adaptively as in the Find stage with the restrictions given in Definition 1. Finally, AI must give his/her guess η′. AI cannot discover that σ∗ is not a valid ciphertext unless he/she asks the H6 oracle with the tuple (IDs∗,IDλ,UIDs∗,t∗,XIDs∗,YIDs∗,TIDs∗,R1∗,V∗,t∗), where V∗=a1∗·(YIDλ+Ppub·h0,IDλ+XIDλ·h2,IDλ+UIDλ,t∗·h3,IDλ,t∗+TIDλ·h1,IDλ,t∗) = abP·h0,IDλ+(rIDλ+xIDλ·h2,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗)·(bP). If this occurs, C retrieves rIDλ, xIDλ, and hkIDλ from list Lk, and it retrieves uIDλ,t∗ and UIDλ,t∗ from list LPe-k. C makes associated hash oracle queries to obtain h0,IDλ, h1,IDλ,t∗, h2,IDλ, and h3,IDλ,t∗. Then, C can output abP=[V∗-(rIDλ+xIDλ·h2,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗)·(bP)]·(h0,IDλ)-1.
Now, we assess the probability of success. In the Challenge stage, the probability thatIDr∗=IDλ is 1/qU-C. In both the partial-private-key and user-period-private-key queries, the probability of C querying IDλ is 1/qU-C. In the Un-GSC stage, the probability of C refusing the right ciphertext is less than qUn-GSC/2k.
In terms of the time complexity, GSC and Un-GSC queries need 7tm and 8tm computations, respectively.Theorem 11 (type II confidentiality).
In the random oracle model, if there is a PPT adversaryAII with a nonnegligible advantage ε against the IND-CL-Basic-KI-GSC-CCA2-II security of the scheme running in encryption or signcryption mode in time t and performing at most qHiHi(i=0,1,2,…,6) queries, qU-C user-creation queries, qSec secret-value queries, qPe-p-k period-private-key queries, qGSC GSC queries, and qUn-GSC Un-GSC queries, then the CDH problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qSec·(1-1/qU-C)qPe-p-k·(qUn-GSC/2k) in time t′<t+(7·qGSC+8·qUn-GSC)·tm, where tm denotes the time for a scalar multiplication on G1.Proof.
Suppose challengerC is given (P,aP,bP)∈G13 for random a,b∈Zq∗. C does not know the values of a and b and is asked to compute abP.
Setup. Adversary AII randomly selects s∈Zq∗ as the master private key and computes the master public key as Ppub=sP. Other public parameters are produced normally. AII gives the system public parameters Params={p,q,E(Fp),G1,P,Ppub,f,H0,H1,H2,H3,H4,H5,H6} and master private key s to C. C maintains nine lists L0,L1,L2,L3,L4,L5,L6,Lk, and LPe-k, which are initially empty. C randomly selects λ∈{1,2,…,qU-C}.
Find Stage.
A
I
I makes queries to the following oracles adaptively: H0,H1,H2,H3,H4,H5,H6, public-key, user-period-private-key, GSC, and Un-GSC queries are the same as in Theorem 10. The partial-private-key and public-key-replacement queries are not needed for AII.
User-Creation Query.
A
I
I provides an identity ID. C looks up list Lk to determine whether it contains the item. If it does, C returns ID’s public key XID and public parameters (YID,TID) to AII. Otherwise, C proceeds as follows and returns public key XID and public parameters (YID,TID) to AII.
C randomly selects rID∈Zq∗ and computes YID=rID·P and yID=rID+s·H0(ID,YID)modq. C randomly selects hkID∈Zq∗ as the helper private key and computes TID=hkID·P.(1)
ID=IDλ. C sets the public key as XID=aP and inserts the tuple (IDλ,XIDλ,YIDλ,-,rIDλ,yIDλ,hkIDλ,TIDλ) into list Lk.(2)
ID≠IDλ. C randomly selects xID∈Zq∗ as the secret value and computes the public key as XID=xID·P. C inserts the tuple (ID,XID,YID,xID,rID,yID,hkID,TID) into list Lk.
Secret-Value Query.
A
I
I provides a created identity ID. (1)
ID≠IDλ. C retrieves xID from list Lk and returns it to AII(2)
ID=IDλ. C aborts.
Challenge Stage. The same as in Theorem 10.
Guess Stage.
A
I
I can make the same queries adaptively as in the Find stage with the restrictions given in Definition 2. Finally, AII must give his/her guess η′. AII cannot discover that σ∗ is not a valid ciphertext unless he/she asks the H6 oracle with the tuple (IDs∗,IDλ,UIDs∗,t∗,XIDs∗,YIDs∗,TIDs∗,R1∗,V∗,t∗), where V∗=a1∗·(YIDλ+Ppub·h0,IDλ+XIDλ·h2,IDλ+UIDλ,t∗·h3,IDλ,t∗+TIDλ·h1,IDλ,t∗) = abP·h2,IDλ+(rIDλ+s·h0,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗)·(bP). If this occurs, C retrieves rIDλ and hkIDλ from list Lk as well as uIDλ,t∗ and UIDλ,t∗ from list LPe-k. C makes associated hash oracles to obtain h0,IDλ, h1,IDλ,t∗, h2,IDλ, and h3,IDλ,t∗. Then, C can output abP=[V∗-(rIDλ+s·h0,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗)·bP]·(h2,IDλ)-1.
Now, we assess the probability of success. In the challenge stage, the probability thatIDr∗=IDλ is 1/qU-C. In both the secret-value and user-period-private-key queries, the probability of C querying IDλ is 1/qU-C. In the Un-GSC stage, the probability of C refusing the right ciphertext is less than qUn-GSC/2k.
In terms of the time complexity, GSC and Un-GSC queries need 7tm and 8tm computations, respectively.


### 6.2. Unforgeability of Basic Key Insulation

Theorem 12 (type I unforgeability).
In the random oracle model, if there is a PPT adversaryAI with a nonnegligible advantage ε against the EUF-CL-Basic-KI-GSC-CMA-I security of the scheme running in signature or signcryption mode in time t and performing at most qHiHi(i=0,1,2,…,6) queries, qU-C user-creation queries, qPa-p-k partial-private-key queries, qPe-p-k period-private-key queries, qGSC GSC queries, and qUn-GSC Un-GSC queries, then the EC-DL problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qPa-p-k·(1-1/qU-C)qPe-p-k·(qUn-GSC/2k)·(ε3/(qH0+qH4)6-3/2k) in time t′<t+(7·qGSC+8·qUn-GSC)·tm, where tm denotes the time for a scalar multiplication on G1.Proof.
Suppose that challengerC is given (P,aP)∈G12 for random a∈Zq∗. C does not know the value of a and is asked to compute a. To utilize adversary AI, challenger C will simulate all the oracles defined in Definition 3.
Setup. The same as in Theorem 10.
Queries. The same as in Theorem 10.
Forgery. Finally, AI outputs a forged GSC ciphertext σ∗=(R1∗,R2∗,c∗) in message m∗ in time period t∗ with IDs∗ as the sender and IDr∗ as the receiver. If IDs∗≠IDλ, C aborts. Otherwise, if σ∗ can pass the validation of the Un-GSC algorithm and AI does not violate the restrictions of Definition 3, according to the multiple-forking lemma [45], we can obtain four valid signatures: (IDλ,IDr∗,m∗,u∗(1),h0,IDλ(1),h4∗(1)),(IDλ,IDr∗,m∗,u∗(2), h0,IDλ(1),h4∗(2)),(IDλ,IDr∗,m∗,u∗(3),h0,IDλ(2),h4∗(3)), and (IDλ,IDr∗,m∗,u∗(4),h0,IDλ(2),h4∗(4)), where h0,IDλ(1) and h0,IDλ(2) are two different hash values corresponding to the H0 oracle and h4∗(1), h4∗(2), h4∗(3), and h4∗(4) are four different hash values corresponding to the H4 oracle. Because u∗=sIDλ,t∗·h4∗+a1∗·h5∗+a2∗modq, we can obtain four equations: (3)u∗1=rIDλ+a·h0,IDλ1+xIDλ·h2,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗·h4∗1+a1∗·h5∗+a2∗modq,u∗2=rIDλ+a·h0,IDλ1+xIDλ·h2,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗·h4∗2+a1∗·h5∗+a2∗modq,u∗3=rIDλ+a·h0,IDλ2+xIDλ·h2,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗·h4∗3+a1∗·h5∗+a2∗modq,u∗4=rIDλ+a·h0,IDλ2+xIDλ·h2,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗·h4∗4+a1∗·h5∗+a2∗modq.
Then,C can compute(4)u∗1-u∗2h4∗1-h4∗2-1=rIDλ+a·h0,IDλ1+xIDλ·h2,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗,u∗3-u∗4h4∗3-h4∗4-1=rIDλ+a·h0,IDλ2+xIDλ·h2,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗,u∗1-u∗2h4∗1-h4∗2-1-u∗3-u∗4h4∗3-h4∗4-1·h0,IDλ1-h0,IDλ2-1=a.
Now, we assess the probability of success. In the Forgery stage, the probability ofIDs∗=IDλ is 1/qU-C. In both the partial-private-key and user-period-private-key queries, the probability of C querying with IDλ is 1/qU-C. In the Un-GSC stage, the probability of C refusing the right ciphertext is less than qUn-GSC/2k. In conjunction with the multiple-forking lemma, the EC-DL problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qPa-p-k·(1-1/qU-C)qPe-p-k·(qUn-GSC/2k)·(ε3/(qH0+qH4)6-3/2k).
In terms of the time complexity, GSC and Un-GSC queries need 7tm and 8tm computations, respectively.Theorem 13 (type II unforgeability).
In the random oracle model, if there is a PPT adversaryAII with a nonnegligible advantage ε against the EUF-CL-Basic-KI-GSC-CMA-II security of the scheme running in signature or signcryption mode in time t and performing at most qHiHi(i=0,1,2,…,6) queries, qU-C user-creation queries, qSec secret-value queries, qPe-p-k period-private-key queries, qGSC GSC queries, and qUn-GSC Un-GSC queries, then the EC-DL problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qSecret·(1-1/qU-C)qPe-p-k·(qUn-GSC/2k)·(ε3/(qH2+qH4)6-3/2k) in time t′<t+(7·qGSC+8·qUn-GSC)·tm, where tm denotes the time for a scalar multiplication on G1.Proof.
Suppose that challengerC is given (P,aP)∈G12 for random a∈Zq∗. C does not know the value of a and is asked to compute a. To utilize adversary AII, challenger C will simulate all the oracles defined in Definition 4.
Setup. The same as in Theorem 11.
Queries. The same as in Theorem 11.
Forgery. Finally, AII outputs a forged GSC ciphertext σ∗=(R1∗,R2∗,c∗) in message m∗ in time period t∗ with IDs∗ as the sender and IDr∗ as the receiver. If IDs∗≠IDλ, C aborts. Otherwise, if σ∗ can pass the validation of the Un-GSC algorithm and AII does not violate the restrictions of Definition 4, according to the multiple-forking lemma [45], we can obtain four valid signatures: (IDλ,IDr∗,m∗,u∗(1),h2,IDλ(1),h4∗(1)),(IDλ,IDr∗,m∗,u∗(2), h2,IDλ(1),h4∗(2)),(IDλ,IDr∗,m∗,u∗(3),h2,IDλ(2),h4∗(3)), and (IDλ,IDr∗,m∗,u∗(4),h2,IDλ(2),h4∗(4)), where h2,IDλ(1) and h2,IDλ(2) are two different hash values corresponding to the H2 oracle and h4∗(1), h4∗(2), h4∗(3), and h4∗(4) are four different hash values corresponding to the H4 oracle. Because u∗=sIDλ,t∗·h4∗+a1∗·h5∗+a2∗modq, we can obtain four equations: (5)u∗1=rIDλ+s·h0,IDλ+a·h2,IDλ1+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗·h4∗1+a1∗·h5∗+a2∗modq,u∗2=rIDλ+s·h0,IDλ+a·h2,IDλ1+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗·h4∗2+a1∗·h5∗+a2∗modq,u∗3=rIDλ+s·h0,IDλ+a·h2,IDλ2+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗·h4∗3+a1∗·h5∗+a2∗modq,u∗4=rIDλ+s·h0,IDλ+a·h2,IDλ2+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗·h4∗4+a1∗·h5∗+a2∗modq.
Then,C can compute (6)u∗1-u∗2h4∗1-h4∗2-1=rIDλ+s·h0,IDλ+a·h2,IDλ1+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗,u∗3-u∗4h4∗3-h4∗4-1=rIDλ+s·h0,IDλ+a·h2,IDλ2+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗,u∗1-u∗2h4∗1-h4∗2-1-u∗3-u∗4h4∗3-h4∗4-1·h2,IDλ1-h2,IDλ2-1=a.
Now, we assess the probability of success. In the Challenge stage, the probability ofIDs∗=IDλ is 1/qU-C. In both the secret-value and user-period-private-key queries, the probability of C querying IDλ is 1/qU-C. In the Un-GSC stage, the probability of C refusing the right ciphertext is less than qUn-GSC/2k. In conjunction with the multiple-forking lemma, the EC-GDL problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qSecret·(1-1/qU-C)qPe-p-k·(qUn-GSC/2k)·(ε3/(qH2+qH4)6-3/2k).
In terms of the time complexity, GSC and Un-GSC queries need 7tm and 8tm computations, respectively.


### 6.3. Confidentiality of Strong Key Insulation

Theorem 14 (type I confidentiality).
In the random oracle model, if there is a PPT adversaryAI with a nonnegligible advantage ε against the IND-CL-Strong-KI-GSC-CCA2-I security of the scheme running in encryption or signcryption mode in time t and performing at most qHiHi(i=0,1,2,…,6) queries, qU-C user-creation queries, qPa-p-k partial-private-key queries, qGSC GSC queries, and qUn-GSC Un-GSC queries, then the CDH problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qPa-p-k·(qUn-GSC/2k) in time t′<t+(7·qGSC+8·qUn-GSC)·tm, where tm denotes the time for a scalar multiplication on G1.Proof.
The proof is almost the same as that of Theorem10. The difference is that AI cannot make a user-period-private-key query but can adaptively ask the helper-key oracle. The GSC oracle is also slightly different.
Helper-Key Query.
A
I provides a created identity ID and a time period t. C returns the user’s helper key hkID and the ephemeral variable uID,t in time period t to AI.
GSC Query.
A
I provides two created identities {IDs,IDr} (one of them may be null), a message m, and a time period t. If IDs is null, it is equal to an encryption oracle, which needs only the public parameters. Otherwise, we consider two cases. (1)
IDs≠IDλ. C first checks list LPe-k to determine whether it contains the item (IDs,t,uIDs,t,UIDs,t,sIDs,t). If it does, C retrieves the period private key sIDs,t in time period t and runs the GSC algorithm as normal. Otherwise, C randomly chooses uIDs,t∈Zq∗ and computes UIDs,t=uIDs,t·P. C retrieves (XIDs,YIDs,TIDs) from list Lk. Then, C makes an H1 query with the tuple (IDs,YIDs,TIDs,t) and obtains a response h1,IDs,t. C makes an H2 query with the tuple (IDs,YIDs,XIDs,TIDs) and obtains a response h2,IDs. C makes an H3 query with the tuple (IDs,YIDs,UIDs,t,t) and obtains a response h3,IDs,t. C retrieves (xIDs,yIDs,hkIDs) from list Lk and computes the period private key SIDs,t in time period t as sIDs,t=yIDs+xIDs·h2,IDs+uIDs,t·h3,IDs,t+hkIDs·h1,IDs,tmodq. C inserts the tuple (IDs,t,uIDs,t,UIDs,t,sIDs,t) into list LPe-k and runs the GSC algorithm as normal.(2)
IDs=IDλ. It is the same as in Theorem 10.
Finally,C returns the GSC ciphertext σ=(R1,R2,c) and UIDs,t to AI.Theorem 15 (type II confidentiality).
In the random oracle model, if there is a PPT adversaryAII with a nonnegligible advantage ε against the IND-CL-Strong-KI-GSC-CCA2-II security of the scheme running in encryption or signcryption mode in time t and performing at most qHiHi(i=0,1,2,…,6) queries, qU-C user-creation queries, qSec secret-value queries, qGSC GSC queries, and qUn-GSC Un-GSC queries, then the CDH problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qSec·(qUn-GSC/2k) in time t′<t+(7·qGSC+8·qUn-GSC)·tm, where tm denotes the time for a scalar multiplication on G1.Proof.
The proof is almost the same as that of Theorem11. The difference is that AII cannot make a user-period-private-key query but can adaptively ask the helper-key oracle.
The user-creation query, secret-value query, public-key query, and Un-GSC queries are the same as in Theorem11.
The helper-key query and GSC query are the same as in Theorem14.


### 6.4. Unforgeability of Strong Key Insulation

Theorem 16 (type I unforgeability).
In the random oracle model, if there is a PPT adversaryAI with a nonnegligible advantage ε against the EUF-CL-Strong-KI-GSC-CMA-I security of the scheme running in signature or signcryption mode in time t and performing at most qHiHi(i=0,1,2,…,6) queries, qU-C user-creation queries, qPa-p-k partial-private-key queries, qGSC GSC queries, and qUn-GSC Un-GSC queries, then the EC-DL problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qPa-p-k·(qUn-GSC/2k)·(ε3/(qH0+qH4)6-3/2k) in time t′<t+(7·qGSC+8·qUn-GSC)·tm, where tm denotes the time for a scalar multiplication on G1.Proof.
The proof is almost the same as that of Theorem12. The difference is that AI cannot make a user-period-private-key query but can adaptively ask the helper-key oracle.
All the oracle queries are the same as in Theorem14.Theorem 17 (type II unforgeability).
In the random oracle model, if there is a PPT adversaryAII with a nonnegligible advantage ε against the EUF-CL-Strong-KI-GSC-CMA-II security of the scheme running in signature or signcryption mode in time t and performing at most qHiHi(i=0,1,2,…,6) queries, qU-C user-creation queries, qSec secret-value queries, qGSC GSC queries, and qUn-GSC Un-GSC queries, then the EC-DL problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qSecret·(qUn-GSC/2k)·(ε3/(qH2+qH4)6-3/2k) in time t′<t+(7·qGSC+8·qUn-GSC)·tm, where tm denotes the time for a scalar multiplication on G1.Proof.
The proof is almost the same as that of Theorem13. The difference is that AII cannot make a user-period-private-key query but can adaptively ask the helper-key oracle.
All the oracle queries are the same as in Theorem15.


### 6.5. Secure Key Update

Theorem 18.
Our certificateless key-insulated GSC scheme supports secure key update.Proof.
If an adversary compromises the user’s storage while a key is being updated from time periodt to t′, then he/she can obtain the user’s period private key sID,t in time period t and the update key ukID,t,t′ from t to t′. Then, he/she can compute the user’s period private key sID,t′=sID,t+ukID,t,t′ in time period t′. The adversary cannot obtain any other useful information except sID,t, ukID,t,t′, and sID,t′. In addition, from the equation sID,t=yID+xID·h2,ID+uID,t·h3,ID,t+hkID·h1,ID,tmodq, he/she cannot derive any private information because the number of unknown variables is greater than the number of equations. Furthermore, he/she cannot derive any private information from the equation ukID,t,t′=uID,t′·h3,ID,t′-uID,t·h3,ID,t+hkID·(h1,ID,t′-h1,ID,t)modq either.


## 6.1. Confidentiality of Basic Key Insulation

Theorem 10 (type I confidentiality).
In the random oracle model, if there is a PPT adversaryAI with a nonnegligible advantage ε against the IND-CL-Basic-KI-GSC-CCA2-I security of the scheme running in encryption or signcryption mode in time t and performing at most qHiHi(i=0,1,2,…,6) queries, qU-C user-creation queries, qPa-p-k partial-private-key queries, qPe-p-k period-private-key queries, qGSC GSC queries, and qUn-GSC Un-GSC queries, then the CDH problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qPa-p-k·(1-1/qU-C)qPe-p-k·(qUn-GSC/2k) in time t′<t+(7·qGSC+8·qUn-GSC)·tm, where tm denotes the time for a scalar multiplication on G1.Proof.
Suppose challengerC is given (P,aP,bP)∈G13 for random a,b∈Zq∗. C does not know the values of a and b and is asked to compute abP. To utilize adversary AI, challenger C will simulate all the oracles defined in Definition 1.
Setup.
C sets Ppub=aP. Other public parameters are produced normally. C gives the system public parameters Params={p,q,E(Fp),G1,P,Ppub,f,H0,H1,H2,H3,H4,H5,H6} to AI. C maintains nine lists, L0,L1,L2,L3,L4,L5,L6,Lk, and LPe-k, which are initially empty. C randomly selects λ∈{1,2,…,qU-C}.
Find Stage.
A
I makes queries to the following oracles adaptively.
User-Creation Query.
A
I provides an identity ID. C looks up list Lk to determine whether it contains the item. If it does, C returns ID’s public key XID and public parameters (YID,TID) to AI. Otherwise, C proceeds as follows and returns public key XID and public parameters (YID,TID) to AI.
C randomly selects xID∈Zq∗ as the secret value and computes the public key as XID=xID·P. C randomly selects hkID∈Zq∗ as the helper private key and computes TID=hkID·P. (1)
ID=IDλ. C randomly selects rIDλ∈Zq∗ and computes YIDλ=rIDλ·P. C inserts the tuple (IDλ,XIDλ,YIDλ,xIDλ,rIDλ,-,hkIDλ,TIDλ) into list Lk.(2)
ID≠IDλ. C randomly selects yID,h0,ID∈Zq∗ and computes YID=yID·P-h0,ID·Ppub. C inserts the tuple (ID,YID,h0,ID) into list L0. If there is a collision in list L0, C rechooses yID,h0,ID∈Zq∗ and repeats the process. C inserts the tuple (ID,XID,YID,xID,-,yID,hkID,TID) into list Lk.
H
0
Q
u
e
r
y. AI supplies a tuple (ID,YID). C first checks list L0 to determine whether it contains the item (ID,YID,h0,ID). If it does, C returns h0,ID. Otherwise, C randomly selects h0,ID∈Zq∗ and repeats the process until h0,ID is not in list L0. C stores the tuple (ID,YID,h0,ID) in list L0 and returns h0,ID to AI.
H
1
Q
u
e
r
y. AI supplies a tuple (ID,YID,TID,t). C first checks list L1 to determine whether it contains the item (ID,YID,TID,t,h1,ID,t). If it does, C returns h1,ID,t. Otherwise, C randomly selects h1,ID,t∈Zq∗ and repeats the process until h1,ID,t is not in list L1. C stores the tuple (ID,YID,TID,t,h1,ID,t) in list L1 and returns h1,ID,t to AI.
H
2
Q
u
e
r
y. AI supplies a tuple (ID,YID,XID,TID). C first checks list L2 to determine whether it contains the item (ID,YID,XID,TID,h2,ID). If it does, C returns h2,ID. Otherwise, C randomly selects h2,ID∈Zq∗ and repeats the process until h2,ID is not in list L2. C stores the tuple (ID,YID,XID,TID,h2,ID) in list L2 and returns h2,ID to AI.
H
3
Q
u
e
r
y. AI supplies a tuple (ID,YID,UID,t,t). C first checks list L3 to determine whether it contains the item (ID,YID,UID,t,t,h3,ID,t). If it does, C returns h3,ID,t. Otherwise, C randomly selects h3,ID,t∈Zq∗ and repeats the process until h3,ID,t is not in list L3. C stores the tuple (ID,YID,UID,t,t,h3,ID,t) in list L3 and returns h3,ID,t to AI.
H
4
Query.
A
I supplies a tuple (m,R1,R2,IDs,YIDs,IDr,UIDr,t,XIDr,YIDr,TIDr). C first checks list L4 to determine whether it contains the item (m,R1,R2,IDs,YIDs,IDr,UIDr,t,XIDr,YIDr,TIDr,h4). If it does, C returns h4. Otherwise, C randomly selects h4∈Zq∗ and repeats the process until h4 is not in list L4. C stores the tuple (m,R1,R2,IDs,YIDs,IDr,UIDr,t,XIDr,YIDr,TIDr,h4) in list L4 and returns h4 to AI.
H
5
Query.
A
I supplies a tuple (m,R1,R2,IDr,UIDr,t,XIDr,YIDr,TIDr). C first checks list L5 to determine whether it contains the item (m,R1,R2,IDr,UIDr,t,XIDr,YIDr,TIDr,h5). If it does, C returns h5. Otherwise, C randomly selects h5∈Zq∗ and repeats the process until h5 is not in list L5. C stores the tuple (m,R1,R2,IDr,UIDr,t,XIDr,YIDr,TIDr,h5) in list L5 and returns h5 to AI.
H
6
Query.
A
I supplies a tuple (IDs,IDr,UIDs,t,XIDs,YIDs,TIDs,R1,V,t). C first checks list L6 to determine whether it contains the item (IDs,IDr,UIDs,t,XIDs,YIDs,TIDs,R1,V,t,h6). If it does, C returns h6. Otherwise, C randomly selects h6∈{0,1}L×zq∗ and repeats the process until h6 is not in list L6. C stores the tuple (IDs,IDr,UIDs,t,XIDs,YIDs,TIDs,R1,V,t,h6) in list L6 and returns h6 to AI.
Partial-Private-Key Query.
A
I provides a created identity ID. (1)
ID≠IDλ. C retrieves yID from list Lk and returns it to AI.(2)
ID=IDλ. C aborts.
Secret-Value Query.
A
I provides a created identity ID. C retrieves xID from list Lk and returns it to AI.
Public-Key Query. AI provides a created identity ID. C retrieves the public key XID and public parameters (YID,TID) from list Lk and returns them to AI.
Public-Key-Replacement Query.
A
I provides a created identity ID and a new public/secret-value pair (XID′,xID′). C replaces the old public/secret-value pair (XID,xID) with the new one (XID′,xID′) and updates list Lk.
User-Period-Private-Key Query.
A
I provides a created identity ID and a time period t. C first checks list LPe-k to determine whether it contains the item (ID,t,uID,t,UID,t,sID,t). If it does, C returns (UID,t,sID,t). Otherwise, we consider two cases.(1)
ID≠IDλ. C randomly chooses uID,t∈Zq∗ and computes UID,t=uID,t·P. C retrieves (XID,YID,TID) from list Lk. Then C makes an H1 query with the tuple (ID,YID,TID,t) and obtains a response h1,ID,t. C makes an H2 query with the tuple (ID,YID,XID,TID) and obtains a response h2,ID. C makes an H3 query with the tuple (ID,YID,UID,t,t) and obtains a response h3,ID,t. C retrieves (xID,yID,hkID) from list Lk and computes the period private key SID,t in time period t as sID,t=yID+xID·h2,ID+uID,t·h3,ID,t+hkID·h1,ID,tmodq. C inserts the tuple (ID,t,uID,t,UID,t,sID,t) into list LPe-k and returns (UID,t,sID,t).(2)
ID=IDλ. C aborts.
GSC Query.
A
I provides two created identities IDs,IDr (one of them may be null), a message m, and a time period t. If IDs is null, it is equal to an encryption oracle, which only requires the public parameters. Otherwise, we consider two cases. (1)
IDs≠IDλ. C runs the GSC algorithm as normal because C can obtain the private key sIDs,t of IDs in time period t.(2)
IDs=IDλ. C first checks list LPe-k to determine whether it contains the item (IDλ,t,uIDλ,t,UIDλ,t,-). If it does, C retrieves (uIDλ,t,UIDλ,t); otherwise, C randomly chooses uIDλ,t∈Zq∗, computes UIDλ,t=uIDλ,t·P, and inserts the tuple (IDλ,t,uIDλ,t,UIDλ,t,-) into list LPe-k.
C randomly chooses a1,r2,h4∈Zq∗ and computes R1=a1·P, R2=r2·P-(YIDλ+Ppub·h0,IDλ+XIDλ·h2,IDλ+UIDλ,t·h3,IDλ,t+TIDλ·h1,IDλ,t)·h4, h5=H5(m,R1,R2,IDr,UIDr,t,XIDr,YIDr,TIDr), and u=a1·h5+r2modq. Then, he/she computes V=a1·(YIDr+Ppub·h0,IDr+XIDr·h2,IDr+UIDr,t·h3,IDr,t+TIDr·h1,IDr,t), h6=f(IDr)·H6(IDλ,IDr,UIDλ,t,XIDλ,YIDλ,TIDλ,R1,V,t), and c=m∥u⊕h6. The values needed for the above computations can be obtained by querying associated oracles. C inserts the tuple (m,R1,R2,IDλ,YIDλ,IDr,UIDr,t,XIDr,YIDr,TIDr,h4) into list L4. If there is a collision, C rechooses a1,r2,h4∈Zq∗ and repeats the process. Finally, C returns σ=(R1,R2,c) to AI.
Un-GSC Query.
A
I provides two created identities {IDs,IDr} (one of them may be null), a ciphertext σ, and a time period t. If IDr is null, it is equal to a signature verification oracle, which needs only the public parameters. Otherwise, we consider two cases.(1)
IDr≠IDλ. C runs the Un-GSC algorithm as normal because C can obtain the private key sIDr,t of IDr in time period t.(2)
IDr=IDλ. C does not know the period private key of IDr in time period t. C retrieves UIDs,t and UIDλ,t from list LPe-k (if UIDs,t or UIDλ,t does not exist in list LPe-k, then C makes a period-private-key or GSC query to ensure that they are produced). C starts from the first item of list L6 to compute m∥u=c⊕h6 and verifies whether the equation u·P=(YIDs+Ppub·h0,IDs+XIDs·h2,IDs+UIDs,t·h3,IDs,t+TIDs·h1,IDs,t)·h4+R1·h5+R2 holds true, where h0,IDs=H0(IDs,YIDs), h1,IDs,t=H1(IDs,YIDs,TIDs,t), h2,IDs=H2(IDs,YIDs,XIDs,TIDs), h3,IDs,t=H3(IDs,YIDs,UIDs,t,t), h4=H4(m,R1,R2,IDs,YIDs,IDλ,UIDλ,t,XIDλ,YIDλ,TIDλ), and h5=H5(m,R1,R2,IDλ,UIDλ,t,XIDλ,YIDλ,TIDλ). The values needed for the above computations can be obtained by querying associated oracles. If the equation holds true, C returns the message m; else C moves to the next item of list L6 and repeats the process. If no message returns when C traverses all the items of list L6, C returns ⊥.
Challenge Stage.
A
I chooses two different messages (m0,m1) with equal length, two created challenge identities (IDs∗,IDr∗) (IDs∗ may be null), and a time period t∗. If IDr∗≠IDλ, C aborts. Otherwise, C randomly chooses η∈0,1 and randomly chooses r2,h5∗∈Zq∗. C retrieves UIDs∗,t∗ and UIDλ,t∗ from list LPe-k (if UIDs∗,t∗ or UIDλ,t∗ does not exist in list LPe-k, then C makes a period-private-key or GSC query to ensure that they are produced). C sets R1∗=bP. C randomly chooses V∗∈G. C computes R2∗=r2·P-(bP)·h5∗,h4∗=H4(mη,R1∗,R2∗,IDs∗,YIDs∗,IDλ,UIDλ,t∗,XIDλ,YIDλ,TIDλ) and u∗=f(IDs∗)·sIDs∗,t∗·h4∗+r2modq. Then, C computes h6∗=H6(IDs∗,IDλ,UIDs∗,t∗,XIDs∗,YIDs∗,TIDs∗,R1∗,V∗,t∗) and c∗=(mη∥u∗)⊕h6∗. The values needed for the above computations can be obtained by querying associated oracles. C inserts the tuple (mη,R1∗,R2∗,IDλ,UIDλ,t∗,XIDλ,YIDλ,TIDλ,h5∗) into list L5. If there is a collision, C rechooses r2,h5∗∈Zq∗ and repeats the process. C returns the challenge ciphertext σ∗=(R1∗,R2∗,c∗) to AI.
Guess Stage.
A
I can make the same queries adaptively as in the Find stage with the restrictions given in Definition 1. Finally, AI must give his/her guess η′. AI cannot discover that σ∗ is not a valid ciphertext unless he/she asks the H6 oracle with the tuple (IDs∗,IDλ,UIDs∗,t∗,XIDs∗,YIDs∗,TIDs∗,R1∗,V∗,t∗), where V∗=a1∗·(YIDλ+Ppub·h0,IDλ+XIDλ·h2,IDλ+UIDλ,t∗·h3,IDλ,t∗+TIDλ·h1,IDλ,t∗) = abP·h0,IDλ+(rIDλ+xIDλ·h2,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗)·(bP). If this occurs, C retrieves rIDλ, xIDλ, and hkIDλ from list Lk, and it retrieves uIDλ,t∗ and UIDλ,t∗ from list LPe-k. C makes associated hash oracle queries to obtain h0,IDλ, h1,IDλ,t∗, h2,IDλ, and h3,IDλ,t∗. Then, C can output abP=[V∗-(rIDλ+xIDλ·h2,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗)·(bP)]·(h0,IDλ)-1.
Now, we assess the probability of success. In the Challenge stage, the probability thatIDr∗=IDλ is 1/qU-C. In both the partial-private-key and user-period-private-key queries, the probability of C querying IDλ is 1/qU-C. In the Un-GSC stage, the probability of C refusing the right ciphertext is less than qUn-GSC/2k.
In terms of the time complexity, GSC and Un-GSC queries need 7tm and 8tm computations, respectively.Theorem 11 (type II confidentiality).
In the random oracle model, if there is a PPT adversaryAII with a nonnegligible advantage ε against the IND-CL-Basic-KI-GSC-CCA2-II security of the scheme running in encryption or signcryption mode in time t and performing at most qHiHi(i=0,1,2,…,6) queries, qU-C user-creation queries, qSec secret-value queries, qPe-p-k period-private-key queries, qGSC GSC queries, and qUn-GSC Un-GSC queries, then the CDH problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qSec·(1-1/qU-C)qPe-p-k·(qUn-GSC/2k) in time t′<t+(7·qGSC+8·qUn-GSC)·tm, where tm denotes the time for a scalar multiplication on G1.Proof.
Suppose challengerC is given (P,aP,bP)∈G13 for random a,b∈Zq∗. C does not know the values of a and b and is asked to compute abP.
Setup. Adversary AII randomly selects s∈Zq∗ as the master private key and computes the master public key as Ppub=sP. Other public parameters are produced normally. AII gives the system public parameters Params={p,q,E(Fp),G1,P,Ppub,f,H0,H1,H2,H3,H4,H5,H6} and master private key s to C. C maintains nine lists L0,L1,L2,L3,L4,L5,L6,Lk, and LPe-k, which are initially empty. C randomly selects λ∈{1,2,…,qU-C}.
Find Stage.
A
I
I makes queries to the following oracles adaptively: H0,H1,H2,H3,H4,H5,H6, public-key, user-period-private-key, GSC, and Un-GSC queries are the same as in Theorem 10. The partial-private-key and public-key-replacement queries are not needed for AII.
User-Creation Query.
A
I
I provides an identity ID. C looks up list Lk to determine whether it contains the item. If it does, C returns ID’s public key XID and public parameters (YID,TID) to AII. Otherwise, C proceeds as follows and returns public key XID and public parameters (YID,TID) to AII.
C randomly selects rID∈Zq∗ and computes YID=rID·P and yID=rID+s·H0(ID,YID)modq. C randomly selects hkID∈Zq∗ as the helper private key and computes TID=hkID·P.(1)
ID=IDλ. C sets the public key as XID=aP and inserts the tuple (IDλ,XIDλ,YIDλ,-,rIDλ,yIDλ,hkIDλ,TIDλ) into list Lk.(2)
ID≠IDλ. C randomly selects xID∈Zq∗ as the secret value and computes the public key as XID=xID·P. C inserts the tuple (ID,XID,YID,xID,rID,yID,hkID,TID) into list Lk.
Secret-Value Query.
A
I
I provides a created identity ID. (1)
ID≠IDλ. C retrieves xID from list Lk and returns it to AII(2)
ID=IDλ. C aborts.
Challenge Stage. The same as in Theorem 10.
Guess Stage.
A
I
I can make the same queries adaptively as in the Find stage with the restrictions given in Definition 2. Finally, AII must give his/her guess η′. AII cannot discover that σ∗ is not a valid ciphertext unless he/she asks the H6 oracle with the tuple (IDs∗,IDλ,UIDs∗,t∗,XIDs∗,YIDs∗,TIDs∗,R1∗,V∗,t∗), where V∗=a1∗·(YIDλ+Ppub·h0,IDλ+XIDλ·h2,IDλ+UIDλ,t∗·h3,IDλ,t∗+TIDλ·h1,IDλ,t∗) = abP·h2,IDλ+(rIDλ+s·h0,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗)·(bP). If this occurs, C retrieves rIDλ and hkIDλ from list Lk as well as uIDλ,t∗ and UIDλ,t∗ from list LPe-k. C makes associated hash oracles to obtain h0,IDλ, h1,IDλ,t∗, h2,IDλ, and h3,IDλ,t∗. Then, C can output abP=[V∗-(rIDλ+s·h0,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗)·bP]·(h2,IDλ)-1.
Now, we assess the probability of success. In the challenge stage, the probability thatIDr∗=IDλ is 1/qU-C. In both the secret-value and user-period-private-key queries, the probability of C querying IDλ is 1/qU-C. In the Un-GSC stage, the probability of C refusing the right ciphertext is less than qUn-GSC/2k.
In terms of the time complexity, GSC and Un-GSC queries need 7tm and 8tm computations, respectively.


## 6.2. Unforgeability of Basic Key Insulation

Theorem 12 (type I unforgeability).
In the random oracle model, if there is a PPT adversaryAI with a nonnegligible advantage ε against the EUF-CL-Basic-KI-GSC-CMA-I security of the scheme running in signature or signcryption mode in time t and performing at most qHiHi(i=0,1,2,…,6) queries, qU-C user-creation queries, qPa-p-k partial-private-key queries, qPe-p-k period-private-key queries, qGSC GSC queries, and qUn-GSC Un-GSC queries, then the EC-DL problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qPa-p-k·(1-1/qU-C)qPe-p-k·(qUn-GSC/2k)·(ε3/(qH0+qH4)6-3/2k) in time t′<t+(7·qGSC+8·qUn-GSC)·tm, where tm denotes the time for a scalar multiplication on G1.Proof.
Suppose that challengerC is given (P,aP)∈G12 for random a∈Zq∗. C does not know the value of a and is asked to compute a. To utilize adversary AI, challenger C will simulate all the oracles defined in Definition 3.
Setup. The same as in Theorem 10.
Queries. The same as in Theorem 10.
Forgery. Finally, AI outputs a forged GSC ciphertext σ∗=(R1∗,R2∗,c∗) in message m∗ in time period t∗ with IDs∗ as the sender and IDr∗ as the receiver. If IDs∗≠IDλ, C aborts. Otherwise, if σ∗ can pass the validation of the Un-GSC algorithm and AI does not violate the restrictions of Definition 3, according to the multiple-forking lemma [45], we can obtain four valid signatures: (IDλ,IDr∗,m∗,u∗(1),h0,IDλ(1),h4∗(1)),(IDλ,IDr∗,m∗,u∗(2), h0,IDλ(1),h4∗(2)),(IDλ,IDr∗,m∗,u∗(3),h0,IDλ(2),h4∗(3)), and (IDλ,IDr∗,m∗,u∗(4),h0,IDλ(2),h4∗(4)), where h0,IDλ(1) and h0,IDλ(2) are two different hash values corresponding to the H0 oracle and h4∗(1), h4∗(2), h4∗(3), and h4∗(4) are four different hash values corresponding to the H4 oracle. Because u∗=sIDλ,t∗·h4∗+a1∗·h5∗+a2∗modq, we can obtain four equations: (3)u∗1=rIDλ+a·h0,IDλ1+xIDλ·h2,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗·h4∗1+a1∗·h5∗+a2∗modq,u∗2=rIDλ+a·h0,IDλ1+xIDλ·h2,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗·h4∗2+a1∗·h5∗+a2∗modq,u∗3=rIDλ+a·h0,IDλ2+xIDλ·h2,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗·h4∗3+a1∗·h5∗+a2∗modq,u∗4=rIDλ+a·h0,IDλ2+xIDλ·h2,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗·h4∗4+a1∗·h5∗+a2∗modq.
Then,C can compute(4)u∗1-u∗2h4∗1-h4∗2-1=rIDλ+a·h0,IDλ1+xIDλ·h2,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗,u∗3-u∗4h4∗3-h4∗4-1=rIDλ+a·h0,IDλ2+xIDλ·h2,IDλ+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗,u∗1-u∗2h4∗1-h4∗2-1-u∗3-u∗4h4∗3-h4∗4-1·h0,IDλ1-h0,IDλ2-1=a.
Now, we assess the probability of success. In the Forgery stage, the probability ofIDs∗=IDλ is 1/qU-C. In both the partial-private-key and user-period-private-key queries, the probability of C querying with IDλ is 1/qU-C. In the Un-GSC stage, the probability of C refusing the right ciphertext is less than qUn-GSC/2k. In conjunction with the multiple-forking lemma, the EC-DL problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qPa-p-k·(1-1/qU-C)qPe-p-k·(qUn-GSC/2k)·(ε3/(qH0+qH4)6-3/2k).
In terms of the time complexity, GSC and Un-GSC queries need 7tm and 8tm computations, respectively.Theorem 13 (type II unforgeability).
In the random oracle model, if there is a PPT adversaryAII with a nonnegligible advantage ε against the EUF-CL-Basic-KI-GSC-CMA-II security of the scheme running in signature or signcryption mode in time t and performing at most qHiHi(i=0,1,2,…,6) queries, qU-C user-creation queries, qSec secret-value queries, qPe-p-k period-private-key queries, qGSC GSC queries, and qUn-GSC Un-GSC queries, then the EC-DL problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qSecret·(1-1/qU-C)qPe-p-k·(qUn-GSC/2k)·(ε3/(qH2+qH4)6-3/2k) in time t′<t+(7·qGSC+8·qUn-GSC)·tm, where tm denotes the time for a scalar multiplication on G1.Proof.
Suppose that challengerC is given (P,aP)∈G12 for random a∈Zq∗. C does not know the value of a and is asked to compute a. To utilize adversary AII, challenger C will simulate all the oracles defined in Definition 4.
Setup. The same as in Theorem 11.
Queries. The same as in Theorem 11.
Forgery. Finally, AII outputs a forged GSC ciphertext σ∗=(R1∗,R2∗,c∗) in message m∗ in time period t∗ with IDs∗ as the sender and IDr∗ as the receiver. If IDs∗≠IDλ, C aborts. Otherwise, if σ∗ can pass the validation of the Un-GSC algorithm and AII does not violate the restrictions of Definition 4, according to the multiple-forking lemma [45], we can obtain four valid signatures: (IDλ,IDr∗,m∗,u∗(1),h2,IDλ(1),h4∗(1)),(IDλ,IDr∗,m∗,u∗(2), h2,IDλ(1),h4∗(2)),(IDλ,IDr∗,m∗,u∗(3),h2,IDλ(2),h4∗(3)), and (IDλ,IDr∗,m∗,u∗(4),h2,IDλ(2),h4∗(4)), where h2,IDλ(1) and h2,IDλ(2) are two different hash values corresponding to the H2 oracle and h4∗(1), h4∗(2), h4∗(3), and h4∗(4) are four different hash values corresponding to the H4 oracle. Because u∗=sIDλ,t∗·h4∗+a1∗·h5∗+a2∗modq, we can obtain four equations: (5)u∗1=rIDλ+s·h0,IDλ+a·h2,IDλ1+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗·h4∗1+a1∗·h5∗+a2∗modq,u∗2=rIDλ+s·h0,IDλ+a·h2,IDλ1+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗·h4∗2+a1∗·h5∗+a2∗modq,u∗3=rIDλ+s·h0,IDλ+a·h2,IDλ2+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗·h4∗3+a1∗·h5∗+a2∗modq,u∗4=rIDλ+s·h0,IDλ+a·h2,IDλ2+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗·h4∗4+a1∗·h5∗+a2∗modq.
Then,C can compute (6)u∗1-u∗2h4∗1-h4∗2-1=rIDλ+s·h0,IDλ+a·h2,IDλ1+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗,u∗3-u∗4h4∗3-h4∗4-1=rIDλ+s·h0,IDλ+a·h2,IDλ2+uIDλ,t∗·h3,IDλ,t∗+hkIDλ·h1,IDλ,t∗,u∗1-u∗2h4∗1-h4∗2-1-u∗3-u∗4h4∗3-h4∗4-1·h2,IDλ1-h2,IDλ2-1=a.
Now, we assess the probability of success. In the Challenge stage, the probability ofIDs∗=IDλ is 1/qU-C. In both the secret-value and user-period-private-key queries, the probability of C querying IDλ is 1/qU-C. In the Un-GSC stage, the probability of C refusing the right ciphertext is less than qUn-GSC/2k. In conjunction with the multiple-forking lemma, the EC-GDL problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qSecret·(1-1/qU-C)qPe-p-k·(qUn-GSC/2k)·(ε3/(qH2+qH4)6-3/2k).
In terms of the time complexity, GSC and Un-GSC queries need 7tm and 8tm computations, respectively.


## 6.3. Confidentiality of Strong Key Insulation

Theorem 14 (type I confidentiality).
In the random oracle model, if there is a PPT adversaryAI with a nonnegligible advantage ε against the IND-CL-Strong-KI-GSC-CCA2-I security of the scheme running in encryption or signcryption mode in time t and performing at most qHiHi(i=0,1,2,…,6) queries, qU-C user-creation queries, qPa-p-k partial-private-key queries, qGSC GSC queries, and qUn-GSC Un-GSC queries, then the CDH problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qPa-p-k·(qUn-GSC/2k) in time t′<t+(7·qGSC+8·qUn-GSC)·tm, where tm denotes the time for a scalar multiplication on G1.Proof.
The proof is almost the same as that of Theorem10. The difference is that AI cannot make a user-period-private-key query but can adaptively ask the helper-key oracle. The GSC oracle is also slightly different.
Helper-Key Query.
A
I provides a created identity ID and a time period t. C returns the user’s helper key hkID and the ephemeral variable uID,t in time period t to AI.
GSC Query.
A
I provides two created identities {IDs,IDr} (one of them may be null), a message m, and a time period t. If IDs is null, it is equal to an encryption oracle, which needs only the public parameters. Otherwise, we consider two cases. (1)
IDs≠IDλ. C first checks list LPe-k to determine whether it contains the item (IDs,t,uIDs,t,UIDs,t,sIDs,t). If it does, C retrieves the period private key sIDs,t in time period t and runs the GSC algorithm as normal. Otherwise, C randomly chooses uIDs,t∈Zq∗ and computes UIDs,t=uIDs,t·P. C retrieves (XIDs,YIDs,TIDs) from list Lk. Then, C makes an H1 query with the tuple (IDs,YIDs,TIDs,t) and obtains a response h1,IDs,t. C makes an H2 query with the tuple (IDs,YIDs,XIDs,TIDs) and obtains a response h2,IDs. C makes an H3 query with the tuple (IDs,YIDs,UIDs,t,t) and obtains a response h3,IDs,t. C retrieves (xIDs,yIDs,hkIDs) from list Lk and computes the period private key SIDs,t in time period t as sIDs,t=yIDs+xIDs·h2,IDs+uIDs,t·h3,IDs,t+hkIDs·h1,IDs,tmodq. C inserts the tuple (IDs,t,uIDs,t,UIDs,t,sIDs,t) into list LPe-k and runs the GSC algorithm as normal.(2)
IDs=IDλ. It is the same as in Theorem 10.
Finally,C returns the GSC ciphertext σ=(R1,R2,c) and UIDs,t to AI.Theorem 15 (type II confidentiality).
In the random oracle model, if there is a PPT adversaryAII with a nonnegligible advantage ε against the IND-CL-Strong-KI-GSC-CCA2-II security of the scheme running in encryption or signcryption mode in time t and performing at most qHiHi(i=0,1,2,…,6) queries, qU-C user-creation queries, qSec secret-value queries, qGSC GSC queries, and qUn-GSC Un-GSC queries, then the CDH problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qSec·(qUn-GSC/2k) in time t′<t+(7·qGSC+8·qUn-GSC)·tm, where tm denotes the time for a scalar multiplication on G1.Proof.
The proof is almost the same as that of Theorem11. The difference is that AII cannot make a user-period-private-key query but can adaptively ask the helper-key oracle.
The user-creation query, secret-value query, public-key query, and Un-GSC queries are the same as in Theorem11.
The helper-key query and GSC query are the same as in Theorem14.


## 6.4. Unforgeability of Strong Key Insulation

Theorem 16 (type I unforgeability).
In the random oracle model, if there is a PPT adversaryAI with a nonnegligible advantage ε against the EUF-CL-Strong-KI-GSC-CMA-I security of the scheme running in signature or signcryption mode in time t and performing at most qHiHi(i=0,1,2,…,6) queries, qU-C user-creation queries, qPa-p-k partial-private-key queries, qGSC GSC queries, and qUn-GSC Un-GSC queries, then the EC-DL problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qPa-p-k·(qUn-GSC/2k)·(ε3/(qH0+qH4)6-3/2k) in time t′<t+(7·qGSC+8·qUn-GSC)·tm, where tm denotes the time for a scalar multiplication on G1.Proof.
The proof is almost the same as that of Theorem12. The difference is that AI cannot make a user-period-private-key query but can adaptively ask the helper-key oracle.
All the oracle queries are the same as in Theorem14.Theorem 17 (type II unforgeability).
In the random oracle model, if there is a PPT adversaryAII with a nonnegligible advantage ε against the EUF-CL-Strong-KI-GSC-CMA-II security of the scheme running in signature or signcryption mode in time t and performing at most qHiHi(i=0,1,2,…,6) queries, qU-C user-creation queries, qSec secret-value queries, qGSC GSC queries, and qUn-GSC Un-GSC queries, then the EC-DL problem can be solved with probability ε′≥ε·1/qU-C·(1-1/qU-C)qSecret·(qUn-GSC/2k)·(ε3/(qH2+qH4)6-3/2k) in time t′<t+(7·qGSC+8·qUn-GSC)·tm, where tm denotes the time for a scalar multiplication on G1.Proof.
The proof is almost the same as that of Theorem13. The difference is that AII cannot make a user-period-private-key query but can adaptively ask the helper-key oracle.
All the oracle queries are the same as in Theorem15.


## 6.5. Secure Key Update

Theorem 18.
Our certificateless key-insulated GSC scheme supports secure key update.Proof.
If an adversary compromises the user’s storage while a key is being updated from time periodt to t′, then he/she can obtain the user’s period private key sID,t in time period t and the update key ukID,t,t′ from t to t′. Then, he/she can compute the user’s period private key sID,t′=sID,t+ukID,t,t′ in time period t′. The adversary cannot obtain any other useful information except sID,t, ukID,t,t′, and sID,t′. In addition, from the equation sID,t=yID+xID·h2,ID+uID,t·h3,ID,t+hkID·h1,ID,tmodq, he/she cannot derive any private information because the number of unknown variables is greater than the number of equations. Furthermore, he/she cannot derive any private information from the equation ukID,t,t′=uID,t′·h3,ID,t′-uID,t·h3,ID,t+hkID·(h1,ID,t′-h1,ID,t)modq either.


## 7. Efficiency Comparison of the Proposed Scheme

Because a certificateless key-insulated signcryption scheme has yet to be proposed and because only five key-insulated signcryption schemes have been reported in the literature, we compare the performance of our scheme in signcryption mode with these schemes. These five schemes are Chen et al.’s identity-based key-insulated signcryption scheme [33], Fan et al.’s PKI-based key-insulated signcryption scheme [34], Wang et al.’s identity-based key-insulated signcryption scheme [35], Zhu et al.’s identity-based key-insulated signcryption scheme [38], and Hong and Sun’s attribute-based key-insulated signcryption scheme [43]. Their common computations are set-initial-key, key-update-h, key-update-u, signcryption, and un-signcryption. The comparisons are presented in Tables 1 and 2. The symbols p, m1, m2, and e denote a pairing computation, a pairing-based scalar multiplication computation on G1, an ECC-based scalar multiplication computation on G1, and an exponentiation computation on G2, respectively. Other computations are ignored because they are not time consuming. |G1|, |G2|, |q|, |m|, and |ID| represent the bit length of an element on G1, G2, and zq∗, a message m, and an identity, respectively. “S” denotes the standard model. “ROM” denotes the random oracle model. S-I-K, K-U-H, K-U-U, Sc, and Un-Sc denote set-initial-key, key-update-h, key-update-u, signcryption, and un-signcryption, respectively.Table 1
Comparison of computational costs.
Schemes
S-I-K
K-U-H
K-U-U
Sc
Un-Sc
Model
Technology
[33]
4m1
3m1
0
6
m
1
+
e
7
p
S
Identity-based
[34]
5m1
4m1
0
p
+
5
m
1
+
e
6
p
+
2
m
1
S
PKI-based
[35]
m
1
m
1
0
p
+
2
m
1
+
e
5
p
+
6
m
1
ROM
Identity-based
[38]
4m1
3m1
0
6
m
1
+
e
7
p
S
Identity-based
[43]
0
0
0
(
4
n
+
4
)
m
2
(4n+4)m2
ROM
Attribute-based
Ours
m
2
m
2
0
7m2
8m2
ROM
Certificateless
Note.  n represents the number of attributes.Table 2
Comparison of communication overheads.
Schemes
Ciphertext size
[33]
6
|
G
1
|
+
|
G
2
|
[34]
4
|
G
1
|
+
|
G
2
|
+
|
q
|
[35]
2
|
G
1
|
+
|
G
2
|
+
|
q
|
[38]
6
|
G
1
|
+
|
G
2
|
[43]
5
|
G
1
|
+
2
|
q
|
+
|
m
|
Ours
2
|
G
1
|
+
|
q
|
+
|
m
|To show the comparisons more directly, we use the Multiprecision Integer and Rational Arithmetic C Library (MIRACL) [46] to test the runtime of the basic cryptographic operations. The average runtime is shown in Table 3 (we tested it 1000 times). The experiment was run on a Windows 7 Home Basic 64-bit operating system. The hardware consisted of an Intel Core i7-4510U CPU running at 2.0 GHz with 8 GB of memory. For pairing-based schemes, we use the supersingular elliptic curve E/Fp:y2=x3-3x with an embedding degree of 2, where q is a 160-bit Solinas prime q=2159+217+1 and p is a 512-bit prime satisfying p+1=2qh. Its security level is equivalent to 80-bit Advanced Encryption Standard (AES). To achieve the same security level, for elliptic curve cryptography- (ECC-) based schemes, we use secp160r1, which is recommended by Certicom Corporation [47].Table 3
Computational costs (milliseconds).
p
m
1
m
2
e
14.90
4.31
0.97
1.25When we take the above parameters, for pairing-based schemes,|G1|=|G2|=1024 and |q|=160; for ECC-based schemes, |G1|=320 and |q|=160. Let |m|=160. We can obtain Table 4 by combining Tables 1, 2, and 3.Table 4
Comparison of performances (n=2).
Schemes
S-I-K
K-U-H
K-U-U
Sc
Un-Sc
Ciphertext
[33]
17.24
12.93
0
27.11
104.30
7168
[34]
21.55
17.24
0
37.70
98.02
5280
[35]
4.31
4.31
0
24.77
100.36
3232
[38]
17.24
12.93
0
27.11
104.30
7168
[43]
0
0
0
11.64
11.64
2080
Ours
0.97
0.97
0
6.79
7.76
960From Table4, we can see that scheme [43] is the most efficient one in the S-I-K and K-U-H stages. Our scheme is very similar to scheme [43] and outperforms other schemes. In the Sc and Un-Sc stages, our scheme is the most efficient scheme. Scheme [43] is very similar to our scheme, whereas other schemes are much less efficient than our scheme. In terms of ciphertext size, our scheme is the shortest.We also compared our scheme with two certificateless GSC schemes. These schemes are Zhou et al.’s scheme [13] and Zhang et al.’s scheme [20]. The comparisons are shown in Table 5. Let |ID|=160, and we can obtain Table 6 by combining Tables 3 and 5.Table 5
Comparison of performances.
Schemes
Sc
Un-Sc
Model
Ciphertext size
[13]
4
m
1
+
e
4
p
+
m
1
ROM
2
G
1
+
m
[20]
4
m
2
5
m
2
ROM
G
1
+
2
q
+
m
Ours
7
m
2
8
m
2
ROM
2
G
1
+
q
+
mTable 6
Comparison of performances.
Schemes
Sc
Un-Sc
Model
Ciphertext size
[13]
18.49
63.91
ROM
2208
[20]
3.88
4.85
ROM
800
Ours
6.79
7.76
ROM
960From Table6, we can see that scheme [20] is the most efficient scheme in terms of Sc, Un-Sc, and ciphertext size. Scheme [20] is a lightweight scheme and achieves the greatest efficiency. Our scheme is very similar to this scheme and outperforms scheme [13]. None of the schemes [13, 20] consider the private key exposure problem, whereas our scheme achieves high efficiency even after considering this problem.In general, the efficiency of our scheme is very similar to those of the lightweight schemes [20, 43]; therefore, our scheme is more suitable for users who communicate with the cloud using mobile devices.


## 8. Conclusions

In this paper, we propose a certificateless key-insulated GSC scheme without bilinear pairings. Our scheme can be used to ensure cloud storage security. We provide a formal definition and security model of certificateless key-insulated GSC. Our scheme is demonstrated to be confidential under the CDH assumption and unforgeable under the EC-DL assumption, and it supports both random-access key update and secure key update. Efficiency evaluations show that our scheme is efficient compared with current key-insulated signcryption schemes and certificateless GSC schemes. Our future work will include designing highly efficient intrusion-resilient GSC schemes.



---

*Source: 8405879-2017-08-02.xml*