# Privacy-Preserving Two-Factor Key Agreement Protocol Based on Chebyshev Polynomials

Authors: Zuowen Tan
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Two-factor authentication is one of the widely used approaches to allow a user to keep a weak password and establish a key shared with a server. Recently, a large number of chaotic maps-based authentication mechanisms have been proposed. However, since the Diffie–Hellman problem of the Chebyshev polynomials defined on the interval [−1,+1] can be solved by Bergamo et al.’s method, most of the secure chaotic maps-based key agreement protocols utilize the enhanced Chebyshev polynomials defined on the interval (−∞,+∞). Thus far, few authenticated key agreement protocols based on chaotic maps have been able to achieve user unlinkability. In this paper, we take the ﬁrst step in addressing this problem. More speciﬁcally, we propose the notions of privacy in authenticated key agreement protocols: anonymity-alone, weak unlinkability, medium unlinkability, and strong unlinkability. Then, we construct two two-factor authentication schemes with medium unlinkability based on Chebyshev polynomials defined on the interval [−1,1] and (−∞,+∞), respectively. We do the formal security analysis of the proposed schemes under the random oracle model. In addition, the proposed protocols satisfy all known security requirements in practical applications. By using Burrows-Abadi-Needham logic (BAN-logic) nonce verification, we demonstrate that the proposed schemes achieve secure authentication. In addition, the detailed comparative security and performance analysis shows that the proposed schemes enable the same functionality but improve the security level.


---

## Body

## 1. Introduction

User authentication is indispensable for many information systems. Authenticated key agreement enables users to establish a session key which two or more parties share over a public channel. The session keys are adopted in subsequent secure communications. Password, hard-ware, and biometrics are always utilized in authentication mechanisms [1–3]. Single-factor authentication only provides limited security; then, the combination of these methods together can achieve higher security. Due to the convenient portability of smart cards, two-factor authentication [4–6] has been intensively investigated.In general, user privacy protection during authenticated key exchange is a big challenge. For two-factor authentication schemes, the important issues should be addressed carefully. Firstly, the authentication mechanism should hide the user’s identity from any eavesdroppers and foreign servers. In other words, mutual authentication cannot reveal the real identity of the user, which is the basic goal of privacy protection, called anonymity. Secondly, the other aspect of user privacy protection is unlinkability. In many applications, the authentication mechanism should hide the user’s movements from any eavesdroppers and other foreign servers. Any unauthorized entity cannot track the user’s movements. Even if any outside adversary has accessed the message transmitted between the user and the server, it still cannot link the user to different authentication sessions.Since chaotic maps provide the semigroup property and have higher efficiency than modular exponential operations and scalar multiplications on an elliptic curve, many chaotic, map-based, two-factor authenticated key agreement protocols [7–12] have been developed in recent years. Thus far, the user privacy preserving chaotic maps-based authenticated key agreement protocols have been intensively investigated [13–17].


### 1.1. Motivation

In two-factor authenticated key agreement protocols, the user privacy must be considered carefully. The basic security requirement is to preserve the user anonymity, while the stricter requirement is unlinkability or untraceability. These concepts in two-factor authenticated key agreement protocols are seldom discussed in detail. Till date, few two-factor authenticated key agreement protocols can provide users with a strong unlinkability.To the best knowledge, most of the two-factor authenticated key agreements based on the Chebyshev polynomial protocols (hereafter, called TAKACP protocols) utilize the enhanced Chebyshev polynomials defined on the interval (−∞, +∞). Now, few secure TAKACP protocols are based on the Chebyshev polynomials defined on the interval [−1, +1]. This is because those TAKACP protocols based on the Chebyshev polynomials over the interval [-1,+1] are vulnerable to Bergamo et al.‘s attacks [18].


### 1.2. Our Contributions

The main contribution of this paper is the two-factor authenticated key agreement protocol based on Chebyshev polynomials defined on the interval [−1,1] and (−∞,+∞), respectively, which solve all abovementioned issues for the ﬁrst time. They satisfy more security requirements than the existing TAKACP protocols.In summary, we list the main contributions below:The user privacy in two-factor authenticated key agreement protocol is expounded. According to the extent of user identity protection, the user privacy preserving in entity authentication protocols is classified into four concepts: anonymity-alone, weak unlinkability, medium unlinkability, and strong unlinkability. Of the four levels, the strong unlinkability is the highest while the anonymity-alone is fundamental for entity authentication. In this paper, we elaborate them by the formal probability model.We analyze the Lin TAKACP protocol and reveal their weaknesses. Detailed analysis shows that it fails to provide session key security. And, it suffers from user impersonation attack. Next, it even cannot provide the weak unlinkability.Analysis of formal security under Random Oracle model and BAN logic nonce verification demonstrate that the proposed schemes provide secure authentication against the CPCDH assumption and integer factorization hardness assumption.The proposed schemes provide more security properties as compared to other TAKACP schemes. And the detailed comparative security analysis also shows that the proposed schemes avoid the weaknesses of the TAKACP protocols [19–21].


### 1.3. System Model

#### 1.3.1. Network Model

The proposed two-factor authenticated key agreement protocols involve two entities, a user U and the server S. At the user registration phase, the server issues a smart card with secret information to U through a secure channel. When the user U logs in to the server, the server and the user authenticate each other over the public channels. In this paper, the two-factor authenticated key agreement protocol is required to provide users with privacy preserving. Any adversary cannot trace the user from the message transmitted over open channels.


#### 1.3.2. Adversary Model

Consider an adversaryA who gets the full control over the communication channel between the user U and the service provider S (except the registration phase). Thus, A could obtain the messages transmitted between the user and the server (except the registration message). Of the phases in a two-factor authenticated key agreement protocol, only the registration phase requires a secure channel between U and S. In other phases, there could be various kinds of passive and active adversaries in the communication channel between U and S. The adversary A can eavesdrop and even block the message transmitted, modify messages, remove messages, or insert messages into the communication channel. Its objective is to compromise the mutual authentication between U and S. A even impersonates a user and attempts to access the server, or the adversary impersonates the server and provides the user with false services.In the single-server environment, since users register on the same server with the same master key, the inside attackerA0/A1 is very powerful. Hereinafter, we refer to a malicious server which may try to recover the password of its client or track the client as an adversary A0; a registered malicious user, or an adversary who has corrupted the user as an adversary A1; and while other adversaries are called as outside adversary A2. To simulate the inside attack, A0 and A1 can get the passwords and information stored in the smart cards of the users except those of a client under attack. If the server is the attack target, A1 is assumed to obtain the passwords and the information stored in the smart cards of all the users.For a two-factor authentication scheme, the basic security property is that the user is required to both have the smart card and know the password. Since the smart cards cannot prevent the information stored in them from being extracted, for example, by monitoring their power consumption, the security of a two-factor authentication scheme is always discussed in the case that the smart card is stolen. In other words, when a user is under attack,A is allowed to either compromise the password or the smart card of the client under attack, but not both.


### 1.4. Organization of the Paper

The remainder of this paper is organized as follows. Section2 reviews the related work. Section 3 introduces some preliminaries. Section 4 shows the limitations of the Lin protocol. Section 5 then presents two novel TAKACP protocols. Next, Section 6 analyzes the security of the proposed schemes. Comparison with the related smart-card-based protocols in terms of security properties and performance will be given in Section 7 , and Section 8 is the conclusion.


## 1.1. Motivation

In two-factor authenticated key agreement protocols, the user privacy must be considered carefully. The basic security requirement is to preserve the user anonymity, while the stricter requirement is unlinkability or untraceability. These concepts in two-factor authenticated key agreement protocols are seldom discussed in detail. Till date, few two-factor authenticated key agreement protocols can provide users with a strong unlinkability.To the best knowledge, most of the two-factor authenticated key agreements based on the Chebyshev polynomial protocols (hereafter, called TAKACP protocols) utilize the enhanced Chebyshev polynomials defined on the interval (−∞, +∞). Now, few secure TAKACP protocols are based on the Chebyshev polynomials defined on the interval [−1, +1]. This is because those TAKACP protocols based on the Chebyshev polynomials over the interval [-1,+1] are vulnerable to Bergamo et al.‘s attacks [18].


## 1.2. Our Contributions

The main contribution of this paper is the two-factor authenticated key agreement protocol based on Chebyshev polynomials defined on the interval [−1,1] and (−∞,+∞), respectively, which solve all abovementioned issues for the ﬁrst time. They satisfy more security requirements than the existing TAKACP protocols.In summary, we list the main contributions below:The user privacy in two-factor authenticated key agreement protocol is expounded. According to the extent of user identity protection, the user privacy preserving in entity authentication protocols is classified into four concepts: anonymity-alone, weak unlinkability, medium unlinkability, and strong unlinkability. Of the four levels, the strong unlinkability is the highest while the anonymity-alone is fundamental for entity authentication. In this paper, we elaborate them by the formal probability model.We analyze the Lin TAKACP protocol and reveal their weaknesses. Detailed analysis shows that it fails to provide session key security. And, it suffers from user impersonation attack. Next, it even cannot provide the weak unlinkability.Analysis of formal security under Random Oracle model and BAN logic nonce verification demonstrate that the proposed schemes provide secure authentication against the CPCDH assumption and integer factorization hardness assumption.The proposed schemes provide more security properties as compared to other TAKACP schemes. And the detailed comparative security analysis also shows that the proposed schemes avoid the weaknesses of the TAKACP protocols [19–21].


## 1.3. System Model

### 1.3.1. Network Model

The proposed two-factor authenticated key agreement protocols involve two entities, a user U and the server S. At the user registration phase, the server issues a smart card with secret information to U through a secure channel. When the user U logs in to the server, the server and the user authenticate each other over the public channels. In this paper, the two-factor authenticated key agreement protocol is required to provide users with privacy preserving. Any adversary cannot trace the user from the message transmitted over open channels.


### 1.3.2. Adversary Model

Consider an adversaryA who gets the full control over the communication channel between the user U and the service provider S (except the registration phase). Thus, A could obtain the messages transmitted between the user and the server (except the registration message). Of the phases in a two-factor authenticated key agreement protocol, only the registration phase requires a secure channel between U and S. In other phases, there could be various kinds of passive and active adversaries in the communication channel between U and S. The adversary A can eavesdrop and even block the message transmitted, modify messages, remove messages, or insert messages into the communication channel. Its objective is to compromise the mutual authentication between U and S. A even impersonates a user and attempts to access the server, or the adversary impersonates the server and provides the user with false services.In the single-server environment, since users register on the same server with the same master key, the inside attackerA0/A1 is very powerful. Hereinafter, we refer to a malicious server which may try to recover the password of its client or track the client as an adversary A0; a registered malicious user, or an adversary who has corrupted the user as an adversary A1; and while other adversaries are called as outside adversary A2. To simulate the inside attack, A0 and A1 can get the passwords and information stored in the smart cards of the users except those of a client under attack. If the server is the attack target, A1 is assumed to obtain the passwords and the information stored in the smart cards of all the users.For a two-factor authentication scheme, the basic security property is that the user is required to both have the smart card and know the password. Since the smart cards cannot prevent the information stored in them from being extracted, for example, by monitoring their power consumption, the security of a two-factor authentication scheme is always discussed in the case that the smart card is stolen. In other words, when a user is under attack,A is allowed to either compromise the password or the smart card of the client under attack, but not both.


## 1.3.1. Network Model

The proposed two-factor authenticated key agreement protocols involve two entities, a user U and the server S. At the user registration phase, the server issues a smart card with secret information to U through a secure channel. When the user U logs in to the server, the server and the user authenticate each other over the public channels. In this paper, the two-factor authenticated key agreement protocol is required to provide users with privacy preserving. Any adversary cannot trace the user from the message transmitted over open channels.


## 1.3.2. Adversary Model

Consider an adversaryA who gets the full control over the communication channel between the user U and the service provider S (except the registration phase). Thus, A could obtain the messages transmitted between the user and the server (except the registration message). Of the phases in a two-factor authenticated key agreement protocol, only the registration phase requires a secure channel between U and S. In other phases, there could be various kinds of passive and active adversaries in the communication channel between U and S. The adversary A can eavesdrop and even block the message transmitted, modify messages, remove messages, or insert messages into the communication channel. Its objective is to compromise the mutual authentication between U and S. A even impersonates a user and attempts to access the server, or the adversary impersonates the server and provides the user with false services.In the single-server environment, since users register on the same server with the same master key, the inside attackerA0/A1 is very powerful. Hereinafter, we refer to a malicious server which may try to recover the password of its client or track the client as an adversary A0; a registered malicious user, or an adversary who has corrupted the user as an adversary A1; and while other adversaries are called as outside adversary A2. To simulate the inside attack, A0 and A1 can get the passwords and information stored in the smart cards of the users except those of a client under attack. If the server is the attack target, A1 is assumed to obtain the passwords and the information stored in the smart cards of all the users.For a two-factor authentication scheme, the basic security property is that the user is required to both have the smart card and know the password. Since the smart cards cannot prevent the information stored in them from being extracted, for example, by monitoring their power consumption, the security of a two-factor authentication scheme is always discussed in the case that the smart card is stolen. In other words, when a user is under attack,A is allowed to either compromise the password or the smart card of the client under attack, but not both.


## 1.4. Organization of the Paper

The remainder of this paper is organized as follows. Section2 reviews the related work. Section 3 introduces some preliminaries. Section 4 shows the limitations of the Lin protocol. Section 5 then presents two novel TAKACP protocols. Next, Section 6 analyzes the security of the proposed schemes. Comparison with the related smart-card-based protocols in terms of security properties and performance will be given in Section 7 , and Section 8 is the conclusion.


## 2. Related Work

In this section, we brieﬂy review some prior related works. Recent years have witnessed efforts on two-factor authentication [19–42]. We summarize some existing two-factor authentication schemes with their methodologies used, limitations, and drawbacks in Table 1.Table 1
Cryptographic methodologies and drawbacks of the existing schemes and the proposed schemes.
Fan et al. [22]Juang et al. [23]Sun et al. [24]Li et al. [25]Guo et al. [19]Lin [20]Lee [21]ProposedTAKACP protocolsCryptographic methodologiesSymmetric encryption Rabin’s public-key cryptosystemSymmetric encryption ECCSymmetric encryption ECCPublic-key cryptosystem ECCSymmetric encryption chaotic map on the interval [−1,1]Symmetric encryption chaotic map on the interval [−1,1]Symmetric encryption chaotic map on the interval (−∞,+∞)Symmetric encryption, Rabin’s public-key cryptosystem chaotic map on the interval [−1,1]/( −∞,+∞)DrawbacksInsecure, no privacy preservationInsecure, no privacy preservationTraceabilityInsecure, no privacy preservationTraceabilityTraceabilityNo free password updatingNone


### 2.1. Two-Factor Authentication Based on Enhanced Chebyshev Polynomials Defined on the Interval (−∞, +∞) and Their Limitations

Researchers have developed chaotic maps-based key agreement protocols which utilize the enhanced Chebyshev polynomials defined on the interval (−∞, +∞). Xiao et al. [31] first presented a chaotic map-based authenticated key agreement protocol by utilizing the semigroup property of Chebyshev chaotic maps [32, 33]. Guo and Zhang [34] showed that the Xiao et al.’s protocol [31] cannot provide the contributory property of key agreement. A malicious server can predetermine the session key. Guo and Zhang presented an improved version [34]. However, Lee demonstrated that the Guo-Zhang protocol [34] is insecure against off-line password guessing attacks [35]. In addition, it fails to provide the session key security. Tseng et al. [7] proposed anonymous key agreement protocol based on Chebyshev chaotic maps. Unfortunately, Niu et al. [8] demonstrate that Tseng et al.’s protocol [7] fails to protect the user anonymity and suffers from inside attacks. Yoon [9] found that the Niu-Wang protocol [8] is vulnerable to Denial of Service attacks. Xue et al. [36] also improved Tseng et al.’s protocol. However, Tan [37] pointed out that the Xue-Hong protocol [36] cannot still provide user anonymity. Moreover, the Xue-Hong protocol suffers from man-in-the-middle attacks. In 2012, Gong et al. [38] proposed password-based key agreement protocol by using extended chaotic maps. Unfortunately, Wang and Luan [39] showed that the key agreement protocol [38] suffers from potential security problems.In 2014, Lin [40] developed an authentication scheme using dynamic identity and chaotic maps. Later, Islam et al. [41] state that Lin’s scheme suffers from user impersonation attack. Islam et al. also presented an improved provably secure scheme [41, 42] to solve the weaknesses of Lin’s scheme. Unluckily, Jiang et al. [10] show that Islam’s scheme is also vulnerable to some potential attacks. Based on the extended Chebyshev polynomials on the interval (−∞,+∞), Lee et al. [21] presented improvement on Lin’s scheme [20]. However, in the login phase of the improved scheme [21], the smart card fails to validate the input of the user. Moreover, in the password change phase, the server must participate in the whole updating process of each user. Hence, it is inconvenient for users to update the password in Lee et al.’s scheme [21].


### 2.2. Two-Factor Authentication Based on Enhanced Chebyshev Polynomials Defined on the Interval [−1,+1] and Their Limitations

Few secure TAKACP protocols [19–21, 35] based on the Chebyshev polynomials defined on the interval [−1,+1] have been presented.In Lee’s TAKACP scheme [35], the user and the server must preshare a password. Hence, when users register with the server, the server must share one different password with every user. In 2013, Guo and Chang [19] have proposed a smart-card-based authenticated key agreement using chaotic maps over the interval [−1,+1]. Subsequently, Hao et al. [43] and Lin [20] pointed out that that there are some security pitfalls in the Guo-Chang scheme [19]. Any adversary can derive the session key only by using the messages transmitted between a user and the server. In addition, the Guo–Chang scheme fails to provide full protection for user identity due to a fixed parameter in every run of the protocol. To eliminate the above weaknesses, Lin presents an improved scheme [20] based on chaotic maps over the interval [−1,+1]. The Lin scheme is highly efficient since it is based on a simple symmetric cryptosystem. Unfortunately, Lee et al. [21] point out that the Lin scheme still fails to withstand denial-of-service and privileged insider attacks. In addition, the Lin scheme does not exhibit the contributory property of key agreements.In this paper, we will show that the Lin scheme violates the session key security. The Lin scheme suffers from impersonation attacks. Specifically, it is still susceptible to Bergamo et al.’s attacks [44] from registered users of the same server. Furthermore, we will demonstrate that the Lin scheme cannot provide the strong privacy protection. We also have found that it is inconvenient for users to update passwords in the Lin scheme [20] and the Guo–Chang scheme [19].


## 2.1. Two-Factor Authentication Based on Enhanced Chebyshev Polynomials Defined on the Interval (−∞, +∞) and Their Limitations

Researchers have developed chaotic maps-based key agreement protocols which utilize the enhanced Chebyshev polynomials defined on the interval (−∞, +∞). Xiao et al. [31] first presented a chaotic map-based authenticated key agreement protocol by utilizing the semigroup property of Chebyshev chaotic maps [32, 33]. Guo and Zhang [34] showed that the Xiao et al.’s protocol [31] cannot provide the contributory property of key agreement. A malicious server can predetermine the session key. Guo and Zhang presented an improved version [34]. However, Lee demonstrated that the Guo-Zhang protocol [34] is insecure against off-line password guessing attacks [35]. In addition, it fails to provide the session key security. Tseng et al. [7] proposed anonymous key agreement protocol based on Chebyshev chaotic maps. Unfortunately, Niu et al. [8] demonstrate that Tseng et al.’s protocol [7] fails to protect the user anonymity and suffers from inside attacks. Yoon [9] found that the Niu-Wang protocol [8] is vulnerable to Denial of Service attacks. Xue et al. [36] also improved Tseng et al.’s protocol. However, Tan [37] pointed out that the Xue-Hong protocol [36] cannot still provide user anonymity. Moreover, the Xue-Hong protocol suffers from man-in-the-middle attacks. In 2012, Gong et al. [38] proposed password-based key agreement protocol by using extended chaotic maps. Unfortunately, Wang and Luan [39] showed that the key agreement protocol [38] suffers from potential security problems.In 2014, Lin [40] developed an authentication scheme using dynamic identity and chaotic maps. Later, Islam et al. [41] state that Lin’s scheme suffers from user impersonation attack. Islam et al. also presented an improved provably secure scheme [41, 42] to solve the weaknesses of Lin’s scheme. Unluckily, Jiang et al. [10] show that Islam’s scheme is also vulnerable to some potential attacks. Based on the extended Chebyshev polynomials on the interval (−∞,+∞), Lee et al. [21] presented improvement on Lin’s scheme [20]. However, in the login phase of the improved scheme [21], the smart card fails to validate the input of the user. Moreover, in the password change phase, the server must participate in the whole updating process of each user. Hence, it is inconvenient for users to update the password in Lee et al.’s scheme [21].


## 2.2. Two-Factor Authentication Based on Enhanced Chebyshev Polynomials Defined on the Interval [−1,+1] and Their Limitations

Few secure TAKACP protocols [19–21, 35] based on the Chebyshev polynomials defined on the interval [−1,+1] have been presented.In Lee’s TAKACP scheme [35], the user and the server must preshare a password. Hence, when users register with the server, the server must share one different password with every user. In 2013, Guo and Chang [19] have proposed a smart-card-based authenticated key agreement using chaotic maps over the interval [−1,+1]. Subsequently, Hao et al. [43] and Lin [20] pointed out that that there are some security pitfalls in the Guo-Chang scheme [19]. Any adversary can derive the session key only by using the messages transmitted between a user and the server. In addition, the Guo–Chang scheme fails to provide full protection for user identity due to a fixed parameter in every run of the protocol. To eliminate the above weaknesses, Lin presents an improved scheme [20] based on chaotic maps over the interval [−1,+1]. The Lin scheme is highly efficient since it is based on a simple symmetric cryptosystem. Unfortunately, Lee et al. [21] point out that the Lin scheme still fails to withstand denial-of-service and privileged insider attacks. In addition, the Lin scheme does not exhibit the contributory property of key agreements.In this paper, we will show that the Lin scheme violates the session key security. The Lin scheme suffers from impersonation attacks. Specifically, it is still susceptible to Bergamo et al.’s attacks [44] from registered users of the same server. Furthermore, we will demonstrate that the Lin scheme cannot provide the strong privacy protection. We also have found that it is inconvenient for users to update passwords in the Lin scheme [20] and the Guo–Chang scheme [19].


## 3. Mathematical Preliminaries

This section briefly introduces Chebyshev polynomials and two problems related to the chaotic maps. Then, we will discuss the user privacy in TAKACP protocols and define the different notions of user privacy.


### 3.1. Mathematical Preliminaries

Letn be an integer and x be a variable taking values over the interval [−1,1]. The Chebyshev polynomial Tn: [−1,1] ⟶ [−1,1] of degree n is defined as(1)Tnx=cosn⋅arccosx,x∈−1,1.The recurrence relation of the Chebyshev polynomial is given by:(2)Tnx=2xTn−1x−Tn−2x,n≥2,T0x=1,T1x=x.The cos(s) and arcos(s) are defined as cos:R⟶−1,1 and arcos: −1,1⟶0,π. There are some examples of Chebyshev polynomials that are shown as follows:(3)T2x=2x2−1,T3x=4x3−3x,T4x=8x4−82+1.The Chebyshev polynomials hold two important properties.Semigroup property: Assume thatr and s are positive numbers. For x∈−1,1, Tr(Ts(x)) = Ts(Tr(x)). Due to its semigroup property, the Chebyshev polynomials satisfy the commutative property under the composition Tr(Ts(x)) = Ts(Tr(x)).Chaotic property: Since the Chebyshev polynomialTn(x) with the positive integer n has a unique continuous invariant measure with positive Lyapunov exponent lnn, it is a chaotic map with its invariant density f∗x=1/π1−x2. Specially, T2(x) is the well-known logistic map.In 2008, Zhang [45] extended the definition of variables from the interval [−1,1] to the interval −∞,+∞ as follows:(4)Tnx=2xTn−1x−Tn−2xmodp,n≥2,where p is a large prime number. And, these enhanced Chebyshev polynomials still commute under the composition, Tr(Ts(x)) = Ts(Tr(x)) mod p.The Chebyshev polynomials over the interval−∞,+∞ have the discrete logarithm problem and Diffie-Hellman problem, which are assumed to be difficult to solve within a probabilistic polynomial time:Definition 1.
Chebyshev polynomial-based Discrete Logarithm (CPDL) problem. Given two elements x and y, find an integer r, such that Tr (x) = y, where Tr (x) is the Chebyshev polynomial.Definition 2.
Chebyshev polynomial-based computational Diffie-Hellman (CPCDH) problem. Given three elements, x, Chebyshev polynomials Tr (x), and Ts(x), compute the value Trs(x).
In contrast with the Chebyshev polynomials over the interval−∞,+∞, the hardness assumption of CPCDH problems over the interval [−1,1] does not hold. Given three elements, x, Tr(x), and Ts(x), although it is computationally infeasible to derive r from the known x and Tr (x), one can apply the method mentioned in [18, 44] to derive(5)r∗=arccosTrx+2kπarccosx|k∈Z,such that Trx=Tr∗x. Thus, one can compute the Diffie-Hellman value Tr∗Tsx=TsTr∗x=TsTrx.Definition 3.
The success probability of a probabilistic polynomial time Turing machineΔ within time upper bound t in solving CPCDH problems is defined as:(6)AdvCPCDHt=PrΔTrx,Tsx=Trsx.Definition 4.
The Chebyshev polynomial-based computational Diffie-Hellman assumption (CPCDH assumption) is the assumption that CPCDH problems are hard. In other words, for every probabilistic Turing machine Δ, AdvCPCDHt is negligible.Definition 5.
Integer factorization assumption (IF assumption) is the assumption that integer factorization is hard. In other words, the probability AdvIFt′ of integer factorization for any probabilistic polynomial time Turing machine within the time upper bound t’ is negligible.


### 3.2. Notions of Privacy in TAKACP Protocols

According to the extent of user identity protection, we divide user privacy preserving into four levels: anonymity-alone, weak unlinkability, medium unlinkability, and strong unlinkability. Among these concepts, the latter is stronger than the former, i.e., anonymity-alone ≤ weak unlinkability ≤ medium unlinkability ≤ strong unlinkability.LetN be the number of members of any user group. Let A1,2Guess be the event that A (that is, A1 and A2 but A0) guesses the identity of the user correctly from the user group, A2DecideADecide be the event that A2(A) decides whether any two executions of the protocol are from the same user, respectively.Definition 6.
(Anonymity-Alone). We define the advantage AdvAnon−Alone(A) of any adversary A as(7)AdvAnon−AloneA=PrA1,2Guess−1N+PrA2Decide−1.
The advantage AdvAnon−Alone(A) measures the sum of the probability of any adversary A1 or any outside adversary A2 obtaining the identity of the user and the probability of any outside adversary A2 linking different sessions with a certain user.
An authenticated key agreement protocol is called to provide Anonymity-Alone if AdvAnon-Alone(A) is negligible. In other words, for any group of N users, A cannot identify the actual user with the probability higher than the probability 1/N of guessing. Hence, the first addition item would approach 0. However, any outside adversary A2 can link different sessions to a certain user.Definition 7.
(weak unlinkability). We define the advantage AdvWeak−Unlin(A) of any adversary A as(8)AdvWeak−UnlinA=PrA1,2Guess−1N+PrA2Decide−12.
An authenticated key agreement scheme achieves weak unlinkability if AdvWeak-Unlin(A) is negligible. Specifically, any adversary A1 or any outside adversary A2 cannot obtain the identity of any other user. Besides, any outside adversary A2 cannot link different sessions to a certain user with a probability larger than 1/2.Definition 8.
(medium unlinkability). We define the advantage Advmedium−Unlin(A) of any adversary A (here, A1 and A2 but A0) as(9)AdvMedium−UnlinA=PrA1,2Decide−12.
An authenticated key agreement scheme is called to satisfy medium unlinkability if AdvMedium-Unlin(A) is negligible. In other words, any participant except the server cannot link different logins to the same user.Definition 9.
(strong unlinkability). We define the advantage AdvStrong−Unlin(A) of any adversary A including A0, A1, and A2 as(10)AdvStrong−UnlinA=PrADecide−12.
An authenticated key agreement scheme is called to satisfy strong unlinkability if AdvStrong−Unlin(A) is negligible.


## 3.1. Mathematical Preliminaries

Letn be an integer and x be a variable taking values over the interval [−1,1]. The Chebyshev polynomial Tn: [−1,1] ⟶ [−1,1] of degree n is defined as(1)Tnx=cosn⋅arccosx,x∈−1,1.The recurrence relation of the Chebyshev polynomial is given by:(2)Tnx=2xTn−1x−Tn−2x,n≥2,T0x=1,T1x=x.The cos(s) and arcos(s) are defined as cos:R⟶−1,1 and arcos: −1,1⟶0,π. There are some examples of Chebyshev polynomials that are shown as follows:(3)T2x=2x2−1,T3x=4x3−3x,T4x=8x4−82+1.The Chebyshev polynomials hold two important properties.Semigroup property: Assume thatr and s are positive numbers. For x∈−1,1, Tr(Ts(x)) = Ts(Tr(x)). Due to its semigroup property, the Chebyshev polynomials satisfy the commutative property under the composition Tr(Ts(x)) = Ts(Tr(x)).Chaotic property: Since the Chebyshev polynomialTn(x) with the positive integer n has a unique continuous invariant measure with positive Lyapunov exponent lnn, it is a chaotic map with its invariant density f∗x=1/π1−x2. Specially, T2(x) is the well-known logistic map.In 2008, Zhang [45] extended the definition of variables from the interval [−1,1] to the interval −∞,+∞ as follows:(4)Tnx=2xTn−1x−Tn−2xmodp,n≥2,where p is a large prime number. And, these enhanced Chebyshev polynomials still commute under the composition, Tr(Ts(x)) = Ts(Tr(x)) mod p.The Chebyshev polynomials over the interval−∞,+∞ have the discrete logarithm problem and Diffie-Hellman problem, which are assumed to be difficult to solve within a probabilistic polynomial time:Definition 1.
Chebyshev polynomial-based Discrete Logarithm (CPDL) problem. Given two elements x and y, find an integer r, such that Tr (x) = y, where Tr (x) is the Chebyshev polynomial.Definition 2.
Chebyshev polynomial-based computational Diffie-Hellman (CPCDH) problem. Given three elements, x, Chebyshev polynomials Tr (x), and Ts(x), compute the value Trs(x).
In contrast with the Chebyshev polynomials over the interval−∞,+∞, the hardness assumption of CPCDH problems over the interval [−1,1] does not hold. Given three elements, x, Tr(x), and Ts(x), although it is computationally infeasible to derive r from the known x and Tr (x), one can apply the method mentioned in [18, 44] to derive(5)r∗=arccosTrx+2kπarccosx|k∈Z,such that Trx=Tr∗x. Thus, one can compute the Diffie-Hellman value Tr∗Tsx=TsTr∗x=TsTrx.Definition 3.
The success probability of a probabilistic polynomial time Turing machineΔ within time upper bound t in solving CPCDH problems is defined as:(6)AdvCPCDHt=PrΔTrx,Tsx=Trsx.Definition 4.
The Chebyshev polynomial-based computational Diffie-Hellman assumption (CPCDH assumption) is the assumption that CPCDH problems are hard. In other words, for every probabilistic Turing machine Δ, AdvCPCDHt is negligible.Definition 5.
Integer factorization assumption (IF assumption) is the assumption that integer factorization is hard. In other words, the probability AdvIFt′ of integer factorization for any probabilistic polynomial time Turing machine within the time upper bound t’ is negligible.


## 3.2. Notions of Privacy in TAKACP Protocols

According to the extent of user identity protection, we divide user privacy preserving into four levels: anonymity-alone, weak unlinkability, medium unlinkability, and strong unlinkability. Among these concepts, the latter is stronger than the former, i.e., anonymity-alone ≤ weak unlinkability ≤ medium unlinkability ≤ strong unlinkability.LetN be the number of members of any user group. Let A1,2Guess be the event that A (that is, A1 and A2 but A0) guesses the identity of the user correctly from the user group, A2DecideADecide be the event that A2(A) decides whether any two executions of the protocol are from the same user, respectively.Definition 6.
(Anonymity-Alone). We define the advantage AdvAnon−Alone(A) of any adversary A as(7)AdvAnon−AloneA=PrA1,2Guess−1N+PrA2Decide−1.
The advantage AdvAnon−Alone(A) measures the sum of the probability of any adversary A1 or any outside adversary A2 obtaining the identity of the user and the probability of any outside adversary A2 linking different sessions with a certain user.
An authenticated key agreement protocol is called to provide Anonymity-Alone if AdvAnon-Alone(A) is negligible. In other words, for any group of N users, A cannot identify the actual user with the probability higher than the probability 1/N of guessing. Hence, the first addition item would approach 0. However, any outside adversary A2 can link different sessions to a certain user.Definition 7.
(weak unlinkability). We define the advantage AdvWeak−Unlin(A) of any adversary A as(8)AdvWeak−UnlinA=PrA1,2Guess−1N+PrA2Decide−12.
An authenticated key agreement scheme achieves weak unlinkability if AdvWeak-Unlin(A) is negligible. Specifically, any adversary A1 or any outside adversary A2 cannot obtain the identity of any other user. Besides, any outside adversary A2 cannot link different sessions to a certain user with a probability larger than 1/2.Definition 8.
(medium unlinkability). We define the advantage Advmedium−Unlin(A) of any adversary A (here, A1 and A2 but A0) as(9)AdvMedium−UnlinA=PrA1,2Decide−12.
An authenticated key agreement scheme is called to satisfy medium unlinkability if AdvMedium-Unlin(A) is negligible. In other words, any participant except the server cannot link different logins to the same user.Definition 9.
(strong unlinkability). We define the advantage AdvStrong−Unlin(A) of any adversary A including A0, A1, and A2 as(10)AdvStrong−UnlinA=PrADecide−12.
An authenticated key agreement scheme is called to satisfy strong unlinkability if AdvStrong−Unlin(A) is negligible.


## 4. Cryptanalysis of the Lin Takacp Protocol

In this section, we first tabulate the important notations in Table2. We then review Lin’s key agreement protocol [20].Table 2
The notations.
SymbolDescriptionSThe serverUA userPWU’s passwordIDU’s identitysThe master key of the serverxA variable with value in [−1,1]⊕Exclusive-OR operationh()A one-way hash function||String concatenationT1, T2, T3The timestampstA random integerSKSession keyEk()Symmetric encryption algorithm withkDk()Symmetric decryption algorithm withk


### 4.1. Brief Review of Lin’s Takacp Protocol

The Lin’s TAKACP scheme [20] is composed of four algorithms: system initialization, user registration, authenticated key exchange, and password change. The notations used in [20] are listed in Table 2. Figures 1–3 separately illustrate the phases of user registration, authenticated key exchange, and password change.Figure 1
User registration phase of the Lin protocol.Figure 2
Authenticated key exchange phase of the Lin protocol.Figure 3
Password change phase of the Lin protocol.


#### 4.1.1. System Initialization

The server S selects a master keys. Then, S computes a Chebyshev polynomial of degree r, i.e., Tr(x), where x∈−1,1, and chooses a one-way hash function h() and a symmetric encryption function Ek() with the secret key k. S keeps r secret.


#### 4.1.2. User Registration Phase

A user registration procedure consists of the following steps.Step 1. The user U selects an identity ID, a password PW, and a random integer t. U computes H = h(PW||t) and then sends the message {ID, H} to the server via a secure channel.Step 2. Upon receiving the registration request, the server S computes R = Es(ID||H), D = H⊕(x||Tr(x)). Then, S writes {R, h(), Ek(), D} to a smart card and sends the smart card to U via a secure channel.Step 3. Upon receiving the smart card, U stores t into it.


#### 4.1.3. Authenticated Key Exchange Phase

U first enters the identityID and password PW. Then, the smart card runs the following steps on S:Step 1. It chooses a random integerj and computes(11)xTrx=D⊕hPWt,v=TjTrx,Q=hIDH.Then, it issues the messageTjx,EvQ,R,T1 to S.Step 2. S computes v=TrTjx and decrypts EvQ,R,T1. Then, S checks the validity of the time stamp T1. Next, S decrypts R and verifies whether Q=hID′H′ holds. If the equation holds, U is authenticated; otherwise, the session is terminated.Step 3. S chooses a random integer j′and returns the login response EvTj′x,hID′T2 to the card. And, S computes session key Tj′Tjx.Step 4. The card first decrypts EvTj′x,hID′T2 and then checks whether the delay time for T2 is acceptable. Next, the card checks whether hIDT2=hID′T2 holds. If the equation holds, S is authenticated. And, the card computes the session key TjTj′x.


#### 4.1.4. Password Change Phase

U first inserts the smart card into a terminal and inputs his or her identityID, the old password PW, and a new password PW∗. Then, the smart card runs the following steps on S:Step 1. The smart card chooses randomly a positive integer i and calculates(12)H′=hPWt,xTrx=D⊕H′,η=TiTrx,H∗=hPW∗t,and deliversTix,EηH′,H∗,R to S.Step 2. S computes η=TrTix, then decrypts EηH′,H∗,R and further R = Es(ID||H). Next, S checks whether the received H′ is equal to H. If the equation holds, the server returns R∗=EsIDH∗ to the card.Step 3. The smart card replaces R with R∗.


### 4.2. Security Weaknesses of Lin’s TAKACP Protocol

Lin [20] demonstrates that the Guo-Chang TAKACP scheme [19] cannot provide full protection for the user’s identity. Any passive inside adversary A1 (i.e., a malicious registered user) could derive the mutually shared session key between the user and the server only by intercepting the transmitted message. Lin claimed that their improvement eliminates the drawbacks. We show that the second security weakness of the Guo-Chang TAKACP scheme still exists in the Lin scheme [20]. In addition, the password change would not only bring inconvenience to the user but also lack the authentication of the server.


#### 4.2.1. Violation of the Session Key Security

Assume that an inside adversaryA1 has intercepted the key exchange message transmitted between the user U and the server. In the Lin scheme, the adversary could derive the session key by performing the following steps.SinceA1 is an inside adversary, A1 can use his password to calculate x||Tr(x). After intercepting U’s login message Tjx,EvQ,R,T1, A1 has obtained Tj(x). Although it is computationally infeasible to calculate j from x and Tj(x), the adversary can apply the method mentioned in [18, 44] to compute(13)j∗=arccosTjx+2kπarccosx|k∈Z,such that Tjx=Tj∗x. Then, the adversary could compute the key v=Tj∗Trx=TrTj∗x=TrTjx.A1 decrypts EvTj′x,hID′T2 with the key v and obtains Tj′x. Finally, the adversary calculates the session key SK=Tj∗Tj′x=Tj′Tj∗x=Tj′Tjx.


#### 4.2.2. Suffering from User Impersonation Attack

Suppose that an inside adversaryA1 does not want to pay the server for the service provided by S. A1 would try to impersonate a legitimate user U. After intercepting U’s login message, the adversary launches the user impersonation attack as described below:(1)
With the login messageTjx,EvQ,R,T1, A1 computes the key v through the same technique as in the leakage attack of the session key in Section 3. Then, A1 decrypts EvQ,R,T1 and obtains {Q, R, T1}.(2)
A1 chooses a random integer j and computes v=TjTrx. It transmits Tjx,EvQ,R,T1 to the server S, where T is the current timestamp.(3)
After receiving the login message,S computes v=TrTjx and decrypts EvQ,R,T. S first checks the validity of the time stamp T. Next, S decrypts R to derive ID||H, and verifies the identity. Since Q = h(ID||H), the server believes that a legitimate user with ID has issued the login request. After that, S selects a Chebyshev polynomial Tj′x, encrypts it with other messages, and transmits the cipher-text to A1.(4)
A1 recovers the map Tj′x with the key v and computes the session key.


#### 4.2.3. Linking Different Sessions to a Same User

The Lin’s TAKACP scheme enhances the protection of user identity. Although any adversaryA1 or A2 cannot obtain the identity of any user, any inside adversary A1 can link different sessions to a certain user. The Lin scheme only can provide weak unlinkablity (for details, see Definition 7 in Section 3), since A1 may execute the linking of sessions to the user as follows.(1)
Intercept the different login messagesTjx,EvQ,R,T1.(2)
Compute the different keysv through the approach described in Section 3.(3)
DecryptEvQ,R,T1 and obtain {Q, R, T1}. For the user, although the parameters {R, T1} change with different logins, Q will be unchanged. Thus, A1 can decide whether the users are the same by comparing the parameter Q’s.


#### 4.2.4. Defects of the Password Change

Firstly, the password change suffers from inside attacks. Consider that a registered userU′ acts as an adversary A1. Since U′ is a registered user of the server S, U′ can derive x||Tr(x) from his own D′,H′ by using his own password. Assume that U′ has intercepted U’s password change request Tix,EηH′,H∗,R. As shown above, U′ can calculate i∗=arccosTix+2kπ/arccosxk∈Z, which satisfies the equation Tix=Ti∗x. Thus, U′ computes the key η and further decrypts EηH′,H∗,R. Then, U′ selects randomly a value H″ of the same length of H∗. And U′ computes EηH′,H″,R and sends Tix,EηH′,H″,R to the server. Since the equation H′=H holds, the server will return R∗=EsID‖H″ to the smart card. The smart card stores R∗instead of R. Thus, the password change has been fulfilled. However, the user U cannot login to the server any more with the new password PW∗. We describe the failure process as follows. When the user U tries to login to S, U computes Q=hID‖H∗ where H∗=hPW∗‖t and then issues Tjx,EvQ,R∗,T1 to the server. The server decrypts EvQ,R∗,T1 and acquires R∗. S further decrypts R∗ to obtain ID,H″. S computes Q′=hID‖H″. Since Q′≠Q, the server will refuse U’s login request.Secondly, the Lin’s TAKACP scheme requires that the server participate during the whole password change phase. In many applications, registered users always need to update their passwords at intervals. Passwords should be freely updated by the smart card holder at will without any interaction with the server, while the server can be totally unaware of the password change. A TAKACP scheme should provide the users with free password changes. If the users’ password change requires the server online, it must be a bottleneck. The Lin scheme requires the server S to computeR∗ during the password change phase. Therefore, it is inconvenient to both the server and the users. For the Lin scheme, the password change is impractical.Thirdly, during the password change phase, the server is not authenticated by the smart card. This would be a serious security drawback. Any adversary could impersonate the server and send an arbitrary value asR∗. The smart card will replace R with R∗. The real card holder cannot login to the server any longer since R∗≠EsID‖H∗. If the password change proceeds through a secure channel as in the user registration phase, the above security drawbacks will be removed. However, this is also infeasible.


## 4.1. Brief Review of Lin’s Takacp Protocol

The Lin’s TAKACP scheme [20] is composed of four algorithms: system initialization, user registration, authenticated key exchange, and password change. The notations used in [20] are listed in Table 2. Figures 1–3 separately illustrate the phases of user registration, authenticated key exchange, and password change.Figure 1
User registration phase of the Lin protocol.Figure 2
Authenticated key exchange phase of the Lin protocol.Figure 3
Password change phase of the Lin protocol.


### 4.1.1. System Initialization

The server S selects a master keys. Then, S computes a Chebyshev polynomial of degree r, i.e., Tr(x), where x∈−1,1, and chooses a one-way hash function h() and a symmetric encryption function Ek() with the secret key k. S keeps r secret.


### 4.1.2. User Registration Phase

A user registration procedure consists of the following steps.Step 1. The user U selects an identity ID, a password PW, and a random integer t. U computes H = h(PW||t) and then sends the message {ID, H} to the server via a secure channel.Step 2. Upon receiving the registration request, the server S computes R = Es(ID||H), D = H⊕(x||Tr(x)). Then, S writes {R, h(), Ek(), D} to a smart card and sends the smart card to U via a secure channel.Step 3. Upon receiving the smart card, U stores t into it.


### 4.1.3. Authenticated Key Exchange Phase

U first enters the identityID and password PW. Then, the smart card runs the following steps on S:Step 1. It chooses a random integerj and computes(11)xTrx=D⊕hPWt,v=TjTrx,Q=hIDH.Then, it issues the messageTjx,EvQ,R,T1 to S.Step 2. S computes v=TrTjx and decrypts EvQ,R,T1. Then, S checks the validity of the time stamp T1. Next, S decrypts R and verifies whether Q=hID′H′ holds. If the equation holds, U is authenticated; otherwise, the session is terminated.Step 3. S chooses a random integer j′and returns the login response EvTj′x,hID′T2 to the card. And, S computes session key Tj′Tjx.Step 4. The card first decrypts EvTj′x,hID′T2 and then checks whether the delay time for T2 is acceptable. Next, the card checks whether hIDT2=hID′T2 holds. If the equation holds, S is authenticated. And, the card computes the session key TjTj′x.


### 4.1.4. Password Change Phase

U first inserts the smart card into a terminal and inputs his or her identityID, the old password PW, and a new password PW∗. Then, the smart card runs the following steps on S:Step 1. The smart card chooses randomly a positive integer i and calculates(12)H′=hPWt,xTrx=D⊕H′,η=TiTrx,H∗=hPW∗t,and deliversTix,EηH′,H∗,R to S.Step 2. S computes η=TrTix, then decrypts EηH′,H∗,R and further R = Es(ID||H). Next, S checks whether the received H′ is equal to H. If the equation holds, the server returns R∗=EsIDH∗ to the card.Step 3. The smart card replaces R with R∗.


## 4.1.1. System Initialization

The server S selects a master keys. Then, S computes a Chebyshev polynomial of degree r, i.e., Tr(x), where x∈−1,1, and chooses a one-way hash function h() and a symmetric encryption function Ek() with the secret key k. S keeps r secret.


## 4.1.2. User Registration Phase

A user registration procedure consists of the following steps.Step 1. The user U selects an identity ID, a password PW, and a random integer t. U computes H = h(PW||t) and then sends the message {ID, H} to the server via a secure channel.Step 2. Upon receiving the registration request, the server S computes R = Es(ID||H), D = H⊕(x||Tr(x)). Then, S writes {R, h(), Ek(), D} to a smart card and sends the smart card to U via a secure channel.Step 3. Upon receiving the smart card, U stores t into it.


## 4.1.3. Authenticated Key Exchange Phase

U first enters the identityID and password PW. Then, the smart card runs the following steps on S:Step 1. It chooses a random integerj and computes(11)xTrx=D⊕hPWt,v=TjTrx,Q=hIDH.Then, it issues the messageTjx,EvQ,R,T1 to S.Step 2. S computes v=TrTjx and decrypts EvQ,R,T1. Then, S checks the validity of the time stamp T1. Next, S decrypts R and verifies whether Q=hID′H′ holds. If the equation holds, U is authenticated; otherwise, the session is terminated.Step 3. S chooses a random integer j′and returns the login response EvTj′x,hID′T2 to the card. And, S computes session key Tj′Tjx.Step 4. The card first decrypts EvTj′x,hID′T2 and then checks whether the delay time for T2 is acceptable. Next, the card checks whether hIDT2=hID′T2 holds. If the equation holds, S is authenticated. And, the card computes the session key TjTj′x.


## 4.1.4. Password Change Phase

U first inserts the smart card into a terminal and inputs his or her identityID, the old password PW, and a new password PW∗. Then, the smart card runs the following steps on S:Step 1. The smart card chooses randomly a positive integer i and calculates(12)H′=hPWt,xTrx=D⊕H′,η=TiTrx,H∗=hPW∗t,and deliversTix,EηH′,H∗,R to S.Step 2. S computes η=TrTix, then decrypts EηH′,H∗,R and further R = Es(ID||H). Next, S checks whether the received H′ is equal to H. If the equation holds, the server returns R∗=EsIDH∗ to the card.Step 3. The smart card replaces R with R∗.


## 4.2. Security Weaknesses of Lin’s TAKACP Protocol

Lin [20] demonstrates that the Guo-Chang TAKACP scheme [19] cannot provide full protection for the user’s identity. Any passive inside adversary A1 (i.e., a malicious registered user) could derive the mutually shared session key between the user and the server only by intercepting the transmitted message. Lin claimed that their improvement eliminates the drawbacks. We show that the second security weakness of the Guo-Chang TAKACP scheme still exists in the Lin scheme [20]. In addition, the password change would not only bring inconvenience to the user but also lack the authentication of the server.


### 4.2.1. Violation of the Session Key Security

Assume that an inside adversaryA1 has intercepted the key exchange message transmitted between the user U and the server. In the Lin scheme, the adversary could derive the session key by performing the following steps.SinceA1 is an inside adversary, A1 can use his password to calculate x||Tr(x). After intercepting U’s login message Tjx,EvQ,R,T1, A1 has obtained Tj(x). Although it is computationally infeasible to calculate j from x and Tj(x), the adversary can apply the method mentioned in [18, 44] to compute(13)j∗=arccosTjx+2kπarccosx|k∈Z,such that Tjx=Tj∗x. Then, the adversary could compute the key v=Tj∗Trx=TrTj∗x=TrTjx.A1 decrypts EvTj′x,hID′T2 with the key v and obtains Tj′x. Finally, the adversary calculates the session key SK=Tj∗Tj′x=Tj′Tj∗x=Tj′Tjx.


### 4.2.2. Suffering from User Impersonation Attack

Suppose that an inside adversaryA1 does not want to pay the server for the service provided by S. A1 would try to impersonate a legitimate user U. After intercepting U’s login message, the adversary launches the user impersonation attack as described below:(1)
With the login messageTjx,EvQ,R,T1, A1 computes the key v through the same technique as in the leakage attack of the session key in Section 3. Then, A1 decrypts EvQ,R,T1 and obtains {Q, R, T1}.(2)
A1 chooses a random integer j and computes v=TjTrx. It transmits Tjx,EvQ,R,T1 to the server S, where T is the current timestamp.(3)
After receiving the login message,S computes v=TrTjx and decrypts EvQ,R,T. S first checks the validity of the time stamp T. Next, S decrypts R to derive ID||H, and verifies the identity. Since Q = h(ID||H), the server believes that a legitimate user with ID has issued the login request. After that, S selects a Chebyshev polynomial Tj′x, encrypts it with other messages, and transmits the cipher-text to A1.(4)
A1 recovers the map Tj′x with the key v and computes the session key.


### 4.2.3. Linking Different Sessions to a Same User

The Lin’s TAKACP scheme enhances the protection of user identity. Although any adversaryA1 or A2 cannot obtain the identity of any user, any inside adversary A1 can link different sessions to a certain user. The Lin scheme only can provide weak unlinkablity (for details, see Definition 7 in Section 3), since A1 may execute the linking of sessions to the user as follows.(1)
Intercept the different login messagesTjx,EvQ,R,T1.(2)
Compute the different keysv through the approach described in Section 3.(3)
DecryptEvQ,R,T1 and obtain {Q, R, T1}. For the user, although the parameters {R, T1} change with different logins, Q will be unchanged. Thus, A1 can decide whether the users are the same by comparing the parameter Q’s.


### 4.2.4. Defects of the Password Change

Firstly, the password change suffers from inside attacks. Consider that a registered userU′ acts as an adversary A1. Since U′ is a registered user of the server S, U′ can derive x||Tr(x) from his own D′,H′ by using his own password. Assume that U′ has intercepted U’s password change request Tix,EηH′,H∗,R. As shown above, U′ can calculate i∗=arccosTix+2kπ/arccosxk∈Z, which satisfies the equation Tix=Ti∗x. Thus, U′ computes the key η and further decrypts EηH′,H∗,R. Then, U′ selects randomly a value H″ of the same length of H∗. And U′ computes EηH′,H″,R and sends Tix,EηH′,H″,R to the server. Since the equation H′=H holds, the server will return R∗=EsID‖H″ to the smart card. The smart card stores R∗instead of R. Thus, the password change has been fulfilled. However, the user U cannot login to the server any more with the new password PW∗. We describe the failure process as follows. When the user U tries to login to S, U computes Q=hID‖H∗ where H∗=hPW∗‖t and then issues Tjx,EvQ,R∗,T1 to the server. The server decrypts EvQ,R∗,T1 and acquires R∗. S further decrypts R∗ to obtain ID,H″. S computes Q′=hID‖H″. Since Q′≠Q, the server will refuse U’s login request.Secondly, the Lin’s TAKACP scheme requires that the server participate during the whole password change phase. In many applications, registered users always need to update their passwords at intervals. Passwords should be freely updated by the smart card holder at will without any interaction with the server, while the server can be totally unaware of the password change. A TAKACP scheme should provide the users with free password changes. If the users’ password change requires the server online, it must be a bottleneck. The Lin scheme requires the server S to computeR∗ during the password change phase. Therefore, it is inconvenient to both the server and the users. For the Lin scheme, the password change is impractical.Thirdly, during the password change phase, the server is not authenticated by the smart card. This would be a serious security drawback. Any adversary could impersonate the server and send an arbitrary value asR∗. The smart card will replace R with R∗. The real card holder cannot login to the server any longer since R∗≠EsID‖H∗. If the password change proceeds through a secure channel as in the user registration phase, the above security drawbacks will be removed. However, this is also infeasible.


## 4.2.1. Violation of the Session Key Security

Assume that an inside adversaryA1 has intercepted the key exchange message transmitted between the user U and the server. In the Lin scheme, the adversary could derive the session key by performing the following steps.SinceA1 is an inside adversary, A1 can use his password to calculate x||Tr(x). After intercepting U’s login message Tjx,EvQ,R,T1, A1 has obtained Tj(x). Although it is computationally infeasible to calculate j from x and Tj(x), the adversary can apply the method mentioned in [18, 44] to compute(13)j∗=arccosTjx+2kπarccosx|k∈Z,such that Tjx=Tj∗x. Then, the adversary could compute the key v=Tj∗Trx=TrTj∗x=TrTjx.A1 decrypts EvTj′x,hID′T2 with the key v and obtains Tj′x. Finally, the adversary calculates the session key SK=Tj∗Tj′x=Tj′Tj∗x=Tj′Tjx.


## 4.2.2. Suffering from User Impersonation Attack

Suppose that an inside adversaryA1 does not want to pay the server for the service provided by S. A1 would try to impersonate a legitimate user U. After intercepting U’s login message, the adversary launches the user impersonation attack as described below:(1)
With the login messageTjx,EvQ,R,T1, A1 computes the key v through the same technique as in the leakage attack of the session key in Section 3. Then, A1 decrypts EvQ,R,T1 and obtains {Q, R, T1}.(2)
A1 chooses a random integer j and computes v=TjTrx. It transmits Tjx,EvQ,R,T1 to the server S, where T is the current timestamp.(3)
After receiving the login message,S computes v=TrTjx and decrypts EvQ,R,T. S first checks the validity of the time stamp T. Next, S decrypts R to derive ID||H, and verifies the identity. Since Q = h(ID||H), the server believes that a legitimate user with ID has issued the login request. After that, S selects a Chebyshev polynomial Tj′x, encrypts it with other messages, and transmits the cipher-text to A1.(4)
A1 recovers the map Tj′x with the key v and computes the session key.


## 4.2.3. Linking Different Sessions to a Same User

The Lin’s TAKACP scheme enhances the protection of user identity. Although any adversaryA1 or A2 cannot obtain the identity of any user, any inside adversary A1 can link different sessions to a certain user. The Lin scheme only can provide weak unlinkablity (for details, see Definition 7 in Section 3), since A1 may execute the linking of sessions to the user as follows.(1)
Intercept the different login messagesTjx,EvQ,R,T1.(2)
Compute the different keysv through the approach described in Section 3.(3)
DecryptEvQ,R,T1 and obtain {Q, R, T1}. For the user, although the parameters {R, T1} change with different logins, Q will be unchanged. Thus, A1 can decide whether the users are the same by comparing the parameter Q’s.


## 4.2.4. Defects of the Password Change

Firstly, the password change suffers from inside attacks. Consider that a registered userU′ acts as an adversary A1. Since U′ is a registered user of the server S, U′ can derive x||Tr(x) from his own D′,H′ by using his own password. Assume that U′ has intercepted U’s password change request Tix,EηH′,H∗,R. As shown above, U′ can calculate i∗=arccosTix+2kπ/arccosxk∈Z, which satisfies the equation Tix=Ti∗x. Thus, U′ computes the key η and further decrypts EηH′,H∗,R. Then, U′ selects randomly a value H″ of the same length of H∗. And U′ computes EηH′,H″,R and sends Tix,EηH′,H″,R to the server. Since the equation H′=H holds, the server will return R∗=EsID‖H″ to the smart card. The smart card stores R∗instead of R. Thus, the password change has been fulfilled. However, the user U cannot login to the server any more with the new password PW∗. We describe the failure process as follows. When the user U tries to login to S, U computes Q=hID‖H∗ where H∗=hPW∗‖t and then issues Tjx,EvQ,R∗,T1 to the server. The server decrypts EvQ,R∗,T1 and acquires R∗. S further decrypts R∗ to obtain ID,H″. S computes Q′=hID‖H″. Since Q′≠Q, the server will refuse U’s login request.Secondly, the Lin’s TAKACP scheme requires that the server participate during the whole password change phase. In many applications, registered users always need to update their passwords at intervals. Passwords should be freely updated by the smart card holder at will without any interaction with the server, while the server can be totally unaware of the password change. A TAKACP scheme should provide the users with free password changes. If the users’ password change requires the server online, it must be a bottleneck. The Lin scheme requires the server S to computeR∗ during the password change phase. Therefore, it is inconvenient to both the server and the users. For the Lin scheme, the password change is impractical.Thirdly, during the password change phase, the server is not authenticated by the smart card. This would be a serious security drawback. Any adversary could impersonate the server and send an arbitrary value asR∗. The smart card will replace R with R∗. The real card holder cannot login to the server any longer since R∗≠EsID‖H∗. If the password change proceeds through a secure channel as in the user registration phase, the above security drawbacks will be removed. However, this is also infeasible.


## 5. The Proposed Takacp Protocol

Lin [20] showed that the Guo-Chang scheme suffers from inside attacks. The analysis above demonstrates that the Lin’ TAKACP scheme [20] cannot still resist against inside attacks. The main cause is that an inside adversary A1 has the common chaotic map Tr(x) with the registered users of the same server. After intercepting the chaotic map Tj(x) transmitted over the public channel, A1 can derive an integer j∗ satisfying Tjx=Tj∗x. The adversary computes the key v to decrypt EvTj′x,hID‖T2,T2 and derive Tj′x. Thus, the adversary can determine the Diffie-Hellman-like session key Tj∗Tj′x.To eliminate these weaknesses, we will seek cryptographic techniques to protect the functionsTjx and Tj′x. In the following, we will use the quadratic residues to present two improved versions. We first describe an improved two-factor authentication scheme (hereafter called TAKACP-1) based on Chebyshev polynomials defined on the interval [−1,1] and then another two-factor authentication scheme (hereafter called TAKACP-2) based on Chebyshev polynomials defined on the interval (−∞,+∞).


### 5.1. Registration Phase

We adopt the same notations as those in the Lin scheme. The server S selectss as the symmetric encryption key, two distinct large primes p and q with p≡q≡3 (mod 4), and a one-way hash function h():{0,1}∗ ⟶{0,1}l where l is a security parameter. The parameters p, q, and s are kept secret. Before a user U gains access to the server S, U must register by performing the following steps as shown in Figure 4.Step R1. U selects a random integer n′with l bits, an identity ID, and password PW. Then, U computes d=hID‖PWn′ and delivers {ID, d} to S through a secure channel.Step R2. S computes c = d⊕Es(ID||n), where n = pq. S stores {c, n, h()} on a smart card and issues the smart card to U via a secure channel.Step R3. The card computes.Figure 4
User registration phase of the proposed TAKACP-1 protocol.


### 5.2. Authenticated Key Exchange PHASE

The userU and the server S cooperatively perform the following steps to generate a session key SK, which is also illustrated in Figure 5.Step A1. U inserts the smart card into the terminal and enters the identity ID and the password PW. The smart card checks whether d2 is equal to h((ID⊕PW)||d1||n). If ID and PW are valid, it computes c = d1⊕h(ID||PW). It generates a nonce n1 of the c’s binary length and randomly chooses a positive integer i and a real number x over [−1,1]. The card computes the Chebyshev polynomials Ti(x), e=c¯n12 mod n, w1=hn1⊕x‖Tix, c0 = h(ID||n1), θ1=hc‖x‖Tix‖c0, where x||Ti(x) is of l-bits. The symbol ¯means that the binary form of c interleaves the binary form of n1 bit by bit. Then, the card transmits the message M1=e,w1,θ1 to the server S.Step A2. Once receiving the login request, S uses Chinese Remainder theorem with p and q to solve the square roots of e. S parses the four roots into two parts, c′,n1′, respectively. Then, S decrypts c′ to obtain ID∗,n∗ and determines the right root by checking if n∗is equal to n. Finally, S obtains the right root c′¯n1′ and the identity ID∗. S computes x‖Tix=hn1′⊕w1, c0∗=hID∗‖n1′, and checks if the received θ1 equals hc′‖x‖Tix‖c0∗. If the equation holds, the server believes that the login comes from a registered user with the identity ID∗. S generates a nonce n2 such that n2||Tj(x) is l-bit in length and randomly chooses a positive integer j. Then, S computes(14)w2=hID∗n1′⊕n2Tjx,SK=hID∗TixTjxn1′n2TjTix,θ2=hc0∗Tjxx⊕hn2SK.And,S sends back the message M2=w2,θ2 to U. Otherwise, S rejects the login request from U.Step A3. Upon receipt of the response message from S, the smart card computes n2‖Tjx=w2⊕hID‖n1, SK∗ = h(ID||Ti(x)||Tj(x)||n1||n2||Ti(Tj(x))). Next, it checks whether θ2 equals h(c||(Tj(x)||x)⊕h(n2)||SK∗). If they are equal, the card authenticates the server. It computes θ3=hSK∗‖n1‖n2‖c0 and forwards the message M3=θ3 to the server S. Otherwise, U terminates the session.Step A4. After receiving the confirmation message from the card, S checks if hSK‖n1′‖n2‖c0∗ equals θ3. If they are equal, the user U with identity ID is authenticated. Moreover, S confirms the session key SK.Figure 5
Authenticated key exchange phase of the proposed TAKACP-1 protocol.


### 5.3. Password Change Phase

If the userU wants to update his password, U performs the following steps.Step C1. U inserts the smart card into the terminal and inputs the identity ID and the old password PW. Then, U issues the updating request.Step C2. The smart card checks whether d2 = h((ID⊕PW)||d1||n) holds. If the equation holds, it answers accepting updating.Step C3. U submits a new password PWnew.Step C4. The smart card computes(15)d1′=d1⊕hIDPW⊕hIDPWnew,d2′=hIDPWnewd1′n.The card removes {d1, d2} and stores d1′,d2′.Now, we describe briefly the TAKACP-2 scheme. There is a little difference between the registration phase of the TAKACP-2 scheme and that of the TAKACP-1 scheme. We will give the detailed description of the registration phase of TAKACP-2 scheme. Another fundamental difference of the authenticated key exchange phase ofTAKACP-2 scheme from TAKACP-1 scheme is that the real number x is drawn from the interval −∞,+∞. The card/server computes the Chebyshev polynomial Ti(x)/Tj(x) mod p0. By making similar modifications to the registration phase, we can have the password change phase. Here, we omit the description of the authenticated key exchange phase and the password change phase in the TAKACP-2 scheme.


### 5.4. Registration Phase of TAKACP-2

We adopt the same notations as those in theTAKACP-1 scheme. The server S selects a large prime p0 besides the symmetric encryption key s, two large primes p, q, and a one-way hash function h():{0,1}∗ ⟶{0,1}l. S keeps p, q, and s secret. Then, U performs the following steps to execute the registration.Step R1’. U selects a random integer n′, an identity ID, and password PW. Then, U computes d=hID‖PWn′ and delivers {ID, d} to S through a secure channel.Step R2’. S computes c = d⊕Es(ID||n||p0) where n = pq. S stores {c, n, p0, h()} on a smart card and issues the smart card to U via a secure channel.Step R3’. The card computes(16)d1=c⊕n′,d2=hID⊕PWd1n⊕p0.Then, U removesn′,c,d and stores {d1, d2} in the card.


## 5.1. Registration Phase

We adopt the same notations as those in the Lin scheme. The server S selectss as the symmetric encryption key, two distinct large primes p and q with p≡q≡3 (mod 4), and a one-way hash function h():{0,1}∗ ⟶{0,1}l where l is a security parameter. The parameters p, q, and s are kept secret. Before a user U gains access to the server S, U must register by performing the following steps as shown in Figure 4.Step R1. U selects a random integer n′with l bits, an identity ID, and password PW. Then, U computes d=hID‖PWn′ and delivers {ID, d} to S through a secure channel.Step R2. S computes c = d⊕Es(ID||n), where n = pq. S stores {c, n, h()} on a smart card and issues the smart card to U via a secure channel.Step R3. The card computes.Figure 4
User registration phase of the proposed TAKACP-1 protocol.


## 5.2. Authenticated Key Exchange PHASE

The userU and the server S cooperatively perform the following steps to generate a session key SK, which is also illustrated in Figure 5.Step A1. U inserts the smart card into the terminal and enters the identity ID and the password PW. The smart card checks whether d2 is equal to h((ID⊕PW)||d1||n). If ID and PW are valid, it computes c = d1⊕h(ID||PW). It generates a nonce n1 of the c’s binary length and randomly chooses a positive integer i and a real number x over [−1,1]. The card computes the Chebyshev polynomials Ti(x), e=c¯n12 mod n, w1=hn1⊕x‖Tix, c0 = h(ID||n1), θ1=hc‖x‖Tix‖c0, where x||Ti(x) is of l-bits. The symbol ¯means that the binary form of c interleaves the binary form of n1 bit by bit. Then, the card transmits the message M1=e,w1,θ1 to the server S.Step A2. Once receiving the login request, S uses Chinese Remainder theorem with p and q to solve the square roots of e. S parses the four roots into two parts, c′,n1′, respectively. Then, S decrypts c′ to obtain ID∗,n∗ and determines the right root by checking if n∗is equal to n. Finally, S obtains the right root c′¯n1′ and the identity ID∗. S computes x‖Tix=hn1′⊕w1, c0∗=hID∗‖n1′, and checks if the received θ1 equals hc′‖x‖Tix‖c0∗. If the equation holds, the server believes that the login comes from a registered user with the identity ID∗. S generates a nonce n2 such that n2||Tj(x) is l-bit in length and randomly chooses a positive integer j. Then, S computes(14)w2=hID∗n1′⊕n2Tjx,SK=hID∗TixTjxn1′n2TjTix,θ2=hc0∗Tjxx⊕hn2SK.And,S sends back the message M2=w2,θ2 to U. Otherwise, S rejects the login request from U.Step A3. Upon receipt of the response message from S, the smart card computes n2‖Tjx=w2⊕hID‖n1, SK∗ = h(ID||Ti(x)||Tj(x)||n1||n2||Ti(Tj(x))). Next, it checks whether θ2 equals h(c||(Tj(x)||x)⊕h(n2)||SK∗). If they are equal, the card authenticates the server. It computes θ3=hSK∗‖n1‖n2‖c0 and forwards the message M3=θ3 to the server S. Otherwise, U terminates the session.Step A4. After receiving the confirmation message from the card, S checks if hSK‖n1′‖n2‖c0∗ equals θ3. If they are equal, the user U with identity ID is authenticated. Moreover, S confirms the session key SK.Figure 5
Authenticated key exchange phase of the proposed TAKACP-1 protocol.


## 5.3. Password Change Phase

If the userU wants to update his password, U performs the following steps.Step C1. U inserts the smart card into the terminal and inputs the identity ID and the old password PW. Then, U issues the updating request.Step C2. The smart card checks whether d2 = h((ID⊕PW)||d1||n) holds. If the equation holds, it answers accepting updating.Step C3. U submits a new password PWnew.Step C4. The smart card computes(15)d1′=d1⊕hIDPW⊕hIDPWnew,d2′=hIDPWnewd1′n.The card removes {d1, d2} and stores d1′,d2′.Now, we describe briefly the TAKACP-2 scheme. There is a little difference between the registration phase of the TAKACP-2 scheme and that of the TAKACP-1 scheme. We will give the detailed description of the registration phase of TAKACP-2 scheme. Another fundamental difference of the authenticated key exchange phase ofTAKACP-2 scheme from TAKACP-1 scheme is that the real number x is drawn from the interval −∞,+∞. The card/server computes the Chebyshev polynomial Ti(x)/Tj(x) mod p0. By making similar modifications to the registration phase, we can have the password change phase. Here, we omit the description of the authenticated key exchange phase and the password change phase in the TAKACP-2 scheme.


## 5.4. Registration Phase of TAKACP-2

We adopt the same notations as those in theTAKACP-1 scheme. The server S selects a large prime p0 besides the symmetric encryption key s, two large primes p, q, and a one-way hash function h():{0,1}∗ ⟶{0,1}l. S keeps p, q, and s secret. Then, U performs the following steps to execute the registration.Step R1’. U selects a random integer n′, an identity ID, and password PW. Then, U computes d=hID‖PWn′ and delivers {ID, d} to S through a secure channel.Step R2’. S computes c = d⊕Es(ID||n||p0) where n = pq. S stores {c, n, p0, h()} on a smart card and issues the smart card to U via a secure channel.Step R3’. The card computes(16)d1=c⊕n′,d2=hID⊕PWd1n⊕p0.Then, U removesn′,c,d and stores {d1, d2} in the card.


## 6. Security Analyses

In this section, we will present the formal semantic security analysis of the proposed protocols under the random oracle model in Part A. Mutual authentication between a user and a server will be confirmed through the widely used BAN logic [46–48] in Part B. In Part C, we conduct the detailed informal security analysis of the proposed protocol. The formal security analysis and informal security analysis both show that our schemes provide stronger security attributes.


### 6.1. Formal Security Analysis in Random Oracle Model

In this subsection, we introduce a formal security model under the widely used Real Or-Random model [49], the authentication security model [50], and the sequence of game models [51].Assume that the server is a trustworthy entity. The server can accept the registration of users and validate the real identity of the users to provide them with services. There exists a secure channel between the server and the user to protect the registration of the user. In the following, we will apply the Dolev-Yao threat model (DY model) [52] to analyze the security of the proposed schemes. According to DY model, any two communicating parties communicate over an insecure channel. Assume that a polynomial time adversary has the ability to control the communication channel, for example, modifying, injecting, monitoring, and deleting messages over the open channel. Any adversary A can make oracle queries, which model the adversary’s capabilities in a real attack. The goal of the adversary is to penetrate the anonymous authentication of a key agreement protocol by compromising requirements for the protocols described below. A malicious registered user may act as A to attempt to obtain the identity information of other users who have registered on the same server.We will simulate various security attacks on the proposed schemes through all possible oracle queries listed below.Execute(Ui, Sj): This query models eavesdropping attacks on honest execution among the user instance Ui and the server instance Sj. The output of this query consists of the messages that were exchanged during the honest execution of the protocol.Send(Ui/Sj,m): This query models an active attack. The oracle query enables A to receive an actual response from a participant Ui/Sj. Specifically, the adversary A sends a message m to instance Ui/Sj, and the participant instance Ui/Sj follows the protocol to give a reply.Reveal(Ui/Sj): This query models known session key attacks. If no session key is defined for an instance Ui/Sj, or if either Ui/Sj, or its partner is asked a Test query, the output of this query is the invalid symbol ⊥. Otherwise, it returns the current session key SK, which has been established between Ui/Sj and its partner to A.Corrupt(U,a): The query models the capability of A to obtain the secret information of a user participant U, thereby corrupting the protocol.Ifa = 1, the query returns U’s password to A.Ifa = 2, the query returns the message stored in the user U’s smart card with A. The oracle simulates that when A gains the smart card of user U, it can extract the secret stored information.Test(Ui/Sj): If no session key is defined, for instance, Ui/Sj or if either Ui/Sj or its partner is asked a Reveal query, the output of this query is the invalid symbol ⊥. Otherwise, the oracle flips a coin b. If b = 1, the output is the session key. Otherwise, the output is a random string drawn from the space of session keys. The Test query is invoked once by the adversary with a fresh oracle. The query is used to define the semantic security of the session key SK.Definition 10.
An instanceUi/Sj is called to be accepted, if upon receiving the last expected protocol message, it goes into an accept state. The ordered concatenation of all sent and received messages by instance Ui/Sj forms the session identification(sid) of Ui/Sj for the current session.Definition 11.
Two instancesUi and Sj are said to be partnered if the three conditions hold simultaneously: (1) both Ui and Sj are accepted; (2) both Ui and Sj share the same sid; and (3) Ui and Sj are mutual partners of each other.Definition 12.
An instanceUi/Sj is called to be fresh if the following conditions are fulfilled simultaneously: (1) Ui/Sj is in the accepting state; (2) Reveal(Ui/Sj) query has never been submitted to Ui/Sj or its partner; and (3) strictly fewer than two Corrupt(Ui,a) queries have been made to Ui or strictly fewer than two Corrupt(Ui,a) queries have been submitted to Sj’s partner Ui.Definition 13.
For thesemantic security, the security model is defined by a game, which consists of two phases. In the first phase, an adversary A is allowed to adaptively issue Send, Execute, Reveal, and Test queries. In the second phase, the adversary A executes a single Test (Ui/Sj) query with the chosen bit b directed to a fresh instance and the query outputs a guess bit b′ for b. If b′=b, then the adversary A wins the above game, i.e., A succeeds in breaking the semantic security of the game of a TAKACP protocol. Let Succ(A) be an event where the adversary A wins the above game. The advantage of the adversary A in breaking the semantic security of the TAKACP protocol is defined by(17)AdvTFAKAA=PrSuccA−12=Prb′−b−12.
A TAKACP protocol is said to besemantically secure if the advantage AdvTFAKAAof any probabilistic polynomial time-bounded adversary A is negligible.Theorem 1.
LetD(W) be a uniformly distributed password (identity) dictionary of size |D|(|W|). Let A (including A1 and A2) be a polynomial time-bound adversary against the semantic security of the TAKACP-2 scheme. Suppose A makes at most qs times Send queries, qe times Execute queries, and qh times hash oracle queries. Then, we have(18)AdvTFAKA−2A≤qs2+qe22n+1+qs2+qe22p0−1+qh22l+1+3qh2l−1+qs2l−1+qs22l+qs23l+qsD+W+qhAdvCPCDHt+AdvIFt′qsW,where l refers to the string length of hash results, AdvCMCDHt is the success probability of any probabilistic polynomial time Turing machine within time upper bound t in solving CPCDH problems, and AdvIFt′ is the probability of integer factorization for any probabilistic polynomial time Turing machine within time upper bound t’.Proof.
We shall use the approach of sequent games to prove this theorem. We first define a sequence of modified attack gamesGi (i = 0,1,2,3,4,5) starting from G0 and terminating at G5. Let Succi be an event defined as the successful guessing of the bit b in Test query corresponding to each game Gi by an adversary A.Game G0: This starting game and the real protocol in random oracles are assumed to be identical. Hence, G0 is the actual attack game. By definition, we have(19)AdvTFAKA−2A=Prsucc0−12.Game G1: This game is the same as the game G0 except that the game simulates all oracle queries including Send, Reveal, Corrupt, Execute, Test, and hash queries. The hash oracles and Reveal, Test, Corrupt, and Execute queries are simulated in Table 3. We simulate the Send queries in Table 4 as in the actual attack game. The simulations maintain three lists of queries: (1) list Lh records the answers to hash oracles, (2) list LA records the answers to the queries which are initiated by A, and (3) list LT records the transcripts between S and U.This game is perfectly indistinguishable from the real execution of the protocol. Hence, we have(20)Prsucc1=Prsucc0.Game G2: In this game, we consider collisions among the results of hash queries, random numbers, and Chebyshev polynomials in the transcripts of messages M1, M2, and M3. We take the random value h from 0,1l as the response of the hash queries. If this query is directly asked by the adversary and (∗, h)←Lh, we abort the game. Otherwise, h is returned. Following the birthday paradox, the probability of collisions of the oracle hash query is at most qh2/2l+1. Furthermore, the messages contain random numbers {n1, n2} and two Chebyshev polynomials {Ti(x), Tj(x)}. And, the probability of random numbers and polynomials collision is at most qs2+qe2/2n+1+qs2+qe2/2p0−1. Games G2 and G1 are perfectly indistinguishable except that the abovementioned collision causes the game to abort. Hence, we have(21)PrSucc2−PrSucc1≤qs2+qe22n+1+qs2+qe22p0−1+qh22l+1.GameG3: This game would abort the execution in the situation where A obtains a valid authenticator without active participation of hash oracles. In the TAKACP-2 protocol, the authenticated key exchange phase involves three message communications, Mi, i = 1,2,3. We consider three cases, Send(U, M1), Send(S, M2), Send(U, M3) in the game G3.Case 1. Considering Send(U, M1) oracle query, we must carefully analyze the elements of message M1. The hash values h(c||x||Ti(x)||c0)∈LA must hold, otherwise the session will be terminated. The maximum calculated probability is up to qh/2l. Again, it must be that h(ID||n1) ∈LA whose probability is at most qh/2l. Finally, the message M1 ∈LT should hold, or the session will stop. For this, the probability is qs/23l.Case 2. Considering Send(S, M2) oracle query, M2 consists of w2 andθ2. The hash values hc0∗‖Tjx⊕hn2‖hID∗‖Tix‖Tjx‖n1′‖n2‖TjTix∈LA must hold; otherwise, the session will be terminated. The maximum probability is up toqh/2l.The probability of valuehID∗‖Tix‖Tjx‖n1′‖n2‖TjTix falling within the list LA is at most qh/2l. Finally, the message M2 should fall within LT, or the session will terminate. The maximum probability is qs/22l.Case 3. To respond Send(U, M3) oracle query, h(h(ID ||Ti(x)||Tj(x)||n1||n2||Ti(Tj(x)))||(n1⊕n2)||c0)∈LA must hold with the total maximum probability qh/2l. Finally, for a transcript M3∈LT, we have the maximum probability as qs/2l.Considering the three cases, we have,GameG4: In this game, when the session key SK is required to compute, we replace the random hash oracle H1 with private oracle H’. That is, the session key is determined without querying the hash oracle. Moreover, we do not use Tj(Ti(x)) or Ti(Tj(x)) to compute SK=H′(ID||Ti(x)||Tj(x)||n1||n2). Thus, the session key is completely independent of hash oracle and Tj(Ti(x)) or Ti(Tj(x)). Games G4 and G3 are perfectly indistinguishable unless the following event AskH1 occurs: the adversary A queries the hash function on ID||Ti(x)||Tj(x)||n1||n2||Tj(Ti(x)) or on the message ID||Ti(x)||Tj(x)||n1||n2||Ti(Tj(x)). Hence, we have(23)PrSucc4−PrSucc3≤PrAskH1.GameG5: In this game, we simulate the executions using the random self-reducibility of the CPCDH problem, given one CPCDH instance (Ti(x), Tj(x)). We choose randomly two integers u,vand compute Tu(Ti(x)), TvTjx. The event AskH2 means that the adversary A had queried the random hash oracle H1 on ID||Ti(x)||Tj(x)||n1||n2||Z, where Z=CPCDHTuTix,TvTjx. It is easy to know that the equation CPCDHTuTix,TvTjx=TuvCPCDHTix,Tjx holds. We have(24)PrSucc5−PrSucc4,PrAskH1=PrAskH2.
According to the definition of the event AskH, the accumulated probability is at leastPrAskH2/qh. Thus, we have(25)PrAskH2≤qhAdvCPCDHt.
In GameG5, Diffie–Hellman keys SK are random and independent of passwords and ephemeral keys. So, there are two possible cases where the adversary distinguishes the real session key from the random key as follows:Case 1. The adversary queries the hash oracle on ID||Ti(x)|| Tj(x)||n1||n2||Tj(Ti(x)).The probability that this event occurs is qh/2l.Case 2. The adversary asks the Send (Ui, m) query and successfully impersonates a user. If the Corrupt(U, 1) has been made, it implies that the Corrupt (U, 2) has not been made. To impersonate the user, the adversary has to obtain the parameter c and the identity. The probability that the event happens is AdvIFt′qs/W. On the contrary, if the Corrupt (U,2) has been made, it is not allowed to reveal the static key PW of the user. Thus, in order to impersonate the user, the adversary has to obtain some information on the password of the user. The success probability of the adversary in the qs sessions is qs/D+W. If the adversary just makes an attempt at random to impersonate the user by computing θ3 and succeeds, it will make the difference; but, the probability for qs sessions is less than. qs/2l
Hence, we have(26)PrSucc5≤12+qh2l+Advt′qsW+qsD+W+qs2l.
Using the triangular inequality and equations (19)–(26), we have the following:(27)AdvTFAKA−2A=PrSucc0−12≤∑i=04PrSucci−PrSucci+1+PrSucc5−12≤qs2+qe22n+1+qs2+qe22p0−1+qh22l+1+3qh2l−1+qs2l−1+qs22l+qs23l+qsD+W+qhAdvCPCDHt+AdvIFt′qsW.
Thus, we have completed the proof of the theorem.
The above theorem is about the security of the proposed TAKACP-2 scheme based on the extended Chebyshev polynomials defined on the interval [−∞, +∞]. To complete the security proof of the TAKACP-1 scheme based on Chebyshev polynomials over the interval [−1, 1], one only needs to delete the CPCDH simulation in GameG5 of the proof of Theorem 1. We only state the results as Theorem 2 without detailed proof.Table 3
Simulation of hash, reveal, test, corrupt, and execute oracle queries.
(i) Hash simulation query performs as follows:If the record (∗; h) is found in the list Lh corresponding to the hash query h(∗), return the hash function h. Otherwise, select a string h∈0,1l and add (∗; h) into Lh. If the query is initiated by A, (∗; h) is stored in LA.(ii)Reveal(Ui/Sj) simulation query performs as follows:If Ui/Sj is in the accepting state, the current session key SK formed by Ui/Sj and its partner is returned.(iii)Test(Ui/Sj) simulation query performs as follows:Through Reveal(Ui/Sj) query, obtain the current session SK and then flip an unbiased coin b. If b = 1, return SK. Otherwise, return a random string from {0,1}l.(iv)Corrupt(U, a) simulation query performs as follows:If a = 1, the query returns the password PW of U. If a = 2, the query returns the secret information stored in the user smart card.(v) Simulation ofExecute(Ui, Sj) query occurs in succession with the simulation of Send queries as shown below.e,w1,θ1←Send(Ui; start), w2,θ2←Send(Sj; e,w1,θ1) and {θ3}←Send(Ui; w2,θ2). Finally, M1 = e,w1,θ1, M2 = w2,θ2, and M3 = {θ3} are returned.Table 4
Simulation ofsend oracle queries.
(i) On a query Send(Ui; start), assuming Ui is in the correct state, we proceed as follows:Choose a positive integer i and a real number x over −∞,+∞ and compute Ti(x), e=c¯n12 mod n, w1=hn1⊕x‖Tix, θ1 = h(c||x||Ti(x)||h(ID||n1)). Then, the answer e,w1,θ1 to the query is returned.(ii) On a query Send(Sj; e,w1,θ1), assuming Sj is in the correct state, we proceed as follows:Solve the square roots of e and obtain c′,n1′. Decrypt c′ and get ID∗,n∗. Compute x‖Tix=hn1′⊕w1, c0∗ = h(ID∗||n1′), and check if the received θ1  = h(c′||x||Ti(x)||c0∗). If the equation does not hold, the server instance terminates without accepting. Otherwise, choose randomly a nonce n2, a positive integer j, and compute w2=hID∗‖n1′⊕n2‖Tjx, SK = h(ID∗||Ti(x)||Tj(x)||n1′||n2||Tj(Ti(x))), θ2 = h(c0∗||(Tj(x)⊕h(n2))||SK). Then, the answer w2,θ2 to the query is returned.(iii) On a query Send(Ui; w2,θ2), assuming Ui is in the correct state, we proceed as follows:Compute n2‖Tjx=w2⊕hID‖n1, SK∗ = h(ID||Ti(x)||Tj(x)||n1||n2||Ti(Tj(x))), and check whether θ2  = h(c||(Tj(x)⊕h(n2))||SK∗). If the equation does not hold, the user instance terminates without accepting. Otherwise, compute θ3 = h(SK∗||(n1⊕n2)||c0), authenticate Sj, and establish SK as the session key. Then, the answer {θ3} to the query is returned.(iv) On a query Send(Sj; {θ3}), assuming Sj is in the correct state, we proceed as follows:Check if θ3 = h(SK||(n1′⊕n2)||c0∗). If the equation does not hold, the server instance terminates without accepting and aborts the session. Otherwise, S accepts the session key SK.Theorem 2.
LetD(W) be a uniformly distributed password (identity) dictionary of size |D|(|W|). Let A (including A1 and A2) be the polynomial time-bound adversary against the semantic security of the TAKACP-1 scheme. Suppose A makes Send queries qs times, Executes queries qe times, and hash oracle queries qh times at most. Then, we have(28)AdvTFAKA−2A≤qs2+qe22n+1+qh22l+1+3qh2l−1+qs2l−1+qs22l+qs23l+qsD+W+AdvIFt′qsW,where l refers to the string length of hash results, AdvCMCDHt is the success probability of any probabilistic polynomial-time Turing machine within the time upper bound t in solving CPCDH problems, and AdvIFt′ is the probability of any probabilistic polynomial-time Turing machine in solving the square root with composite number module within time upper bound t’.Theorem 3.
The proposed TAKACP-1(TAKACP-2)scheme achieves the property of the medium unlinkability.Proof.
Consider that the insider adversaryA1 would attempt to violate the user anonymity of the proposed schemes. Further suppose that the Corrupt (U, 2) has been made. The smart card of the user U is compromised. The adversary A has extracted the elements {d1, d2, n} for TAKACP-1({d1, d2,n,p0} for TAKACP-2) in the smart card. Since d1 = Es(ID||n)⊕h(ID||PW), d2 = h((ID⊕PW)||d1||n) in TAKACP-1, or d1 = Es(ID||n||p0)⊕h(ID||PW), d2 = h((ID⊕PW)||d1||(n⊕p0)) in TAKACP-2, A cannot divide d1 or d2 into the exclusive-OR items Es(ID||n) or Es(ID||n||p0), h(ID||PW), h(ID⊕PW) correctly. In essence, even if A has Es(ID||n), A cannot still recover ID from it without the master key s. Since d2 = h((ID⊕PW)||d1||n) or h((ID⊕PW)||d1|| (n⊕p0)), owing to the one-way hash function, A1 cannot derive ID or PW from d2.
Now consider the authenticated key exchange phase. Assume thatM0,1=e0,w0,1,θ0,1 and M1,1=e1,w1,1,θ1,1 are two requesting messages produced by one user in two different authentication sessions, where(29)e0,1=c¯n0,12modn,w0,1=hn0,1⊕xT0ix,θ0,1=hcxT0ixhIDn0,1,e1,1=c¯n1,12modn,w1,1=hn1,1⊕yT1iy,θ1,1=hcyT1iyhIDn1,1.
Due to the usage of the random integers {n0,1, n1,1}, e0,1 is independent of e1,1. Likewise, owing to the randomness of {x, y, 0i,1i}, T0i(x) is independent of T1i(y). Thus, w0,1 is independent of w1,1. As h() is a secure cryptographic hash function, the same is true for θ0,1and θ1,1. Therefore, A believes that M0,1 and M1,1 are independent of each other. We can make similar analysis of the response messages M0,2=w0,2,θ0,2, M1,2=w1,2,θ1,2, and the confirmation messages M0,3=w0,3,θ0,3, M1,3=w1,3,θ1,3. From the above analysis, we have PrADecide=1/2. Thus, AdvStrong−Unlin(A) = 0.
Therefore, our protocols achieve medium unlinkability. Any adversary (butA0) is unable to link two different protocol sessions to the same user.


### 6.2. Authentication Proof Based on BAN-Logic

In this section, we introduce the well-popular Burrows-Abadi-Needham Logic (BAN-logic) to validate the authentication of the proposed protocols. By using BAN logic, we also try to find out flaws in the proposed schemes and deal with authentication issues among the participants. The formal verification of the BAN logic demonstrates that the proposed protocols achieve mutual authentication and allow the user and the server to establish session keys. It is well-known that BAN logic [46] is the widely used logical analysis method of reasoning the beliefs of participants in an authentication protocol [47, 48]. BAN logic uses a set of postulates to analyze and verify authentication schemes. BAN logic has three elementary items, i.e., formulas/statements, principals, and keys. Let X and Y be two statements, P and Q be principals, K be the symbol for a key. The basic expressions of BAN logic are described in Table 5. More details can be found in [46–48].Table 5
Notations of BAN logic.
SymbolDescriptP|≡XThe principalP believes a statement X, or P would be entitled to believe X.P⊲XP sees X. P has received a message containing X and can read and repeat X (possibly after doing some decryption).P|∼XP once said X. P at some time sent a message containing X. It is not known whether this is a replay, though it is known that P believed X when he or she sent it.P|≡XP has jurisdiction over X. P is an authority on X and is trusted on this matter.#(X)The formulaX is fresh. That is, X has never been sent in a message at any time before the current run of the protocolP↔KQK is a key shared between P and Q. P and Q may use K to communicate. And K is good since it can never be discovered by any principal except P or Q, or a principal trusted by either P or Q.P⇔XQThe formulaX is a shared key known only to P and Q, possibly to principals trusted by them.{X}KThe formulaX is encrypted by K.<X>YThis representsX combined with the formula Y. It is intended that Y be a secret and that its presence proves the identity of whoever utters <X>Y. X is simply concatenated with Y while Y plays a role as proof or origin for X.The main logical postulates of theBAN logic are listed as follows:Message-meaning rule:P|≡P↔KQ,P⊲XK/P|≡Q|∼X, P|≡P⇔KQ,P⊲XK/P|≡Q|∼X: If P believes that it shares K with Q and sees X encrypted by K (or X combined with K), then P believes that Q once said X.The nonce-verification rule:P|≡#X,P|≡Q|∼X/P|≡Q|≡XIf P believes thatX could have been uttered only recently and Q once said X, then P believes that Q believes X.The freshness propagation rule:P|≡#X/P|≡#X,YIf P believes thatX is fresh, then P also believes that (X, Y) is fresh.The jurisdiction rule:P|≡Q|⇒X,P|≡Q|≡X/P|≡XIf P believes thatQ has authority over X and Q believes X, then P trusts Q on the truth of X.The message decryption rule:P|≡P↔KQ,P⊲XK/P⊲XIfP believes that it shares K with Q and sees encrypted X by K, then P sees X.In the following, we apply BAN logic to analyze the TAKACP-1 scheme. Similar analysis can be applied to the TAKACP-2 scheme. According to the analytic procedures of the BAN logic, the proposed TAKACP-1 scheme must satisfy the following goals:Goal (1): U|≡S|≡U↔SKS,Goal (2): U|≡U↔SKS,Goal (3): S|≡U|≡U↔SKS,Goal (4): S|≡U↔SKS.The generic form of the proposed TAKACP-1 scheme is described below.From messageM1, U⟶S: {c, n1}n, x,Tixhn1, < c0, x,Ti(x)>c.From messageM2, S⟶U: n2,TjxhID∗‖n1′, Tj′x,hn2,SKc0.From messageM3, U⟶S: n1⊕n2,SKc0.The idealized form of the proposed TAKACP-1 scheme in the language of formal logic is given below.MessageM1: U⟶S: x,Tix,U↔c0S,U⇔nSU↔cS.MessageM2: S⟶U: n2,Tjx,U↔SKSU↔c0S.MessageM3: U⟶S: n1,n2,U↔SKSU↔c0S.We make the assumptions about the initial state to analyze the proposed TAKACP-1 scheme:H1: U|≡#n1, U|≡#Tix;H2: S|≡#n2, S|≡#Tjx;H3: S|≡U↔cS;H4: U|≡U↔c0S;H5: S|≡U|⇒U↔c0S;H6: U|≡S|⇒U↔SKS;H7: S|≡U|⇒U↔SKS.According to the BAN logic and the assumptions, we give the main proof as follows:From messageM1, we haveS1: S⊲x,Tix,U↔c0S,U⇔nSU↔cS.FromS1, H3, and Rule (1), we haveS2: S|≡U|∼x,Tix,U↔c0S,U⇔nS.FromS2, H2, Rule (2) and Rule (3), we haveS3: S|≡U|≡U↔c0S.FromS3, H5, and Rule (4), we haveS4: S|≡U↔c0S.From messageM2, we haveS5: U⊲n2,Tjx,U↔SKSU↔c0S.FromS5, H4, and Rule (1), we haveS6: U|≡S|∼n2,Tjx,U↔SKS.FromS6, H1, Rule (2), and Rule (3), we haveS7: U|≡S|≡U↔SKS(Goal (1)).FromS7, H6, and Rule (4), we haveS8: U|≡U↔SKS(Goal (2)).From messageM3, we haveS9: S⊲n1,n2,U↔SKSU↔c0S.FromS9, S4, and Rule (1), we haveS10: S|≡U|∼n1,n2,U↔SKS.FromS10, H2, Rule (2), and Rule (3), we haveS11: S|≡U|≡U↔SKS(Goal (3)).FromS11, H7, and Rule (4), we haveS12: S|≡U↔SKS (Goal (4)).


### 6.3. Informal Security Analysis

In this section, we analyze the security of the proposed protocols. We will show that the proposed protocols satisfy the essential security requirements, including the ability to provide medium unlinkability, the contributory property of key agreements, session key security, two-factor secrecy, and free updating of passwords. Furthermore, we confirm that the proposed schemes can withstand replay attacks and password-guessing attacks. In the following, we will not expound the two-factor security since its proof has been given in Part A and Part B of Section4, respectively.


#### 6.3.1. Medium Unlinkability

In Part A of Section4, we have demonstrated that our protocols can provide medium unlinkability. Now, we compare the privacy-preserving of our protocols with that of the schemes of Guo-Chang [19], Lin [20], and Sun et al. [24].In the Guo-Chang scheme, since the user identity is encrypted with the master key of the server into the login requestR, any adversary A cannot reveal the user identity. So Pr[AGuess] = 1/N. However, R is unchanged until the user updates the password. Thus, any outside adversary can distinguish whether the users in two authentication sessions are identical. That is, PrA2Decide=1. Thus, we have AdvAnon−Alone(A) = 0 and AdvWeak−Unlin(A)≥1/2. Hence, the Guo-Chang scheme provides anonymity-alone but weak unlinkability. Similarly, since every request of the user contains the unchanged element IM, Sun et al.’s scheme [24] only achieves the property anonymity-alone.The Lin scheme can provide weak unlinkability. Specifically, although the elementsQ and R are kept unchanged, they are transmitted in the ciphertext EvQ,R,T1. Since any outside adversary A2 cannot calculate the key v, they cannot obtain R. But any inside adversary A1 can compute v and acquire Q, R. For every login of the user, the parameters {Q, R} are static until the user changes its password or identity. Thus, A1 can still decide whether different login requests are from the same user or not. Then, we have PrA1,2Decide=1. Hence, AdvMedium-Unlin(A) > 1/2. The Lin scheme cannot provide medium unlinkability.In the proposed protocols,i and x are chosen randomly by every individual user. Therefore, no unchanged login message can be derived by the other registered users. Thus, we obtain that AdvMedium-Unlin(A) = 0. However, each time the user logins to the server, the server validates his or her identity. So, the advantage AdvStrong-Unlin(A) is nonnegligible. The proposed schemes cannot achieve the medium unlinkability.


#### 6.3.2. Contributory Property of Key Agreement

In the proposed protocols, the session keySK is h(ID||Ti(x)||Tj(x)||n1||n2||Ti(Tj(x))). Only for the TAKACP-1 scheme, the server can use the method mentioned in [18, 44] to compute i∗ and j∗, thus satisfying Tix=Ti∗x, Tjx=Tj∗x, where Ti∗Tj∗x represents a previous parameter. Since x, Tixand n1 are randomly selected by the user and SK contains Tix and n1, the server still fails to predetermine a session key. Likewise, since Tj(x) and n2 are randomly selected by the server and SK contains Tj(x) and n2, the user cannot predetermine a session key. Notably, neither the server nor the user can determine the specific session key alone in advance. Therefore, the proposed protocols satisfy the contributory property of key agreements.


#### 6.3.3. Session Key Security

Firstly, sincei, j, n1 and n2 are selected randomly in every run of the protocols, the session key SK = h(ID||Ti(x)|| Tj(x)||n1||n2||Ti(Tj(x))) is independent of the previously generated session keys. Thus, the proposed protocols can resist against known-key attacks.Secondly, we demonstrate that the proposed protocols can prevent any inside adversary from computing the session keys. Consider that an inside adversaryA1 has eavesdropped the communication messages e,w1,θ1,w2,θ2,θ3 between the user and the server. Since A1 is a legal user of the same server, A1 knows n. However, n1 cannot be derived from e without the server’s private keys p and q, where e=c¯n12 mod n, owing to the quadratic residue assumption. Thus, the adversary cannot still recover x||Ti(x) from w1 without the knowledge of n1, where w1=hn1⊕x‖Tix. Moreover, A cannot work out h(ID||n1). A1 cannot obtain n2||Tj(x) from w2, since w2=hID∗‖n1′⊕n2‖Tjx. Since θ1=hc‖x‖Tix‖c0, θ2=hc0∗‖Tjx⊕hn2‖SK, and θ3=hSK∗‖n1⊕n2‖c0, due to the one-way property of the hash function, A1 cannot determine Ti(x), Tj(x), or SK. In a word, the session key cannot be derived from the messages transmitted over the public channel. The proposed schemes achieve session key security.


#### 6.3.4. Free Updating of Password

As described in Part C of Section5, a user can freely update password without any interaction with the server during the password change phase.


#### 6.3.5. Resistance to Password Guessing Attacks

In the proposed TAKACP protocols, the login request messagee is information that involves password PW. An inside adversary A1 may guess the password through the equation c = d1⊕h(ID||PW). However, an inside adversary A1 cannot still obtain c from e since e=c¯n12 mod n. Therefore, the proposed protocols can resist password guessing attacks.


#### 6.3.6. Resistance to Replay Attacks

The proposed schemes maintain freshness by using two nonces and two chaotic maps. Specifically, the proposed protocols guarantee the freshness of messages by usingTi(x) and n1 in Step A1, Tj(x) and n2 in Step A2, and {Ti(x), Tj(x), n1, n2} in Steps A3 and A4, respectively. Since n1 is protected by the quadratic residues, only the server and the user itself know it. Ti(x), Tj(x), and n2 are contained in w1 and w2. They can be calculated only when one knows the nonce n1. Therefore, the proposed schemes can prevent replaying attacks.


## 6.1. Formal Security Analysis in Random Oracle Model

In this subsection, we introduce a formal security model under the widely used Real Or-Random model [49], the authentication security model [50], and the sequence of game models [51].Assume that the server is a trustworthy entity. The server can accept the registration of users and validate the real identity of the users to provide them with services. There exists a secure channel between the server and the user to protect the registration of the user. In the following, we will apply the Dolev-Yao threat model (DY model) [52] to analyze the security of the proposed schemes. According to DY model, any two communicating parties communicate over an insecure channel. Assume that a polynomial time adversary has the ability to control the communication channel, for example, modifying, injecting, monitoring, and deleting messages over the open channel. Any adversary A can make oracle queries, which model the adversary’s capabilities in a real attack. The goal of the adversary is to penetrate the anonymous authentication of a key agreement protocol by compromising requirements for the protocols described below. A malicious registered user may act as A to attempt to obtain the identity information of other users who have registered on the same server.We will simulate various security attacks on the proposed schemes through all possible oracle queries listed below.Execute(Ui, Sj): This query models eavesdropping attacks on honest execution among the user instance Ui and the server instance Sj. The output of this query consists of the messages that were exchanged during the honest execution of the protocol.Send(Ui/Sj,m): This query models an active attack. The oracle query enables A to receive an actual response from a participant Ui/Sj. Specifically, the adversary A sends a message m to instance Ui/Sj, and the participant instance Ui/Sj follows the protocol to give a reply.Reveal(Ui/Sj): This query models known session key attacks. If no session key is defined for an instance Ui/Sj, or if either Ui/Sj, or its partner is asked a Test query, the output of this query is the invalid symbol ⊥. Otherwise, it returns the current session key SK, which has been established between Ui/Sj and its partner to A.Corrupt(U,a): The query models the capability of A to obtain the secret information of a user participant U, thereby corrupting the protocol.Ifa = 1, the query returns U’s password to A.Ifa = 2, the query returns the message stored in the user U’s smart card with A. The oracle simulates that when A gains the smart card of user U, it can extract the secret stored information.Test(Ui/Sj): If no session key is defined, for instance, Ui/Sj or if either Ui/Sj or its partner is asked a Reveal query, the output of this query is the invalid symbol ⊥. Otherwise, the oracle flips a coin b. If b = 1, the output is the session key. Otherwise, the output is a random string drawn from the space of session keys. The Test query is invoked once by the adversary with a fresh oracle. The query is used to define the semantic security of the session key SK.Definition 10.
An instanceUi/Sj is called to be accepted, if upon receiving the last expected protocol message, it goes into an accept state. The ordered concatenation of all sent and received messages by instance Ui/Sj forms the session identification(sid) of Ui/Sj for the current session.Definition 11.
Two instancesUi and Sj are said to be partnered if the three conditions hold simultaneously: (1) both Ui and Sj are accepted; (2) both Ui and Sj share the same sid; and (3) Ui and Sj are mutual partners of each other.Definition 12.
An instanceUi/Sj is called to be fresh if the following conditions are fulfilled simultaneously: (1) Ui/Sj is in the accepting state; (2) Reveal(Ui/Sj) query has never been submitted to Ui/Sj or its partner; and (3) strictly fewer than two Corrupt(Ui,a) queries have been made to Ui or strictly fewer than two Corrupt(Ui,a) queries have been submitted to Sj’s partner Ui.Definition 13.
For thesemantic security, the security model is defined by a game, which consists of two phases. In the first phase, an adversary A is allowed to adaptively issue Send, Execute, Reveal, and Test queries. In the second phase, the adversary A executes a single Test (Ui/Sj) query with the chosen bit b directed to a fresh instance and the query outputs a guess bit b′ for b. If b′=b, then the adversary A wins the above game, i.e., A succeeds in breaking the semantic security of the game of a TAKACP protocol. Let Succ(A) be an event where the adversary A wins the above game. The advantage of the adversary A in breaking the semantic security of the TAKACP protocol is defined by(17)AdvTFAKAA=PrSuccA−12=Prb′−b−12.
A TAKACP protocol is said to besemantically secure if the advantage AdvTFAKAAof any probabilistic polynomial time-bounded adversary A is negligible.Theorem 1.
LetD(W) be a uniformly distributed password (identity) dictionary of size |D|(|W|). Let A (including A1 and A2) be a polynomial time-bound adversary against the semantic security of the TAKACP-2 scheme. Suppose A makes at most qs times Send queries, qe times Execute queries, and qh times hash oracle queries. Then, we have(18)AdvTFAKA−2A≤qs2+qe22n+1+qs2+qe22p0−1+qh22l+1+3qh2l−1+qs2l−1+qs22l+qs23l+qsD+W+qhAdvCPCDHt+AdvIFt′qsW,where l refers to the string length of hash results, AdvCMCDHt is the success probability of any probabilistic polynomial time Turing machine within time upper bound t in solving CPCDH problems, and AdvIFt′ is the probability of integer factorization for any probabilistic polynomial time Turing machine within time upper bound t’.Proof.
We shall use the approach of sequent games to prove this theorem. We first define a sequence of modified attack gamesGi (i = 0,1,2,3,4,5) starting from G0 and terminating at G5. Let Succi be an event defined as the successful guessing of the bit b in Test query corresponding to each game Gi by an adversary A.Game G0: This starting game and the real protocol in random oracles are assumed to be identical. Hence, G0 is the actual attack game. By definition, we have(19)AdvTFAKA−2A=Prsucc0−12.Game G1: This game is the same as the game G0 except that the game simulates all oracle queries including Send, Reveal, Corrupt, Execute, Test, and hash queries. The hash oracles and Reveal, Test, Corrupt, and Execute queries are simulated in Table 3. We simulate the Send queries in Table 4 as in the actual attack game. The simulations maintain three lists of queries: (1) list Lh records the answers to hash oracles, (2) list LA records the answers to the queries which are initiated by A, and (3) list LT records the transcripts between S and U.This game is perfectly indistinguishable from the real execution of the protocol. Hence, we have(20)Prsucc1=Prsucc0.Game G2: In this game, we consider collisions among the results of hash queries, random numbers, and Chebyshev polynomials in the transcripts of messages M1, M2, and M3. We take the random value h from 0,1l as the response of the hash queries. If this query is directly asked by the adversary and (∗, h)←Lh, we abort the game. Otherwise, h is returned. Following the birthday paradox, the probability of collisions of the oracle hash query is at most qh2/2l+1. Furthermore, the messages contain random numbers {n1, n2} and two Chebyshev polynomials {Ti(x), Tj(x)}. And, the probability of random numbers and polynomials collision is at most qs2+qe2/2n+1+qs2+qe2/2p0−1. Games G2 and G1 are perfectly indistinguishable except that the abovementioned collision causes the game to abort. Hence, we have(21)PrSucc2−PrSucc1≤qs2+qe22n+1+qs2+qe22p0−1+qh22l+1.GameG3: This game would abort the execution in the situation where A obtains a valid authenticator without active participation of hash oracles. In the TAKACP-2 protocol, the authenticated key exchange phase involves three message communications, Mi, i = 1,2,3. We consider three cases, Send(U, M1), Send(S, M2), Send(U, M3) in the game G3.Case 1. Considering Send(U, M1) oracle query, we must carefully analyze the elements of message M1. The hash values h(c||x||Ti(x)||c0)∈LA must hold, otherwise the session will be terminated. The maximum calculated probability is up to qh/2l. Again, it must be that h(ID||n1) ∈LA whose probability is at most qh/2l. Finally, the message M1 ∈LT should hold, or the session will stop. For this, the probability is qs/23l.Case 2. Considering Send(S, M2) oracle query, M2 consists of w2 andθ2. The hash values hc0∗‖Tjx⊕hn2‖hID∗‖Tix‖Tjx‖n1′‖n2‖TjTix∈LA must hold; otherwise, the session will be terminated. The maximum probability is up toqh/2l.The probability of valuehID∗‖Tix‖Tjx‖n1′‖n2‖TjTix falling within the list LA is at most qh/2l. Finally, the message M2 should fall within LT, or the session will terminate. The maximum probability is qs/22l.Case 3. To respond Send(U, M3) oracle query, h(h(ID ||Ti(x)||Tj(x)||n1||n2||Ti(Tj(x)))||(n1⊕n2)||c0)∈LA must hold with the total maximum probability qh/2l. Finally, for a transcript M3∈LT, we have the maximum probability as qs/2l.Considering the three cases, we have,GameG4: In this game, when the session key SK is required to compute, we replace the random hash oracle H1 with private oracle H’. That is, the session key is determined without querying the hash oracle. Moreover, we do not use Tj(Ti(x)) or Ti(Tj(x)) to compute SK=H′(ID||Ti(x)||Tj(x)||n1||n2). Thus, the session key is completely independent of hash oracle and Tj(Ti(x)) or Ti(Tj(x)). Games G4 and G3 are perfectly indistinguishable unless the following event AskH1 occurs: the adversary A queries the hash function on ID||Ti(x)||Tj(x)||n1||n2||Tj(Ti(x)) or on the message ID||Ti(x)||Tj(x)||n1||n2||Ti(Tj(x)). Hence, we have(23)PrSucc4−PrSucc3≤PrAskH1.GameG5: In this game, we simulate the executions using the random self-reducibility of the CPCDH problem, given one CPCDH instance (Ti(x), Tj(x)). We choose randomly two integers u,vand compute Tu(Ti(x)), TvTjx. The event AskH2 means that the adversary A had queried the random hash oracle H1 on ID||Ti(x)||Tj(x)||n1||n2||Z, where Z=CPCDHTuTix,TvTjx. It is easy to know that the equation CPCDHTuTix,TvTjx=TuvCPCDHTix,Tjx holds. We have(24)PrSucc5−PrSucc4,PrAskH1=PrAskH2.
According to the definition of the event AskH, the accumulated probability is at leastPrAskH2/qh. Thus, we have(25)PrAskH2≤qhAdvCPCDHt.
In GameG5, Diffie–Hellman keys SK are random and independent of passwords and ephemeral keys. So, there are two possible cases where the adversary distinguishes the real session key from the random key as follows:Case 1. The adversary queries the hash oracle on ID||Ti(x)|| Tj(x)||n1||n2||Tj(Ti(x)).The probability that this event occurs is qh/2l.Case 2. The adversary asks the Send (Ui, m) query and successfully impersonates a user. If the Corrupt(U, 1) has been made, it implies that the Corrupt (U, 2) has not been made. To impersonate the user, the adversary has to obtain the parameter c and the identity. The probability that the event happens is AdvIFt′qs/W. On the contrary, if the Corrupt (U,2) has been made, it is not allowed to reveal the static key PW of the user. Thus, in order to impersonate the user, the adversary has to obtain some information on the password of the user. The success probability of the adversary in the qs sessions is qs/D+W. If the adversary just makes an attempt at random to impersonate the user by computing θ3 and succeeds, it will make the difference; but, the probability for qs sessions is less than. qs/2l
Hence, we have(26)PrSucc5≤12+qh2l+Advt′qsW+qsD+W+qs2l.
Using the triangular inequality and equations (19)–(26), we have the following:(27)AdvTFAKA−2A=PrSucc0−12≤∑i=04PrSucci−PrSucci+1+PrSucc5−12≤qs2+qe22n+1+qs2+qe22p0−1+qh22l+1+3qh2l−1+qs2l−1+qs22l+qs23l+qsD+W+qhAdvCPCDHt+AdvIFt′qsW.
Thus, we have completed the proof of the theorem.
The above theorem is about the security of the proposed TAKACP-2 scheme based on the extended Chebyshev polynomials defined on the interval [−∞, +∞]. To complete the security proof of the TAKACP-1 scheme based on Chebyshev polynomials over the interval [−1, 1], one only needs to delete the CPCDH simulation in GameG5 of the proof of Theorem 1. We only state the results as Theorem 2 without detailed proof.Table 3
Simulation of hash, reveal, test, corrupt, and execute oracle queries.
(i) Hash simulation query performs as follows:If the record (∗; h) is found in the list Lh corresponding to the hash query h(∗), return the hash function h. Otherwise, select a string h∈0,1l and add (∗; h) into Lh. If the query is initiated by A, (∗; h) is stored in LA.(ii)Reveal(Ui/Sj) simulation query performs as follows:If Ui/Sj is in the accepting state, the current session key SK formed by Ui/Sj and its partner is returned.(iii)Test(Ui/Sj) simulation query performs as follows:Through Reveal(Ui/Sj) query, obtain the current session SK and then flip an unbiased coin b. If b = 1, return SK. Otherwise, return a random string from {0,1}l.(iv)Corrupt(U, a) simulation query performs as follows:If a = 1, the query returns the password PW of U. If a = 2, the query returns the secret information stored in the user smart card.(v) Simulation ofExecute(Ui, Sj) query occurs in succession with the simulation of Send queries as shown below.e,w1,θ1←Send(Ui; start), w2,θ2←Send(Sj; e,w1,θ1) and {θ3}←Send(Ui; w2,θ2). Finally, M1 = e,w1,θ1, M2 = w2,θ2, and M3 = {θ3} are returned.Table 4
Simulation ofsend oracle queries.
(i) On a query Send(Ui; start), assuming Ui is in the correct state, we proceed as follows:Choose a positive integer i and a real number x over −∞,+∞ and compute Ti(x), e=c¯n12 mod n, w1=hn1⊕x‖Tix, θ1 = h(c||x||Ti(x)||h(ID||n1)). Then, the answer e,w1,θ1 to the query is returned.(ii) On a query Send(Sj; e,w1,θ1), assuming Sj is in the correct state, we proceed as follows:Solve the square roots of e and obtain c′,n1′. Decrypt c′ and get ID∗,n∗. Compute x‖Tix=hn1′⊕w1, c0∗ = h(ID∗||n1′), and check if the received θ1  = h(c′||x||Ti(x)||c0∗). If the equation does not hold, the server instance terminates without accepting. Otherwise, choose randomly a nonce n2, a positive integer j, and compute w2=hID∗‖n1′⊕n2‖Tjx, SK = h(ID∗||Ti(x)||Tj(x)||n1′||n2||Tj(Ti(x))), θ2 = h(c0∗||(Tj(x)⊕h(n2))||SK). Then, the answer w2,θ2 to the query is returned.(iii) On a query Send(Ui; w2,θ2), assuming Ui is in the correct state, we proceed as follows:Compute n2‖Tjx=w2⊕hID‖n1, SK∗ = h(ID||Ti(x)||Tj(x)||n1||n2||Ti(Tj(x))), and check whether θ2  = h(c||(Tj(x)⊕h(n2))||SK∗). If the equation does not hold, the user instance terminates without accepting. Otherwise, compute θ3 = h(SK∗||(n1⊕n2)||c0), authenticate Sj, and establish SK as the session key. Then, the answer {θ3} to the query is returned.(iv) On a query Send(Sj; {θ3}), assuming Sj is in the correct state, we proceed as follows:Check if θ3 = h(SK||(n1′⊕n2)||c0∗). If the equation does not hold, the server instance terminates without accepting and aborts the session. Otherwise, S accepts the session key SK.Theorem 2.
LetD(W) be a uniformly distributed password (identity) dictionary of size |D|(|W|). Let A (including A1 and A2) be the polynomial time-bound adversary against the semantic security of the TAKACP-1 scheme. Suppose A makes Send queries qs times, Executes queries qe times, and hash oracle queries qh times at most. Then, we have(28)AdvTFAKA−2A≤qs2+qe22n+1+qh22l+1+3qh2l−1+qs2l−1+qs22l+qs23l+qsD+W+AdvIFt′qsW,where l refers to the string length of hash results, AdvCMCDHt is the success probability of any probabilistic polynomial-time Turing machine within the time upper bound t in solving CPCDH problems, and AdvIFt′ is the probability of any probabilistic polynomial-time Turing machine in solving the square root with composite number module within time upper bound t’.Theorem 3.
The proposed TAKACP-1(TAKACP-2)scheme achieves the property of the medium unlinkability.Proof.
Consider that the insider adversaryA1 would attempt to violate the user anonymity of the proposed schemes. Further suppose that the Corrupt (U, 2) has been made. The smart card of the user U is compromised. The adversary A has extracted the elements {d1, d2, n} for TAKACP-1({d1, d2,n,p0} for TAKACP-2) in the smart card. Since d1 = Es(ID||n)⊕h(ID||PW), d2 = h((ID⊕PW)||d1||n) in TAKACP-1, or d1 = Es(ID||n||p0)⊕h(ID||PW), d2 = h((ID⊕PW)||d1||(n⊕p0)) in TAKACP-2, A cannot divide d1 or d2 into the exclusive-OR items Es(ID||n) or Es(ID||n||p0), h(ID||PW), h(ID⊕PW) correctly. In essence, even if A has Es(ID||n), A cannot still recover ID from it without the master key s. Since d2 = h((ID⊕PW)||d1||n) or h((ID⊕PW)||d1|| (n⊕p0)), owing to the one-way hash function, A1 cannot derive ID or PW from d2.
Now consider the authenticated key exchange phase. Assume thatM0,1=e0,w0,1,θ0,1 and M1,1=e1,w1,1,θ1,1 are two requesting messages produced by one user in two different authentication sessions, where(29)e0,1=c¯n0,12modn,w0,1=hn0,1⊕xT0ix,θ0,1=hcxT0ixhIDn0,1,e1,1=c¯n1,12modn,w1,1=hn1,1⊕yT1iy,θ1,1=hcyT1iyhIDn1,1.
Due to the usage of the random integers {n0,1, n1,1}, e0,1 is independent of e1,1. Likewise, owing to the randomness of {x, y, 0i,1i}, T0i(x) is independent of T1i(y). Thus, w0,1 is independent of w1,1. As h() is a secure cryptographic hash function, the same is true for θ0,1and θ1,1. Therefore, A believes that M0,1 and M1,1 are independent of each other. We can make similar analysis of the response messages M0,2=w0,2,θ0,2, M1,2=w1,2,θ1,2, and the confirmation messages M0,3=w0,3,θ0,3, M1,3=w1,3,θ1,3. From the above analysis, we have PrADecide=1/2. Thus, AdvStrong−Unlin(A) = 0.
Therefore, our protocols achieve medium unlinkability. Any adversary (butA0) is unable to link two different protocol sessions to the same user.


## 6.2. Authentication Proof Based on BAN-Logic

In this section, we introduce the well-popular Burrows-Abadi-Needham Logic (BAN-logic) to validate the authentication of the proposed protocols. By using BAN logic, we also try to find out flaws in the proposed schemes and deal with authentication issues among the participants. The formal verification of the BAN logic demonstrates that the proposed protocols achieve mutual authentication and allow the user and the server to establish session keys. It is well-known that BAN logic [46] is the widely used logical analysis method of reasoning the beliefs of participants in an authentication protocol [47, 48]. BAN logic uses a set of postulates to analyze and verify authentication schemes. BAN logic has three elementary items, i.e., formulas/statements, principals, and keys. Let X and Y be two statements, P and Q be principals, K be the symbol for a key. The basic expressions of BAN logic are described in Table 5. More details can be found in [46–48].Table 5
Notations of BAN logic.
SymbolDescriptP|≡XThe principalP believes a statement X, or P would be entitled to believe X.P⊲XP sees X. P has received a message containing X and can read and repeat X (possibly after doing some decryption).P|∼XP once said X. P at some time sent a message containing X. It is not known whether this is a replay, though it is known that P believed X when he or she sent it.P|≡XP has jurisdiction over X. P is an authority on X and is trusted on this matter.#(X)The formulaX is fresh. That is, X has never been sent in a message at any time before the current run of the protocolP↔KQK is a key shared between P and Q. P and Q may use K to communicate. And K is good since it can never be discovered by any principal except P or Q, or a principal trusted by either P or Q.P⇔XQThe formulaX is a shared key known only to P and Q, possibly to principals trusted by them.{X}KThe formulaX is encrypted by K.<X>YThis representsX combined with the formula Y. It is intended that Y be a secret and that its presence proves the identity of whoever utters <X>Y. X is simply concatenated with Y while Y plays a role as proof or origin for X.The main logical postulates of theBAN logic are listed as follows:Message-meaning rule:P|≡P↔KQ,P⊲XK/P|≡Q|∼X, P|≡P⇔KQ,P⊲XK/P|≡Q|∼X: If P believes that it shares K with Q and sees X encrypted by K (or X combined with K), then P believes that Q once said X.The nonce-verification rule:P|≡#X,P|≡Q|∼X/P|≡Q|≡XIf P believes thatX could have been uttered only recently and Q once said X, then P believes that Q believes X.The freshness propagation rule:P|≡#X/P|≡#X,YIf P believes thatX is fresh, then P also believes that (X, Y) is fresh.The jurisdiction rule:P|≡Q|⇒X,P|≡Q|≡X/P|≡XIf P believes thatQ has authority over X and Q believes X, then P trusts Q on the truth of X.The message decryption rule:P|≡P↔KQ,P⊲XK/P⊲XIfP believes that it shares K with Q and sees encrypted X by K, then P sees X.In the following, we apply BAN logic to analyze the TAKACP-1 scheme. Similar analysis can be applied to the TAKACP-2 scheme. According to the analytic procedures of the BAN logic, the proposed TAKACP-1 scheme must satisfy the following goals:Goal (1): U|≡S|≡U↔SKS,Goal (2): U|≡U↔SKS,Goal (3): S|≡U|≡U↔SKS,Goal (4): S|≡U↔SKS.The generic form of the proposed TAKACP-1 scheme is described below.From messageM1, U⟶S: {c, n1}n, x,Tixhn1, < c0, x,Ti(x)>c.From messageM2, S⟶U: n2,TjxhID∗‖n1′, Tj′x,hn2,SKc0.From messageM3, U⟶S: n1⊕n2,SKc0.The idealized form of the proposed TAKACP-1 scheme in the language of formal logic is given below.MessageM1: U⟶S: x,Tix,U↔c0S,U⇔nSU↔cS.MessageM2: S⟶U: n2,Tjx,U↔SKSU↔c0S.MessageM3: U⟶S: n1,n2,U↔SKSU↔c0S.We make the assumptions about the initial state to analyze the proposed TAKACP-1 scheme:H1: U|≡#n1, U|≡#Tix;H2: S|≡#n2, S|≡#Tjx;H3: S|≡U↔cS;H4: U|≡U↔c0S;H5: S|≡U|⇒U↔c0S;H6: U|≡S|⇒U↔SKS;H7: S|≡U|⇒U↔SKS.According to the BAN logic and the assumptions, we give the main proof as follows:From messageM1, we haveS1: S⊲x,Tix,U↔c0S,U⇔nSU↔cS.FromS1, H3, and Rule (1), we haveS2: S|≡U|∼x,Tix,U↔c0S,U⇔nS.FromS2, H2, Rule (2) and Rule (3), we haveS3: S|≡U|≡U↔c0S.FromS3, H5, and Rule (4), we haveS4: S|≡U↔c0S.From messageM2, we haveS5: U⊲n2,Tjx,U↔SKSU↔c0S.FromS5, H4, and Rule (1), we haveS6: U|≡S|∼n2,Tjx,U↔SKS.FromS6, H1, Rule (2), and Rule (3), we haveS7: U|≡S|≡U↔SKS(Goal (1)).FromS7, H6, and Rule (4), we haveS8: U|≡U↔SKS(Goal (2)).From messageM3, we haveS9: S⊲n1,n2,U↔SKSU↔c0S.FromS9, S4, and Rule (1), we haveS10: S|≡U|∼n1,n2,U↔SKS.FromS10, H2, Rule (2), and Rule (3), we haveS11: S|≡U|≡U↔SKS(Goal (3)).FromS11, H7, and Rule (4), we haveS12: S|≡U↔SKS (Goal (4)).


## 6.3. Informal Security Analysis

In this section, we analyze the security of the proposed protocols. We will show that the proposed protocols satisfy the essential security requirements, including the ability to provide medium unlinkability, the contributory property of key agreements, session key security, two-factor secrecy, and free updating of passwords. Furthermore, we confirm that the proposed schemes can withstand replay attacks and password-guessing attacks. In the following, we will not expound the two-factor security since its proof has been given in Part A and Part B of Section4, respectively.


### 6.3.1. Medium Unlinkability

In Part A of Section4, we have demonstrated that our protocols can provide medium unlinkability. Now, we compare the privacy-preserving of our protocols with that of the schemes of Guo-Chang [19], Lin [20], and Sun et al. [24].In the Guo-Chang scheme, since the user identity is encrypted with the master key of the server into the login requestR, any adversary A cannot reveal the user identity. So Pr[AGuess] = 1/N. However, R is unchanged until the user updates the password. Thus, any outside adversary can distinguish whether the users in two authentication sessions are identical. That is, PrA2Decide=1. Thus, we have AdvAnon−Alone(A) = 0 and AdvWeak−Unlin(A)≥1/2. Hence, the Guo-Chang scheme provides anonymity-alone but weak unlinkability. Similarly, since every request of the user contains the unchanged element IM, Sun et al.’s scheme [24] only achieves the property anonymity-alone.The Lin scheme can provide weak unlinkability. Specifically, although the elementsQ and R are kept unchanged, they are transmitted in the ciphertext EvQ,R,T1. Since any outside adversary A2 cannot calculate the key v, they cannot obtain R. But any inside adversary A1 can compute v and acquire Q, R. For every login of the user, the parameters {Q, R} are static until the user changes its password or identity. Thus, A1 can still decide whether different login requests are from the same user or not. Then, we have PrA1,2Decide=1. Hence, AdvMedium-Unlin(A) > 1/2. The Lin scheme cannot provide medium unlinkability.In the proposed protocols,i and x are chosen randomly by every individual user. Therefore, no unchanged login message can be derived by the other registered users. Thus, we obtain that AdvMedium-Unlin(A) = 0. However, each time the user logins to the server, the server validates his or her identity. So, the advantage AdvStrong-Unlin(A) is nonnegligible. The proposed schemes cannot achieve the medium unlinkability.


### 6.3.2. Contributory Property of Key Agreement

In the proposed protocols, the session keySK is h(ID||Ti(x)||Tj(x)||n1||n2||Ti(Tj(x))). Only for the TAKACP-1 scheme, the server can use the method mentioned in [18, 44] to compute i∗ and j∗, thus satisfying Tix=Ti∗x, Tjx=Tj∗x, where Ti∗Tj∗x represents a previous parameter. Since x, Tixand n1 are randomly selected by the user and SK contains Tix and n1, the server still fails to predetermine a session key. Likewise, since Tj(x) and n2 are randomly selected by the server and SK contains Tj(x) and n2, the user cannot predetermine a session key. Notably, neither the server nor the user can determine the specific session key alone in advance. Therefore, the proposed protocols satisfy the contributory property of key agreements.


### 6.3.3. Session Key Security

Firstly, sincei, j, n1 and n2 are selected randomly in every run of the protocols, the session key SK = h(ID||Ti(x)|| Tj(x)||n1||n2||Ti(Tj(x))) is independent of the previously generated session keys. Thus, the proposed protocols can resist against known-key attacks.Secondly, we demonstrate that the proposed protocols can prevent any inside adversary from computing the session keys. Consider that an inside adversaryA1 has eavesdropped the communication messages e,w1,θ1,w2,θ2,θ3 between the user and the server. Since A1 is a legal user of the same server, A1 knows n. However, n1 cannot be derived from e without the server’s private keys p and q, where e=c¯n12 mod n, owing to the quadratic residue assumption. Thus, the adversary cannot still recover x||Ti(x) from w1 without the knowledge of n1, where w1=hn1⊕x‖Tix. Moreover, A cannot work out h(ID||n1). A1 cannot obtain n2||Tj(x) from w2, since w2=hID∗‖n1′⊕n2‖Tjx. Since θ1=hc‖x‖Tix‖c0, θ2=hc0∗‖Tjx⊕hn2‖SK, and θ3=hSK∗‖n1⊕n2‖c0, due to the one-way property of the hash function, A1 cannot determine Ti(x), Tj(x), or SK. In a word, the session key cannot be derived from the messages transmitted over the public channel. The proposed schemes achieve session key security.


### 6.3.4. Free Updating of Password

As described in Part C of Section5, a user can freely update password without any interaction with the server during the password change phase.


### 6.3.5. Resistance to Password Guessing Attacks

In the proposed TAKACP protocols, the login request messagee is information that involves password PW. An inside adversary A1 may guess the password through the equation c = d1⊕h(ID||PW). However, an inside adversary A1 cannot still obtain c from e since e=c¯n12 mod n. Therefore, the proposed protocols can resist password guessing attacks.


### 6.3.6. Resistance to Replay Attacks

The proposed schemes maintain freshness by using two nonces and two chaotic maps. Specifically, the proposed protocols guarantee the freshness of messages by usingTi(x) and n1 in Step A1, Tj(x) and n2 in Step A2, and {Ti(x), Tj(x), n1, n2} in Steps A3 and A4, respectively. Since n1 is protected by the quadratic residues, only the server and the user itself know it. Ti(x), Tj(x), and n2 are contained in w1 and w2. They can be calculated only when one knows the nonce n1. Therefore, the proposed schemes can prevent replaying attacks.


## 6.3.1. Medium Unlinkability

In Part A of Section4, we have demonstrated that our protocols can provide medium unlinkability. Now, we compare the privacy-preserving of our protocols with that of the schemes of Guo-Chang [19], Lin [20], and Sun et al. [24].In the Guo-Chang scheme, since the user identity is encrypted with the master key of the server into the login requestR, any adversary A cannot reveal the user identity. So Pr[AGuess] = 1/N. However, R is unchanged until the user updates the password. Thus, any outside adversary can distinguish whether the users in two authentication sessions are identical. That is, PrA2Decide=1. Thus, we have AdvAnon−Alone(A) = 0 and AdvWeak−Unlin(A)≥1/2. Hence, the Guo-Chang scheme provides anonymity-alone but weak unlinkability. Similarly, since every request of the user contains the unchanged element IM, Sun et al.’s scheme [24] only achieves the property anonymity-alone.The Lin scheme can provide weak unlinkability. Specifically, although the elementsQ and R are kept unchanged, they are transmitted in the ciphertext EvQ,R,T1. Since any outside adversary A2 cannot calculate the key v, they cannot obtain R. But any inside adversary A1 can compute v and acquire Q, R. For every login of the user, the parameters {Q, R} are static until the user changes its password or identity. Thus, A1 can still decide whether different login requests are from the same user or not. Then, we have PrA1,2Decide=1. Hence, AdvMedium-Unlin(A) > 1/2. The Lin scheme cannot provide medium unlinkability.In the proposed protocols,i and x are chosen randomly by every individual user. Therefore, no unchanged login message can be derived by the other registered users. Thus, we obtain that AdvMedium-Unlin(A) = 0. However, each time the user logins to the server, the server validates his or her identity. So, the advantage AdvStrong-Unlin(A) is nonnegligible. The proposed schemes cannot achieve the medium unlinkability.


## 6.3.2. Contributory Property of Key Agreement

In the proposed protocols, the session keySK is h(ID||Ti(x)||Tj(x)||n1||n2||Ti(Tj(x))). Only for the TAKACP-1 scheme, the server can use the method mentioned in [18, 44] to compute i∗ and j∗, thus satisfying Tix=Ti∗x, Tjx=Tj∗x, where Ti∗Tj∗x represents a previous parameter. Since x, Tixand n1 are randomly selected by the user and SK contains Tix and n1, the server still fails to predetermine a session key. Likewise, since Tj(x) and n2 are randomly selected by the server and SK contains Tj(x) and n2, the user cannot predetermine a session key. Notably, neither the server nor the user can determine the specific session key alone in advance. Therefore, the proposed protocols satisfy the contributory property of key agreements.


## 6.3.3. Session Key Security

Firstly, sincei, j, n1 and n2 are selected randomly in every run of the protocols, the session key SK = h(ID||Ti(x)|| Tj(x)||n1||n2||Ti(Tj(x))) is independent of the previously generated session keys. Thus, the proposed protocols can resist against known-key attacks.Secondly, we demonstrate that the proposed protocols can prevent any inside adversary from computing the session keys. Consider that an inside adversaryA1 has eavesdropped the communication messages e,w1,θ1,w2,θ2,θ3 between the user and the server. Since A1 is a legal user of the same server, A1 knows n. However, n1 cannot be derived from e without the server’s private keys p and q, where e=c¯n12 mod n, owing to the quadratic residue assumption. Thus, the adversary cannot still recover x||Ti(x) from w1 without the knowledge of n1, where w1=hn1⊕x‖Tix. Moreover, A cannot work out h(ID||n1). A1 cannot obtain n2||Tj(x) from w2, since w2=hID∗‖n1′⊕n2‖Tjx. Since θ1=hc‖x‖Tix‖c0, θ2=hc0∗‖Tjx⊕hn2‖SK, and θ3=hSK∗‖n1⊕n2‖c0, due to the one-way property of the hash function, A1 cannot determine Ti(x), Tj(x), or SK. In a word, the session key cannot be derived from the messages transmitted over the public channel. The proposed schemes achieve session key security.


## 6.3.4. Free Updating of Password

As described in Part C of Section5, a user can freely update password without any interaction with the server during the password change phase.


## 6.3.5. Resistance to Password Guessing Attacks

In the proposed TAKACP protocols, the login request messagee is information that involves password PW. An inside adversary A1 may guess the password through the equation c = d1⊕h(ID||PW). However, an inside adversary A1 cannot still obtain c from e since e=c¯n12 mod n. Therefore, the proposed protocols can resist password guessing attacks.


## 6.3.6. Resistance to Replay Attacks

The proposed schemes maintain freshness by using two nonces and two chaotic maps. Specifically, the proposed protocols guarantee the freshness of messages by usingTi(x) and n1 in Step A1, Tj(x) and n2 in Step A2, and {Ti(x), Tj(x), n1, n2} in Steps A3 and A4, respectively. Since n1 is protected by the quadratic residues, only the server and the user itself know it. Ti(x), Tj(x), and n2 are contained in w1 and w2. They can be calculated only when one knows the nonce n1. Therefore, the proposed schemes can prevent replaying attacks.


## 7. Security, Functionality, and Performance Comparison

In this section, we will make a comparison with the related TAKACP protocols in terms of security, functionality, and performance.


### 7.1. Security Comparison

We compare the security of our proposed TAKACP schemes with respect to the related authenticated key agreement schemes [19–25, 27–30]. Table 6 summarizes the security properties of the proposed schemes and illustrates the comparison result.Table 6
Security comparison.
S1S2S3S4S5S6S7S8S9S10Fan et al. [22]YesNoYesYesYesYesNoYesYesNoJuang et al. [23]NoNoYesYesNoYesNoYesYesNoSun et al. [24]NoAnonymity-aloneYesYesYesYesYesYesYesNoLi et al. [25]NoNoYesYesYesYesNoYesYesNoMaitra [27]NoMedium unlinkabilityYesNoYesYesYesYesYesNoChaudhry et al. [28]YesNoYesYesYesNo#YesYesNoGuo et al. [19]YesAnonymity-aloneYesYesNoYesNoYesYesNoLin [20]YesWeak unlinkabilityYesYesNoYesNoYesYesNoLee [21]YesMedium unlinkabilityYesYesYesYesNoYesYesNoIrshad et al. [29]YesNoYesYesYesYesYesYesYesNoIrshad et al. [30]NoMedium unlinkabilityYesYesYesYesYesYesYesYesOur protocolsYesMedium unlinkabilityYesYesYesYesYesYesYesYesS1: No password table and verification table; S2: User privacy-preserving; S3: Mutual authentication; S4: Contributory property of key agreement; S5: Session key security; S6: Two-factor secrecy; S7: Free updating of password; S8: Resistance to password guessing attacks; S9: Resistance to replay attack. S10: Key confirmation.As is indicated in Table6, the proposed schemes are highly secure as compared to the related authenticated key agreement schemes [19–25, 27–30]. Especially, the proposed schemes can deal with several imperative security issues which most of the authenticated key agreement protocols based on the Chebyshev polynomials defined on the interval [−1,+1] suffer from. For example, the proposed schemes eliminate their weaknesses of the Lin scheme and the Guo-Chang scheme. In contrast, the authentication protocols [22, 23, 25, 28, 29] cannot preserve user anonymity. The protocol in [27] cannot provide the contributory property of key agreement since the session key is determined by the user. The authentication protocols [19, 20, 23] even cannot provide the session key security. Those protocols presented in [19–21, 23] cannot provide free updating of passwords. The Guo-Chang scheme achieves the anonymity-alone, while the Lin scheme provides weak unlinkability. The proposed schemes achieve the property, medium unlinkability. Note that designing the two-factor authentication protocol with strong unlinkability is still challenging.


### 7.2. Performance Comparison

In this section, we evaluate the performance of the proposed schemes and make a comparison with the related authenticated key agreement schemes [19–25] in terms of the communication cost, storage, and computational overhead.We suppose that the block size of secure symmetric cryptosystems is 128 bits, and the output size of a secure one-way hash function is 256 bits. In order to make the factoring problems infeasible in practical implementation, let the modulen be an integer of 1024 bits. Since the registration of our schemes is based on a one-way hash function, the password length can be 128 bits. Suppose that the size of ID is 64 bits. In our proposed scheme, the cryptographic parameters {c, d} must be stored in the smart card. The length of this information is 1152 + 128 = 1280 bits, where d can be 128 bits and c must be encrypted in nine blocks. The size of the information stored in the smart card is 64 + 64 + 128 × 7 + 1024 = 2048 bits in Fan et al.’s scheme [22], 128 × 3 + 128 + 64 + 64+256 = 896 bits in Juang et al.’s scheme [23], 128 + 128 × 3 = 512 bits in Sun et al.’s scheme [24], 128 × 3 + 128 + 64 + 64 = 640 bits in Li et al.’s scheme [25], 128 × 3 + 256 + 256 = 896 bits in Guo et al.’s scheme [19], 128 × 3 + 256 + 128 + 128 = 896 bits in Lin’s scheme [20], and 128 × 2 + 128 + 128 = 512 bits in Lee’s scheme [21]. As is shown in Table 7, during the registration, the smart card needs a little larger storage space in the proposed schemes than those in other schemes [19–25, 28, 29]. However, it is practically insignificant considering the fact that most current mobile devices, including 4G cellular phones, personal digital assistants (PDAs), and notebook computers, have over a few hundred MB or a few GB of available memory.Table 7
Storage cost and communication cost comparison.
SC1 (in bits)SC2∗SC2 (in bits)SC3∗SC3 (in bits)SC4∗SC4 (in bits)Fan et al. [22]2048351231856##Juang et al. [23]89635783153652560Sun et al. [24]51221923154800Li et al. [25]64015763320055248Maitra [27]1600117922441600Chaudhry et al. [28]512151232624##Guo et al. [19]89613202179221408Lin [20]89613202140821280Lee [21]51213202108821440Irshad et al. [29]768113442108800Irshad et al. [30]1024113445518400Our protocols128013203229400SC1 denotes the storage cost of the smart card in the registration phase. SC2∗ denotes the round number of message transmission in the registration phase. SC2 denotes the total size of the transmitted message in the registration phase. SC3∗ denotes the number of message transmissions in the authenticated key exchange phase. SC3 denotes the total size of the transmitted message in the authenticated key exchange phase. SC4∗ denotes the number of the message transmission in the password change phase. SC4 denotes the total size of transmitted message in the password change phase. # denotes that the scheme does not provide the functionality of password updating.In our proposed schemes, the messages transmitted in the registration phase are {ID, d}. The communication cost of the login protocol is 64 + 256 = 320 bits. The total size of messages transmitted during the authenticated key exchange phase for cryptographic parameters e,w1,θ1, w2,θ2, and {θ3} is (1024 + 256 + 256) + (256 + 256) + 256 = 2294 bits. The authenticated key exchange phase requires three rounds of message transmission. During the password change, the proposed schemes require no message transmission between the user and the server since the server is not involved with the phase. Let the module number of the elliptic curve be an integer of 163 bits in Juang et al.’s scheme [23] and Sun et al.’s scheme [24]. Let the time stamp be a string of 32 bits in Guo et al.’s scheme [19], Lin’s scheme [20], and Lee’s scheme [21]. In Juang et al.’s scheme, the communication cost of the login phase about cryptographic parameters bi,EVie, {u, Ms}, and {MU} is (384 + 384) + (256 + 256) + 256 = 1536 bits, where EVie is the encryption of three blocks. The password change phase of Juang et al.’s scheme [23] requires that the user needs to agree on a session key with the server through the log-in phase in advance and then transmit the messages ESkIDi,hPWi∗‖b∗and ESkbi∗, respectively. Hence, the size of the message transmitted in the password change phase of Juang et al.’s scheme is 2560 bits. By similar analysis, we can evaluate the communication cost of other related schemes [19–22, 24, 25, 27–30]. The communication cost and storage cost among our schemes and related schemes are shown in Table 7.As can be seen from Table7, during the authenticated key exchange phase, the size of the message transmitted between the user and the server in the proposed schemes is a little larger than the size of the message in the schemes [19–24,29]. However, the proposed schemes can provide the user with stronger privacy protection than the schemes in [22–24]. It also can achieve the session key confirmation, but the schemes [19–21,29] cannot provide the function. Moreover, the scheme in [29] cannot preserve the anonymity of the user. During the password change phase in the proposed schemes, no message transmission between the user and the serve is required. Compared with the proposed scheme, the server of the other schemes [19–23,25] is involved with the password change. Furthermore, quite a few messsages will be transmitted between the user and the server.Now, we evaluate the computation cost of our protocols and related protocols. LetTc denote the time to execute a Chebyshev polynomial computing. Let Ts represent the time to execute a symmetric encryption/decryption operation. We refer to Th as the time to execute a one-way hash function operation. Let Tm denote the time to execute a scalar multiplication in the elliptic curve group. Te represents the time to execute one exponentiation operation. We denote by Tsq the time to execute a squaring operation. Tcrt represents the time to solve the square root through the CRT method. Since the XOR operations cost very little, we neglect it. Since a user is required to register with a server one time, the computational cost in the registration phase is not listed in Table 8.Table 8
Computation overhead comparison.
C1C2C3C4Fan et al. [22]4Th + 1Tsq ≈ 0.0175 ms3Th + 1Ts + 1Tcrt ≈ 0.0238 ms##Juang et al. [23]3Th + 3Ts ≈ 0.021 ms4Th + 6Ts + 1Tm ≈ 0.186 ms14Th  + 5Ts ≈ 0.1015 ms52Th + 5Ts ≈ 0.2345 msSun et al. [24]4Th + 2Tm ≈ 0.232 ms4Th + 1Ts + 1Tm ≈ 0.1335 ms2Th ≈ 0.007 ms0Li et al. [25]8Th + 4Ts ≈ 0.0385 ms10Th + 10Ts + 1Tm ≈ 0.249 ms21Th + 6Ts ≈ 0.1365 ms70Th + 9Ts ≈ 0.3395 msMaitra [27]8Th + 6te + 1tm ≈ 157.069 ms8Th + 4te + 1tm + 1tinv ≈ 150.029 ms6Th ≈ 0.042 ms0Chaudhry et al. [28]1Tp + 6Th + 3Tm + 2Ta + 2Te + 2tm + 1tinv ≈ 183.7542 ms3Tp + 5Th + 4Tm + 3Ta + 2Te + 1tm ≈ 462.9762 ms##Guo et al. [19]2Th + 2Ts + 3Tc ≈ 0.3925 ms2Th + 2Ts + 3Tc ≈ 0.3925 ms2Th + 1Ts + 2Tc ≈ 0.2542 ms3Ts + 1Tc ≈ 0.153 msLin [20]3Th + 2Ts + 2Tc ≈ 0.2745 ms2Th + 3Ts + 3Tc ≈ 0.403 ms2Th + 1Ts + 1Tc ≈ 0.1327 ms3Ts + 1Tc ≈ 0.153 msLee [21]3Th + 1Ts + 3Tc ≈ 0.3945 ms2Th + 2Ts + 3Tc ≈ 0.3925 ms4Th + 1Ts + 2Tc ≈ 0.2675 ms2Th + 3Ts + 1Tc ≈ 0.16 msIrshad et al. [29]7Th + 4Tc ≈ 0.5105 ms4Th + 3Tc ≈ 0.3785 ms6Th ≈ 0.042 ms0Irshad et al. [30]11Th + 3Tc ≈ 0.4030 ms7Th + 2Tc ≈ 0.2675 ms8Th ≈ 0.056 ms0Our protocols9Th + 1Tsq + 1Tc ≈ 0.1565 ms7Th + 1Tcrt  + 1Ts + 1Tc ≈ 0.1593 ms2Th ≈ 0.014 ms0C1 denotes the computational cost of a user in the authenticated key exchange phase. C2 refers to the computational cost of the server in the authenticated key exchange phase. C3/C4 represents the computational cost of the user/server during the password change phase. N/A represents no requirement of computation. # denotes that the scheme does not provide the functionality of password updating.The proposed protocols protect the random numbern1 and the shared secret c by using the quadratic residues. The user requires one modular squaring operation, and the server requires one square root solving operation through the CRT and one symmetric decryption. The proposed protocols require no symmetric encryption operation. It needs only one Chebyshev polynomial computing in the user, which is less than one (two) Chebyshev polynomial computing than those in the Lin scheme (the Guo-Chang scheme). The proposed protocol requires one symmetric encryption operation and one Chebyshev polynomial computing in the server, which is less than two (one) symmetric encryption operations and two (two) Chebyshev polynomial computing than those in the Lin scheme (the Guo-Chang scheme). In the proposed protocols, one modular squaring operation does not affect user efficiency since the implementation of one modular squaring [35] can be reduced to only a few hundred gate-equivalents. In practical implementation of the proposed protocols, to efficiently compute the square roots in Zn∗, the server does the pre-computation [22]. To be specific, S pre-computes and stores the inverse p’ of p modular q and the inverse q’ of q modular p. In order to compute the square root of a, one first computes a1=ap+1/4 mod p and a2=aq+1/4, then he or she can calculate rapidly the four square roots of a in Zn∗, for example, (p’pa2 + q’qa1) mod n. Due to p ≡ q ≡ 3 (mod 4), the computation of (a1, a2) requires about the same time as performing a modular exponentiation computation in Zn∗. Consequently, we have 1Tcrt≈1Te.We have executed these operations by utilizing PyCrypto library in Python language in the computer with 16 GB RAM and a clock speed of 3.60 GHz. The time cost of all operations is as follows:Th ≈ 0.0035 ms, Tc ≈ 0.1215 ms, Ts ≈ 0.0105 ms, Tm ≈ 0.109 ms, Tsq ≈ 0.0035 ms, and Tcrt ≈ 0.0028 ms. Table 8 summarizes the computation cost of our scheme with those described in [19–25, 27–30]. As shown in Table 8 and Figure 6, during the authenticated key exchange phase, both the user and the server in the proposed protocols are required at the lowest computation cost among these two-factor authentication protocols [19–21, 29, 30] based on chaotic maps. In addition, the proposed schemes require no involvement of the server during the password change phase. Moreover, in comparison with the related schemes [19–25], the user is required at a very low computation cost during the password change phase of the proposed schemes.Figure 6
Computation overhead comparison of TAKACP protocols (in milliseconds).


## 7.1. Security Comparison

We compare the security of our proposed TAKACP schemes with respect to the related authenticated key agreement schemes [19–25, 27–30]. Table 6 summarizes the security properties of the proposed schemes and illustrates the comparison result.Table 6
Security comparison.
S1S2S3S4S5S6S7S8S9S10Fan et al. [22]YesNoYesYesYesYesNoYesYesNoJuang et al. [23]NoNoYesYesNoYesNoYesYesNoSun et al. [24]NoAnonymity-aloneYesYesYesYesYesYesYesNoLi et al. [25]NoNoYesYesYesYesNoYesYesNoMaitra [27]NoMedium unlinkabilityYesNoYesYesYesYesYesNoChaudhry et al. [28]YesNoYesYesYesNo#YesYesNoGuo et al. [19]YesAnonymity-aloneYesYesNoYesNoYesYesNoLin [20]YesWeak unlinkabilityYesYesNoYesNoYesYesNoLee [21]YesMedium unlinkabilityYesYesYesYesNoYesYesNoIrshad et al. [29]YesNoYesYesYesYesYesYesYesNoIrshad et al. [30]NoMedium unlinkabilityYesYesYesYesYesYesYesYesOur protocolsYesMedium unlinkabilityYesYesYesYesYesYesYesYesS1: No password table and verification table; S2: User privacy-preserving; S3: Mutual authentication; S4: Contributory property of key agreement; S5: Session key security; S6: Two-factor secrecy; S7: Free updating of password; S8: Resistance to password guessing attacks; S9: Resistance to replay attack. S10: Key confirmation.As is indicated in Table6, the proposed schemes are highly secure as compared to the related authenticated key agreement schemes [19–25, 27–30]. Especially, the proposed schemes can deal with several imperative security issues which most of the authenticated key agreement protocols based on the Chebyshev polynomials defined on the interval [−1,+1] suffer from. For example, the proposed schemes eliminate their weaknesses of the Lin scheme and the Guo-Chang scheme. In contrast, the authentication protocols [22, 23, 25, 28, 29] cannot preserve user anonymity. The protocol in [27] cannot provide the contributory property of key agreement since the session key is determined by the user. The authentication protocols [19, 20, 23] even cannot provide the session key security. Those protocols presented in [19–21, 23] cannot provide free updating of passwords. The Guo-Chang scheme achieves the anonymity-alone, while the Lin scheme provides weak unlinkability. The proposed schemes achieve the property, medium unlinkability. Note that designing the two-factor authentication protocol with strong unlinkability is still challenging.


## 7.2. Performance Comparison

In this section, we evaluate the performance of the proposed schemes and make a comparison with the related authenticated key agreement schemes [19–25] in terms of the communication cost, storage, and computational overhead.We suppose that the block size of secure symmetric cryptosystems is 128 bits, and the output size of a secure one-way hash function is 256 bits. In order to make the factoring problems infeasible in practical implementation, let the modulen be an integer of 1024 bits. Since the registration of our schemes is based on a one-way hash function, the password length can be 128 bits. Suppose that the size of ID is 64 bits. In our proposed scheme, the cryptographic parameters {c, d} must be stored in the smart card. The length of this information is 1152 + 128 = 1280 bits, where d can be 128 bits and c must be encrypted in nine blocks. The size of the information stored in the smart card is 64 + 64 + 128 × 7 + 1024 = 2048 bits in Fan et al.’s scheme [22], 128 × 3 + 128 + 64 + 64+256 = 896 bits in Juang et al.’s scheme [23], 128 + 128 × 3 = 512 bits in Sun et al.’s scheme [24], 128 × 3 + 128 + 64 + 64 = 640 bits in Li et al.’s scheme [25], 128 × 3 + 256 + 256 = 896 bits in Guo et al.’s scheme [19], 128 × 3 + 256 + 128 + 128 = 896 bits in Lin’s scheme [20], and 128 × 2 + 128 + 128 = 512 bits in Lee’s scheme [21]. As is shown in Table 7, during the registration, the smart card needs a little larger storage space in the proposed schemes than those in other schemes [19–25, 28, 29]. However, it is practically insignificant considering the fact that most current mobile devices, including 4G cellular phones, personal digital assistants (PDAs), and notebook computers, have over a few hundred MB or a few GB of available memory.Table 7
Storage cost and communication cost comparison.
SC1 (in bits)SC2∗SC2 (in bits)SC3∗SC3 (in bits)SC4∗SC4 (in bits)Fan et al. [22]2048351231856##Juang et al. [23]89635783153652560Sun et al. [24]51221923154800Li et al. [25]64015763320055248Maitra [27]1600117922441600Chaudhry et al. [28]512151232624##Guo et al. [19]89613202179221408Lin [20]89613202140821280Lee [21]51213202108821440Irshad et al. [29]768113442108800Irshad et al. [30]1024113445518400Our protocols128013203229400SC1 denotes the storage cost of the smart card in the registration phase. SC2∗ denotes the round number of message transmission in the registration phase. SC2 denotes the total size of the transmitted message in the registration phase. SC3∗ denotes the number of message transmissions in the authenticated key exchange phase. SC3 denotes the total size of the transmitted message in the authenticated key exchange phase. SC4∗ denotes the number of the message transmission in the password change phase. SC4 denotes the total size of transmitted message in the password change phase. # denotes that the scheme does not provide the functionality of password updating.In our proposed schemes, the messages transmitted in the registration phase are {ID, d}. The communication cost of the login protocol is 64 + 256 = 320 bits. The total size of messages transmitted during the authenticated key exchange phase for cryptographic parameters e,w1,θ1, w2,θ2, and {θ3} is (1024 + 256 + 256) + (256 + 256) + 256 = 2294 bits. The authenticated key exchange phase requires three rounds of message transmission. During the password change, the proposed schemes require no message transmission between the user and the server since the server is not involved with the phase. Let the module number of the elliptic curve be an integer of 163 bits in Juang et al.’s scheme [23] and Sun et al.’s scheme [24]. Let the time stamp be a string of 32 bits in Guo et al.’s scheme [19], Lin’s scheme [20], and Lee’s scheme [21]. In Juang et al.’s scheme, the communication cost of the login phase about cryptographic parameters bi,EVie, {u, Ms}, and {MU} is (384 + 384) + (256 + 256) + 256 = 1536 bits, where EVie is the encryption of three blocks. The password change phase of Juang et al.’s scheme [23] requires that the user needs to agree on a session key with the server through the log-in phase in advance and then transmit the messages ESkIDi,hPWi∗‖b∗and ESkbi∗, respectively. Hence, the size of the message transmitted in the password change phase of Juang et al.’s scheme is 2560 bits. By similar analysis, we can evaluate the communication cost of other related schemes [19–22, 24, 25, 27–30]. The communication cost and storage cost among our schemes and related schemes are shown in Table 7.As can be seen from Table7, during the authenticated key exchange phase, the size of the message transmitted between the user and the server in the proposed schemes is a little larger than the size of the message in the schemes [19–24,29]. However, the proposed schemes can provide the user with stronger privacy protection than the schemes in [22–24]. It also can achieve the session key confirmation, but the schemes [19–21,29] cannot provide the function. Moreover, the scheme in [29] cannot preserve the anonymity of the user. During the password change phase in the proposed schemes, no message transmission between the user and the serve is required. Compared with the proposed scheme, the server of the other schemes [19–23,25] is involved with the password change. Furthermore, quite a few messsages will be transmitted between the user and the server.Now, we evaluate the computation cost of our protocols and related protocols. LetTc denote the time to execute a Chebyshev polynomial computing. Let Ts represent the time to execute a symmetric encryption/decryption operation. We refer to Th as the time to execute a one-way hash function operation. Let Tm denote the time to execute a scalar multiplication in the elliptic curve group. Te represents the time to execute one exponentiation operation. We denote by Tsq the time to execute a squaring operation. Tcrt represents the time to solve the square root through the CRT method. Since the XOR operations cost very little, we neglect it. Since a user is required to register with a server one time, the computational cost in the registration phase is not listed in Table 8.Table 8
Computation overhead comparison.
C1C2C3C4Fan et al. [22]4Th + 1Tsq ≈ 0.0175 ms3Th + 1Ts + 1Tcrt ≈ 0.0238 ms##Juang et al. [23]3Th + 3Ts ≈ 0.021 ms4Th + 6Ts + 1Tm ≈ 0.186 ms14Th  + 5Ts ≈ 0.1015 ms52Th + 5Ts ≈ 0.2345 msSun et al. [24]4Th + 2Tm ≈ 0.232 ms4Th + 1Ts + 1Tm ≈ 0.1335 ms2Th ≈ 0.007 ms0Li et al. [25]8Th + 4Ts ≈ 0.0385 ms10Th + 10Ts + 1Tm ≈ 0.249 ms21Th + 6Ts ≈ 0.1365 ms70Th + 9Ts ≈ 0.3395 msMaitra [27]8Th + 6te + 1tm ≈ 157.069 ms8Th + 4te + 1tm + 1tinv ≈ 150.029 ms6Th ≈ 0.042 ms0Chaudhry et al. [28]1Tp + 6Th + 3Tm + 2Ta + 2Te + 2tm + 1tinv ≈ 183.7542 ms3Tp + 5Th + 4Tm + 3Ta + 2Te + 1tm ≈ 462.9762 ms##Guo et al. [19]2Th + 2Ts + 3Tc ≈ 0.3925 ms2Th + 2Ts + 3Tc ≈ 0.3925 ms2Th + 1Ts + 2Tc ≈ 0.2542 ms3Ts + 1Tc ≈ 0.153 msLin [20]3Th + 2Ts + 2Tc ≈ 0.2745 ms2Th + 3Ts + 3Tc ≈ 0.403 ms2Th + 1Ts + 1Tc ≈ 0.1327 ms3Ts + 1Tc ≈ 0.153 msLee [21]3Th + 1Ts + 3Tc ≈ 0.3945 ms2Th + 2Ts + 3Tc ≈ 0.3925 ms4Th + 1Ts + 2Tc ≈ 0.2675 ms2Th + 3Ts + 1Tc ≈ 0.16 msIrshad et al. [29]7Th + 4Tc ≈ 0.5105 ms4Th + 3Tc ≈ 0.3785 ms6Th ≈ 0.042 ms0Irshad et al. [30]11Th + 3Tc ≈ 0.4030 ms7Th + 2Tc ≈ 0.2675 ms8Th ≈ 0.056 ms0Our protocols9Th + 1Tsq + 1Tc ≈ 0.1565 ms7Th + 1Tcrt  + 1Ts + 1Tc ≈ 0.1593 ms2Th ≈ 0.014 ms0C1 denotes the computational cost of a user in the authenticated key exchange phase. C2 refers to the computational cost of the server in the authenticated key exchange phase. C3/C4 represents the computational cost of the user/server during the password change phase. N/A represents no requirement of computation. # denotes that the scheme does not provide the functionality of password updating.The proposed protocols protect the random numbern1 and the shared secret c by using the quadratic residues. The user requires one modular squaring operation, and the server requires one square root solving operation through the CRT and one symmetric decryption. The proposed protocols require no symmetric encryption operation. It needs only one Chebyshev polynomial computing in the user, which is less than one (two) Chebyshev polynomial computing than those in the Lin scheme (the Guo-Chang scheme). The proposed protocol requires one symmetric encryption operation and one Chebyshev polynomial computing in the server, which is less than two (one) symmetric encryption operations and two (two) Chebyshev polynomial computing than those in the Lin scheme (the Guo-Chang scheme). In the proposed protocols, one modular squaring operation does not affect user efficiency since the implementation of one modular squaring [35] can be reduced to only a few hundred gate-equivalents. In practical implementation of the proposed protocols, to efficiently compute the square roots in Zn∗, the server does the pre-computation [22]. To be specific, S pre-computes and stores the inverse p’ of p modular q and the inverse q’ of q modular p. In order to compute the square root of a, one first computes a1=ap+1/4 mod p and a2=aq+1/4, then he or she can calculate rapidly the four square roots of a in Zn∗, for example, (p’pa2 + q’qa1) mod n. Due to p ≡ q ≡ 3 (mod 4), the computation of (a1, a2) requires about the same time as performing a modular exponentiation computation in Zn∗. Consequently, we have 1Tcrt≈1Te.We have executed these operations by utilizing PyCrypto library in Python language in the computer with 16 GB RAM and a clock speed of 3.60 GHz. The time cost of all operations is as follows:Th ≈ 0.0035 ms, Tc ≈ 0.1215 ms, Ts ≈ 0.0105 ms, Tm ≈ 0.109 ms, Tsq ≈ 0.0035 ms, and Tcrt ≈ 0.0028 ms. Table 8 summarizes the computation cost of our scheme with those described in [19–25, 27–30]. As shown in Table 8 and Figure 6, during the authenticated key exchange phase, both the user and the server in the proposed protocols are required at the lowest computation cost among these two-factor authentication protocols [19–21, 29, 30] based on chaotic maps. In addition, the proposed schemes require no involvement of the server during the password change phase. Moreover, in comparison with the related schemes [19–25], the user is required at a very low computation cost during the password change phase of the proposed schemes.Figure 6
Computation overhead comparison of TAKACP protocols (in milliseconds).


## 8. Conclusion

In this paper, we examine the limitations of Lin’s chaotic map-based authenticated key agreement protocol. We have proposed two TAKACP protocols with key confirmation. Compared with the Lin protocol and the Guo-Chang protocol, the proposed protocols achieve the following additional merits: session key secrecy, medium unlinkability, and free updating of passwords. The proposed protocols with the enhanced security do not affect the user’s or the server’s efficiency. Therefore, the proposed protocols are highly feasible for practical implementation.



---

*Source: 6697898-2021-06-03.xml*