A Strongly Unforgeable Certificateless Signature Scheme and Its Application in IoT Environments

Abstract

With the widespread application of the Internet of Things (IoT), ensuring communication security for IoT devices is of considerable importance. Since IoT data are vulnerable to eavesdropping, tampering, forgery, and other attacks during an open network transmission, the integrity and authenticity of data are fundamental security requirements in the IoT. A certificateless signature (CLS) is a viable solution for providing data integrity, data authenticity, and identity identification in resource-constrained IoT devices. Therefore, designing a secure and efficient CLS scheme for IoT environments has become one of the main objectives of IoT security research. However, the existing CLS schemes rarely focus on strong unforgeability and replay attacks. Herein, we design a novel CLS scheme to protect the integrity and authenticity of IoT data. In addition to satisfying the strong unforgeability requirement, the proposed scheme also resists public key replacement attacks, malicious-but-passive key-generation-centre attacks, and replay attacks. Compared with other related CLS schemes without random oracles, our CLS scheme has a shorter private key, stronger security, and lower communication and computational costs.

1. Introduction

The Internet of Things (IoT) is a self-establishing network of smart devices that are equipped with electronics, sensors, software, and actuators and that are connected via the Internet to generate, collect, and exchange data [1]. Since IoT devices connect objects in different environments to the Internet for information exchange and communication to realize intelligent identification, location, tracking, monitoring, management, and other functions, IoT devices have the ability to support a wide range of services. Consequently, the IoT builds a network that covers various things throughout the world via numerous IoT devices, and it enables various human-to-human, human-to-thing, thing-to-thing, and thing-to-thing interactions. Figure 1 shows a variety of IoT applications, including intelligent transportation, military target tracking, surveillance, public safety, smart home, industrial monitoring, smart city, medical equipment, and food traceability [2]. The application of the IoT involves all economic and social aspects of daily life and fundamentally changes the way in which humans interact with the world around them. Hence, the IoT is considered to be an information technology revolution and has become a growth point for the global economy [3].

Various IoT-enabled devices with embedded sensors collect and send IoT data to data centres over public networks; thus, the issues of security and privacy in IoT environments have become increasingly important [4,5]. Only authentic data can be stored in data centres, which requires the integrity and authenticity of the data transmitted by an IoT device to be checked before being stored. The signature-based cryptosystem is technology that provides the integrity, real source, unforgeability, and non-repudiation of the data. An IoT device signs the data using its private key during data transmission, and the data centre confirms the data authenticity and integrity by verifying the validity of the received signature. Therefore, a digital signature scheme can ensure data integrity and data authenticity in the IoT. However, the IoT differs from traditional networks. Most IoT devices have limited computational and processing capabilities, short communication ranges, and restricted storage and power resources. Conventional cryptosystems cannot run on resource-constrained IoT devices. The main reason is that conventional cryptosystems are classified into two categories: PKI-based and ID-based cryptosystems. Traditional PKI-based cryptosystems require certificates to authenticate users’ public keys, which results in a large amount of computational overhead and communication costs to manage and exchange certificates. The identity-based cryptosystem avoids the use of certificates, but there are security flaws in key escrow that make it unsuitable for large-scale network environments. Hence, designing an efficient, secure signature scheme is very important for IoT security.

In a signature scheme, the private key of the signer is used to sign the message, and the validity of the corresponding signature is verified by the signer’s public key. The signature’s validity not only ensures that the signer with the private key can apply a valid signature to the message but also ensures the authenticity and integrity of the message. The user’s public key is generally a random string; thus, authenticating the authenticity of the user’s public key is particularly crucial. In traditional public key infrastructure (PKI) settings, a certificate issued by a fully trusted authority associates the user’s public key with the user’s real identity. The authenticity of the user’s public key can be verified by the legality of the corresponding certificate. However, the storage, distribution, verification, and revocation of certificates in PKI are resource-intensive and computationally expensive tasks [6]. Hence, PKI is unsuitable for resource-constrained IoT environments.

Shamir [7] proposed identity-based cryptography (IBC) to solve the complex certificate management problems in PKI. IBC allows a key generation centre (KGC) to produce the user’s private key, but the corresponding user’s public key comes from their public identity information, such as an e-mail address or mobile phone number. However, KGC can replace the user to decrypt any ciphertext or to forge the signature of any message without being found, which results in the key escrow problem.

The concept of certificateless signature (CLS) was introduced by Al-Riyami and Paterson [8]. In a CLS scheme, the user’s private key consists of two parts: One is a partial private key generated by the KGC, and the other is a secret value calculated independently by the user. The CLS scheme solves the key escrow problem because the KGC is unable to obtain the user’s final private key. In addition, the user generates the corresponding public key based on its secret value, but it is not necessary to verify the authenticity of the public key by using the certificate. In practical applications, the user’s public key is sent to the recipient together with the signature or is obtained from a public directory in a proper manner.

Certificateless signatures have received considerable attention in recent years, and researchers have designed numerous CLS schemes [9,10,11,12]. Most existing CLS schemes [13,14,15] have been proven to be secure in the random oracle model [16], where a cryptographic hash function is modelled as an ideal random oracle. The random oracle paradigm helps construct efficient cryptographic schemes, but it has received substantial criticism. It has been shown that, when random oracles are instantiated with actual hash functions, the cryptographic scheme that proves to be secure using the random oracle model may be unsafe in reality [17]. To overcome this security flaw, Liu et al. [18] designed the first CLS scheme without random oracles. Later, several CLS schemes [19,20,21,22] in the standard model were proposed, but these schemes cannot resist public key replacement (PKR) attacks or malicious-but-passive KGC (MKGC) attacks. In addition, most existing CLS schemes [23,24,25] without random oracles are proven to be existentially unforgeable against adaptive chosen-message attacks. This security notion only ensures that an attacker cannot forge the signature of any new message; it does not guarantee that the attacker generates the valid signature for the signed message. However, some signature schemes are malleable [26]; thus, an attacker can generate multiple valid signatures of the same message by using the previous message–signature pair without the signer’s private key. In other words, these schemes do not satisfy strong unforgeability, which is a stronger security notion than existential unforgeability. Strong unforgeability is desirable in some applications [27,28,29] (such as electronic commerce, construction of certificateless signcryption schemes, and certificateless group signature schemes). If a CLS signature scheme satisfies existential unforgeability and can prevent an attacker from forging a valid signature of a previously signed message, then we say that the CLS scheme is strongly unforgeable. Strong unforgeability is an important property of the CLS scheme, but few CLS schemes [30] satisfy strong unforgeability in the standard model. Unfortunately, none of those strongly unforgeable CLS schemes considers replay attacks [31,32]. Note that the energy of the IoT device is one of the main factors that restricts improvements in network performance. However, replay attacks, which are considered to be one of the major attacks faced by IoT devices, can consume a large amount of node energy. Therefore, a CLS scheme that is applicable to IoT environments must consider replay attacks.

In this paper, motivated by the above concerns, we present a new CLS scheme for IoT environments that is more secure and efficient than the previous CLS schemes. As a potential signature-based authentication technology, our proposed scheme manifests a solution to the problems of data authenticity and data integrity in the IoT. The main contributions of this paper are the following.

• A novel CLS scheme without random oracles is constructed. Under the collision-resistant hash function (CRHF) and computational Diffie–Hellman (CDH) assumptions, the proposed CLS scheme is proven to be strongly unforgeable against adaptive chosen-message attacks in the standard model.
• In our CLS scheme, the user’s public key is not only bound to the user’s partial private key but also embedded into the signature of the message. This makes the proposed CLS scheme have a higher security trust level and be capable of resisting PKR attacks and MKGC attacks.
• The proposed CLS scheme resists replay attacks by verifying the freshness of the timestamp and the validity of the signature. To our best knowledge, our scheme is the first CLS scheme with a strong unforgeability in the standard model that can resist replay attacks.
• Compared to other CLS schemes in the standard model, our CLS scheme has higher security, a smaller key size, a shorter signature length, and lower computational overhead for signature generation and signature verification.
• Due to the aforementioned functionalities, our CLS scheme is able to be implemented and deployed in IoT environments where IoT devices have limited computing power, storage space, and communication bandwidth.

The remainder of this paper is organized as follows. We present the relevant CLS works in Section 2. Then, we introduce some preliminaries and security notions of the CLS scheme in Section 3. The proposed CLS scheme and its security proof are presented in Section 4 and Section 5. Section 6 gives the CLS system model for IoT environments and performance analysis. Section 7 concludes this paper.

2. Related Work

The first CLS scheme was proposed by Al-Riyami and Paterson [8]. Later, Huang et al. [33] noted that their CLS scheme [8] was unable to resist PKR attacks and proposed security notions for CLS schemes. Since then, researchers have constructed a large number of provably secure CLS schemes [9,10,11,12,13,14,15] in the random oracle model. Aiming to eliminate the security requirements of ideal random oracles, Liu et al. [18] constructed a CLS scheme without random oracles based on the identity-based signature scheme proposed by Paterson and Schuldt [34]. However, Xiong et al. [19] and Huang et al. [35] demonstrated that Liu et al.’s CLS scheme [18] was insecure against MKGC attacks. To enhance the security of Liu et al.’s CLS scheme [18], Xiong et al. [19] presented an improved scheme, but it was still vulnerable to MKGC attacks [36]. Furthermore, Xia et al. [37] showed that several CLS schemes [18,19,20] without random oracles were susceptible to PKR attacks.

Subsequently, Yu et al. [21] designed a CLS scheme and claimed that their scheme was secure in the standard model. However, Yuan et al. [23] and Pang et al. [27] independently demonstrated that Yu et al.’s CLS scheme [21] was insecure against PKR or MKGC attacks. As a countermeasure, Yuan et al. [23] designed an enhanced scheme, but it did not satisfy strong unforgeability. Based on the Boneh–Boyen signature [38] and Pointcheval–Sanders signature [39], Canard and Trinh [25] constructed a CLS scheme with a low computational cost. However, Canard and Trinh’s CLS scheme [25] was existentially unforgeable in the standard model. Subsequently, Huang et al. [22] constructed a CLS scheme with strong unforgeability in the standard model. Unfortunately, Yang et al. [30] demonstrated that Huang et al.’s CLS scheme [22] failed to achieve a strong unforgeability and was vulnerable to MKGC attacks. Furthermore, Yang et al. [30] presented a secure CLS scheme, but their scheme still has some drawbacks, including a longer private key size and a higher computational overhead than those of the previous schemes.

Digital signatures are widely used to ensure data authenticity and integrity. Yeh et al. [4] devised a CLS scheme for IoT environments. However, Jia et al. [40] demonstrated that Yeh et al.’s scheme [4] was insecure against PKR attacks and then proposed a new CLS scheme to overcome the flaws of Yeh et al.’s scheme [4]. Based on technologies such as RSA, DSA, and Merkle tree, Li et al. [41] proposed an IoT data communication framework to provide integrity and authenticity. Frädrich et al. [42] used redactable signature [43] to design another framework for the IoT environment to allow the redaction of parts from signed data and proved its security in the random oracle model. To achieve the security requirements in IoT, Challa et al. [44] presented a new signature-based authenticated key establishment scheme for the IoT environment. Based on Nyberg’s fast one-way accumulator [45], Yao et al. [46] designed a lightweight multicast authentication mechanism for small scale IoT applications. Yang et al. [47] proposed a certificateless aggregate signature scheme for vehicular ad hoc networks to reduce transmission bandwidth and verification overhead of signatures. To protect the identity privacy of IoT devices, Yang et al. [48] constructed a strong designated-verifier proxy re-signature (SDVPRS) scheme in the standard model and applied it to the IoT environment. Unfortunately, the existing data integrity and authenticity schemes in IoT have two drawbacks. (1) Some schemes [41,42,44,46,47,48] require heavy management and communication overheads of certificates to achieve authenticity authentication of the user’s public key. (2) Most of the schemes [4,40,41,42,44,46,47] are proved to be secure in the random oracle model. To fill thess gaps, Karati et al. [3] presented a secure CLS scheme for IoT environments in the standard model, but their scheme did not consider a strong unforgeability and replay attacks. To our best knowledge, designing an efficient CLS scheme that both satisfies strong unforgeability in the standard model and is resistant to PKR attacks, MKGC attacks, and replay attacks remains an open issue. Therefore, in this paper, we advance such a construction for IoT environments to ensure data integrity and data authenticity.

3. Preliminaries

Here, we briefly review some preliminary knowledge, including the definition of bilinear pairings, the complexity assumptions, and the security model of the CLS schemes.

3.1. Bilinear Paring

Assume that $G_1$ and $G_2$ are cyclic groups with the same order of prime p and that g is any generator of $G_1$. A bilinear pair $e:G_1\times G_1\to G_2$ is a map that satisfies the following conditions [23]:

• Bilinearity: $e(g^a,g^b)=e{(g,g)}^{ab}$ for all $a,b\in Z_p$.
• Nondegeneracy: $e(g,g)\ne 1$.
• Computability: There is an algorithm that can efficiently calculate $e(g^a,g^b)$ for any $a,b\in Z_p$.

3.2. Complexity Assumptions

Given two elements $g,h\in G_1$, the discrete logarithm (DL) problem [30] is to find an integer $a\in Z_p$ such that $h=g^a$.

Let $\mathcal{A}$ denote an attacker with probabilistic polynomial time (PPT). The advantage $\epsilon$ of $\mathcal{A}$ to solve the DL problem in $G_1$ is defined as

$$Ad{v}_{\mathcal{A}}^{DL}=\mathrm{Pr}[\mathcal{A}(g,h)=a:a\in Z_p]\ge \epsilon .$$

Definition 1 (DL assumption).

We say that the DL assumption holds in $G_1$ if there is no PPT attacker $\mathcal{A}$ to solve the DL problem with a non-negligible advantage ε.

Given three elements, $g,g^a,and{g}^b\in G_1$ for unknown, randomly chosen $a,b\in Z_p$, the computational Diffie–Hellman (CDH) problem [22] is to calculate $g^{ab}\in G_1$.

The advantage $\epsilon$ that any PPT adversary $\mathcal{A}$ can solve the CDH problem in $G_1$ is defined as

$$Ad{v}_{\mathcal{A}}^{CDH}=\mathrm{Pr}[\mathcal{A}(g,g^a,g^b)=g^{ab}:a,b\in Z_p]\ge \epsilon .$$

Definition 2 (CDH assumption).

The CDH assumption holds in $G_1$ if there is no PPT attacker $\mathcal{A}$ to solve the CDH problem with a non-negligible advantage ε.

Suppose that $\left\{H_k\right\}$ represents a family of hash functions $H_k:{\{0,1\}}^{\ast }\to {\{0,1\}}^n$, where n is the length of the output value of $H_k$ and k is an index. Given the index k, the collision resistance of hash function (CRHF) [30] $H_k$ is to find $m_0\ne m_1$ such that $H_k\left(m_0\right)=H_k\left(m_1\right)$. The advantage $\epsilon$ of any PPT adversary $\mathcal{A}$ in breaking the collision resistance of $H_k$ is defined as

$$\begin{array}{cc}\hfill Ad{v}_{\mathcal{A}}^{CRHF}=\mathrm{Pr}& [\mathcal{A}\left(k\right)=(m_0,m_1):m_0\ne m_1,H_k\left(m_0\right)=H_k\left(m_1\right)]\ge \epsilon .\hfill \end{array}$$

Definition 3 (CRHF assumption).

A hash family $\left\{H_k\right\}$ is collision resistant if the advantage ε of any PPT adversary $\mathcal{A}$ to break the collision resistance of hash function $H_k$ is negligible.

3.3. Security Model of CLS

A CLS scheme consists of six algorithms, as follows:

• $\mathbf{Setup}$: This algorithm takes as input a security parameter $\lambda$, and it outputs the master secret key $msk$ and system parameters $param$.
• $\mathbf{SetPubKey}$: This algorithm takes as input $param$ and an identity $ID$, and it outputs a secret value $us{k}_{ID}$ and a public key $p{k}_{ID}$.
• $\mathbf{PSKExtract}$: This algorithm takes as input $param$, $ID$, and $p{k}_{ID}$, and it returns a partial private key $ps{k}_{ID}$ for identity $ID$.
• $\mathbf{SetSecKey}$: Upon receiving $param$, $us{k}_{ID}$, and $ps{k}_{ID}$, this algorithm outputs a private key $s{k}_{ID}$.
• $\mathbf{Sign}$: This algorithm takes as input $param$, an identity $ID$’s private key $s{k}_{ID}$ and public key $p{k}_{ID}$, a timestamp T, and a message m, and it returns a signature $\sigma$ on m.
• $\mathbf{Verify}$: Upon receiving $param$, $ID$, $p{k}_{ID}$, T, m, and $\sigma$, this algorithm outputs 1 if $\sigma$ is a valid signature of $ID$ on m with respect to T and $p{k}_{ID}$, and it outputs 0 otherwise.

According to the security model for CLS presented in References [15,35], a CLS scheme’s security should consider two types of adversaries: type I and type II adversaries. A type I adversary is a PKR attacker who knows the secret value of the targeted entity and who can replace any entity’s public key with its own. A type I adversary models an outside attacker who is not capable of possessing the master secret key of the KGC. In contrast, a type II adversary models an honest-but-curious KGC attacker who holds the master secret key of the KGC and generates the partial private key of any entity. However, a type II adversary can neither perform the entity’s PKR nor obtain the secret value of the targeted entity. To meet more realistic security requirements, Au et al. [49] presented an enhanced security model in which a type II adversary is viewed as an MKGC attacker. In this case, a malicious KGC can access the master secret key of the KGC and may embed extra trapdoors in the system parameters and the master secret key during the initialization phase of the system. Hence, the type II adversary that we focus on is an MKGC attacker. Here, the security model for a strongly secure CLS scheme is formalized via the following games (denoted Games 1 and 2) between a challenger $\mathcal{C}$ and an adversary $\mathcal{A}\in \{{\mathcal{A}}_1,{\mathcal{A}}_2\}$.

Game 1: Executed between a challenger $\mathcal{C}$ and a type I adversary ${\mathcal{A}}_1$.

• Initialization: $\mathcal{C}$ first runs the algorithm $\mathbf{Setup}$ to obtain the master secret key $msk$ and system parameters $param$. $\mathcal{C}$ then runs the algorithm $\mathbf{SetPubKey}$ to output the secret value $us{k}^{\ast }$ and corresponding public key $p{k}^{\ast }$ of the targeted entity. Finally, $\mathcal{C}$ sends $param$ and $(us{k}^{\ast },p{k}^{\ast })$ to ${\mathcal{A}}_1$ while keeping $msk$ secret.
• Queries: ${\mathcal{A}}_1$ can adaptively access the following oracles with $\mathcal{C}$.

  –

  Public Key Query${\mathcal{O}}_{pk}\left(I{D}_i\right)$: Upon receiving an identity $I{D}_i$, $\mathcal{C}$ runs the algorithm $\mathbf{SetPubKey}$ to obtain a public key $p{k}_i$ and sends it to ${\mathcal{A}}_1$.

  –

  Public Key Replacement (PKR) Query${\mathcal{O}}_{rep}(I{D}_i,p{k}_i^{{}^{\prime }})$: Upon receiving such a query, $\mathcal{C}$ finds and replaces the original public key $p{k}_i$ of identity $I{D}_i$ with a new public key $p{k}_i^{{}^{\prime }}$.

  –

  Partial Private Key Query${\mathcal{O}}_{psk}(I{D}_i,p{k}_i)$: Upon receiving an identity $I{D}_i$ and a public key $p{k}_i$, $\mathcal{C}$ runs the algorithm $\mathbf{PSKExtract}$ to generate a partial private key $ps{k}_i$ and sends it to ${\mathcal{A}}_1$.

  –

  Private Key Query${\mathcal{O}}_{sk}\left(I{D}_i\right)$: When ${\mathcal{A}}_1$ initiates a private key inquiry about an identity $I{D}_i$, $\mathcal{C}$ executes the algorithm $\mathbf{SetSecKey}$ to produce a private key $s{k}_i$ and sends it to ${\mathcal{A}}_1$. Note that $\mathcal{C}$ returns the symbol ⊥ if $I{D}_i$ has already appeared in PKR queries.

  –

  Signing Query${\mathcal{O}}_{sign}(I{D}_i,T,m)$: Upon receiving an identity $I{D}_i$, a timestamp Tm and a message m, $\mathcal{C}$ first executes the algorithm $\mathbf{SetSecKey}$ to produce a private key $s{k}_i$ and then uses $s{k}_i$, T, and the identity $I{D}_i$’s matching public key $p{k}_i$ to execute the algorithm $\mathbf{Sign}$ to produce a signature ${\sigma }_i$ on m. Finally, $\mathcal{C}$ sends ${\sigma }_i$ to ${\mathcal{A}}_1$.

• Forgery: ${\mathcal{A}}_1$ eventually outputs a forged signature ${\sigma }^{\ast }$ on a message $m^{\ast }$ corresponding to an identity $I{D}^{\ast }$, a timestamp $T^{\ast }$, and the targeted public key $p{k}^{\ast }$. It is said that ${\mathcal{A}}_1$ wins this game when the following conditions are fulfilled:

  (1)

  $\mathbf{Verify}(param,I{D}^{\ast },p{k}^{\ast },T^{\ast },m^{\ast },{\sigma }^{\ast })=1$.

  (2)

  $I{D}^{\ast }$ is not requested in ${\mathcal{O}}_{psk}(I{D}_i,p{k}_i)$ and ${\mathcal{O}}_{sk}\left(I{D}_i\right)$.

  (3)

  $(I{D}^{\ast },T^{\ast },m^{\ast },{\sigma }^{\ast })$ is not an output of the oracle ${\mathcal{O}}_{sign}(I{D}_i,T,m)$.

Game 2: Executed between a challenger $\mathcal{C}$ and a type II adversary ${\mathcal{A}}_2$. To launch malicious attacks more easily, ${\mathcal{A}}_2$ is allowed to set some trapdoors during the initialization phase of the game.

• Initialization: $\mathcal{C}$ invokes ${\mathcal{A}}_2$ to produce the master secret key $msk$ and system parameters $param$. Then, $\mathcal{C}$ runs the algorithm $\mathbf{SetPubKey}$ to produce the secret value $us{k}^{\ast }$ and the corresponding public key $p{k}^{\ast }$ of the targeted entity. Finally, $\mathcal{C}$ sends $p{k}^{\ast }$ to ${\mathcal{A}}_2$ while keeping $us{k}^{\ast }$ secret.
• Queries: ${\mathcal{A}}_2$ can adaptively access the oracles ${\mathcal{O}}_{pk}\left(I{D}_i\right)$, ${\mathcal{O}}_{sk}\left(I{D}_i\right)$, and ${\mathcal{O}}_{sign}(I{D}_i,T,m)$, which are defined in Game 1, and $\mathcal{C}$ responds in the same way as it does in Game 1.
• Forgery: ${\mathcal{A}}_2$ eventually outputs a forged signature ${\sigma }^{\ast }$ on a message $m^{\ast }$ corresponding to an identity $I{D}^{\ast }$, a timestamp $T^{\ast }$, and the targeted public key $p{k}^{\ast }$. It is said that ${\mathcal{A}}_2$ wins this game when the following conditions are fulfilled:

  (1)

  $\mathbf{Verify}(param,I{D}^{\ast },p{k}^{\ast },T^{\ast },m^{\ast },{\sigma }^{\ast })=1$.

  (2)

  $I{D}^{\ast }$ is not requested in ${\mathcal{O}}_{sk}\left(I{D}_i\right)$.

  (3)

  $(I{D}^{\ast },T^{\ast },m^{\ast },{\sigma }^{\ast })$ is not an output of the oracle ${\mathcal{O}}_{sign}(I{D}_i,T,m)$.

$Ad{v}_{{\mathcal{A}}_i}^{SUF}=\mathrm{Pr}\left[{\mathcal{A}}_{i}succeeds\right]$ denotes the advantage that ${\mathcal{A}}_i$ wins the above games, where $i\in \{1,2\}$.

Definition 4.

A CLS scheme is said to be strongly unforgeable against adaptive chosen message attacks if the advantages $Ad{v}_{{\mathcal{A}}_1}^{SUF}$ and $Ad{v}_{{\mathcal{A}}_2}^{SUF}$ are negligible for all PPT type I adversaries ${\mathcal{A}}_1$ and type II adversaries ${\mathcal{A}}_2$.

4. Proposed CLS Scheme

Based on Waters’ scheme [26] and its variants [28,34], we propose an undeniable and strongly unforgeable CLS scheme in the standard model. Our CLS scheme is described as follows.

• $\mathbf{Setup}$: Upon giving the security parameter $\lambda$ as input, the KGC produces the master secret key and system parameters by performing the following steps.

  (1)

  Select $G_1$ and $G_2$ as two cyclic groups with prime order p, a generator g of $G_1$, and a bilinear pairing $e:G_1\times G_1\to G_2$.

  (2)

  Select two random values $\alpha ,\beta \in Z_p^{\ast }$ and compute $g_1=g^{\alpha }$ and $g_2=g^{\beta }$.

  (3)

  Select two random elements $u_0,v_0\in G_1$ and two vectors $\overrightarrow{u}=\left(u_i\right)$ and $\overrightarrow{v}=\left(v_j\right)$ of lengths $n_u$ and $n_m$, respectively, where $u_i,v_j\in G_1$ for $i=1,\dots ,n_u$ and $j=1,\dots ,n_m$.

  (4)

  Select three collision-resistant hash functions $H_1:{\{0,1\}}^{\ast }\to {\{0,1\}}^{n_u}$, $H_2:{\{0,1\}}^{\ast }\to {\{0,1\}}^{n_m}$, and $H_3:{\{0,1\}}^{\ast }\to Z_p^{\ast }$.

  (5)

  Secretly keep the master key $msk=g^{\alpha \beta }$ and publicly broadcast the system parameters $param=\{G_1,G_2,p,g$, $e,g_1,g_2,u_0,v_0,\overrightarrow{u},\overrightarrow{v},H_1,H_2,H_3\}$.

• $\mathbf{SetPubKey}$: An entity with identity $ID$ randomly selects ${\theta }_1,{\theta }_2,{\theta }_3\in Z_p^{\ast }$ and computes

  $$p{k}_{ID,1}=g^{{\theta }_1},p{k}_{ID,2}=g^{{\theta }_2}\mathrm{and}p{k}_{ID,3}=g^{{\theta }_3}.$$
  Then, the entity computes $us{k}_{ID}=g^{{\theta }_1{\theta }_2}$ as its secret value and sets its public key $p{k}_{ID}=(p{k}_{ID,1},p{k}_{ID,2},p{k}_{ID,3})$.
• $\mathbf{PSKExtract}$: Given an identity $ID$ and a public key $p{k}_{ID}$ of an entity, the KGC first computes a vector $\overrightarrow{Q}=H_1(ID,p{k}_{ID})=(Q_1,\dots ,Q_{n_u})\in {\{0,1\}}^{n_u}$ and $U_{ID}=u_0{\displaystyle \prod _{i=1}^{n_u}}{u}_i^{Q_i}$. Then, the KGC selects $s\in Z_p^{\ast }$ at random and computes

  $$ps{k}_{ID,1}=g^{\alpha \beta }{\left(U_{ID}\right)}^s\mathrm{and}ps{k}_{ID,2}=g^s.$$
  Finally, the KGC sends the partial private key $ps{k}_{ID}=(ps{k}_{ID,1},ps{k}_{ID,2})$ to the entity via a secure channel.
  After receiving $ps{k}_{ID}=(ps{k}_{ID,1},ps{k}_{ID,2})$ from the KGC, the entity can check the correctness of $ps{k}_{ID}$ by verifying

  $$e(ps{k}_{ID,1},g)=e(g_2,g_1)e(U_{ID},ps{k}_{ID,2}).$$
  If this equation holds, then the entity accepts $ps{k}_{ID}$ as a valid partial private key.
• $\mathbf{SetSecKey}$: The entity with identity $ID$ selects a random value $r\in Z_p^{\ast }$ and computes a vector $\overrightarrow{Q}=H_1(ID,p{k}_{ID})=(Q_1,\dots ,Q_{n_u})\in {\{0,1\}}^{n_u}$ and $U_{ID}=u_0{\displaystyle \prod _{i=1}^{n_u}}{u}_i^{Q_i}$, where $p{k}_{ID}$ is $ID$’s public key. Then, the entity uses its secret value $us{k}_{ID}$ and partial private key $ps{k}_{ID}=(ps{k}_{ID,1},ps{k}_{ID,2})$ to compute its private key

  $$\begin{array}{cc}\hfill s{k}_{ID}& =(s{k}_{ID,1},s{k}_{ID,2})\hfill \\ & =(ps{k}_{ID,1}·us{k}_{ID}·{\left(U_{ID}\right)}^r,ps{k}_{ID,2}·g^r)\hfill \\ & =(g^{\alpha \beta }{\left(U_{ID}\right)}^s·g^{{\theta }_1{\theta }_2}·{\left(U_{ID}\right)}^r,g^s·g^r)\hfill \\ & =(g^{\alpha \beta }{g}^{{\theta }_1{\theta }_2}{\left(U_{ID}\right)}^{s+r},g^{s+r}).\hfill \end{array}$$
• $\mathbf{Sign}$: The signer with identity $ID$ generates a signature of a message m by performing the following steps.

  (1)

  Select a random value $r_m\in Z_p^{\ast }$ and compute ${\sigma }_3=g^{r_m}$.

  (2)

  Choose the current timestamp T and compute a vector $\overrightarrow{M}=H_2(m,T)=(M_1,\dots ,M_{n_m})\in {\{0,1\}}^{n_m}$ and $V_m=v_0{\displaystyle \prod _{j=1}^{n_m}}{v}_j^{M_j}$.

  (3)

  Compute

  $$\begin{array}{cc}\hfill h& =H_3(m,T,ID,p{k}_{ID},s{k}_{ID,2},{\sigma }_3,param),\hfill \\ \hfill {\sigma }_1& =s{k}_{ID,1}·{\left({\left(p{k}_{ID,3}\right)}^h{V}_m\right)}^{r_m},\hfill \\ \hfill {\sigma }_2& =s{k}_{ID,2},\hfill \end{array}$$

  where $s{k}_{ID}=(s{k}_{ID,1},s{k}_{ID,2})$ and $p{k}_{ID}=$ $(p{k}_{ID,1},p{k}_{ID,2},p{k}_{ID,3})$ are the private and public keys of identity $ID$, respectively.

  (4)

  Output $\sigma =({\sigma }_1,{\sigma }_2,{\sigma }_3)$ as a signature of m.

• $\mathbf{Verify}$: Given the signer’s identity $ID$ and public key $p{k}_{ID}=$ $(p{k}_{ID,1},p{k}_{ID,2},p{k}_{ID,3})$, timestamp T, and a signature $\sigma =({\sigma }_1,{\sigma }_2,{\sigma }_3)$ of message m, the verifier first chooses the current time $T^{{}^{\prime }}$. Then, the verifier verifies the legality of $\sigma$ as follows.

  (1)

  If $T^{{}^{\prime }}-T>\delta$, where $\delta$ is a threshold value, the verifier refuses to verify the validity of $\sigma$ and exits.

  (2)

  If $T^{{}^{\prime }}-T\le \delta$, the verifier computes $\overrightarrow{Q}=H_1(ID,p{k}_{ID})$, $U_{ID}$, $\overrightarrow{M}=H_2(m,T)$, $V_m$ and

  $$h=H_3(m,T,ID,p{k}_{ID},s{k}_{ID,2},{\sigma }_3,param).$$

  Then, the verifier checks

  $$\begin{array}{cc}\hfill e({\sigma }_1,g)=& e(g_2,g_1)·e(p{k}_{ID,1},p{k}_{ID,2})·e(U_{ID},{\sigma }_2)·e({\left(p{k}_{ID,3}\right)}^h{V}_m,{\sigma }_3).\hfill \end{array}$$

  If this equation holds, the verifier accepts $\sigma$ and outputs 1; otherwise, the verifier rejects $\sigma$ and outputs 0.

Correctness: The correctness of a signature $\sigma =({\sigma }_1,{\sigma }_2,{\sigma }_3)$ on a message m is presented as follows:

$$\begin{array}{cc}\hfill e({\sigma }_1,g)=& e(s{k}_{ID,1}·{\left({\left(p{k}_{ID,3}\right)}^h{V}_m\right)}^{r_m},g)\hfill \\ \hfill =& e(g^{\alpha \beta }{g}^{{\theta }_1{\theta }_2}{\left(U_{ID}\right)}^{s+r}·{\left({\left(p{k}_{ID,3}\right)}^h{V}_m\right)}^{r_m},g)\hfill \\ \hfill =& e(g^{\alpha \beta },g)·e(g^{{\theta }_1{\theta }_2},g)·e({\left(U_{ID}\right)}^{s+r},g)·e({\left({\left(p{k}_{ID,3}\right)}^h{V}_m\right)}^{r_m},g)\hfill \\ \hfill =& e(g^{\alpha },g^{\beta })·e(g^{{\theta }_1},g^{{\theta }_2})·e(U_{ID},g^{s+r})·e({\left(p{k}_{ID,3}\right)}^h{V}_m,g^{r_m})\hfill \\ \hfill =& e(g_2,g_1)·e(p{k}_{ID,1},p{k}_{ID,2})·e(U_{ID},{\sigma }_2)·e({\left(p{k}_{ID,3}\right)}^h{V}_m,{\sigma }_3).\hfill \end{array}$$

5. Security Proof

In our CLS scheme, the algorithm $\mathbf{SetSecKey}$ randomizes the entity’s secret value $us{k}_{ID}$ and partial private key $ps{k}_{ID}=(ps{k}_{ID,1},ps{k}_{ID,2})$ to generate the final private key $s{k}_{ID}=(s{k}_{ID,1},s{k}_{ID,2})=(ps{k}_{ID,1}·us{k}_{ID}·{\left(U_{ID}\right)}^r,ps{k}_{ID,2}·g^r)$. Hence, it is not feasible for a malicious KGC to produce a valid signature without the secret value $us{k}_{ID}$. Additionally, the KGC cannot derive the entity’s private key $s{k}_{ID}$ from the master secret key $msk$ and the entity’s partial private key $ps{k}_{ID}$.

To prevent PKR and MKGC attacks, a part $p{k}_{ID,3}$ of the entity’s public key is embedded in the signature $\sigma$. Only each entity can produce its legal public key $p{k}_{ID}=(p{k}_{ID,1},p{k}_{ID,2},p{k}_{ID,3})=(g^{{\theta }_1},g^{{\theta }_2},g^{{\theta }_3})$; thus, the malicious KGC can neither set the entity’s public key at will nor derive the secret value $us{k}_{ID}$ from the signature. Furthermore, it is impossible to obtain the value ${\left(p{k}_{ID,3}\right)}^{r_m}$ directly from the entity’s public key $p{k}_{ID}$ and the public value ${\sigma }_3=g^{r_m}$ of the signature unless the adversary can solve the CDH problem.

The algorithm $\mathbf{PSKExtract}$ binds each entity’s public key $p{k}_{ID}$, identity $ID$, and partial private key $ps{k}_{ID}$, which can enhance the trust level of the proposed CLS scheme. If the KGC attempts to replace the entity’s public key $p{k}_{ID}$, then the entity’s identity $ID$ and the new public key must be re-bound to compute a new partial private key, which results in the entity’s identity $ID$ corresponding to two public keys and two partial private keys. Therefore, our CLS scheme can easily determine whether the KGC replaced the entity’s public key.

In addition, $H_3$ is a collision-resistant hash function. The hash value h combines the message m, the identity $ID$, public key $p{k}_{ID}$, two values ${\sigma }_2$, and ${\sigma }_3$ in the signature, a timestamp T, and system parameters $param$ as $h=H_3(m,T,ID,p{k}_{ID},s{k}_{ID,2},{\sigma }_3,param)$. Hence, an attacker cannot forge a new valid signature from an existing signature on a message; that is, an adversary cannot generate a valid signature on any previously signed/new message in our CLS scheme.

In the following, we introduce two theorems to demonstrate that our CLS scheme satisfies a strong unforgeability against PKR and MKGC attacks in the standard model. Reduction technology is used to prove the strong unforgeability of the proposed scheme; specifically, if an attacker breaks the security of the scheme, a solver then uses the attacker’s ability to solve the underlying hard problem related to the scheme. However, this problem is intractable in reality; thus, such an attacker does not exist. Furthermore, we prove that the proposed CLS scheme can resist replay attacks.

Theorem 1.

In the standard model, our CLS scheme is strongly unforgeable against PKR attacks. Specifically, there is a type I adversary ${\mathcal{A}}_1$ that breaks the security of the proposed CLS scheme with advantage ${\epsilon }_1$ after making at most $q_{pk}$ public key queries, $q_{psk}$ partial private key queries, $q_{rep}$ PKR queries, $q_{sk}$ private key queries, and $q_s$ signing queries. Then, an algorithm $\mathcal{C}$ can use the forgery of ${\mathcal{A}}_1$ to solve the CDH problem with advantage ${\epsilon }_1^{{}^{\prime }}$.

Proof. 

$\mathcal{C}$ is given a random instance $(g,g^a,g^b)\in G_1^3$ of the CDH problem, and $\mathcal{C}$’s goal is to output $g^{ab}$ with the help of ${\mathcal{A}}_1$. The algorithm $\mathcal{C}$ simulates the challenger in Game 1 and responds to ${\mathcal{A}}_1$’s queries as follows.

• Initialization: $\mathcal{C}$ first sets $l_u=2(q_{psk}+q_{sk}+q_s)$ and $l_m=2q_s$ such that $l_u(n_u+1)<p$ and $l_m(n_m+1)<p$. Then, $\mathcal{C}$ simulates the algorithm $\mathbf{Setup}$ by performing the following steps:

  (1)

  Randomly select $k_u$$(0\le k_u\le n_u)$ and $k_m$$(0\le k_m\le n_m)$.

  (2)

  Randomly select $x_0,x_1,\dots ,x_{n_u}\in Z_{l_u}$, $y_0,y_1$, $\dots ,y_{n_u}\in Z_p$, $c_0,c_1,\dots ,c_{n_m}\in Z_{l_m}$, and $d_0,d_1,\dots$, $d_{n_m}\in Z_p$.

  (3)

  Select three hash functions $H_1:{\{0,1\}}^{\ast }\to {\{0,1\}}^{n_u}$, $H_2:{\{0,1\}}^{\ast }\to {\{0,1\}}^{n_m}$, and $H_3:{\{0,1\}}^{\ast }\to Z_p^{\ast }$. Note that the adopted hash functions are not considered to be random oracles in the following proof.

  (4)

  Set $g_1=g^a$ and $g_2=g^b$, where $g^a$ and $g^b$ are from the input of the instance of the CDH problem. Note that the master secret key is implicitly set to $msk=g^{ab}$.

  (5)

  Assign $u_0=g_2^{-l_u{k}_u+x_0}{g}^{y_0}$, $u_i=g_2^{x_i}{g}^{y_i}$ for $i=1,\dots ,n_u$, $v_0=g_2^{-l_m{k}_m+c_0}{g}^{d_0}$, and $v_j=g_2^{c_j}{g}^{d_j}$ for $j=1,\dots ,n_m$, and set $\overrightarrow{u}=(u_1,\dots ,u_{n_u})$ and $\overrightarrow{v}=(v_1,\dots ,v_{n_m})$.

  (6)

  Select three random integers ${\theta }_1^{\ast },{\theta }_2^{\ast },{\theta }_3^{\ast }\in Z_p^{\ast }$ and compute $p{k}_1^{\ast }=g^{{\theta }_1^{\ast }}$, $p{k}_2^{\ast }=g^{{\theta }_2^{\ast }}$, and $p{k}_3^{\ast }=g^{{\theta }_3^{\ast }}$. Next, set the secret value of the targeted entity to $us{k}^{\ast }=g^{{\theta }_1^{\ast }{\theta }_2^{\ast }}$ and the corresponding public key to $p{k}^{\ast }=(p{k}_1^{\ast },p{k}_2^{\ast },p{k}_3^{\ast })$.

  (7)

  Send system parameters $param=\{G_1,G_2,p,g$, $e,g_1,g_2,u_0,v_0,\overrightarrow{u},\overrightarrow{v},H_1,H_2,H_3\}$ and the targeted entity’s secret value/public key pair $(us{k}^{\ast },p{k}^{\ast })$ to ${\mathcal{A}}_1$.

  From the perspective of ${\mathcal{A}}_1$, the distribution of the system parameters produced by $\mathcal{C}$ is identical to the real construction.
  In our CLS scheme, we have $\overrightarrow{Q}=H_1(ID,p{k}_{ID})=(Q_1,\dots ,Q_{n_u})\in {\{0,1\}}^{n_u}$ for an identity $ID$ and a public key $p{k}_{ID}$, and we have $\overrightarrow{M}=H_2(m,T)=(M_1$, $\dots ,M_{n_m})\in {\{0,1\}}^{n_m}$ for a message m and a timestamp T. Aiming to simplify the analysis, we define the following four functions:

  $$\begin{array}{cc}\hfill F\left(ID\right)& =-l_u{k}_u+x_0+{\displaystyle \sum _{i=1}^{n_u}}{x}_i{Q}_i,J\left(ID\right)=y_0+{\displaystyle \sum _{i=1}^{n_u}}{y}_i{Q}_i,\hfill \\ \hfill K\left(m\right)& =-l_m{k}_m+c_0+{\displaystyle \sum _{j=1}^{n_m}}{c}_j{M}_j,L\left(m\right)=d_0+{\displaystyle \sum _{j=1}^{n_m}}{d}_j{M}_j.\hfill \end{array}$$
  Hence, we have the following equations:

  $$\begin{array}{cc}\hfill U_{ID}& =u_0{\displaystyle \prod _{i=1}^{n_u}}{u}_i^{Q_i}=g_2^{F\left(ID\right)}{g}^{J\left(ID\right)},\hfill \\ \hfill V_m& =v_0{\displaystyle \prod _{j=1}^{n_m}}{v}_j^{M_j}=g_2^{K\left(m\right)}{g}^{L\left(m\right)}.\hfill \end{array}$$
• Queries: $\mathcal{C}$ maintains a list $\mathcal{L}=\left\{\right(I{D}_i,{\theta }_{i,1},{\theta }_{i,2},{\theta }_{i,3}$, $us{k}_i,p{k}_i,ps{k}_i,s{k}_i\left)\right\}$, which is initially empty. $\mathcal{C}$ constructs the following oracles to answer a series of ${\mathcal{A}}_1$’s queries.

  –

  Public Key Query${\mathcal{O}}_{pk}\left(I{D}_i\right)$: When ${\mathcal{A}}_1$ initiates such an inquiry for an identity $I{D}_i$, $\mathcal{C}$ looks up the corresponding entry in the list $\mathcal{L}$. If $I{D}_i$ is found in $\mathcal{L}$, $\mathcal{C}$ returns $p{k}_i$ to ${\mathcal{A}}_1$. Otherwise, $\mathcal{C}$ randomly selects ${\theta }_{i,1},{\theta }_{i,2},{\theta }_{i,3}\in Z_p^{\ast }$ and computes the secret value $us{k}_i=g^{{\theta }_{i,1}{\theta }_{i,2}}$ and the public key $p{k}_i=(p{k}_{i,1},p{k}_{i,2},p{k}_{i,3})=(g^{{\theta }_{i,1}},g^{{\theta }_{i,2}},g^{{\theta }_{i,3}})$. Then, $\mathcal{C}$ stores $\left\{(I{D}_i,{\theta }_{i,1},{\theta }_{i,2},{\theta }_{i,3},us{k}_i,p{k}_i)\right\}$ in $\mathcal{L}$ and sends $p{k}_i$ to ${\mathcal{A}}_1$.

  –

  Public Key Replacement Query${\mathcal{O}}_{rep}(I{D}_i,p{k}_i^{{}^{\prime }})$: If there is an entry for the identity $I{D}_i$ in the list $\mathcal{L}$, $\mathcal{C}$ replaces the original public key $p{k}_i$ of $I{D}_i$ with a new public key $p{k}_i^{{}^{\prime }}$. Otherwise, $\mathcal{C}$ directly sets $p{k}_i^{{}^{\prime }}$ as the public key of $I{D}_i$.

  –

  Partial Private Key Query${\mathcal{O}}_{psk}(I{D}_i,p{k}_i)$: When ${\mathcal{A}}_1$ requests a partial private key of an identity $I{D}_i$ and a public key $p{k}_i$, $\mathcal{C}$ returns $ps{k}_i$ to ${\mathcal{A}}_1$ if there is an entry for $I{D}_i$ and $p{k}_i$ in the list $\mathcal{L}$. Otherwise, $\mathcal{C}$ computes $F\left(I{D}_i\right)$ and $J\left(I{D}_i\right)$.

  (1)

  If $F\left(I{D}_i\right)\ne 0\mathrm{mod}{l}_u$, $\mathcal{C}$ randomly selects $s_i\in Z_p^{\ast }$ and calculates a partial private key

  $$\begin{array}{cc}\hfill ps{k}_i& =(ps{k}_{i,1},ps{k}_{i,2})\hfill \\ & =(g_1^{\frac{-J\left(I{D}_i\right)}{F\left(I{D}_i\right)}}{\left(U_{I{D}_i}\right)}^{s_i},g_1^{\frac{-1}{F\left(I{D}_i\right)}}{g}^{s_i}),\hfill \end{array}$$

  where $U_{I{D}_i}=u_0{\displaystyle \prod _{k=1}^{n_u}}{u}_k^{Q_{i,k}}$ and ${\overrightarrow{Q}}_i=H_1(I{D}_i$, $p{k}_i)=(Q_{i,1},\dots ,Q_{i,n_u})\in {\{0,1\}}^{n_u}$. Then, $\mathcal{C}$ stores the partial private key of the corresponding entry in $\mathcal{L}$ and sends $ps{k}_i$ to ${\mathcal{A}}_1$.

  (2)

  If $F\left(I{D}_i\right)=0\mathrm{mod}{l}_u$, $\mathcal{C}$ terminates the simulation.

  Note that the partial private key $ps{k}_i=(ps{k}_{i,1},ps{k}_{i,2})$ generated by $\mathcal{C}$ is legal.

  $$\begin{array}{cc}\hfill ps{k}_{i,1}& =g_1^{\frac{-J\left(I{D}_i\right)}{F\left(I{D}_i\right)}}{\left(U_{I{D}_i}\right)}^{s_i}\hfill \\ & =g_2^a{\left(g_2^{F\left(I{D}_i\right)}{g}^{J\left(I{D}_i\right)}\right)}^{\frac{-a}{F\left(I{D}_i\right)}}{\left(U_{I{D}_i}\right)}^{s_i}\hfill \\ & =g_2^a{\left(U_{I{D}_i}\right)}^{s_i-\frac{a}{F\left(I{D}_i\right)}}\hfill \\ & =g^{ab}{\left(U_{I{D}_i}\right)}^{s_i-\frac{a}{F\left(I{D}_i\right)}},\hfill \\ \hfill ps{k}_{i,2}& =g_1^{\frac{-1}{F\left(I{D}_i\right)}}{g}^{s_i}=g^{s_i-\frac{a}{F\left(I{D}_i\right)}}.\hfill \end{array}$$

  Then, we have

  $$e(ps{k}_{i,1},g)=e(g_2,g_1)e(U_{I{D}_i},ps{k}_{i,2}).$$

  Hence, from ${\mathcal{A}}_1$’s perspective, the partial private key $ps{k}_i$ simulated by $\mathcal{C}$ is computationally indistinguishable from that computed by the real KGC.

  –

  Private Key Query${\mathcal{O}}_{sk}\left(I{D}_i\right)$: When ${\mathcal{A}}_1$ requests the private key of an identity $I{D}_i$, $\mathcal{C}$ checks for an entry of $I{D}_i$ in $\mathcal{L}$. If it exists, $\mathcal{C}$ returns $s{k}_i$ to ${\mathcal{A}}_1$; otherwise, $\mathcal{C}$ computes $F\left(I{D}_i\right)$ and $J\left(I{D}_i\right)$. If $F\left(I{D}_i\right)=0\mathrm{mod}{l}_u$, $\mathcal{C}$ terminates; otherwise, $\mathcal{C}$ initiates a public key query about $I{D}_i$ to acquire a secret value $us{k}_i$ and a public key $p{k}_i$ and then initiates a partial private key query with $(I{D}_i,p{k}_i)$ to acquire a partial private key $ps{k}_i$. Next, $\mathcal{C}$ executes the algorithm $\mathbf{SetSecKey}$ to create a private key $s{k}_i$, stores $s{k}_i$ of the corresponding entry in $\mathcal{L}$ and sends $s{k}_i$ to ${\mathcal{A}}_1$.

  –

  Signing Query${\mathcal{O}}_{sign}(I{D}_i,T,m)$: Upon receiving an identity $I{D}_i$, a timestamp T, and a message m, $\mathcal{C}$ issues a query ${\mathcal{O}}_{pk}\left(I{D}_i\right)$ to acquire a public key $p{k}_i=(p{k}_{i,1},p{k}_{i,2},p{k}_{i,3})$ and the triplet $({\theta }_{i,1},{\theta }_{i,2},{\theta }_{i,3})$. Then, $\mathcal{C}$ proceeds as follows.

  (1)

  If $F\left(I{D}_i\right)\ne 0\mathrm{mod}{l}_u$, $\mathcal{C}$ first makes a query ${\mathcal{O}}_{sk}\left(I{D}_i\right)$ to acquire a private key $s{k}_i$ and then runs the algorithm $\mathbf{Sign}$ to generate a signature ${\sigma }_i$ of m. Finally, $\mathcal{C}$ sends ${\sigma }_i$ to ${\mathcal{A}}_1$.

  (2)

  If $F\left(I{D}_i\right)=0\mathrm{mod}{l}_u$, $\mathcal{C}$ computes $K\left(m\right)$. If $K\left(m\right)=0\mathrm{mod}{l}_m$, $\mathcal{C}$ terminates; otherwise, $\mathcal{C}$ randomly selects $r_i,r_m\in Z_p^{\ast }$ and computes ${\overrightarrow{Q}}_i=H_1(I{D}_i,p{k}_i)$, $U_{I{D}_i}$, $\overrightarrow{M}=H_2(m,T)$, and $V_m$. Furthermore, $\mathcal{C}$ computes

  $$\begin{array}{cc}\hfill {\sigma }_{i,2}=& g^{r_i},\hfill \\ \hfill {\sigma }_{i,3}=& g_1^{\frac{-1}{K\left(m\right)}}{g}^{r_m},\hfill \\ \hfill h_i=& H_3(m,T,I{D}_i,p{k}_i,{\sigma }_{i,2},{\sigma }_{i,3},param),\hfill \\ \hfill {\sigma }_{i,1}=& {\left(U_{I{D}_i}\right)}^{r_i}{g}_1^{\frac{-L\left(m\right)-h_i{\theta }_{i,3}}{K\left(m\right)}}{\left({\left(p{k}_{i,3}\right)}^{h_i}{V}_m\right)}^{r_m}{g}^{{\theta }_{i,1}{\theta }_{i,2}}.\hfill \end{array}$$

  Finally, $\mathcal{C}$ sends ${\sigma }_i=({\sigma }_{i,1},{\sigma }_{i,2},{\sigma }_{i,3})$ to ${\mathcal{A}}_1$.

  For ${\tilde{r}}_m=r_m-\frac{a}{K\left(m\right)}$, we have

  $$\begin{array}{cc}\hfill {\sigma }_{i,1}=& {\left(U_{I{D}_i}\right)}^{r_i}{g}_1^{\frac{-L\left(m\right)-h_i{\theta }_{i,3}}{K\left(m\right)}}{\left({\left(p{k}_{i,3}\right)}^{h_i}{V}_m\right)}^{r_m}{g}^{{\theta }_{i,1}{\theta }_{i,2}}\hfill \\ \hfill =& {\left(U_{I{D}_i}\right)}^{r_i}{g}^{ab}{\left(g_2^{K\left(m\right)}{g}^{L\left(m\right)}{g}^{h_i{\theta }_{i,3}}\right)}^{\frac{-a}{K\left(m\right)}}{\left({\left(p{k}_{i,3}\right)}^{h_i}{V}_m\right)}^{r_m}{g}^{{\theta }_{i,1}{\theta }_{i,2}}\hfill \\ \hfill =& g^{ab}{g}^{{\theta }_{i,1}{\theta }_{i,2}}{\left(U_{I{D}_i}\right)}^{r_i}{\left({\left(p{k}_{i,3}\right)}^{h_i}{V}_m\right)}^{r_m-\frac{a}{K\left(m\right)}}\hfill \\ \hfill =& g^{ab}{g}^{{\theta }_{i,1}{\theta }_{i,2}}{\left(U_{I{D}_i}\right)}^{r_i}{\left({\left(p{k}_{i,3}\right)}^{h_i}{V}_m\right)}^{{\tilde{r}}_m},\hfill \\ \hfill {\sigma }_{i,2}=& g^{r_i},\hfill \\ \hfill {\sigma }_{i,3}=& g_1^{\frac{-1}{K\left(m\right)}}{g}^{r_m}=g^{r_m-\frac{a}{K\left(m\right)}}=g^{{\tilde{r}}_m}.\hfill \end{array}$$
  Clearly, the signature ${\sigma }_i=({\sigma }_{i,1},{\sigma }_{i,2},{\sigma }_{i,3})$ generated by $\mathcal{C}$ is legal because ${\sigma }_i$ satisfies the following verification equation:

  $$\begin{array}{cc}\hfill e({\sigma }_{i,1},g)=& e(g^{ab}{g}^{{\theta }_{i,1}{\theta }_{i,2}}{\left(U_{I{D}_i}\right)}^{r_i}{\left({\left(p{k}_{i,3}\right)}^{h_i}{V}_m\right)}^{{\tilde{r}}_m},g)\hfill \\ \hfill =& e(g^a,g^b)e(g^{{\theta }_{i,1}},g^{{\theta }_{i,2}})e(U_{I{D}_i},g^{r_i})e({\left(p{k}_{i,3}\right)}^{h_i}{V}_m,g^{{\tilde{r}}_m})\hfill \\ \hfill =& e(g_2,g_1)·e(p{k}_{i,1},p{k}_{i,2})·e(U_{I{D}_i},{\sigma }_{i,2})e({\left(p{k}_{i,3}\right)}^{h_i}{V}_m,{\sigma }_{i,3}).\hfill \end{array}$$
  From ${\mathcal{A}}_1$’s perspective, the signatures simulated by $\mathcal{C}$ are computationally indistinguishable from those produced by the real signer.
• Forgery: ${\mathcal{A}}_1$ eventually outputs a signature ${\sigma }^{\ast }=({\sigma }_1^{\ast },{\sigma }_2^{\ast },{\sigma }_3^{\ast })$ on a message $m^{\ast }$ corresponding to an identity $I{D}^{\ast }$, a timestamp $T^{\ast }$, and targeted public key $p{k}^{\ast }$. If $F\left(I{D}^{\ast }\right)\ne 0\mathrm{mod}p$ or $K\left(m^{\ast }\right)\ne 0\mathrm{mod}p$, $\mathcal{C}$ terminates; otherwise, $\mathcal{C}$ computes $h^{\ast }=H_3(m^{\ast },T^{\ast },I{D}^{\ast },p{k}^{\ast },{\sigma }_2^{\ast },{\sigma }_3^{\ast },param)$ and uses $({\theta }_1^{\ast },{\theta }_2^{\ast },{\theta }_3^{\ast })$ to output $g^{ab}$ as a solution to the CDH instance as follows:

  $$\begin{array}{cc}& \frac{{\sigma }_1^{\ast }}{g^{{\theta }_1^{\ast }{\theta }_2^{\ast }}{\left({\sigma }_2^{\ast }\right)}^{J\left(I{D}^{\ast }\right)}{\left({\sigma }_3^{\ast }\right)}^{L\left(m^{\ast }\right)+h^{\ast }{\theta }_3^{\ast }}}\hfill \\ \hfill =& \frac{g_2^a{g}^{{\theta }_1^{\ast }{\theta }_2^{\ast }}{\left(U_{I{D}^{\ast }}\right)}^{r_{ID}^{\ast }}{\left({\left(p{k}_3^{\ast }\right)}^{h^{\ast }}{V}_{m^{\ast }}\right)}^{r_m^{\ast }}}{g^{{\theta }_1^{\ast }{\theta }_2^{\ast }}{\left(g^{r_{ID}^{\ast }}\right)}^{J\left(I{D}^{\ast }\right)}{\left(g^{r_m^{\ast }}\right)}^{L\left(m^{\ast }\right)+h^{\ast }{\theta }_3^{\ast }}}\hfill \\ \hfill =& \frac{g_2^a{\left(g_2^{F\left(I{D}^{\ast }\right)}{g}^{J\left(I{D}^{\ast }\right)}\right)}^{r_{ID}^{\ast }}{\left({\left(g^{{\theta }_3^{\ast }}\right)}^{h^{\ast }}\left(g_2^{K\left(m^{\ast }\right)}{g}^{L\left(m^{\ast }\right)}\right)\right)}^{r_m^{\ast }}}{{\left(g^{J\left(I{D}^{\ast }\right)}\right)}^{r_{ID}^{\ast }}{\left(g^{{\theta }_3^{\ast }}\right)}^{r_m^{\ast }{h}^{\ast }}{\left(g^{L\left(m^{\ast }\right)}\right)}^{r_m^{\ast }}}\hfill \\ \hfill =& g_2^a{g}_2^{F\left(I{D}^{\ast }\right)r_{ID}^{\ast }}{g}_2^{K\left(m^{\ast }\right)r_m^{\ast }}\hfill \\ & (\mathrm{since}F\left(I{D}^{\ast }\right)=K\left(m^{\ast }\right)=0\mathrm{mod}p)\hfill \\ \hfill =& g_2^a\hfill \\ \hfill =& g^{ab}.\hfill \end{array}$$

Now, we analyze the probability that $\mathcal{C}$ can successfully solve the CDH problem. If the following conditions hold, $\mathcal{C}$ completes the above simulation without aborting.

(1)

All partial private key queries on $(I{D}_i,p{k}_i)$ have $F\left(I{D}_i\right)\ne 0\mathrm{mod}{l}_u$.

(2)

All private key queries on $I{D}_i$ have $F\left(I{D}_i\right)\ne 0\mathrm{mod}{l}_u$.

(3)

All signing queries on $(I{D}_i,T,m)$ have $F\left(I{D}_i\right)\ne 0\mathrm{mod}{l}_u$ or $K\left(m\right)\ne 0\mathrm{mod}{l}_m$.

(4)

In the forgery phase, $F\left(I{D}^{\ast }\right)=0\mathrm{mod}p$ and $K\left(m^{\ast }\right)=0\mathrm{mod}p$.

Here, we define four independent events $X_i$, $X^{\ast }$, $Y_j$, and $Y^{\ast }$ as follows.

• $X_i:F\left(I{D}_i\right)\ne 0\mathrm{mod}{l}_u$ for the ith query, where $1\le i\le q_{psk}+q_{sk}+q_s$.
• $X^{\ast }:F\left(I{D}^{\ast }\right)=0\mathrm{mod}p$.
• $Y_j:K\left(m_j\right)\ne 0\mathrm{mod}{l}_m$ for the jth query, where $1\le j\le q_s$.
• $Y^{\ast }:K\left(m^{\ast }\right)=0\mathrm{mod}p$.

Because the events ${\bigcap }_{i=1}^{q_{psk}+q_{sk}+q_s}{X}_i$, $X^{\ast }$, ${\bigcap }_{j=1}^{q_s}{Y}_j$, and $Y^{\ast }$ are independent, the probability that $\mathcal{C}$ does not terminate is

$$\begin{array}{cc}\hfill \mathrm{Pr}[\neg abort]\ge & \mathrm{Pr}[{\displaystyle \bigcap _{i=1}^{q_{psk}+q_{sk}+q_s}}{X}_i\cap X^{\ast }\cap {\displaystyle \bigcap _{j=1}^{q_s}}{Y}_j\cap Y^{\ast }]\hfill \\ \hfill =& \mathrm{Pr}\left[X^{\ast }\right]·\mathrm{Pr}[{\displaystyle \bigcap _{i=1}^{q_{psk}+q_{sk}+q_s}}{X}_i|X^{\ast }]·\mathrm{Pr}[Y^{\ast }]·\mathrm{Pr}[{\displaystyle \bigcap _{j=1}^{q_s}}{Y}_j|Y^{\ast }].\hfill \end{array}$$

From $l_u(n_u+1)<p$, $l_m(n_m+1)<p$, $0\le k_u\le n_u$, $0\le k_m\le n_m$, $x_0,x_1,\dots ,x_{n_u}\in Z_{l_u}$ and $c_0,c_1,\dots ,c_{n_m}\in Z_{l_m}$, we have $0\le l_u{k}_u<p$, $0\le l_m{k}_m<p$, $0\le x_0+{\displaystyle \sum _{i=1}^{n_u}}{x}_i{Q}_i<p$ and $0\le c_0+{\displaystyle \sum _{j=1}^{n_m}}{c}_j{M}_j<p$. Therefore, it is easy to derive $F\left(ID\right)=0\mathrm{mod}{l}_u$ and $K\left(m\right)=0\mathrm{mod}{l}_m$ from $F\left(ID\right)=0\mathrm{mod}p$ and $K\left(m\right)=0\mathrm{mod}p$, respectively. Moreover, $F\left(ID\right)\ne 0\mathrm{mod}{l}_u$ implies that $F\left(ID\right)\ne 0\mathrm{mod}p$, and $K\left(m\right)\ne 0\mathrm{mod}{l}_m$ implies that $K\left(m\right)\ne 0\mathrm{mod}p$. Since $x_0,x_1,\dots ,x_{n_u}$ and $c_0,c_1,\dots ,c_{n_m}$ are randomly chosen, we obtain the probabilities of the events $X^{\ast }$ and $Y^{\ast }$ as follows:

$$\begin{array}{cc}\hfill \mathrm{Pr}\left[X^{\ast }\right]=& \mathrm{Pr}[F\left(I{D}^{\ast }\right)=0\mathrm{mod}p]\hfill \\ \hfill \ge & \mathrm{Pr}[F\left(I{D}^{\ast }\right)=0\mathrm{mod}p\cap F\left(I{D}^{\ast }\right)=0\mathrm{mod}{l}_u]\hfill \\ \hfill =& \mathrm{Pr}[F\left(I{D}^{\ast }\right)=0\mathrm{mod}{l}_u]\mathrm{Pr}[F\left(I{D}^{\ast }\right)=0\mathrm{mod}p|F\left(I{D}^{\ast }\right)=0\mathrm{mod}{l}_u]\hfill \\ \hfill =& \frac{1}{l_u}\frac{1}{n_u+1},\hfill \\ \hfill \mathrm{Pr}\left[Y^{\ast }\right]=& \mathrm{Pr}[K\left(m^{\ast }\right)=0\mathrm{mod}p]\hfill \\ \hfill \ge & \mathrm{Pr}[K\left(m^{\ast }\right)=0\mathrm{mod}p\cap K\left(m^{\ast }\right)=0\mathrm{mod}{l}_m]\hfill \\ \hfill =& \mathrm{Pr}[K\left(m^{\ast }\right)=0\mathrm{mod}{l}_m]\mathrm{Pr}[K\left(m^{\ast }\right)=0\mathrm{mod}p|K\left(m^{\ast }\right)=0\mathrm{mod}{l}_m]\hfill \\ \hfill =& \frac{1}{l_m}\frac{1}{n_m+1}.\hfill \end{array}$$

Furthermore, we have

$$\begin{array}{cc}\hfill \mathrm{Pr}[{\displaystyle \bigcap _{i=1}^{q_{psk}+q_{sk}+q_s}}{X}_i|X^{\ast }]=& 1-\mathrm{Pr}[{\displaystyle \bigcup _{i=1}^{q_{psk}+q_{sk}+q_s}}\neg X_i|X^{\ast }]\hfill \\ \hfill \ge & 1-{\displaystyle \sum _{i=1}^{q_{psk}+q_{sk}+q_s}}\mathrm{Pr}[\neg X_i|X^{\ast }]\hfill \\ \hfill =& 1-\frac{q_{psk}+q_{sk}+q_s}{l_u},\hfill \\ \hfill \mathrm{Pr}[{\displaystyle \bigcap _{j=1}^{q_s}}{Y}_j|Y^{\ast }]=& 1-\mathrm{Pr}[{\displaystyle \bigcup _{j=1}^{q_s}}\neg Y_j|Y^{\ast }]\hfill \\ \hfill \ge & 1-{\displaystyle \sum _{j=1}^{q_s}}\mathrm{Pr}[\neg Y_j|Y^{\ast }]=1-\frac{q_s}{l_m}.\hfill \end{array}$$

Since $l_u=2(q_{psk}+q_{sk}+q_s)$ and $l_m=2q_s$, we write

$$\begin{array}{cc}\hfill \mathrm{Pr}[\neg abort]\ge & \frac{1}{l_u}·\frac{1}{n_u+1}·\left(1-\frac{q_{psk}+q_{sk}+q_s}{l_u}\right)\frac{1}{l_m}·\frac{1}{n_m+1}·\left(1-\frac{q_s}{l_m}\right)\hfill \\ \hfill =& \frac{1}{16q_s(n_u+1)(n_m+1)(q_{psk}+q_{sk}+q_s)}.\hfill \end{array}$$

Therefore, if ${\mathcal{A}}_1$ breaks the strong unforgeability of the proposed CLS scheme with advantage ${\epsilon }_1$, then $\mathcal{C}$ has an advantage ${\epsilon }_1^{{}^{\prime }}\ge$$\frac{{\epsilon }_1}{16q_s(n_u+1)(n_m+1)(q_{psk}+q_{sk}+q_s)}$ to solve the given instance of the CDH problem. □

Theorem 2.

In the standard model, the proposed CLS scheme is strongly unforgeable against MKGC attacks launched by the type II adversary ${\mathcal{A}}_2$. Concretely, assuming that ${\mathcal{A}}_2$ compromises the security of our CLS scheme with advantage ${\epsilon }_2$ after making at most $q_{pk}$ public key queries, $q_{sk}$ private key queries, and $q_s$ signing queries, then an algorithm $\mathcal{C}$ can use ${\mathcal{A}}_2$’s forgery to solve the CDH problem in $G_1$ with advantage ${\epsilon }_2^{{}^{\prime }}$.

Proof. 

Supposing that a PPT adversary ${\mathcal{A}}_2$ breaks the strong unforgeability of our CLS scheme in an adaptive chosen-message attack, we can construct an algorithm $\mathcal{C}$ that calls ${\mathcal{A}}_2$ as a subroutine to violate the CDH assumption. Assuming that $\mathcal{C}$ is given a random instance $(g,A=g^a,B=g^b)\in G_1^3$, to calculate $g^{ab}$, $\mathcal{C}$ simulates the challenger in Game 2 to answer all ${\mathcal{A}}_2$’s queries.

• Initialization: For the given values $q_{sk}$, $q_s$, $n_u$, and $n_m$, $\mathcal{C}$ sets $l_u=2(q_{sk}+q_s)$ and $l_m=2q_s$ such that $l_u(n_u+1)<p$ and $l_m(n_m+1)<p$. $\mathcal{C}$ selects a random element ${\theta }^{\ast }\in Z_p^{\ast }$ and calculates $p{k}_3^{\ast }=g^{{\theta }^{\ast }}$. Then, $\mathcal{C}$ sets the targeted entity’s public key $p{k}^{\ast }=(p{k}_1^{\ast },p{k}_2^{\ast },p{k}_3^{\ast })=(A=g^a,B=g^b,g^{{\theta }^{\ast }})$ and sends parameters $(G_1,G_2,p,g,e)$ and $p{k}^{\ast }$ to ${\mathcal{A}}_2$.
  Subsequently, ${\mathcal{A}}_2$ performs the following steps to produce other system parameters and the master secret key.

  (1)

  Select two random integers $k_u$ and $k_m$, where $0\le k_u\le n_u$ and $0\le k_m\le n_m$.

  (2)

  Randomly select $x_0,x_1,\dots ,x_{n_u}\in Z_{l_u}$, $c_0,c_1,\dots ,$$c_{n_m}\in Z_{l_m}$ and $y_0,y_1$, $\dots ,y_{n_u}$, $d_0,d_1,\dots$, $d_{n_m}\in Z_p$.

  (3)

  Select three collision-resistant hash functions $H_1:{\{0,1\}}^{\ast }\to {\{0,1\}}^{n_u}$, $H_2:{\{0,1\}}^{\ast }\to {\{0,1\}}^{n_m}$, and $H_3:{\{0,1\}}^{\ast }\to Z_p^{\ast }$.

  (4)

  Assign $u_0=B^{-l_u{k}_u+x_0}{g}^{y_0}$, $u_i=B^{x_i}{g}^{y_i}$ for $i=1,\dots ,n_u$, $v_0=B^{-l_m{k}_m+c_0}{g}^{d_0}$, and $v_j=B^{c_j}{g}^{d_j}$ for $j=1,\dots ,n_m$ and set $\overrightarrow{u}=(u_1,\dots ,u_{n_u})$ and $\overrightarrow{v}=(v_1,\dots ,v_{n_m})$.

  (5)

  Select two random values $\alpha ,\beta \in Z_p^{\ast }$ and compute $g_1=g^{\alpha }$, $g_2=g^{\beta }$ and $msk=g^{\alpha \beta }$.

  (6)

  Send parameters $(g_1,g_2,u_0,v_0,\overrightarrow{u},\overrightarrow{v},H_1,H_2,H_3)$ and the master secret key $msk$ to $\mathcal{C}$.

  Note that the secret value of the targeted entity is $us{k}^{\ast }=g^{ab}$, which is unknown to $\mathcal{C}$, and the system parameters are $param=\{G_1,G_2,p,g,e,g_1,g_2,u_0$, $v_0,\overrightarrow{u},\overrightarrow{v},H_1,H_2,H_3\}$.
  As the initialization phase in Theorem 1, we define the following four functions:

  $$\begin{array}{cc}\hfill F\left(ID\right)& =-l_u{k}_u+x_0+{\displaystyle \sum _{i=1}^{n_u}}{x}_i{Q}_i,J\left(ID\right)=y_0+{\displaystyle \sum _{i=1}^{n_u}}{y}_i{Q}_i,\hfill \\ \hfill K\left(m\right)& =-l_m{k}_m+c_0+{\displaystyle \sum _{j=1}^{n_m}}{c}_j{M}_j,L\left(m\right)=d_0+{\displaystyle \sum _{j=1}^{n_m}}{d}_j{M}_j.\hfill \end{array}$$
  Furthermore, we have the following equations:

  $$\begin{array}{cc}\hfill U_{ID}& =u_0{\displaystyle \prod _{i=1}^{n_u}}{u}_i^{Q_i}=B^{F\left(ID\right)}{g}^{J\left(ID\right)},\hfill \\ \hfill V_m& =v_0{\displaystyle \prod _{j=1}^{n_m}}{v}_j^{M_j}=B^{K\left(m\right)}{g}^{L\left(m\right)}.\hfill \end{array}$$
• Queries: $\mathcal{C}$ maintains an initially empty list ${\mathcal{L}}_2$ of tuples $\left\{(I{D}_i,{\theta }_{i,1},{\theta }_{i,2},{\theta }_{i,3},p{k}_i,s{k}_i)\right\}$ and builds the following oracles to answer the queries initiated by ${\mathcal{A}}_2$.

  –

  Public Key Query${\mathcal{O}}_{pk}\left(I{D}_i\right)$: When ${\mathcal{A}}_2$ issues such a query on an identity $I{D}_i$, $\mathcal{C}$ looks up the corresponding entry in list ${\mathcal{L}}_2$ and sends $p{k}_i$ to ${\mathcal{A}}_2$. Otherwise, if ${\mathcal{L}}_2$ does not store this entry, $\mathcal{C}$ randomly selects ${\theta }_{i,1},{\theta }_{i,2},{\theta }_{i,3}\in Z_p^{\ast }$ and computes the public key $p{k}_i=(p{k}_{i,1},p{k}_{i,2},p{k}_{i,3})=(A^{{\theta }_{i,1}},B^{{\theta }_{i,2}},g^{{\theta }_{i,3}})=(g^{a{\theta }_{i,1}},g^{b{\theta }_{i,2}},g^{{\theta }_{i,3}})$. Note that the secret value is $us{k}_i=g^{ab{\theta }_{i,1}{\theta }_{i,2}}$, but a and b are unknown to $\mathcal{C}$. Then, $\mathcal{C}$ stores $\left\{\right(I{D}_i$, ${\theta }_{i,1},{\theta }_{i,2},{\theta }_{i,3},p{k}_i\left)\right\}$ in ${\mathcal{L}}_2$ and transmits $p{k}_i$ to ${\mathcal{A}}_2$.

  –

  Private Key Query${\mathcal{O}}_{sk}\left(I{D}_i\right)$: Upon receipt of a query on an identity $I{D}_i$, $\mathcal{C}$ returns $s{k}_i$ to ${\mathcal{A}}_2$ if $I{D}_i$ is found in ${\mathcal{L}}_2$; otherwise, $\mathcal{C}$ makes a query ${\mathcal{O}}_{pk}\left(I{D}_i\right)$ to obtain a public key $p{k}_i=(p{k}_{i,1},p{k}_{i,2},p{k}_{i,3})$ and the triplet $({\theta }_{i,1},{\theta }_{i,2},{\theta }_{i,3})$ and then verifies whether $F\left(I{D}_i\right)=0\mathrm{mod}{l}_u$.

  (1)

  If $F\left(I{D}_i\right)=0\mathrm{mod}{l}_u$, $\mathcal{C}$ exits the simulation.

  (2)

  If $F\left(I{D}_i\right)\ne 0\mathrm{mod}{l}_u$, $\mathcal{C}$ selects $s_i\in Z_p^{\ast }$ and uses the master secret key $msk=g^{\alpha \beta }$ to compute

  $$\begin{array}{cc}\hfill s{k}_{i,1}& =A^{\frac{-J\left(I{D}_i\right){\theta }_{i,1}{\theta }_{i,2}}{F\left(I{D}_i\right)}}{g}^{\alpha \beta }{\left(U_{I{D}_i}\right)}^{s_i},\hfill \\ \hfill s{k}_{i,2}& =A^{\frac{-{\theta }_{i,1}{\theta }_{i,2}}{F\left(I{D}_i\right)}}{g}^{s_i},\hfill \end{array}$$

  where $U_{I{D}_i}=u_0{\displaystyle \prod _{k=1}^{n_u}}{u}_k^{Q_{i,k}}$ and ${\overrightarrow{Q}}_i=H_1(I{D}_i$, $p{k}_i)=(Q_{i,1},\dots ,Q_{i,n_u})\in {\{0,1\}}^{n_u}$. Then, $\mathcal{C}$ stores the private key of the corresponding entry in ${\mathcal{L}}_2$ and sends $s{k}_i=(s{k}_{i,1},s{k}_{i,2})$ to ${\mathcal{A}}_2$.

  The correctness of $s{k}_i$ simulated by $\mathcal{C}$ is

  $$\begin{array}{cc}\hfill s{k}_{i,1}=& A^{\frac{-J\left(I{D}_i\right){\theta }_{i,1}{\theta }_{i,2}}{F\left(I{D}_i\right)}}{g}^{\alpha \beta }{\left(U_{I{D}_i}\right)}^{s_i}\hfill \\ \hfill =& g^{\alpha \beta }{g}^{ab{\theta }_{i,1}{\theta }_{i,2}}{\left(g^{bF\left(I{D}_i\right)}{g}^{J\left(I{D}_i\right)}\right)}^{\frac{-a{\theta }_{i,1}{\theta }_{i,2}}{F\left(I{D}_i\right)}}{\left(U_{I{D}_i}\right)}^{s_i}\hfill \\ \hfill =& g^{\alpha \beta }{g}^{ab{\theta }_{i,1}{\theta }_{i,2}}{\left(U_{I{D}_i}\right)}^{s_i-\frac{a{\theta }_{i,1}{\theta }_{i,2}}{F\left(I{D}_i\right)}}\hfill \\ \hfill =& g^{\alpha \beta }{g}^{ab{\theta }_{i,1}{\theta }_{i,2}}{\left(U_{I{D}_i}\right)}^{{\tilde{s}}_i},\hfill \\ \hfill s{k}_{i,2}=& A^{\frac{-{\theta }_{i,1}{\theta }_{i,2}}{F\left(I{D}_i\right)}}{g}^{s_i}=g^{s_i-\frac{a{\theta }_{i,1}{\theta }_{i,2}}{F\left(I{D}_i\right)}}=g^{{\tilde{s}}_i},\hfill \end{array}$$

  where ${\tilde{s}}_i=s_i-\frac{a{\theta }_{i,1}{\theta }_{i,2}}{F\left(I{D}_i\right)}$. Hence, the above equations indicate that $s{k}_i=(s{k}_{i,1},s{k}_{i,2})$ is a valid private key of identity $I{D}_i$.

  –

  Signing Query${\mathcal{O}}_{sign}(I{D}_i,T,m)$: Upon receiving a message m, an identity $I{D}_i$, and a timestamp T, $\mathcal{C}$ issues a query ${\mathcal{O}}_{pk}\left(I{D}_i\right)$ to obtain a public key $p{k}_i=(p{k}_{i,1},p{k}_{i,2},p{k}_{i,3})$ and a triplet $({\theta }_{i,1},{\theta }_{i,2},{\theta }_{i,3})$. Then, $\mathcal{C}$ considers the following two cases:

  (1)

  If $F\left(I{D}_i\right)\ne 0\mathrm{mod}{l}_u$, $\mathcal{C}$ makes a query ${\mathcal{O}}_{sk}\left(I{D}_i\right)$ to obtain a private key $s{k}_i$ and then runs the algorithm $\mathbf{Sign}$ to generate a signature ${\sigma }_i$ on m. Finally, $\mathcal{C}$ sends ${\sigma }_i$ to ${\mathcal{A}}_2$.

  (2)

  If $F\left(I{D}_i\right)=0\mathrm{mod}{l}_u$, $\mathcal{C}$ computes $K\left(m\right)$. If $K\left(m\right)=0\mathrm{mod}{l}_m$, $\mathcal{C}$ quits the simulation; otherwise, $\mathcal{C}$ randomly selects $r_i,r_m\in Z_p^{\ast }$ and computes ${\overrightarrow{Q}}_i=H_1(I{D}_i,p{k}_i)$, $U_{I{D}_i}$, $\overrightarrow{M}=H_2(m,T)$, and $V_m$. Furthermore, $\mathcal{C}$ computes

  $$\begin{array}{cc}\hfill {\sigma }_{i,2}=& g^{r_i},\hfill \\ \hfill {\sigma }_{i,3}=& A^{\frac{-{\theta }_{i,1}{\theta }_{i,2}}{K\left(m\right)}}{g}^{r_m},\hfill \\ \hfill h_i=& H_3(m,T,I{D}_i,p{k}_i,{\sigma }_{i,2},{\sigma }_{i,3},param),\hfill \\ \hfill {\sigma }_{i,1}=& g^{\alpha \beta }{\left(U_{I{D}_i}\right)}^{r_i}{A}^{\frac{(L\left(m\right)-h_i{\theta }_{i,3}){\theta }_{i,1}{\theta }_{i,2}}{K\left(m\right)}}{\left({\left(p{k}_{i,3}\right)}^{h_i}{V}_m\right)}^{r_m}.\hfill \end{array}$$

  Finally, $\mathcal{C}$ sends ${\sigma }_i=({\sigma }_{i,1},{\sigma }_{i,2},{\sigma }_{i,3})$ to ${\mathcal{A}}_2$.

  Let ${\tilde{r}}_m=r_m-\frac{a{\theta }_{i,1}{\theta }_{i,2}}{K\left(m\right)}$; then, we have

  $$\begin{array}{cc}\hfill {\sigma }_{i,1}=& g^{\alpha \beta }{\left(U_{I{D}_i}\right)}^{r_i}{A}^{\frac{(L\left(m\right)-h_i{\theta }_{i,3}){\theta }_{i,1}{\theta }_{i,2}}{K\left(m\right)}}{\left({\left(p{k}_{i,3}\right)}^{h_i}{V}_m\right)}^{r_m}\hfill \\ \hfill =& g^{\alpha \beta }{g}^{ab{\theta }_{i,1}{\theta }_{i,2}}{\left(g^{bK\left(m\right)}{g}^{L\left(m\right)}{g}^{h_i{\theta }_{i,3}}\right)}^{\frac{-a{\theta }_{i,1}{\theta }_{i,2}}{K\left(m\right)}}{\left(U_{I{D}_i}\right)}^{r_i}{\left({\left(p{k}_{i,3}\right)}^{h_i}{V}_m\right)}^{r_m}\hfill \\ \hfill =& g^{\alpha \beta }{g}^{ab{\theta }_{i,1}{\theta }_{i,2}}{\left(\left(B^{K\left(m\right)}{g}^{L\left(m\right)}\right){\left(g^{{\theta }_{i,3}}\right)}^{h_i}\right)}^{\frac{-a{\theta }_{i,1}{\theta }_{i,2}}{K\left(m\right)}}{\left(U_{I{D}_i}\right)}^{r_i}{\left({\left(p{k}_{i,3}\right)}^{h_i}{V}_m\right)}^{r_m}\hfill \\ \hfill =& g^{\alpha \beta }{g}^{ab{\theta }_{i,1}{\theta }_{i,2}}{\left(U_{I{D}_i}\right)}^{r_i}{\left({\left(p{k}_{i,3}\right)}^{h_i}{V}_m\right)}^{r_m-\frac{a{\theta }_{i,1}{\theta }_{i,2}}{K\left(m\right)}}\hfill \\ \hfill =& g^{\alpha \beta }{g}^{ab{\theta }_{i,1}{\theta }_{i,2}}{\left(U_{I{D}_i}\right)}^{r_i}{\left({\left(p{k}_{i,3}\right)}^{h_i}{V}_m\right)}^{{\tilde{r}}_m},\hfill \\ \hfill {\sigma }_{i,2}=& g^{r_i},\hfill \\ \hfill {\sigma }_{i,3}=& A^{\frac{-{\theta }_{i,1}{\theta }_{i,2}}{K\left(m\right)}}{g}^{r_m}=g^{\frac{-a{\theta }_{i,1}{\theta }_{i,2}}{K\left(m\right)}}{g}^{r_m}=g^{r_m-\frac{a{\theta }_{i,1}{\theta }_{i,2}}{K\left(m\right)}}=g^{{\tilde{r}}_m}.\hfill \end{array}$$
  The simulated signature ${\sigma }_i=({\sigma }_{i,1},{\sigma }_{i,2},{\sigma }_{i,3})$ satisfies the following signature verification equation; thus, ${\sigma }_i$ is a valid signature on message m:

  $$\begin{array}{cc}\hfill e({\sigma }_{i,1},g)=& e(g^{\alpha \beta }{g}^{ab{\theta }_{i,1}{\theta }_{i,2}}{\left(U_{I{D}_i}\right)}^{r_i}{\left({\left(p{k}_{i,3}\right)}^{h_i}{V}_m\right)}^{{\tilde{r}}_m},g)\hfill \\ \hfill =& e(g^{\alpha \beta },g)e(g^{ab{\theta }_{i,1}{\theta }_{i,2}},g)e({\left(U_{I{D}_i}\right)}^{r_i},g)e({\left({\left(p{k}_{i,3}\right)}^{h_i}{V}_m\right)}^{{\tilde{r}}_m},g)\hfill \\ \hfill =& e(g^{\alpha },g^{\beta })e(g^{a{\theta }_{i,1}},g^{b{\theta }_{i,2}})e(U_{I{D}_i},g^{r_i})e({\left(p{k}_{i,3}\right)}^{h_i}{V}_m,g^{{\tilde{r}}_m})\hfill \\ \hfill =& e(g_2,g_1)e(p{k}_{i,1},p{k}_{i,2})e(U_{I{D}_i},{\sigma }_{i,2})e({\left(p{k}_{i,3}\right)}^{h_i}{V}_m,{\sigma }_{i,3}).\hfill \end{array}$$
• Forgery: ${\mathcal{A}}_2$ eventually outputs a signature ${\sigma }^{\ast }=({\sigma }_1^{\ast },{\sigma }_2^{\ast },{\sigma }_3^{\ast })$ on a message $m^{\ast }$ corresponding to an identity $I{D}^{\ast }$, a timestamp $T^{\ast }$, and the targeted public key $p{k}^{\ast }$. If $F\left(I{D}^{\ast }\right)\ne 0\mathrm{mod}p$ or $K\left(m^{\ast }\right)\ne 0\mathrm{mod}p$, $\mathcal{C}$ terminates; otherwise, $\mathcal{C}$ calculates $h^{\ast }=H_3(m^{\ast },T^{\ast },I{D}^{\ast },p{k}^{\ast },{\sigma }_2^{\ast },{\sigma }_3^{\ast },param)$ and then uses ${\theta }^{\ast }$ and $g^{\alpha \beta }$ to output the CDH value $g^{ab}$ by calculating

  $$\begin{array}{cc}& \frac{{\sigma }_1^{\ast }}{g^{\alpha \beta }{\left({\sigma }_2^{\ast }\right)}^{J\left(I{D}^{\ast }\right)}{\left({\sigma }_3^{\ast }\right)}^{L\left(m^{\ast }\right)+h^{\ast }{\theta }^{\ast }}}\hfill \\ \hfill =& \frac{g^{\alpha \beta }{g}^{ab}{\left(U_{I{D}^{\ast }}\right)}^{r_{ID}^{\ast }}{\left({\left(p{k}_3^{\ast }\right)}^{h^{\ast }}{V}_{m^{\ast }}\right)}^{r_m^{\ast }}}{g^{\alpha \beta }{\left(g^{r_{ID}^{\ast }}\right)}^{J\left(I{D}^{\ast }\right)}{\left(g^{r_m^{\ast }}\right)}^{L\left(m^{\ast }\right)+h^{\ast }{\theta }^{\ast }}}\hfill \\ \hfill =& \frac{g^{ab}{\left(B^{F\left(I{D}^{\ast }\right)}{g}^{J\left(I{D}^{\ast }\right)}\right)}^{r_{ID}^{\ast }}{\left({\left(p{k}_3^{\ast }\right)}^{h^{\ast }}\left(B^{K\left(m^{\ast }\right)}{g}^{L\left(m^{\ast }\right)}\right)\right)}^{r_m^{\ast }}}{{\left(g^{J\left(I{D}^{\ast }\right)}\right)}^{r_{ID}^{\ast }}{\left(g^{{\theta }^{\ast }}\right)}^{r_m^{\ast }{h}^{\ast }}{{\left(g^{r_m^{\ast }}\right)}^{r_m^{\ast }}}^{L\left(m^{\ast }\right)}}\hfill \\ \hfill =& g^{ab}{B}^{F\left(I{D}^{\ast }\right)r_{ID}^{\ast }}{B}^{K\left(m^{\ast }\right)r_m^{\ast }}\hfill \\ & (\mathrm{since}F\left(I{D}^{\ast }\right)=K\left(m^{\ast }\right)=0\mathrm{mod}p)\hfill \\ \hfill =& g^{ab}.\hfill \end{array}$$

Here, we discuss the probability of $\mathcal{C}$ outputting a correct solution for the CDH instance. $\mathcal{C}$ completes the above simulation if all of the following events occur:

• $F\left(I{D}_i\right)\ne 0\mathrm{mod}{l}_u$ during private key queries.
• $F\left(I{D}_i\right)\ne 0\mathrm{mod}{l}_u$ or $K\left(m\right)\ne 0\mathrm{mod}{l}_m$ during signing queries.
• $F\left(I{D}^{\ast }\right)=0\mathrm{mod}p$ and $K\left(m^{\ast }\right)=0\mathrm{mod}p$ in the forgery phase.

The probability of $\mathcal{C}$ completing the simulation is analogous to that in Theorem 1. We define four independent events, $X_i$, $X^{\ast }$, $Y_j$, and $Y^{\ast }$, as follows:

• $X_i:F\left(I{D}_i\right)\ne 0\mathrm{mod}{l}_u$ for $1\le i\le q_{sk}+q_s$.
• $X^{\ast }:F\left(I{D}^{\ast }\right)=0\mathrm{mod}p$.
• $Y_j:K\left(m_j\right)\ne 0\mathrm{mod}{l}_m$ for $1\le j\le q_s$.
• $Y^{\ast }:K\left(m^{\ast }\right)=0\mathrm{mod}p$.

Similar to the probability analysis in Theorem 1, we give the probability of $\mathcal{C}$ not aborting as

$$\begin{array}{cc}\hfill \mathrm{Pr}[\neg abort]=& \mathrm{Pr}[{\displaystyle \bigcap _{i=1}^{q_{sk}+q_s}}{X}_i\cap X^{\ast }\cap {\displaystyle \bigcap _{j=1}^{q_s}}{Y}_j\cap Y^{\ast }]\hfill \\ \hfill =& \mathrm{Pr}\left[X^{\ast }\right]\mathrm{Pr}[{\displaystyle \bigcap _{i=1}^{q_{sk}+q_s}}{X}_i|X^{\ast }]\mathrm{Pr}\left[Y^{\ast }\right]\mathrm{Pr}[{\displaystyle \bigcap _{j=1}^{q_s}}{Y}_j|Y^{\ast }]\hfill \\ \hfill =& \frac{1}{l_u(n_u+1)}\left(1-\frac{q_{sk}+q_s}{l_u}\right)\frac{1}{l_m(n_m+1)}\left(1-\frac{q_s}{l_m}\right)\hfill \\ \hfill =& \frac{1}{16q_s(q_{sk}+q_s)(n_u+1)(n_m+1)}.\hfill \end{array}$$

Hence, $\mathcal{C}$ can solve the given instance of the CDH problem with advantage ${\epsilon }_2^{{}^{\prime }}\ge \frac{{\epsilon }_2}{16q_s(q_{sk}+q_s)(n_u+1)(n_m+1)}$. □

We obtain Theorem 3 by combining Theorems 1 and 2, as follows.

Theorem 3.

In the standard model, our CLS scheme is strongly unforgeable against adaptive chosen-message attacks corresponding to type I and II adversaries under the CDH and CRHF assumptions.

Theorem 4.

Our CLS scheme is resistant to replay attacks.

Proof. 

In replay attacks, the adversary generally initiates two types of attacks [31,32]. One is to directly replay the intercepted message and the corresponding signature, and the other is to modify the timestamp in the signature of the intercepted message and to create a new signature for the message.

In the first type of attack, it is assumed that the adversary replays an intercepted combination of message m, timestamp T, and signature $\sigma$ generated by an IoT device. Upon receiving this combination $\{m,T,\sigma \}$, the data centre compares the timestamp T in the combination with the current timestamp $T^{{}^{\prime }}$. If the value of $T^{{}^{\prime }}-T$ exceeds the threshold $\delta$, the data centre can determine that m in this combination is a replayed message and can discard m. Therefore, the first type of attack has no effect on our CLS scheme. □

Since our CLS scheme satisfies strong unforgeability, the attacker cannot generate a legal signature for any message. Therefore, in the second type of attack, the attacker can only use the existing combination $\{m,T,\sigma \}$ to initiate the attack. In the proposed scheme, the timestamp T is bound to the message m, i.e., $\overrightarrow{M}=H_2(m,T)$. Additionally, the timestamp T is embedded in the parameter h in the form of $h=H_3(m,T,ID,p{k}_{ID},{\sigma }_2,{\sigma }_3,param)$ and is also embedded in the signature $\sigma$ of the message m in the form of ${\left(p{k}_3\right)}^{r_{m}h}$. If the attacker wants to replace T in the signature $\sigma$ with a new timestamp $T^{\ast }$, the attacker needs to calculate $h^{\ast }=H_3(m,T^{\ast },ID,p{k}_{ID},{\sigma }_2,{\sigma }_3,param)$ and ${\left(p{k}_3\right)}^{r_m{h}^{\ast }}$. Although an attacker can calculate $h^{\ast }$ and ${\left(p{k}_3\right)}^{h^{\ast }}$, the difficulty in calculating $r_m$ from ${\left(p{k}_3\right)}^{r_{m}h}$ is equivalent to solving the DL problem. However, if the attacker does not know $r_m$, then they cannot calculate the correct value ${\left(p{k}_3\right)}^{r_m{h}^{\ast }}$. In addition, $T^{\ast }$ must satisfy the conditions $H_2(m,T)=H_2(m,T^{\ast })$ and $H_1(m,T)=H_1(m,T^{\ast })$, which is equivalent to finding a collision of the hash functions $H_2$ and $H_3$. Since the DL problem is unsolvable in reality and the functions $H_2$ and $H_3$ are CRHF, the second type of attack does not compromise the security of our CLS scheme. In summary, the proposed CLS scheme can efficiently withstand replay attacks.

6. Application in IoT Environments and Performance Analysis

6.1. System Model

In a CLS scheme for IoT environments, it is very important that data are not modified and that the source of the data is authentic during data transmission. Therefore, we mainly focus on the integrity and authenticity of IoT data in our system while simultaneously reducing the bandwidth, computational cost, and storage overhead for IoT devices. Figure 2 shows our CLS system model for IoT environments, which consists of three entities: PKG, data centre, and IoT device.

• PKG: This entity is primarily responsible for producing system parameters and computing partial private keys for the data centre and each IoT device. The PKG sends system parameters to all of the entities through a public channel and transmits an individual partial private key to each entity via a secure channel.
• Data centre: This entity has a strong computing power and storage space; thus, it can check the integrity and authenticity of the data by verifying the signature sent by each IoT device and can store the authentic data for other users to use. Initially, the data centre submits its identity information to the PKG to apply for the corresponding partial private key; it then saves the system parameters and partial private key sent by the PKG.
• IoT device: This entity equipped with sensors has limited computational and memory resources and limited battery capacity. During the registration of the IoT device, the PKG generates a unique partial private key based on the physical address of each IoT device. After the IoT device is embedded with system parameters and its private key, it signs messages collected from the physical world and sends the corresponding signatures along with messages to the data centre.

6.2. Performance Analysis

In this subsection, we analyze the performance of the proposed CLS scheme. Compared with other cryptographic operations, bilinear pairing and exponentiation are the most time-consuming operations [22,28]; hence, our efficiency analysis mainly emphasizes the computational costs of these two operations.

Table 1. A comparison of the CLS scheme performance.

Scheme	KeySize	SigSize	Sign	Verify
Yu et al. [21]	$\left|p\right|+2|G_1|$	$4|G_1|$	$7E$	$E+5P$
Yuan et al. [23]	$\left|p\right|+2|G_1|$	$3|G_1|$	$3E$	$E+6P$
Pang et al. [27]	$\left|p\right|+2|G_1|$	$3|G_1|$	$7E$	$4E+5P$
Huang et al. [22]	$3|G_1|$	$3|G_1|$	$5E$	$3E+6P$
Yang et al. [30]	$(4+n_u)\left|p\right|+2|G_1|$	$\left|p\right|+4|G_1|$	$10E$	$3E+7P$
Our scheme	$2|G_1|$	$3|G_1|$	$3E$	$E+3P$

and

Table 2. A comparison of the security attributes.

Scheme	Type I	Type II	SUF	Replay Attacks
Yu et al. [21]	No	No	No	No
Yuan et al. [23]	Yes	Yes	No	No
Pang et al. [27]	Yes	Yes	No	No
Huang et al. [22]	Yes	No	No	No
Yang et al. [30]	Yes	Yes	Yes	No
Our scheme	Yes	Yes	Yes	Yes

compare the performance of our CLS scheme and other related CLS schemes [21,22,23,27,30] without random oracles in terms of private key size, signature length, computational cost, and security. In Table 1, the KeySize and SigSize columns list the sizes of the private key and signature, respectively. The Sign and Verify columns present the computational costs of the algorithms $\mathbf{Sign}$ and $\mathbf{Verify}$, respectively. Let P and E represent the execution times of a bilinear pairing and an exponentiation, respectively. Let $n_u$ represent the length of an identity, and let $|G_1|$ and $\left|p\right|$ represent the lengths of an element in $G_1$ and $Z_p$, respectively. In Table 2, the columns Type I, Type II, and Replay attacks show whether the CLS scheme can resist PKR attacks, MKGC attacks, and replay attacks, respectively. The SUF column denotes whether the CLS scheme satisfies a strong unforgeability in the standard model. It should be noted that the key length affects the storage capacity of the IoT device and the data center and that the signature length affects the communication capabilities of the IoT device and the storage capacity of the data center. In addition, the overhead of signature generation and signature verification affect the computing power of the IoT device and the data center, respectively.

From Table 1 and Table 2, the length of the private key in our CLS scheme is $2|G_1|$, which is the shortest among the six CLS schemes. The size of the signature in the proposed CLS scheme is $3|G_1|$, which is equivalent to that of the schemes presented in References [22,23,27] but smaller than that of other schemes [21,30]. In the signing phase, our CLS scheme requires three exponentiations, as does Yuan et al.’s scheme [23], but is superior to other schemes [21,22,27,30]. In the verification phase, the computational cost of the proposed CLS scheme is $E+5P$, which is lower than that of the five other CLS schemes. Moreover, the efficiency of the verification process in our CLS scheme can be improved by a pre-calculation. Note that the verification equation for signature legitimacy is as follows:

$$\begin{array}{c}\hfill e({\sigma }_1,g)=e(g_2,g_1)·e(p{k}_{ID,1},p{k}_{ID,2})·e(U_{ID},{\sigma }_2)·e({\left(p{k}_{ID,3}\right)}^h{V}_m,{\sigma }_3).\end{array}$$

Here, $e(g_2,g_1)$ and $e(p{k}_{ID,1},p{k}_{ID,2})$ can be pre-computed; thus, the time cost of verification in our CLS scheme can be reduced to one exponentiation and 3 bilinear pairings. Furthermore, only our CLS scheme can resist PKR attacks, MKGC attacks, and replay attacks while satisfying a strong unforgeability.

We also evaluated the performance of the proposed CLS scheme via experiments conducted with the PBC-0.47-VC cryptographic library [50]. The simulation program was run on a laptop equipped with a basic configuration of a 2.50 GHz CPU, 8 GB RAM, and the 64-bit Windows 10 operating system. To obtain faster pairing computation, we selected the Type A curve in the PBC library, which is a super-singular curve $y^2=x^3+x$ built with the 512-bit order of the base field. The results of the experiment are presented in Figure 3, Figure 4, Figure 5 and Figure 6.

The IoT device must secretly store its private key; therefore, the size of the private key is important for an IoT device with a limited storage capacity. As shown in Figure 3, the size of the private key in our CLS scheme is 256 bits, which is 92.8% of that in Yuan et al.’s CLS scheme [23]. However, the size of the private key increases linearly with the length of the entity’s identity in Yang et al.’s CLS scheme [30]. For example, if the length $n_u$ of the entity’s identity is 100 bits, then the private key size in our CLS scheme is approximately 11% of that in Yang et al.’s CLS scheme [30]. In other words, our CLS scheme has a higher performance in private key length.

Since IoT devices possess limited battery power and communication bandwidth, one of the goals of our CLS scheme is to reduce the communication overhead of IoT devices. The most critical factor affecting communication cost is signature size. Figure 4 shows that the signature size of our CLS scheme and that of Yuan et al. [23] is 384 bits, while the signature size of Yang et al.’s CLS scheme [30] is 532 bits. Hence, the proposed CLS scheme has a lower communication overhead.

Due to the characteristics of IoT devices, such as limited computing and processing power, the computational overhead of generating signatures for IoT devices should be as small as possible. Figure 5 shows that the cost of signature generation in our CLS scheme is almost the same as that in Yuan et al.’s CLS scheme [23] but less than that in Yang et al.’s CLS scheme [30].

The data centre has a strong computation and storage capability to verify the validity of signatures sent by IoT devices. Figure 6 shows that the proposed CLS scheme greatly reduces the computational overhead of signature verification and that its performance is superior to that of the other two schemes [23,30].

A scheme in the random oracle model usually has a higher computational performance, but its security depends on the ideal random oracle. Both our scheme and Yang et al.’s [48] scheme are provable in the standard model, and their security only depends on the difficulty of the associated mathematical problems. Therefore, these two schemes have higher security than other schemes [4,40,41,42,44,46,47]. Our scheme and Yang et al.’s scheme [48] use CLS and SDVPRS respectively to guarantee the integrity and authenticity of data in IoT. We compare the signature generation and verification overhead of two schemes, and the corresponding results are shown in Figure 7 and Figure 8.

From Figure 7, we can see that the computational cost of signature generation in our scheme is lower than that in the scheme of Reference [48]. This is because the signature generation in the scheme of Reference [48] requires an additional bilinear pairing operation. Figure 8 shows that the time consumption of signature verification in the scheme of Reference [48] is lower than ours, but the scheme in Reference [48] does not satisfy the properties of a strong unforgeability and replay attack resistance. As a result, our scheme has a higher security.

In summary, the results of all the above experimental analyses are consistent with those of the theoretical analysis in Table 1. Therefore, we conclude that our CLS scheme is applicable to IoT environments.

7. Conclusions

The IoT is profoundly changing production activities, social management, and public services, but ensuring the integrity and authenticity of data is an important issue for IoT. To solve this problem, a new CLS scheme for IoT environments is presented in this paper. In addition to protecting data integrity and data authenticity, our CLS scheme also reduces the computational and communication costs for IoT devices. The proposed CLS scheme is proven to be strongly unforgeable against adaptive chosen-message attacks under the CDH and CRHF assumptions in the standard model. Additionally, our CLS scheme can withstand replay attacks. Furthermore, the performance comparisons demonstrate that our CLS scheme outperforms the previous CLS schemes without random oracles. The Internet of Vehicles is considered to be one of the most potential areas in IoT and has wide application prospects in the field of intelligent transportation. Compared with ordinary sensors, the vehicle terminal equipment has a more stable power supply and higher computing power and storage space. Hence, our CLS scheme is suitable for the Internet of Vehicles.