# A Secure Certificateless Signature Scheme for Space-Based Internet of Things

Authors: Tongwei Liu; Wei Peng; Kai Zhu; Baokang Zhao
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Space-based Internet of things (S-IoT) can provide global services and connection capabilities. It has broad emerging application, including marine monitoring, forest monitoring, animal monitoring, disaster emergency response and other fields. However, owing to the openness of satellite communications, S-IoT is vulnerable to hijacking attacks, and malicious attackers can tamper with or forge transmitted messages. More seriously, due to limited S-IoT node resources, it is difficult to directly apply existing security solutions to terrestrial networks to the S-IoT. In this study, we propose CSP, a novel, secure, and efficient scheme based on certificateless signatures and bilinear pairings for S-IoT. CSP consists of six phases: system setup, partial private key settings, private key settings, public key settings, signing and verifying. In CSP, we especially design that part of the private key comes from the ground KGC and the other part is generated by the communication entity itself. We theoretically prove CSP is secure, and it is able to resist tampering or forgery attacks. Moreover, it can also ensure the authenticity, integrity, unforgeability, and nonrepudiation of transmitted messages. We also conducted extensive experiments and compared CSP with the existing schemes. The experimental results demonstrate that CSP can significantly reduce the total scheme time consumption. Especially, it can reduce about 50–60% of the time in the signature verification phase.


---

## Body

## 1. Introduction

Space-based Internet of Things(S-IoT) has broad application prospects in the fields of disaster emergency, animal monitoring, air pollution monitoring, aerospace measurement and control, aviation and navigation, and mobile communications [1–6], as shown in Figure 1. At present, the IoT generally transmits information through terrestrial networks such as the Internet and mobile communication networks, which severely limits the application scope and makes it hard to achieve true interconnection of all things. Terrestrial networks mainly cover densely populated areas such as cities and towns. More than 70% of the Earth’s area and more than 3 billion people are not covered by terrestrial networks. S-IoT can cover sparsely populated areas such as oceans, polar regions, and deserts [7, 8]. In addition, S-IoT can also be applied in situations where terrestrial infrastructure has been damaged, such as reconstruction in disaster areas. According to the forecast of McKinsey, an American consulting company, the output value of S-IoT will reach 560 billion to 850 billion dollars within the next 5 years. It is expected that the number of machine-to-machine (M2M) and IoT networks connected to S-IoT will reach 5.96 million by 2025 [9].Figure 1
S-IoT application scenarios.Authentication is one of the fundamental issues for security [10]. However, owing to the openness of satellite communications, identity authentication between nodes and message integrity authentication face significant challenges. First, in S-IoT, a single satellite usually needs to provide data transmission services for massive ground nodes. The particularity of the environment makes the messages transmitted by satellites vulnerable to security threats such as eavesdropping, tampering, and forgery. Therefore, the communication security between satellite nodes is indispensable. Second, since the communication bandwidth of a satellite is typically narrow and satellite storage resources are also limited, the authentication scheme must be efficient. Third, in S-IoT, scores of ground nodes are distributed in the wild and may even be carried by animals. The computing, storage, and energy resources of ground nodes are severely limited due to the constraints of weight, volume, and deployment environment. These constraints require that the operations of ground nodes must be simple enough to operate [11]. Therefore, a secure and effective authentication scheme is urgently needed to ensure the development of S-IoT.The main contribution of this study can be summarized as follows:(1)
We proposed CSP, a novel, secure, and efficient scheme based on certificateless signatures and bilinear pairings for S-IoT. To set the complete private key, a partial private key comes from the ground KGC and the other part of the private key is generated by the communication entity itself. In this way, CSP does not need a certificate authority and solves the key escrow issues.(2)
We have proved CSP, which has strong security and can effectively resist the attacks of external and internal adversaries. Moreover, CSP enables authenticity, integrity, unforgeability, and nonrepudiation of transmitted messages.(3)
We designed the CSP so that it only needs one hash function. Compared with the previous schemes, our scheme reduces the bilinear pairing operations in the verification phase. Performance evaluation shows that CSP can significantly reduce the total scheme time consumption. Especially, it can reduce about 50-60% of the time in the signature verification phase.The organization of this study is summarized as follows. In Section2, we review the related work. The S-IoT architecture, some principles of cryptography, and security model are described in Section 3. In Section 4, we elaborate on our proposed scheme for CSP. We present the security analysis of CSP in Section 5. In Section 6, we evaluate the performance. We finally conclude the study and discuss the future research direction in Section 7.


## 2. Related Work

The existing work on the certification of IoT can be roughly divided into three types. The first method is the authentication based on the public key infrastructure (PKI) mechanism, the second method is the authentication based on the identity-based cryptosystem (IBC), and the third method is the authentication based on the certificateless public key cryptography (CL-PKC).In the traditional PKI, the certificate authority (CA) complexly manages the public key and identity information of all users and issues certificates to authenticated users. However, the generation, storage, distribution, verification, and revocation of certificates can be resource intensive.Shamir [12] introduced IBC to try to solve the tedious problem of certificate management. As shown in [13], in addition to human users, computers and servers, smartphones, other mobile devices, and IoT devices also have their own identities. The IBC uses the user’s identity information directly as the public key. The user’s private key is generated by the key generation center (KGC) using the master key and the user’s identity information. There have also been some studies [14, 15] on IBC in recent years. However, in an IBC system, the KGC must be highly trusted because it can encrypt and decrypt messages on behalf of any system user. This creates a key escrow problem inherent in the IBC system. Once KGC is invaded or breached, all users’ private keys and identity information will be leaked. Then, the entire system will be paralyzed.To solve these problems, Al-Riyam et al. [16] proposed CL-PKC. They designed a novel certificateless signature (CLS) scheme, in which KGC only provides part of the user’s private key, and the other part is generated by the user, which can solve the key escrow problem. In addition, different from the traditional PKI system, users in the CL-PKC system do not need to be authenticated. Therefore, CLS do not need a certificate authority. CLS can be divided into two categories: one contains bilinear pairs and the other does not contain them.Later, CLS technology has been greatly developed. In 1996, Bellare and Rogaway [17] proposed a random oracle model (ROM) to prove the security of the CLS scheme. This model can efficiently evaluate the scheme, but there are many loopholes. At the beginning of this century, Choudary Gorantla and Saxena [18] claimed to have proposed a high-efficiency CLS scheme. However, in 2006, Cao et al. [19] proved that their scheme is not secure against key substitution attacks. Zhang et al. [20] designed a new certificateless signature scheme using bilinear pairings and used the ROM to achieve strict security proofs under the assumption of computing the Diffie–Hellman Problem (DHP), but their algorithm’s computational cost is significant.In 2012, Tso et al. [21] proposed a certificateless short signature scheme. However, Du and Wen [22] point out that the scheme cannot resist the attack of the second type of strong adversary in the ROM model. There are also two short CLS schemes [23, 24], both of which have been proven to be secure. However, the scheme in [23] needs to perform two bilinear calculations during verification, while the scheme in [24] requires three bilinear calculations. Obviously, the computational cost is relatively high. The first CLS scheme without bilinear pairings is proposed in [25], but it is pointed out in [26] that this scheme is vulnerable to the second type of strong adversaries. After that, proposed CLS schemes without bilinear pairings were proposed in [27, 28], respectively. However, it is pointed out in [29, 30] that both schemes are vulnerable to the first type of super-adversaries. In 2015, Hassouna et al. [31] claimed to propose a strongly secure CLS scheme and proved its security under the assumption of two classes of strong adversary attacks. However, scholars soon proved that the scheme in [31] is insecure in the face of the attack of the first type of strong adversary. In addition, Wang et al. [32] proposed a novel, reliable, and efficient pairing-free certificateless scheme for the Industrial Internet of Things (IIoT) that utilizes the state-of-the-art blockchain technique and smart contracts. In 2018, Jia et al. [33] proposed an efficient and nonbilinear pairwise CLS scheme suitable for the IoT. In 2020, Du et al. [34] found that the scheme in [33] could not resist the attack of the first type of adversaries and proposed a new scheme. In the same year, a bilinear pair-free CLS scheme suitable for resource-constrained scenarios was proposed in [35]. However, in 2021, Xu et al. [36] found that the solution of [35] was vulnerable to signature forgery attacks and could not achieve its purpose.Table1 shows the main mechanisms and shortcomings of the existing works. From the above, we can see that the existing PKI and IBC mechanisms may not be suitable for S-IoT. The CLS scheme without bilinear pairings does not seem to be reassuring in terms of security. Especially, in recent years, the scheme proposed in a short period of time will be found to be unsafe. However, existing CLS schemes containing bilinear pairings have a large overhead. If these schemes are applied to the S-IoT, they will take up a large amount of resources. Therefore, we want to design a CLS scheme that balances security and computational overhead, which is suitable for the special environment of S-IoT.Table 1
Existing works.
MethodMain mechanismServicesShortcomingsPKIPublic key certificate, certificate authority (CA), registrar authority (RA), etc.Authentication, integrity, confidentiality, data fairness, nonrepudiationCertificate management consumes a lot of resourcesIBCUser ID is the user’s public key (which can be their name, IP address, e-mail address, mobile phone number, etc.)Authentication, integrity, confidentiality, and nonrepudiationKey escrow issueCL-PKCThe user’s private key is divided into two parts; one is generated by KGC, and the other is generated by the userAuthentication, Integrity, Confidentiality, and nonrepudiationSome existing schemes have low security or high overhead; it is not fully considered for S-IoT scenarios


## 3. Preliminaries

### 3.1. S-IoT Architecture

The typical S-IoT architecture [3] is shown in Figure 2. The S-IoT architecture consists of three parts: space segment, ground segment, and user terminal. The space segment consists of a constellation of satellites. The ground segment mainly includes the ground stations and the control stations. The user terminal refers to various terminals which are mainly used to send and receive signals. Information security is an important issue in S-IoT. There may be malicious nodes attacking the S-IoT system through eavesdropping, forgery, tampering, and other means.Figure 2
S-IoT architecture [3].


### 3.2. Elliptic Curve

Elliptic curve cryptography (ECC) is a method of constructing cryptographic schemes from elliptic curves over finite fields. Elliptic curve cyphers can achieve the same strength with shorter keys than RSA; that is, elliptic curve cyphers have shorter key lengths but higher strength. In general, an elliptic curve cypher with a key length of 160 bits can achieve the same strength as RSA with a key length of 1024 bits.Letp be a large prime number of length λ, GF(p) represents a finite field, and an elliptic curve is a series of points satisfying the following equations:(1)G=x,y:y2=x3+ax+b,4a3+27b2modp≠0∪Oa,b∈GFp,where O represents the point at infinity.


### 3.3. Bilinear Pairing

Let the bilinear mapping bee:G1×G2⟶G2, where G1 and G2 are the additive cyclic group and the multiplicative cyclic group of order prime p, respectively. The generator of G1 is P. The bilinear map satisfies the following properties:(1)
Bilinearity:∀Q,W,Z∈G1; there are eQ,W+Z=eQ,W⋅eQ,Z and Q+W,Z=eQ,Z⋅eW,Z. Then, ∀a,b∈Zq∗, eaQ,bW=eQ,Wab(2)
Nondegenerate:∃P,Q∈G1,eP,Q≠1(3)
Computability:∀P,Q∈G1; there is a valid algorithm that can compute eP,Q


### 3.4. Elliptic Curve Computational Diffie–Hellman Problem (ECDHP)

GivenaP,bP∈G1,a,b,c∈Zq∗, where P is the generator of G1, it is hard to calculate abP∈G1.


### 3.5. Bilinear Diffie–Hellman Problem (BDHP)

GivenaP,bP,cP∈G1,a,b,c∈Zq∗, where P is the generator of G1, it is hard to calculate eP,Pabc∈G2.


### 3.6. Certificateless Signature

A certificateless signature scheme generally includes three entities: KGC, signer, and verifier. The general steps of the CLS are as follows:(1)
Setup: this step is performed by KGC. We input a security parameterl and output the system master key s and public parameter params. KGC securely keeps the system master key s and makes params public.(2)
Set partial private key: this step is performed by KGC. We input the system master keys, the public parameter params and the signer’s identity ID. Then, we output the partial private key D.(3)
Set private key: this step is performed by the signer. We input the public parametersparams, the signer’s identity ID, the partial private key D, and the signer’s secret value. We output the private key sk.(4)
Set public key: this step is performed by the signer. We input the public parameterparams and the signer’s secret value and output the public key pk.(5)
Sign: this step is performed by the signer. We input public parametersparams, message m, the signer’s ID, the private key sk, and the public key pk and output the signature σ.(6)
Verify: this step is performed by the verifier. We input public parametersparams, message m, signer ID, the public key pk, and the signature σ and, finally, output Verifym,σ,params,ID,pk⟶true or false.


### 3.7. Security Model of CLS

As mentioned in [37, 38], traditional security controls and detection systems are often tailored against external threats, but insider attacks are also an ever-increasing threat to a system with dire consequences. For comprehensive consideration of safety, in a certificateless cryptosystem, external adversary and internal adversary A1 and A2 can be assumed [12]. At first, there are normal and strong adversaries in ROM. In [39], the adversary is expanded and classified into normal, strong, and super three levels. Through oracle queries, a normal adversary can only obtain the valid signature of the entity with the original public key. If the entity’s public key is replaced, the normal adversary cannot obtain a valid signature. If the public key of a strong adversary has been replaced, the adversary cannot obtain a valid signature until providing the associated secret value of the new public key. A super adversary can obtain the valid signature of the entity whose public key has been replaced without the new secret value. Here, we consider the case of super adversary attacks.The first type of adversaryA1: these kinds of adversaries are also called external adversaries. The adversary can replace the public key of the target entity, but cannot obtain the master key of the KGC and partial private key of the entity.The second type of adversaryA2: these kinds of adversaries are also called internal adversaries. The adversary knows the master key of KGC and the partial private key, but cannot replace the public key of the target entity.


#### 3.7.1. Type-I Model

Setup: challengerC executes the algorithm to get the master secret key s and public parameters params. Then, C keeps s as secret and makes the parameters public.Queries:A1 adaptively asks one of the following queries to C.(1)
Public key extraction query:A1 obtains the public key pki of IDi(2)
Replace public key query:A1 replaces pki with pki′ which A1 chooses(3)
Private key extraction query:A1 obtains the private key ski of IDi(4)
Signature query:A1 obtains a valid signature σ for IDi,mOutput: finally,A1 outputs a valid forgery σ∗ for IDi∗,m∗, where Verifym∗,σ∗,params,IDi∗,pki′⟶true


#### 3.7.2. Type-II Model

Setup: challengerC executes the algorithm to get the master secret key s and public parameters params. Then, C keeps s as secret and makes params public.Queries:A2 adaptively asks one of the following queries to C.(1)
Public key extraction query:A2 obtains the public key pki of IDi(2)
Partial private key extraction query:A2 obtains the partial private key Di of IDi(3)
Signature query:A2 obtains a valid signature σ for IDi,mOutput: finally,A2 outputs a valid forgery σ∗ for IDi∗,m∗, where Verifym∗,σ∗,params,IDi∗,pki⟶true.


## 3.1. S-IoT Architecture

The typical S-IoT architecture [3] is shown in Figure 2. The S-IoT architecture consists of three parts: space segment, ground segment, and user terminal. The space segment consists of a constellation of satellites. The ground segment mainly includes the ground stations and the control stations. The user terminal refers to various terminals which are mainly used to send and receive signals. Information security is an important issue in S-IoT. There may be malicious nodes attacking the S-IoT system through eavesdropping, forgery, tampering, and other means.Figure 2
S-IoT architecture [3].


## 3.2. Elliptic Curve

Elliptic curve cryptography (ECC) is a method of constructing cryptographic schemes from elliptic curves over finite fields. Elliptic curve cyphers can achieve the same strength with shorter keys than RSA; that is, elliptic curve cyphers have shorter key lengths but higher strength. In general, an elliptic curve cypher with a key length of 160 bits can achieve the same strength as RSA with a key length of 1024 bits.Letp be a large prime number of length λ, GF(p) represents a finite field, and an elliptic curve is a series of points satisfying the following equations:(1)G=x,y:y2=x3+ax+b,4a3+27b2modp≠0∪Oa,b∈GFp,where O represents the point at infinity.


## 3.3. Bilinear Pairing

Let the bilinear mapping bee:G1×G2⟶G2, where G1 and G2 are the additive cyclic group and the multiplicative cyclic group of order prime p, respectively. The generator of G1 is P. The bilinear map satisfies the following properties:(1)
Bilinearity:∀Q,W,Z∈G1; there are eQ,W+Z=eQ,W⋅eQ,Z and Q+W,Z=eQ,Z⋅eW,Z. Then, ∀a,b∈Zq∗, eaQ,bW=eQ,Wab(2)
Nondegenerate:∃P,Q∈G1,eP,Q≠1(3)
Computability:∀P,Q∈G1; there is a valid algorithm that can compute eP,Q


## 3.4. Elliptic Curve Computational Diffie–Hellman Problem (ECDHP)

GivenaP,bP∈G1,a,b,c∈Zq∗, where P is the generator of G1, it is hard to calculate abP∈G1.


## 3.5. Bilinear Diffie–Hellman Problem (BDHP)

GivenaP,bP,cP∈G1,a,b,c∈Zq∗, where P is the generator of G1, it is hard to calculate eP,Pabc∈G2.


## 3.6. Certificateless Signature

A certificateless signature scheme generally includes three entities: KGC, signer, and verifier. The general steps of the CLS are as follows:(1)
Setup: this step is performed by KGC. We input a security parameterl and output the system master key s and public parameter params. KGC securely keeps the system master key s and makes params public.(2)
Set partial private key: this step is performed by KGC. We input the system master keys, the public parameter params and the signer’s identity ID. Then, we output the partial private key D.(3)
Set private key: this step is performed by the signer. We input the public parametersparams, the signer’s identity ID, the partial private key D, and the signer’s secret value. We output the private key sk.(4)
Set public key: this step is performed by the signer. We input the public parameterparams and the signer’s secret value and output the public key pk.(5)
Sign: this step is performed by the signer. We input public parametersparams, message m, the signer’s ID, the private key sk, and the public key pk and output the signature σ.(6)
Verify: this step is performed by the verifier. We input public parametersparams, message m, signer ID, the public key pk, and the signature σ and, finally, output Verifym,σ,params,ID,pk⟶true or false.


## 3.7. Security Model of CLS

As mentioned in [37, 38], traditional security controls and detection systems are often tailored against external threats, but insider attacks are also an ever-increasing threat to a system with dire consequences. For comprehensive consideration of safety, in a certificateless cryptosystem, external adversary and internal adversary A1 and A2 can be assumed [12]. At first, there are normal and strong adversaries in ROM. In [39], the adversary is expanded and classified into normal, strong, and super three levels. Through oracle queries, a normal adversary can only obtain the valid signature of the entity with the original public key. If the entity’s public key is replaced, the normal adversary cannot obtain a valid signature. If the public key of a strong adversary has been replaced, the adversary cannot obtain a valid signature until providing the associated secret value of the new public key. A super adversary can obtain the valid signature of the entity whose public key has been replaced without the new secret value. Here, we consider the case of super adversary attacks.The first type of adversaryA1: these kinds of adversaries are also called external adversaries. The adversary can replace the public key of the target entity, but cannot obtain the master key of the KGC and partial private key of the entity.The second type of adversaryA2: these kinds of adversaries are also called internal adversaries. The adversary knows the master key of KGC and the partial private key, but cannot replace the public key of the target entity.


### 3.7.1. Type-I Model

Setup: challengerC executes the algorithm to get the master secret key s and public parameters params. Then, C keeps s as secret and makes the parameters public.Queries:A1 adaptively asks one of the following queries to C.(1)
Public key extraction query:A1 obtains the public key pki of IDi(2)
Replace public key query:A1 replaces pki with pki′ which A1 chooses(3)
Private key extraction query:A1 obtains the private key ski of IDi(4)
Signature query:A1 obtains a valid signature σ for IDi,mOutput: finally,A1 outputs a valid forgery σ∗ for IDi∗,m∗, where Verifym∗,σ∗,params,IDi∗,pki′⟶true


### 3.7.2. Type-II Model

Setup: challengerC executes the algorithm to get the master secret key s and public parameters params. Then, C keeps s as secret and makes params public.Queries:A2 adaptively asks one of the following queries to C.(1)
Public key extraction query:A2 obtains the public key pki of IDi(2)
Partial private key extraction query:A2 obtains the partial private key Di of IDi(3)
Signature query:A2 obtains a valid signature σ for IDi,mOutput: finally,A2 outputs a valid forgery σ∗ for IDi∗,m∗, where Verifym∗,σ∗,params,IDi∗,pki⟶true.


## 3.7.1. Type-I Model

Setup: challengerC executes the algorithm to get the master secret key s and public parameters params. Then, C keeps s as secret and makes the parameters public.Queries:A1 adaptively asks one of the following queries to C.(1)
Public key extraction query:A1 obtains the public key pki of IDi(2)
Replace public key query:A1 replaces pki with pki′ which A1 chooses(3)
Private key extraction query:A1 obtains the private key ski of IDi(4)
Signature query:A1 obtains a valid signature σ for IDi,mOutput: finally,A1 outputs a valid forgery σ∗ for IDi∗,m∗, where Verifym∗,σ∗,params,IDi∗,pki′⟶true


## 3.7.2. Type-II Model

Setup: challengerC executes the algorithm to get the master secret key s and public parameters params. Then, C keeps s as secret and makes params public.Queries:A2 adaptively asks one of the following queries to C.(1)
Public key extraction query:A2 obtains the public key pki of IDi(2)
Partial private key extraction query:A2 obtains the partial private key Di of IDi(3)
Signature query:A2 obtains a valid signature σ for IDi,mOutput: finally,A2 outputs a valid forgery σ∗ for IDi∗,m∗, where Verifym∗,σ∗,params,IDi∗,pki⟶true.


## 4. Proposed CSP Scheme

Our proposed scheme, CSP, is as follows:Setup (KGC): the function of KGC is completed by the network control center (NCC) on the ground. KGC inputs security parameterk and selects elliptic curve addition cyclic group G1 and multiplication cyclic group G2 with order q. The generator of G1 is P. We set up bilinear mapping e:G1×G1⟶G2. KGC selects a random number s∈Zq∗ as the system master key and calculates Ppub=s⋅P as the system public key. KGC selects a secure hash function H1:0,1∗⟶Zq∗. KGC securely saves the master key s and makes the parameter params=q,G1,G2,e,P,Ppub,H1 to the public.Set partial private key (KGC): after KGC receivesIDi from the entity(the satellite or the user on the ground) Si, it calculates Qi=H1IDi and then calculates the partial private key Di=sQiP of Si.Set public/private key (entity): KGC sendsDi to Si. Si randomly selects the secret value xi,xi′∈Zq∗, and then calculates Xi=xiP, Qi=H1IDi, and Zi=xi′P,Yi=xiPpub. We take Xi,Yi as the public key pki and take Di,Zi as the private key ski.Sign (entity): whenSi needs to sign a message m, the specific description is as follows:(1)
Si randomly selects a large integer a∈Zq∗(2)
Si calculates Mi=xi2H1m∈Zq∗(3)
Si calculates Ni=axi′Qi∈Zq∗(4)
Si calculates si=eMiDi,Zia(5)
Si sends σi=m,Ni,si as a signatureVerify (entity): when another entitySj receives the message m with the signature σi, it uses the public key pki of Si to verify the signature. The specific description is as follows:(1)
Sj calculates Mj=H1m∈Zq∗.(2)
Sj calculates eMjNiXi,Yi.(3)
Sj verifies that si=sj. If the equation holds to prove that the signature is valid; otherwise, the verification fails, the message is discarded, and a reauthentication message rm is returned.Correctness analysis:(2)si=eMiDi,Zi=eP,PaMisQixi′=eP,PaH1msQixi′xi2=eH1maxi′QixiP,sxiP=eMjNiXi,Yi=sj.As shown in Figure 3, the steps of interaction between satellite nodes are as follows:Step 1 (KGC): KGC generates system parametersparams=q,G1,G2,e,P,Ppub,H1 to the public. Then, KGC calculates partial private keys. KGC sends partial private keys to the corresponding satellites. In this scene, we take satellites Si, Sj, and Sk as an example.Step 2 (Si, Sj, Sk): Si randomly selects the secret value xi,xi′∈Zq∗, and then calculates Xi, Qi, Zi, Yi and Xi′, Qi′, Zi′, Yi′. We take Xi,Yi as the public key pki. We take Xi′,Yi′ as the public key pki′. We take Di,Zi as the private key ski. We take Di,Zi′ as the private key ski′.Step 3 (Si): when Si needs to sign a message m, Si generates σi=m,Ni,si as the signature of the message m to Sj and generates σi′=m′,Ni′,si′ as the signature of the message m′ to Sk.Step 4 (Sj, Sk): when satellites Sj and Sk receive the message m and m′ with the signature σi and σi′, Sj uses the public key pki to verify the signature σi and Sk uses the public key pki′ to verify the signature σi′.As shown in Figure4, the steps of interaction between satellite and ground nodes are as follows:Step 1 (KGC): KGC generates system parametersparams=q,G1,G2,e,P,Ppub,H1 for the public. Then KGC calculates partial private keys. KGC sends partial private keys to the corresponding satellite and ground nodes. In this scene, take the satellite Si and the ground node Sj as an example.Step 2 (Si,Sj): Si randomly selects the secret value xi,xi′∈Zq∗, and then calculates Xi, Qi, Zi, and Yi. Sj randomly selects the secret value xj,xj′∈Zq∗, and then calculates Xj, Qj, Zj, and Yj.We take Xj,Yj as the public key pkj and take Dj,Zj as the private key skj.Step 3 (Si): Si generates σi=m,Ni,si as the signature.Step 4 (Sj): when the ground node Sj receives the message m with the signature σi, it uses the public key pki of Si to verify the signature σi.Figure 3
Interaction between satellite nodes.Figure 4
Interaction between the satellite and ground nodes.


## 5. Security Analysis

Lemma 1.
Under the attack of the first type of super adversaryA1, it is assumed that A1 can adaptively perform qH for H1 oracle queries, qd for partial private key extraction queries, qsk for private key extraction queries, qpk for public key extraction queries, and qs for signature queries; there is an algorithm C that can solve the ECDHP problem with the advantage of ε′≥ε1/qH1−1/qHqsk+qpk.Proof.
LetA1 be a super adversary, and we assume that the challenge for C is to know that Zi=xi′P (which can be obtained in the private key query below), and aP,a∈Zq∗. C calculates axi′P after interacting with A1. We play the game as follows:Game 1: challengerC inputs the security parameter l, runs the system establishment algorithm to generate the system master key s and system parameter params, then sends the params to A1, and saves s in secret.After going through all the queries,A1 outputs a forged signature m∗.N∗,S∗; if the forgery meets the following requirements, the super adversary A1 is considered to win.(1)
A1 has never submitted ID∗,m∗ to the signature oracle(2)
A1 never submitted ID∗ to partial private key oracles(3)
Verifym∗,σ∗,params,ID∗,pki′⟶trueH1 oracle query: C maintains a list LH1 consisting of triples IDi,Qi,Mi, and the list is initially empty. When A1 asks C for H1 with identity IDi, if IDi has been stored in LH1, then C returns the corresponding value to A1; otherwise, C calculates Qi=nP,n∈Zq∗; let Mi=ri,ri∈Zq∗; we insert the new tuple IDi,Qi,Mi into the list LH1 and return to A1.Setup:C runs the system algorithm, selects a generator P, and calculates Ppub=sP, where s is the system master key that C does not know; in this game, C randomly selects an identity ID∗, generates system parameters params=P,Ppub,H1, and send to A1.Public key extraction query:C maintains a list Lpk consisting of triples IDi,xi,pki, and the list is initially empty. When A1 inputs IDi to ask, if IDi has been stored in Lpk, C returns the corresponding value to A1; otherwise, C calculates Xi=xiP,Y=xiP,x∈Zq∗ and returns the value to pki. Then, C inserts IDi,xi,pki into the list Lpk.Public key query: whenA1 enters IDi,pki query, if the tuple IDi,xi,pki corresponding to IDi exists in the list Lpk, C sets pki=pki′ and sets IDi,xi,pki and returns the list Lpk; otherwise, C performs the public key generation step to generate IDi,xi,pki, then sets pki=pki′, and returns IDi,xi,pki′ to the list Lpk.Private key extraction query:C maintains a list Lsk consisting of four tuples IDi,xi′,ski,Zi, and the list is initially empty. When A1 asks with IDi, if IDi has been stored in Lsk, C returns the corresponding value to A1; otherwise, C calculates Z=xi′P,xi′∈Zq∗, and converts the new tuple IDi,xi′,ski,Zi which is inserted into the list Lsk and returned to A1.Signature query: whenC receives a IDi,mi signature query, it performs the following steps:(1)
IfID=ID∗, C aborts the query and outputs an error; otherwise, C queries IDi,xi′,ski,Zi, IDi,xi,pki, IDi,Qi,Mi from Lsk,Lpk,LH.(2)
CalculateNi=axi′Qi∈Zq∗,a∈Zq∗(3)
Calculatesi=eMiDi,Zia, signs the message using Ni,si. C sends Ni,si to A1.A1 aborts the query and outputs the signature σ=N∗,S∗ of the identity IDi∗ on the message m∗, which satisfies the verification condition:(3)S∗=eV,V′=sj=eMj′NiXi,Yi=eMj′xiP,xiPpubaxi′Qi=eMj′xiP,xisPaxi′Qi=eMj′xi2sQiP,axi′P.It can be known thatV′=axi′P, which solves the ECDHP problem. Set events E1, E2 and E3 are as follows:E1: A1 goes through a series of queries and C does not abort.E2: A1 successfully forges a valid signature.E3: there is ID=ID∗ in forged signature.We setPrE2|E1≥ε, then obviously we have:(4)PrE1≥1−1qHqsk+qpk,PrE2|E1≥ε,PrE3|E1E2≥1qH.
It can be calculated thatC can solve the ECDHP problem with a nonnegligible probability: ε′≥ε1/qH1−1/qHqsk+qpk. This proof is unforgeable against adaptive selective message attacking the signature. Therefore, it is proved that the scheme can guarantee the authenticity and integrity of the message under the attack of the first type of super adversary A1.Lemma 2.
Under the attack of the second type of super adversaryA2, it is assumed that A2 can adaptively perform qH for H1 oracle queries, qd for partial private key extraction queries, qsk for private key extraction queries, qpk for public key extraction queries, and qs for signature extraction queries; there is an algorithm C that can solve the BDHP problem with the advantage of ε′≥ε1/qH1−1/qHqd+qpk.Proof.
LetA2 be a super adversary. We assume that the challenge for C is that given the master key s, Di=sQiP (which can be obtained in the partial private key query below), b=sQi,aPandcP,a,c∈Zq∗ an calculate S∗=eP,Pabc after interacting with A2.Game 2: challengerC inputs the security parameter l, runs the system establishment algorithm to generate the system master key s and system parameter params, then sends the params to A2, and saves s in secret.After going through all the queries,A2 outputs a forged signature m∗.N∗,S∗; if the forgery meets the following requirements, the super adversary A2 is considered to win.(1)
A2 has never submitted ID∗,m∗ to the signature oracle(2)
A2 never submitted ID∗ to private key oracles(3)
Verifym∗,σ∗,params,ID∗,pki⟶trueH1 oracle query: C maintains a list LH1 consisting of triples IDi,Qi,Mi, and the list is initially empty. When A2 asks C for H1 with identity IDi, if IDi has been stored in LH1, then C returns the corresponding value to A2; otherwise, C calculates Qi=nP,n∈Zq∗; let Mi=ri,ri∈Zq∗, and we insert the new tuple IDi,Qi,Mi into the list LH1, and return to A2.Setup:C runs the system algorithm, selects a generator P, and calculates Ppub=sP, where s is the system master key that C does not know; in this game, C randomly selects an identity ID∗, generates system parameters params=P,Ppub,H1, and sends to A2.Public key extraction query:C maintains a list Lpk consisting of triples IDi,xi,pki, and the list is initially empty. When A2 inputs IDi to ask, if IDi has been stored in Lpk, C returns the corresponding value to A2; otherwise, C calculates Xi=xiP,Y=xiP,x∈Zq∗ and returns the value to pki. Then, C inserts IDi,xi,pki into the list Lpk.Partial private key extraction query:C maintains a list LD, consisting of triples IDi,Qi,Di, and the list is initially empty. When A2 asks C with identity IDi, if ID=ID∗, C aborts and outputs an error; otherwise, if IDi has been stored in LD, C returns the corresponding value to A2; if IDi is not stored in LD, then C extracts the tuple IDi,Qi,Mi from the list LH, calculates Di=sQiP, and returns it to A2.Signature query: whenC receives a IDi,mi signature query, it performs the following steps:(1)
IfID=ID∗, C aborts the query and outputs an error; otherwise, C queries IDi,Qi,Mi, IDi,xi,pki, IDi,Qi,Mi from LD,Lpk,LH(2)
We calculateNi=axi′Qi∈Zq∗,a∈Zq∗(3)
We calculatesi=eMiDi,Zia and sign the message using Ni,si. C sends Ni,si to A2A2 aborts the query and outputs the signature σ=N∗,S∗ of the identity IDi∗ on the message m∗, which satisfies the verification condition:(5)S∗=eV,V′=si=eMiDi,Zi=eP,PaNisQixi′xi2.The premise that the signature satisfies the verification conditions is the parameterc=Nixi′xi2 which is known to A2. Thus, A2 can calculate S∗=eP,Pabc which solves the BDHP problem. We set events E1, E2, and E3 are as follows:E1: A2 goes through a series of queries and C does not abort.E2: A2 successfully forges a valid signature.E3: there is ID=ID∗ in forged signature.We setPrE2|E1≥ε; then, obviously we have(6)PrE1≥1−1qHqd+qpk,PrE2|E1≥ε,PrE3|E1E2≥1qH.
It can be calculated thatC can solve the BDHP problem with a nonnegligible probability: ε′≥ε1/qH1−1/qHqd+qpk. This proof is unforgeable against adaptive selective messaging attacks on the signature. Therefore, it is proved that the scheme can guarantee the authenticity and integrity of the message under the attack of the second type of super adversary A2.
The above is a formal analysis in the ROM, which can ensure the strong security of CSP. The informal analysis is as follows.
Authenticity: CSP can realize the authentication of the message source and the authentication of the communication entity. This is determined by adding the identity information of the communication entity in the signature.
Integrity: CSP can guarantee that data have not been tampered with or damaged. This is determined by adding a hash function to the message in the signature. Once the message is changed, the corresponding hash function will change, which will result in authentication failure.
Unforgeability: CSP means that nobody except the communication entity itself can forge the signature. This is determined by the private key generation method of CSP. Only the ground KGC knows the secret value that generates the partial private key and only the communication entity itself knows the complete private key.
Nonrepudiation: CSP requires that neither the sender nor the receiver can deny the transmission. This is determined by adding the identity information of the sender in the signature. Besides, the receiver must reply with a message indicating whether the verification was successful.


## 6. Performance Evaluation

In this section, we test the performance of CSP. We compare CSP with existing representative CLS schemes. To ensure a benchmark for comparison, CSP uses widely accepted parameters. The program runs on a virtual machine with an Intel(R) Core(TM) i7-9750H-CPU@2.60 GHz and 16 GB of RAM, using the Ubuntu18.04LT operating system. Using the Type-A type in the PBC library, its security level is comparable to that of 1024 bit RSA. The Type-A of this library is constructed on the elliptic curvey2=x3+x in the finite field GF(p), where p is a large prime number of 160 bits. Assuming the message length is 128 bits.Table2 shows the time required for various operations in the simulation environment of this study. We can see that the bilinear pairing operation takes the longest, followed by the hash operation and the point multiplication operation. Since the scalar addition and multiplication operations take negligible time compared to other operations, we ignore the overhead of these two types of operations in the comparison. The value in the table is the average time of each operation 100 times.Table 2
Symbol description and operation time.
SymbolOperationTime (ms)TrGenerating a random number0.120ThA hash operation1.943TpmA point multiplication operation0.886TaddA scalar addition operation0.001TmA scalar multiplication operation0.001TpA bilinear pairing operation1.962Table3 shows the efficiency comparison of CLS schemes for satellite-to-satellite nodes. In S-IoT, we first consider the case of authentication between satellite nodes. Since each satellite node provides services for massive ground nodes, we believe that the authentication of satellite nodes requires high security. Therefore, we consider that when a satellite wants to authenticate with other satellites, it needs to use different public and private keys. It mains that the satellite node Si uses ski,pki for authentication with the satellite node Sj, while Si uses ski′,pki′ for authentication with the satellite node Skj≠k. In S-IoT, the roles of users and signers who generate public and private keys can only be assumed by the satellite itself, which cannot be delegated to a third party. Therefore, when calculating the overhead of the signing in this case, the overhead of generating public and private keys is included. Due to the difference in algorithms between CLS schemes with bilinear pairings and those without, the CLS schemes without bilinear pairings often include the point addition operation and the modular inverse operation. However, the time of these two operations is relatively short. For a more intuitive comparison, these two operations are ignored here.Table 3
Comparison of CLS schemes for satellite-to-satellite nodes.
SchemeSignVerifyTypeSecurity againstA1Security againstA2Signature sizeDu’s et al. [34]3Tpm+3Th+2Tr4Tpm+3ThWithout bilinear pairsSuperSuperG1+Zq∗Thumbur’s et al. [35]3Tpm+2Th+2Tr3Tpm+2ThWithout bilinear pairsInsecureSuperG1+Zq∗Xu’s et al. [36]3Tpm+3Th+3Tr4Tpm+3ThWithout bilinear pairsSuperSuperG1+Zq∗Hassouna’s et al. [31]4Tpm+3Th+1Tp+3Tr4Tp+1ThWith bilinear pairsInsecureStrongG1+G2CSP5Tpm+2Th+1Tp+3Tr1Tp+1Tpm+1ThWith bilinear pairsSuperSuperG1+Zq∗The values of security againstA1 and A2 are determined according to which level of adversary attack (normal, strong, and super) the corresponding scheme can resist in ROM. Among these schemes, it is mentioned in [36] that the scheme in [35] was vulnerable to signature forgery attacks and was insecure against A1, and the scheme in [31] has recently been shown to be insecure in the face of the attack of A1.It can be seen from Figure5 that, in the simulation environment of this study, except for the unsafe schemes in the table, the scheme in [34] has the shortest time of 8.727 ms when signing. CSP needs 10.638 ms for signing, which is in the middle level of these schemes. However, in the verification and total time comparison, the overhead of CSP is the smallest, which are 4.681 ms and 15.319 ms. Compared with the scheme in [34], CSP improves the efficiency by about 50% and 15%, respectively. In the CLS schemes with bilinear pairs, CSP has the smallest overhead in both the signature and verification phases, which improves efficiency by about 9% and 60%, respectively. Besides, CSP can prove a higher level of security. The reason is that the scheme in [31] does not fully use the user’s public key when verifying the signature. It only uses part of the public key, which leads to the additional verification if the public key is authentic and valid. The authenticity and validity of the public key will increase the overhead of the bilinear pairing operations.Table4 shows the efficiency comparison of CLS schemes for satellite-to-ground nodes. When the satellite node is authenticated with the ground node in S-IoT, it is troublesome and resource-consuming to frequently update the public and private keys. Therefore, when the satellite Si is authenticated with the ground node, it only uses ski,pki.Table 4
Comparison of CLS schemes for satellite-to-ground nodes.
SchemeSignVerifyTypeSecurity againstA1Security againstA2Signature sizeDu’s et al. [34]1Tpm4Tpm+3ThWithout bilinear pairingsSuperSuperG1+Zq∗Thumbur’s et al. [35]1Tpm3Tpm+2ThWithout bilinear pairingsInsecureSuperG1+Zq∗Xu’s et al. [36]1Tpm+2Th4Tpm+3ThWithout bilinear pairingsSuperSuperG1+Zq∗Hassouna’s et al. [31]1Tpm+1Th+1Tp4Tp+1ThWith bilinear pairingsInsecureStrongG1+G2CSP1Tpm+1Th+1Tp1Tp+1Tpm+1ThWith bilinear pairingsSuperSuperG1+Zq∗We can see from Figure6 that the scheme in [34] has the shortest times of 0.886 ms in the signing phase, except for the unsafe scheme. CSP needs 4.791 ms, which is similar to the schemes in [31, 36]. In the verification phase and total time comparison, CSP still has the best performance, which improves efficiency by about 50% and 7%, respectively.Finally, we discuss the issue of CSP complexity. For the scenario in Figure5, to complete the authentication between satellite nodes, three authentication messages need to be transmitted. The communication cost of each authentication message is 480 bits. The signature cost is 10.638 ms, and the verification cost is 4.681 ms. For the scenario in Figure 6, three authentication messages between the satellite and the ground node need to be transmitted. The communication cost of each authentication message is 480 bits. The signature cost is 4.971 ms. The verification cost is 4.681 ms. The CSP performance is shown in Table 5.Figure 5
Comparison of CLS schemes for interaction between satellite nodes.Figure 6
Comparison of CLS schemes for interaction between satellite-to-ground nodes.Table 5
CSP performance.
ScenarioThe number of transmitted authentication messagesComputational operationsTotal cost (ms)Communication cost (bits)Satellite-to-satellite nodes36Tpm+3Th+2Tp+3Tr15.319480Satellite-to-ground nodes32Tpm+2Th+2Tp9.472480


## 7. Conclusions and Future Work

Due to the special environment and restricted resources, the security solution used by the terrestrial network for communication cannot be directly applied to the S-IoT. This study proposes a strong, secure certificateless signature scheme with bilinear pairings named CSP, which is suitable for S-IoT. Before the satellite is connected to the space-based network, the manufacturer or the company that undertakes the work of KGC inputs the partial private key and public parameters to the satellite. The satellite uses its own identity information and secret value to calculate the public key, the private key, and the signature. CSP can ensure the authenticity, integrity, unforgeability, and nonrepudiation of transmitted messages. The CSP solves the problems of complicated certificate management in the traditional PKI system key escrow in the IBC system. In the future, the secure access of satellites facing a large number of ground nodes is an important issue. In recent years, an ultra-super-fast authentication protocol for electric vehicles, charging by utilizing the characteristics of extended chaotic maps, has been proposed in [40] which can resist man-in-the-middle attacks, replay attacks, and impersonation attacks. This work provides us with new ideas on how to perform rapid authentication when considering a large number of nodes that want to access satellites. Besides, analysis shows that compared with similar schemes, CSP can achieve a higher security level and lower overhead. However, CSP still needs a relatively long time in the signature phase, which is the research direction of future work.



---

*Source: 5818879-2022-11-15.xml*