# An Efficient Chaotic Map-Based Authentication Scheme with Mutual Anonymity

Authors: Yousheng Zhou; Junfeng Zhou; Feng Wang; Feng Guo
Journal: Applied Computational Intelligence and Soft Computing
 (2016)

---

## Abstract

A chaotic map-based mutual authentication scheme with strong anonymity is proposed in this paper, in which the real identity of the user is encrypted with a shared key between the user and the trusted server. Only the trusted server can determine the real identity of a user during the authentication, and any other entities including other users of the system get nothing about the user’s real identity. In addition, the shared key of encryption can be easily computed by the user and trusted server using the Chebyshev map without additional burdensome key management. Once the partnered two users are authenticated by the trusted server, they can easily proceed with the agreement of the session key. Formal security analysis demonstrates that the proposed scheme is secure under the random oracle model.


---

## Body

## 1. Introduction

Due to its characteristic of sensibility of initial conditions and the chaotic parameter, a chaos system shows aperiodicity and pseudorandomness, and it has been widely used in many cryptographic constructions, such as chaotic system based hash functions [1–3], chaotic system based encryption [4–8], and chaotic based block cipher [9], and so forth.Authentication and key agreement are the fundamental blocks used to achieve authenticity and confidentiality in cryptographic system. Much efforts on chaotic maps based authentication and key establishment have been made in recent years. In 2009, Han and Chang [10] proposed a chaotic map-based key agreement protocol, which removes the constraint of synchronization. However, Yoon and Yoo [11] pointed out that Han and Chang’s [10] scheme cannot counter replay attack. Later, Tseng et al. [12] presented a chaotic map-based key agreement protocol for smart card-oriented application, which is vulnerable to internal attack and lacks perfect forward security as pointed out by Niu and Wang [13]. Though Niu and Wang [13] improved Tseng et al.’s [12] scheme and proposed a new one, it is expensive and cannot resist DoS attack. In addition, other researchers investigated the improvement for key agreement of smart card [14, 15]. Wang and Zhao [16] first proposed trusted third party (TTP) based key agreement scheme using the Chebyshev chaotic maps, which is improved by Yoon and Jeon [17] for its vulnerability to tampering attack. In 2012, Lai et al. [18] developed a novel TTP based key agreement protocol using the extended Chebyshev map, but their scheme cannot counter internal attack and off-line key guessing attack [19]. Later, Lee et al. [20] presented a mutual anonymous authentication scheme with the extended Chebyshev map, but it can incur the man-in-the-middle attack. Tan [21] proposed a novel authentication and key agreement protocol with smart card, which can achieve user anonymity; however, the cost consumption is expensive. To cut the heavy computation cost due to the smart card, Gong et al. [22] proposed an improved chaotic map-based key management scheme without a smart card. However, Wang and Luan [23] pointed out that Gong et al.’s scheme exists key management issues and potential security problems and then proposed a new secure key agreement protocol. In addition, some chaotic maps based schemes [24–28] have been investigated for solving various security problems.Although a lot of works on chaotic maps based authentication have been made, most of them cannot provide mutual authentication and are vulnerable to external attack. Only few schemes address this issue using encryption; however, the confidentiality of these schemes is not perfect, since internal users of the system can know the real identities of others during the execution of the authentication process. As the popularity of wireless communication enabled devices, the private information of users, such as identity and locations, can be easily illegally intercepted and then exploited to trace individuals by potential attackers [29]. The privacy of the user has attracted increasing attention from both industry and academia nowadays. To the best of our knowledge, a scheme can that addresses this privacy requirement does not exist. Motived by this, a mutual chaotic map-based authentication scheme with mutual anonymity is proposed in this paper, which has the following properties.(
1) Mutual Strong Anonymity. When user, Alice, in the system interacts with another user, Bob, to fulfill the authentication process, no entity except the trusted server can learn some information about the real identity of Alice and Bob. Furthermore, Alice and Bob cannot determine the opposite side as well; that is, Alice does not know Bob’s real identity and vice versa.(
2) Untraceability. Any internal user cannot connect any two authentication sessions; that is, to say, even if a system user Alice has established a session with the same user Bob who was once authenticated, Alice still cannot determine that the opposite side is Bob using the historic session. In addition, any external entities cannot determine whether users in one session are the similar to users in another session using the intercepted messages.The rest of the paper is organized as follows; some related basics and definitions are introduced in Section2. The concrete construction of the proposed scheme is illustrated in Section 3. Analysis and comparison are presented in Section 4. At last, the paper is concluded.


## 2. Preliminaries

This section introduces the common user requirements, the security requirements for mutual authentication, some basics about the Chebyshev chaotic map and its advantage, and the security definitions.


### 2.1. Requirements

#### 2.1.1. User Requirements

Given that the authentication scheme to be constructed should be easy to use, the following user requirements need to be satisfied.(
1) Independency. The system should enable users to choose their seeds to produce the shared encryption/decryption keys independently, which means the user can encrypt the transferred messages with a distinctive key in a new authentication session without additional agreement with the trusted server in advance.(
2) Round-Optimization. When a user wants to authenticate another entity, the number of the interactive rounds should be minimized as much as possible, which is helpful to save computation and communication cost, meanwhile users’ experiences will be enhanced as well.(
3) Anonymity. From the user perspective, his real identity needs protection and it should not be exposed to other entities except the trusted server.


#### 2.1.2. Security Requirements

Since the objective of our proposed protocol is to provide a reliable and robust authentication mechanism to counter all possible outside and inside attacks, based on previous studies [21–25, 32, 33], we give the following critical requirements to provide secure authentication.(
1) Mutual Authentication. After the involved partnered two users finish the process of authentication, they should be convinced that the opposite user is an authentic one, not a forged one.(
2) Efficiency. Since the process of mutual authentication is on-line and the trusted server is required to support all authentication processes, the communication and computation costs should be as low as possible.(
3) Integrity. This means the involved entities can verify the integrity of received messages, which aims to detect possible damage to those messages.(
4) Confidentiality. After the authentication process, a session key should be produced for both partnered users to provide a secure communication, and it ensures forward secrecy as well.Next, a brief introduction of the Chebyshev map and some related preliminaries [25, 31, 33] are given.


### 2.2. The Chebyshev Chaotic Maps

#### 2.2.1. Definitions of Chebyshev Chaotic Maps

Definition 1.
Letn be an integer, x
∈
[
-
1,1
], and an n-order Chebyshev polynomial map T
n
(
x
)
:
[
-
1,1
]
→
[
-
1,1
] is defined as follows:(1)
T
n
x
=
cos
⁡
n
∗
arccos
⁡
x
.According to the definition, the Chebyshev polynomial map can also be defined recursively as follows:(2)
T
n
x
=
2
∗
x
∗
T
n
-
1
x
-
T
n
-
2
x
,where T
0
(
x
)
=
1 and T
2
(
x
)
=
x, n
≥
2.The Chebyshev polynomial map has the following two properties.(1) Semigroup property is as follows:(3)
T
r
T
s
x
=
cos
⁡
r
∗
cos
-
1
⁡
s
∗
cos
-
1
⁡
x
=
cos
⁡
r
∗
s
∗
cos
-
1
⁡
x
=
T
s
r
x
=
T
s
T
r
x
,where r, s are two integers, x
∈
[
-
1,1
].(2) Chaos property is as follows. Whenn is bigger than 1, an n-degree Chebyshev polynomial map T
n
(
x
)
:
[
-
1,1
]
→
[
-
1,1
] has the constant measure f
∗
(
x
)
=
1
/
(
π
1
-
x
2
) and positive Lyapunov exponent λ
=
ln
⁡
n
>
0.According to the periodicity ofy
=
cos
⁡
x, there exist multiple x associated with the same y to make the equation hold. To improve the security of classic Chebyshev polynomial map, Zhang [33] gave a proof that the Chebyshev polynomial map still keeps the semigroup property over the interval (
-
∞
,
∞
), which is calledthe extended Chebyshev chaotic maps with the following definition:(4)
T
n
x
=
2
x
T
n
-
1
x
-
T
n
-
2
x
mod
⁡
P
,where n
≥
2, x
∈
[
-
1,1
], and P is a big prime number. It can be easily found the following equation holds as well:(5)
T
r
T
s
x
=
T
s
r
x
=
T
s
T
r
x
mod
⁡
P
.Definition 2 (discrete logarithm problem (DLP)).
Given any two big integersx, y, find an integer s to make the equation T
s
(
x
)
≡
y hold.Definition 3 (decisional Diffie-Hellman problem (DDH)).
GivenT
r
(
x
), T
s
(
x
), and T
u
(
x
), where r, s, and u are unknown, determine whether equation T
s
r
(
x
)
=
T
u
(
x
)
mod
⁡
P holds or not.


#### 2.2.2. The Advantages of Using Chebyshev Chaotic Maps

As a chaotic system characterizes excellent properties of diffusion and confusion, it is widely used to design various cryptographic schemes. Our design aims to provide a secure efficient mutual authentication with strong anonymity, and this means encryption will be integrated to keep the confidentiality of the identities. However, the traditional public key cryptography schemes are not desirable to achieve it since the management of encryption key in these schemes produces heavy computational burden. Inspired by the excellent semigroup property, the extended Chebyshev chaotic map over the finite field is used to develop our protocol since the discrete logarithm problem and Diffie-Hellman problem are assumed to be intractable within polynomial time [21]. However, there are no hardness assumptions of the discrete logarithm problems or the Diffie-Hellman problems about the Chebyshev chaotic maps over the interval [
-
1,1
] [34], so that it is still challenging to design a secure chaotic map-based key agreement protocol over the interval [
-
1,1
]. Meanwhile, with the Chebyshev chaotic map, our proposed based scheme enables the users and trusted server efficiently to generate the shared encryption key and agree session key without additional key management. Though there are some other types of chaos systems, only the extended Chebyshev chaotic map has the semigroup property and satisfies the requirements stated above. In addition, the Chebyshev map has good chaotic properties with mixture and ergodicity, and the chaotic sequences generated by the Chebyshev map have good statistical distribution characteristics as the mean is 0 [35]. Wang et al. [7, 8] pointed out that low dimension chaotic maps have degradation of dynamics in finite precision computations in computers; however, this issue can be addressed using appropriate implementation; for example, Liu et al. [36] proposed an analogue-digital mixed method to solve the dynamical degradation of digital chaotic system. Given the previous advantages, the extended Chebyshev chaotic map is used to construct mutual authentication with strong anonymity in this paper.


### 2.3. Security Definitions

Based on the attack model in literatures [37, 38], the security model of the proposed chaotic map based mutual authentication and key agreement with strong anonymity (
CMASA
) is defined in this section. In the model, the capability of the adversary A is defined by the following interactive game which consists of oracle queries and security assumptions.A can join the game through issuing series of oracle queries to any participant from the entity set ∏
U
i including the trusted server. During the interactive activities, A is assigned with some attacking capabilities to the authentication protocol. The communication channel is under the full control of A, which means A can intercept, block, inject, delete, and modify any message transferred via this channel. The queries that A can issue are as follows.E
x
c
u
t
e
(
∏
U
i
). This query is designed to assign A with passive attacking capability. After the execution of this query, all the transferred messages produced by the honest parities will be output according to the definition of P.S
e
n
d
(
∏
U
i
,
M
). This query is designed to simulate the situation that A has controlled the whole communication process. A can issue S
e
n
d query on M to ∏
U
i, and the corresponding entity from ∏
U
i will compute the results according to P and respond to A.R
e
v
e
a
l
(
∏
U
i
). This query is used to simulate the known key attacking. If it is a valid session, all the computed shared session keys by ∏
U
i will be responded to and null will be responded to otherwise.C
o
r
r
u
p
t
(
∏
U
i
). This query is used to simulate that A corrupts entities from ∏
U
i. A can obtain the permanent password and real identification of ∏
U
i with this query.S
y
m
E
n
c
(
{
E
,
D
}
,
k
,
{
M
,
C
}
). This query is designed to assign A with the capability of accessing the encryption oracle. In order to respond to A correctly, a list L
e is needed to setup and maintenance. Upon receiving the query S
y
m
E
n
c
(
E
,
k
,
M
), first check if there exists some entry {
K
,
M
,
C
} in L
e. If yes, return C of the corresponding entry; otherwise, a random value C
′ will be returned. Meanwhile, a new tuple {
K
,
M
,
C
′
} will be added into L
e. Equivalently, for the decryption query S
y
m
E
n
c
(
D
,
k
,
C
), first check if there exists some entry {
K
,
M
,
C
} in L
e, if yes, return M of the corresponding entry, and a random value M
′ will be returned, otherwise. Meanwhile, the new tuple {
K
,
M
′
,
C
} will be added to L
e.H
a
s
h
(
M
). This query is utilized to simulate hashing for A. To respond to A effectively, a list L
h will be set up. Upon receiving the query on m from A, firstly check if there already exists some entry {
m
,
h
} in L
h. If yes, return the value h of the existing entry to A. Otherwise, generate a random value h
′ as the response and add {
m
,
h
′
} to L
h at the same time.T
e
s
t
(
∏
U
i
). This query is used to measure the semantic security of the session key K
S. If the entity of this session key U has already computed K
S with his partnered peer, return K
S to A. Otherwise, null will be responded to. A can also issue a single T
e
s
t query to ∏
U
i, and ∏
U
i will make an unbiased toss b
∈
(
0,1
) to demine the response. If b
=
1, return K
S to A. Otherwise, return a random value.Definition 4 (security of the session key (ASK-Secure)).
In an adversary involved interactive game, the adversaryA can arbitrarily issue Test query, where the response is the real session key or a random value. If A issued a Test query to an unauthorized entity, A would be responded with ⊥. If A issued a Test query to a dishonest entity or the entity whose peer is dishonest, the corresponding real session key will be responded to. Otherwise, a random c from an unbiased coin toss is used to determine that the response is the real session key or a random value. A would guess the uncovered c through analyzing the response. Let the event E
=
{
A
wins  this  game
}, and let Adv
P
ASK
(
A
) be the advantage that A wins the distinguishability of P. If Adv
P
ASK
(
A
) is negligible, then P is called ASK-Secure [37].Definition 5 (security of symmetric encryption (OT-Secure)).
One-time security of symmetric encryption (OT-Secure) [39] means that the indistinguishability of symmetric encryption under the passive attack can also be called find-guess security. Let π
=
(
E
,
D
) be a symmetric encryption scheme and let A
=
(
A
1
,
A
2
) be an adversary of π, and then consider the following interactive game between π and A.(1)
Choosea
←
KSP.
(2)
Input1
k to run A
1. A
1 outputs two distinctive messages m
0
,
m
2
∈
MSP and the state s.
(3)
Chooseb
←
R
(
0,1
) randomly and compute c
←
E
a
(
m
b
).
(4)
Inputc
,
s and run A
2, and then A
2 outputs b
′
∈
[
0,1
].The advantage ofA represents how far it will guess the right b with the possibility bigger than 1
/
2; that is 2
P
r
[
b
=
b
′
]
-
1. During the whole process of the game, A is passive; in other words, it cannot access any encryption or decryption oracle.


## 2.1. Requirements

### 2.1.1. User Requirements

Given that the authentication scheme to be constructed should be easy to use, the following user requirements need to be satisfied.(
1) Independency. The system should enable users to choose their seeds to produce the shared encryption/decryption keys independently, which means the user can encrypt the transferred messages with a distinctive key in a new authentication session without additional agreement with the trusted server in advance.(
2) Round-Optimization. When a user wants to authenticate another entity, the number of the interactive rounds should be minimized as much as possible, which is helpful to save computation and communication cost, meanwhile users’ experiences will be enhanced as well.(
3) Anonymity. From the user perspective, his real identity needs protection and it should not be exposed to other entities except the trusted server.


### 2.1.2. Security Requirements

Since the objective of our proposed protocol is to provide a reliable and robust authentication mechanism to counter all possible outside and inside attacks, based on previous studies [21–25, 32, 33], we give the following critical requirements to provide secure authentication.(
1) Mutual Authentication. After the involved partnered two users finish the process of authentication, they should be convinced that the opposite user is an authentic one, not a forged one.(
2) Efficiency. Since the process of mutual authentication is on-line and the trusted server is required to support all authentication processes, the communication and computation costs should be as low as possible.(
3) Integrity. This means the involved entities can verify the integrity of received messages, which aims to detect possible damage to those messages.(
4) Confidentiality. After the authentication process, a session key should be produced for both partnered users to provide a secure communication, and it ensures forward secrecy as well.Next, a brief introduction of the Chebyshev map and some related preliminaries [25, 31, 33] are given.


## 2.1.1. User Requirements

Given that the authentication scheme to be constructed should be easy to use, the following user requirements need to be satisfied.(
1) Independency. The system should enable users to choose their seeds to produce the shared encryption/decryption keys independently, which means the user can encrypt the transferred messages with a distinctive key in a new authentication session without additional agreement with the trusted server in advance.(
2) Round-Optimization. When a user wants to authenticate another entity, the number of the interactive rounds should be minimized as much as possible, which is helpful to save computation and communication cost, meanwhile users’ experiences will be enhanced as well.(
3) Anonymity. From the user perspective, his real identity needs protection and it should not be exposed to other entities except the trusted server.


## 2.1.2. Security Requirements

Since the objective of our proposed protocol is to provide a reliable and robust authentication mechanism to counter all possible outside and inside attacks, based on previous studies [21–25, 32, 33], we give the following critical requirements to provide secure authentication.(
1) Mutual Authentication. After the involved partnered two users finish the process of authentication, they should be convinced that the opposite user is an authentic one, not a forged one.(
2) Efficiency. Since the process of mutual authentication is on-line and the trusted server is required to support all authentication processes, the communication and computation costs should be as low as possible.(
3) Integrity. This means the involved entities can verify the integrity of received messages, which aims to detect possible damage to those messages.(
4) Confidentiality. After the authentication process, a session key should be produced for both partnered users to provide a secure communication, and it ensures forward secrecy as well.Next, a brief introduction of the Chebyshev map and some related preliminaries [25, 31, 33] are given.


## 2.2. The Chebyshev Chaotic Maps

### 2.2.1. Definitions of Chebyshev Chaotic Maps

Definition 1.
Letn be an integer, x
∈
[
-
1,1
], and an n-order Chebyshev polynomial map T
n
(
x
)
:
[
-
1,1
]
→
[
-
1,1
] is defined as follows:(1)
T
n
x
=
cos
⁡
n
∗
arccos
⁡
x
.According to the definition, the Chebyshev polynomial map can also be defined recursively as follows:(2)
T
n
x
=
2
∗
x
∗
T
n
-
1
x
-
T
n
-
2
x
,where T
0
(
x
)
=
1 and T
2
(
x
)
=
x, n
≥
2.The Chebyshev polynomial map has the following two properties.(1) Semigroup property is as follows:(3)
T
r
T
s
x
=
cos
⁡
r
∗
cos
-
1
⁡
s
∗
cos
-
1
⁡
x
=
cos
⁡
r
∗
s
∗
cos
-
1
⁡
x
=
T
s
r
x
=
T
s
T
r
x
,where r, s are two integers, x
∈
[
-
1,1
].(2) Chaos property is as follows. Whenn is bigger than 1, an n-degree Chebyshev polynomial map T
n
(
x
)
:
[
-
1,1
]
→
[
-
1,1
] has the constant measure f
∗
(
x
)
=
1
/
(
π
1
-
x
2
) and positive Lyapunov exponent λ
=
ln
⁡
n
>
0.According to the periodicity ofy
=
cos
⁡
x, there exist multiple x associated with the same y to make the equation hold. To improve the security of classic Chebyshev polynomial map, Zhang [33] gave a proof that the Chebyshev polynomial map still keeps the semigroup property over the interval (
-
∞
,
∞
), which is calledthe extended Chebyshev chaotic maps with the following definition:(4)
T
n
x
=
2
x
T
n
-
1
x
-
T
n
-
2
x
mod
⁡
P
,where n
≥
2, x
∈
[
-
1,1
], and P is a big prime number. It can be easily found the following equation holds as well:(5)
T
r
T
s
x
=
T
s
r
x
=
T
s
T
r
x
mod
⁡
P
.Definition 2 (discrete logarithm problem (DLP)).
Given any two big integersx, y, find an integer s to make the equation T
s
(
x
)
≡
y hold.Definition 3 (decisional Diffie-Hellman problem (DDH)).
GivenT
r
(
x
), T
s
(
x
), and T
u
(
x
), where r, s, and u are unknown, determine whether equation T
s
r
(
x
)
=
T
u
(
x
)
mod
⁡
P holds or not.


### 2.2.2. The Advantages of Using Chebyshev Chaotic Maps

As a chaotic system characterizes excellent properties of diffusion and confusion, it is widely used to design various cryptographic schemes. Our design aims to provide a secure efficient mutual authentication with strong anonymity, and this means encryption will be integrated to keep the confidentiality of the identities. However, the traditional public key cryptography schemes are not desirable to achieve it since the management of encryption key in these schemes produces heavy computational burden. Inspired by the excellent semigroup property, the extended Chebyshev chaotic map over the finite field is used to develop our protocol since the discrete logarithm problem and Diffie-Hellman problem are assumed to be intractable within polynomial time [21]. However, there are no hardness assumptions of the discrete logarithm problems or the Diffie-Hellman problems about the Chebyshev chaotic maps over the interval [
-
1,1
] [34], so that it is still challenging to design a secure chaotic map-based key agreement protocol over the interval [
-
1,1
]. Meanwhile, with the Chebyshev chaotic map, our proposed based scheme enables the users and trusted server efficiently to generate the shared encryption key and agree session key without additional key management. Though there are some other types of chaos systems, only the extended Chebyshev chaotic map has the semigroup property and satisfies the requirements stated above. In addition, the Chebyshev map has good chaotic properties with mixture and ergodicity, and the chaotic sequences generated by the Chebyshev map have good statistical distribution characteristics as the mean is 0 [35]. Wang et al. [7, 8] pointed out that low dimension chaotic maps have degradation of dynamics in finite precision computations in computers; however, this issue can be addressed using appropriate implementation; for example, Liu et al. [36] proposed an analogue-digital mixed method to solve the dynamical degradation of digital chaotic system. Given the previous advantages, the extended Chebyshev chaotic map is used to construct mutual authentication with strong anonymity in this paper.


## 2.2.1. Definitions of Chebyshev Chaotic Maps

Definition 1.
Letn be an integer, x
∈
[
-
1,1
], and an n-order Chebyshev polynomial map T
n
(
x
)
:
[
-
1,1
]
→
[
-
1,1
] is defined as follows:(1)
T
n
x
=
cos
⁡
n
∗
arccos
⁡
x
.According to the definition, the Chebyshev polynomial map can also be defined recursively as follows:(2)
T
n
x
=
2
∗
x
∗
T
n
-
1
x
-
T
n
-
2
x
,where T
0
(
x
)
=
1 and T
2
(
x
)
=
x, n
≥
2.The Chebyshev polynomial map has the following two properties.(1) Semigroup property is as follows:(3)
T
r
T
s
x
=
cos
⁡
r
∗
cos
-
1
⁡
s
∗
cos
-
1
⁡
x
=
cos
⁡
r
∗
s
∗
cos
-
1
⁡
x
=
T
s
r
x
=
T
s
T
r
x
,where r, s are two integers, x
∈
[
-
1,1
].(2) Chaos property is as follows. Whenn is bigger than 1, an n-degree Chebyshev polynomial map T
n
(
x
)
:
[
-
1,1
]
→
[
-
1,1
] has the constant measure f
∗
(
x
)
=
1
/
(
π
1
-
x
2
) and positive Lyapunov exponent λ
=
ln
⁡
n
>
0.According to the periodicity ofy
=
cos
⁡
x, there exist multiple x associated with the same y to make the equation hold. To improve the security of classic Chebyshev polynomial map, Zhang [33] gave a proof that the Chebyshev polynomial map still keeps the semigroup property over the interval (
-
∞
,
∞
), which is calledthe extended Chebyshev chaotic maps with the following definition:(4)
T
n
x
=
2
x
T
n
-
1
x
-
T
n
-
2
x
mod
⁡
P
,where n
≥
2, x
∈
[
-
1,1
], and P is a big prime number. It can be easily found the following equation holds as well:(5)
T
r
T
s
x
=
T
s
r
x
=
T
s
T
r
x
mod
⁡
P
.Definition 2 (discrete logarithm problem (DLP)).
Given any two big integersx, y, find an integer s to make the equation T
s
(
x
)
≡
y hold.Definition 3 (decisional Diffie-Hellman problem (DDH)).
GivenT
r
(
x
), T
s
(
x
), and T
u
(
x
), where r, s, and u are unknown, determine whether equation T
s
r
(
x
)
=
T
u
(
x
)
mod
⁡
P holds or not.


## 2.2.2. The Advantages of Using Chebyshev Chaotic Maps

As a chaotic system characterizes excellent properties of diffusion and confusion, it is widely used to design various cryptographic schemes. Our design aims to provide a secure efficient mutual authentication with strong anonymity, and this means encryption will be integrated to keep the confidentiality of the identities. However, the traditional public key cryptography schemes are not desirable to achieve it since the management of encryption key in these schemes produces heavy computational burden. Inspired by the excellent semigroup property, the extended Chebyshev chaotic map over the finite field is used to develop our protocol since the discrete logarithm problem and Diffie-Hellman problem are assumed to be intractable within polynomial time [21]. However, there are no hardness assumptions of the discrete logarithm problems or the Diffie-Hellman problems about the Chebyshev chaotic maps over the interval [
-
1,1
] [34], so that it is still challenging to design a secure chaotic map-based key agreement protocol over the interval [
-
1,1
]. Meanwhile, with the Chebyshev chaotic map, our proposed based scheme enables the users and trusted server efficiently to generate the shared encryption key and agree session key without additional key management. Though there are some other types of chaos systems, only the extended Chebyshev chaotic map has the semigroup property and satisfies the requirements stated above. In addition, the Chebyshev map has good chaotic properties with mixture and ergodicity, and the chaotic sequences generated by the Chebyshev map have good statistical distribution characteristics as the mean is 0 [35]. Wang et al. [7, 8] pointed out that low dimension chaotic maps have degradation of dynamics in finite precision computations in computers; however, this issue can be addressed using appropriate implementation; for example, Liu et al. [36] proposed an analogue-digital mixed method to solve the dynamical degradation of digital chaotic system. Given the previous advantages, the extended Chebyshev chaotic map is used to construct mutual authentication with strong anonymity in this paper.


## 2.3. Security Definitions

Based on the attack model in literatures [37, 38], the security model of the proposed chaotic map based mutual authentication and key agreement with strong anonymity (
CMASA
) is defined in this section. In the model, the capability of the adversary A is defined by the following interactive game which consists of oracle queries and security assumptions.A can join the game through issuing series of oracle queries to any participant from the entity set ∏
U
i including the trusted server. During the interactive activities, A is assigned with some attacking capabilities to the authentication protocol. The communication channel is under the full control of A, which means A can intercept, block, inject, delete, and modify any message transferred via this channel. The queries that A can issue are as follows.E
x
c
u
t
e
(
∏
U
i
). This query is designed to assign A with passive attacking capability. After the execution of this query, all the transferred messages produced by the honest parities will be output according to the definition of P.S
e
n
d
(
∏
U
i
,
M
). This query is designed to simulate the situation that A has controlled the whole communication process. A can issue S
e
n
d query on M to ∏
U
i, and the corresponding entity from ∏
U
i will compute the results according to P and respond to A.R
e
v
e
a
l
(
∏
U
i
). This query is used to simulate the known key attacking. If it is a valid session, all the computed shared session keys by ∏
U
i will be responded to and null will be responded to otherwise.C
o
r
r
u
p
t
(
∏
U
i
). This query is used to simulate that A corrupts entities from ∏
U
i. A can obtain the permanent password and real identification of ∏
U
i with this query.S
y
m
E
n
c
(
{
E
,
D
}
,
k
,
{
M
,
C
}
). This query is designed to assign A with the capability of accessing the encryption oracle. In order to respond to A correctly, a list L
e is needed to setup and maintenance. Upon receiving the query S
y
m
E
n
c
(
E
,
k
,
M
), first check if there exists some entry {
K
,
M
,
C
} in L
e. If yes, return C of the corresponding entry; otherwise, a random value C
′ will be returned. Meanwhile, a new tuple {
K
,
M
,
C
′
} will be added into L
e. Equivalently, for the decryption query S
y
m
E
n
c
(
D
,
k
,
C
), first check if there exists some entry {
K
,
M
,
C
} in L
e, if yes, return M of the corresponding entry, and a random value M
′ will be returned, otherwise. Meanwhile, the new tuple {
K
,
M
′
,
C
} will be added to L
e.H
a
s
h
(
M
). This query is utilized to simulate hashing for A. To respond to A effectively, a list L
h will be set up. Upon receiving the query on m from A, firstly check if there already exists some entry {
m
,
h
} in L
h. If yes, return the value h of the existing entry to A. Otherwise, generate a random value h
′ as the response and add {
m
,
h
′
} to L
h at the same time.T
e
s
t
(
∏
U
i
). This query is used to measure the semantic security of the session key K
S. If the entity of this session key U has already computed K
S with his partnered peer, return K
S to A. Otherwise, null will be responded to. A can also issue a single T
e
s
t query to ∏
U
i, and ∏
U
i will make an unbiased toss b
∈
(
0,1
) to demine the response. If b
=
1, return K
S to A. Otherwise, return a random value.Definition 4 (security of the session key (ASK-Secure)).
In an adversary involved interactive game, the adversaryA can arbitrarily issue Test query, where the response is the real session key or a random value. If A issued a Test query to an unauthorized entity, A would be responded with ⊥. If A issued a Test query to a dishonest entity or the entity whose peer is dishonest, the corresponding real session key will be responded to. Otherwise, a random c from an unbiased coin toss is used to determine that the response is the real session key or a random value. A would guess the uncovered c through analyzing the response. Let the event E
=
{
A
wins  this  game
}, and let Adv
P
ASK
(
A
) be the advantage that A wins the distinguishability of P. If Adv
P
ASK
(
A
) is negligible, then P is called ASK-Secure [37].Definition 5 (security of symmetric encryption (OT-Secure)).
One-time security of symmetric encryption (OT-Secure) [39] means that the indistinguishability of symmetric encryption under the passive attack can also be called find-guess security. Let π
=
(
E
,
D
) be a symmetric encryption scheme and let A
=
(
A
1
,
A
2
) be an adversary of π, and then consider the following interactive game between π and A.(1)
Choosea
←
KSP.
(2)
Input1
k to run A
1. A
1 outputs two distinctive messages m
0
,
m
2
∈
MSP and the state s.
(3)
Chooseb
←
R
(
0,1
) randomly and compute c
←
E
a
(
m
b
).
(4)
Inputc
,
s and run A
2, and then A
2 outputs b
′
∈
[
0,1
].The advantage ofA represents how far it will guess the right b with the possibility bigger than 1
/
2; that is 2
P
r
[
b
=
b
′
]
-
1. During the whole process of the game, A is passive; in other words, it cannot access any encryption or decryption oracle.


## 3. Concrete Construction

The detailed construction of the proposed scheme is presented in this section. For convenience, the descriptions of all symbols to be used are listed in Description of Symbols.Suppose there exist three entities in our scheme, two system usersA, B, who need to authenticate each other, and a trusted third party Tread. During the authentication, Tread will authenticate A and B using their submitted messages. If Tread identifies that A or B has been revoked, the authentication process will be terminated. The whole process of authentication consists of two stages, that is, registration and authentication including key establishment.At the beginning of registration,A, B generate their passwords, respectively. They precompute passwords using a hash function and then submit them to Tread together with identifications and other related information. Upon receiving the registration queries from A and B, Tread will check the validity of the submitted information. If yes, the registering is successful and Tread would securely store the needed information locally. The authenticating can be launched by A or B, and then the process will be conducted through the following interactive steps.


### 3.1. Registration

A user can register using the following steps.(1) Tread chooses two random numbersx
,
s and a big prime number P, then computes T
s
=
T
s
(
x
)
mod
⁡
P, and publishes (
x
,
T
s
,
P
).(2) Useru chooses his P
W
u and computes H
(
H
P
W
u
∥
I
D
u
), and then sends {
I
D
u
,
H
(
P
W
u
)
,
H
(
H
(
P
W
u
)
∥
I
D
u
)
} to Tread.(3) Tread checks the validity ofI
D
u and H
(
P
W
u
) using H
(
H
(
P
W
u
)
∥
I
D
u
). If yes, it stores {
I
D
u
,
H
(
P
W
u
)
}. Otherwise, user u fails to register in the system.


### 3.2. Mutual Authentication and Key Establishment

UsersA and B can finish the authentication and establishment by following the steps shown in Figure 1.Figure 1
Process of authentication and key establishing.(
1)
A
→
B. A first chooses two numbers x
A, r
A randomly, and then computes T
A
=
T
r
A
(
x
), N
A
=
x
A
⊕
H
(
P
W
A
), and K
T
A
=
T
r
A
(
T
s
)
mod
⁡
P, where N
A denotes the temporary identification of A and K
T
A denotes the shared session key between A and Tread. After that, A encrypts I
D
A, x
A, and H
(
N
A
∥
t
A
∥
T
A
) using K
T
A; that is C
1
=
E
K
T
A
(
I
D
A
∥
x
A
∥
H
(
N
A
∥
t
A
∥
T
A
)
), where t
A is the timestamp of A. Next, A sends M
1
=
{
C
1
,
N
A
,
t
A
,
T
A
} to B.(
2)
B
→
T
r
e
a
d. Upon receiving M
1 from A, B first checks if t
B
-
t
A
<
Δ
T holds or not, where t
B is the timestamp of B. If yes, it stores N
A temporarily. Then, it chooses x
B, r
B randomly and computes T
B
=
T
r
B
(
x
), N
B
=
x
B
⊕
H
(
P
W
B
), and K
T
B
=
T
r
B
(
T
s
)
mod
⁡
P, where N
B denotes the temporary identification of B and K
T
B denotes the shared session key between B and Tread. After that, B encrypts I
D
B, x
B, and H
(
N
B
∥
t
B
∥
T
B
) using K
T
B, that is E
K
T
B
(
I
D
B
∥
x
B
∥
H
(
N
B
∥
t
B
∥
T
B
)
), where t
B is the timestamp of B. Next, B sends M
1
,
M
2
=
{
C
2
,
N
B
,
t
B
,
T
B
} to Tread.(
3)
T
r
e
a
d
→
B. Upon receiving M
1, M
2 from B, Tread checks if T
-
t
A
<
Δ
T, T
-
t
B
<
Δ
T holds or not, where T denotes the timestamp of Tread and Δ
T denotes the permissible time interval threshold. If so, Tread will compute the shared keys K
T
A
′
=
T
s
T
A
mod
⁡
P, K
T
B
′
=
T
s
(
T
B
)
mod
⁡
P, k
1
=
H
(
N
A
∥
t
A
∥
T
A
), and k
2
=
H
(
N
B
∥
t
B
∥
T
B
), then it decrypts T
A and T
B using K
T
A
′ and K
T
B
′. After that, Tread checks if H
(
N
A
∥
t
A
∥
T
A
)
=
k
1, H
(
N
B
∥
t
B
∥
T
B
)
=
k
2 hold or not. If yes, Tread validates N
A and N
B as follows.Step 1.
Search forH
(
P
W
A
) and H
(
P
W
B
) in the database.Step 2.
ComputeN
A
⊕
H
(
P
W
A
) and N
B
⊕
H
(
P
W
B
). And then check if both N
A
⊕
H
P
W
A
=
x
A and N
B
⊕
H
P
W
B
=
x
B hold or not. If yes, go to Step 3; else it terminates.Step 3.
Computeh
1
=
H
x
A and h
2
=
H
(
H
x
A
∥
H
x
B
), and then sends M
3
=
{
h
1
,
h
2
} to B.(
4)
B
→
A. Upon receiving M
3 from A, B first computes h
2
′
=
H
(
H
(
x
A
)
∥
H
(
x
B
)
) and then checks if h
2
′
=
h
2. If yes, B checks the temporary identification N
A of A. After that, B computes K
B
A
=
T
B
(
T
A
)
mod
⁡
P, h
3
=
H
(
K
B
A
∥
H
(
x
A
)
∥
N
B
), where K
B
A is the session key between B and A, and then sends M
4
=
{
h
3
,
T
B
,
N
B
} to A.(
5)
A
→
B. Upon receiving M
4 from B, A first computes K
A
B
=
T
A
(
T
B
)
mod
⁡
P, h
3
′
=
H
(
K
A
B
∥
H
(
x
A
)
∥
N
B
), where K
A
B is the session key between A and B and then checks if h
3
′
=
h
3. If yes, A confirms the temporary identification N
B of B and establishes the session key K
A
B. Then A computes the hash value M
5
=
H
(
K
A
B
∥
H
(
x
A
)
∥
N
B
) and sends it to B.At last,B checks M
5 from A as follows: firstly, it computes M
5
′
=
H
K
B
A
∥
N
B and then it checks if M
5
′
=
M
5. If it holds, the authentication is done.


## 3.1. Registration

A user can register using the following steps.(1) Tread chooses two random numbersx
,
s and a big prime number P, then computes T
s
=
T
s
(
x
)
mod
⁡
P, and publishes (
x
,
T
s
,
P
).(2) Useru chooses his P
W
u and computes H
(
H
P
W
u
∥
I
D
u
), and then sends {
I
D
u
,
H
(
P
W
u
)
,
H
(
H
(
P
W
u
)
∥
I
D
u
)
} to Tread.(3) Tread checks the validity ofI
D
u and H
(
P
W
u
) using H
(
H
(
P
W
u
)
∥
I
D
u
). If yes, it stores {
I
D
u
,
H
(
P
W
u
)
}. Otherwise, user u fails to register in the system.


## 3.2. Mutual Authentication and Key Establishment

UsersA and B can finish the authentication and establishment by following the steps shown in Figure 1.Figure 1
Process of authentication and key establishing.(
1)
A
→
B. A first chooses two numbers x
A, r
A randomly, and then computes T
A
=
T
r
A
(
x
), N
A
=
x
A
⊕
H
(
P
W
A
), and K
T
A
=
T
r
A
(
T
s
)
mod
⁡
P, where N
A denotes the temporary identification of A and K
T
A denotes the shared session key between A and Tread. After that, A encrypts I
D
A, x
A, and H
(
N
A
∥
t
A
∥
T
A
) using K
T
A; that is C
1
=
E
K
T
A
(
I
D
A
∥
x
A
∥
H
(
N
A
∥
t
A
∥
T
A
)
), where t
A is the timestamp of A. Next, A sends M
1
=
{
C
1
,
N
A
,
t
A
,
T
A
} to B.(
2)
B
→
T
r
e
a
d. Upon receiving M
1 from A, B first checks if t
B
-
t
A
<
Δ
T holds or not, where t
B is the timestamp of B. If yes, it stores N
A temporarily. Then, it chooses x
B, r
B randomly and computes T
B
=
T
r
B
(
x
), N
B
=
x
B
⊕
H
(
P
W
B
), and K
T
B
=
T
r
B
(
T
s
)
mod
⁡
P, where N
B denotes the temporary identification of B and K
T
B denotes the shared session key between B and Tread. After that, B encrypts I
D
B, x
B, and H
(
N
B
∥
t
B
∥
T
B
) using K
T
B, that is E
K
T
B
(
I
D
B
∥
x
B
∥
H
(
N
B
∥
t
B
∥
T
B
)
), where t
B is the timestamp of B. Next, B sends M
1
,
M
2
=
{
C
2
,
N
B
,
t
B
,
T
B
} to Tread.(
3)
T
r
e
a
d
→
B. Upon receiving M
1, M
2 from B, Tread checks if T
-
t
A
<
Δ
T, T
-
t
B
<
Δ
T holds or not, where T denotes the timestamp of Tread and Δ
T denotes the permissible time interval threshold. If so, Tread will compute the shared keys K
T
A
′
=
T
s
T
A
mod
⁡
P, K
T
B
′
=
T
s
(
T
B
)
mod
⁡
P, k
1
=
H
(
N
A
∥
t
A
∥
T
A
), and k
2
=
H
(
N
B
∥
t
B
∥
T
B
), then it decrypts T
A and T
B using K
T
A
′ and K
T
B
′. After that, Tread checks if H
(
N
A
∥
t
A
∥
T
A
)
=
k
1, H
(
N
B
∥
t
B
∥
T
B
)
=
k
2 hold or not. If yes, Tread validates N
A and N
B as follows.Step 1.
Search forH
(
P
W
A
) and H
(
P
W
B
) in the database.Step 2.
ComputeN
A
⊕
H
(
P
W
A
) and N
B
⊕
H
(
P
W
B
). And then check if both N
A
⊕
H
P
W
A
=
x
A and N
B
⊕
H
P
W
B
=
x
B hold or not. If yes, go to Step 3; else it terminates.Step 3.
Computeh
1
=
H
x
A and h
2
=
H
(
H
x
A
∥
H
x
B
), and then sends M
3
=
{
h
1
,
h
2
} to B.(
4)
B
→
A. Upon receiving M
3 from A, B first computes h
2
′
=
H
(
H
(
x
A
)
∥
H
(
x
B
)
) and then checks if h
2
′
=
h
2. If yes, B checks the temporary identification N
A of A. After that, B computes K
B
A
=
T
B
(
T
A
)
mod
⁡
P, h
3
=
H
(
K
B
A
∥
H
(
x
A
)
∥
N
B
), where K
B
A is the session key between B and A, and then sends M
4
=
{
h
3
,
T
B
,
N
B
} to A.(
5)
A
→
B. Upon receiving M
4 from B, A first computes K
A
B
=
T
A
(
T
B
)
mod
⁡
P, h
3
′
=
H
(
K
A
B
∥
H
(
x
A
)
∥
N
B
), where K
A
B is the session key between A and B and then checks if h
3
′
=
h
3. If yes, A confirms the temporary identification N
B of B and establishes the session key K
A
B. Then A computes the hash value M
5
=
H
(
K
A
B
∥
H
(
x
A
)
∥
N
B
) and sends it to B.At last,B checks M
5 from A as follows: firstly, it computes M
5
′
=
H
K
B
A
∥
N
B and then it checks if M
5
′
=
M
5. If it holds, the authentication is done.


## 4. Analysis

### 4.1. Security

The proof of the security consists of multiple interactive games, and it is based on the difference lemma [37], which is briefly reviewed as follows.Lemma 6 (difference lemma).
LetE
a
,
E
b, and E
c be the events following some distribution. If E
a
∧
¬
E
c
⇔
E
b
∧
¬
E
c, then the following equation holds:(6)
Pr
⁡
E
a
-
Pr
⁡
E
b
≤
Pr
⁡
E
c
.The proof of this lemma can be found in [37].


#### 4.1.1. Security of Session Key

The security of session key for our proposed scheme is given by Theorem7.Theorem 7.
LetA
d
v
Γ
O
T be the advantage that an O
T adversary breaks the symmetric encryption within time t
1, and let A
D
V
G
D
D
H be the advantage that D
D
H adversary breaks D
D
H with time t
2. Then, the advantage that A breaks a A
S
K-secure mutual authentication scheme is (7)
A
d
v
m
s
a
a
a
s
k
t
′
,
q
0
,
q
1
,
q
2
,
q
3
≤
∑
i
=
1
3
q
i
2
2
λ
-
1
+
2
q
1
+
2
q
2
l
+
2
A
d
v
Γ
O
T
t
1
,
q
0
,
q
1
,
q
2
,
q
3
+
2
A
D
V
G
D
D
H
t
2
,
q
0
,
q
1
,
q
2
,
q
3
,where t
′
≤
t
1
+
t
2
+
(
q
1
+
q
2
)
τ
1
+
q
3
(
τ
2
+
τ
3
), q
0 is the times of Send queries, q
1
,
q
2 are the times of S
y
m
E
n
c queries of A to T and B to T respectively, q
3 is the times of H
a
s
h queries, l is the size of I
D
u space, λ is the security parameter, and τ
1
,
τ
2, and τ
3 are the running time of single symmetric cryptographic operation, chaotic map operation, and Hash operation respectively.Proof.
To illustrate the proof, six interactive gamesG
i (0
≤
i
≤
5) are introduced. In every game G
i, A can arbitrarily issue any oracle queries defined in Section 2.3. When every game G
i is done, the possibility of event E
i
=
{
A wins G
i
} can be captured.
Game
G
0. This game depicts the attacking from A on MSAA in reality. According to the definition, the advantage should be as follows:(8)
Adv
msaa
OT
A
=
2
Pr
⁡
E
0
-
1
.
Game
G
1. This game can simulate all oracle queries; the only difference is that guessing attack on real identification will be simulated as well. Since I
D
A, I
D
B will be encrypted by OT-Secure symmetric encryption, every value of E
K
T
A
(
I
D
A
∥
x
A
∥
H
(
N
A
∥
T
A
∥
T
r
A
x
)
), E
K
T
B
(
I
D
B
∥
x
B
∥
H
(
N
B
∥
T
B
∥
T
r
B
x
)
) should be distinctive. Therefore, A has no other auxiliary information to validate its guess on the real identification; that is to say, the success possibility is (
q
1
+
q
2
)
/
N. According to the difference lemma [37], we can have(9)
Pr
⁡
E
0
-
Pr
⁡
E
1
≤
q
1
+
q
2
l
.
Game
G
2. This game is the same as previous games except for the additional simulation of breaking symmetric encryption using S
y
m
E
n
c. According to the difference lemma, we can have(10)
Pr
⁡
E
1
-
Pr
⁡
E
2
≤
q
1
+
q
2
2
λ
+
Adv
Γ
OT
A
.
Game
G
3. This game is same as the previous games, except for the additional simulation of collusion attack to Hash. Game G
3 is indistinguishable against G
2 except for the possible collision in L
H. According to the Birthday Paradox and difference lemma, we can have(11)
Pr
⁡
E
2
-
Pr
⁡
E
3
≤
q
3
2
2
λ
.
Game
G
4. This game is same as the previous games except for the modification on the response of T
a
(
x
)
mod
⁡
P and T
b
(
x
)
mod
⁡
P on the S
e
n
d query. Assume (
X
,
Y
,
Z
)
=
(
T
a
(
x
)
,
T
b
(
x
)
,
T
a
b
(
x
)
) is a random extended chaotic CDH triple. The simulator S will serve all oracle queries from all honest entities using (
X
,
Y
,
Z
). To do so, S firstly sets passwords for A and B and then responds as follows: it computes the chaotic maps {
(
a
0
,
T
a
0
(
x
)
)
,
(
b
0
,
T
b
0
(
x
)
)
,
T
a
0
(
x
)
,
T
b
0
(
x
), and z
0
=
T
a
0
b
0
(
x
)
} and stores them in the list, where a
0
,
b
0 is random. For the Test query, it returns the stored z
0 as the response. In terms of the definition, the response for Test query is valid. Meanwhile, the random variable set in G
3 will be replaced by another identical distributed random variable set in G
4. Hence, the possibility that A wins G
4 and G
3 is the same, then we have(12)
Pr
⁡
E
3
=
Pr
⁡
E
4
.
Game
G
5. This game simulates A breaking DDH. All the queries are same as the previous queries except that the response (
X
,
Y
,
Z
) is not a CDH triple, but a random triple (
T
u
(
x
)
,
T
v
(
x
)
,
T
w
(
x
)
).
Assume thatA
DDH is a challenger who attempts to break the distinguishability of DDH over G, then A
ask is an adversary who is capable of breaking the security of session key. A
DDH responds to c
∈
(
0,1
) from the unbiased toss as follows. If c
=
1, it returns the real session key to A
ask; else it returns a random number to A
ask. After that, A
ask outputs its guess, c
′. If c
′
=
c, A
ask wins this game. A
DDH can respond for querying E
x
c
u
t
e
,
C
o
r
r
u
p
t
,
S
y
m
E
n
c, and T
e
s
t; the process is the same as previous games except for the query on (
X
,
Y
,
Z
) as inputs. If A
ask outputs c, A
DDH outputs 1; otherwise, it outputs 0. If (
X
,
Y
,
Z
) is exactly a real CDH triple, then A
DDH runs A
ask in G
4, so we have Pr
⁡
[
A
DDH outputs 1
]
=
P
r
[
E
4
]. If (
X
,
Y
,
Z
) is a random triple, A
DDH runs A
ask in G
5, so we have Pr
⁡
A
DDH
o
u
t
p
u
t
s
0
=
Pr
⁡
[
E
5
]. Thus,(13)
Pr
⁡
E
4
-
Pr
⁡
E
5
≤
Adv
G
DDH
A
DDH
.Since the session key Z
0 is random, the information about c does not leak, so we have(14)
Pr
⁡
E
5
=
1
2
.According to formulas (8)–(14), the advantage can be evaluated as follows:(15)
Adv
msaa
ask
A
ask
≤
∑
i
=
1
3
q
i
2
2
λ
-
1
+
2
q
1
+
2
q
2
l
+
2
Adv
Γ
OT
t
1
,
q
0
,
q
1
,
q
2
,
q
3
+
2
Adv
G
DDH
t
2
,
q
0
,
q
1
,
q
2
,
q
3
.


#### 4.1.2. Strong Anonymity for Client

To prevent the exposure of real identification during the message exchange, one practical solution is employing pseudonym. In the proposed scheme, if the adversaryA attempts to obtain the real identification of a system user, the first possible step is to obtain the key to decrypt the cihpertext C
i even if A can intercept all the transferred messages. Though A possesses T
r
A
(
x
), T
r
B
(
x
), and T
s, he or she still faces the difficulty of solving DL problem if A tries to deduce the secret value from T
A
T or T
B
T. Since A cannot decrypt C
i, he or she cannot get to know the real identification, and then the privacy of users is preserved. For the entities who get involved in the authentication, they only get the temporary identification, which is generated by the XOR operation on the real identification and random number, so that they cannot know the real identification of the partnered peer. Even if he or she stores N
i for off-line analysis in future, N
i
∗ in the next session is generated by another distinctive random number, so N
i and N
i
∗ are indistinguishable for the PPT adversary A. Furthermore, a system user entity even cannot determine whether the current partnered peer is the same with those in historic sessions or not. Thus, our proposed scheme achieves the strong anonymity successfully.


#### 4.1.3. Resistance to Man-in-the-Middle Attack

Suppose there exists an active attackerA over the communication channel, who attempts to intercept and tamper the messages transferred via this channel to conduct the man-in-the-middle attack. If A tries to carry out the attack by tampering C
1, C
2, he or she will face the difficulty of solving DL problem. If A attempts to tamper or forge C
3, C
4, and C
5, he or she will face the difficulty of breaking the secure one-way hash function according to the definition of the protocol. Above all, the proposed protocol is secure enough to prevent the man-in-the-middle attack.


#### 4.1.4. Resistance to Replay Attack

According to the construction of the presented protocol, all the transferred messages ofA, B, and Tread use timestamps t
A, t
B to provide freshness. Furthermore, the system users have independently chosen (x
A
,
r
A) and (x
B
,
r
B) randomly to ensure freshness at the beginning of every authentication session. So, the proposed scheme can counter replay attack effectively.


#### 4.1.5. Forward Secrecy

In our scheme, the forward secrecy means the previous used session key cannot be deduced even if adversaryA is given the current session key and the password of the user. Actually, the establishment of the session key K
A
B (or K
B
A) between A and B is based on x
A and x
B chosen by themselves independently, and A cannot get anything about K
A
B (or K
B
A) because the randomness of x
A and x
B, and the success possibility will not increase even if P
W
A and P
W
B are given to the adversary.


#### 4.1.6. Backward Secrecy

The backward secrecy of our scheme refers to the fact that even if the adversaryA has obtained a client’s password, all historic session keys, and current session key, could not finish authentication and key agreement. However, all the messages are transferred in anonymous way; thus, A cannot generate a valid message without knowing the real user identification according to the protocol, even if he or she is given the password P
W. So, our scheme achieves the backward secrecy.The overall comparison of security between our proposed scheme and the existing similar schemes is listed in Table1.Table 1
Comparison of security.
Scheme
Lee et al.’s [20]
Xie et al.’s [26]
Farash and Attari’s [30]
Li et al.’s [31]
Lee et al.’s [25]
Niu and Wang’s [32]
Ours
Forward secrecy
√
√
√
√
√
√
√
Backward secrecy
√
×
×
×
×
√
√
Resistance to the replay attack
√
√
√
√
√
√
√
Resistance to the MIM attack
×
√
√
√
√
√
√
Mutual anonymity
√
×
×
×
×
×
√
Strong anonymity
×
×
×
×
×
×
√All the schemes listed in Table1 have employed random number in the construction, so they all can achieve the forward secrecy. Since only our scheme and work in [20] uncover the real identification, both schemes can ensure the backward secrecy. Subsequently, all the schemes in [25, 26, 30, 31] cannot provide mutual anonymity for the same reason. Although the scheme in [20] can uncover the real identification for the outside attacker, the authenticated peers can know the real identification of each other, so that it lacks the strong anonymity, and the scheme in [32] fails to protect the identity of the server because the identity of the user is transferred in plaintext during authentication, so it cannot provide strong anonymity. For the use of timestamp and random number, all the schemes in Table 1 can counter the replay attack. However, in the scheme of [20], the attacker can choose a random number x
′ and compute R
A
′
=
T
x
′
r, and then he or she can finish the authentication successfully by blocking and injecting operation; thus, it is vulnerable to the man-in-the-middle attack.


### 4.2. Comparison of Performance

The overall performance comparison is listed in Table2.Table 2
Comparison on performance.
Scheme
Client
Server
Lee et al. [20]
6
T
H
+
6
T
C
4
T
H
+
2
T
C
Xie et al.’s [26]
6
T
H
+
6
T
C
6
T
H
+
4
T
C
Farash and Attari’s [30]
8
T
H
+
6
T
C
4
T
H
+
4
T
C
Li et al.’s [31]
4
T
H
+
8
T
C
5
T
C
Lee et al.’s [25]
9
T
H
+
2
T
E
+
2
T
D
+
7
T
C
4
T
H
+
2
T
E
+
2
T
D
+
2
T
C
Niu and Wang’s [32]
4
T
H
+
2
T
E
+
2
T
D
+
4
T
C
2
T
E
+
2
T
D
Ours
7
T
H
+
2
T
E
+
6
T
C
3
T
H
+
2
T
D
+
2
T
CAs the authentication is a sort of synchronized process, the total computational cost of the client and server in a whole authentication and key agreement should be investigated. Since the cost of XOR operation and module addition are much cheaper, these two operations are not included in comparison, and only symmetric encryption/decryption operation, chaotic map operation, and hash operations are evaluated. Although no much advantage of performance is won in the proposed scheme, its critical privacy preserving feature deserves it.


### 4.3. Application Prospects

Our proposed scheme can be applied to privacy-sensitive situations, such as VANETs [29]. Consider an authentication scenario in VANETs as shown in Figure 2. Since the communication via wireless channel, the system is susceptible to attack from outside and inside adversaries. When the driver of vehicle A detects that another vehicle B nearby is sharing some resources, he becomes interested in using the application installed in his vehicle, he then issues a request of accessing the data. On one hand, for security, A is not allowed to access B’s data directly, and B would firstly verify whether A is an authentic entity. However, A and B are unwilling to reveal their real identities to each other. Then, A and B have to proceed with a mutual anonymous authentication protocol. Meanwhile, A and B also want to keep themselves anonymous even if they authenticate each other again in the future, since few drivers like to expose their trace to other untrusted entities.Figure 2
Authentication in VANETs.On the other hand, the real identities ofA and B including the transferred messages should be kept confidential to any external entities, and any external attacker is not allowed to distinguish users from two different sessions using all intercepted messages. However, our proposed protocol can achieve all goals stated previously. Since the road side unit (RSU) is supposed to be trusted, then it can be regarded as the trusted server in our protocol, and then vehicle A and B can fulfill authentication via RSU by following the steps as defined in Section 3.


## 4.1. Security

The proof of the security consists of multiple interactive games, and it is based on the difference lemma [37], which is briefly reviewed as follows.Lemma 6 (difference lemma).
LetE
a
,
E
b, and E
c be the events following some distribution. If E
a
∧
¬
E
c
⇔
E
b
∧
¬
E
c, then the following equation holds:(6)
Pr
⁡
E
a
-
Pr
⁡
E
b
≤
Pr
⁡
E
c
.The proof of this lemma can be found in [37].


### 4.1.1. Security of Session Key

The security of session key for our proposed scheme is given by Theorem7.Theorem 7.
LetA
d
v
Γ
O
T be the advantage that an O
T adversary breaks the symmetric encryption within time t
1, and let A
D
V
G
D
D
H be the advantage that D
D
H adversary breaks D
D
H with time t
2. Then, the advantage that A breaks a A
S
K-secure mutual authentication scheme is (7)
A
d
v
m
s
a
a
a
s
k
t
′
,
q
0
,
q
1
,
q
2
,
q
3
≤
∑
i
=
1
3
q
i
2
2
λ
-
1
+
2
q
1
+
2
q
2
l
+
2
A
d
v
Γ
O
T
t
1
,
q
0
,
q
1
,
q
2
,
q
3
+
2
A
D
V
G
D
D
H
t
2
,
q
0
,
q
1
,
q
2
,
q
3
,where t
′
≤
t
1
+
t
2
+
(
q
1
+
q
2
)
τ
1
+
q
3
(
τ
2
+
τ
3
), q
0 is the times of Send queries, q
1
,
q
2 are the times of S
y
m
E
n
c queries of A to T and B to T respectively, q
3 is the times of H
a
s
h queries, l is the size of I
D
u space, λ is the security parameter, and τ
1
,
τ
2, and τ
3 are the running time of single symmetric cryptographic operation, chaotic map operation, and Hash operation respectively.Proof.
To illustrate the proof, six interactive gamesG
i (0
≤
i
≤
5) are introduced. In every game G
i, A can arbitrarily issue any oracle queries defined in Section 2.3. When every game G
i is done, the possibility of event E
i
=
{
A wins G
i
} can be captured.
Game
G
0. This game depicts the attacking from A on MSAA in reality. According to the definition, the advantage should be as follows:(8)
Adv
msaa
OT
A
=
2
Pr
⁡
E
0
-
1
.
Game
G
1. This game can simulate all oracle queries; the only difference is that guessing attack on real identification will be simulated as well. Since I
D
A, I
D
B will be encrypted by OT-Secure symmetric encryption, every value of E
K
T
A
(
I
D
A
∥
x
A
∥
H
(
N
A
∥
T
A
∥
T
r
A
x
)
), E
K
T
B
(
I
D
B
∥
x
B
∥
H
(
N
B
∥
T
B
∥
T
r
B
x
)
) should be distinctive. Therefore, A has no other auxiliary information to validate its guess on the real identification; that is to say, the success possibility is (
q
1
+
q
2
)
/
N. According to the difference lemma [37], we can have(9)
Pr
⁡
E
0
-
Pr
⁡
E
1
≤
q
1
+
q
2
l
.
Game
G
2. This game is the same as previous games except for the additional simulation of breaking symmetric encryption using S
y
m
E
n
c. According to the difference lemma, we can have(10)
Pr
⁡
E
1
-
Pr
⁡
E
2
≤
q
1
+
q
2
2
λ
+
Adv
Γ
OT
A
.
Game
G
3. This game is same as the previous games, except for the additional simulation of collusion attack to Hash. Game G
3 is indistinguishable against G
2 except for the possible collision in L
H. According to the Birthday Paradox and difference lemma, we can have(11)
Pr
⁡
E
2
-
Pr
⁡
E
3
≤
q
3
2
2
λ
.
Game
G
4. This game is same as the previous games except for the modification on the response of T
a
(
x
)
mod
⁡
P and T
b
(
x
)
mod
⁡
P on the S
e
n
d query. Assume (
X
,
Y
,
Z
)
=
(
T
a
(
x
)
,
T
b
(
x
)
,
T
a
b
(
x
)
) is a random extended chaotic CDH triple. The simulator S will serve all oracle queries from all honest entities using (
X
,
Y
,
Z
). To do so, S firstly sets passwords for A and B and then responds as follows: it computes the chaotic maps {
(
a
0
,
T
a
0
(
x
)
)
,
(
b
0
,
T
b
0
(
x
)
)
,
T
a
0
(
x
)
,
T
b
0
(
x
), and z
0
=
T
a
0
b
0
(
x
)
} and stores them in the list, where a
0
,
b
0 is random. For the Test query, it returns the stored z
0 as the response. In terms of the definition, the response for Test query is valid. Meanwhile, the random variable set in G
3 will be replaced by another identical distributed random variable set in G
4. Hence, the possibility that A wins G
4 and G
3 is the same, then we have(12)
Pr
⁡
E
3
=
Pr
⁡
E
4
.
Game
G
5. This game simulates A breaking DDH. All the queries are same as the previous queries except that the response (
X
,
Y
,
Z
) is not a CDH triple, but a random triple (
T
u
(
x
)
,
T
v
(
x
)
,
T
w
(
x
)
).
Assume thatA
DDH is a challenger who attempts to break the distinguishability of DDH over G, then A
ask is an adversary who is capable of breaking the security of session key. A
DDH responds to c
∈
(
0,1
) from the unbiased toss as follows. If c
=
1, it returns the real session key to A
ask; else it returns a random number to A
ask. After that, A
ask outputs its guess, c
′. If c
′
=
c, A
ask wins this game. A
DDH can respond for querying E
x
c
u
t
e
,
C
o
r
r
u
p
t
,
S
y
m
E
n
c, and T
e
s
t; the process is the same as previous games except for the query on (
X
,
Y
,
Z
) as inputs. If A
ask outputs c, A
DDH outputs 1; otherwise, it outputs 0. If (
X
,
Y
,
Z
) is exactly a real CDH triple, then A
DDH runs A
ask in G
4, so we have Pr
⁡
[
A
DDH outputs 1
]
=
P
r
[
E
4
]. If (
X
,
Y
,
Z
) is a random triple, A
DDH runs A
ask in G
5, so we have Pr
⁡
A
DDH
o
u
t
p
u
t
s
0
=
Pr
⁡
[
E
5
]. Thus,(13)
Pr
⁡
E
4
-
Pr
⁡
E
5
≤
Adv
G
DDH
A
DDH
.Since the session key Z
0 is random, the information about c does not leak, so we have(14)
Pr
⁡
E
5
=
1
2
.According to formulas (8)–(14), the advantage can be evaluated as follows:(15)
Adv
msaa
ask
A
ask
≤
∑
i
=
1
3
q
i
2
2
λ
-
1
+
2
q
1
+
2
q
2
l
+
2
Adv
Γ
OT
t
1
,
q
0
,
q
1
,
q
2
,
q
3
+
2
Adv
G
DDH
t
2
,
q
0
,
q
1
,
q
2
,
q
3
.


### 4.1.2. Strong Anonymity for Client

To prevent the exposure of real identification during the message exchange, one practical solution is employing pseudonym. In the proposed scheme, if the adversaryA attempts to obtain the real identification of a system user, the first possible step is to obtain the key to decrypt the cihpertext C
i even if A can intercept all the transferred messages. Though A possesses T
r
A
(
x
), T
r
B
(
x
), and T
s, he or she still faces the difficulty of solving DL problem if A tries to deduce the secret value from T
A
T or T
B
T. Since A cannot decrypt C
i, he or she cannot get to know the real identification, and then the privacy of users is preserved. For the entities who get involved in the authentication, they only get the temporary identification, which is generated by the XOR operation on the real identification and random number, so that they cannot know the real identification of the partnered peer. Even if he or she stores N
i for off-line analysis in future, N
i
∗ in the next session is generated by another distinctive random number, so N
i and N
i
∗ are indistinguishable for the PPT adversary A. Furthermore, a system user entity even cannot determine whether the current partnered peer is the same with those in historic sessions or not. Thus, our proposed scheme achieves the strong anonymity successfully.


### 4.1.3. Resistance to Man-in-the-Middle Attack

Suppose there exists an active attackerA over the communication channel, who attempts to intercept and tamper the messages transferred via this channel to conduct the man-in-the-middle attack. If A tries to carry out the attack by tampering C
1, C
2, he or she will face the difficulty of solving DL problem. If A attempts to tamper or forge C
3, C
4, and C
5, he or she will face the difficulty of breaking the secure one-way hash function according to the definition of the protocol. Above all, the proposed protocol is secure enough to prevent the man-in-the-middle attack.


### 4.1.4. Resistance to Replay Attack

According to the construction of the presented protocol, all the transferred messages ofA, B, and Tread use timestamps t
A, t
B to provide freshness. Furthermore, the system users have independently chosen (x
A
,
r
A) and (x
B
,
r
B) randomly to ensure freshness at the beginning of every authentication session. So, the proposed scheme can counter replay attack effectively.


### 4.1.5. Forward Secrecy

In our scheme, the forward secrecy means the previous used session key cannot be deduced even if adversaryA is given the current session key and the password of the user. Actually, the establishment of the session key K
A
B (or K
B
A) between A and B is based on x
A and x
B chosen by themselves independently, and A cannot get anything about K
A
B (or K
B
A) because the randomness of x
A and x
B, and the success possibility will not increase even if P
W
A and P
W
B are given to the adversary.


### 4.1.6. Backward Secrecy

The backward secrecy of our scheme refers to the fact that even if the adversaryA has obtained a client’s password, all historic session keys, and current session key, could not finish authentication and key agreement. However, all the messages are transferred in anonymous way; thus, A cannot generate a valid message without knowing the real user identification according to the protocol, even if he or she is given the password P
W. So, our scheme achieves the backward secrecy.The overall comparison of security between our proposed scheme and the existing similar schemes is listed in Table1.Table 1
Comparison of security.
Scheme
Lee et al.’s [20]
Xie et al.’s [26]
Farash and Attari’s [30]
Li et al.’s [31]
Lee et al.’s [25]
Niu and Wang’s [32]
Ours
Forward secrecy
√
√
√
√
√
√
√
Backward secrecy
√
×
×
×
×
√
√
Resistance to the replay attack
√
√
√
√
√
√
√
Resistance to the MIM attack
×
√
√
√
√
√
√
Mutual anonymity
√
×
×
×
×
×
√
Strong anonymity
×
×
×
×
×
×
√All the schemes listed in Table1 have employed random number in the construction, so they all can achieve the forward secrecy. Since only our scheme and work in [20] uncover the real identification, both schemes can ensure the backward secrecy. Subsequently, all the schemes in [25, 26, 30, 31] cannot provide mutual anonymity for the same reason. Although the scheme in [20] can uncover the real identification for the outside attacker, the authenticated peers can know the real identification of each other, so that it lacks the strong anonymity, and the scheme in [32] fails to protect the identity of the server because the identity of the user is transferred in plaintext during authentication, so it cannot provide strong anonymity. For the use of timestamp and random number, all the schemes in Table 1 can counter the replay attack. However, in the scheme of [20], the attacker can choose a random number x
′ and compute R
A
′
=
T
x
′
r, and then he or she can finish the authentication successfully by blocking and injecting operation; thus, it is vulnerable to the man-in-the-middle attack.


## 4.1.1. Security of Session Key

The security of session key for our proposed scheme is given by Theorem7.Theorem 7.
LetA
d
v
Γ
O
T be the advantage that an O
T adversary breaks the symmetric encryption within time t
1, and let A
D
V
G
D
D
H be the advantage that D
D
H adversary breaks D
D
H with time t
2. Then, the advantage that A breaks a A
S
K-secure mutual authentication scheme is (7)
A
d
v
m
s
a
a
a
s
k
t
′
,
q
0
,
q
1
,
q
2
,
q
3
≤
∑
i
=
1
3
q
i
2
2
λ
-
1
+
2
q
1
+
2
q
2
l
+
2
A
d
v
Γ
O
T
t
1
,
q
0
,
q
1
,
q
2
,
q
3
+
2
A
D
V
G
D
D
H
t
2
,
q
0
,
q
1
,
q
2
,
q
3
,where t
′
≤
t
1
+
t
2
+
(
q
1
+
q
2
)
τ
1
+
q
3
(
τ
2
+
τ
3
), q
0 is the times of Send queries, q
1
,
q
2 are the times of S
y
m
E
n
c queries of A to T and B to T respectively, q
3 is the times of H
a
s
h queries, l is the size of I
D
u space, λ is the security parameter, and τ
1
,
τ
2, and τ
3 are the running time of single symmetric cryptographic operation, chaotic map operation, and Hash operation respectively.Proof.
To illustrate the proof, six interactive gamesG
i (0
≤
i
≤
5) are introduced. In every game G
i, A can arbitrarily issue any oracle queries defined in Section 2.3. When every game G
i is done, the possibility of event E
i
=
{
A wins G
i
} can be captured.
Game
G
0. This game depicts the attacking from A on MSAA in reality. According to the definition, the advantage should be as follows:(8)
Adv
msaa
OT
A
=
2
Pr
⁡
E
0
-
1
.
Game
G
1. This game can simulate all oracle queries; the only difference is that guessing attack on real identification will be simulated as well. Since I
D
A, I
D
B will be encrypted by OT-Secure symmetric encryption, every value of E
K
T
A
(
I
D
A
∥
x
A
∥
H
(
N
A
∥
T
A
∥
T
r
A
x
)
), E
K
T
B
(
I
D
B
∥
x
B
∥
H
(
N
B
∥
T
B
∥
T
r
B
x
)
) should be distinctive. Therefore, A has no other auxiliary information to validate its guess on the real identification; that is to say, the success possibility is (
q
1
+
q
2
)
/
N. According to the difference lemma [37], we can have(9)
Pr
⁡
E
0
-
Pr
⁡
E
1
≤
q
1
+
q
2
l
.
Game
G
2. This game is the same as previous games except for the additional simulation of breaking symmetric encryption using S
y
m
E
n
c. According to the difference lemma, we can have(10)
Pr
⁡
E
1
-
Pr
⁡
E
2
≤
q
1
+
q
2
2
λ
+
Adv
Γ
OT
A
.
Game
G
3. This game is same as the previous games, except for the additional simulation of collusion attack to Hash. Game G
3 is indistinguishable against G
2 except for the possible collision in L
H. According to the Birthday Paradox and difference lemma, we can have(11)
Pr
⁡
E
2
-
Pr
⁡
E
3
≤
q
3
2
2
λ
.
Game
G
4. This game is same as the previous games except for the modification on the response of T
a
(
x
)
mod
⁡
P and T
b
(
x
)
mod
⁡
P on the S
e
n
d query. Assume (
X
,
Y
,
Z
)
=
(
T
a
(
x
)
,
T
b
(
x
)
,
T
a
b
(
x
)
) is a random extended chaotic CDH triple. The simulator S will serve all oracle queries from all honest entities using (
X
,
Y
,
Z
). To do so, S firstly sets passwords for A and B and then responds as follows: it computes the chaotic maps {
(
a
0
,
T
a
0
(
x
)
)
,
(
b
0
,
T
b
0
(
x
)
)
,
T
a
0
(
x
)
,
T
b
0
(
x
), and z
0
=
T
a
0
b
0
(
x
)
} and stores them in the list, where a
0
,
b
0 is random. For the Test query, it returns the stored z
0 as the response. In terms of the definition, the response for Test query is valid. Meanwhile, the random variable set in G
3 will be replaced by another identical distributed random variable set in G
4. Hence, the possibility that A wins G
4 and G
3 is the same, then we have(12)
Pr
⁡
E
3
=
Pr
⁡
E
4
.
Game
G
5. This game simulates A breaking DDH. All the queries are same as the previous queries except that the response (
X
,
Y
,
Z
) is not a CDH triple, but a random triple (
T
u
(
x
)
,
T
v
(
x
)
,
T
w
(
x
)
).
Assume thatA
DDH is a challenger who attempts to break the distinguishability of DDH over G, then A
ask is an adversary who is capable of breaking the security of session key. A
DDH responds to c
∈
(
0,1
) from the unbiased toss as follows. If c
=
1, it returns the real session key to A
ask; else it returns a random number to A
ask. After that, A
ask outputs its guess, c
′. If c
′
=
c, A
ask wins this game. A
DDH can respond for querying E
x
c
u
t
e
,
C
o
r
r
u
p
t
,
S
y
m
E
n
c, and T
e
s
t; the process is the same as previous games except for the query on (
X
,
Y
,
Z
) as inputs. If A
ask outputs c, A
DDH outputs 1; otherwise, it outputs 0. If (
X
,
Y
,
Z
) is exactly a real CDH triple, then A
DDH runs A
ask in G
4, so we have Pr
⁡
[
A
DDH outputs 1
]
=
P
r
[
E
4
]. If (
X
,
Y
,
Z
) is a random triple, A
DDH runs A
ask in G
5, so we have Pr
⁡
A
DDH
o
u
t
p
u
t
s
0
=
Pr
⁡
[
E
5
]. Thus,(13)
Pr
⁡
E
4
-
Pr
⁡
E
5
≤
Adv
G
DDH
A
DDH
.Since the session key Z
0 is random, the information about c does not leak, so we have(14)
Pr
⁡
E
5
=
1
2
.According to formulas (8)–(14), the advantage can be evaluated as follows:(15)
Adv
msaa
ask
A
ask
≤
∑
i
=
1
3
q
i
2
2
λ
-
1
+
2
q
1
+
2
q
2
l
+
2
Adv
Γ
OT
t
1
,
q
0
,
q
1
,
q
2
,
q
3
+
2
Adv
G
DDH
t
2
,
q
0
,
q
1
,
q
2
,
q
3
.


## 4.1.2. Strong Anonymity for Client

To prevent the exposure of real identification during the message exchange, one practical solution is employing pseudonym. In the proposed scheme, if the adversaryA attempts to obtain the real identification of a system user, the first possible step is to obtain the key to decrypt the cihpertext C
i even if A can intercept all the transferred messages. Though A possesses T
r
A
(
x
), T
r
B
(
x
), and T
s, he or she still faces the difficulty of solving DL problem if A tries to deduce the secret value from T
A
T or T
B
T. Since A cannot decrypt C
i, he or she cannot get to know the real identification, and then the privacy of users is preserved. For the entities who get involved in the authentication, they only get the temporary identification, which is generated by the XOR operation on the real identification and random number, so that they cannot know the real identification of the partnered peer. Even if he or she stores N
i for off-line analysis in future, N
i
∗ in the next session is generated by another distinctive random number, so N
i and N
i
∗ are indistinguishable for the PPT adversary A. Furthermore, a system user entity even cannot determine whether the current partnered peer is the same with those in historic sessions or not. Thus, our proposed scheme achieves the strong anonymity successfully.


## 4.1.3. Resistance to Man-in-the-Middle Attack

Suppose there exists an active attackerA over the communication channel, who attempts to intercept and tamper the messages transferred via this channel to conduct the man-in-the-middle attack. If A tries to carry out the attack by tampering C
1, C
2, he or she will face the difficulty of solving DL problem. If A attempts to tamper or forge C
3, C
4, and C
5, he or she will face the difficulty of breaking the secure one-way hash function according to the definition of the protocol. Above all, the proposed protocol is secure enough to prevent the man-in-the-middle attack.


## 4.1.4. Resistance to Replay Attack

According to the construction of the presented protocol, all the transferred messages ofA, B, and Tread use timestamps t
A, t
B to provide freshness. Furthermore, the system users have independently chosen (x
A
,
r
A) and (x
B
,
r
B) randomly to ensure freshness at the beginning of every authentication session. So, the proposed scheme can counter replay attack effectively.


## 4.1.5. Forward Secrecy

In our scheme, the forward secrecy means the previous used session key cannot be deduced even if adversaryA is given the current session key and the password of the user. Actually, the establishment of the session key K
A
B (or K
B
A) between A and B is based on x
A and x
B chosen by themselves independently, and A cannot get anything about K
A
B (or K
B
A) because the randomness of x
A and x
B, and the success possibility will not increase even if P
W
A and P
W
B are given to the adversary.


## 4.1.6. Backward Secrecy

The backward secrecy of our scheme refers to the fact that even if the adversaryA has obtained a client’s password, all historic session keys, and current session key, could not finish authentication and key agreement. However, all the messages are transferred in anonymous way; thus, A cannot generate a valid message without knowing the real user identification according to the protocol, even if he or she is given the password P
W. So, our scheme achieves the backward secrecy.The overall comparison of security between our proposed scheme and the existing similar schemes is listed in Table1.Table 1
Comparison of security.
Scheme
Lee et al.’s [20]
Xie et al.’s [26]
Farash and Attari’s [30]
Li et al.’s [31]
Lee et al.’s [25]
Niu and Wang’s [32]
Ours
Forward secrecy
√
√
√
√
√
√
√
Backward secrecy
√
×
×
×
×
√
√
Resistance to the replay attack
√
√
√
√
√
√
√
Resistance to the MIM attack
×
√
√
√
√
√
√
Mutual anonymity
√
×
×
×
×
×
√
Strong anonymity
×
×
×
×
×
×
√All the schemes listed in Table1 have employed random number in the construction, so they all can achieve the forward secrecy. Since only our scheme and work in [20] uncover the real identification, both schemes can ensure the backward secrecy. Subsequently, all the schemes in [25, 26, 30, 31] cannot provide mutual anonymity for the same reason. Although the scheme in [20] can uncover the real identification for the outside attacker, the authenticated peers can know the real identification of each other, so that it lacks the strong anonymity, and the scheme in [32] fails to protect the identity of the server because the identity of the user is transferred in plaintext during authentication, so it cannot provide strong anonymity. For the use of timestamp and random number, all the schemes in Table 1 can counter the replay attack. However, in the scheme of [20], the attacker can choose a random number x
′ and compute R
A
′
=
T
x
′
r, and then he or she can finish the authentication successfully by blocking and injecting operation; thus, it is vulnerable to the man-in-the-middle attack.


## 4.2. Comparison of Performance

The overall performance comparison is listed in Table2.Table 2
Comparison on performance.
Scheme
Client
Server
Lee et al. [20]
6
T
H
+
6
T
C
4
T
H
+
2
T
C
Xie et al.’s [26]
6
T
H
+
6
T
C
6
T
H
+
4
T
C
Farash and Attari’s [30]
8
T
H
+
6
T
C
4
T
H
+
4
T
C
Li et al.’s [31]
4
T
H
+
8
T
C
5
T
C
Lee et al.’s [25]
9
T
H
+
2
T
E
+
2
T
D
+
7
T
C
4
T
H
+
2
T
E
+
2
T
D
+
2
T
C
Niu and Wang’s [32]
4
T
H
+
2
T
E
+
2
T
D
+
4
T
C
2
T
E
+
2
T
D
Ours
7
T
H
+
2
T
E
+
6
T
C
3
T
H
+
2
T
D
+
2
T
CAs the authentication is a sort of synchronized process, the total computational cost of the client and server in a whole authentication and key agreement should be investigated. Since the cost of XOR operation and module addition are much cheaper, these two operations are not included in comparison, and only symmetric encryption/decryption operation, chaotic map operation, and hash operations are evaluated. Although no much advantage of performance is won in the proposed scheme, its critical privacy preserving feature deserves it.


## 4.3. Application Prospects

Our proposed scheme can be applied to privacy-sensitive situations, such as VANETs [29]. Consider an authentication scenario in VANETs as shown in Figure 2. Since the communication via wireless channel, the system is susceptible to attack from outside and inside adversaries. When the driver of vehicle A detects that another vehicle B nearby is sharing some resources, he becomes interested in using the application installed in his vehicle, he then issues a request of accessing the data. On one hand, for security, A is not allowed to access B’s data directly, and B would firstly verify whether A is an authentic entity. However, A and B are unwilling to reveal their real identities to each other. Then, A and B have to proceed with a mutual anonymous authentication protocol. Meanwhile, A and B also want to keep themselves anonymous even if they authenticate each other again in the future, since few drivers like to expose their trace to other untrusted entities.Figure 2
Authentication in VANETs.On the other hand, the real identities ofA and B including the transferred messages should be kept confidential to any external entities, and any external attacker is not allowed to distinguish users from two different sessions using all intercepted messages. However, our proposed protocol can achieve all goals stated previously. Since the road side unit (RSU) is supposed to be trusted, then it can be regarded as the trusted server in our protocol, and then vehicle A and B can fulfill authentication via RSU by following the steps as defined in Section 3.


## 5. Conclusions

Of all the existing chaotic map based authentication schemes, most of them neglect the anonymity of the user. Since the privacy preservation in cryptographic systems has become a great concern nowadays, it is necessary to take the appropriate measures to address this problem. Thus, an extended Chebyshev chaotic map-based mutual authentication scheme with strong anonymity is investigated in this paper, in which the outside attacker, even the authenticated peers, cannot determine the real identity of others. The strong anonymity feature of the proposed scheme is suitable for the privacy sensible applications, such as mobile social networks, vehicle ad hoc networks.



---

*Source: 3916942-2016-04-14.xml*