# Efficient Hierarchical Authentication Protocol for Multiserver Architecture

Authors: Jiangheng Kou; Mingxing He; Ling Xiong; Zeqiong Lv
Journal: Security and Communication Networks
 (2020)

---

## Abstract

The multiserver architecture authentication (MSAA) protocol plays a significant role in achieving secure communications between devices. In recent years, researchers proposed many new MSAA protocols to gain more functionality and security. However, in the existing studies, registered users can access to all registered service providers in the system without any limitation. To ensure that the system can restrict users that are at different levels and can access to different levels of service providers, we propose a new lightweight hierarchical authentication protocol for multiserver architecture using a Merkle tree to verify user’s authentication right. The proposed protocol has hierarchical authentication functionality, high security, and reasonable computation and communication costs. Moreover, the security analysis demonstrates that the proposed protocol satisfies the security requirements in practical applications, and the proposed protocol is provably secure in the general security model.


---

## Body

## 1. Introduction

Rapid advances in wireless communication technologies bring convenience to our lives. With an increasing number of users and services, the single-server architecture authentication protocols can no longer meet people’s various requirements [1]. Multiserver architecture authentication (MSAA) protocols have emerged and been widely used in the Internet of things, wireless sensor networks, smart grid, cloud computing, and mobile payment. Because MSAA protocols have better properties than single-server architecture authentication protocols [2, 3], it becomes a hot spot in current research.However, due to the openness of the multiserver environment, an adversary can easily control communication channels and carries out many types of attacks such as intercept, modify, replay, and delay messages between multiple parties. For defending these attacks, researchers proposed many authentication protocols for the multiserver architecture that are using cryptographic methods to secure communication between different parties. New protocols also have lower computation and communication costs than the previous protocols. Currently, MSAA protocols can be divided into two types by whether it involves the registration centerRC at the authentication phase. The first type is MSAA protocols with the RC involving at the authentication phase (MSAA1) [1, 2, 4–11], and the second type is MSAA protocols without RC involving at the authentication phase (MSAA2) [12–23]. In MSAA1 protocols,RC verifies every mutual authentication process, which makes it a bottleneck in MSAA1 protocols. The communication cost in MSAA1 protocols is significantly increased compared to MSAA2 protocols. To address these drawbacks, researchers proposed many MSAA2 protocols which have more efficiency and security than the existing MSAA1 protocols [14].Currently, hierarchical authentication functionality is missing in the existing MSAA2 protocols. When a user registered atRC, he/she can authenticate with all registered service providers [24] and access to their services. However, there are many different users and service providers in this system, and the user’s level is different from each other, and low-level users should not successfully authenticate with high-level service providers and access to their services. Besides, there should be some high-level service providers only providing service for some particular users such as VIP users. In general, the MSAA protocols with the hierarchical authentication functionality will have flexibility in managing user authentication rights and access capabilities. The hierarchical authentication functionality has been achieved in the MSAA1 protocol [2, 4]. In the MSAA1 protocol, an RC is required at the authentication phase. Therefore, RC can verify the user’s authentication rights to determine whether he/she can access to service providers that are at a particular level. However, MSAA1 protocols have several drawbacks such as unreasonable communication cost that we showed earlier, making the whole system inefficient. Suppose we apply the existing MSAA2 protocols to the above environment; there should be multiple RCs to manage users and service providers at different levels. Users and service providers need to store various certificates from different RCs. The missing of hierarchical authentication functionality in the existing MSAA2 protocols motivates us to design a new lightweight hierarchical authentication protocol for multiserver architecture.The proposed protocol uses a self-constructed Merkle tree to achieve hierarchical authentication functionality. In the proposed protocol, a session key is established between service providers and users without involvingRC; this significantly reduces communication cost and makes the authentication process faster. The proposed protocol can meet the security requirements of the multiserver architecture and is provably secure in general security model.The remainder of this paper is organized as follows. Section2 discusses the related work. Section 3 describes preliminaries. In Section 4, we show the details of the proposed protocol. Section 5 gives out the formal security proof of the proposed protocol. Section 6 presents a comparison of the proposed protocol with other related protocols on security, computation, and communication costs. Section 7 concludes the paper.


## 2. Related Work

Li et al. [1] proposed a new multiserver architecture authentication (MSAA) protocol for cloud computing based on the identity-based model. Shao and Chin [4] proposed an authentication protocol for multiserver architecture but failed to resist the server spoofing and the impersonation attacks. He and Wang [5] constructed the first genuinely three-factor authentication protocol for the multiserver architecture, but their protocol is vulnerable to the known session-specific temporary information attack and impersonation attack. Odelu et al. [6] proposed an improved protocol to solve the security drawbacks in [5]. Xie et al. [7] proposed a two-factor authentication protocol. However, Xie’s protocol cannot resist the lost smart card attack and the offline dictionary guessing attack. To address the drawbacks, Chandrakar and Om [8] proposed a new security-enhanced three-factor protocol. Feng et al. [9] proposed an enhanced biometrics-based authentication protocol that can provide user anonymity. Amin et al. [10] proposed a lightweight authentication protocol that has lower computational and communication costs. Cui et al. [11] proposed an efficient protocol that only uses nonce, exclusive-OR operation, and one-way hash function; their protocol greatly reduces the computation cost. However, in this kind of protocol, they all need the help of an online registration center to achieve mutual authentication, which increases the communication cost.In order to solve the drawbacks in the first type protocol, Choi et al. [12] proposed the first MSAA protocol without the online registration center. Tseng et al. [13] proposed a list-free ID-based authentication protocol using bilinear pairings for the multiserver architecture. However, Tseng et al. [13] cannot provide credentials privacy and untraceability for users. Recently, Odelu et al. [14] and He et al. [15] proposed new protocols that reduce the computation and communication costs. Irshad et al. [16] found protocol in [17] cannot achieve desired security goals. Therefore, they proposed an improved multiserver authentication protocol for distributed mobile cloud computing services. Afterward, Xiong et al. [18] found protocol in [16] has unreasonable computation cost, so they proposed an enhanced protocol for distributed mobile cloud. At the same time, Xiong et al. [19] proposed a new lightweight anonymous authentication protocol to reduce computation and communication costs. Barman et al. [25] used fuzzy commitment approach to secure the information stored on personal device. Kumari et al. [20] proposed a concept of the fuzzy extractor to provide the proper matching of biometric patterns. Xu et al. [21] proposed a new protocol that provides untraceability. Jiang et al. [22] performed a security analysis to the protocol in [17], pointing out that it is vulnerable to the impersonation attack. Chatterjee et al. [23] proposed a biometric-based protocol using the chaotic map and enhanced the security for multiserver architecture. We summarize techniques, advantages, and disadvantages that the existing protocols used in Table 1.Table 1
Related work summaries.
Protocol
Technique
Advantage
Disadvantage
[1]
Identity-based
Lightweight and efficient
Cannot provide user anonymity
[4]
Identity-based
Provides user anonymity, resists server spoofing attack and impersonation attack, etc.
Cannot resist server spoofing attack and impersonation attacks
[5]
Biometrics-based
First truly three-factor authenticated scheme
Cannot resist known session-specific temporary attack and the impersonation attack
[6]
Biometrics-based
Provides secure authentication and resists passive and active attacks
Needs registration center online for authentication
[7]
Identity-based
Security enhanced and supports smart card revocation and password update without centralized storage
Cannot resist the lost smart card attack and the offline dictionary guessing attack
[8]
Biometrics-based
Efficient in terms of computation cost, communication cost, and resists smart card storage cost
High maintenance cost
[9]
Biometrics-based
Incurs low overhead, suitable for deployment at mobile devices
Needs registration center online for authentication
[10]
Two-factor-based
Security enhanced, lightweight, and efficient
Needs registration center online for authentication
[11]
Identity-based
Resists the server spoofing attack
Needs registration center online for authentication
[12]
Identity-based
Does not need registration center online for authentication
Cannot provide hierarchical authentication
[13]
Identity-based
Provides black/white list-free and simple revocation mechanism
Cannot provide credentials privacy and untraceability
[14]
Identity-based
Provides SK-security and strong credentials’ privacy
Cannot provide hierarchical authentication
[15]
Identity-based
Uses the self-certified public key cryptography and has lower computation and communication costs
Cannot provide hierarchical authentication
[16]
Two-factor-based
Resists server spoofing attack, desynchronization attack, and denial-of-service attack
Cannot provide hierarchical authentication
[17]
Two-factor-based
Reduces authentication processing time required by communication and computation between cloud service providers and traditional trusted third-party service
Cannot resist service provider impersonation attack and has no user revocation facility
[18]
Biometrics-based
Provides three-factor security, user revocation, and reregistration
Cannot provide hierarchical authentication
[19]
Biometrics-based
User anonymity, perfect forward secrecy, and resistance to desynchronization attack
Cannot provide hierarchical authentication
[21]
Two-factor-based
Provides user untraceability and perfect forward security
Cannot provide hierarchical authentication
[23]
Biometric-based
Uses chaotic map to improve efficiency
Cannot provide hierarchical authentication


## 3. Preliminaries

In this section, we introduce preliminaries of the proposed protocol.LetG1 and G2 be an additive cyclic group and a multiplicative cyclic group, both of them have a large prime order q. Let e^:G1×G1⟶G2 denote a bilinear map. Suppose P is a generator of G1, g is a generator of G2. A bilinear map e^ has the following properties:(i)
Bilinearity: for allP,Q∈G1 and for all a,b∈Zq∗, e^aP,bQ=e^P,Qab(ii)
Computability: there exists an algorithm that can successfully computee^P,Q for all P,Q∈G1(iii)
Nondegeneracy: there existsP,Q∈G1 such that e^P,Q≠1, where 1 is the identity element of G2We list the hard problems that we used in the proposed protocol as follows:(i)
Discrete logarithm (DL) problem: given an elementx∈G2, it is hard to compute a∈Zq∗ such that x=ga(ii)
Computational Diffie–Hellman (CDH) problem: given two elementsga,gb∈G2, it is hard to compute ga⋅b∈G2, where a and b are unknown and randomly chosen from Zq∗(iii)
Modified Bilinear Inverse Diffie–Hellman withk value (k-mBIDH) problem [12]: given k elements α1,α2,…,αkαi∈Zq∗ and k+2 elements τ⋅P,η⋅P,1/τ+α1⋅P,1/τ+α2⋅P,…,1/τ+αk⋅P each of them is in G1, it is hard to compute e^P,Pη/τ+α, where α∉α1,α2,…,αk and τ and η are two unknown elements in Zq∗A security system parameter generator used in the proposed protocol is introduced below.Gen
⋅: the system parameter generator takes a security parameter n and outputs system parameters, a bilinear map, an elliptic curve, a multiplicative group, etc. Intuitively, the system parameters will be publicly known.The notations used in the proposed protocol are listed in Table2.Table 2
Notations used in the proposed protocol.
Notation
Description
RC
The registration center
U
i
Theith user
S
j
Thejth service provider
A
The adversary
ID
U
i
The identity ofith user
ID
S
j
The identity ofjth service provider
pw
The password of a user
b
i
Theith user’s personal biometrics
σ
i
The biometric key
e
The private key expire parameter
r
^
1
,
r
^
2
Random numbers fromZq∗
sk
The session key
Concatenation operation
T
The authentication right tree
T
^
The authentication right tree on service provider side
a
i
,
a
^
i
The authentication right parameters
K
R
i
Theith node of the authentication right tree
L
i
The subnode ofKRi
f
⋅
The fuzzy-extractor generation procedure
f
⋅
−
1
The deterministic reproduction procedure
H
i
⋅
Secure one-way hash functions
IDRL
ID revocation list


## 4. The Proposed Protocol

### 4.1. RC Initialization Phase

Registration center runs the generation functionGen1n which takes a security parameter n∈Z+ and outputs parameters as follows:(1)
RC chooses two bilinear map groups G1 and G2 with a prime order q, the generator P∈G1 and g=e^P,P∈G2, where e^:G1×G1⟶G2 is a bilinear map.(2)
RC chooses cryptographic hash functions H1:0,1∗⟶Zq∗, H2:G2⟶Zq∗, H3:0,1∗⟶G1, H4:0,1∗⟶0,1n.(3)
RC chooses a random number s⟵RZq∗ as the master key, computes the corresponding public key Ppub=sP∈G1, and constructs an authentication right tree T as Figure 1. The detail of the tree will be described in Section 4.5. Finally, RC publishes G1,G2,q,e^,P,Ppub,g,H1,H2,H3,H4.Figure 1
Authentication right tree.


### 4.2. User Registration Phase

If a userUi wants to register with the registration center RC, the following steps will be executed. The main steps are provided in Table 3.(1)
Ui sends his/her identity IDUi to RC via a secure channel.(2)
RC selects an authentication parameter KRi∈T and computes the Ui’s private key dUi=1/s+H1IDUieKRi⋅P, where e is the expire date of the private key and T is an authentication right tree. RC chooses a parameter ai∈T and sends dUi,ai to Ui via a secure channel.(3)
Ui computes σi,θi⟵fbi using the fuzzy-extractor generation procedure f⋅ [26], where σi is a biometric key, θi is a public reproduction parameter, and bi is his/her personal biometrics. Ui computes A=dUi⊕H3pwσi and uses the widely implemented fuzzy-verifier technique [27, 28] to compute B=H4H4IDUiH4pwσimodn0, where pw is his/her password and n0 is the integer that defines in [27]. Finally, Ui stores ai,θi,A,B,e,f⋅,f−1⋅,t,H1,H2,H3,H4 on its mobile device, where t is the threshold in fuzzy extractor, f⋅ is the probabilistic generation procedure for outputting σi, and θi, f−1⋅ is the deterministic reproduction procedure that can recover σi and θi from a new personal biometrics input.Table 3
User registration phase.
Mobile userUi
Registration centerRC
⟶
secure channel
ID
U
i
Computes private keydUi=1/s+H1IDUieKRi⋅P and selects ai∈T⟵secure channeldUi,ai
Computesσi,θi⟵fbiA=dUi⊕H3pwσi, B=H4H4IDUiH4pwσimodn0 and stores ai,θi,A,B,e,f⋅,f−1⋅,t,H1,H2,H3,H4


### 4.3. Service Provider Registration Phase

If a service providerSj wants to register with the RC, the following steps will be executed. The main steps are provided in Table 4.(1)
Sj sends his/her identity IDSj to RC via a secure channel.(2)
RC computes the private key dSj=1/s+H1IDSj⋅P for Sj and sends dSj,T^ to him via a secure channel, where T^ is an authentication right tree for service provider. We will describe the detail of T^ in Section 4.5.(3)
Finally,Sj saves dSj,T^.Table 4
Service provider registration phase.
Service providerSj
Registration centerRC
⟶
secure channel
ID
S
j
ComputesdSj=1/s+H1IDSj⋅P←secure channeldSj,T^
StoresdSj,T^


### 4.4. User and Service Provider Authentication Phase

In this part, we show the mutual authentication phase between a user and a service provider without involvingRC. The main steps are provided in Table 5.(1)
First,Ui inputs his/her biometrics bi, identity IDUi and password pw into his/her mobile device. Mobile device computes σi=f−1θi,bi and B∗=H4H4IDUiH4pwσimodn0 and verifies the validity of inputted biometrics and password by computing B∗=?B. If it holds, mobile device retrieves Ui’s private key by computing dUi=A⊕H3pwσi and temporarily saves IDUi. Then, Ui selects a temporary session secret r¯1, calculates r1=H1r¯1dUi, and computes g1=gr1, C=r1⋅H1IDSjP+Ppub by using the identity of Sj. Next, Ui computesD=H1IDUieIDSjg1, E=r1+D⋅dUi, and F=aiIDUieIDSj⊕H2gr1. Finally, Ui sends the login message C,E,F to Sj.(2)
After receivingC,E,F, Sj checks whether IDUi is in IDRL; if IDUi is not in IDRL, Sj retrieves g1 using his/her private key dSj as g1=gr1=e^C,dSj. Sj retrieves ai,D,IDUi,e,IDSj by computing F⊕H2g1. Sj computes KRi=H4KRi+1Li, where Li=H4aiai^, and verifies e^E,H1IDUieKRi⋅P+Ppub=?g1⋅gD. If both are equal, Ui is allowed to authenticate with Sj. Then, Sj selects a temporary session secret r^2, then he/she calculates r2=H1r2^dSj and computes g2=gr2, and session key is set as sk=H2g1r2=H2gr1r2. Finally Sj calculates G=H4skg1g2IDSjC and sends the message g2,G to Ui.(3)
Upon receivingg2,G, Ui computes sk=H2g2r1=H2gr1r2and G∗=H4skg1g2IDSjC and checks whether G and G∗ are equal. If both are not equal, Ui aborts the session. Otherwise, Ui confirms Sj as a valid service provider and sets sk as session key between Ui and Sj.Table 5
User and service provider authentication phase.
Mobile userUi
Service providerSj
r
1
=
H
1
r
1
^
d
U
i
,
g
1
=
g
r
1 C=r1⋅H1IDSj⋅P+Ppub D=H1IDUieIDSjg1 E=r1+D⋅dUiF=aiIDUieIDSj⊕H2g1→C,E,F
Retrievesg1=gr1=e^C,dSjaiIDUieIDSj=F⊕H2g1, computes Li=H4aia^i, KRi=H4KRi+1Lie^E,H1IDUieKRi⋅P+Ppub=?g1⋅gD, and accepts/rejects r2=H1r2^dSj,g2=gr2sk=H2g1r2G=H4skg1g2IDSjC⟵G,g2
Computessk=H2g2r1G∗=H4skg1g2IDSjC, checks G∗=?G, and accepts/rejects sk


### 4.5. Tree Construction and Verification

The proposed protocol uses an authentication right treeT to store user’s and service provider’s hierarchical authentication information. T is a Merkle hash tree that was introduced by Merkle [29] in 1998. Merkle hash tree is a digital signature scheme that only uses a conventional encryption function to compute the digital signature, making it extremely efficient. In 2009, Satoshi proposed a peer-to-peer electronic cash system, as known as bitcoin [30]. Bitcoin system stores transactions in Merkle hash tree, which saves disk space, and this method can be used to verify transactions in each block. Therefore, we use a Merkle hash tree to construct our authentication right tree. In this part, we will show how we construct an authentication tree and how to verify a user’s authentication right based on the rules of Merkle hash tree.


#### 4.5.1. Tree Construction

First, we introduce the construction of the authentication right treeT as Figure 1. An authentication tree T contains the information of n different levels. The first level is the lowest level in the system, and the nth level is the highest level in the system. Node KRi denotes a user that has the authentication right which is from the first level to ith level. Value stored in node KRi is computed from the hash values of its left child node KRi−1 and right child node Li as KRi=H4KRi−1Li. The calculation of node KR1 as KR1=H4L1 is different from other KR nodes. If a user is at the first level, KR1 is embed in his/her private key, and he/she can only access to first level service providers in this system. If user is at ith level, KRi is embed in his/her private key, and he/she can access to service providers which are from first to ith levels. The right child node Li is an intermediate variable, which prepares for calculating KRi. Value stored in node Li is computed from the hash values of its left leaf node ai and right leaf node a^i as Li=H4aiai^. Leaf node ai and a^i are two 160-bit random strings that are stored on user and service provider separately. If a user is at ith level, number i is stored in the last log2n bits, and the first 160−log2n bits should be a random string.


#### 4.5.2. Tree Stored on Service Provider

The authentication right treeT^ stored on the service provider has a little different from T. Service provider uses T^ to verify user’s authentication right. The scale of T^ stored on each service provider is based on the level of service provider. As we mentioned above, nth level is the highest level in the system. If service provider is at nth level, he/she only provides service for nth level user, so he/she only needs to save the authentication right tree T^ as Figure 2. If service provider is at the jth level, he/she can provide service for user that is from jth to nth level. Therefore, he/she needs to save aj^ to an^ and KRj−1 to KRn as Figure 3, where the symbol “?” denotes the node that service provider does not have.Figure 2
Authentication right tree onnth level service provider.Figure 3
Authentication right tree onjth level service provider.


#### 4.5.3. Authentication Right Verification

When anith level user wants to access a jth level service provider, where i≥j, user sends ai to service provider, and when service provider received authentication parameter ai, he/she checks the last log2n bits of ai to get user’s level and finds ai^. Service provider computes the value of Li as Li=H4aiai^ and the value of KRi as KRi=H4KRi−1Li. Then service provider verifies user’s authentication right by calculating e^E,H1IDUieKRi⋅P+Ppub=?g1⋅gD. If the equation holds, service provider continues. Otherwise, he/she aborts the session. For instance, if a 10th level user wants to access to a 5th level service provider, user sends a10 to service provider, and when service provider received authentication parameter a10, he/she checks the last log2n bits of a10 to get user’s level and finds a10^. Service provider computes L10=H4a10a10^ and KR10=H4KR9L10. Service provider verifies user’s authentication right by calculating e^E,H1IDUieKR10⋅P+Ppub=?g1⋅gD. If the equation holds, service provider continues. Otherwise, he/she aborts the authentication.


### 4.6. The User Revocation and Reregistration Phase

Revocation and reregistration has been used in many protocols [31, 32]. In this part, we describe user revocation and reregistration. When a user Ui lost his/her smart card, he/she needs to reregister. Ui submits his/her personal information to RC, and then, RC verifies Ui’s personal information and checks the expire date of the private key dUi. If dUi has already expired, RC issues Ui a new private key with a new expire date. If dUi has not expired, RC issues Ui a new ID and a new private key with the same expire date as the lost smart card. RC adds the lost IDUi to its ID revocation list IDRL and board casts IDUi to all service providers. After received IDUi, service providers save it into their local storage.


## 4.1. RC Initialization Phase

Registration center runs the generation functionGen1n which takes a security parameter n∈Z+ and outputs parameters as follows:(1)
RC chooses two bilinear map groups G1 and G2 with a prime order q, the generator P∈G1 and g=e^P,P∈G2, where e^:G1×G1⟶G2 is a bilinear map.(2)
RC chooses cryptographic hash functions H1:0,1∗⟶Zq∗, H2:G2⟶Zq∗, H3:0,1∗⟶G1, H4:0,1∗⟶0,1n.(3)
RC chooses a random number s⟵RZq∗ as the master key, computes the corresponding public key Ppub=sP∈G1, and constructs an authentication right tree T as Figure 1. The detail of the tree will be described in Section 4.5. Finally, RC publishes G1,G2,q,e^,P,Ppub,g,H1,H2,H3,H4.Figure 1
Authentication right tree.


## 4.2. User Registration Phase

If a userUi wants to register with the registration center RC, the following steps will be executed. The main steps are provided in Table 3.(1)
Ui sends his/her identity IDUi to RC via a secure channel.(2)
RC selects an authentication parameter KRi∈T and computes the Ui’s private key dUi=1/s+H1IDUieKRi⋅P, where e is the expire date of the private key and T is an authentication right tree. RC chooses a parameter ai∈T and sends dUi,ai to Ui via a secure channel.(3)
Ui computes σi,θi⟵fbi using the fuzzy-extractor generation procedure f⋅ [26], where σi is a biometric key, θi is a public reproduction parameter, and bi is his/her personal biometrics. Ui computes A=dUi⊕H3pwσi and uses the widely implemented fuzzy-verifier technique [27, 28] to compute B=H4H4IDUiH4pwσimodn0, where pw is his/her password and n0 is the integer that defines in [27]. Finally, Ui stores ai,θi,A,B,e,f⋅,f−1⋅,t,H1,H2,H3,H4 on its mobile device, where t is the threshold in fuzzy extractor, f⋅ is the probabilistic generation procedure for outputting σi, and θi, f−1⋅ is the deterministic reproduction procedure that can recover σi and θi from a new personal biometrics input.Table 3
User registration phase.
Mobile userUi
Registration centerRC
⟶
secure channel
ID
U
i
Computes private keydUi=1/s+H1IDUieKRi⋅P and selects ai∈T⟵secure channeldUi,ai
Computesσi,θi⟵fbiA=dUi⊕H3pwσi, B=H4H4IDUiH4pwσimodn0 and stores ai,θi,A,B,e,f⋅,f−1⋅,t,H1,H2,H3,H4


## 4.3. Service Provider Registration Phase

If a service providerSj wants to register with the RC, the following steps will be executed. The main steps are provided in Table 4.(1)
Sj sends his/her identity IDSj to RC via a secure channel.(2)
RC computes the private key dSj=1/s+H1IDSj⋅P for Sj and sends dSj,T^ to him via a secure channel, where T^ is an authentication right tree for service provider. We will describe the detail of T^ in Section 4.5.(3)
Finally,Sj saves dSj,T^.Table 4
Service provider registration phase.
Service providerSj
Registration centerRC
⟶
secure channel
ID
S
j
ComputesdSj=1/s+H1IDSj⋅P←secure channeldSj,T^
StoresdSj,T^


## 4.4. User and Service Provider Authentication Phase

In this part, we show the mutual authentication phase between a user and a service provider without involvingRC. The main steps are provided in Table 5.(1)
First,Ui inputs his/her biometrics bi, identity IDUi and password pw into his/her mobile device. Mobile device computes σi=f−1θi,bi and B∗=H4H4IDUiH4pwσimodn0 and verifies the validity of inputted biometrics and password by computing B∗=?B. If it holds, mobile device retrieves Ui’s private key by computing dUi=A⊕H3pwσi and temporarily saves IDUi. Then, Ui selects a temporary session secret r¯1, calculates r1=H1r¯1dUi, and computes g1=gr1, C=r1⋅H1IDSjP+Ppub by using the identity of Sj. Next, Ui computesD=H1IDUieIDSjg1, E=r1+D⋅dUi, and F=aiIDUieIDSj⊕H2gr1. Finally, Ui sends the login message C,E,F to Sj.(2)
After receivingC,E,F, Sj checks whether IDUi is in IDRL; if IDUi is not in IDRL, Sj retrieves g1 using his/her private key dSj as g1=gr1=e^C,dSj. Sj retrieves ai,D,IDUi,e,IDSj by computing F⊕H2g1. Sj computes KRi=H4KRi+1Li, where Li=H4aiai^, and verifies e^E,H1IDUieKRi⋅P+Ppub=?g1⋅gD. If both are equal, Ui is allowed to authenticate with Sj. Then, Sj selects a temporary session secret r^2, then he/she calculates r2=H1r2^dSj and computes g2=gr2, and session key is set as sk=H2g1r2=H2gr1r2. Finally Sj calculates G=H4skg1g2IDSjC and sends the message g2,G to Ui.(3)
Upon receivingg2,G, Ui computes sk=H2g2r1=H2gr1r2and G∗=H4skg1g2IDSjC and checks whether G and G∗ are equal. If both are not equal, Ui aborts the session. Otherwise, Ui confirms Sj as a valid service provider and sets sk as session key between Ui and Sj.Table 5
User and service provider authentication phase.
Mobile userUi
Service providerSj
r
1
=
H
1
r
1
^
d
U
i
,
g
1
=
g
r
1 C=r1⋅H1IDSj⋅P+Ppub D=H1IDUieIDSjg1 E=r1+D⋅dUiF=aiIDUieIDSj⊕H2g1→C,E,F
Retrievesg1=gr1=e^C,dSjaiIDUieIDSj=F⊕H2g1, computes Li=H4aia^i, KRi=H4KRi+1Lie^E,H1IDUieKRi⋅P+Ppub=?g1⋅gD, and accepts/rejects r2=H1r2^dSj,g2=gr2sk=H2g1r2G=H4skg1g2IDSjC⟵G,g2
Computessk=H2g2r1G∗=H4skg1g2IDSjC, checks G∗=?G, and accepts/rejects sk


## 4.5. Tree Construction and Verification

The proposed protocol uses an authentication right treeT to store user’s and service provider’s hierarchical authentication information. T is a Merkle hash tree that was introduced by Merkle [29] in 1998. Merkle hash tree is a digital signature scheme that only uses a conventional encryption function to compute the digital signature, making it extremely efficient. In 2009, Satoshi proposed a peer-to-peer electronic cash system, as known as bitcoin [30]. Bitcoin system stores transactions in Merkle hash tree, which saves disk space, and this method can be used to verify transactions in each block. Therefore, we use a Merkle hash tree to construct our authentication right tree. In this part, we will show how we construct an authentication tree and how to verify a user’s authentication right based on the rules of Merkle hash tree.


### 4.5.1. Tree Construction

First, we introduce the construction of the authentication right treeT as Figure 1. An authentication tree T contains the information of n different levels. The first level is the lowest level in the system, and the nth level is the highest level in the system. Node KRi denotes a user that has the authentication right which is from the first level to ith level. Value stored in node KRi is computed from the hash values of its left child node KRi−1 and right child node Li as KRi=H4KRi−1Li. The calculation of node KR1 as KR1=H4L1 is different from other KR nodes. If a user is at the first level, KR1 is embed in his/her private key, and he/she can only access to first level service providers in this system. If user is at ith level, KRi is embed in his/her private key, and he/she can access to service providers which are from first to ith levels. The right child node Li is an intermediate variable, which prepares for calculating KRi. Value stored in node Li is computed from the hash values of its left leaf node ai and right leaf node a^i as Li=H4aiai^. Leaf node ai and a^i are two 160-bit random strings that are stored on user and service provider separately. If a user is at ith level, number i is stored in the last log2n bits, and the first 160−log2n bits should be a random string.


### 4.5.2. Tree Stored on Service Provider

The authentication right treeT^ stored on the service provider has a little different from T. Service provider uses T^ to verify user’s authentication right. The scale of T^ stored on each service provider is based on the level of service provider. As we mentioned above, nth level is the highest level in the system. If service provider is at nth level, he/she only provides service for nth level user, so he/she only needs to save the authentication right tree T^ as Figure 2. If service provider is at the jth level, he/she can provide service for user that is from jth to nth level. Therefore, he/she needs to save aj^ to an^ and KRj−1 to KRn as Figure 3, where the symbol “?” denotes the node that service provider does not have.Figure 2
Authentication right tree onnth level service provider.Figure 3
Authentication right tree onjth level service provider.


### 4.5.3. Authentication Right Verification

When anith level user wants to access a jth level service provider, where i≥j, user sends ai to service provider, and when service provider received authentication parameter ai, he/she checks the last log2n bits of ai to get user’s level and finds ai^. Service provider computes the value of Li as Li=H4aiai^ and the value of KRi as KRi=H4KRi−1Li. Then service provider verifies user’s authentication right by calculating e^E,H1IDUieKRi⋅P+Ppub=?g1⋅gD. If the equation holds, service provider continues. Otherwise, he/she aborts the session. For instance, if a 10th level user wants to access to a 5th level service provider, user sends a10 to service provider, and when service provider received authentication parameter a10, he/she checks the last log2n bits of a10 to get user’s level and finds a10^. Service provider computes L10=H4a10a10^ and KR10=H4KR9L10. Service provider verifies user’s authentication right by calculating e^E,H1IDUieKR10⋅P+Ppub=?g1⋅gD. If the equation holds, service provider continues. Otherwise, he/she aborts the authentication.


## 4.5.1. Tree Construction

First, we introduce the construction of the authentication right treeT as Figure 1. An authentication tree T contains the information of n different levels. The first level is the lowest level in the system, and the nth level is the highest level in the system. Node KRi denotes a user that has the authentication right which is from the first level to ith level. Value stored in node KRi is computed from the hash values of its left child node KRi−1 and right child node Li as KRi=H4KRi−1Li. The calculation of node KR1 as KR1=H4L1 is different from other KR nodes. If a user is at the first level, KR1 is embed in his/her private key, and he/she can only access to first level service providers in this system. If user is at ith level, KRi is embed in his/her private key, and he/she can access to service providers which are from first to ith levels. The right child node Li is an intermediate variable, which prepares for calculating KRi. Value stored in node Li is computed from the hash values of its left leaf node ai and right leaf node a^i as Li=H4aiai^. Leaf node ai and a^i are two 160-bit random strings that are stored on user and service provider separately. If a user is at ith level, number i is stored in the last log2n bits, and the first 160−log2n bits should be a random string.


## 4.5.2. Tree Stored on Service Provider

The authentication right treeT^ stored on the service provider has a little different from T. Service provider uses T^ to verify user’s authentication right. The scale of T^ stored on each service provider is based on the level of service provider. As we mentioned above, nth level is the highest level in the system. If service provider is at nth level, he/she only provides service for nth level user, so he/she only needs to save the authentication right tree T^ as Figure 2. If service provider is at the jth level, he/she can provide service for user that is from jth to nth level. Therefore, he/she needs to save aj^ to an^ and KRj−1 to KRn as Figure 3, where the symbol “?” denotes the node that service provider does not have.Figure 2
Authentication right tree onnth level service provider.Figure 3
Authentication right tree onjth level service provider.


## 4.5.3. Authentication Right Verification

When anith level user wants to access a jth level service provider, where i≥j, user sends ai to service provider, and when service provider received authentication parameter ai, he/she checks the last log2n bits of ai to get user’s level and finds ai^. Service provider computes the value of Li as Li=H4aiai^ and the value of KRi as KRi=H4KRi−1Li. Then service provider verifies user’s authentication right by calculating e^E,H1IDUieKRi⋅P+Ppub=?g1⋅gD. If the equation holds, service provider continues. Otherwise, he/she aborts the session. For instance, if a 10th level user wants to access to a 5th level service provider, user sends a10 to service provider, and when service provider received authentication parameter a10, he/she checks the last log2n bits of a10 to get user’s level and finds a10^. Service provider computes L10=H4a10a10^ and KR10=H4KR9L10. Service provider verifies user’s authentication right by calculating e^E,H1IDUieKR10⋅P+Ppub=?g1⋅gD. If the equation holds, service provider continues. Otherwise, he/she aborts the authentication.


## 4.6. The User Revocation and Reregistration Phase

Revocation and reregistration has been used in many protocols [31, 32]. In this part, we describe user revocation and reregistration. When a user Ui lost his/her smart card, he/she needs to reregister. Ui submits his/her personal information to RC, and then, RC verifies Ui’s personal information and checks the expire date of the private key dUi. If dUi has already expired, RC issues Ui a new private key with a new expire date. If dUi has not expired, RC issues Ui a new ID and a new private key with the same expire date as the lost smart card. RC adds the lost IDUi to its ID revocation list IDRL and board casts IDUi to all service providers. After received IDUi, service providers save it into their local storage.


## 5. Security Proof

In this section, we analyze the security of our protocol. First, we present a security model for our protocol, which is based on Bellare–Rogaway (BR) model [33] and CK-adversary model [34], and we use Zipf’s law [35] to enhance the security of the base model. Second, we show that the security of the proposed protocol is based on the hardness of mathematical problems. Third, we show that our protocol satisfies security requirements.


### 5.1. Security Model

We propose a security model for the proposed protocol based on literature studies [5, 15, 27, 33, 36]. There are Ui and Sj at the authentication phase of the proposed protocol. The security of the proposed protocol is defined by a game played between an adversary A and a challenger C. Let ΠΛl denote the lth instance of the participant of Λ∈Ui,Sj, respectively. In this game, we describe the capabilities of A that is defined in the literature [27] as follows:(i)
A can enumerate offline all the items in the Cartesian product Did⋆Dpw within polynomial time, where Dpw and Did denote the password space and the identity space, respectively(ii)
A has the capability of somehow learning the victim’s identity when evaluating security strength (but not privacy provisions) of the protocol(iii)
A is in full control of the communication channel between the protocol participants(iv)
A may either (i) learn the password of a legitimate user via malicious card reader or (ii) extract the sensitive parameters in the card memory by side-channel attacks, but cannot achieve both(v)
A can learn previous session keys(vi)
A has the capability of learning server’s longtime private keys only when evaluating the resistance to eventual failure of the server (e.g., forward secrecy)A can issue queries to C and get answers from it as follows:(i)
Hiqj: at any time, A issues query qj where qj can be any string, and C picks a random number rj∈Zq∗ and stores qj,rj into list ℋilist, where i∈1,2,3,4 and j∈polyn. Finally, C sends rj to A.(ii)
ExtractUID (IDUi): A issues queries of user identity IDUi, and C generates users private key dUi and stores IDUi,dUi into list ℰdUilist.(iii)
ExtractSIDIDSj: A issues queries of service provider’s identity IDSj, and C generates service provider’s private key dSj and stores IDSj,dSj into list ℰdSjlist.(iv)
SendΠΛl: A issues query of the message m, and C runs the protocol and returns the result to A.(v)
SKRevealΠΛl: A issues query, and C returns the session key produced in ΠΛl to A.(vi)
CorruptUIDIDUi: A issues the query of user’s identity IDUi, and C returns user’s private key dUi to A.(vii)
CorruptSIDIDSj: A issues the query of service provider’s identity IDSj, and C returns service provider’s private key dSj to A.(viii)
TestΠΛl: when A issues the query, C flips a random coin b∈0,1. If b=1, C sends session key in ΠΛl to A; otherwise, b=0, and C picks a random number with the same length of session key and sends it to A.After issuing the queries above,A outputs b′, where b′ is about the coin b produced in Test ΠΛl-query. A violates the authentication key agreement (AKA) of the proposed protocol Σ, if A can guess b correctly. We define A’s advantage in attacking the proposed protocol Σ as AdvΣAKAA=2Prb=b′−1.Definition 1.
(AKA-Secure). The proposed protocolΣ is authentication key agreement secure (AKA-Secure) if AdvΣAKAA=2Prb=b′−1 is negligible for any polynomial-time adversary A.
A violates the mutual authentication of the proposed protocol Σ, if A can generate a legal login message or a legal response message. Let EU,S and ES,U denote the events that A generates a legal login message and a legal response message. We define the advantage of A attacking the mutual authentication of the proposed protocol Σ as AdvΣMAA=PrEU,S+PrES,U.Definition 2.
(MA-Secure). The proposed protocolΣ is mutual authentication secure (MA-Secure) if AdvΣMAA is negligible for any polynomial-time adversary A.


### 5.2. Proof of Security

In this part, we show the proposed protocolΣ for multiserver architecture is AKA-secure and MA-secure in the security model we described above.Lemma 1.
No polynomial-time adversaryA can forge a legal login message with a nonnegligible probability ϵ.Proof.
Suppose the adversaryA forges a legal login message with a nonnegligible probability ϵ. We show there is a challenger C who can solve the discrete logarithm (DL) problem with a nonnegligible probability.
Given an instanceg,gs of the DL problem, the aim of challenger C is to compute s∈Zq∗, and C sends the system parameters G1,G2,q,e^,P,Ppub,g,H1,H2,H3,H4 to A. C randomly selects IDUi and answers A’s queries according to the following description:(i)
Hiqj: C maintains a list Hilist initialized empty. Upon receiving the query qj, C checks if qj,rj exists in Hilist. If yes, C sends rj to A; otherwise, Crandomly picks rj∈Zq∗ and stores qj,rj in Hilist then sends rj to A, where j∈polyn.(ii)
ExtractUIDIDUi: C maintains a list ℰdUilist initialized empty. When receiving the query IDUi, Cchecks if IDUi,dUi exists in ℰdUilist then C send dUi to A; otherwise, C executes the operations as follows:(1)
IfIDUi=IDUch, C sets H1IDUi⟵α,dUi⟵⊥ and stores IDUi,α into H1list, IDUi,dUi into ℰUlist(2)
Otherwise ifIDUi≠IDUch, C randomly selects αi∈α1,α2,…,αk, sets H1IDUch⟵αi,dUi⟵1/s+αi⋅P, and stores IDUi,αi in H1list, IDUi,dUi in ℰdUilist(iii)
ExtractSIDIDSj: C maintains a list ℰdSjlist initialized empty. When receiving the query IDSj, C checks if IDSj,dSj exists in ℰdSjlist. If yes, C send dSj to A; otherwise, C randomly picks rdSj∈Zq∗ and computes dSj=1/s+rdSj⋅P. C stores IDSj,dSj into ℰdSjlist, IDSj,rdSj into H1list and sends dSj to A.(iv)
SendΠΛl: C checks if Λ and Uch are equal; if yes, C aborts the game; otherwise, C operates according to protocol Σ.(v)
SKRevealΠΛl: after received the query, C sends session key produced in ΠΛl to A.(vi)
CorruptUIDIDUi: C searches for IDUi,dUi in ℰdUilist and returns dUi to A.(vii)
CorruptSIDIDSj: C searches for IDSj,dSj in ℰdSjlist and returns dSj to A.(viii)
TestΠΛl: C randomly picks a number with the same length of session key and sends it to A.
At last,A outputs a legal login message C,E,F corresponding to user’s identity IDUi. If IDUi≠IDUch, C aborts the game. Based on the forking lemma [37], A can output another legal login message C,E′,F′. Because the login messages is legal, we get the following two equations, gUi is computed by rising g to the power of a random number chose by A:(1)e^E,H1IDUieKRi⋅P+Ppub=gUi⋅gD,e^E′,H1IDUieKRi⋅P+Ppub=gUi⋅gD′.
Based on the two equations above, we get the following equations:(2)e^E,H1IDUieKRi⋅P+Ppube^E′,H1IDUieKRi⋅P+Ppub=gUi⋅gDgUi⋅gD′=gD−D′,C outputs D−D′−1⋅E−E′ as the solution to the given DL problem. The probability that C can solve the DL problem is described as follows:(i)
E1: C dose not abort in the any Send-queries(ii)
E2: A outputs a legal login request(iii)
E3: IDUi and IDUI are equal
Letl denote the number of bits in biometric data, qSend and qH1 denote the number of Send-queries and H1-queries executed in the game, C′ and s′ are the Zipf’s parameters [35], and l is the length of biometric information. We can get PrE1≥1−1/qSend+1qSend, PrE2E1≥ε, and PrE3E1∧E2≥1/qH1.
Therefore, the nonnegligible probability thatC can solve the DL problem is given by(3)PrE1∧E2∧E3=PrE3E1∧E2,PrE2E1⋅PrE1≥1−1/qSend+1qSendqH1⋅ε+maxC′⋅qSends′,qSend2l.
This contradicts with the hardness of the DL problem. Therefore, we get that no polynomial-time adversary against the proposed MSAA protocol can forge a legal login message with a nonnegligible probability.Lemma 2.
No polynomial-time adversaryA can forge a legal response message with a nonnegligible probability.Proof.
Suppose the adversaryA forges a legal response message with a nonnegligible probability ε. We show there is a challenger C who can solve the k-mBIDH problem with a nonnegligible probability.
Given an instanceP,y⋅P,z⋅P,1/y+α1⋅P,1/y+α2⋅P,…,1/y+αk⋅P∈G1 of the k-mBIDH problem, the aim of challenger C is to compute e^P,Ps/y+α; he picks a random number x∈Zq∗ and computes x⋅P,y⋅P, and sends the system parameters G1,G2,q,e,P,Ppub,g,H1,H2,H3,H4 to A. C randomly selects IDUi and answers A’s queries according to the following description:(i)
Hiqj: C maintains a list Hilist initialized empty. Upon receiving the query qj, C checks if qj,rj exists in Hilist. If yes, C sends rj to A; otherwise, C randomly picks rj∈Zq∗ and stores qj,rj in Hilist then sends rj to A, where j∈polyn.(ii)
ExtractUIDIDUi: C maintains a list ℰdUilist initialized empty. When receiving the query IDUi, C checks if IDUi,dUi exists in ℰdUilist and then C sends dUi to A; otherwise, C randomly picks rdUi∈Zq∗and computes dUi=1/s+rdUi⋅P. C stores IDUi,dUi in ℰdUilist, IDUi,rdUi in H1list and sends dUi to A.(iii)
ExtractSIDIDSj: C maintains a list ℰdSjlist initialized empty. When receiving the query IDSj, C checks if IDSj,dSj exists in ℰdSjlist and then C sends dSj to A; otherwise, C executes the operations as follows:(1)
IfIDSj=IDSch, C sets H1IDUi⟵α and stores IDSj,α into H1list, IDSj,⊥ into ℰdSjlist(2)
Otherwise ifIDSj≠IDSch, C randomly selects αi∈α1,α2,…,αk, sets H1IDSj⟵α, and stores IDSj,αi in H1list, IDSj,αi,1/s+αi⋅P in ℰdSjlist(iv)
SendΠΛl: C checks if Λ and Sch are equal; if yes, C aborts the game; otherwise, C operates according to the proposed protocol Σ.
Finally,A outputs a response message corresponding to identity IDSj. C outputs g1 as the solution of k-mBIDH problem. The probability that C can solve the k-mBIDH problem is described as follows:(i)
E1: C dose not abort in any Send-queries(ii)
E2: C outputs a legal response message(iii)
E3: IDSJ and IDSch are equal
LetqSend,qH1, and qH2 denote the number of Response-query, H1-query, and H2-query in the game. We can get PrE1≥1−1/qSend+1qSend, PrE2E1≥ε, and PrE3E1∧E2≥1/qH1⋅qH2. Therefore, the nonnegligible probability that C can solve the k-mBIDH problem is given by(4)PrE1∧E2∧E3=PrE3E1∧E2⋅PrE2E1⋅PrE1≥1−1/qSend+1qSendqH1⋅qH2⋅ε.
This contradicts with the hardness of thek-mBIDH problem. Therefore, we get that no polynomial-time adversary against the proposed MSAA protocol can forge a legal response message with a nonnegligible probability.Theorem 1.
The proposed protocol is MA-secure if the DL problem and thek-mBIDH problem are hard.Proof.
Based on Lemmas1 and 2, we get no polynomial-time adversary can forge a legal login message or a legal response message if the DL problem and the k-mBIDH problem are hard. Therefore, we get the proposed protocol is MA-secure.Theorem 2.
The proposed protocol is AKA-secure if the CDH problem is hard.Proof.
SupposeA guesses b correctly in Test-query with a nonnegligible probability ϵ, then C can solve the CDH problem with a nonnegligible probability.
LetEsk denote the event that A gets the correct session key. Since the probability that A correctly guesses the value b is at least 1/2, we can get PrEsk≥ε/2.
LetETU and ETS denote the events that A uses in the Test-query to a user’s instance and a service provider’s instance, respectively. Let EU,S denote the event that A can violate the user to service provider authentication. We get the following two equations:(5)ε2≤PrEsk=PrEsk∧ETU+PrEsk∧ETS∧EU,S+PrEsk∧ETS∧¬EU,S≤PrEsk∧ETU+PrEU,S+PrEsk∧ETS∧¬EU,S,PrEsk∧ETU+PrEsk∧ETS∧¬EU,S≥ε2−PrEU,S.
SincePrETS∧EU,S=PrETU, we get(6)PrETS∧EU,S≥ε4−PrEU,S2.
We get the probability as follows:(7)Prsk=H2gr1r2r1,r2⟵Zq∗≥ε4−PrEU,S2.
According to the proof of Lemma1, we get PrEU,S is negligible. However, ε/4−PrEU,S/2 is nonnegligible, suppose that x=gr1,y=gr2 where r1,r2∈Zq∗. Given an instance x,y of the CDH problem, A computes z=gr1⋅r2with a nonnegligible probability ε/4−PrEU,S/2. Therefore, C can use A to solve the CDH problem with a nonnegligible probability. This contradicts with the hardness of the CDH problem. Therefore, we can conclude that the proposed protocol is AKA-secure if the CDH problem is hard.


### 5.3. Security Requirements Analysis

We briefly show the proposed protocol satisfies the security requirements as follows:(i)
Single registration: according to the specification of the proposed protocol, a user registers at the registration center once, and he/she can log into registered service providers, which is at a specific level. Therefore, the proposed protocol can provide single registration.(ii)
Mutual authentication: two lemmas described above show that the adversary against the proposed protocol cannot produce a valid login or response message. Then,IDUi and IDSj can authenticate with the participant by checking the legality of the received response message and login message, respectively. Therefore, the proposed protocol can support mutual authentication.(iii)
User anonymity: according to the proposed protocol, the user’s identityIDUi is only in the message F=DIDUieIDSj⊕H2gr1. To get IDUi, adversary needs to compute gr1 from C=r1⋅H1IDSj⋅P+Ppub, and it turns out the adversary need to solve the k-mBIDH problem. Then, we know that the proposed protocol can provide user anonymity as long as k-mBIDH problem is hard.(iv)
Untraceability: according to the proposed protocol, user generates a new random numberr1∈Zq∗to compute C=r1⋅H1IDSj⋅P+Ppub,gr1,F=aiDIDUieIDSj⊕H2gr1. Due to the randomness of r1, adversary cannot find any relation of messages sent by the user and cannot trace the user’s behavior. Therefore, the proposed protocol can provide untraceability.(v)
Session key agreement: according to the proposed protocol, both two participants calculate session keysk=H2gr1r2, which can be used in future communications. Therefore, the proposed protocol can provide session key agreement.(vi)
Perfect forward secrecy: assume the adversary steals both private keys of the user and the service provider. We also assume that the adversary interceptsC,E,F,G,g2 sent between the user and the service provider. Using the service provider’s private key, the adversary can compute g1=e^C,dSj=gr1. To get session key sk=H2gr1r2, the adversary must to compute g1r2=g2r1=gr1r2 where g1=gr1,g2=gr2. Thus, adversary must solve the CDH problem. Then, the proposed protocol can provide the perfect forward secrecy, since the CDH problem is hard.(vii)
No smart card lose attack [20]: assume the adversary steals the user’s device. By using the side-channel attack, the adversary can extract the data B=H4IDUiH4pwσi,A=dUi⊕H3pwσi. The adversary can guess password pw, but he/she cannot verify its correctness because we have implemented the fuzzy-verifier technique [27, 28]. The adversary cannot get the user’s password, so he cannot get the user’s private key dUi. Therefore, adversaries cannot impersonate the user to the service provider, and the proposed protocol can resist smart card lose attack.(viii)
No password verifier table: according to the proposed protocol, both two participants need to store their private keys, and the registration center needs no password verifier table. Thus, the proposed protocol provides no password verifier table.(ix)
No online registration center: according to the proposed protocol, two participants can authenticate with each other without the help of the registration center. Thus, the proposed protocol does not need an online registration center.(x)
Hierarchical authentication: this security requirement only satisfied by the proposed protocol. The hierarchical informationKRi is embedded in the user’s private keydUi=1/s+H1IDUieKRi⋅P, when authentication is with a service provider, service provider will check the user’s authentication right by computing whether the equation e^E,H1IDUieKRi⋅P+Ppub=?g1⋅gD holds.(xi)
The resistance of various attacks: the proposed protocol can resist the insider attack, the replay attack, the man-in-the-middle attack, etc. We briefly describe it as follows:(1)
Temporary information attack: if the adversary gets the temporary informationr1^,r2^, he/she has no ability to derive the user’s secret key from r1+D⋅dUi because the exponential of g is composed of two values: one is session temporary secret r1^ and other is the private key of the user dUi. Therefore, the proposed protocol is secure against temporary information attack.(2)
Insider attack: suppose an insider in the system gets the user’s informationIDUi,H3pwσi. The adversary can guess a password pw. However, he/she cannot verify its correctness because user’s password is protected by the secure hash function and the biometric key σi. Thus, the insider cannot get user’s password, and the proposed protocol withstands the insider attack.(3)
User impersonation attack [38, 39]: according to the proof of Lemma 1, we conclude that no adversary can forge a legal login message without the user’s private key. Thus, the service provider can find out about the attack by verifying the validity of the received login message. Therefore, the proposed protocol can resist the user impersonation attack.(4)
Server spoofing attack: according to the proof of Lemma2, we know that no adversary can generate a legal response message without the service provider’s private key. Therefore, users can find out about the attack by verifying the validity of the received response message. Therefore, the proposed protocol can resist the server spoofing attack.(5)
Modification attack: according to the proof of Lemma1, we know that C,E,F is a digital signature of the login message and no polynomial-time adversary can forge a legal one. The service provider can find any modification by checking if the equation g1=gr1=e^C,dSj and e^E,H1IDUieKRi⋅P+Ppub=?g1⋅gDholds. Besides G is the message authentication code of the response message C,E,F under the key g1=e^C,dSj. The user can find out about any modification of the response message because the hash function H4⋅ is secure. Therefore, the proposed protocol can resist the modification attack.(6)
Replay attack: according to the proposed protocol, both two participants generate new random numberr1,r2∈Zq∗ and g1=gr1,g2=gr2, which are involved in the login message and the response message. Due to the freshness of g1,g2, the user and the service provider can find the replay of messages by checking the validity of the received message. Therefore, the proposed protocol resists the replay attack.(7)
Man-in-the-middle attack: based on the above description, we conclude that the proposed protocol provides mutual authentication between two participants. Therefore, the proposed protocol can resist the man-in-the-middle attack.


### 5.4. Security Comparison

In this part, we compare the security of the proposed protocol with other multiserver architecture protocols in Table6. We introduce a new independent criterion, which is based on a widely adopted standard [40, 41] as follows:C1 (no password verifier table): the server does not need to maintain a database for storing user passwords or some derived values of user passwords.C2 (password friendly): the password is memorable and can be chosen freely and changed locally by the user.C3 (no password exposure): the password cannot be derived by the privileged administrator of the server.C4 (no smart card loss attack): the scheme is free from smart card loss attack, i.e., unauthorized users getting a victim’s card should not be able to easily change the password of the smart card, recover the victim’s password by using online, offline or hybrid guessing attacks, or impersonate the user to login to the system, even if the smart card is obtained and/or secret data in the smart card are revealed.C5 (resistance to known attacks): the scheme resists various kinds of basic/sophisticated attacks, including offline password guessing attack, replay attack, parallel session attack, desynchronization attack, stolen verifier attack, impersonation attack, key control, unknown key share attack, and known key attack.C6 (sound repairability): the scheme provides smart card revocation with good repairability, i.e., a user can revoke her card without changing her identity.C7 (provision of key agreement): the client and the server can establish a common session key for secure data communications during the authentication process.C8 (no clock synchronization): the scheme is not prone to the problems of clock synchronization and time delay, i.e., the server needs not to synchronize its time clock with these time clocks of all input devices used by smart cards, and vice versa.C9 (timely typo detection): the user will be timely notified if she inputs a wrong password by mistake when login.C10 (mutual authentication): the user and server can verify the authenticity of each other.C11 (user anonymity): the scheme can protect user identity and prevent user activities from being traced.C12 (forward secrecy): the scheme provides the property of perfect forward secrecy.C13 (hierarchical authentication): when a server authenticates with a user, it checks the user’s authentication right. If the user authentication right belongs to the server authentication level, the authentication is successful. Otherwise, the authentication request is denied.Table 6
Performance comparison.
Protocol rounds
Computation cost
Communication cost
Storage cost
Security requirements
User side
Server side
User side
Server side
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
C13
Odelu et al. [14]
3
T
m
t
p
+
4
T
h
+
3
T
s
m
+
2
T
exp
≈
78.519
T
m
t
p
+
4
T
h
+
4
T
exp
+
T
s
m
+
T
mul
+
2
T
b
p
≈
15.303
832
672
1674
✓
✓
✓
✕
✕
✓
✓
✓
✓
✓
✓
✓
✕
He et al. [15]
3
2
T
s
m
+
T
p
a
+
2
T
exp
+
8
T
h
≈
31.837
T
b
p
+
4
T
exp
+
2
T
mul
+
5
T
h
≈
5.246
2240
1184
3424
✓
✓
✓
✕
✕
✕
✓
✓
✕
✓
✓
✓
✕
Ours
2
3
T
s
m
+
2
T
exp
+
T
p
a
+
6
T
h
≈
45.354
2
T
b
p
+
4
T
exp
+
T
s
m
+
T
p
a
+
T
mul
+
7
T
h
≈
11.107
896
672
1834
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓


## 5.1. Security Model

We propose a security model for the proposed protocol based on literature studies [5, 15, 27, 33, 36]. There are Ui and Sj at the authentication phase of the proposed protocol. The security of the proposed protocol is defined by a game played between an adversary A and a challenger C. Let ΠΛl denote the lth instance of the participant of Λ∈Ui,Sj, respectively. In this game, we describe the capabilities of A that is defined in the literature [27] as follows:(i)
A can enumerate offline all the items in the Cartesian product Did⋆Dpw within polynomial time, where Dpw and Did denote the password space and the identity space, respectively(ii)
A has the capability of somehow learning the victim’s identity when evaluating security strength (but not privacy provisions) of the protocol(iii)
A is in full control of the communication channel between the protocol participants(iv)
A may either (i) learn the password of a legitimate user via malicious card reader or (ii) extract the sensitive parameters in the card memory by side-channel attacks, but cannot achieve both(v)
A can learn previous session keys(vi)
A has the capability of learning server’s longtime private keys only when evaluating the resistance to eventual failure of the server (e.g., forward secrecy)A can issue queries to C and get answers from it as follows:(i)
Hiqj: at any time, A issues query qj where qj can be any string, and C picks a random number rj∈Zq∗ and stores qj,rj into list ℋilist, where i∈1,2,3,4 and j∈polyn. Finally, C sends rj to A.(ii)
ExtractUID (IDUi): A issues queries of user identity IDUi, and C generates users private key dUi and stores IDUi,dUi into list ℰdUilist.(iii)
ExtractSIDIDSj: A issues queries of service provider’s identity IDSj, and C generates service provider’s private key dSj and stores IDSj,dSj into list ℰdSjlist.(iv)
SendΠΛl: A issues query of the message m, and C runs the protocol and returns the result to A.(v)
SKRevealΠΛl: A issues query, and C returns the session key produced in ΠΛl to A.(vi)
CorruptUIDIDUi: A issues the query of user’s identity IDUi, and C returns user’s private key dUi to A.(vii)
CorruptSIDIDSj: A issues the query of service provider’s identity IDSj, and C returns service provider’s private key dSj to A.(viii)
TestΠΛl: when A issues the query, C flips a random coin b∈0,1. If b=1, C sends session key in ΠΛl to A; otherwise, b=0, and C picks a random number with the same length of session key and sends it to A.After issuing the queries above,A outputs b′, where b′ is about the coin b produced in Test ΠΛl-query. A violates the authentication key agreement (AKA) of the proposed protocol Σ, if A can guess b correctly. We define A’s advantage in attacking the proposed protocol Σ as AdvΣAKAA=2Prb=b′−1.Definition 1.
(AKA-Secure). The proposed protocolΣ is authentication key agreement secure (AKA-Secure) if AdvΣAKAA=2Prb=b′−1 is negligible for any polynomial-time adversary A.
A violates the mutual authentication of the proposed protocol Σ, if A can generate a legal login message or a legal response message. Let EU,S and ES,U denote the events that A generates a legal login message and a legal response message. We define the advantage of A attacking the mutual authentication of the proposed protocol Σ as AdvΣMAA=PrEU,S+PrES,U.Definition 2.
(MA-Secure). The proposed protocolΣ is mutual authentication secure (MA-Secure) if AdvΣMAA is negligible for any polynomial-time adversary A.


## 5.2. Proof of Security

In this part, we show the proposed protocolΣ for multiserver architecture is AKA-secure and MA-secure in the security model we described above.Lemma 1.
No polynomial-time adversaryA can forge a legal login message with a nonnegligible probability ϵ.Proof.
Suppose the adversaryA forges a legal login message with a nonnegligible probability ϵ. We show there is a challenger C who can solve the discrete logarithm (DL) problem with a nonnegligible probability.
Given an instanceg,gs of the DL problem, the aim of challenger C is to compute s∈Zq∗, and C sends the system parameters G1,G2,q,e^,P,Ppub,g,H1,H2,H3,H4 to A. C randomly selects IDUi and answers A’s queries according to the following description:(i)
Hiqj: C maintains a list Hilist initialized empty. Upon receiving the query qj, C checks if qj,rj exists in Hilist. If yes, C sends rj to A; otherwise, Crandomly picks rj∈Zq∗ and stores qj,rj in Hilist then sends rj to A, where j∈polyn.(ii)
ExtractUIDIDUi: C maintains a list ℰdUilist initialized empty. When receiving the query IDUi, Cchecks if IDUi,dUi exists in ℰdUilist then C send dUi to A; otherwise, C executes the operations as follows:(1)
IfIDUi=IDUch, C sets H1IDUi⟵α,dUi⟵⊥ and stores IDUi,α into H1list, IDUi,dUi into ℰUlist(2)
Otherwise ifIDUi≠IDUch, C randomly selects αi∈α1,α2,…,αk, sets H1IDUch⟵αi,dUi⟵1/s+αi⋅P, and stores IDUi,αi in H1list, IDUi,dUi in ℰdUilist(iii)
ExtractSIDIDSj: C maintains a list ℰdSjlist initialized empty. When receiving the query IDSj, C checks if IDSj,dSj exists in ℰdSjlist. If yes, C send dSj to A; otherwise, C randomly picks rdSj∈Zq∗ and computes dSj=1/s+rdSj⋅P. C stores IDSj,dSj into ℰdSjlist, IDSj,rdSj into H1list and sends dSj to A.(iv)
SendΠΛl: C checks if Λ and Uch are equal; if yes, C aborts the game; otherwise, C operates according to protocol Σ.(v)
SKRevealΠΛl: after received the query, C sends session key produced in ΠΛl to A.(vi)
CorruptUIDIDUi: C searches for IDUi,dUi in ℰdUilist and returns dUi to A.(vii)
CorruptSIDIDSj: C searches for IDSj,dSj in ℰdSjlist and returns dSj to A.(viii)
TestΠΛl: C randomly picks a number with the same length of session key and sends it to A.
At last,A outputs a legal login message C,E,F corresponding to user’s identity IDUi. If IDUi≠IDUch, C aborts the game. Based on the forking lemma [37], A can output another legal login message C,E′,F′. Because the login messages is legal, we get the following two equations, gUi is computed by rising g to the power of a random number chose by A:(1)e^E,H1IDUieKRi⋅P+Ppub=gUi⋅gD,e^E′,H1IDUieKRi⋅P+Ppub=gUi⋅gD′.
Based on the two equations above, we get the following equations:(2)e^E,H1IDUieKRi⋅P+Ppube^E′,H1IDUieKRi⋅P+Ppub=gUi⋅gDgUi⋅gD′=gD−D′,C outputs D−D′−1⋅E−E′ as the solution to the given DL problem. The probability that C can solve the DL problem is described as follows:(i)
E1: C dose not abort in the any Send-queries(ii)
E2: A outputs a legal login request(iii)
E3: IDUi and IDUI are equal
Letl denote the number of bits in biometric data, qSend and qH1 denote the number of Send-queries and H1-queries executed in the game, C′ and s′ are the Zipf’s parameters [35], and l is the length of biometric information. We can get PrE1≥1−1/qSend+1qSend, PrE2E1≥ε, and PrE3E1∧E2≥1/qH1.
Therefore, the nonnegligible probability thatC can solve the DL problem is given by(3)PrE1∧E2∧E3=PrE3E1∧E2,PrE2E1⋅PrE1≥1−1/qSend+1qSendqH1⋅ε+maxC′⋅qSends′,qSend2l.
This contradicts with the hardness of the DL problem. Therefore, we get that no polynomial-time adversary against the proposed MSAA protocol can forge a legal login message with a nonnegligible probability.Lemma 2.
No polynomial-time adversaryA can forge a legal response message with a nonnegligible probability.Proof.
Suppose the adversaryA forges a legal response message with a nonnegligible probability ε. We show there is a challenger C who can solve the k-mBIDH problem with a nonnegligible probability.
Given an instanceP,y⋅P,z⋅P,1/y+α1⋅P,1/y+α2⋅P,…,1/y+αk⋅P∈G1 of the k-mBIDH problem, the aim of challenger C is to compute e^P,Ps/y+α; he picks a random number x∈Zq∗ and computes x⋅P,y⋅P, and sends the system parameters G1,G2,q,e,P,Ppub,g,H1,H2,H3,H4 to A. C randomly selects IDUi and answers A’s queries according to the following description:(i)
Hiqj: C maintains a list Hilist initialized empty. Upon receiving the query qj, C checks if qj,rj exists in Hilist. If yes, C sends rj to A; otherwise, C randomly picks rj∈Zq∗ and stores qj,rj in Hilist then sends rj to A, where j∈polyn.(ii)
ExtractUIDIDUi: C maintains a list ℰdUilist initialized empty. When receiving the query IDUi, C checks if IDUi,dUi exists in ℰdUilist and then C sends dUi to A; otherwise, C randomly picks rdUi∈Zq∗and computes dUi=1/s+rdUi⋅P. C stores IDUi,dUi in ℰdUilist, IDUi,rdUi in H1list and sends dUi to A.(iii)
ExtractSIDIDSj: C maintains a list ℰdSjlist initialized empty. When receiving the query IDSj, C checks if IDSj,dSj exists in ℰdSjlist and then C sends dSj to A; otherwise, C executes the operations as follows:(1)
IfIDSj=IDSch, C sets H1IDUi⟵α and stores IDSj,α into H1list, IDSj,⊥ into ℰdSjlist(2)
Otherwise ifIDSj≠IDSch, C randomly selects αi∈α1,α2,…,αk, sets H1IDSj⟵α, and stores IDSj,αi in H1list, IDSj,αi,1/s+αi⋅P in ℰdSjlist(iv)
SendΠΛl: C checks if Λ and Sch are equal; if yes, C aborts the game; otherwise, C operates according to the proposed protocol Σ.
Finally,A outputs a response message corresponding to identity IDSj. C outputs g1 as the solution of k-mBIDH problem. The probability that C can solve the k-mBIDH problem is described as follows:(i)
E1: C dose not abort in any Send-queries(ii)
E2: C outputs a legal response message(iii)
E3: IDSJ and IDSch are equal
LetqSend,qH1, and qH2 denote the number of Response-query, H1-query, and H2-query in the game. We can get PrE1≥1−1/qSend+1qSend, PrE2E1≥ε, and PrE3E1∧E2≥1/qH1⋅qH2. Therefore, the nonnegligible probability that C can solve the k-mBIDH problem is given by(4)PrE1∧E2∧E3=PrE3E1∧E2⋅PrE2E1⋅PrE1≥1−1/qSend+1qSendqH1⋅qH2⋅ε.
This contradicts with the hardness of thek-mBIDH problem. Therefore, we get that no polynomial-time adversary against the proposed MSAA protocol can forge a legal response message with a nonnegligible probability.Theorem 1.
The proposed protocol is MA-secure if the DL problem and thek-mBIDH problem are hard.Proof.
Based on Lemmas1 and 2, we get no polynomial-time adversary can forge a legal login message or a legal response message if the DL problem and the k-mBIDH problem are hard. Therefore, we get the proposed protocol is MA-secure.Theorem 2.
The proposed protocol is AKA-secure if the CDH problem is hard.Proof.
SupposeA guesses b correctly in Test-query with a nonnegligible probability ϵ, then C can solve the CDH problem with a nonnegligible probability.
LetEsk denote the event that A gets the correct session key. Since the probability that A correctly guesses the value b is at least 1/2, we can get PrEsk≥ε/2.
LetETU and ETS denote the events that A uses in the Test-query to a user’s instance and a service provider’s instance, respectively. Let EU,S denote the event that A can violate the user to service provider authentication. We get the following two equations:(5)ε2≤PrEsk=PrEsk∧ETU+PrEsk∧ETS∧EU,S+PrEsk∧ETS∧¬EU,S≤PrEsk∧ETU+PrEU,S+PrEsk∧ETS∧¬EU,S,PrEsk∧ETU+PrEsk∧ETS∧¬EU,S≥ε2−PrEU,S.
SincePrETS∧EU,S=PrETU, we get(6)PrETS∧EU,S≥ε4−PrEU,S2.
We get the probability as follows:(7)Prsk=H2gr1r2r1,r2⟵Zq∗≥ε4−PrEU,S2.
According to the proof of Lemma1, we get PrEU,S is negligible. However, ε/4−PrEU,S/2 is nonnegligible, suppose that x=gr1,y=gr2 where r1,r2∈Zq∗. Given an instance x,y of the CDH problem, A computes z=gr1⋅r2with a nonnegligible probability ε/4−PrEU,S/2. Therefore, C can use A to solve the CDH problem with a nonnegligible probability. This contradicts with the hardness of the CDH problem. Therefore, we can conclude that the proposed protocol is AKA-secure if the CDH problem is hard.


## 5.3. Security Requirements Analysis

We briefly show the proposed protocol satisfies the security requirements as follows:(i)
Single registration: according to the specification of the proposed protocol, a user registers at the registration center once, and he/she can log into registered service providers, which is at a specific level. Therefore, the proposed protocol can provide single registration.(ii)
Mutual authentication: two lemmas described above show that the adversary against the proposed protocol cannot produce a valid login or response message. Then,IDUi and IDSj can authenticate with the participant by checking the legality of the received response message and login message, respectively. Therefore, the proposed protocol can support mutual authentication.(iii)
User anonymity: according to the proposed protocol, the user’s identityIDUi is only in the message F=DIDUieIDSj⊕H2gr1. To get IDUi, adversary needs to compute gr1 from C=r1⋅H1IDSj⋅P+Ppub, and it turns out the adversary need to solve the k-mBIDH problem. Then, we know that the proposed protocol can provide user anonymity as long as k-mBIDH problem is hard.(iv)
Untraceability: according to the proposed protocol, user generates a new random numberr1∈Zq∗to compute C=r1⋅H1IDSj⋅P+Ppub,gr1,F=aiDIDUieIDSj⊕H2gr1. Due to the randomness of r1, adversary cannot find any relation of messages sent by the user and cannot trace the user’s behavior. Therefore, the proposed protocol can provide untraceability.(v)
Session key agreement: according to the proposed protocol, both two participants calculate session keysk=H2gr1r2, which can be used in future communications. Therefore, the proposed protocol can provide session key agreement.(vi)
Perfect forward secrecy: assume the adversary steals both private keys of the user and the service provider. We also assume that the adversary interceptsC,E,F,G,g2 sent between the user and the service provider. Using the service provider’s private key, the adversary can compute g1=e^C,dSj=gr1. To get session key sk=H2gr1r2, the adversary must to compute g1r2=g2r1=gr1r2 where g1=gr1,g2=gr2. Thus, adversary must solve the CDH problem. Then, the proposed protocol can provide the perfect forward secrecy, since the CDH problem is hard.(vii)
No smart card lose attack [20]: assume the adversary steals the user’s device. By using the side-channel attack, the adversary can extract the data B=H4IDUiH4pwσi,A=dUi⊕H3pwσi. The adversary can guess password pw, but he/she cannot verify its correctness because we have implemented the fuzzy-verifier technique [27, 28]. The adversary cannot get the user’s password, so he cannot get the user’s private key dUi. Therefore, adversaries cannot impersonate the user to the service provider, and the proposed protocol can resist smart card lose attack.(viii)
No password verifier table: according to the proposed protocol, both two participants need to store their private keys, and the registration center needs no password verifier table. Thus, the proposed protocol provides no password verifier table.(ix)
No online registration center: according to the proposed protocol, two participants can authenticate with each other without the help of the registration center. Thus, the proposed protocol does not need an online registration center.(x)
Hierarchical authentication: this security requirement only satisfied by the proposed protocol. The hierarchical informationKRi is embedded in the user’s private keydUi=1/s+H1IDUieKRi⋅P, when authentication is with a service provider, service provider will check the user’s authentication right by computing whether the equation e^E,H1IDUieKRi⋅P+Ppub=?g1⋅gD holds.(xi)
The resistance of various attacks: the proposed protocol can resist the insider attack, the replay attack, the man-in-the-middle attack, etc. We briefly describe it as follows:(1)
Temporary information attack: if the adversary gets the temporary informationr1^,r2^, he/she has no ability to derive the user’s secret key from r1+D⋅dUi because the exponential of g is composed of two values: one is session temporary secret r1^ and other is the private key of the user dUi. Therefore, the proposed protocol is secure against temporary information attack.(2)
Insider attack: suppose an insider in the system gets the user’s informationIDUi,H3pwσi. The adversary can guess a password pw. However, he/she cannot verify its correctness because user’s password is protected by the secure hash function and the biometric key σi. Thus, the insider cannot get user’s password, and the proposed protocol withstands the insider attack.(3)
User impersonation attack [38, 39]: according to the proof of Lemma 1, we conclude that no adversary can forge a legal login message without the user’s private key. Thus, the service provider can find out about the attack by verifying the validity of the received login message. Therefore, the proposed protocol can resist the user impersonation attack.(4)
Server spoofing attack: according to the proof of Lemma2, we know that no adversary can generate a legal response message without the service provider’s private key. Therefore, users can find out about the attack by verifying the validity of the received response message. Therefore, the proposed protocol can resist the server spoofing attack.(5)
Modification attack: according to the proof of Lemma1, we know that C,E,F is a digital signature of the login message and no polynomial-time adversary can forge a legal one. The service provider can find any modification by checking if the equation g1=gr1=e^C,dSj and e^E,H1IDUieKRi⋅P+Ppub=?g1⋅gDholds. Besides G is the message authentication code of the response message C,E,F under the key g1=e^C,dSj. The user can find out about any modification of the response message because the hash function H4⋅ is secure. Therefore, the proposed protocol can resist the modification attack.(6)
Replay attack: according to the proposed protocol, both two participants generate new random numberr1,r2∈Zq∗ and g1=gr1,g2=gr2, which are involved in the login message and the response message. Due to the freshness of g1,g2, the user and the service provider can find the replay of messages by checking the validity of the received message. Therefore, the proposed protocol resists the replay attack.(7)
Man-in-the-middle attack: based on the above description, we conclude that the proposed protocol provides mutual authentication between two participants. Therefore, the proposed protocol can resist the man-in-the-middle attack.


## 5.4. Security Comparison

In this part, we compare the security of the proposed protocol with other multiserver architecture protocols in Table6. We introduce a new independent criterion, which is based on a widely adopted standard [40, 41] as follows:C1 (no password verifier table): the server does not need to maintain a database for storing user passwords or some derived values of user passwords.C2 (password friendly): the password is memorable and can be chosen freely and changed locally by the user.C3 (no password exposure): the password cannot be derived by the privileged administrator of the server.C4 (no smart card loss attack): the scheme is free from smart card loss attack, i.e., unauthorized users getting a victim’s card should not be able to easily change the password of the smart card, recover the victim’s password by using online, offline or hybrid guessing attacks, or impersonate the user to login to the system, even if the smart card is obtained and/or secret data in the smart card are revealed.C5 (resistance to known attacks): the scheme resists various kinds of basic/sophisticated attacks, including offline password guessing attack, replay attack, parallel session attack, desynchronization attack, stolen verifier attack, impersonation attack, key control, unknown key share attack, and known key attack.C6 (sound repairability): the scheme provides smart card revocation with good repairability, i.e., a user can revoke her card without changing her identity.C7 (provision of key agreement): the client and the server can establish a common session key for secure data communications during the authentication process.C8 (no clock synchronization): the scheme is not prone to the problems of clock synchronization and time delay, i.e., the server needs not to synchronize its time clock with these time clocks of all input devices used by smart cards, and vice versa.C9 (timely typo detection): the user will be timely notified if she inputs a wrong password by mistake when login.C10 (mutual authentication): the user and server can verify the authenticity of each other.C11 (user anonymity): the scheme can protect user identity and prevent user activities from being traced.C12 (forward secrecy): the scheme provides the property of perfect forward secrecy.C13 (hierarchical authentication): when a server authenticates with a user, it checks the user’s authentication right. If the user authentication right belongs to the server authentication level, the authentication is successful. Otherwise, the authentication request is denied.Table 6
Performance comparison.
Protocol rounds
Computation cost
Communication cost
Storage cost
Security requirements
User side
Server side
User side
Server side
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
C13
Odelu et al. [14]
3
T
m
t
p
+
4
T
h
+
3
T
s
m
+
2
T
exp
≈
78.519
T
m
t
p
+
4
T
h
+
4
T
exp
+
T
s
m
+
T
mul
+
2
T
b
p
≈
15.303
832
672
1674
✓
✓
✓
✕
✕
✓
✓
✓
✓
✓
✓
✓
✕
He et al. [15]
3
2
T
s
m
+
T
p
a
+
2
T
exp
+
8
T
h
≈
31.837
T
b
p
+
4
T
exp
+
2
T
mul
+
5
T
h
≈
5.246
2240
1184
3424
✓
✓
✓
✕
✕
✕
✓
✓
✕
✓
✓
✓
✕
Ours
2
3
T
s
m
+
2
T
exp
+
T
p
a
+
6
T
h
≈
45.354
2
T
b
p
+
4
T
exp
+
T
s
m
+
T
p
a
+
T
mul
+
7
T
h
≈
11.107
896
672
1834
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓


## 6. Performance Comparison

We show the computation and communication costs of the proposed protocol. We compare its performance with other protocol. For the purpose of getting a trusted security level (1024-bit RSA algorithm), an Ate pairing:e^:G1×G1⟶G2is used. G1 with order q is generated by a point on a supersingular elliptic curve EFp:y2=x3+1 which is defined on the finite field Fp. Order q is a 160-bit prime number and p is a 512-bit prime number.


### 6.1. Computation Cost Comparison

We give the running time of various operations performed in the proposed protocol, and we compare the results with He et al. [15] and Odelu et al. [14]. In this section, we use the following notations for the following running times in this paper:(i)
Tbp: the running time of a bilinear pairing operation(ii)
Tsm: the running time of a scalar multiplication operation in G1(iii)
Tmtp: the running time of a map-to-point hash function in G1(iv)
Tpa: the running time of a point addition operation in G1(v)
Texp: the running time of an exponentiation operation in G2(vi)
Tmul: the running time of a multiplication operation in G2(vii)
Th: the running time of a general hash operationThe above operations are implemented with MIRACLE [42] library on a rooted android mobile phone (A5000 with Qualcomm 801 processor, 2-gigabyte memory, Google Android 4.4.2 operating system) and a personal computer (Lenovo with an i7-6700HQ 2.6 GHz, 16-gigabyte memory, Windows 7® operating system). The running time of those operations is listed in Table 7.Table 7
The running time of related operations (milliseconds).
T
m
t
p
T
b
p
T
s
m
T
p
a
T
exp
T
mul
T
h
User
33.582
32.713
13.405
0.081
2.249
0.008
0.056
Server
4.174
1.665
1.665
0.011
0.260
0.001
0.006We compare the computation costs of the proposed protocol with He et al. [15] and Odelu et al. [14] based on the running time of the user and the service providerand the result is shown in Table 6.


### 6.2. Communication Cost Comparison

According to the description of the trusted security level,q is a 160-bit prime number and p is a 512-bit prime number. The size of an element in G1,G2 is 1024 bits. The size of the hash function’s output is 160 bits, and the identity and the expire parameter are both 32 bits. In our protocol, we only have two rounds of communication for establishing a session key. On client side, the messages C,E,F require 320 + 320+256 = 896 bits, and on service provider side, messages G,g2 require 160 + 512 = 672 bits. The total communication costs are 1568 bits. In He et al.’s [15] protocol, on client side, messages RUi,CUi require 1024 + 32+1024 + 160 = 2240 bits, and on server side, messages y,αSj require 1024 + 160 = 1184 bits. In Odelu et al.’s [14] protocol, on client side, messages M1,M3 require 320 + 512 = 832 bits, and on server side, message M2 require 672 bits. The comparison of communication costs is shown in Table 6.


### 6.3. Storage Cost Analysis

Because the mobile devices are limited to storage spaces, we therefore analyze the storage cost on the user side to show the proposed protocol has reasonable storage cost. In Odelu et al.’s protocol, a user needs to storeEi,Lti,ei,θi,t,e,Lti,P,Ppub,g,q in his/her device, which costs 1674 bits. In He et al.’s protocol, user needs to store Rui,y,asj,gUi,ψUi,vUi,bUi, which costs 3230 bits. In our protocol, user needs to store A,B,θi,ai,e,P,Ppub,g,q, which costs 1834 bits.


## 6.1. Computation Cost Comparison

We give the running time of various operations performed in the proposed protocol, and we compare the results with He et al. [15] and Odelu et al. [14]. In this section, we use the following notations for the following running times in this paper:(i)
Tbp: the running time of a bilinear pairing operation(ii)
Tsm: the running time of a scalar multiplication operation in G1(iii)
Tmtp: the running time of a map-to-point hash function in G1(iv)
Tpa: the running time of a point addition operation in G1(v)
Texp: the running time of an exponentiation operation in G2(vi)
Tmul: the running time of a multiplication operation in G2(vii)
Th: the running time of a general hash operationThe above operations are implemented with MIRACLE [42] library on a rooted android mobile phone (A5000 with Qualcomm 801 processor, 2-gigabyte memory, Google Android 4.4.2 operating system) and a personal computer (Lenovo with an i7-6700HQ 2.6 GHz, 16-gigabyte memory, Windows 7® operating system). The running time of those operations is listed in Table 7.Table 7
The running time of related operations (milliseconds).
T
m
t
p
T
b
p
T
s
m
T
p
a
T
exp
T
mul
T
h
User
33.582
32.713
13.405
0.081
2.249
0.008
0.056
Server
4.174
1.665
1.665
0.011
0.260
0.001
0.006We compare the computation costs of the proposed protocol with He et al. [15] and Odelu et al. [14] based on the running time of the user and the service providerand the result is shown in Table 6.


## 6.2. Communication Cost Comparison

According to the description of the trusted security level,q is a 160-bit prime number and p is a 512-bit prime number. The size of an element in G1,G2 is 1024 bits. The size of the hash function’s output is 160 bits, and the identity and the expire parameter are both 32 bits. In our protocol, we only have two rounds of communication for establishing a session key. On client side, the messages C,E,F require 320 + 320+256 = 896 bits, and on service provider side, messages G,g2 require 160 + 512 = 672 bits. The total communication costs are 1568 bits. In He et al.’s [15] protocol, on client side, messages RUi,CUi require 1024 + 32+1024 + 160 = 2240 bits, and on server side, messages y,αSj require 1024 + 160 = 1184 bits. In Odelu et al.’s [14] protocol, on client side, messages M1,M3 require 320 + 512 = 832 bits, and on server side, message M2 require 672 bits. The comparison of communication costs is shown in Table 6.


## 6.3. Storage Cost Analysis

Because the mobile devices are limited to storage spaces, we therefore analyze the storage cost on the user side to show the proposed protocol has reasonable storage cost. In Odelu et al.’s protocol, a user needs to storeEi,Lti,ei,θi,t,e,Lti,P,Ppub,g,q in his/her device, which costs 1674 bits. In He et al.’s protocol, user needs to store Rui,y,asj,gUi,ψUi,vUi,bUi, which costs 3230 bits. In our protocol, user needs to store A,B,θi,ai,e,P,Ppub,g,q, which costs 1834 bits.


## 7. Conclusion

In this paper, we have proposed a hierarchical authentication protocol for the multiserver environment. The significant contribution of this paper is that we have built an authentication right tree based on the Merkle hash tree, which can be used to verify the authentication right of a user when he/she is authenticating with the service provider. The extended hierarchical authentication feature has added more flexibility and security to multiserver architecture. The security proof has demonstrated that our protocol is provably secure under the random oracle model. Our protocol has reasonable computation and communication costs, which could be suitable for multiserver architecture.



---

*Source: 2523834-2020-03-24.xml*