# PSAA: Provable Secure and Anti-Quantum Authentication Based on Randomized
RLWE for Space Information Network

Junyan Guo, Ye Du, Xuesong Wu, Meihong Li, Runfang Wu, Zhichao Sun J. Guo, Y.
Du, X. Wu, M. Li, R. Wu and Z. Sun are with the Beijing Key Laboratory of
Security and Privacy in Intelligent Transportation, Beijing Jiaotong
University, Beijing 100044, China (Corresponding author: Y. Du, e-mail:
ydu@bjtu.edu.cn).

###### Abstract

Currently, due to the high scalability and global coverage of space
information network (SIN), more service providers and users are willing to
provide or subscribe to personal services through the satellite network.
However, the messages are transmitted in public satellite-ground links, which
makes access users vulnerable to various forms of attacks. Existing
authentication protocols do not meet the expected security and short delay
requirements to ensure the security of real-time user access and the
confidentiality of communication content. Moreover, with the development of
quantum computers, the difficult problems such as ECDLP and DLP have also been
proven to be solvable in polynomial time, leading to new threats. Therefore,
in this paper, we propose a provably secure and anti-quantum authentication
protocol based on randomized RLWE. The protocol not only meets the pre-defined
security requirements, but also reduces the total delay of the authentication
phase based on the pre-negotiation and fewer authentication transmission. In
addition, a concise handover scheme is designed for signal handover scenarios
caused by satellite dynamic topology. Further rigorous formal and informal
security proofs and performance analysis show that our proposed protocol is
more applicable to SIN, while ensuring higher security and resisting various
attacks with lower authentication delay.

###### Index Terms:

Access authentication, randomized RLWE, security analysis, space information
network

##  1 Introduction

With the continuous development of satellite communication technology, global
services free from time and geography constraints will gradually become
possible [1]. Space information network (SIN) as a large integrated
heterogeneous network, which includes satellite backbone networks, inter-
satellite links and satellite-ground links in a broad sense, is proposed in
this context to meet the needs of land-based, sea-based and space-based users
for real-time communication, navigation, disaster warning and other services.
Compared with traditional terrestrial networks, SIN has unique advantages.
First, as an extension of the terrestrial network, SIN provides reliable
communication and broadband services through satellite networks to sparsely
populated and remote areas such as the oceans, deserts, or mountainous regions
at a lower cost [2]. Secondly, as long as it has the ability to access and
communicate with satellites, regardless of geographic location, service
providers anywhere can provide subscription services to users around the
world. In addition, through the unified acquisition, coordination and
integration of satellite resources and ground resources, SIN can more easily
meet the needs of users for personalized and diverse [3].

At present, the Internet of Things (IoT) technology is booming, and the IoT
devices have been applied in various areas of work and life, such as smart
home, intelligent transportation and industrial control systems [4]. In some
scenarios, IoT devices are distributed in areas that cannot be covered by
traditional terrestrial networks and can only access SIN. However, due to the
openness of the satellite-to-ground link, the devices are vulnerable to
various attacks initiated by the adversary, such as eavesdropping attacks,
replay attacks, impersonation attacks, man-in-the-middle attacks, device loss
attacks and insider attacks, when they access to the network and then transmit
sensitive data [5]. The authentication protocol is an effective measure to
verify the legitimacy of access users and prevent malicious nodes from
accessing and performing destructive behaviors. If no effective access
authentication protocol is adopted, not only device privacy and confidential
data will be leaked, but also the computing and communication resources of SIN
will be greatly consumed, which will have a huge negative impact on the
stability of the whole society. Although many authentication protocols have
been proposed by scholars, they are not suitable for providing secure and
reliable communication services to time-sensitive users because of security
vulnerabilities or long authentication delay. Not only the above problems,
most existing protocols are proposed based on public key cryptography
mechanisms such as the discrete logarithm problem (DLP) and the elliptic curve
discrete logarithm problem (ECDLP), and these difficult assumptions have been
proved to be solved by Shor algorithm [6] in polynomial time, which ultimately
makes the protocols vulnerable. In addition, although Ma et al. [7] proposed
the first lattice-based anti-quantum three-party authentication protocol, the
security drawbacks and extremely large communication overhead make this
protocol not applicable to SIN. Therefore, in this paper, we propose a
sufficiently secure and low delay authentication protocol for SIN that
supports mutual authentication and negotiation the session key for SIN. In
particular, our main contributions in this paper are as follows:

  * (1)

We propose a new provable secure and anti-quantum authentication protocol for
SIN, named PSAA protocol. In the authentication phase, the satellite replaces
the terrestrial control station to verify the legitimate identity of the
access user, and as a relay node enable the terrestrial control station and
the user to negotiate a secure session key, which reduces the traditional at
least 4 satellite-to-ground transmissions to only 2 times. Moreover, for the
signal handover scenario caused by the satellite mobile topology, we also
designed a low computing and storage load handover verification scheme to
enable the next satellite and the user to mutually verify the legitimacy of
each other.

  * (2)

In the PSAA protocol, we add unpredictable random sample values based on
randomized ring learning with errors (RLWE) to avoid key reuse attacks without
affecting mutual authentication, key negotiation and identity privacy.

  * (3)

The security of PSAA protocol is proved by two formal and the informal
analysis methods, which proves not only the semantic security of the
negotiated session key, but also meets the security requirements and
resistance to various forms of attacks.

  * (4)

The performance analysis and comparison of security attributes, authentication
delay and communication overhead with related protocols show that the PSAA
protocol has less authentication delay and communication overhead than another
anti-quantum protocol and is more suitable for the user to access SIN under
the premise of ensuring higher security and quantum resistance.

The rest of the paper is organized as follows. Section 2 involves the related
work. Section 3 introduces the mathematical preliminaries. Section 4 details
the system model, threat model and security requirements. Section 5 elaborates
our proposed PSAA protocol. Sections 6 and 7 analyze the security and
performance, respectively. Finally, Section 8 draws the conclusion of this
paper.

##  2 Related Work

In recent years, researchers have successively proposed many authentication
protocols for SIN. Cruickshank et al. [8] first proposed the prototype of the
authentication protocol. However, in the protocol [8], the authentication
messages between the user and the terrestrial control station are all
encrypted and decrypted by the public key cryptographic mechanism, which makes
the system to bear the complex computation overhead. In addition, user privacy
is also not properly protected. To overcome the shortcomings in [8], Hwang et
al. [9] proposed using symmetric encryption mechanism to reduce the
computational overhead during authentication process and to protect the true
identity of user with a temporary identity, which has also been shown to be
resistant to replay attacks. However, Chang et al. [10] showed that [9] does
not satisfy forward security, and if the session key is leaked, the key
security of other sessions will be affected. Since then, Chen et al. [11]
proposed an authentication protocol that does not need to store the
certificate and can be self-verified based on the message authentication code
(MAC). In 2012, Zheng et al. [12] proposed a lightweight authentication
protocol based only on hash functions and XOR operations. Besides, [12] was
proved to be mutually authenticated by SVO logic. However, although [12]
greatly reduces the computational overhead, the high authentication delay
caused by 9 message transmissions is not suitable for real-time communication.
In addition, Zhao et al. [13] found [12] vulnerable to identity spoofing
attacks.

In 2019, Ostad-Sharif et al. [14] and Qi et al. [15] both proposed
authentication and session key negotiation protocols based on elliptic curve
cryptography. In these two protocols, the satellite acts as a relay node
between the user and the terrestrial control station during the authentication
phase, only forwarding the authentication message without verifying the
validity of the message and the sender. As a result, the adversary can send a
large number of useless messages to the satellite to consume the precious
satellite resources. In addition, [14] implements three-factor verification
including smart device, password, and biometric when the user logs in to avoid
device loss attacks, while [15] only verifies the two-factor, making it more
vulnerable to offline password attacks and smart device loss attacks. For [14]
and [15], the authentication is completed at least 4 satellite-to-ground
transmissions, which also causes the authentication delay to be too long to be
suitable for time-sensitive users. Recently, Yang et al. [16] and Xue et al.
[4] proposed that satellites verify the legitimacy of access users without the
need for TCS to be responsible for access control, which reduces the
authentication delay. However, neither of these two protocols can resist
device loss attacks, that is, the adversary can access SIN and obtain network
services after obtaining the device lost by the legitimate user. Besides, with
the development of quantum computers, the difficult problems based on elliptic
curve cryptography have been proved to be solved in polynomial time [6], which
makes the protocols [14, 15, 16, 4] no longer secure in the post-quantum era.

Recently, Ma et al. [7] proposed anti-quantum access authentication scheme
based on lattice and Gentry’s encryption mechanism. However, this scheme does
not design a specific mechanism to resist replay attacks and device loss
attacks. Moreover, the longer authentication delay and extremely large
communication overhead make [7] unsuitable for resource-constrained users and
SIN.

##  3 Mathematical Preliminaries

In this section, we briefly review and introduce the mathematical
preliminaries of ring learning with errors (RLWE) and biometric fuzzy
extractor involved in our proposed protocol.

###  3.1 Ring Learning With Errors

Define the quotient ring of a polynomial $R_{q}=Z_{q}[x]/(x^{n}+1)$, where $n$
is a power of 2 and $q$ is a prime number with modulo $n$ equal to 1. The
coefficient vector of any polynomial element $a$ in $R_{q}$ can be expressed
as $a=(a_{0},a_{1},\dots,a_{n-1})$. The Gaussian distribution on $R_{q}$ is
defined as $\chi_{\beta}$, where the positive real number $\beta$ is the
standard deviation of the distribution.

Let $Z_{q}=\\{-\frac{q-1}{2},\dots,\frac{q-1}{2}\\}$ and the middle set
$E=\\{-\lfloor\frac{q}{4}\rfloor,\dots,\lfloor\frac{q}{4}\rfloor\\}$, then the
error reconciliation of RLWE has the following two core functions, namely
$Cha$ and $Mod_{2}$. $Cha$ is considered a characteristic function, that is,
if $x\in E$ then $Cha(x)=1$, otherwise $Cha(x)=0$. The other is the auxiliary
modular function, $Mod_{2}(v,w)=(v+w\cdot\frac{q-1}{2})\bmod q\bmod 2$, where
$v\in Z_{q}$, $w=Cha(v)$ [17, 18]. These two functions have the following
lemma.

Lemma 1: Given an odd prime number $q$ and two elements $v,w\in Z_{q}$, then
$Mod_{2}(v,Cha(v))=Mod_{2}(w,Cha(v))$, where
$\left|v-w\right|\leq\frac{q}{4}-2$. Similarly, this lemma also holds for the
polynomial ring elements in $R_{q}$ [19].

Since the key reuse attack has been proved to have a security threat to the
original reconciliation-based RLWE scheme, that is, using the same public key
more than the usage threshold will cause the adversary to recover the
corresponding private key through $Cha$ function values [20]. In order to fix
this vulnerability, [21] proposed a randomized RLWE scheme, which improves
randomization by adding additional unpredictable error values to prevent the
adversary from obtaining the private key. Our proposed PSAA protocol is based
on the randomized RLWE of [21], which avoids the threat of private key leakage
caused by using the same public key.

Definition 1: RLWE assumption: Let $R_{q}$ and $\chi_{\beta}$ be as defined
above and a fix polynomial ring elements $s\in R_{q}$, $A_{s,\chi_{\beta}}$ is
the distribution over $(a,a\cdot s+2\cdot e)$, where $a$, $e$ are randomly
sampled from $R_{q}$. RLWE assumption implies that it is difficult to
distinguish $A_{s,\chi_{\beta}}$ from uniform distribution on $R^{2}_{q}$ in
polynomial time, and it can be reduced to Shortest Vector Problem (SVP) in the
lattice [18, 19, 21].

###  3.2 Biometric Fuzzy Extractor

The biometric key is more secure than the password in that it has higher
entropy and is not only able to identify users with higher accuracy but also
can’t be forgotten [22]. The biometric fuzzy extractor can generate a
biometric key based on biometric features such as iris, fingerprint, etc., and
re-extract the same biometric key from the biometric features within the error
threshold during re-identification [23]. The fuzzy extractor contains two
functions, $Gen$ and $Rep$, which are described in detail as follows.

  * •

$Gen(BIO)$ is the probabilistic generation function that inputs the biometric
$BIO$ and outputs the biometric key $\sigma$ and the public auxiliary data
$v$.

  * •

$Rep(BIO^{*},v)$ is the reproduction function that retrieves the biometric key
$\sigma$ from the auxiliary data $v$ and the re-entered biometric $BIO^{*}$ if
and only if the error between $BIO$ and $BIO^{*}$ is less than the threshold
$\delta$.

##  4 System Model, Threat Model and Security Requirements

This section describes in detail the system model, threat model and security
requirements in SIN.

###  4.1 System Model

Figure 1: System model

As shown in Figure 1, the SIN traditionally contains four types of entities:
network control center (NCC), terrestrial control station (TCS), satellite
node and user. The following details describe the functions of each entity.

  * •

As mentioned in [16, 4], NCC is a fully trusted control and monitoring center
for the entire system, providing registration services for satellite nodes and
terrestrial control stations, and has the highest level of security protection
so that no other adversary can break its security mechanism and obtain
confidential information.

  * •

TCS provides registration services for users and subscription services for
registered users through relay satellites.

  * •

Satellite node serves as a relay node for communication between the user and
the TCS, and the subscription service provided by the TCS can be forwarded to
the user through the satellite node. To ensure the signal strength and the
quality of service for time-sensitive users, low earth orbit (LEO) satellites
that is closer to the user are usually used as relay nodes [14]. In addition,
the satellite already has the ability to perform complex calculations [16, 4].

  * •

User registered at TCS during the registration phase can use the smart device
to calculate, store and communicate with satellites to receive subscription
services provided by TCS.

###  4.2 Threat Model

The threat model of the proposed protocol defines the adversary’s capabilities
based on the widely used Dolev-Yao model [24] and Canetti-Krawczyk model [25],
that is, adversaries can not only control insecure or public channels in SIN,
but also obtain the confidential information in the user’s smart device. The
adversary assumes the following specific capabilities.

  * •

Adversary can eavesdrop, store and replay all the authentication interaction
information in the public channel.

  * •

Adversary can forge or modify the eavesdropped authentication information and
resend it to the legitimate node.

  * •

Adversary can obtain the information stored in the user device through power
analysis [26].

  * •

Adversary knows the details of the authentication protocol and can obtain a
clear and correct response after sending an authentication message as a
participant of the protocol.

###  4.3 Security Requirements

Based on existing authentication protocols, we conclude that a well-designed
and secure protocol in SIN should meet the following security requirements.

  * •

Mutual authentication. When the user accesses SIN, the user and the satellite
should be able to mutually verify the legitimacy of each other.

  * •

Key negotiation. During the authentication phase, the user and TCS should be
able to negotiate a secure session key to protect the next communication, and
the session key should be determined by both parties, not only by one party.

  * •

Identity anonymous. The user’s identity is sensitive and private information
that should be anonymized to prevent the adversary from obtaining its true
identity.

  * •

Perfect forward/backward secrecy. The security of previous and future session
keys is not compromised when the current session key is obtained by the
adversary.

  * •

Attacks resistance. To ensure the reliability and security of the
authentication process, the protocol proposed should be able to withstand
various forms of attacks such as eavesdropping attacks, replay attacks,
impersonation attacks, man-in-the-middle attacks, device loss attacks, and
insider attacks. In addition, because the rapid development of quantum
computing poses a great threat to authentication protocols based on elliptic
curve and discrete logarithmic cryptography, our proposed protocol should also
be resistant to quantum attacks to avoid leakage of privacy and confidential
information.

##  5 Proposed Protocol: PSAA

In this section, we describe in detail the proposed PSAA protocol in the order
of the system initialization phase, registration phase, pre-negotiation phase,
login and authentication phase, handover phase, password and biometric update
phase. In addition, to introduce the PSAA protocol more conveniently and
unambiguously, we simplify the system to include only one satellite $L_{j}$,
one TCS and one user $u_{i}$. The symbols involved in the protocol are shown
in Table I.

TABLE I: Symbol list Notation |  Description
---|---
$ID_{j},ID_{tcs}$ |  Identity of $L_{j}$ and TCS
$ID_{i}$ |  True identity of $u_{i}$
$TID_{i}$ |  Temporary Identity of $u_{i}$
$PW_{i},BIO_{i}$ |  Password and biometric of $u_{i}$
$q$ |  Odd prime
$n$ |  Power of 2
$\chi_{\beta}$ |  Discrete Gaussian distribution with scalar $\beta$
$re,se,te$ |  Random sampled values from $\chi_{\beta}$
$R_{q}$ |  Polynomial ring
$sk_{ncc}$ |  Private key of NCC
$pk_{j},sk_{j}$ |  Public and private key pair of $L_{j}$
$pk_{i},sk_{i}$ |  Public and private key pair of $u_{i}$
$pk_{tcs},sk_{tcs}$ |  Public and private key pair of TCS
$Gen(\cdot),Rep(\cdot)$ |  Two functions of biometric fuzzy extractor
$\sigma_{i}$ |  Biometric key of $u_{i}$
$v_{i}$ |  Auxiliary data of $\sigma_{i}$
$h(\cdot)$ |  Secure hash function $h:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{l}$
$H(\cdot)$ |  Secure hash function $H:\\{0,1\\}^{*}\rightarrow R_{q}$
$t,T$ |  Timestamp
$\oplus$ |  XOR operation
$key$ |  Session key

###  5.1 System Initialization Phase

NCC generates system public parameters and the master private key through the
following steps.

  * (1)

NCC first chooses an integer $n$ that is a power of 2 and then chooses the
prime number $q$ such that $q\bmod n=1$.

  * (2)

NCC chooses the discrete Gaussian distribution $\chi_{\beta}$ with the
standard deviation $\beta$ on polynomial ring $R_{q}$.

  * (3)

Next, NCC chooses two secure hash functions
$h:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{l}$ and $H:\\{0,1\\}^{*}\rightarrow
R_{q}$, and two functions of the biometric fuzzy extractor, namely
$Gen(\cdot)$ and $Rep(\cdot)$.

  * (4)

Then NCC randomly selects two elements $a$ and $sk_{ncc}$ from $\chi_{\beta}$.

  * (5)

Finally, NCC uses $sk_{ncc}$ as the master private key and stores it
confidentially, then publishes public parameters and functions
$\\{n,q,\chi_{\beta},a,h(\cdot),H(\cdot),Gen(\cdot),Rep(\cdot)\\}$ to the
entire system.

###  5.2 Registration Phase

The registration phase is divided into two categories by entity type, one is
TCS and satellite node registration, the other is user registration. During
the registration phase of TCS and satellite node, TCS and satellite node
submit registration requests to NCC to obtain public-private key pairs issued
by NCC. Similarly, in the user registration phase, the user submits a
registration request to the TCS that provides a specific subscription services
to obtain the authentication parameters required for access. It is worth
mentioning that during the registration phase all messages are transmitted
over secure channels. The detailed steps for the registration phase are
described below.

TCS registration. First, TCS randomly samples $sk_{tcs}$ and $se_{tcs}$ from
$\chi_{\beta}$, and calculates $pk_{tcs}=a\cdot sk_{tcs}+2\cdot se_{tcs}$,
where $pk_{tcs}$ and $sk_{tcs}$ are the master public-private key pairs of
TCS. Then TCS sends its identity $ID_{tcs}$ and $pk_{tcs}$ to NCC. Finally,
NCC calculates $p_{ncc}=h(sk_{ncc},T)$, where $T$ is the expiration timestamp,
then publicly publishes $\\{ID_{tcs},pk_{tcs},T\\}$ to the entire system. TCS
securely stores $\\{sk_{tcs},p_{ncc}\\}$.

Satellite node registration. The registration process is similar to TCS
registration. First, $L_{j}$ randomly samples master private key $sk_{j}$ and
$se_{j}$ from $\chi_{\beta}$, calculates master public key $pk_{j}=a\cdot
sk_{j}+2\cdot se_{j}$, and sends $\\{ID_{j},pk_{j}\\}$ to NCC. Then NCC
publicly publishes $\\{ID_{j},pk_{j},T\\}$ to the entire system. Finally,
$L_{j}$ securely stores $\\{sk_{j},p_{ncc}\\}$.

When the validity of TCS and satellite nodes reach the expiration time $T$,
the registration request needs to be resubmitted to NCC.

Figure 2: User registration

User registration. As shown in Figure 2, $u_{i}$ registers with TCS through
the following steps.

  * (1)

$u_{i}$ enters the identity $ID_{i}$, password $PW_{i}$, and biometric
$BIO_{i}$, then executes the probabilistic generation function $Gen(BIO_{i})$
to obtain the biometric key $\sigma_{i}$ and the public auxiliary data
$v_{i}$. Next, $u_{i}$ calculates $RPW_{i}=h(PW_{i},\sigma_{i})$ and master
public key $pk_{i}=a\cdot sk_{i}+2\cdot se_{i}$, where $sk_{i}$ and $se_{i}$
are randomly sampled from $\chi_{\beta}$ and $sk_{i}$ is the master private
key. Finally, $u_{i}$ sends the registration request
$\\{ID_{i},RPW_{i},pk_{i}\\}$ to TCS.

  * (2)

After receiving the registration request from $u_{i}$, TCS calculates
$sk^{0}_{i-tcs}=(pk_{i}\cdot sk_{tcs}+2\cdot te^{0}_{i-tcs})\cdot
te^{0}_{i-tcs}+2\cdot re^{0}_{i-tcs}$, where $te^{0}_{i-tcs}$ and
$re^{0}_{i-tcs}$ are randomly sampled from $\chi_{\beta}$. Next, TCS
calculates $sw^{0}_{i-tcs}=Cha(sk^{0}_{i-tcs})$,
$s\sigma^{0}_{i-tcs}=Mod_{2}(sk^{0}_{i-tcs},sw^{0}_{i-tcs})$, $u_{i}$’s
temporary identity $TID_{i}=ID_{i}\oplus s\sigma^{0}_{i-tcs}$,
$p_{i}=h(TID_{i},pk_{i},sk_{tcs})$, $mpu=h(ID_{tcs},pk_{tcs},sk_{tcs})$,
$pu_{i}=h(TID_{i},h(mpu,T))$, $DID_{i}=TID_{i}\oplus h(ID_{i},RPW_{i})$,
$DP_{i}=p_{i}\oplus RPW_{i}$, $DPU_{i}=pu_{i}\oplus h(TID_{i},p_{i})$,
$mver^{*}=h(TID_{i},p_{i},pu_{i})$. Finally, TCS returns the registration
response $\\{DID_{i},DP_{i},DPU_{i},mver^{*}\\}$ to $u_{i}$ and securely
stores $\\{TID_{i},pk_{i},s\sigma^{0}_{i-tcs},p_{i},mpu,pu_{i}\\}$.

  * (3)

$u_{i}$ calculates $DSK_{i}=sk_{i}\oplus mver^{*}$,
$ver_{i}=h(TID_{i},DID_{i},DP_{i},sk_{i})$ after receiving the registration
response, where $ver_{i}$ is used to verify the correctness of the identity
$ID_{i}$, password $PW_{i}$ and biometric $BIO_{i}$ entered by the user when
logging in, and to check that the authentication parameters stored in the
device have not been modified. Finally, $u_{i}$ stores
$\\{DID_{i},DP_{i},DPU_{i},DSK_{i},ver_{i},v_{i}\\}$ in the device.

###  5.3 Pre-Negotiation Phase

Figure 3: Pre-Negotiation phase

Figure 3 shows the pre-negotiation phase between the satellite and TCS. The
satellite sends a pre-negotiation request to negotiate authentication
parameters for future user access and construct a secure channel with TCS.
Pre-negotiation reduces the computational and communication overhead of user
access authentication phase to meet the quality of service requirements of
time-sensitive users. The detailed steps of pre-negotiation phase are as
follows.

Figure 4: Authentication process

  * (1)

$L_{j}$ calculates $DPK_{j}=pk_{j}+H(p_{ncc},t_{1})$,
$a_{1}=h(ID_{j},pk_{j},DPK_{j},t_{1})$, where $t_{1}$ is the current
timestamp, and then sends the pre-negotiation message
$\\{ID_{j},DPK_{j},t_{1},a_{1}\\}$ to TCS.

  * (2)

After receiving the pre-negotiation message
$\\{ID_{j},DPK_{j},t_{1},a_{1}\\}$, TCS first checks the freshness of $t_{1}$
by verifying whether the timestamp is within the allowable transmission delay
threshold. Next, TCS calculates
$pk^{{}^{\prime}}_{j}=DPK_{j}-H(p_{ncc},t_{1})$ and checks whether
$a_{1}=h(ID_{j},pk^{{}^{\prime}}_{j},DPK_{j},t_{1})$ holds. If the check
passes, the pre-negotiation message sent by $L_{j}$ has not been tampered with
and is indeed sent by the legitimate satellite node, otherwise terminate the
pre-negotiation. Then TCS randomly samples $te_{j-tcs}$ and $re_{j-tcs}$ from
$\chi_{\beta}$ and calculates $sk_{j-tcs}=(pk^{{}^{\prime}}_{j}\cdot
sk_{tcs}+2\cdot te_{j-tcs})\cdot te_{j-tcs}+2\cdot re_{j-tcs}$,
$sw_{j-tcs}=Cha(sk_{j-tcs})$,
$s\sigma_{j-tcs}=Mod_{2}(sk_{j-tcs},sw_{j-tcs})$,
$DCU_{j}=s\sigma_{j-tcs}\oplus h(mpu,T)$,
$a_{2}=h(ID_{tcs},pk_{tcs},s\sigma_{j-tcs},h(mpu,T),t_{2})$ and the session
key between $L_{j}$ and TCS is
$k_{j-tcs}=h(ID_{tcs},ID_{j},s\sigma_{j-tcs},t_{2})$, where $t_{2}$ is the
timestamp, $k_{j-tcs}$ is used to construct the secure channel between $L_{j}$
and TCS to protect the security of future mutual communication during access
authentication phase and communication. Finally, TCS sends the pre-negotiation
response $\\{ID_{tcs},pk_{tcs},sw_{j-tcs},te_{j-tcs},DCU_{j},t_{2},a_{2}\\}$
to $L_{j}$.

  * (3)

After receiving the message
$\\{ID_{tcs},pk_{tcs},sw_{j-tcs},te_{j-tcs},DCU_{j},t_{2},a_{2}\\}$, $L_{j}$
first checks the timestamp $t_{2}$, then randomly samples
$re^{{}^{\prime}}_{j-tcs}$ from $\chi_{\beta}$ and calculates
$sk^{{}^{\prime}}_{j-tcs}=(pk_{tcs}\cdot sk_{j}+2\cdot te_{j-tcs})+2\cdot
re^{{}^{\prime}}_{j-tcs}$,
$s\sigma^{{}^{\prime}}_{j-tcs}=Mod_{2}(sk^{{}^{\prime}}_{j-tcs},sw_{j-tcs})$
and $HPU_{j}=DCU_{j}\oplus s\sigma^{{}^{\prime}}_{j-tcs}$. Next, $L_{j}$
checks whether
$a_{2}=h(ID_{tcs},pk_{tcs},s\sigma^{{}^{\prime}}_{j-tcs},HPU_{j},t_{2})$
holds. If the equation holds, the pre-negotiation response message is not
modified and $L_{j}$ confirms that the sender is the legitimate node. Finally,
$L_{j}$ calculates
$k_{j-tcs}=h(ID_{tcs},ID_{j},s\sigma^{{}^{\prime}}_{j-tcs},t_{2})$, which is
used as the session key to construct a secure communication channel with TCS.

###  5.4 Login and Authentication Phase

Before accessing SIN and submitting the access request, the user needs to
complete the three-factor login verification, that is, verify the parameters
stored in the smart device and the identity, password and biometric entered by
the user. Login verification can prevent the adversary from using the user’s
lost device to send a large number of access requests and consume the
computing and communication resources of the satellite and TCS in SIN. The
detailed steps of login and authentication phase are as follows, and the
authentication phase is shown in Figure 4.

  * (1)

$u_{i}$ enters the identity $ID^{*}_{i}$, password $PW^{*}_{i}$ and scans the
biometric $BIO^{*}_{i}$, and then obtains the biometric key $\sigma^{*}_{i}$
through the reproduction function of biometric fuzzy extractor and the public
auxiliary data $v_{i}$. Next, $u_{i}$ calculates
$RPW^{{}^{\prime}}_{i}=h(PW^{*}_{i},\sigma^{*}_{i})$,
$TID^{{}^{\prime}}_{i}=DID_{i}\oplus h(ID^{*}_{i},RPW^{{}^{\prime}}_{i})$,
$p^{{}^{\prime}}_{i}=DP_{i}\oplus RPW^{{}^{\prime}}_{i}$,
$pu^{{}^{\prime}}_{i}=DPU_{i}\oplus
h(TID^{{}^{\prime}}_{i},p^{{}^{\prime}}_{i})$,
$sk^{{}^{\prime}}_{i}=DSK_{i}\oplus
h(TID^{{}^{\prime}}_{i},p^{{}^{\prime}}_{i},pu^{{}^{\prime}}_{i})$, and checks
whether $ver_{i}=h(TID^{{}^{\prime}}_{i},DID_{i},DP_{i},sk^{{}^{\prime}}_{i})$
holds. If the check passes, it means that $ID^{*}_{i}$, $PW^{*}_{i}$ and
$BIO^{*}_{i}$ entered by $u_{i}$ are correct and the parameters
$\\{DID_{i},DP_{i},DPU_{i},DSK_{i},ver_{i},v_{i}\\}$ stored in the device have
not been tampered with, otherwise the login is terminated. After that, $u_{i}$
randomly samples $te^{1}_{i-tcs}$ and $re^{1}_{i-tcs}$ from $\chi_{\beta}$ and
calculates $sk^{1}_{i-tcs}=(pk_{tcs}\cdot sk_{i}+2\cdot te^{1}_{i-tcs})\cdot
te^{1}_{i-tcs}+2\cdot re^{1}_{i-tcs}$, $sw^{1}_{i-tcs}=Cha(sk^{1}_{i-tcs})$,
$s\sigma^{1}_{i-tcs}=Mod_{2}(sk^{1}_{i-tcs},sw^{1}_{i-tcs})$,
$HPU_{i}=h(pu_{i},t_{3})$,
$HP_{i}=h(TID_{i},ID_{tcs},p_{i},s\sigma^{1}_{i-tcs})$, $a_{3}=HPU_{i}\oplus
HP_{i}$,
$a_{4}=h(TID_{i},ID_{tcs},te^{1}_{i-tcs},sw^{1}_{i-tcs},HPU_{i},a_{3},t_{3})$,
where $t_{3}$ is the timestamp. Finally, $u_{i}$ sends the access request
$\\{TID_{i},ID_{tcs},te^{1}_{i-tcs},sw^{1}_{i-tcs},a_{3},a_{4},t_{3}\\}$ to
$L_{j}$.

  * (2)

After receiving the access request from $u_{i}$, $L_{j}$ first checks the
timestamp $t_{2}$ of the message, calculates
$HPU^{{}^{\prime}}_{i}=h(h(TID_{i},HPU_{j}),t_{3})$ and verifies whether
$a_{4}=h(TID_{i},ID_{tcs},te^{1}_{i-tcs},sw^{1}_{i-tcs},HPU^{{}^{\prime}}_{i},a_{3},t_{3})$
is established. If the verification is passed, the access request received
through the non-secure channel has not been maliciously modified and comes
from the legitimate node $u_{i}$. Next, $L_{j}$ calculates
$HP^{{}^{\prime}}_{i}=a_{3}\oplus HPU^{{}^{\prime}}_{i}$,
$a_{5}=h(HP^{{}^{\prime}}_{i},TID_{i},te^{1}_{i-tcs},sw^{1}_{i-tcs},t_{4})$,
where $t_{4}$ is the current timestamp. Finally, $L_{j}$ simultaneously sends
$\\{a_{5},t_{4}\\}$ and
$\\{TID_{i},te^{1}_{i-tcs},sw^{1}_{i-tcs},HP_{i},t_{4}\\}$ to $u_{i}$ and TCS,
respectively.

  * (3)

After receiving the message $\\{a_{5},t_{4}\\}$ from $L_{j}$, $u_{i}$ checks
the timestamp $t_{4}$ and whether
$a_{5}=h(HP_{i},TID_{i},te^{1}_{i-tcs},sw^{1}_{i-tcs},t_{4})$ is established.
If the check passes, $u_{i}$ calculates the session key
$key=h(TID_{i},ID_{tcs},pk_{i},pk_{tcs},s\sigma^{1}_{i-tcs})$.

  * (4)

TCS receives $\\{TID_{i},te^{1}_{i-tcs},sw^{1}_{i-tcs},HP_{i},t_{4}\\}$ from
$L_{j}$, first checks the timestamp $t_{4}$ and randomly samples
$re^{1^{\prime}}_{i-tcs}$ from $\chi_{\beta}$, then calculates
$sk^{1^{\prime}}_{i-tcs}=(pk_{i}\cdot sk_{tcs}+2\cdot te^{1}_{i-tcs})\cdot
te^{1}_{i-tcs}+2\cdot re^{1^{\prime}}_{tcs}$,
$s\sigma^{1^{\prime}}_{i-tcs}=Mod_{2}(sk^{1^{\prime}}_{i-tcs},sw^{1^{\prime}}_{i-tcs})$.
Next, TCS checks whether
$HP_{i}=h(TID_{i},ID_{tcs},p_{i},s\sigma^{1^{\prime}}_{i-tcs})$ holds. If the
equation holds, TCS confirms that $u_{i}$ is the legitimate user and then
calculates the session key
$key=h(TID_{i},ID_{tcs},pk_{i},pk_{tcs},s\sigma^{1^{\prime}}_{i-tcs})$.

So far, the satellite and TCS authenticate the legitimacy of the access user.
Similarly, the user confirms the legitimacy of the satellite node.
Furthermore, the session key $key$ will protect the future communication
between the TCS and the user.

###  5.5 Handover Phase

Figure 5: Handover scenario

As shown in Figure 5, the blue circle is the current satellite (C-SAT) signal
coverage, and the red circle is the next satellite (N-SAT) signal coverage.
Due to the mobility of C-SAT, the signal strength received by the user and TCS
gradually decreases. At this time, the user and TCS need to make signal
handover in the overlapping areas of C-SAT and N-SAT satellite signal
coverage. In the handover process, only relay satellite replacement is
involved, which means that the user and TCS do not need to renegotiate the new
session key but only need to mutually authenticate with N-SAT separately.
Although Xue et al. [4] proposed a handover verification scheme based on the
whitelist mechanism for such handover scenario, there are many shortcomings as
follows. First, the user does not confirm the validity of the N-SAT relay
satellite before handing over the signal. Secondly, the user’s handover
request can be easily captured and replayed by an adversary to obtain the
N-SAT signal relay service. Finally, since the relay satellite typically serve
thousands of users, using the whitelist mechanism can greatly consume the
valuable storage capacity of the satellite. Therefore, to overcome the above
shortcomings, we propose a handover scheme that supports mutual authentication
between the user and the N-SAT, resists replay attacks and does not consume
the storage overhead of the N-SAT satellite. The detailed steps of the
handover phase are as follows.

  * (1)

Pre-negotiation. Similar to the pre-negotiation phase in the third subsection
of this section, TCS and N-SAT mutually confirm the legal identity of each
other through pre-negotiation, and TCS transmits to N-SAT the authentication
parameter $HPU_{N-SAT}$ that enable N-SAT and the user to mutually
authenticate.

  * (2)

$u_{i}$ sends the handover request. After $u_{i}$ enters the correct identity
$ID_{i}$, password $PW_{i}$ and biometric $BIO_{i}$, then randomly samples
$HO_{i}$ from $\chi_{\beta}$ and calculates $HPU_{i}=h(pu_{i},t_{5})$,
$HPO_{i}=HPU_{i}\oplus h(HO_{i},t_{5})$,
$a_{6}=h(TID_{i},ID_{N-SAT},HPO_{i},HPU_{i},t_{5})$, where $t_{5}$ is the
timestamp. Finally, $u_{i}$ sends the handover request
$\\{TID_{i},ID_{N-SAT},HPO_{i},a_{6},t_{5}\\}$ via C-SAT to N-SAT.

  * (3)

N-SAT verification. N-SAT first checks the freshness of the timestamp $t_{5}$,
then calculates $HPU^{{}^{\prime}}_{i}=h(h(TID_{i},HPU_{N-SAT}),t_{5})$ and
checks whether
$a_{6}=h(TID_{i},ID_{N-SAT},HPO_{i},HPU^{{}^{\prime}}_{i},t_{5})$ holds. If
the check passes, the handover request is not tampered with and $u_{i}$ is a
legitimate user. Next, N-SAT calculates
$a_{7}=h(TID_{i},ID_{N-SAT},HPO_{i}\oplus HPU^{{}^{\prime}}_{i},t_{6})$ and
sends the request response $\\{a_{7},t_{6}\\}$ to $u_{i}$.

  * (4)

$u_{i}$ verification. $u_{i}$ checks the timestamp $t_{6}$ and whether
$a_{7}=h(TID_{i},ID_{N-SAT},h(HO_{i},t_{5}),t_{6})$ holds. If the check
passes, $u_{i}$ confirms that N-SAT is a valid relay node and the future
mutual communication between the user and TCS will be relayed by N-SAT.

In the third and fourth steps of the handover process, the N-SAT satellite and
the user mutually authenticate each other for legitimacy. And since the
handover messages include timestamps and one-way hash check values, the
adversary cannot obtain relay services from the satellite through replay
attacks. Furthermore, the N-SAT satellite only needs three hashing operations
and does not need to store the whitelist but only stores the authentication
parameter $HPU_{N-SAT}$ negotiated with TCS in the pre-negotiation phase,
which greatly reduces the computing and storage load of the resource-
constrained relay satellite.

###  5.6 Password and Biometric Update Phase

For some security purposes, the user can update his or her password and
biometric without interacting with TCS, which can greatly reduce the
communication and computation overhead of TCS. The detailed steps of the
password and biometric update phase are as follows.

  * (1)

$u_{i}$ enters the identity $ID^{*}_{i}$, old password $PW^{old}_{i}$, and
biometric $BIO^{old}_{i}$ then obtains the biometric key $\sigma^{old}_{i}$
through $Rep$ function.

  * (2)

The device calculates
$RPW^{{}^{\prime}}_{i}=h(PW^{old}_{i},\sigma^{old}_{i})$,
$TID^{{}^{\prime}}_{i}=DID_{i}\oplus h(ID^{*}_{i},RPW^{{}^{\prime}}_{i})$,
$p^{{}^{\prime}}_{i}=DP_{i}\oplus RPW^{{}^{\prime}}_{i}$,
$pu^{{}^{\prime}}=DPU_{i}\oplus h(TID^{{}^{\prime}}_{i},p^{{}^{\prime}}_{i})$,
$sk^{{}^{\prime}}_{i}=DSK_{i}\oplus
h(TID^{{}^{\prime}}_{i},p^{{}^{\prime}}_{i},pu^{{}^{\prime}}_{i})$, and checks
whether $ver_{i}=h(TID^{{}^{\prime}}_{i},DID_{i},DP_{i},sk^{{}^{\prime}}_{i})$
holds. If the check passes, continue to the next step, otherwise terminate the
update.

  * (3)

$u_{i}$ enters new password $PW^{new}_{i}$ and biometric $BIO^{new}_{i}$, then
obtains the new biometric key $\sigma^{new}_{i}$ and auxiliary data
$v^{new}_{i}$ through $Gen$ function.

  * (4)

The device calculates $RPW^{new}_{i}=h(PW^{new}_{i},\sigma^{new}_{i})$,
$DID^{new}_{i}=TID_{i}\oplus h(ID_{i},RPW^{new}_{i})$,
$DP^{new}_{i}=p_{i}\oplus RPW^{new}_{i}$,
$ver^{new}_{i}=h(TID_{i},DID^{new}_{i},DP^{new}_{i},sk_{i})$ and finally
deletes {$DID^{old}_{i}$, $DP^{old}_{i}$, $v^{old}_{i}$, $ver_{i}$} and stores
{$DID^{new}_{i}$, $DP^{new}_{i}$, $v^{new}_{i}$, $ver^{new}_{i}$} in the
device. After that, $u_{i}$ can log in with the new password $PW^{new}_{i}$
and new biometric $BIO^{new}_{i}$.

##  6 Security Analysis

In this section, we first formally prove the security of our proposed PSAA
protocol based on the widely accepted random oracle model (ROM) [27, 28] and
the automated validation of internet security protocols and applications
(AVISPA) tool [29], in which ROM proves the semantic security of the
negotiated session key, and AVISPA proves that the PSAA protocol can resist
eavesdropping attacks, replay attacks and man-in-the-middle attacks. Then the
informal security analysis method discusses that PSAA protocol can meet the
security requirements mentioned in Section 4.

###  6.1 Formal Security Analysis Based on ROM

According to protocol we proposed, there are a total of three instances in the
authentication phase, namely $u_{i}$, $L_{j}$ and TCS. Based on the threat
model, the adversary $\mathcal{A}$ is defined as a Turing machine that
attempts to break the PSAA protocol in probabilistic polynomial time. The
following definitions need to be made before ROM-based proof.

Participants. The symbols $\prod^{x}_{u_{i}}$, $\prod^{y}_{L_{j}}$ and
$\prod^{z}_{TCS}$ represent the $x$-th, $y$-th, and $z$-th instances of
$u_{i}$, $L_{j}$, and TCS, respectively. Each instance is an oracle, that is,
after receiving the correct authentication message, it will respond honestly.

Accepted state. After instance $\prod^{x}$ receives the last correct expected
message according to the steps of authentication phase, the instance is in the
accepted state. The session identification $sid$ represents all the messages
received and sent in sequence in the current session of instance $\prod^{x}$.

Freshness. If the current session key of instance $\prod^{x}$ or its partner
$\prod^{y}$ is not obtained by adversary $\mathcal{A}$, then instance
$\prod^{x}$ or $\prod^{y}$ is said to be fresh.

Partnering. Instances $\prod^{x}$ and $\prod^{y}$ become partners when they
meet the following three conditions simultaneously.

  * •

$\prod^{x}$ and $\prod^{y}$ are all in the accepted state.

  * •

$\prod^{x}$ and $\prod^{y}$ have the same session identification $sid$ and
mutually authenticate each other.

  * •

$\prod^{x}$ and $\prod^{y}$ are each other’s partners [30].

Adversary. As described in the threat model, $\mathcal{A}$ can not only
intercept all messages transmitted in the public channel and modify, forge and
replay them, but also obtain information stored in the user’s smart device
through power analysis. We define the capabilities of $\mathcal{A}$ as the
following query oracles.

  * •

Execute($\prod^{x}_{u_{i}}$, $\prod^{y}_{L_{j}}$, $\prod^{z}_{TCS}$).
$\mathcal{A}$ can obtain all authentication messages transmitted by instances
$\prod^{x}_{u_{i}}$, $\prod^{y}_{L_{j}}$ and $\prod^{z}_{TCS}$ in the public
channel during the authentication process through this query. The query oracle
can be regarded as an eavesdropping attack.

  * •

Send($\prod^{x}$, M). Through this query, $\mathcal{A}$ can send a message M
to instance $\prod^{x}$, where M can be a message obtained by eavesdropping,
or a modified or forged message.

  * •

Reveal($\prod^{x}$). $\mathcal{A}$ can obtain the current session key of
instance $\prod^{x}$ and its partner $\prod^{y}$ through the Reveal query.

  * •

$h$(M). $h$ oracle maintains a hash list $L_{h}:\\{M_{i},\zeta_{i}\\}$, where
$\zeta_{i}$ is the hash value of message $M_{i}$. When $\mathcal{A}$ queries
$h$ oracle for the hash value of the message M, if M is in $L_{h}$, returns
$\zeta$, otherwise $\zeta$ is randomly selected from $\\{0,1\\}^{l}$, then
$\zeta$ is stored in $L_{h}$ and returned to $\mathcal{A}$.

  * •

CorruptSmartDevice($\prod^{x}$). $\mathcal{A}$ can obtain the information
stored in instance $\prod^{x}$ through this query. This query can be regarded
as a power analysis attack or a side channel attack on the user’s smart device
[28, 31].

  * •

Test($\prod^{x}$). Test query is to check whether the current session key
$key$ of $\prod^{x}$ meets semantic security under the random oracle model.
When $\mathcal{A}$ queries the test oracle, $\prod^{x}$ first chooses an
unbiased coin $C\in\\{0,1\\}$ and flip it. If $C=1$, $\prod^{x}$ returns the
current session key $key$ to $\mathcal{A}$, and if $C=0$, $\prod^{x}$ returns
to $\mathcal{A}$ a random string $str$ of the same length as $key$, otherwise
returns null.

Semantic security of session key. In ROM, if $\mathcal{A}$ cannot distinguish
the true session key from the session key and a random string of the same
length as the session key, it means that $\mathcal{A}$ cannot compromise the
semantic security of the session key. When testing the semantic security of
the session key, $\mathcal{A}$ can query Test($\prod^{x}$) multiple times.
Each time $\prod^{x}$ re-selects an unbiased coin $C$ and flip it, then
$\mathcal{A}$ guesses the true value of the coin is $C^{{}^{\prime}}$ through
the above query. If $C=C^{{}^{\prime}}$, $\mathcal{A}$ wins the game. We
define the probability of $\mathcal{A}$ to win the game as $Pr(Succ)$, and the
advantage of breaking the protocol PSAA is
$Adv^{\mathcal{A}}_{PSAA}=|2Pr(Succ)-1|$. When
$Adv^{\mathcal{A}}_{PSAA}<\epsilon$, the protocol PSAA is secure and
$\mathcal{A}$ cannot compromise the semantic security of the session key,
where $\epsilon$ is a negligible value.

Theorem 1. Suppose that $\mathcal{A}$ is a Turing machine in probability
polynomial time attempting to break the protocol PSAA and obtain the session
key. $q_{h}$, $q_{s}$ and $q_{e}$ respectively represent the maximum number of
times $\mathcal{A}$ can query $h$, Send, Execute. Besides, $|D|$ is the size
of the user password set, $l_{1}$ is the length of the biometric key,
$|\chi_{\beta}|$ is the distribution range of Gaussian distribution
$\chi_{\beta}$, $|h|$ is the output range of the hash function $h$,
$Adv^{\mathcal{A}}_{RLWE}$ is the advantage that $\mathcal{A}$ can solve the
RLWE assumption in polynomial time. Then the advantage of $\mathcal{A}$ who
breaks the protocol PSAA and obtains the session key is defined as
$Adv^{\mathcal{A}}_{PSAA}$, and when
$Adv^{\mathcal{A}}_{PSAA}\leq\frac{q^{2}_{h}}{|h|}+\frac{(q_{s}+q_{e})^{2}}{|\chi_{\beta}|}+\frac{q_{s}}{2^{l_{1}-1}|D|}+2Adv^{\mathcal{A}}_{RLWE}$
holds, it can be considered that our proposed protocol PSAA is secure.

$Proof$: In order to evaluate the advantage of $\mathcal{A}$ in breaking the
semantic security of the key, we execute a series of games, namely $Game_{0}$,
$Game_{1}$, $Game_{2}$, $Game_{3}$ and $Game_{4}$. We define $Succ_{i}$ to
represent the event in which $\mathcal{A}$ wins $Game_{i}$, and $Pr(Succ_{i})$
to represent the probability of this event. The proof is similar to [14, 32]
and the details are as follows.

$Game_{0}$. In this game, an unbiased coin $C$ is randomly selected and
flipped. $\mathcal{A}$ implements the real attack on the protocol PSAA to
guess the true value of the coin, then we get the following formula:

$Adv^{\mathcal{A}}_{PSAA}=|2Pr[Succ_{0}]-1|$ (1)

$Game_{1}$. Compared with $Game_{0}$, $\mathcal{A}$ performs
Execute($\prod^{x}_{u_{i}}$, $\prod^{y}_{L_{j}}$, $\prod^{z}_{TCS}$) query to
obtain the authentication message transmitted between the three entities in
the non-secure channel. Through this query, $\mathcal{A}$ can only get
$\\{TID_{i},ID_{tcs},te^{1}_{i-tcs},sw^{1}_{i-tcs},a_{3},a_{4},t_{3}\\}$ and
$\\{a_{5},t_{4}\\}$. Since
$key=h(TID_{i},ID_{tcs},pk_{i},pk_{tcs},s\sigma^{1}_{i-tcs})$ where
$s\sigma^{1}_{i-tcs}=Mod_{2}(sk^{1}_{i-tcs},sw^{1}_{i-tcs})$, $\mathcal{A}$
cannot obtain $sk^{1}_{i-tcs}$ that can directly calculate
$s\sigma^{1}_{i-tcs}$ from the intercepted message. Therefore, compared with
$Game_{0}$, the advantage of breaking the protocol PSAA has not improved. Then
we can get the following formula:

$Pr[Succ_{1}]=Pr[Succ_{0}]$ (2)

$Game_{2}$. In $Game_{2}$, $\mathcal{A}$ uses Send and $h$ queries to forge or
modify authentication messages, and finally implements active attacks such as
forging or replaying messages. When the hash value of the message forged by
$\mathcal{A}$ is the same as the authentication message, the secret value can
be obtained through hash collision. According to the birthday paradox, the
maximum hash collision probability of $h$ is $\frac{q^{2}_{h}}{2|h|}$.
Furthermore, since $sk^{1}_{i-tcs}=(pk_{tcs}\cdot sk_{i}+2\cdot
te^{1}_{i-tcs})\cdot te^{1}_{i-tcs}+2\cdot re^{1}_{i-tcs}$ where
$te^{1}_{i-tcs}$ and $re^{1}_{i-tcs}$ are random sampling values in
$\chi_{\beta}$, the maximum probability of a collision with a random value is
$\frac{(q_{s}+q_{e})^{2}}{2|\chi_{\beta}|}$. Then we can get the following
formula:

$|Pr[Succ_{2}]-Pr[Succ_{1}]|\leq\frac{q^{2}_{h}}{2|h|}+\frac{(q_{s}+q_{e})^{2}}{2|\chi_{\beta}|}$
(3)

$Game_{3}$. Different from the previous game in that $\mathcal{A}$ can use
CorruptSmartDevice query to obtain the information
$\\{DID_{i},DP_{i},DPU_{i},DSK_{i},ver_{i},v_{i}\\}$ stored in the user’s
smart device and try to derive the user’s password $PW_{i}$ and the biometric
key $\sigma_{i}$ from the stored information. Once $\mathcal{A}$ has the
correct user password and biometric key, he/she can pass the check of
$ver_{i}$ and obtains the master private key $sk_{i}$. The probability of
$\mathcal{A}$ guessing the password and the biometric key is $\frac{1}{|D|}$
and $\frac{1}{2^{l1}}$, respectively. In addition, $\mathcal{A}$ can only
execute up to $q_{s}$ queries, and only when the password and the biometric
key are correct at the same time can pass the verification, then we can get
the following formula:

$|Pr[Succ_{3}]-Pr[Succ_{2}]|\leq\frac{q_{s}}{2^{l_{1}}|D|}$ (4)

$Game_{4}$. In this game, $\mathcal{A}$ attempts to obtain the session key
$key=h(TID_{i},ID_{tcs},pk_{i},pk_{tcs},s\sigma^{1}_{i-tcs})$ by intercepting
$\\{te^{1}_{i-tcs},sw^{1}_{i-tcs},pk_{i},pk_{tcs}\\}$ in the public channel,
where $s\sigma^{1}_{i-tcs}=Mod_{2}(sk^{1}_{i-tcs},sw^{1}_{i-tcs})$,
$sk^{1}_{i-tcs}=(pk_{tcs}\cdot sk_{i}+2\cdot te^{1}_{i-tcs})\cdot
te^{1}_{i-tcs}+2\cdot re^{1}_{i-tcs}$. $\mathcal{A}$ calculates $sk_{i}$,
$sk_{tcs}$ and $sk^{1}_{i-tcs}$ from the public parameters $pk_{i}$ and
$pk_{tcs}$, which can be reduced to solve the RLWE assumption. Then we can get
the following formula:

$|Pr[Succ_{4}]-Pr[Succ_{3}]|\leq Adv^{\mathcal{A}}_{RLWE}$ (5)

Finally, $\mathcal{A}$ has no other advantage to break the semantic security
of the session key without the above method, so we can get the following
formula:

$Pr[Succ_{4}]=\frac{1}{2}$ (6)

According to formula 1 and formula 6, we can get the following formula:

$\displaystyle Adv^{\mathcal{A}}_{PSAA}$
$\displaystyle=2|Pr[Succ_{0}]-\frac{1}{2}|$ (7)
$\displaystyle=2|Pr[Succ_{0}]-Pr[Succ_{4}]|$

Next, according to the triangle inequality and formulas 2, 3, 4, 5, we can get
the following formula:

$\displaystyle Adv^{\mathcal{A}}_{PSAA}$
$\displaystyle\leq\frac{q^{2}_{h}}{|h|}+\frac{(q_{s}+q_{e})^{2}}{|\chi_{\beta}|}+\frac{q_{s}}{2^{l_{1}-1}|D|}+2Adv^{\mathcal{A}}_{RLWE}$
(8)

###  6.2 Formal Security Verification Simulation Based on AVISPA

Figure 6: Role specification for user

AVISPA [33] is a simulation verification tool for large-scale Internet
security-sensitive protocols and has been widely used to construct defect-free
authentication protocols, such as: [14, 31, 34], etc. So far, AVISPA supports
a total of four security verification back-ends: On-the-fly Model-Checker
(OFMC), Constraint Logic based Attack Searcher (CL-AtSe), SAT-based Model-
Checker (SATMC) and Tree Automata based on Automatic Approximations for the
Analysis of Security Protocols (TA4SP). Most scholars usually use OFMC and CL-
AtSe back-ends to analyze the security of the network protocol. AVISPA outputs
the protocol verification result through the following steps. First, use the
language called High Level Protocol Specification Language (HLPSL) provided by
AVISPA to represent the specifications of all roles and clarify their
potential security attributes. Second, an automated translator called hlpsl2if
to convert role specifications represented by HLPSL to the intermediate format
(IF). For each back-end, IF is a lower-level and more acceptable format than
HLPSL. Finally, role specifications in IF format is input to a back-end and
output format (OF) is generated, where the result of OF can indicate whether
the protocol is safe or unsafe.

Figure 7: Role specification for satellite

Figure 8: Role specification for TCS

Figure 9: Role specification for session, environment and goal

Figures 6, 7 and 8 respectively show the role specifications of the user,
satellite node and TCS in HLPSL. In addition, the session, environment and
goal are defined as shown in Figure 9, where the adversary is represented by i
and can obtain all transmitted authentication messages based on Dolev-Yao
model. Finally, we verify the security of PSAA protocol based on OFMC and CL-
AtSe back-ends, the results are shown in Figures 10 and 11 respectively. The
simulation results of the two back-ends show that our proposed PSAA protocol
is safe and does not have any attack path to enable the adversary to implement
eavesdropping attacks, replay attacks and man-in-the-middle attacks.

Figure 10: Simulation result using OFMC backend

Figure 11: Simulation result using CL-AtSe backend

###  6.3 Informal Security Analysis

####  6.3.1 Mutual Authentication

In the second step of the authentication phase, after receiving the access
request
$\\{TID_{i},ID_{tcs},te^{1}_{i-tcs},sw^{1}_{i-tcs},a_{3},a_{4},t_{3}\\}$ from
$u_{i}$, $L_{j}$ calculates
$HPU^{{}^{\prime}}_{i}=h(h(TID_{i},HPU_{j}),t_{3})$ and checks whether
$a_{4}=h(TID_{i},ID_{tcs},te^{1}_{i-tcs},sw^{1}_{i-tcs},HPU^{{}^{\prime}}_{i},a_{3},t_{3})$
is holds. $HPU_{i}$ can only be calculated by a user who has registered with
the TCS, that is, $u_{i}$ is a legitimate user and the access request has not
been modified if the check is passed. Similarly, after receiving the access
response $\\{a_{5},t_{4}\\}$ from $L_{j}$, $u_{i}$ confirms the legitimacy of
$L_{j}$ by checking whether
$a_{5}=h(HP_{i},TID_{i},te^{1}_{i-tcs},sw^{1}_{i-tcs},t_{4})$ is established,
because only $L_{j}$ after mutual authentication with TCS in the pre-
negotiation phase can obtain the correct authentication parameters $HP_{i}$
through $a_{3}\oplus HPU_{i}$. Therefore, the proposed PSAA protocol can meet
the security requirements of mutual authentication.

####  6.3.2 Key Negotiation

In the third and fourth steps of the authentication phase, TCS and $u_{i}$
respectively calculate the session key
$key=h(TID_{i},ID_{tcs},pk_{i},pk_{tcs},s\sigma^{1}_{i-tcs})$, where
$s\sigma^{1}_{i-tcs}=Mod_{2}(sk^{1}_{i-tcs},sw^{1}_{i-tcs})$,
$sk^{1}_{i-tcs}=(pk_{tcs}\cdot sk_{i}+2\cdot te^{1}_{i-tcs})\cdot
te^{1}_{i-tcs}+2\cdot re^{1}_{i-tcs}$ or $(pk_{i}\cdot sk_{tcs}+2\cdot
te^{1}_{i-tcs})\cdot te^{1}_{i-tcs}+2\cdot re^{1^{\prime}}_{tcs}$. The session
key is not determined by $u_{i}$ or TCS alone, but by the joint negotiation of
the master public-private key pair of both parties. Moreover, the adversary
cannot extract the master private keys of both parties through the
eavesdropped $pk_{i}$, $pk_{tcs}$, $sw^{1}_{i-tcs}$ and other parameters in
the public channel unless the adversary can solve the RLWE assumption in
polynomial time. Therefore, the proposed PSAA protocol can meet the security
requirements of key negotiation.

####  6.3.3 Identity anonymous

During the entire authentication phase, $u_{i}$’s true identity $ID_{i}$ is
not transmitted in the public channel but the temporary identity $TID_{i}$,
where $TID_{i}=ID_{i}\oplus s\sigma^{0}_{i-tcs}$. If the adversary attempts to
obtain $ID_{i}$ through $TID_{i}\oplus s\sigma^{0}_{i-tcs}$, it can only
compute $s\sigma^{0}_{i-tcs}$ from $pk_{i}$ and $pk_{tcs}$ by solving the RLWE
assumption in polynomial time, which is difficult for the adversary.
Therefore, the adversary cannot obtain the true identity of the user and the
proposed PSAA protocol can meet the security requirements of identity
anonymous.

####  6.3.4 Perfect forward/backward secrecy

Each time when authenticating and negotiating a session key
$key=h(TID_{i},ID_{tcs},pk_{i},pk_{tcs},s\sigma^{1}_{i-tcs})$, $u_{i}$ needs
to randomly select $te^{1}_{i-tcs}$, $re^{1}_{i-tcs}$ from $\chi_{\beta}$ to
calculate $sk^{1}_{i-tcs}$, $sw^{1}_{i-tcs}$ and $s\sigma^{1}_{i-tcs}$. Due to
the randomness of $te^{1}_{i-tcs}$ and $re^{1}_{i-tcs}$, the session keys of
the previous and the next session are not associated with the current session
key, that is, even if the adversary obtains the current session key, it will
not compromise the security of the forward and backward session keys.
Therefore, the proposed PSAA protocol can meet the security requirements of
perfect forward/backward secrecy.

####  6.3.5 Eavesdropping attack

Similar as described in section 6.3.2, the adversary can only obtain the
parameters
$\\{TID_{i},pk_{i},ID_{tcs},pk_{tcs},te^{1}_{i-tcs},sw^{1}_{i-tcs},a_{3},a_{4},a_{5},t_{3},t_{4}\\}$
transmitted in the public channel after an eavesdropping attack. The adversary
cannot calculate the secret $s\sigma^{1}_{i-tcs}$ from the obtained $pk_{i}$,
$pk_{tcs}$ and other parameters, unless the RLWE assumption is resolved in
polynomial time. Therefore, the proposed PSAA protocol is resistant to
eavesdropping attack.

####  6.3.6 Replay attack

All interactive messages in the authentication phase include a timestamp and a
hash check value. If the adversary replays the eavesdropped original
interactive information, all legal entities can simply compare the current
timestamp with the timestamp of the message to determine whether it is
maliciously replayed. Even if the adversary tampered with the timestamp in the
replayed message, the adversary cannot modify the hash value due to the one-
way feature of the hash function, and finally the malicious replayed message
cannot be received by the legal entity. Therefore, the proposed PSAA protocol
is resistant to replay attack.

####  6.3.7 Impersonation attack

The adversary can impersonate a user or a satellite node to launch
impersonation attacks. When the adversary impersonates $u_{i}$ to send an
access request to $L_{j}$, the adversary needs to obtain the parameter
$pu_{i}$ that TCS distributes to the legitimate user $u_{i}$ during the
registration phase. However, the adversary cannot extract $pu_{i}$ from the
public parameters, so a legitimate access request cannot be constructed to
impersonate $u_{i}$. Similarly, when the adversary impersonates $L_{j}$, it is
impossible to construct a legitimate response $\\{a_{5},t_{4}\\}$ that passes
user verification without obtaining $HPU_{j}$, where
$a_{5}=h(HP^{{}^{\prime}}_{i},TID_{i},te^{1}_{i-tcs},sw^{1}_{i-tcs},t_{4})$
and $HP^{{}^{\prime}}_{i}=a_{3}\oplus h(h(TID_{i},HPU_{j}),t_{3})$. Therefore,
the proposed PSAA protocol is resistant to impersonation attack.

####  6.3.8 Man-in-the-middle attack

The adversary to implement the man-in-the-middle attack must be able to
respectively impersonate $u_{i}$ to communicate with the $L_{j}$ and
impersonate $L_{j}$ to communicate with $u_{i}$. However, in the proof of
impersonation attack, it has been proven that the adversary cannot impersonate
a legitimate user or satellite node. Therefore, the proposed PSAA protocol is
resistant to man-in-the-middle attack.

####  6.3.9 Device loss attack

When the user’s device is lost and acquired by the adversary, the adversary
cannot log in to the device and access SIN as a legitimate node because the
user’s true identity $ID_{i}$, password $PW_{i}$ and biometric $BIO_{i}$
cannot be obtained. Furthermore, even if the adversary obtains
$\\{DID_{i},DP_{i},DPU_{i},DSK_{i},ver_{i},v_{i}\\}$ stored in the device
through power analysis, it is impossible to calculate authentication
parameters such as the user’s master private key $sk_{i}$ without $ID_{i}$,
$PW_{i}$ and $BIO_{i}$. Therefore, the proposed PSAA protocol is resistant to
device loss attack.

####  6.3.10 Insider attack

The insider attack refers to a privileged insider in TCS attempting to obtain
the user’s password $PW_{i}$, biometric $BIO_{i}$, and the master private key
$sk_{i}$ during user registration. However, the registration request submitted
by $u_{i}$ does not directly contain $PW_{i}$, $BIO_{i}$ and $sk_{i}$, but
$RPW_{i}$ and $pk_{i}$, where $RPW_{i}=h(PW_{i},\sigma_{i})$, $pk_{i}=a\cdot
sk_{i}+2\cdot se_{i}$. Due to the one-way nature of the hash function and the
difficult assumption of RLWE, the adversary cannot get $PW_{i}$, $BIO_{i}$ and
$sk_{i}$ from $RPW_{i}$ and $pk_{i}$. Therefore, the proposed PSAA protocol is
resistant to insider attack.

####  6.3.11 Quantum attack

The session key negotiation mechanism of the PSAA protocol is designed based
on the RLWE assumption, in which RLWE has been proved to be an efficient and
secure post-quantum cryptography primitive and can be reduced to SVP in the
lattice. In addition, we refer to the randomization mechanism proposed in [21]
to add additional unpredictable random values to avoid public-private key pair
reuse attack. Therefore, the proposed PSAA protocol is resistant to quantum
attack.

##  7 Performance Comparison

In this section, we compare the proposed PSAA protocol with the other five
latest related protocols [14, 15, 16, 4, 7] in SIN in terms of security
attributes, authentication delay, and communication overhead. In order not to
lose generality, we use the NTL library [35, 19] and Openssl library to
simulate the cryptographic primitives of these protocols in C language without
multithreading and parallelism, then run on a computer with Intel(R) Core(TM)
i7-7820HQ CPU @ 2.90GHz processor and 8.00 GB RAM. At the same time, to ensure
the security strength of the protocol, we set parameters $n$, $q$, $\beta$ to
1024, 120833, 2.6, respectively, and the parameters selected make the security
strength of PSAA sufficient to cover the security strength of AES-192 and
AES-256 [19]. In addition, for other related protocols, set the elliptic curve
to secp256r1, the output length of the hash function $h$ is 256 bits, the
length of the temporary identity $TID_{i}$ and the timestamp is 100 bits, the
size of the point in the additive cyclic group is 512 bits, the symmetric
encryption/decryption algorithm is AES-256. Moreover, we ensure the accuracy
of the time cost of each cryptographic primitive by operating 10,000 times on
the relevant cryptographic primitives and taking the average value.

###  7.1 Comparison of Security Attributes

TABLE II: Comparison of security attributes

Security attributes |  [14] |  [15] |  [16] |  [4] |  [7] |  Our
---|---|---|---|---|---|---
Mutual authentication |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓
Key negotiation |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓
Identity anonymous |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓
PFS/FBS |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓
Eavesdropping attack |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓
Replay attack |  ✓ |  ✓ |  ✓ |  ✓ |  $\times$ |  ✓
Impersonation attack |  $\times$ |  $\times$ |  ✓ |  ✓ |  ✓ |  ✓
Man-in-the-middle attack |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓
Device loss attack |  ✓ |  $\times$ |  $\times$ |  $\times$ |  $\times$ |  ✓
Insider attack |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓
Quantum attack |  $\times$ |  $\times$ |  $\times$ |  $\times$ |  ✓ |  ✓

As shown in Table II, we evaluate and compare the security attributes of
related protocols and our proposed PSAA protocols for mutual authentication,
key negotiation, identity anonymity, perfect forward/backward secrecy
(PFS/FBS), and the ability to withstand eavesdropping, replay, impersonation,
man-in-the-middle, device loss, insider and quantum attacks. Among them, [14]
and [15] do not check the validity of the satellite node during the operation
of the entire protocol, which will be vulnerable to satellite impersonation
attacks. For protocols [16] and [4], due to the lack of a login verification
mechanism, an adversary can use the user’s lost legitimate device as a
legitimate node to access SIN. In addition, even though [15] has a simple
login mechanism, it only verifies the user password, which will also make the
protocol vulnerable to offline password guessing attacks. The security of all
four related protocols is based on the difficult problem of elliptic curve
cryptography, which has been proven to be breakable in polynomial time in the
post-quantum era, so these protocols are vulnerable to quantum attacks.
Besides, although the lattice-based protocol [7] can resist quantum attacks,
it lacks detailed mechanisms for historical authentication message replay
verification and user three-factor login verification, so it cannot resist
replay attacks and device loss attacks. Therefore, from the security analysis
and the security attribute comparison results in Table II, it is obvious that
our proposed PSAA protocol can meet all security attributes and its security
is better than other protocols.

###  7.2 Comparison of Authentication Delay

TABLE III: Execution time of various primitive operations

Notation |  Description |  Time (us)
---|---|---
$T_{h}$ |  Hash operation |  0.372
$T_{bp}$ |  Pairing operation |  624.168
$T_{ed}$ |  Encryption/decryption operation |  6.028
$T_{mul}$ |  ECC point multiplication operation |  10.67
$T_{add}$ |  ECC point addition operation |  0.711
$T_{samp}$ |  Sampling operation on $\chi_{\beta}$ |  25.763
$T_{rmul}$ |  Multiplication operation in $R_{q}$ |  202.786
$T_{radd}$ |  Addition operation in $R_{q}$ |  11.702
$T_{cha}$ |  $Cha$ operation |  17.002
$T_{lmul}$ |  Matrix-vector multiplication operation |  1025.011
$T_{ladd}$ |  Matrix addition operation |  1060.936

The authentication delay refers to the time interval from when a user
initiates an access request to when the session key is negotiated with TCS in
the authentication phase, which includes the computational overhead and
message transmission time. Figure III shows the each execution time of the
relevant cryptographic primitives involved in the protocols we obtained
through experiments, and the computational overhead of $Mod_{2}$ is small
enough to be neglected as [17]. Moreover, the transmission time $T_{u-s}$ of
the authentication message in the satellite-ground link is reasonably set to
10 ms [4]. It is worth mentioning that when analyzing the computational
overhead, we do not consider the calculation time required in the user login
verification phase.

TABLE IV: Comparison of authentication delay

Protocol |  Computational overhead |  Transmission time |  Total
---|---|---|---
[14] |  $6T_{mul}+9T_{h}$ |  $4T_{u-s}$ |  40.067 ms
[15] |  $6T_{mul}+10T_{h}+2T_{ed}$ |  $6T_{u-s}$ |  60.080 ms
[16] |  $\approx 14T_{mul}+2T_{bp}+3T_{h}$ |  $2T_{u-s}$ |  21.400 ms
[4] |  $9T_{mul}+6T_{h}+4T_{add}+2T_{ed}$ |  $2T_{u-s}$ |  20.113 ms
[7] |  $5T_{lmul}+3T_{ladd}+7T_{h}+2T_{ed}$ |  $2T_{u-s}$ |  28.322 ms
Our |  $3T_{samp}+T_{cha}+8T_{rmul}+4T_{radd}+11T_{h}+2T_{ed}$ |  $2T_{u-s}$ |  21.780 ms

For [14], the computational overhead for the entire authentication phase
includes six ECC point multiplication operations and nine hash operations,
which is equal to $6T_{mul}+9T_{h}=0.067$ ms, and the transmission time
required for authentication messages to be transmitted four times sequentially
in the satellite-ground link is $4T_{u-s}=40$ ms, so the total authentication
delay is 40.067 ms.

Similarly for the [15], the entire computational overhead includes six ECC
point multiplication operations, ten hash operations and two
encryption/decryption operations, which is equal to
$6T_{mul}+10T_{h}+2T_{ed}=0.080$ ms, and the transmission time required for
authentication messages is $6T_{u-s}=60$ ms, so the total authentication delay
is 60.080 ms.

For [16], the entire computational overhead approximately include fourteen ECC
point multiplication operations, two pairing operations and three hash
operations, which is equal to $14T_{mul}+2T_{bp}+3T_{h}=0.400$ ms, and the
transmission time is only $2T_{u-s}=20$ ms due to the parallel transmission of
messages in the authentication phase, so the total authentication delay is
20.400 ms.

For [4], the entire computational overhead includes nine ECC point
multiplication operations, six hash operations, four ECC point addition
operations and two encryption/decryption operations, which is equal to
$9T_{mul}+6T_{h}+4T_{add}+2T_{ed}=0.113$ ms, and the parallel transmission of
messages like [16] causes the authentication message transmission time to be
$2T_{u-s}=20$ ms, so the total authentication delay is 20.113 ms.

For [7], the entire computational overhead includes five matrix-vector
multiplication operations, three matrix addition operations, seven hash
operations and two encryption/decryption operations, which is equal to
$5T_{lmul}+3T_{ladd}+7T_{h}+2T_{ed}=8.322$ ms, and the transmission time is
$2T_{u-s}=20$ ms, so the total authentication delay of [7] is 28.322 ms.

For the PSAA protocol we proposed, the computational overhead of user,
satellite, and TCS are $2T_{samp}+T_{cha}+4T_{rmul}+2T_{radd}+5T_{h}$,
$4T_{h}+T_{ed}$, and $T_{samp}+4T_{rmul}+2T_{radd}+2T_{h}+T_{ed}$,
respectively, and the total computational overhead is
$3T_{samp}+T_{cha}+8T_{rmul}+4T_{radd}+11T_{h}+2T_{ed}=1.780$ ms. Moreover, in
the second step of the authentication phase, the satellite sends messages to
both the user and the TCS at the same time, resulting in the total
transmission time is $2T_{u-s}=20$ ms. Therefore, the authentication delay of
PSAA protocol is 21.780 ms.

From Table IV, our proposed PSAA protocol is far superior to [14] and [15] in
terms of authentication delay and reduces the delay of about 18.287 ms and
38.3 ms, respectively, which greatly improves the quality of service for users
in SIN. In addition, the PSAA protocol reduces the authentication delay of
6.542 ms compared with the same anti-quantum protocol [7], which is more
efficient. Besides, although the authentication delay of [16] and [4] is
slightly lower than that of the PSAA protocol we proposed, the PSAA protocol
in the post-quantum era provides higher security and anti-quantum properties,
which can also better serve users.

###  7.3 Comparison of Communication Overhead

TABLE V: Comparison of communication overhead Protocol |  User |  Satellite |  TCS |  Total
---|---|---|---|---
[14] |  968 bits |  1836 bits |  868 bits |  3672 bits
[15] |  1580 bits |  2648 bits |  968 bits |  5196 bits
[16] |  1168 bits |  3360 bits |  - |  4528 bits
[4] |  2392 bits |  2804 bits |  - |  5196 bits
[7] |  0.781 MB |  400.430 MB |  - |  401.211 MB
Our |  19244 bits |  19244 bits |  - |  38488 bits

The total size of authentication messages sent or forwarded by all entities in
the authentication phase is considered as the communication overhead.

For [14], the authentication messages transmitted by user, satellite and TCS
are $\\{TID_{i},E_{i},S_{i},T_{i}\\}$,
$\\{TID_{i},E_{i},S_{i},T_{i},ID_{leo},X_{tcs},S_{tcs}\\}$ and
$\\{TID_{i},X_{tcs},S_{tcs}\\}$ respectively, where $TID_{i}=ID_{i}\oplus
h(E_{i}||F_{i})$, $\\{E_{i},X_{tcs}\\}$ are the points of the elliptic curve,
$\\{S_{i},S_{tcs}\\}$ are hash values, $T_{i}$ is the timestamp, $ID_{leo}$ is
the identity. Therefore, the communication overhead of user, satellite, and
tcs are $100+512+256+100=968$ bits, $100+512+256+100+100+512+256=1836$ bits,
and $512+256+100=868$ bits, respectively, and the total communication overhead
of [14] is 3672 bits.

For [15], the authentication messages transmitted by user, satellite and TCS
are $\\{c,X,t_{1},Z\\}$, $\\{c,X,t_{1},ID_{leo},A_{tcs},Y,t_{2},Z,ID_{leo}\\}$
and $\\{A_{tcs},Y,t_{2},ID_{leo}\\}$ respectively, where $c$ is the
symmetrically encrypted ciphertext of
$\\{ID_{i},R_{i},H(ID_{i},R_{i}),t_{1}\\}$, $\\{X,Y\\}$ are the points of the
elliptic curve, $\\{t_{1},t_{2}\\}$ are timestamps, $\\{ID_{leo},ID_{i}\\}$
are identities, $\\{R_{i},A_{tcs},Z\\}$ are hash values. Therefore, the
communication overhead of user, satellite, and tcs are
$100+256+256+100+512+100+256=1580$ bits,
$100+256+256+100+512+100+100+256+512+100+256+100=2648$ bits,
$256+512+100+100=968$ bits, respectively, and the total communication overhead
of [15] is 5196 bits.

For [16], the authentication messages transmitted by user, satellite and TCS
are $\\{TID_{u},ID_{fleo},ID_{tcs},g^{r_{u}},ts_{3},\sigma_{u}\\}$,
$2\\{TID_{u},ID_{fleo},ID_{ftcs},g^{r_{u}},g^{r_{ftcs}},ts_{4},\sigma_{ftcs}\\}$,
$\varnothing$ respectively, where $\\{TID_{u},ID_{fleo},ID_{tcs}\\}$ are
identities, $\\{g^{r_{u}},g^{r_{ftcs}}\\}$ are points in the additive cyclic
group, $\\{\sigma_{u},\sigma_{ftcs}\\}$ are hash values, $\\{ts_{3},ts_{4}\\}$
are timestamps. Therefore, the communication overhead of user, satellite are
$100+100+100+512+100+256=1168$ bits,
$2\times\\{100+100+100+512+512+100+256\\}=3360$ bits, respectively, and the
total communication overhead of [16] is 4528 bits.

For [4], the authentication messages transmitted by user, satellite and TCS
are $\\{ID_{leo},R_{j},P_{j},v_{j},TS_{1}\\}$,
$\\{2TID_{j},P_{leo},R_{tcs},v_{leo},R_{leo},2TS_{2},R_{j}\\}$, $\varnothing$
respectively, where
$P_{j}=\\{pk_{j},TID_{j},Enc(pk_{ncc},TID_{j},ID_{j}),LT_{j}\\}$,
$P_{leo}=\\{pk_{leo},ID_{leo}\\}$, $\\{ID_{leo},TID_{j},ID_{j}\\}$ are
identities, $\\{R_{j},R_{leo},R_{tcs},pk_{j},pk_{ncc},pk_{leo}\\}$ are the
points of the elliptic curve, $\\{TS_{1},TS_{2}\\}$ are timestamps, the length
of $v_{j}$ and $v_{leo}$ is 256bits. Therefore, the communication overhead of
user, satellite are $100+512+512+100+512+100+100+100+256+100=2392$ bits,
$2\times 100+512+100+512+256+512+2\times 100+512=2804$ bits, respectively, and
the total communication overhead of [4] is 5196 bits.

For [7], the authentication messages transmitted by user, satellite and TCS
are $\\{C_{i},e_{i}\\}$, $\\{MAC_{s},U_{G},M_{S},Enc(C_{i},M_{i})\\}$,
$\varnothing$ respectively, where $MAC_{s}$ is hash value, $C_{i}\in
Z^{m+1}_{q1}$, $e_{i}\in Z^{m}_{q1}$, $U_{G}\in Z^{n\times(m+1)}_{q1}$,
$\\{M_{S},M_{i}\\}\in Z^{m+1}_{2}$, and $q1=n^{2}=$ 1048576,
$m=8n\log_{2}q1=163840$ [7], so the sizes of $C_{i}$, $e_{i}$, $U_{G}$,
$M_{S}$, $M_{i}$ are 3276820 bits, 3276800 bits, 400 MB, 163841 bits, 163841
bits respectively. Therefore, the communication overhead of user, satellite
are 0.781 MB, 400.430 MB, the total communication overhead of [7] is 401.211
MB.

According to [36], the size of the element in $\chi_{\beta}$ is
$n\cdot\lceil\log_{2}q\rceil$ bits, so the size of $te^{i}_{i-tcs}$
transmitted in the PSAA protocol is 17408 bits. In the authentication phase of
the PSSLA protocol, a total of three messages
$\\{TID_{i},ID_{tcs},te^{1}_{i-tcs},sw^{1}_{i-tcs},a_{3},a_{4},t_{3}\\}$,
$\\{a_{5},t_{4}\\}$, and
$\\{TID_{i},te^{1}_{i-tcs},sw^{1}_{i-tcs},HP_{i},t_{4}\\}$ are transmitted,
and their sizes are $100+100+17408+1024+256+256+100=19244$ bits, $256+100=356$
bits, and $100+17408+1024+256+100=18888$ bits, respectively. Therefore, the
total communication overhead of our proposed PSAA protocol is 38488 bits.

From the comparison of the communication overhead shown in Table V, it can be
concluded that the communication overhead of PSAA is greater than that of
protocols [14, 15, 16, 4]. This is because the elements in RLWE, such as
$te^{1}_{i-tcs}$, are much larger in size than the traditional cryptography
mechanism, the common drawback of the quantum-resistant lattice-based
cryptography mechanism [37, 21, 38, 39] result in the PSAA protocol has higher
communication overhead. In addition, compared with the quantum-resistant
protocol [7], the PSAA protocol significantly reduces the communication
overhead and makes SIN more available. Although the PSAA protocol has
disadvantages in communication overhead compared with non-anti-quantum
protocols, it has higher security and quantum resistance with little increase
in authentication delay, and with the development of satellite communication
technology, satellites already have higher communication capabilities, so we
believe that the proposed PSAA protocol is more suitable for SIN in the post-
quantum era.

##  8 Conclusion

In this paper, we first analyze the deficiencies and security defects of the
existing related protocols, and summarize the security requirements of a well-
designed protocol in SIN, and then propose a new PSAA protocol based on
randomized RLWE, which can not only meets the security requirements of mutual
authentication, key negotiation, identity anonymity and resist various known
attacks, but also has quantum resistance. In the PSAA protocol, the satellite
verifies the user’s legitimacy and allows the user to negotiate a session key
with TCS, which reduces the authentication delay and guarantees the quality of
service of the access user. For the proof of the security of the protocol, two
formal analysis methods, ROM model and AVISPA, and the informal analysis
method, demonstrate that the PSAA protocol meets all the security requirements
previously summarized. Moreover, performance analysis and comparison show that
the PSAA protocol is more suitable for SIN than other protocols under the
premise of ensuring security and quantum resistance.

## Acknowledgments

The authors would like to thank all the anonymous reviewers for their helpful
advice.

## References

  * [1] H. Yao, L. Wang, X. Wang, Z. Lu, and Y. Liu, “The space-terrestrial integrated network: An overview,” _IEEE Communications Magazine_ , vol. 56, no. 9, pp. 178–185, 2018.
  * [2] J. Guo and Y. Du, “Fog service in space information network: architecture, use case, security and challenges,” _IEEE Access_ , vol. 8, pp. 11 104–11 115, 2020.
  * [3] H.-C. Chao, D. E. Comer, and O. Kao, “Space and terrestrial integrated networks: Emerging research advances, prospects, and challenges,” _IEEE Network_ , vol. 33, no. 1, pp. 6–7, 2019.
  * [4] K. Xue, W. Meng, S. Li, D. S. Wei, H. Zhou, and N. Yu, “A secure and efficient access and handover authentication protocol for internet of things in space information networks,” _IEEE Internet of Things Journal_ , vol. 6, no. 3, pp. 5485–5499, 2019.
  * [5] C. Jiang, X. Wang, J. Wang, H.-H. Chen, and Y. Ren, “Security in space information networks,” _IEEE communications magazine_ , vol. 53, no. 8, pp. 82–88, 2015.
  * [6] P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in _Proceedings 35th annual symposium on foundations of computer science_. Ieee, 1994, pp. 124–134.
  * [7] R. Ma, J. Cao, D. Feng, and H. Li, “Laa: Lattice-based access authentication scheme for iot in space information networks,” _IEEE Internet of Things Journal_ , vol. 7, no. 4, pp. 2791–2805, 2019.
  * [8] H. Cruickshank, “A security system for satellite networks,” in _Fifth International Conference on Satellite Systems for Mobile Communications and Navigation, 1996._ IET, 1996, pp. 187–190.
  * [9] M.-S. Hwang, C.-C. Yang, and C.-Y. Shiu, “An authentication scheme for mobile satellite communication systems,” _ACM SIGOPS Operating Systems Review_ , vol. 37, no. 4, pp. 42–47, 2003.
  * [10] Y.-F. Chang and C.-C. Chang, “An efficient authentication protocol for mobile satellite communication systems,” _ACM SIGOPS Operating Systems Review_ , vol. 39, no. 1, pp. 70–84, 2005.
  * [11] T.-H. Chen, W.-B. Lee, and H.-B. Chen, “A self-verification authentication mechanism for mobile satellite communication systems,” _Computers & Electrical Engineering_, vol. 35, no. 1, pp. 41–48, 2009.
  * [12] G. Zheng, H.-T. Ma, C. Cheng, and Y.-C. Tu, “Design and logical analysis on the access authentication scheme for satellite mobile communication networks,” _IET Information Security_ , vol. 6, no. 1, pp. 6–13, 2012.
  * [13] W. Zhao, A. Zhang, J. Li, X. Wu, and Y. Liu, “Analysis and design of an authentication protocol for space information network,” in _MILCOM 2016-2016 IEEE Military Communications Conference_. IEEE, 2016, pp. 43–48.
  * [14] A. Ostad-Sharif, D. Abbasinezhad-Mood, and M. Nikooghadam, “Efficient utilization of elliptic curve cryptography in design of a three-factor authentication protocol for satellite communications,” _Computer Communications_ , vol. 147, pp. 85–97, 2019.
  * [15] M. Qi, J. Chen, and Y. Chen, “A secure authentication with key agreement scheme using ecc for satellite communication systems,” _International Journal of Satellite Communications and Networking_ , vol. 37, no. 3, pp. 234–244, 2019.
  * [16] Q. Yang, K. Xue, J. Xu, J. Wang, F. Li, and N. Yu, “Anfra: Anonymous and fast roaming authentication for space information network,” _IEEE Transactions on Information Forensics and Security_ , vol. 14, no. 2, pp. 486–497, 2018.
  * [17] Q. Feng, D. He, S. Zeadally, N. Kumar, and K. Liang, “Ideal lattice-based anonymous authentication protocol for mobile devices,” _IEEE Systems Journal_ , vol. 13, no. 3, pp. 2775–2785, 2018.
  * [18] J. Ding, X. Xie, and X. Lin, “A simple provably secure key exchange scheme based on the learning with errors problem.” _IACR Cryptol. ePrint Arch._ , vol. 2012, p. 688, 2012.
  * [19] J. Ding, T. Takagi, X. Gao, and Y. Wang, “Ding key exchange,” Technical report, National Institute of Standards and Technology, 2017 …, Tech. Rep., 2017\.
  * [20] J. Ding, S. Alsayigh, R. Saraswathy, S. Fluhrer, and X. Lin, “Leakage of signal function with reused keys in rlwe key exchange,” in _2017 IEEE International Conference on Communications (ICC)_. IEEE, 2017, pp. 1–6.
  * [21] X. Gao, J. Ding, L. Li, and J. Liu, “Practical randomized rlwe-based key exchange against signal leakage attack,” _IEEE Transactions on Computers_ , vol. 67, no. 11, pp. 1584–1593, 2018.
  * [22] J. Guo and Y. Du, “A secure three-factor anonymous roaming authentication protocol using ecc for space information networks,” _Peer-to-Peer Networking and Applications_ , vol. 14, no. 2, pp. 898–916, 2021.
  * [23] Y. Dodis, L. Reyzin, and A. Smith, “Fuzzy extractors: How to generate strong keys from biometrics and other noisy data,” in _International conference on the theory and applications of cryptographic techniques_. Springer, 2004, pp. 523–540.
  * [24] D. Dolev and A. Yao, “On the security of public key protocols,” _IEEE Transactions on information theory_ , vol. 29, no. 2, pp. 198–208, 1983.
  * [25] R. Canetti and H. Krawczyk, “Analysis of key-exchange protocols and their use for building secure channels,” in _International conference on the theory and applications of cryptographic techniques_. Springer, 2001, pp. 453–474.
  * [26] T. S. Messerges, E. A. Dabbish, and R. H. Sloan, “Examining smart-card security under the threat of power analysis attacks,” _IEEE transactions on computers_ , vol. 51, no. 5, pp. 541–552, 2002.
  * [27] M. Bellare and P. Rogaway, “Random oracles are practical: A paradigm for designing efficient protocols,” in _Proceedings of the 1st ACM Conference on Computer and Communications Security_ , 1993, pp. 62–73.
  * [28] S. Chatterjee, S. Roy, A. K. Das, S. Chattopadhyay, N. Kumar, and A. V. Vasilakos, “Secure biometric-based authentication scheme using chebyshev chaotic map for multi-server environment,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 15, no. 5, pp. 824–839, 2016.
  * [29] A. Armando, D. Basin, Y. Boichut, Y. Chevalier, L. Compagna, J. Cuéllar, P. H. Drielsma, P.-C. Héam, O. Kouchnarenko, J. Mantovani _et al._ , “The avispa tool for the automated validation of internet security protocols and applications,” in _International conference on computer aided verification_. Springer, 2005, pp. 281–285.
  * [30] J. Srinivas, A. K. Das, M. Wazid, and N. Kumar, “Anonymous lightweight chaotic map-based authenticated key agreement protocol for industrial internet of things,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 17, no. 6, pp. 1133–1146, 2018.
  * [31] S. Challa, A. K. Das, V. Odelu, N. Kumar, S. Kumari, M. K. Khan, and A. V. Vasilakos, “An efficient ecc-based provably secure three-factor user authentication and key agreement protocol for wireless healthcare sensor networks,” _Computers & Electrical Engineering_, vol. 69, pp. 534–554, 2018.
  * [32] V. Dabra, A. Bala, and S. Kumari, “Lba-pake: Lattice-based anonymous password authenticated key exchange for mobile devices,” _IEEE Systems Journal_ , 2020\.
  * [33] L. Vigano, “Automated security protocol analysis with the avispa tool,” _Electronic Notes in Theoretical Computer Science_ , vol. 155, pp. 61–86, 2006.
  * [34] A. K. Das, A. K. Sutrala, S. Kumari, V. Odelu, M. Wazid, and X. Li, “An efficient multi-gateway-based three-factor user authentication and key agreement scheme in hierarchical wireless sensor networks,” _Security and Communication Networks_ , vol. 9, no. 13, pp. 2070–2092, 2016.
  * [35] V. Shoup _et al._ , “Ntl: A library for doing number theory,” 2001.
  * [36] X. Gao, J. Ding, J. Liu, and L. Li, “Post-quantum secure remote password protocol from rlwe problem,” in _International Conference on Information Security and Cryptology_. Springer, 2017, pp. 99–116.
  * [37] D. S. Gupta, S. H. Islam, M. S. Obaidat, A. Karati, and B. Sadoun, “Laac: Lightweight lattice-based authentication and access control protocol for e-health systems in iot environments,” _IEEE Systems Journal_ , 2020.
  * [38] X. Gao, “Comparison analysis of ding’s rlwe-based key exchange protocol and newhope variants,” _Advances in Mathematics of Communications_ , vol. 13, no. 2, p. 221, 2019.
  * [39] E. Alkim, L. Ducas, T. Pöppelmann, and P. Schwabe, “Newhope without reconciliation.” _IACR Cryptol. ePrint Arch._ , vol. 2016, p. 1157, 2016\.