# Authenticated Diffie-Hellman Key Agreement Scheme that Protects Client Anonymity and Achieves Half-Forward Secrecy

Authors: Hung-Yu Chien
Journal: Mobile Information Systems
 (2015)

---

## Abstract

Authenticated Diffie-Hellman key agreement (D-H key) is the de facto building block for establishing secure session keys in many security systems. Regarding the computations of authenticated D-H key agreement, the operation of modular exponentiation is the most expensive computation, which incurs a heavy loading on those clients where either their computational capacities or their batteries are limited and precious. As client’s privacy is a big concern in several e-commerce applications, it is desirable to extend authenticated D-H key agreement to protect client’s identity privacy. This paper proposes a new problem: the modified elliptic curves computational Diffie-Hellman problem (MECDHP) and proves that the MECDHP is as hard as the conventional elliptic curves computational Diffie-Hellman problem (ECDHP). Based on the MECDHP, we propose an authenticated D-H key agreement scheme which greatly improves client computational efficiency and protects client’s anonymity from outsiders. This new scheme is attractive to those applications where the clients need identity protection and lightweight computation.


---

## Body

## 1. Introduction

Authentication is an essential security; however, many existent authentication schemes either did not provide key agreement during authentication [1–3], did not protect client privacy [4], or required many expensive modular exponentiations [4–16]. Authenticated key agreement aims at simultaneously providing authentication of communicating parties and establishing secure session keys. Nowadays it is very easy for any network operators or even outsiders to collect users’ behavior and violate their privacy when they surf the Internet if key agreement schemes do not protect users’ identities. It is, therefore, imperative to design key agreement schemes which protect client’s identity. With such schemes, users’ privacy can be protected when they enjoy Internet activities, e-commerce or m-commerce transactions.Conventionally, the computational Diffie-Hellman problem over Galis field (called CDHP) and the same problem over elliptic curves (called ECDHP) are the most popular building blocks for many authenticated key agreement schemes [4–8, 10–19], owing to their hardness. However, the modular exponentiation computations over Galis field or the point multiplications over elliptic curves impose a heavy computational stress on those clients where either their computing capacities or their batteries are limited. Such clients are called thin clients in the rest of this paper. Even a native D-H key scheme (not including authentication of communicating parties) that uses the CDHP requires of each party two modular exponentiations, and the corresponding version over elliptic curves would require of each party two point multiplications. Generally an authenticated version of D-H key scheme or an extended version of D-H key scheme which protects client’s anonymity would require more modular exponentiations or more point multiplications [9–12, 14–16, 20], respectively.It is, therefore, important to reduce the number of exponentiation computations/point multiplications for those thin clients. In 2014, Chien [4] formulated the modified computational D-H problem (MCDHP) and proposed an authenticated D-H key agreement scheme, using the MCDHP. The scheme [4] effectively reduced the number of modular exponentiations but it did not protect client’s anonymity.Conventionally, key agreement schemes transmit participants’ identities in plaintext. As privacy has been a big concern in many applications, it is desirable to protect participants’ identities during the key agreement process. Such kinds of key agreement schemes are called authenticated key agreement schemes with client anonymity (or simply an anonymous authenticated key agreement). Chien [12] classified four types of two-party key agreement schemes, according to the protection of participants’ anonymity. Type 1: the privacy of identities of two communicating parties is not protected; this type corresponds to those conventional two-party key agreement schemes. Type 2: the client’s identity is protected from the outsiders, but the identity of the server is not protected. Type 3: the client’s identity is protected from the outsiders, but the anonymity of the server is only protected from unregistered entities. The scenarios for such a type are like that; in a mission-oriented ad hoc network, the clients and the servers want to protect their identities from outsiders, while all the preregistered clients know the IP address or MAC address of the servers. Type 4: both the identity of the client and the identity of the server are protected from outsiders. Type 2 is the most popular one for authenticated key agreement schemes that protect participant’s anonymity, because it corresponds to the cases where clients want to protect their anonymity from outsiders. In this paper, we focus on authenticated two-party key agreement for Type 2 cases and aim to improve client’s computational efficiency.Authentication with anonymity protection is a popular topic, and there are some popular techniques for achieving client’s anonymity during authentication process. Chien [2] classifies existent techniques into four categories: probabilistic encryption-based scheme like the OAKley protocol [13], pseudonym-based schemes like [20], hash-chain-based scheme like Ohkubo et al.’s scheme [1], and error-correction-codes-based scheme like [2, 3]. It is challenging to extend the existent CDHP-based key agreement schemes like [5–7, 13] (or ECDHP-based schemes like [8]) to their anonymous versions and reduce the modular exponentiation load (or the point multiplication load). In this paper, we first formulate a modified ECDHP (MECDHP) and prove its security. Then we propose a new authenticated two-party key agreement scheme with client anonymity, based on the MECDHP problem and Ohkubo et al.’s hashing chain technique [1].The new scheme protects client anonymity, effectively reduces the computational load for client, and preserves the strong security of the ECDHP.The rest of this paper is organized as follows. Section2 introduces the MECDHP and proves its security. Section 3 proposes our new scheme. Section 4 examines its security and evaluates its performance. Section 5 states our conclusions and discussions.


## 2. The MECDHP Problem and the Security Requirements

In this section, we first propose the MECDHP and prove its security. Then we introduce the model and discuss the security requirements of an authenticated key agreement scheme with client anonymity.Elliptic Curves over
G
F
(
p
)
. A nonsupersingular elliptic curve E
(
F
p
) is the set of points P
=
(
x
,
y
) and the point O (called thepoint at infinity), where x
,
y
∈
Z
P satisfy the equation y
2
≡
x
3
+
a
x
+
b
(
mod
⁡
p
) (a
,
b
∈
Z
p are constants, such that 4
a
3
+
27
b
2
≠
0
mod
⁡
p). Two points P
=
(
x
1
,
y
1
) and Q
=
(
x
2
,
y
2
) on the elliptic curve E can be added together using the following rule: if x
2
=
x
1 and y
2
=
-
y
1, then P
+
Q
=
O; otherwise, P
+
Q
=
(
x
3
,
y
3
), where x
3
=
λ
2
-
x
1
-
x
2
mod
⁡
p, y
3
=
λ
(
x
1
-
x
3
)
-
y
1
mod
⁡
p, and λ
=
(
y
2
-
y
1
)
/
(
x
2
-
x
1
) if P
≠
Q or λ
=
(
3
x
1
2
+
a
)
/
(
2
y
1
) if P
=
Q.Definition 1.
The computational elliptic curve Diffie-Hellman problem (ECDHP) is as follows: given an elliptic curve over a finite fieldF
p, a point P
∈
E
(
F
p
) of orderq and points A
=
a
P and B
=
b
P
∈
P find the point C
=
a
b
P.Now we formulate a new problem called the modified computational elliptic curve Diffie-Hellman problem (MECDHP) as follows.Definition 2.
Themodified computational elliptic curve Diffie-Hellman problem (the MECDHP) is as follows: given an elliptic curve over a finite field F
p, a point P
∈
E
(
F
p
) of order q, a
+
x
, and points A
=
x
P and B
=
b
P
∈
P find the point C
=
a
b
P.We prove the hardness of the MECDHP to be as hard as the ECDHP as follows.Theorem 3.
The MECDHP is as hard as the ECDHP.Proof.
We prove this by reduction.
(1) The MECDHP Is Reduced to the ECDHP. Given an instance of the MECDHP problem (x
+
a, P, x
P, and b
P), we can compute (
x
+
a
)
P
-
x
P
=
a
P and get the instance (P, a
P, and b
P) for the ECDHP. Assume there is one oracle that can answer the ECDHP. Now we input the instance (P, a
P, and b
P) to the oracle, and we get the answer a
b
P.
(2) The ECDHP Is Reduced to the MECDHP. Assume there is one oracle that can answer the MECDHP: given (x
+
a, P, x
P, and b
P), it outputs a
b
P.
Now given an instance of the CDHP (P, a
P, and b
P), we then choose a random valuet and input the instance (t, P, a
P, and b
P) to the MECDHP oracle. The oracle will answer b
(
t
P
-
a
P
)
=
b
(
t
-
a
)
P
=
t
b
P
-
a
b
P. Using the response, we can derive -
(
t
b
P
-
a
b
P
-
t
(
b
P
)
)
=
-
(
-
a
b
P
)
=
a
b
P. That is, we get the answer for the ECDHP problem (P, a
P, and b
P).
Based on the above arguments, we prove the theorem.Now we introduce the model and discuss the security requirements of authenticated D-H key agreement scheme with client anonymity as follows. Our model consists of three kinds of entities: clients, servers, and outsiders. Clients would like to establish secure session keys with servers via key agreement schemes and their identities should not be learned by any outsiders. An outsider can actively manipulate the communications via replay, modification, or interception.(1) Consider Mutual authentication of client and server and resistance to various attacks like replay attack, impersonation attack, man-in-the-middle attack, and known key attack.(2) Consider Partial forward secrecy and perfect forward secrecy. Here partial forward secrecy requires that even if we assume one party’s long-term private key is disclosed someday, the previous communications (the session keys before the disclosure) are still secure. If partial forward secrecy is preserved only when one specific party’s private key is compromised but it does not hold for the other party, then it is called half forward secrecy. While perfect forward requires that even if we assume both of the two parties’ long-term private keys are disclosed someday, the previous communications (the session keys before the disclosure) are still secure.(3) Anonymity of the client: the identities of clients should be well protected from outsiders.


## 3. New Authenticated D-H Key Agreement Scheme with Client Anonymity

We introduce the following notations. We will omit the modq operation in the rest of this paper to simplify the presentation when the context is clear.The Notations.
E
(
F
p
),P, andqare as follows: E
(
F
p
) is an elliptic curve over F
p.P
∈
E
(
F
p
) is a generator point for a group over E
(
F
p
).
h
(
), g
(
) are two cryptographic hash functions. Two different hash functions are chosen here to hinder outsiders from tracking users, using correlated data. This idea is inspired by [1]. These functions could be implemented using a pseudorandom function (PRF) with distinct paddings.
C,Sare as follows:C and S, respectively, denote client and server.
I
D
C
,
I
D
S are as follows: I
D
C and I
D
S, respectively, denote the identity of the client and that of the server, where I
D
S is static while I
D
C is dynamically updated.
c,sare as follows: c
,
s
∈
Z
q
∗, respectively, denote the private key of C and that of S.
P
C
,
P
S are as follows: P
C
=
c
P and P
S
=
s
P, respectively, denote their corresponding public keys.
x,yare as follows: x
,
y
∈
Z
q
∗, respectively, denote ephemeral private keys.
X,Yare as follows: X
=
x
P, and Y
=
y
P denotes their corresponding public keys.
⊕, || are as follows: ⊕ denotes the exclusive OR operation. || denotes concatenation. Here we abusively use the notation ⊕ between two elliptic curve points to represent (
x
1
,
y
1
)
⊕
(
x
2
,
y
2
)
=
(
x
1
⊕
x
2
,
y
1
⊕
y
2
).The scheme is depicted in Figure1 and is described as follows.Figure 1
Authenticated D-H key agreement with client anonymity.The scheme consists of two phases: initial phase and key agreement phase.The Initialization Phase. Each registered client C shares its identity I
D
C and public key P
C with the serverS, where S keeps two values I
D
C
,
old and I
D
C
,
new to track the dynamically changing identity of the client. Both I
D
C
,
old and I
D
C
,
new are initialized as I
D
C. Each client keeps the identity and the public key P
S of the server.The Key Agreement Phase.
(1)
S
→
C: I
D
S
,
Y.
The server randomly chooses an integery
∈
R
Z
q
∗, computes Y
=
y
P, and sends (I
D
S
,
Y) to the client.
(2)
C
→
S: g
(
I
D
C
)
,
c
+
x
,
Aut
h
C.
The client chooses a random integerx
∈
R
Z
q
∗ and computes K
C
,
S
=
x
Y, B
L
=
x
P
S, and Aut
h
C
=
h
(
(
P
C
+
K
C
,
S
)
⊕
B
L
). He sends (g
(
I
D
C
)
,
c
+
x
,
Aut
h
C) to the server.
(3)
S
→
C: Aut
h
S.
Upon receiving the client’s data, the server first searches its data base to look up the entry that satisfies eitherg
(
I
D
C
)
=
?
g
(
I
D
C
,
old
) or g
(
I
D
C
)
=
?
g
(
I
D
C
,
new
). The matched entry (I
D
C
,
old or I
D
C
,
new) is referred as I
D
C
,
matched. The server uses the matched entry to get the corresponding public key P
C and computes X
=
(
c
+
x
)
P
-
P
C
=
x
P, B
L
=
s
X
=
s
x
P, and K
C
,
S
=
y
X
=
x
y
P. It then checks whether the equation h
(
(
P
C
+
K
C
,
S
)
⊕
B
L
)
=
?
Aut
h
C holds. If the verification succeeds, then it updates I
D
C
,
old
=
I
D
C
,
matched and I
D
C
,
new
=
h
(
I
D
C
,
matched
) and computes Aut
h
S
=
h
(
P
C
⊕
K
C
,
S
⊕
B
L
).
(4)
C: the client uses its local values to verify the validity of Aut
h
S. If the verification succeeds, then it updates its identity I
D
C as h
(
I
D
C
).
The final session key of the session is computed using any secure hash function: one example is likeh
(
P
C
,
P
S
,
x
+
c
,
Y
,
K
C
,
S
).


## 4. Security Analysis and Performance Evaluation

### 4.1. Security Analysis

In this section, we examine the security of the proposed authenticated D-H key agreement scheme with client anonymity. The formulated MECDHP used in the scheme has been proved to be as hard as the conventional ECDHP. Our new scheme improves the computational efficiency of client while preserving the strong security properties of conventional secure D-H key agreement schemesunder the assumption that the communicating parties’ long-term secret keys are secure. But, the security properties might change when client’s long-term secret keys are compromised. We examine these properties as follows.Authentication of the Client. The authentication of the client depends on its ability of providing a valid Aut
h
C
=
h
(
(
P
C
+
K
C
,
S
)
⊕
B
L
) in response to server’s challenge Y. To have a valid Aut
h
C, the client should be able to providewell-formed “x
+
c,” on which the server can correctly derive the corresponding X
=
(
c
+
x
)
P
-
P
C
=
x
P, B
L
=
s
X
=
s
x
P, and K
C
,
S
=
y
X
=
x
y
P to verify the Aut
h
C. A well-formed “x
+
c” implies that the client knows the private key c. This ensures the authentication of the client.Authentication of the Server. The authentication of server depends on server’s ability of providing a valid Aut
h
S
=
h
(
P
C
⊕
K
C
,
S
⊕
B
L
), which depends on the server’s ability of computing B
L
=
s
X, using X
=
(
c
+
x
)
P
-
P
C
=
x
P. To compute B
L
=
s
X, it requires the knowledge of the server’s private key s. This ensures the authentication of the server.Resistance to Replay Attack and Man-in-the-Middle Attack. The client and the server, respectively, issue new challenges x
+
c and Y in each session. The server is expected to generate the corresponding value B
L
=
s
X
=
s
(
(
x
+
c
)
P
-
P
C
), where the value is derived from the well-formed challenge x
+
c. The client is expected to have the ability of computing the value K
C
,
S
=
x
Y, where Y is the challenge. All of the computations involve new challenges. As long as the challenges are random and fresh, this ensures the resistance to replay attack and man-in-the-middle attack.Half Forward Secrecy. Partial forward secrecy concerns the privacy of session keys corresponding to those sessions before one party’s private key was compromised.(1)
If we assume that the server’s long-term secrets is compromised, then the forward privacy of the session key h
(
P
C
,
P
S
,
x
+
c
,
Y
,
K
C
,
S
) is still preserved, because the computation of the session key involves K
C
,
S. Here the computation of K
C
,
S needs the knowledge of either x or y. This ensures the partial forward secrecy against server’s compromise.
(2)
If we assume the client’s long-term secretc is compromised, then the attacker can derive the ephemeral secret x from x
+
c and derive the session key; that is, our scheme does not preserve partial forward secrecy against client’s compromise. So we call that our scheme ownshalf forward secrecy property but not perfect forward secrecy.Client Anonymity. The client-identity-related data transmitted in our protocol include g
(
I
D
C
), Aut
h
C
=
h
(
(
P
C
+
K
C
,
S
)
⊕
B
L
), and Aut
h
S
=
h
(
P
C
⊕
K
C
,
S
⊕
B
L
). The identity I
D
C is updated as h
(
I
D
C
) per successful authentication, and only its hashed value g
(
I
D
C
) is transmitted. Therefore, an attacker could not learn clients’ identities and could not track any client using eavesdropped data. The other identity-related data is client’s public key P
C. The calculations of Aut
h
C and Aut
h
S first obscure P
C with random value B
L and then apply hashing: this ensures that attackers cannot link the transmissions to any specific client.


### 4.2. Performance Evaluation

Now we examine the performance of our scheme in terms of communication cost and computational cost. Regarding communication cost, we concern the number of message steps and the length of message length. Our scheme requires three message steps. It demands the message length3
L
h
+
2
L
point
+
1
L
q, where L
h denotes the length of hash function (|
h
(
)
| and |
g
(
)
|), L
point denotes the length of string representation of one elliptic curve point, and L
q denotes the bit length ofq.Next we examine the computational cost of our scheme. The client in our scheme demands2
T
PS
+
1
T
PA
+
3
T
XOR
+
3
T
h, where T
PS denotes the time complexity of one elliptic curve point multiplication, T
PA denotes that of one elliptic curve point addition, T
XOR denotes that of one XOR operation, and T
h denotes that of one hash operation. The server averagely needs 4
T
PS
+
2
T
PA
+
3
T
XOR
+
(
n
+
2
)
T
h to find the matched client (each trial for one potential client takes two hash operations), where n denotes the number of entries of potential clients in the database.Table1 summarizes the performance comparison of the proposed scheme with its counterparts. The notations used in the table are introduced in the bottom of the table. The security of the schemes [10–12, 14] is based on RSA and the CDHP problem, and our scheme is based on the MECDHP problem.Please note that even though the authors [15]claimed that their scheme was based on the ECDHP problem but actually its session key security was based on the privacy of nonce and the fixed D-H key(the fixed key
s
P
C
=
c
P
C
=
c
s
P),if one private key of either the server or the client is compromised, then the fixed D-H key and one nonce are compromised; therefore, its security is not strong as the ECDHP.Table 1
Summary of performance comparison among two-party key agreement schemes with client anonymity.
Scheme
Ours.
Yoon-You [11]
Chien [12]
Yang et al. [10]
Wu-Hsu [14]
Wang et al. [15]
Number of steps
3
3
3
3
3
3
Length of message
3
L
h
+
2
L
point
+
1
L
q
3
L
N
+
1
L
Time
+
1
L
ID
3
L
N
+
1
L
Time
+
1
L
ID
3
L
N
+
1
L
Time
+
1
L
ID
3
L
N
+
1
L
Time
5
L
nonce
+
4
L
point
+
1
L
ID
Computational cost of client
2
T
PS
+
T
PA
+
3
T
XOR
+
3
T
h
5
T
exp
⁡
+
2
T
multi
+
1
T
enc
5
T
exp
⁡
+
1
T
multi
+
1
T
enc
+
2
T
h
5
T
exp
⁡
+
3
T
multi
+
1
T
enc
+
1
T
h
4
T
exp
⁡
+
3
T
multi
+
1
T
h
4
T
PS + 2
T
enc + 3
T
h
Computational cost for server
4
T
PS
+
2
T
PA
+
3
T
XOR
+
(
n
+
2
)
T
h
5
T
exp
⁡
+
2
T
multi
+
1
T
enc
5
T
exp
⁡
+
2
T
multi
+
1
T
enc
+
2
T
h
5
T
exp
⁡
+
2
T
multi
+
1
T
enc
+
1
T
h
4
T
exp
⁡
+
2
T
multi
+
1
T
h
4
T
PS
+
2
T
enc
+
3
T
h
Security properties
Mutual auth.
Mutual auth.
Mutual auth.
Client/server impersonation [11]
Client/server impersonation [11]
Mutual auth.
Client anonymity
Yes
Fail (Note5)
Yes
Yes
Yes
Yes
Forward secrecy
Half forward secrecy
Yes
Yes
Yes
Yes
Note3
NP problem
MCDHP
RSA, CDHP
RSA, CDHP
RSA, CDHP
RSA, CDHP
Note3
Note1: L
N: the bit length of RSA modulus N; L
h: the length of hash function (h
(
) and g
(
)); L
point: the length of string representation of one elliptic curve point, and L
q denotes the bit length of q. L
Time: the bit length of timestamp; L
ID: the length of identity; L
nonce: the length of nonce.
Note2: T
PS: time complexity of one elliptic curve point multiplication; T
PA: time complexity for one elliptic curve point addition; T
XOR: time complexity for one XOR operation; T
h: time complexity  for one hash operation; T
exp
⁡: time complexity of one modular exponentiation; T
multi: time complexity of one modular multiplication; T
enc: time complexity of one symmetric encryption.
Note3: The session key security was based on the privacy of nonce and the fixed D-H key (the fixed key s
P
C
=
c
P
C
=
c
s
P). If one private key of either the server or the client is compromised, then the long-term, fixed D-H key is compromised and one of the nonce is compromised; therefore, its security is not strong as the ECDHP.
Note4: Our scheme applies hashing to protect the dynamic identity while other schemes use encryption of identity to protect anonymity; therefore, we can simplify the comparison by assuming L
h
=
L
ID.
Note5: Chien [12] reported the failure of client anonymity of Yoon-You’s scheme [11].Regarding the communicational performance, we focus on the number of message steps and the length of the messages. According to National Security Agency of the USA [18], to have an equivalent security of an 80-bit symmetric encryption, RSA algorithm and Diffie-Hellman algorithm need 1024-bit key while ECC only needs 160-bit key. From the table, we can see that all the schemes require three message steps. Because the schemes [9–12, 14] used RSA and the CDHP, their message length is larger than our scheme and the scheme [15]. And, the message length of our scheme is shorter than its ECC-based counterpart [15].Now we compare the computational performance. Recently there have been several publications like [21–24] discussing the implementation performances of ECC standard and other public-key standards (like RSA and El-Gamal public key), where [21] compared various software implementations of point multiplication, [22] aimed at improving hardware implementation of point multiplication, [23] discussed the hardware implementation performance of RSA digital signature and ECDSA, and [24] compared implementation performance of El-Gamal elliptic curve encryption method using two different libraries. These works focused on the implementation performances of elliptic curve point multiplication and related standards (like ECC standards, RSA digital signature, and El-Gamal elliptic curve encryption). For a fair comparison of custom-designed algorithms that consist of underlying field operations (like field multiplication and exponentiation in Z
p, field multiplication in Z
q, and elliptic curve point multiplication), the figures in NSA [18] and the algebra equations of elliptic curve operations in terms of underlying field operations from [19] have been widely adopted [15]. We adopt the same principle in the following evaluation, since it gives a fair comparison of custom-designed algorithms.The security of ECC with 160-bit key is equivalent to that of RSA with 1024-bit key or D-H algorithm with 1024-bit key. Under the above figures,T
multi
,
p (the time complexity of a field multiplication in Z
p, where p is 1024-bit) is 41 times T
multi
,
q (the time complexity of field multiplication in Z
q, where q is 160-bit), T
PS
~
=
29
T
multi
,
p, T
exp
⁡
~
=
240
T
multi
,
p
~
=
8
T
PS, T
PA
~
=
0.12
T
multi
,
p, and T
PS
~
=
241 T
PA, where ~
= means “roughly equal.” To simplify the comparison and get an insight of the computational performance, we can focus on the number of ECC point multiplications, point addition, modular exponentiation, and modular multiplication only because the other operations are not computationally significant. In this simplification, the client in our scheme needs 2
T
PS
+
T
PA
~
=
58.12
T
multi
,
p, the client in [11] needs 5
T
exp
⁡
+
2
T
multi
,
p
~
=
1202
T
multi
,
p, the client in [12] takes 5
T
exp
⁡
+
1
T
multi
,
p
~
=
1201
T
multi
,
p, the client in [10] requires 5
T
exp
⁡
+
3
T
multi
,
p
~
=
1203
T
multi
,
p, the client in [14] demands 4
T
exp
⁡
+
3
T
multi
,
p
~
=
9633
T
multi
,
p, and the client in Wang et al.’s scheme [15] requires 4
T
PS
~
=
116
T
multi
,
p. Based on these figures, we can get an insight that the client in our scheme only takes roughly 1/20 computational complexity of those RSA-based schemes like [10–12, 14] and takes only 1/2 time complexity of Wang et al.’s ECC-based scheme [15].


## 4.1. Security Analysis

In this section, we examine the security of the proposed authenticated D-H key agreement scheme with client anonymity. The formulated MECDHP used in the scheme has been proved to be as hard as the conventional ECDHP. Our new scheme improves the computational efficiency of client while preserving the strong security properties of conventional secure D-H key agreement schemesunder the assumption that the communicating parties’ long-term secret keys are secure. But, the security properties might change when client’s long-term secret keys are compromised. We examine these properties as follows.Authentication of the Client. The authentication of the client depends on its ability of providing a valid Aut
h
C
=
h
(
(
P
C
+
K
C
,
S
)
⊕
B
L
) in response to server’s challenge Y. To have a valid Aut
h
C, the client should be able to providewell-formed “x
+
c,” on which the server can correctly derive the corresponding X
=
(
c
+
x
)
P
-
P
C
=
x
P, B
L
=
s
X
=
s
x
P, and K
C
,
S
=
y
X
=
x
y
P to verify the Aut
h
C. A well-formed “x
+
c” implies that the client knows the private key c. This ensures the authentication of the client.Authentication of the Server. The authentication of server depends on server’s ability of providing a valid Aut
h
S
=
h
(
P
C
⊕
K
C
,
S
⊕
B
L
), which depends on the server’s ability of computing B
L
=
s
X, using X
=
(
c
+
x
)
P
-
P
C
=
x
P. To compute B
L
=
s
X, it requires the knowledge of the server’s private key s. This ensures the authentication of the server.Resistance to Replay Attack and Man-in-the-Middle Attack. The client and the server, respectively, issue new challenges x
+
c and Y in each session. The server is expected to generate the corresponding value B
L
=
s
X
=
s
(
(
x
+
c
)
P
-
P
C
), where the value is derived from the well-formed challenge x
+
c. The client is expected to have the ability of computing the value K
C
,
S
=
x
Y, where Y is the challenge. All of the computations involve new challenges. As long as the challenges are random and fresh, this ensures the resistance to replay attack and man-in-the-middle attack.Half Forward Secrecy. Partial forward secrecy concerns the privacy of session keys corresponding to those sessions before one party’s private key was compromised.(1)
If we assume that the server’s long-term secrets is compromised, then the forward privacy of the session key h
(
P
C
,
P
S
,
x
+
c
,
Y
,
K
C
,
S
) is still preserved, because the computation of the session key involves K
C
,
S. Here the computation of K
C
,
S needs the knowledge of either x or y. This ensures the partial forward secrecy against server’s compromise.
(2)
If we assume the client’s long-term secretc is compromised, then the attacker can derive the ephemeral secret x from x
+
c and derive the session key; that is, our scheme does not preserve partial forward secrecy against client’s compromise. So we call that our scheme ownshalf forward secrecy property but not perfect forward secrecy.Client Anonymity. The client-identity-related data transmitted in our protocol include g
(
I
D
C
), Aut
h
C
=
h
(
(
P
C
+
K
C
,
S
)
⊕
B
L
), and Aut
h
S
=
h
(
P
C
⊕
K
C
,
S
⊕
B
L
). The identity I
D
C is updated as h
(
I
D
C
) per successful authentication, and only its hashed value g
(
I
D
C
) is transmitted. Therefore, an attacker could not learn clients’ identities and could not track any client using eavesdropped data. The other identity-related data is client’s public key P
C. The calculations of Aut
h
C and Aut
h
S first obscure P
C with random value B
L and then apply hashing: this ensures that attackers cannot link the transmissions to any specific client.


## 4.2. Performance Evaluation

Now we examine the performance of our scheme in terms of communication cost and computational cost. Regarding communication cost, we concern the number of message steps and the length of message length. Our scheme requires three message steps. It demands the message length3
L
h
+
2
L
point
+
1
L
q, where L
h denotes the length of hash function (|
h
(
)
| and |
g
(
)
|), L
point denotes the length of string representation of one elliptic curve point, and L
q denotes the bit length ofq.Next we examine the computational cost of our scheme. The client in our scheme demands2
T
PS
+
1
T
PA
+
3
T
XOR
+
3
T
h, where T
PS denotes the time complexity of one elliptic curve point multiplication, T
PA denotes that of one elliptic curve point addition, T
XOR denotes that of one XOR operation, and T
h denotes that of one hash operation. The server averagely needs 4
T
PS
+
2
T
PA
+
3
T
XOR
+
(
n
+
2
)
T
h to find the matched client (each trial for one potential client takes two hash operations), where n denotes the number of entries of potential clients in the database.Table1 summarizes the performance comparison of the proposed scheme with its counterparts. The notations used in the table are introduced in the bottom of the table. The security of the schemes [10–12, 14] is based on RSA and the CDHP problem, and our scheme is based on the MECDHP problem.Please note that even though the authors [15]claimed that their scheme was based on the ECDHP problem but actually its session key security was based on the privacy of nonce and the fixed D-H key(the fixed key
s
P
C
=
c
P
C
=
c
s
P),if one private key of either the server or the client is compromised, then the fixed D-H key and one nonce are compromised; therefore, its security is not strong as the ECDHP.Table 1
Summary of performance comparison among two-party key agreement schemes with client anonymity.
Scheme
Ours.
Yoon-You [11]
Chien [12]
Yang et al. [10]
Wu-Hsu [14]
Wang et al. [15]
Number of steps
3
3
3
3
3
3
Length of message
3
L
h
+
2
L
point
+
1
L
q
3
L
N
+
1
L
Time
+
1
L
ID
3
L
N
+
1
L
Time
+
1
L
ID
3
L
N
+
1
L
Time
+
1
L
ID
3
L
N
+
1
L
Time
5
L
nonce
+
4
L
point
+
1
L
ID
Computational cost of client
2
T
PS
+
T
PA
+
3
T
XOR
+
3
T
h
5
T
exp
⁡
+
2
T
multi
+
1
T
enc
5
T
exp
⁡
+
1
T
multi
+
1
T
enc
+
2
T
h
5
T
exp
⁡
+
3
T
multi
+
1
T
enc
+
1
T
h
4
T
exp
⁡
+
3
T
multi
+
1
T
h
4
T
PS + 2
T
enc + 3
T
h
Computational cost for server
4
T
PS
+
2
T
PA
+
3
T
XOR
+
(
n
+
2
)
T
h
5
T
exp
⁡
+
2
T
multi
+
1
T
enc
5
T
exp
⁡
+
2
T
multi
+
1
T
enc
+
2
T
h
5
T
exp
⁡
+
2
T
multi
+
1
T
enc
+
1
T
h
4
T
exp
⁡
+
2
T
multi
+
1
T
h
4
T
PS
+
2
T
enc
+
3
T
h
Security properties
Mutual auth.
Mutual auth.
Mutual auth.
Client/server impersonation [11]
Client/server impersonation [11]
Mutual auth.
Client anonymity
Yes
Fail (Note5)
Yes
Yes
Yes
Yes
Forward secrecy
Half forward secrecy
Yes
Yes
Yes
Yes
Note3
NP problem
MCDHP
RSA, CDHP
RSA, CDHP
RSA, CDHP
RSA, CDHP
Note3
Note1: L
N: the bit length of RSA modulus N; L
h: the length of hash function (h
(
) and g
(
)); L
point: the length of string representation of one elliptic curve point, and L
q denotes the bit length of q. L
Time: the bit length of timestamp; L
ID: the length of identity; L
nonce: the length of nonce.
Note2: T
PS: time complexity of one elliptic curve point multiplication; T
PA: time complexity for one elliptic curve point addition; T
XOR: time complexity for one XOR operation; T
h: time complexity  for one hash operation; T
exp
⁡: time complexity of one modular exponentiation; T
multi: time complexity of one modular multiplication; T
enc: time complexity of one symmetric encryption.
Note3: The session key security was based on the privacy of nonce and the fixed D-H key (the fixed key s
P
C
=
c
P
C
=
c
s
P). If one private key of either the server or the client is compromised, then the long-term, fixed D-H key is compromised and one of the nonce is compromised; therefore, its security is not strong as the ECDHP.
Note4: Our scheme applies hashing to protect the dynamic identity while other schemes use encryption of identity to protect anonymity; therefore, we can simplify the comparison by assuming L
h
=
L
ID.
Note5: Chien [12] reported the failure of client anonymity of Yoon-You’s scheme [11].Regarding the communicational performance, we focus on the number of message steps and the length of the messages. According to National Security Agency of the USA [18], to have an equivalent security of an 80-bit symmetric encryption, RSA algorithm and Diffie-Hellman algorithm need 1024-bit key while ECC only needs 160-bit key. From the table, we can see that all the schemes require three message steps. Because the schemes [9–12, 14] used RSA and the CDHP, their message length is larger than our scheme and the scheme [15]. And, the message length of our scheme is shorter than its ECC-based counterpart [15].Now we compare the computational performance. Recently there have been several publications like [21–24] discussing the implementation performances of ECC standard and other public-key standards (like RSA and El-Gamal public key), where [21] compared various software implementations of point multiplication, [22] aimed at improving hardware implementation of point multiplication, [23] discussed the hardware implementation performance of RSA digital signature and ECDSA, and [24] compared implementation performance of El-Gamal elliptic curve encryption method using two different libraries. These works focused on the implementation performances of elliptic curve point multiplication and related standards (like ECC standards, RSA digital signature, and El-Gamal elliptic curve encryption). For a fair comparison of custom-designed algorithms that consist of underlying field operations (like field multiplication and exponentiation in Z
p, field multiplication in Z
q, and elliptic curve point multiplication), the figures in NSA [18] and the algebra equations of elliptic curve operations in terms of underlying field operations from [19] have been widely adopted [15]. We adopt the same principle in the following evaluation, since it gives a fair comparison of custom-designed algorithms.The security of ECC with 160-bit key is equivalent to that of RSA with 1024-bit key or D-H algorithm with 1024-bit key. Under the above figures,T
multi
,
p (the time complexity of a field multiplication in Z
p, where p is 1024-bit) is 41 times T
multi
,
q (the time complexity of field multiplication in Z
q, where q is 160-bit), T
PS
~
=
29
T
multi
,
p, T
exp
⁡
~
=
240
T
multi
,
p
~
=
8
T
PS, T
PA
~
=
0.12
T
multi
,
p, and T
PS
~
=
241 T
PA, where ~
= means “roughly equal.” To simplify the comparison and get an insight of the computational performance, we can focus on the number of ECC point multiplications, point addition, modular exponentiation, and modular multiplication only because the other operations are not computationally significant. In this simplification, the client in our scheme needs 2
T
PS
+
T
PA
~
=
58.12
T
multi
,
p, the client in [11] needs 5
T
exp
⁡
+
2
T
multi
,
p
~
=
1202
T
multi
,
p, the client in [12] takes 5
T
exp
⁡
+
1
T
multi
,
p
~
=
1201
T
multi
,
p, the client in [10] requires 5
T
exp
⁡
+
3
T
multi
,
p
~
=
1203
T
multi
,
p, the client in [14] demands 4
T
exp
⁡
+
3
T
multi
,
p
~
=
9633
T
multi
,
p, and the client in Wang et al.’s scheme [15] requires 4
T
PS
~
=
116
T
multi
,
p. Based on these figures, we can get an insight that the client in our scheme only takes roughly 1/20 computational complexity of those RSA-based schemes like [10–12, 14] and takes only 1/2 time complexity of Wang et al.’s ECC-based scheme [15].


## 5. Conclusions and Further Investigations

This paper has formulated a new problem called the MECDHP and has proved its security being equivalent to the conventional ECDHP. Based on the MECDHP, we have proposed a new authenticated D-H key agreement scheme which protects client anonymity and greatly improves client’s computational efficiency. Based on the figures of 160-bit ECC key and 1024-bit RSA key (or 1024-bit D-H algorithm), the client of our scheme requires only 1/20 time complexity of its RSA-based counterparts [10–12, 14] and takes only 1/2 time complexity of Wang et al.’s ECC-based scheme [15]. Security analysis shows that the scheme achieves half forward secrecy: it achieves forward secrecy if server’s private key is compromised but the session keys of a compromised client would be disclosed. Here we note that it only affects the session keys of compromised clients. These excellent performances make our scheme quite attractive to those thin clients that require anonymity protection. One interesting open issue is whether we can improve the computational efficiency of existent authenticated D-H key agreement schemes while still preserving the perfect forward secrecy.



---

*Source: 354586-2015-05-03.xml*