# A Novel RLWE-Based Anonymous Mutual Authentication Protocol for Space Information Network

Authors: Junyan Guo; Ye Du
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Currently, space information network (SIN) has become an increasingly important role in real life. As a large heterogeneous wireless network, SIN can better provide global mobile services to users anytime and anywhere, even in extreme geographic environments. In addition, there is no need to build the communication base-stations every few kilometers on the ground to ensure high service quality, which greatly reduces the construction costs and can be used as an economical communication method in sparsely populated areas. So there is a trend that more and more end users are more likely to get SIN services than traditional terrestrial cellular networks. However, due to the openness and publicity of the satellite wireless channel and the limited resources of the satellite nodes, the privacy and security cannot be perfectly guaranteed and may even be vulnerable to attacks initiated by the adversary such as replay attacks, impersonation attacks, and eavesdropping attacks. To improve the access security of SIN, researchers have proposed a series of authentication protocols based on different cryptographic assumptions. Nevertheless, existing research shows that these protocols cannot meet the requirements of higher and higher security and short authentication delay. In addition, these protocols are mainly based on public key cryptography mechanisms such as DLP and ECDLP, which can be solved by postquantum computers in polynomial time, so these protocols will no longer be secure. To solve the vulnerability of these protocols, in this paper, we propose a new RLWE-based anonymous mutual authentication and key agreement protocol, which guarantees higher security with low computational overhead even in the postquantum era. Detailed security analysis shows that our protocol meets security requirements and is resistant to a variety of known attacks. Besides, combining security comparison and performance analysis, our proposed protocol is more practical than other protocols in SIN.


---

## Body

## 1. Introduction

With the continuous development of globalization, users are increasingly demanding communication and are required to establish high-quality communication connections with others. In this context, SIN is proposed to meet the needs of users for reliability and availability globalization services [1]. As a large heterogeneous network covering the globe, SIN includes various satellite constellations to provide navigation, communication, weather, reconnaissance, and other services for numerous users. In the future, SIN will not only serve the Earth users, but also serve space satellites and interstellar spacecraft with advanced space technology [2]. Compared with traditional terrestrial cellular networks, SIN has the following three characteristics [3]. First, SIN covers a wider range and can provide the stable signal in cities, villages, and even extreme environments. Second, as long as the device has the ability to communicate with satellites, it can join SIN as an end user or service provider anywhere in the world, which greatly improves scalability. Third, SIN does not require the laying of large amounts of ground facilities like a terrestrial network, and the signals are not affected by the terrain. SIN is a scarce resource for present and future, so the United States and Europe have carried out a series of key national research projects such as Thuraya [4], MUOS [5], ISICOM [6], and TSAT [7].As a key communications architecture in marine, aerospace, military, and remote IoT applications, confidential and internal information will be transmitted to each other through SIN wireless channels [3]. Because security is not a primary concern when initially deploying SIN, the current research on security is still insufficient. At present, researchers have begun to shift from researching the functional requirements to the security requirements, and access authentication is the focus of their research [8, 9]. Accessing authentication is the first step for the end user to apply for service to the satellite node; it is even more necessary to take some light mechanisms to ensure the security and the quality of service (QoS). There are two key factors affecting the security and performance of the authentication protocol: one is the openness of the satellite wireless channel, the public channel will result in data being easily captured by adversaries, and the cryptographic mechanism should be used to resist the attack initiated by the malicious node. The other is the authentication delay caused by messages transmission and computing overhead. For delay-sensitive users who require real-time communication, the authentication delay should be as small as possible, even if the signal delay caused by satellites located 500 to 3,000 kilometers above the ground is unavoidable.Currently, hardware technology is developing rapidly, and satellites can already carry more complex computing devices [10]. The three-party or two-party authentication protocols proposed in other research areas can provide a reference for designing authentication protocols suitable for SIN but cannot be directly applied. For example, in mobile pay-TV systems, [11] proposes a time slot-based key distribution mechanism that divides 24 hours by 45 minutes and arranges them in a binary tree. Service providers can provide up to 16 communication keys for a single user. However, when the number of users increases, it will occupy a lot of storage space of the service provider, which is not suitable for satellite with shortage of resources. In global mobility networks, [12] proposed a roaming authentication scheme based on the chaotic map-based discrete logarithm problem (CMBDLP). When a user and the foreign agent authenticate with each other, they need to transfer information four times with the participation of home agent, which increases the user's waiting time, and this does not meet the SIN low-latency requirement. Other scholars have also proposed many authentication protocols based on difficult problems such as elliptic curve discrete logarithm problem (ECDLP) [13], discrete logarithm problem (DLP) [14], large integer factorization problem (LIFP) [15, 16], and hash function [17], but these protocols still cannot be directly applied to SIN unless high security and efficiency are not considered. Furthermore, with the advent of the postquantum era, most authentication protocols that rely on public key cryptography have the potential to be resolved in polynomial time. So these authentication protocols may present security risks in the future. Therefore, this paper proposes a novel RLWE-based anonymous mutual authentication protocol for space information network, which can meet the requirements of high security and efficiency. In our protocol, LEO satellites serve as nodes that end users want to access. Terrestrial control station (TCS) provides system registration services for end users and LEO satellites. In the process of mutual authentication between the end user and the LEO satellite, the temporary identity is used so that the true identity is not revealed, and TCS does not participate in the authentication process as an offline node, which greatly reduces the authentication delay. In addition, the authentication protocol is based on the RLWE assumption which has been shown to be as difficult as the worst-case problem in the ideal lattice [18] and is also resistant to quantum computing with less computational overhead [19]. It is worth mentioning that our proposed protocol has the following main contributions:(1)
We propose a novel RLWE-based anonymous mutual authentication protocol that enables both the end user and the LEO satellite to authenticate each other. In addition, TCS does not participate in the authentication process, which greatly reduces the communication delay to better meet the needs of delay-sensitive users.(2)
This is the first anonymous authentication protocol for antiquantum computing in SIN. Moreover, in this paper, detailed security analysis proves that our protocol can meet the security requirements based on the well-known Dolev–Yao threat model [20] and resist various attacks by adversaries.(3)
Considering the linkability of the user identity may be known by the adversary with background knowledge during the temporary identity transmission process, our protocol allows the end user to apply for a new temporary identity from TCS in the public channel, which enhances anonymity and unlinkability.The rest of this paper is organized as follows: in Section2, we first briefly discuss related work. Then we show the background information related to the protocol in Section 3. In Section 4, we describe the proposed protocol in detail. Detailed analysis of the security and performance of the proposed protocol is provided in Sections 5 and 6, respectively. Finally, Section 7 presents the conclusion of this paper.


## 2. Related Work

In recent years, researchers have been enthusiastic about security and privacy issues in the authentication protocol for space information network (SIN). In 1996, Cruickshank [21] proposed the first authentication protocol in satellite networks using the public key cryptosystem to authenticate the legitimate identity of the end user and the satellite, respectively, and uses the symmetric key system to encrypt the communication data. However, the protocol requires terrestrial control station (TCS) to participate during the authentication process, which results in a large delay in the authentication process, and the use of four complicated encryption and decryption operations results in large computational overhead. Then Hwang et al. [22] proposed an authentication protocol that uses the symmetric key to encrypt the message transmission in the mutual authentication phase without the need for a public key mechanism. Although the computational overhead is reduced, the shared key in each authentication is only determined by the TCS, and the end user does not participate in generating the shared key, without enabling the end user to trust the security of the shared key. To overcome the weaknesses in [22], Chang and Chang [23] proposed an authentication scheme with only hash functions and XOR operations. This scheme greatly reduces the computational complexity and ensures that the shared key is jointly generated by both parties, but still cannot overcome the problem of TCS participating in the authentication process which will result in the increase of TCS computing load and a large delay of authentication. In 2012, Zheng et al. [24] proposed a more effective protocol to reduce the computational complexity of TCS, but proved in [25] that [24] cannot resist the denial of service (DoS) attack and the identity spoofing attack. Recently, Yang et al. [10] proposed a new anonymous fast authentication protocol based on the q-SDH problem and elliptic curve digital signature algorithm (ECDSA) for authenticating roaming users in foreign domains. In the authentication stage, the protocol does not compromise the anonymity of the user’s identity and can resist replay attacks, man-in-the-middle attacks, and modification attacks. Unfortunately, the protocol does not have user login authentication, which will result in that if the user’s device is stolen, the adversary can use the user's device to impersonate as a legitimate user. Besides, in the postquantum era, the difficult problems that [10] relies on have been proven to be resolved in polynomial time, and the anonymity and communication security will be invalid. Feng et al. [26] first proposed an anonymous authentication protocol based on ideal lattices and resistant to quantum computing. However, there are two defects in [26] that cannot be applied. First, when the adversary intercepts the message sent by the user in authentication phase and the message is directly replayed or modified, then the server will spend a lot of computational overhead to check whether it is a legitimate message. If the adversary sends a large number of forged authentication messages, it will consume a lot of system resources. Secondly, server provides both registration and user authentication functions, while satellite nodes in SIN cannot simultaneously undertake heavy computing and storage tasks due to limited resources. In summary, previous authentication protocols based on hash or classic hard problems cannot meet the anonymity, security, and low-latency requirements. Therefore, in this paper, we design an access authentication and key agreement protocol, which can guarantee the anonymity of users and has lower transmission delay.


## 3. Preliminaries

In this section, we give a review of background information and the notations on RLWE and then briefly describe the system model and threat model that the protocol relies on. Finally, the security requirements are presented.


### 3.1. Ring Learning with Errors

Letn=2k, where k∈ℤ. The rings of polynomials over ℤ and ℤq, respectively, are denoted by ℤx and ℤqx, where q is an odd prime number and qmod2n=1. Consider the two rings ℝ=ℤx/xn+1 and ℝq=ℤqx/xn+1. For any polynomial element y in ℝ or ℝq, denote it by its coefficient vector in ℤn and ℤqn, respectively. Given a fixed positive real β , the discrete Gaussian distribution over ℝq is denoted by χβ . We refer to [19, 27, 28] for a more description of RLWE with the following lemmas.Lemma 1.
For any two elementsa,b∈ℝ, there exist a⋅b≤n⋅a⋅b and a⋅b∞≤n⋅a∞⋅b∞.Lemma 2.
Given any positive realβ=ωlogn, the PrX←χβX>β⋅n≤2−n+1[29].For an odd primeq>2, let ℤq=−q−1/2,…,q−1/2 and the subset E=−⌊q/4⌋,…,⌊q/4⌋ as the middle set of ℤq. For any x∈ℤq, the characteristic function Cha of the set E complement is defined as(1)Chax=0,x∈E,1,x∉E.The auxiliary modular functionMod2:ℤq×0,1⟶0,1 is defined as Mod2v,b=v+b⋅q−1/2modqmod2, where v∈ℤq and b=Chav, with the following lemma for these two functions.Lemma 3.
Given an odd prime numberq, we have two ring elements v, e∈ℤq such that e<q/8. Then, the equation Mod2v,chav=Mod2w,chav holds, where w=v+2⋅e.The two functionsCha and Mod2 can be extended to the ring ℝq by applying coefficients to ring elements and can also follow the lemmas mentioned above. Given a ring element v=v0,…,vn−1∈ℝq and b=b0,…,bn−1∈0,1n, we have Chav=Chav0,…,Chavn−1 and Mod2v,b=Mod2v0,b0,…,Mod2vn−1,bn−1. Then, for w=v+2⋅e, we have Mod2w,Chaw=Mod2v,Chaw, where the absolute value of each element in e is less than q/8 [30].Definition 1.
Ring learning with errors (RLWE) assumption: letℝq and χβ be defined as above. v, e are randomly selected from ℝq and χβ, respectively. The RLWE assumption states that it is hard for any PPT algorithm to distinguish ℝq×χβ from the uniform distribution on ℝq2 . The hardness of the RLWE assumption can be reduced to the Shortest Independent Vectors Problem (SIVP) over ideal lattices [31].


### 3.2. System Model

As shown in Figure1, SIN contains a total of three types of entities: terrestrial control station (TCS), satellite node, and end user. The following details describe the functions of each entity.(i)
TCS is a control center to provide registration services to end users and satellite nodes. Moreover, TCS is considered a trusted entity with the highest level of firewall and intrusion detection system. Any attack can be detected and taken with corresponding security measures to prevent attacker from intruding into TCS.(ii)
Satellite node is the service provider for end users in SIN. In order to reduce the delay of users accessing SIN, LEO satellites that are closer to the ground are usually used. LEO satellites are not all legal service providers, and there may be some LEO satellites controlled by malicious adversaries.(iii)
End user is user with the smart device and has the ability to compute, store, and communicate with satellites. The end user will request access to the SIN to get the subscribed service. It needs to be reminded that the smart device is at risk of being lost or stolen.Figure 1
Space information network.


### 3.3. Threat Model

In our protocol we make use of the Dolev–Yao threat model, which means that the adversary will control all openness and public channels in SIN. The adversary can arbitrarily monitor, intercept, modify, and replay messages transmitted between nodes and has unlimited storage space to store all the information monitored. The protocol we designed is to allow legitimate nodes to authenticate each other’s identity, deny illegal access, and ensure that secrets are not obtained by adversaries under the Dolev–Yao threat model.


### 3.4. Security Requirements

According to the characteristics of the previously proposed authentication protocol in SIN, a well-designed protocol should meet the following security requirements.


#### 3.4.1. Mutual Authentication

Satellite nodes should have the ability to verify the legal identity of the end user and prevent access by nonlegitimate users. Similarly, the end user should also have the same ability to verify access to legitimate satellites.


#### 3.4.2. Identity Anonymity

The identity of the end user should remain anonymous, and no one other than TCS and the end user himself can know the true identity of the user.


#### 3.4.3. Key Establishment

After successful mutual authentication of the satellite and the end user, they should jointly construct a shared key to protect future communication.


#### 3.4.4. Perfect Forward Secrecy

The authentication protocol also needs to meet the requirement that the shared key leakage does not lead to the previous and future session key leaks.


#### 3.4.5. Attack Resistance

In the authentication process, in order to ensure the accuracy and security of authentication, the protocol should be able to withstand various attacks initiated by the adversary such as replay attack, modification attack, eavesdropping attack, and impersonation attack.


## 3.1. Ring Learning with Errors

Letn=2k, where k∈ℤ. The rings of polynomials over ℤ and ℤq, respectively, are denoted by ℤx and ℤqx, where q is an odd prime number and qmod2n=1. Consider the two rings ℝ=ℤx/xn+1 and ℝq=ℤqx/xn+1. For any polynomial element y in ℝ or ℝq, denote it by its coefficient vector in ℤn and ℤqn, respectively. Given a fixed positive real β , the discrete Gaussian distribution over ℝq is denoted by χβ . We refer to [19, 27, 28] for a more description of RLWE with the following lemmas.Lemma 1.
For any two elementsa,b∈ℝ, there exist a⋅b≤n⋅a⋅b and a⋅b∞≤n⋅a∞⋅b∞.Lemma 2.
Given any positive realβ=ωlogn, the PrX←χβX>β⋅n≤2−n+1[29].For an odd primeq>2, let ℤq=−q−1/2,…,q−1/2 and the subset E=−⌊q/4⌋,…,⌊q/4⌋ as the middle set of ℤq. For any x∈ℤq, the characteristic function Cha of the set E complement is defined as(1)Chax=0,x∈E,1,x∉E.The auxiliary modular functionMod2:ℤq×0,1⟶0,1 is defined as Mod2v,b=v+b⋅q−1/2modqmod2, where v∈ℤq and b=Chav, with the following lemma for these two functions.Lemma 3.
Given an odd prime numberq, we have two ring elements v, e∈ℤq such that e<q/8. Then, the equation Mod2v,chav=Mod2w,chav holds, where w=v+2⋅e.The two functionsCha and Mod2 can be extended to the ring ℝq by applying coefficients to ring elements and can also follow the lemmas mentioned above. Given a ring element v=v0,…,vn−1∈ℝq and b=b0,…,bn−1∈0,1n, we have Chav=Chav0,…,Chavn−1 and Mod2v,b=Mod2v0,b0,…,Mod2vn−1,bn−1. Then, for w=v+2⋅e, we have Mod2w,Chaw=Mod2v,Chaw, where the absolute value of each element in e is less than q/8 [30].Definition 1.
Ring learning with errors (RLWE) assumption: letℝq and χβ be defined as above. v, e are randomly selected from ℝq and χβ, respectively. The RLWE assumption states that it is hard for any PPT algorithm to distinguish ℝq×χβ from the uniform distribution on ℝq2 . The hardness of the RLWE assumption can be reduced to the Shortest Independent Vectors Problem (SIVP) over ideal lattices [31].


## 3.2. System Model

As shown in Figure1, SIN contains a total of three types of entities: terrestrial control station (TCS), satellite node, and end user. The following details describe the functions of each entity.(i)
TCS is a control center to provide registration services to end users and satellite nodes. Moreover, TCS is considered a trusted entity with the highest level of firewall and intrusion detection system. Any attack can be detected and taken with corresponding security measures to prevent attacker from intruding into TCS.(ii)
Satellite node is the service provider for end users in SIN. In order to reduce the delay of users accessing SIN, LEO satellites that are closer to the ground are usually used. LEO satellites are not all legal service providers, and there may be some LEO satellites controlled by malicious adversaries.(iii)
End user is user with the smart device and has the ability to compute, store, and communicate with satellites. The end user will request access to the SIN to get the subscribed service. It needs to be reminded that the smart device is at risk of being lost or stolen.Figure 1
Space information network.


## 3.3. Threat Model

In our protocol we make use of the Dolev–Yao threat model, which means that the adversary will control all openness and public channels in SIN. The adversary can arbitrarily monitor, intercept, modify, and replay messages transmitted between nodes and has unlimited storage space to store all the information monitored. The protocol we designed is to allow legitimate nodes to authenticate each other’s identity, deny illegal access, and ensure that secrets are not obtained by adversaries under the Dolev–Yao threat model.


## 3.4. Security Requirements

According to the characteristics of the previously proposed authentication protocol in SIN, a well-designed protocol should meet the following security requirements.


### 3.4.1. Mutual Authentication

Satellite nodes should have the ability to verify the legal identity of the end user and prevent access by nonlegitimate users. Similarly, the end user should also have the same ability to verify access to legitimate satellites.


### 3.4.2. Identity Anonymity

The identity of the end user should remain anonymous, and no one other than TCS and the end user himself can know the true identity of the user.


### 3.4.3. Key Establishment

After successful mutual authentication of the satellite and the end user, they should jointly construct a shared key to protect future communication.


### 3.4.4. Perfect Forward Secrecy

The authentication protocol also needs to meet the requirement that the shared key leakage does not lead to the previous and future session key leaks.


### 3.4.5. Attack Resistance

In the authentication process, in order to ensure the accuracy and security of authentication, the protocol should be able to withstand various attacks initiated by the adversary such as replay attack, modification attack, eavesdropping attack, and impersonation attack.


## 3.4.1. Mutual Authentication

Satellite nodes should have the ability to verify the legal identity of the end user and prevent access by nonlegitimate users. Similarly, the end user should also have the same ability to verify access to legitimate satellites.


## 3.4.2. Identity Anonymity

The identity of the end user should remain anonymous, and no one other than TCS and the end user himself can know the true identity of the user.


## 3.4.3. Key Establishment

After successful mutual authentication of the satellite and the end user, they should jointly construct a shared key to protect future communication.


## 3.4.4. Perfect Forward Secrecy

The authentication protocol also needs to meet the requirement that the shared key leakage does not lead to the previous and future session key leaks.


## 3.4.5. Attack Resistance

In the authentication process, in order to ensure the accuracy and security of authentication, the protocol should be able to withstand various attacks initiated by the adversary such as replay attack, modification attack, eavesdropping attack, and impersonation attack.


## 4. Our Proposed Protocol

In this section we present a novel RLWE-based anonymous authentication protocol. The detailed protocol description will be introduced in the order of system initialization phase, registration phase, authentication phase, password update phase, and temporary identity update phase.


### 4.1. System Initialization Phase

In the system initialization phase, TCS generates the master key pair and some system public parameters according to the following steps:(1)
TCS sets system security parametersk(2)
TCS chooses an odd prime numberq and an integer n, where n is a power of 2 and qmod2n=1(3)
TCS chooses a discrete Gaussian distributionχβ and a random ring element a, where β is a fixed positive number and a∈ℝq(4)
TCS randomly sampless,e⟵χβ and computes the master public key pTCS=a⋅s+2⋅e, where s is the master private key(5)
TCS chooses a security hash functionh:0,1∗⟶0,1k(6)
TCS publishes the system parametersq,n,χβ,a,pTCS,h to the public and securely stores the master private key sThe system initialization phase is performed once when the system is laid out and not during other phases. Since it is only executed once, the computational overhead of the system initialization phase can be considered negligible.


### 4.2. Registration Phase

The registration phase is the process by which TCS interacts with trustworthy end users and satellite nodes. In this phase, the satellite and the end user need to submit the true identityID and other necessary parameters to TCS. It is worth noting that end users also need to generate the temporary identity TID that masks the true identity during the authentication phase. Then TCS generates the parameters needed for mutual authentication in the future for the end user and the satellite node, respectively. We briefly show this process in Figure 2 and the more detailed steps will be described in Algorithm 1 and the rest of this section. We assume that the satellite set is SLEO with N1 satellites and the end user set is Suser with N2 users. For a clearer presentation, in the following description, we simplify the system model with only one end user ui, one satellite LEOj, and TCS. Besides, it is necessary to note that the messages in this phase are transmitted in the secure channel.(1)
LEOj generates the true identity IDLj and computes the master public key pmLj=a⋅smLj+2⋅emLj, where smLj and emLj are randomly sampled from χβ. smLj is assumed to be the master private key and is stored securely by LEOj. Finally, LEOj sends the message IDLj,pmLj to TCS. It needs to be reminded that the identity of the IDLj satellite node is not private, so there is no need to anonymize it.(2)
ui generates the true identity IDui, temporary identity TIDui, and password PWui and then chooses the satellite node IDLj which it wants to communicate with. The function of PWui is used for login verification and it will be required in authentication phase, password update phase, and temporary identity update phase. Next, ui computes the master public key pmui=a⋅smui+2⋅emui, where smui and emui are randomly sampled from χβ. smui is assumed to be the master private key and is stored securely by ui. Then ui computes TWDui=hTIDui,PWui, which is to protect the PWui from being known by the TCS. Finally, ui sends the message IDui,TIDui,IDLj,TWDui,pmui to TCS.(3)
TCS computesDIui=hTIDui,s, DPui=DIui⊕TWDui, and Vui=hTIDui,TWDui,DPui after receiving the registration message of ui. Then TCS sends the messages DPui,Vui,pmLj to ui and TIDui,pmui to LEOLj. Vui is used to check if the temporary identity TIDui and password PWui entered are correct when ui logs into the smart device. The function of the DPui is to enable ui to update the password PWui as wishes and detailed in the password update phase. The function of DIui is to prevent ui from changing TIDui by himself. If ui is free to update the temporary identity TIDui, the legal identity of ui cannot be distinguished during the authentication phase. By binding the master private key s of the TCS to TIDui, even if ui attempts to update TIDui, it cannot change DIui, DPui, and Vui without TCS. Finally, TCS stores IDui,TIDui,pmui and IDLj,pmLj.(4)
ui stores the message DPui,Vui,pmLj.(5)
LEOj stores the message TIDui,pmui.Figure 2
Registration phase.Algorithm 1: Registration phase.
(1)
LEOj:(2)
Generates the true identityIDLj;(3)
Randomly samplessmLj,emLj and computes the master public key pmLj=a⋅smLj+2⋅emLj;(4)
Stores the master private keysmLj;(5)
SubmitsIDLj,pmLj to TCS;(6)
LEOj END(7)
ui:(8)
Generates the true identityIDui, temporary-ID TIDui, password PWui and chooses the satellite node IDLj;(9)
Randomly samplessmui, emui and computes the master public key pmui=a⋅smui+2⋅emui;(10)
ComputesTWDui=hTIDui,PWui;(11)
SubmitsIDui,TIDuI,IDLj,TWDui,pmui to TCS;(12)
ui END(13)
TCS:(14)
ComputesDIui=hTIDui,s, DPui=DIui⊕TWDui, Vui=hTIDui,TWDui,DPui;(15)
TransmitsDPui,Vui,pmLj to ui and TIDui,pmui to LEOj;(16)
StoresIDui,TIDui,pmui and IDLj,pmLj;(17)
TCS END(18)
ui stores DPui,Vui,pmLj;(19)
LEOj stores TIDui,pmui;


### 4.3. Authentication Phase

As shown in Figure3, in this phase, ui and LEOj mutually authenticate each other's legal identity in accordance with the following steps and negotiate a shared session key to encrypt future communications. It is worth noting that the three interactive messages are transmitted in the public channel and the messages are transmitted in plaintext.(1)
ui needs to input the temporary identity TIDui′ and password PWui' to login the smart device before requesting authentication. The device computes TWDui′=hTIDui′,PWui′, Vui′=hTIDui′,TWDui′,DPui. Then it checks whether Vui′=Vui. If they are not equal, the access request is terminated immediately; otherwise the following steps are continued according to the protocol. This process is to prevent the device from falling into the adversary and being disguised as ui. Next, the smart device computes kL=pmLj⋅smui, wL=ChakL, σL=Mod2kL,wL, and αL=hTIDui,wL,σL,ts1. Finally, ui sends the message TIDui,wL,ts1,αL to LEOj. ts1 is the timestamp used to prevent the replay attacks by the adversary. The rest of the timestamps in this paper have the same function as ts1.(2)
After receiving the messageTIDui,wL,ts1,αL, LEOj first checks the timestamp ts1 and compares it with the current time to see if it is within the time allowed. If the timestamp is not within the allowed range, the access request is denied; otherwise LEOj computes kL′=pmui⋅smLj, σL′=Mod2kL′,wL, and αL′=hTIDui,wL,σL′,ts1. Then it checks whether αL′=αL. If they are not equal, the end user who sent the access request is not legitimate and LEOj rejects the access request; otherwise the next steps of the authentication protocol are continued. Next, LEOj computes pLj=a⋅sLj+2⋅eLj and α0=hTIDui,wL,σL′,pLj,ts2, where sLj and eLj are randomly sampled from χβ. Finally, LEOj sends the message pLj,ts2,α0 to ui.(3)
After receiving the messagepLj,ts2,α0, ui first checks the timestamp ts2 and compares it with the current time to see if it is within the time allowed. If the timestamp is not within the allowed range, the access request is denied; otherwise ui computes α0′=hTIDui,wL,σL,pLj,ts2. Then ui checks whether α0′=α0. If they are not equal, ui will assume that the satellite requested to access during the authentication phase is not the true LEOj and actively stops the access request; otherwise it continues to compute pui=a⋅sui+2⋅eui, ki=pLj⋅sui, σi=Mod2ki,wi, aid=DPui⊕hTIDui,wL,σL,pui,pLj,wi,σi, αi=hTIDui,wL,σL,pui,pLj,wi,aid,σi,ts3, and the final session key hDPui,TIDui,wL,σL,pui,pLj,wi,σi,αi. Finally, ui sends the message pui,wi,aid,ts3,αi to LEOj.(4)
After receiving the messagepui,wi,aid,ts3,αi, LEOj performs the same timestamp check process as steps 2 and 3. If the timestamp is not within the allowed range, the access request is denied; otherwise LEOj computes ki′=pui⋅sLj, σi′=Mod2ki′,wi, αi′=hTIDui,wL,σL′,pui,pLj,wi,aid,σi′,ts3. Then LEOj checks αi′=αi. If they are not equal, the received message is not sent by the real IDui or modified by malicious nodes, and then the access request is immediately terminated; otherwise it computes DPui′=aid⊕hTIDui,wL,σL′,pui,pLj,wi,σi′ and the final session key hDPui′,TIDui,wL,σL′,pui,pLj,wi,σi′,αi.Figure 3
Authentication phase.Algorithm 2: Password update phase.
(1)
InputTIDui′,PWuiOld(2)
TWDui′=hTIDui′,PWuiOld;(3)
Vui′=hTIDui′,TWDui′,DPui;(4)
ifVui′=Vuithen(5)
Deny the password update;(6)
else(7)
InputPWuiNew(8)
TWDuiNew=hTIDui,PWuiNew;(9)
DPuiNew=DPuiOld⊕TWDuiOld⊕TWDuiNew;(10)
VuiNew=hTIDui,TWDuiNew,DPuiNew;(11)
Smart device storesTIDui,DPuiNew,VuiNew;


### 4.4. Password Update Phase

Whenui wants to change the old password PWuiOld to the new password PWuiNew, an attempt as shown in Algorithm 2 is made to perform the password update phase. Firstly, ui needs to input the temporary identity TIDui and the correct old password PWuiOld. Then the smart device computes TWDui′=hTIDui′,PWuiOld, Vui′=hTIDui′,TWDui′,DPui and checks whether Vui′=Vui. If they are not equal, the password update phase is terminated immediately. Otherwise, ui inputs the new password PWuiNew and the smart device computes TWDuiNew=hTIDui,PWuiNew, DPuiNew=DPuiOld⊕TWDuiOld⊕TWDuiNew, and VuiNew=hTIDui,TWDuiNew,DPuiNew. Use DPuiNew and VuiNew to replace DPuiOld and VuiOld, where VuiNew will be used as the new verification value of the login device in the future. Finally, the smart device stores TIDui,DPuiNew,VuiNew.


### 4.5. Temporary Identity Update Phase

This phase is only performed when the previous temporary identityTIDuiOld is no longer sufficient for their identity anonymity and security requirements. As shown in Figure 4, ui finally obtains a new legal temporary identity TIDuiNew through two message exchanges and updates the parameters associated with the temporary identity TID such as DI, TWD, DP, and V. We note that all messages between TCS and ui are transmitted in the public channel.(1)
ui needs to input the correct TIDui and PWui. After the verification is successful, ui chooses a new temporary identity TIDuiNew and then computes kTCS=pTCS⋅smui, wTCS=ChakTCS, σTCS=Mod2kTCS,wTCS, αi=TIDuiNew⊕hTIDuiOld,wTCS,σTCS,ts4, and α=hTIDuiOld,TIDuiNew,wTCS,αi,ts4. Finally, ui sends the message TIDuiOld,wTCS,ts4,αi,α to TCS.(2)
After receiving the messageTIDuiOld,wTCS,ts4,αi,α, TCS first checks the timestamp ts4 and compares it with the current time to see if it is within the time allowed. If ts4 is valid, TCS computes kTCS′=pmui⋅s, σTCS′=Mod2kTCS′,wTCS, TIDuiNew′=αi⊕hTIDuiOld,wTCS,σTCS′,ts4, and α′=hTIDuiOld,TIDuiNew′,wTCS,αi,ts4. Then TCS checks whether α′=α. If the check is valid, TCS can not only know the legal identity of the end user, but also know the new temporary identity TIDuiNew that ui wants to update. Next, TCS continues to compute DIuiNew=hTIDuiNew′,s, DIa=DIuiNew⊕hTIDuiOld,TIDuiNew′,σTCS′, and α1=hTIDuiOld,TIDuiNew′,wTCS,σTCS′,DIa,ts5. Finally, TCS sends the message DIa,α1,ts5 to ui and the message TIDuiOld,TIDuiNew′ to LEOj which updates the association between TIDui and pmui. The message transmits between LEOj and TCS in the secure channel.(3)
After receiving the messageDIa,α1,ts5, ui also needs to first check if ts5 is within the time allowed. If the check is valid, ui computes α1′=hTIDuiOld,TIDuiNew,wTCS,σTCS,DIa,ts5. Then ui checks whether α1′=α1. If the check is valid, the entity communicating with it can be identified as TCS. Next ui continues to compute DIuiNew=DIa⊕hTIDuiOld,TIDuiNew,σTCS, TWDuiNew=hTIDuiNew,PWui, and DPuiNew=DIuiNew⊕TWDuiNew. Finally, updating VuiNew=hTIDuiNew,TWDuiNew,DPuiNew allows ui to input the TIDuiNew and PWui can login the device correctly.Figure 4
Temporary identity update phase.


## 4.1. System Initialization Phase

In the system initialization phase, TCS generates the master key pair and some system public parameters according to the following steps:(1)
TCS sets system security parametersk(2)
TCS chooses an odd prime numberq and an integer n, where n is a power of 2 and qmod2n=1(3)
TCS chooses a discrete Gaussian distributionχβ and a random ring element a, where β is a fixed positive number and a∈ℝq(4)
TCS randomly sampless,e⟵χβ and computes the master public key pTCS=a⋅s+2⋅e, where s is the master private key(5)
TCS chooses a security hash functionh:0,1∗⟶0,1k(6)
TCS publishes the system parametersq,n,χβ,a,pTCS,h to the public and securely stores the master private key sThe system initialization phase is performed once when the system is laid out and not during other phases. Since it is only executed once, the computational overhead of the system initialization phase can be considered negligible.


## 4.2. Registration Phase

The registration phase is the process by which TCS interacts with trustworthy end users and satellite nodes. In this phase, the satellite and the end user need to submit the true identityID and other necessary parameters to TCS. It is worth noting that end users also need to generate the temporary identity TID that masks the true identity during the authentication phase. Then TCS generates the parameters needed for mutual authentication in the future for the end user and the satellite node, respectively. We briefly show this process in Figure 2 and the more detailed steps will be described in Algorithm 1 and the rest of this section. We assume that the satellite set is SLEO with N1 satellites and the end user set is Suser with N2 users. For a clearer presentation, in the following description, we simplify the system model with only one end user ui, one satellite LEOj, and TCS. Besides, it is necessary to note that the messages in this phase are transmitted in the secure channel.(1)
LEOj generates the true identity IDLj and computes the master public key pmLj=a⋅smLj+2⋅emLj, where smLj and emLj are randomly sampled from χβ. smLj is assumed to be the master private key and is stored securely by LEOj. Finally, LEOj sends the message IDLj,pmLj to TCS. It needs to be reminded that the identity of the IDLj satellite node is not private, so there is no need to anonymize it.(2)
ui generates the true identity IDui, temporary identity TIDui, and password PWui and then chooses the satellite node IDLj which it wants to communicate with. The function of PWui is used for login verification and it will be required in authentication phase, password update phase, and temporary identity update phase. Next, ui computes the master public key pmui=a⋅smui+2⋅emui, where smui and emui are randomly sampled from χβ. smui is assumed to be the master private key and is stored securely by ui. Then ui computes TWDui=hTIDui,PWui, which is to protect the PWui from being known by the TCS. Finally, ui sends the message IDui,TIDui,IDLj,TWDui,pmui to TCS.(3)
TCS computesDIui=hTIDui,s, DPui=DIui⊕TWDui, and Vui=hTIDui,TWDui,DPui after receiving the registration message of ui. Then TCS sends the messages DPui,Vui,pmLj to ui and TIDui,pmui to LEOLj. Vui is used to check if the temporary identity TIDui and password PWui entered are correct when ui logs into the smart device. The function of the DPui is to enable ui to update the password PWui as wishes and detailed in the password update phase. The function of DIui is to prevent ui from changing TIDui by himself. If ui is free to update the temporary identity TIDui, the legal identity of ui cannot be distinguished during the authentication phase. By binding the master private key s of the TCS to TIDui, even if ui attempts to update TIDui, it cannot change DIui, DPui, and Vui without TCS. Finally, TCS stores IDui,TIDui,pmui and IDLj,pmLj.(4)
ui stores the message DPui,Vui,pmLj.(5)
LEOj stores the message TIDui,pmui.Figure 2
Registration phase.Algorithm 1: Registration phase.
(1)
LEOj:(2)
Generates the true identityIDLj;(3)
Randomly samplessmLj,emLj and computes the master public key pmLj=a⋅smLj+2⋅emLj;(4)
Stores the master private keysmLj;(5)
SubmitsIDLj,pmLj to TCS;(6)
LEOj END(7)
ui:(8)
Generates the true identityIDui, temporary-ID TIDui, password PWui and chooses the satellite node IDLj;(9)
Randomly samplessmui, emui and computes the master public key pmui=a⋅smui+2⋅emui;(10)
ComputesTWDui=hTIDui,PWui;(11)
SubmitsIDui,TIDuI,IDLj,TWDui,pmui to TCS;(12)
ui END(13)
TCS:(14)
ComputesDIui=hTIDui,s, DPui=DIui⊕TWDui, Vui=hTIDui,TWDui,DPui;(15)
TransmitsDPui,Vui,pmLj to ui and TIDui,pmui to LEOj;(16)
StoresIDui,TIDui,pmui and IDLj,pmLj;(17)
TCS END(18)
ui stores DPui,Vui,pmLj;(19)
LEOj stores TIDui,pmui;


## 4.3. Authentication Phase

As shown in Figure3, in this phase, ui and LEOj mutually authenticate each other's legal identity in accordance with the following steps and negotiate a shared session key to encrypt future communications. It is worth noting that the three interactive messages are transmitted in the public channel and the messages are transmitted in plaintext.(1)
ui needs to input the temporary identity TIDui′ and password PWui' to login the smart device before requesting authentication. The device computes TWDui′=hTIDui′,PWui′, Vui′=hTIDui′,TWDui′,DPui. Then it checks whether Vui′=Vui. If they are not equal, the access request is terminated immediately; otherwise the following steps are continued according to the protocol. This process is to prevent the device from falling into the adversary and being disguised as ui. Next, the smart device computes kL=pmLj⋅smui, wL=ChakL, σL=Mod2kL,wL, and αL=hTIDui,wL,σL,ts1. Finally, ui sends the message TIDui,wL,ts1,αL to LEOj. ts1 is the timestamp used to prevent the replay attacks by the adversary. The rest of the timestamps in this paper have the same function as ts1.(2)
After receiving the messageTIDui,wL,ts1,αL, LEOj first checks the timestamp ts1 and compares it with the current time to see if it is within the time allowed. If the timestamp is not within the allowed range, the access request is denied; otherwise LEOj computes kL′=pmui⋅smLj, σL′=Mod2kL′,wL, and αL′=hTIDui,wL,σL′,ts1. Then it checks whether αL′=αL. If they are not equal, the end user who sent the access request is not legitimate and LEOj rejects the access request; otherwise the next steps of the authentication protocol are continued. Next, LEOj computes pLj=a⋅sLj+2⋅eLj and α0=hTIDui,wL,σL′,pLj,ts2, where sLj and eLj are randomly sampled from χβ. Finally, LEOj sends the message pLj,ts2,α0 to ui.(3)
After receiving the messagepLj,ts2,α0, ui first checks the timestamp ts2 and compares it with the current time to see if it is within the time allowed. If the timestamp is not within the allowed range, the access request is denied; otherwise ui computes α0′=hTIDui,wL,σL,pLj,ts2. Then ui checks whether α0′=α0. If they are not equal, ui will assume that the satellite requested to access during the authentication phase is not the true LEOj and actively stops the access request; otherwise it continues to compute pui=a⋅sui+2⋅eui, ki=pLj⋅sui, σi=Mod2ki,wi, aid=DPui⊕hTIDui,wL,σL,pui,pLj,wi,σi, αi=hTIDui,wL,σL,pui,pLj,wi,aid,σi,ts3, and the final session key hDPui,TIDui,wL,σL,pui,pLj,wi,σi,αi. Finally, ui sends the message pui,wi,aid,ts3,αi to LEOj.(4)
After receiving the messagepui,wi,aid,ts3,αi, LEOj performs the same timestamp check process as steps 2 and 3. If the timestamp is not within the allowed range, the access request is denied; otherwise LEOj computes ki′=pui⋅sLj, σi′=Mod2ki′,wi, αi′=hTIDui,wL,σL′,pui,pLj,wi,aid,σi′,ts3. Then LEOj checks αi′=αi. If they are not equal, the received message is not sent by the real IDui or modified by malicious nodes, and then the access request is immediately terminated; otherwise it computes DPui′=aid⊕hTIDui,wL,σL′,pui,pLj,wi,σi′ and the final session key hDPui′,TIDui,wL,σL′,pui,pLj,wi,σi′,αi.Figure 3
Authentication phase.Algorithm 2: Password update phase.
(1)
InputTIDui′,PWuiOld(2)
TWDui′=hTIDui′,PWuiOld;(3)
Vui′=hTIDui′,TWDui′,DPui;(4)
ifVui′=Vuithen(5)
Deny the password update;(6)
else(7)
InputPWuiNew(8)
TWDuiNew=hTIDui,PWuiNew;(9)
DPuiNew=DPuiOld⊕TWDuiOld⊕TWDuiNew;(10)
VuiNew=hTIDui,TWDuiNew,DPuiNew;(11)
Smart device storesTIDui,DPuiNew,VuiNew;


## 4.4. Password Update Phase

Whenui wants to change the old password PWuiOld to the new password PWuiNew, an attempt as shown in Algorithm 2 is made to perform the password update phase. Firstly, ui needs to input the temporary identity TIDui and the correct old password PWuiOld. Then the smart device computes TWDui′=hTIDui′,PWuiOld, Vui′=hTIDui′,TWDui′,DPui and checks whether Vui′=Vui. If they are not equal, the password update phase is terminated immediately. Otherwise, ui inputs the new password PWuiNew and the smart device computes TWDuiNew=hTIDui,PWuiNew, DPuiNew=DPuiOld⊕TWDuiOld⊕TWDuiNew, and VuiNew=hTIDui,TWDuiNew,DPuiNew. Use DPuiNew and VuiNew to replace DPuiOld and VuiOld, where VuiNew will be used as the new verification value of the login device in the future. Finally, the smart device stores TIDui,DPuiNew,VuiNew.


## 4.5. Temporary Identity Update Phase

This phase is only performed when the previous temporary identityTIDuiOld is no longer sufficient for their identity anonymity and security requirements. As shown in Figure 4, ui finally obtains a new legal temporary identity TIDuiNew through two message exchanges and updates the parameters associated with the temporary identity TID such as DI, TWD, DP, and V. We note that all messages between TCS and ui are transmitted in the public channel.(1)
ui needs to input the correct TIDui and PWui. After the verification is successful, ui chooses a new temporary identity TIDuiNew and then computes kTCS=pTCS⋅smui, wTCS=ChakTCS, σTCS=Mod2kTCS,wTCS, αi=TIDuiNew⊕hTIDuiOld,wTCS,σTCS,ts4, and α=hTIDuiOld,TIDuiNew,wTCS,αi,ts4. Finally, ui sends the message TIDuiOld,wTCS,ts4,αi,α to TCS.(2)
After receiving the messageTIDuiOld,wTCS,ts4,αi,α, TCS first checks the timestamp ts4 and compares it with the current time to see if it is within the time allowed. If ts4 is valid, TCS computes kTCS′=pmui⋅s, σTCS′=Mod2kTCS′,wTCS, TIDuiNew′=αi⊕hTIDuiOld,wTCS,σTCS′,ts4, and α′=hTIDuiOld,TIDuiNew′,wTCS,αi,ts4. Then TCS checks whether α′=α. If the check is valid, TCS can not only know the legal identity of the end user, but also know the new temporary identity TIDuiNew that ui wants to update. Next, TCS continues to compute DIuiNew=hTIDuiNew′,s, DIa=DIuiNew⊕hTIDuiOld,TIDuiNew′,σTCS′, and α1=hTIDuiOld,TIDuiNew′,wTCS,σTCS′,DIa,ts5. Finally, TCS sends the message DIa,α1,ts5 to ui and the message TIDuiOld,TIDuiNew′ to LEOj which updates the association between TIDui and pmui. The message transmits between LEOj and TCS in the secure channel.(3)
After receiving the messageDIa,α1,ts5, ui also needs to first check if ts5 is within the time allowed. If the check is valid, ui computes α1′=hTIDuiOld,TIDuiNew,wTCS,σTCS,DIa,ts5. Then ui checks whether α1′=α1. If the check is valid, the entity communicating with it can be identified as TCS. Next ui continues to compute DIuiNew=DIa⊕hTIDuiOld,TIDuiNew,σTCS, TWDuiNew=hTIDuiNew,PWui, and DPuiNew=DIuiNew⊕TWDuiNew. Finally, updating VuiNew=hTIDuiNew,TWDuiNew,DPuiNew allows ui to input the TIDuiNew and PWui can login the device correctly.Figure 4
Temporary identity update phase.


## 5. Security Analysis

In this section, we analyze and discuss the security requirements of our protocol and prove that our protocol is sufficiently secure to resist insider attacks, replay attacks, modification attacks, eavesdropping attacks, and impersonation attacks. As shown in Table1, we also compared the security attributes with other related protocols.Table 1
Comparison of security attributes.
Security attribute[21][22][23][24][10]OursMutual authentication✓✓✓✓✓✓Identity anonymity✗✓✓✓✓✓Key establishment✓✓✓✓✓✓Perfect forward secrecy✓✗✗✓✓✓Login authentication✗✗✗✗✗✓Insider attack✓✓✓✓✓✓Replay attack✓✓✓✓✓✓Modification attack✓✓✓✓✓✓Eavesdropping attack✓✓✓✓✓✓Impersonation attack✓✗✓✗✓✓


### 5.1. Mutual Authentication

In step 2 of authentication phase,LEOj authenticates the legal identity of ui by checking αL′=αL, where αL′=hTIDui,wL,σL′,ts1. Since LEOj has securely stored the temporary identity TIDui and the public key pmui in registration phase, only the user whose temporary identity is TIDui and has the public-private key pair pmui,smui can compute the same σL as LEOj and then can pass the check. No one can compute the matching private key smui by TIDui and pmui unless the SIVP assumption can be solved with PPT algorithm. Similarly, in step 3 of authentication phase, ui authenticates the legal identity of LEOj by checking α0′=α0, where α0=hTIDui,wL,σL,pLj,ts2. Since ui has securely stored the IDLj and the public key , the adversary can only disguise as LEOj if it solves the SIVP assumption in polynomial time. In addition, as [26], the secure hash function is used to ensure the integrity of the messages in the public channel transmission. Therefore, the authentication protocol can meet the security requirements of mutual authentication.


### 5.2. Identity Anonymity

In the whole system, onlyui and TCS know the true identity IDui. Whether in the authentication phase or in the temporary identity update phase, the temporary identity TIDui is transmitted in the public channel. IDui has no relevance to TIDui and cannot be inferred from TIDui. The adversary can only obtain the true identity of the user from TCS which preserves the relationship between TIDui and IDui. However, the highest level of security protection of TCS makes it impossible for adversary. Therefore, the authentication protocol can meet the security requirements of identity anonymity.


### 5.3. Key Establishment

In step 3 and step 4 of authentication phase,ui and LEOj independently generated the final shared session key hDPui,TIDui,wL,σL,pui,pLj,wi,σi,αi, where nonpublic parameters σL=Mod2kL,wL and σi=Mod2ki,wi require both parties to participate to compute k and avoid the shared key being determined by the single party. Moreover, the adversary cannot guess k from the public key unless there is a more efficient algorithm to solve the SIVP assumption. Therefore, the authentication protocol can meet the security requirements of key establishment.


### 5.4. Perfect Forward Secrecy

In our protocol, the shared key negotiated by the two parties ishDPui,TIDui,wL,σL,pui,pLj,wi,σi,αi, except for σL, σi, and DPui, which are parameters that can be directly intercepted in the public channel. σL and DPui can be regarded as long-term secrets of ui and LEOj. In addition, σi is generated by sui and eui randomly sampled from χβ at each authentication. Even if long-term secrets are captured by the adversary, due to the randomness of sui and eui, the adversary cannot know the previous session key. Therefore, the authentication protocol provides perfect forward secrecy.


### 5.5. Login Authentication

Only after entering the correct temporary identityTID and password PW can the user perform the access authentication in accordance with the steps. When the user’s device is lost, the adversary cannot use the device, which avoids the security threat of the adversary pretending to be a legitimate user. Moreover, it can not only deny malicious access directly at the device side, but also reduce the computational cost of SIN.


### 5.6. Resistance of Insider Attacks

Although TCS is a trusted entity in the SIN, it is inevitable that the possibility of insiders stealing the user’s password exists. During the registration phase, the user did not submit the passwordPW directly to TCS but TWD=hTID,PW. Due to the one-way security of the hash function h, insiders cannot get PW from TWD. Therefore, the authentication protocol can meet the security requirements of resistance of insider attacks.


### 5.7. Resistance of Replay Attacks

It is noted that each message transmission contains a timestampts, which is hashed with σ. σ can only be known by both parties to the authentication and the adversary cannot know, which ensures that the message cannot be modified. So even if the adversary replays the authentication message, the user or satellite node can check whether it is the replay attack in two steps. First, check if the timestamp ts is within the allowed range; then compute the hash value α of the message and compare it with α′ sent by the other party. Even if the adversary modifies the timestamp ts in the message and passes the first step of checking but cannot get σ, it is impossible to forge the correct hash value with the modified ts. Furthermore, parameters sLj,eLj,sui,eui are randomly sampled, which results in different public keys p and hash values α for each session. ui and LEOj can also detect replay attacks by verifying these parameters. Therefore, the authentication protocol can meet the security requirements of resistance to replay attacks.


### 5.8. Resistance of Modification Attacks

During the authentication phase, each step contains a final message hashα which is the hash value of the message transmitted this time and some key data previously negotiated. For example, the message pLj,ts2,α0 is transmitted by LEOj to ui in the second step, where α0=hTIDui,wL,σL,pLj,ts2. α0 contains not only the message pLj and the timestamp ts2 but also the previously negotiated parameters TIDui, wL, and σL. Due to the security features of the hash function h, any changes to the message can be verified. Therefore, the authentication protocol can meet the security requirements of resistance of modification attacks.


### 5.9. Resistance of Eavesdropping Attacks

In our whole protocol, the adversary can only obtain data such asTIDui, wL, pLj, pui, wi, and a series of hash values and timestamps. Due to the security of the hash function, the adversary cannot get any useful information from the hash value. In addition, the final shared key is hDPui,TIDui,wL,σL,pui,pLj,wi,σi,αi, where σL and σi cannot compute by the known parameters such as TIDui, wL, pLj, pui, wi unless the SIVP assumption is solved. Therefore, the authentication protocol can meet the security requirements against eavesdropping attacks.


### 5.10. Resistance of Impersonation Attacks

An adversary may impersonate a legitimate user or satellite node to submit or respond to access requests. However, the adversary can only obtain the public key of both parties, but cannot obtain the private key for authentication and negotiation of shared key, so it is impossible to forge hash values to pass authentication. Therefore, the authentication protocol can meet the security requirements of resistance to impersonation attacks.


## 5.1. Mutual Authentication

In step 2 of authentication phase,LEOj authenticates the legal identity of ui by checking αL′=αL, where αL′=hTIDui,wL,σL′,ts1. Since LEOj has securely stored the temporary identity TIDui and the public key pmui in registration phase, only the user whose temporary identity is TIDui and has the public-private key pair pmui,smui can compute the same σL as LEOj and then can pass the check. No one can compute the matching private key smui by TIDui and pmui unless the SIVP assumption can be solved with PPT algorithm. Similarly, in step 3 of authentication phase, ui authenticates the legal identity of LEOj by checking α0′=α0, where α0=hTIDui,wL,σL,pLj,ts2. Since ui has securely stored the IDLj and the public key , the adversary can only disguise as LEOj if it solves the SIVP assumption in polynomial time. In addition, as [26], the secure hash function is used to ensure the integrity of the messages in the public channel transmission. Therefore, the authentication protocol can meet the security requirements of mutual authentication.


## 5.2. Identity Anonymity

In the whole system, onlyui and TCS know the true identity IDui. Whether in the authentication phase or in the temporary identity update phase, the temporary identity TIDui is transmitted in the public channel. IDui has no relevance to TIDui and cannot be inferred from TIDui. The adversary can only obtain the true identity of the user from TCS which preserves the relationship between TIDui and IDui. However, the highest level of security protection of TCS makes it impossible for adversary. Therefore, the authentication protocol can meet the security requirements of identity anonymity.


## 5.3. Key Establishment

In step 3 and step 4 of authentication phase,ui and LEOj independently generated the final shared session key hDPui,TIDui,wL,σL,pui,pLj,wi,σi,αi, where nonpublic parameters σL=Mod2kL,wL and σi=Mod2ki,wi require both parties to participate to compute k and avoid the shared key being determined by the single party. Moreover, the adversary cannot guess k from the public key unless there is a more efficient algorithm to solve the SIVP assumption. Therefore, the authentication protocol can meet the security requirements of key establishment.


## 5.4. Perfect Forward Secrecy

In our protocol, the shared key negotiated by the two parties ishDPui,TIDui,wL,σL,pui,pLj,wi,σi,αi, except for σL, σi, and DPui, which are parameters that can be directly intercepted in the public channel. σL and DPui can be regarded as long-term secrets of ui and LEOj. In addition, σi is generated by sui and eui randomly sampled from χβ at each authentication. Even if long-term secrets are captured by the adversary, due to the randomness of sui and eui, the adversary cannot know the previous session key. Therefore, the authentication protocol provides perfect forward secrecy.


## 5.5. Login Authentication

Only after entering the correct temporary identityTID and password PW can the user perform the access authentication in accordance with the steps. When the user’s device is lost, the adversary cannot use the device, which avoids the security threat of the adversary pretending to be a legitimate user. Moreover, it can not only deny malicious access directly at the device side, but also reduce the computational cost of SIN.


## 5.6. Resistance of Insider Attacks

Although TCS is a trusted entity in the SIN, it is inevitable that the possibility of insiders stealing the user’s password exists. During the registration phase, the user did not submit the passwordPW directly to TCS but TWD=hTID,PW. Due to the one-way security of the hash function h, insiders cannot get PW from TWD. Therefore, the authentication protocol can meet the security requirements of resistance of insider attacks.


## 5.7. Resistance of Replay Attacks

It is noted that each message transmission contains a timestampts, which is hashed with σ. σ can only be known by both parties to the authentication and the adversary cannot know, which ensures that the message cannot be modified. So even if the adversary replays the authentication message, the user or satellite node can check whether it is the replay attack in two steps. First, check if the timestamp ts is within the allowed range; then compute the hash value α of the message and compare it with α′ sent by the other party. Even if the adversary modifies the timestamp ts in the message and passes the first step of checking but cannot get σ, it is impossible to forge the correct hash value with the modified ts. Furthermore, parameters sLj,eLj,sui,eui are randomly sampled, which results in different public keys p and hash values α for each session. ui and LEOj can also detect replay attacks by verifying these parameters. Therefore, the authentication protocol can meet the security requirements of resistance to replay attacks.


## 5.8. Resistance of Modification Attacks

During the authentication phase, each step contains a final message hashα which is the hash value of the message transmitted this time and some key data previously negotiated. For example, the message pLj,ts2,α0 is transmitted by LEOj to ui in the second step, where α0=hTIDui,wL,σL,pLj,ts2. α0 contains not only the message pLj and the timestamp ts2 but also the previously negotiated parameters TIDui, wL, and σL. Due to the security features of the hash function h, any changes to the message can be verified. Therefore, the authentication protocol can meet the security requirements of resistance of modification attacks.


## 5.9. Resistance of Eavesdropping Attacks

In our whole protocol, the adversary can only obtain data such asTIDui, wL, pLj, pui, wi, and a series of hash values and timestamps. Due to the security of the hash function, the adversary cannot get any useful information from the hash value. In addition, the final shared key is hDPui,TIDui,wL,σL,pui,pLj,wi,σi,αi, where σL and σi cannot compute by the known parameters such as TIDui, wL, pLj, pui, wi unless the SIVP assumption is solved. Therefore, the authentication protocol can meet the security requirements against eavesdropping attacks.


## 5.10. Resistance of Impersonation Attacks

An adversary may impersonate a legitimate user or satellite node to submit or respond to access requests. However, the adversary can only obtain the public key of both parties, but cannot obtain the private key for authentication and negotiation of shared key, so it is impossible to forge hash values to pass authentication. Therefore, the authentication protocol can meet the security requirements of resistance to impersonation attacks.


## 6. Performance Analysis

In this section, we present the performance analysis of the protocol for authentication delay and communication overhead. Because our proposed protocol is the first postquantum anonymous authentication scheme for SIN, we just choose to compare it with the classic authentication scheme [23] and the latest proposed protocol [10]. Furthermore, to make the comparison more intuitive and consider the practicality of the protocol for smart devices, we set the parameters in the protocol as [19]. The integer n is 1024 and the odd prime number q is 12289. For discrete Gaussian distribution parameter β is set to logβ=17.1. Finally, choose the secure hash function SHA3 with output of 512 bits.


### 6.1. Authentication Delay

Authentication delay refers to the sum of the total computing time and the transmission time of both devices from the beginning to the end in the mutual authentication phase. Before discussing the authentication delay of our proposed protocol in detail, we need to use the following symbols to represent the average time overhead caused by different operations.TGe is used to represent the sampling time from the discrete Gaussian distribution χβ. Tsmul and Tpmul represent multiplication with scalar and multiplication time in ℝq, respectively. Tpma represents the time of the multiplication and addition operation in ℝq. TCha indicates the time when the Cha function is executed once. Th is the time when the SHA3 hash function is executed once. To better analyze the performance of our proposed protocol, we quote the overhead time of various computation operations in [26]. The satellite node and the end user in the proposed protocol correspond to the server and the mobile device in [26], respectively. The machine is equipped with 3.4 GHz Intel Core i7-6700 processor and 8 GB RAM as the satellite node and the end user with 1.4 GHz Quad-core Exynos 4412 processor and 1 GB RAM. Both parties used the LatticeCrypto library and the MIRACL library when implementing the protocol. The experimental results are shown in Table 2 and it is worth mentioning that the computation overhead of Mod2 function is small enough to be neglected. In addition, since LEO satellites are usually located 500 km–3000 km from the ground, it is reasonable to set the single message delivery time to Tu−LEO=5ms. The following is the analysis of the computing time according to the steps in the authentication phase.Table 2
Execution times of RLWE-related operations.
NotationSatellite node (ns)End user (ns)TGe73.503561.483Tsmul0.2986.655Tpmul0.30713.052Tpma2.54929.505TCha0.68935.515Th14.09180.964(1)
In the first step, afterTIDui' and PWui' entered by ui, the device performs two hash operations to check whether they are correct. If the verification passes, ui also needs to perform one multiplication operation in ℝq, one Cha function in ℝq, and one hash operation. Therefore, the total computing time overhead of ui is 3×Thu+Tpmulu+TChau=591.459ns.(2)
In the second step, after receiving the message,LEOj first needs to perform one multiplication operation in ℝq and one hash operation to check the validity of the message. If the verification passes, it also needs to continue to perform two random sampling operations in χβ, one multiplication with scalar in ℝq, one multiplication and addition operation in ℝq, and one hash operation. Therefore, the total computing time overhead of LEOj is 2×ThL+TpmulL+2×TGeL+TsmulL+TpmaL=178.34ns.(3)
Next, afterui receives the response message from LEOj, ui first performs one hash operation to check the validity of the message. If the verification passes, ui also needs to perform two sampling operations in χβ, one multiplication with scalar in ℝq, one multiplication and addition operation in ℝq, one multiplication time in ℝq, one Cha function in ℝq, and three hash operations. Therefore, the total computing time overhead of ui is 4×Thu+2×TGeu+Tsmulu+Tpmau+Tpmulu+TChau =1931.549ns.(4)
Finally, afterLEOj receives the response message from ui, it first performs one multiplication operation in ℝq and one hash operation to check the validity of the message. If the verification passes, LEOj also needs to continue to perform two hash operations. Therefore, the total computing time overhead of LEOj is 3×ThL+TpmulL=42.577ns.In general, the two parties of authenticating the identity and building the session key need to execute 2523.008 ns at the end user and 220.917 ns at the satellite node, respectively. The total computing time required for the protocol is 2743.925ns. Besides, the three messaging times required for the authentication phase are 3×Tu−LEO=15ms. So the authentication delay of our proposed protocol is 15.003 ms and the computing time is only a small part of the authentication delay.In [23], the computing time depends on the maximum number of accesses N and the j−th access. In order to achieve the shortest time, we set N=1, j=1. Therefore, both the end user and the satellite node of the authentication process need to perform four hash operations and the computing times aare 4×Thu=723.856ns and 4×ThL=56.36ns, respectively. Besides, the five messaging times required for the authentication phase are 5×Tu−LEO=25ms. So, the authentication delay of [23] is 25.001 ms. However, in general, in order to reduce the computational task of TCS, N is set to a larger value which makes the authentication delay greatly increase and the performance of the protocol degrade.In [10], the protocol is based on the q−Strong Diffie–Hellman problem [32] where the execution of the protocol requires pairing operation, multiplication operation, and exponentiation operation in the additive cyclic group. The experimental results of these operations in [26] are as described in Table 3. In the authentication phase, the end user needs to execute the total of nine multiplication operations, three exponentiation operations, two pairing operations, and one hash operation, so the computing time of end user is 9×Tmulu+3×Texpu+2×Tpairu+Thu=115.485ms. The satellite node executes five multiplication operations, four exponentiation operations, two pairing operations, and one hash operation, so the computing time of satellite node is 5×TmulL+4×TexpL+2×TpairL+ThL=18.202ms. The total computing time required for the protocol is 133.687 ms. Besides, the two messaging times required for the authentication phase are 2×Tu−LEO=10ms. So, the authentication delay of [10] is 143.687 ms.Table 3
Execution times ofq−Strong DH related operations.
NotationSatellite node (ms)End user (ms)Tpair8.26252.533Tmul0.0020.012Texp0.4173.437Table4 shows the comparison of the authentication delays of our proposed protocol with the other two protocols. It can be seen from the table that the authentication delay of our proposed protocol is significantly lower than [10, 23], which is a more effective authentication scheme.Table 4
Comparison of authentication delay.
Satellite nodeEnd userTransmission timeTotal[23]56.36ns723.856ns25ms25.001ms[10]18.202ms115.485ms10ms143.687msOur220.917ns2523.008ns15ms15.003ms


### 6.2. Communication Overhead

According to the security of the protocol and the support for the device mentioned earlier, we set the size of elements inℝq to 4096 bits, the output of the SHA3 function is 512 bits, and the length of the identity and the timestamp is 100 bits. There are three message transmissions in the mutual authentication phase of our protocol. First, ui sends TIDui,wL,ts1,αL to LEOj. Then, LEOj responds pLj,ts2,α0 to ui. Finally, ui sends a confirmation message pui,wi,aid,ts3,αi to the LEOj. Therefore, the total communication overhead of the protocol is 100+4096+100+512+4096+100+512+4096+4096+512+100+512=18832 bits.In [23], both parties need to transmit six hash values and six identity messages, so the total transmission overhead is 6×512+6×100=3672 bits. In [10], assume that the length of element in cycle group and all signatures is 160 bits. Therefore, according to the communication overhead in [10], it can be concluded that the total of 2480 bits of messages needs to be transmitted during the authentication phase.It is worth noting that the communication overhead of the proposed protocol is greater than other protocols because the protocol is based on RLWE, and a common flaw in the ringℝq is that the key size is larger than the traditional encryption system. Considering that satellite network bandwidth has grown significantly and the authentication delay is small enough for delay-sensitive users, so we believe that our proposed protocol is a practicable scheme which is superior to other protocols.


## 6.1. Authentication Delay

Authentication delay refers to the sum of the total computing time and the transmission time of both devices from the beginning to the end in the mutual authentication phase. Before discussing the authentication delay of our proposed protocol in detail, we need to use the following symbols to represent the average time overhead caused by different operations.TGe is used to represent the sampling time from the discrete Gaussian distribution χβ. Tsmul and Tpmul represent multiplication with scalar and multiplication time in ℝq, respectively. Tpma represents the time of the multiplication and addition operation in ℝq. TCha indicates the time when the Cha function is executed once. Th is the time when the SHA3 hash function is executed once. To better analyze the performance of our proposed protocol, we quote the overhead time of various computation operations in [26]. The satellite node and the end user in the proposed protocol correspond to the server and the mobile device in [26], respectively. The machine is equipped with 3.4 GHz Intel Core i7-6700 processor and 8 GB RAM as the satellite node and the end user with 1.4 GHz Quad-core Exynos 4412 processor and 1 GB RAM. Both parties used the LatticeCrypto library and the MIRACL library when implementing the protocol. The experimental results are shown in Table 2 and it is worth mentioning that the computation overhead of Mod2 function is small enough to be neglected. In addition, since LEO satellites are usually located 500 km–3000 km from the ground, it is reasonable to set the single message delivery time to Tu−LEO=5ms. The following is the analysis of the computing time according to the steps in the authentication phase.Table 2
Execution times of RLWE-related operations.
NotationSatellite node (ns)End user (ns)TGe73.503561.483Tsmul0.2986.655Tpmul0.30713.052Tpma2.54929.505TCha0.68935.515Th14.09180.964(1)
In the first step, afterTIDui' and PWui' entered by ui, the device performs two hash operations to check whether they are correct. If the verification passes, ui also needs to perform one multiplication operation in ℝq, one Cha function in ℝq, and one hash operation. Therefore, the total computing time overhead of ui is 3×Thu+Tpmulu+TChau=591.459ns.(2)
In the second step, after receiving the message,LEOj first needs to perform one multiplication operation in ℝq and one hash operation to check the validity of the message. If the verification passes, it also needs to continue to perform two random sampling operations in χβ, one multiplication with scalar in ℝq, one multiplication and addition operation in ℝq, and one hash operation. Therefore, the total computing time overhead of LEOj is 2×ThL+TpmulL+2×TGeL+TsmulL+TpmaL=178.34ns.(3)
Next, afterui receives the response message from LEOj, ui first performs one hash operation to check the validity of the message. If the verification passes, ui also needs to perform two sampling operations in χβ, one multiplication with scalar in ℝq, one multiplication and addition operation in ℝq, one multiplication time in ℝq, one Cha function in ℝq, and three hash operations. Therefore, the total computing time overhead of ui is 4×Thu+2×TGeu+Tsmulu+Tpmau+Tpmulu+TChau =1931.549ns.(4)
Finally, afterLEOj receives the response message from ui, it first performs one multiplication operation in ℝq and one hash operation to check the validity of the message. If the verification passes, LEOj also needs to continue to perform two hash operations. Therefore, the total computing time overhead of LEOj is 3×ThL+TpmulL=42.577ns.In general, the two parties of authenticating the identity and building the session key need to execute 2523.008 ns at the end user and 220.917 ns at the satellite node, respectively. The total computing time required for the protocol is 2743.925ns. Besides, the three messaging times required for the authentication phase are 3×Tu−LEO=15ms. So the authentication delay of our proposed protocol is 15.003 ms and the computing time is only a small part of the authentication delay.In [23], the computing time depends on the maximum number of accesses N and the j−th access. In order to achieve the shortest time, we set N=1, j=1. Therefore, both the end user and the satellite node of the authentication process need to perform four hash operations and the computing times aare 4×Thu=723.856ns and 4×ThL=56.36ns, respectively. Besides, the five messaging times required for the authentication phase are 5×Tu−LEO=25ms. So, the authentication delay of [23] is 25.001 ms. However, in general, in order to reduce the computational task of TCS, N is set to a larger value which makes the authentication delay greatly increase and the performance of the protocol degrade.In [10], the protocol is based on the q−Strong Diffie–Hellman problem [32] where the execution of the protocol requires pairing operation, multiplication operation, and exponentiation operation in the additive cyclic group. The experimental results of these operations in [26] are as described in Table 3. In the authentication phase, the end user needs to execute the total of nine multiplication operations, three exponentiation operations, two pairing operations, and one hash operation, so the computing time of end user is 9×Tmulu+3×Texpu+2×Tpairu+Thu=115.485ms. The satellite node executes five multiplication operations, four exponentiation operations, two pairing operations, and one hash operation, so the computing time of satellite node is 5×TmulL+4×TexpL+2×TpairL+ThL=18.202ms. The total computing time required for the protocol is 133.687 ms. Besides, the two messaging times required for the authentication phase are 2×Tu−LEO=10ms. So, the authentication delay of [10] is 143.687 ms.Table 3
Execution times ofq−Strong DH related operations.
NotationSatellite node (ms)End user (ms)Tpair8.26252.533Tmul0.0020.012Texp0.4173.437Table4 shows the comparison of the authentication delays of our proposed protocol with the other two protocols. It can be seen from the table that the authentication delay of our proposed protocol is significantly lower than [10, 23], which is a more effective authentication scheme.Table 4
Comparison of authentication delay.
Satellite nodeEnd userTransmission timeTotal[23]56.36ns723.856ns25ms25.001ms[10]18.202ms115.485ms10ms143.687msOur220.917ns2523.008ns15ms15.003ms


## 6.2. Communication Overhead

According to the security of the protocol and the support for the device mentioned earlier, we set the size of elements inℝq to 4096 bits, the output of the SHA3 function is 512 bits, and the length of the identity and the timestamp is 100 bits. There are three message transmissions in the mutual authentication phase of our protocol. First, ui sends TIDui,wL,ts1,αL to LEOj. Then, LEOj responds pLj,ts2,α0 to ui. Finally, ui sends a confirmation message pui,wi,aid,ts3,αi to the LEOj. Therefore, the total communication overhead of the protocol is 100+4096+100+512+4096+100+512+4096+4096+512+100+512=18832 bits.In [23], both parties need to transmit six hash values and six identity messages, so the total transmission overhead is 6×512+6×100=3672 bits. In [10], assume that the length of element in cycle group and all signatures is 160 bits. Therefore, according to the communication overhead in [10], it can be concluded that the total of 2480 bits of messages needs to be transmitted during the authentication phase.It is worth noting that the communication overhead of the proposed protocol is greater than other protocols because the protocol is based on RLWE, and a common flaw in the ringℝq is that the key size is larger than the traditional encryption system. Considering that satellite network bandwidth has grown significantly and the authentication delay is small enough for delay-sensitive users, so we believe that our proposed protocol is a practicable scheme which is superior to other protocols.


## 7. Conclusion

In this paper we propose a novel RLWE-based anonymous mutual authentication protocol for SIN which is an antiquantum computing protocol. In the security analysis, we elaborated that the proposed protocol can meet the security requirements of SIN access authentication and compare the security with other related protocols. The analysis results show that our protocol is more secure than other protocols. Moreover, in the performance analysis, it is further stated that the authentication delay of our proposed protocol is very small. Although the communication overhead is slightly larger, the protocol we proposed under the trade-off communication delay and communication overhead is practical for SIN in the future.



---

*Source: 5167832-2020-08-25.xml*