# An eCK-secure authenticated key exchange protocol without random oracles.

1. IntroductionA two-party key exchange protocol is a cryptographic protocol between Alice and Bob in which each party communicates with each other over an insecure channel and shares a common session key. The most famous key exchange protocol is the Diffie-Hellman key exchange, which is secure against a benign adversary who passively eavesdrops on the party's communication. However, it is well-known that the Diffie-Hellman protocol is insecure against an active adversary who can control and modify the exchanged messages (i.e., man-in-the-middle attacks). A protocol proven secure against an active adversary is called an authenticated key exchange (AKE) protocol. In a public key infrastructure (PKI) based AKE protocol, each party possesses static secret key used for static public key, in addition to the ephemeral secret key used for ephemeral public key (ephemeral secret/public key is randomly selected per session), and computes the session key.

The security definitions for two-party key exchange were developed by several researchers [1][2][3][4]. In their literature, an active adversary can obtain several types of secret information. The main difference among the security definitions in these papers is that an adversary can obtain what kind of internal secret of the party (static secret key, ephemeral secret key and session key). Among these papers, LaMacchia, Lauter and Mityagin [4] presented a strong security definition for two-pass key exchange protocol, which we call the extended Canetti-Krawczyk (eCK) security model. This security model allows an active adversary to obtain various private information regarding a target session and it captures many known desirable security properties for AKE including the resistance to key-compromise impersonation (KCI) attacks, weak perfect forward secrecy (wPFS), and resilience to the leakage of ephemeral secret keys (RLE).

There are some protocols proven in the eCK security model [4] [5] [6] [7] [8][9][10][11][12] [13]. The first eCK-secure AKE protocol, called NAXOS, was proposed by LaMacchia, Lauter and Mityagin [4]. NAXOS is provably secure in the random oracle model under the gap Diffie-Hellman (GDH) assumption. In their paper, they used an implementation technique that we call the NAXOS trick. Ustaoglu employed the NAXOS trick to the HMQV protocol [14] and proposed an eCK-secure AKE protocol called CMQV [5]. HMQV is secure in a slight variant of the Canetti-Krawczyk security model and satisfies the KCI-security, wPFS and RLE, but has not been proven to be eCK-secure. CMQV is eCK-secure in the random oracle model under the GDH assumption. Lee et al. proposed two eCK-secure key exchange protocols to improve the efficiency of the security reduction or complexity assumption [7][8], but these protocols also use the NAXOS trick and are provably secure in the random oracle model. Okamoto [6] presented an eCK-secure key exchange protocol without random oracles and under the NAXOS trick. Therefore, many of the eCK-secure AKE protocols rely on the NAXOS trick.

The NAXOS trick is an implementation technique that hides the exponent of an ephemeral public key from an adversary even if the adversary obtains the ephemeral secret key. In a typical Diffie-Hellman based key exchange protocol, the ephemeral secret key, x, is used as the exponent of the ephemeral public key such as X := [g.sup.x]. However, in a key exchange protocol that utilizes the NAXOS trick, the exponent of the ephemeral public key is generated by hashing of the ephemeral secret key, x, and the static secret key, a , e.g., H(x,a) . Therefore, even if the secrity model allows an adversary to obtain the ephemeral secret key, the exponent of the ephemeral public key is still unknown to the adversary. Recently, Ustaoglu [10], Kim et al. [11], Sarr et al. [12], and Moriyama-Okamoto [13] proposed eCK-secure key exchange protocols without the NAXOS trick. The main motivation to avoid the NAXOS trick is to consider the leakage of the exponent of the ephemeral public key since it may be revealed via side-channel attacks or power analysis in a realistic setting. Therefore, even though the NAXOS trick hides the exponent of the ephemeral public key, it may be leaked via such side-channel attacks and then the eCK security is no longer ensured for AKE protocols that employs the NAXOS trick.

We present a new eCK-secure AKE protocol that does not use the NAXOS trick, which is provably secure without random oracles, and is as efficient as Okamoto protocol [6]. The exponent, i.e., the ephemeral secret key of an ephemeral public key, is purely independent from the static secret key and the risk of leaking the static secret key is reduced. We note that all AKE protocols provided in [10], [11] and [12] are provably secure in the random oracle model and that this does not imply the security in the real world (see [15]). In comparison to [13], the size of the static secret/public key is reduced and the session key computation is further improved. Nonetheless, we can provide a security proof under the eCK security model. The proposed protocol is an extended version of the Okamoto protocol [6] and is eCK-secure without random oracles under the Decision Diffie-Hellman (DDH) assumption, pair-wise independent pseudo-random function family, and collision resistant hash function family.

2. Preliminaries

2.1 Notation

When B is a probabilistic machine or algorithm, A(x) denotes the random variable of the output of A on input [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denotes that y is randomly selected from A(x) according to its distribution. Then, A(x) [right arrow] a indicates the event that A outputs a on input x if a is a value. When A is a set, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] means that y is uniformly selected from A . When A is a value, y := x denotes that A is set as y.

2.2 The DDH assumption

Let G be a group of prime order q and [{[G.sub.k]}.sub.k] be set of group G with security parameter k . For all k [member of] N, we define sets D(k):={(G, [g.sub.1], [g.sub.2], [g.sup.*.sub.1], [g.sup.*.sub.2])| G [member of] [{G}.sub.k], [g.sub.1], [g.sub.2] [member of] [G.sup.2], x [member of] [Z.sub.q]} and R(k) := (G, [g.sub.1][g.sub.2][y.sub.1],[y.sub.2]) | G [member of] [{G}.sub.k], ([g.sub.1],[g.sub.2], [y.sub.1],[y.sub.2] [member of] [G.sup.4]}.

The DDH advantage of algorithm M is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

for all k [member of] N. We say that the DDH assumption holds in [{[G.sub.k]}.sub.k[member of]N] if for any probabilistic polynomial-time adversary M, [Adv.sup.DDH.sub.M] (k) is negligible in k .

2.3 Pseudo-Random Function (PRF)

Let k [member of] N be a security parameter. A pseudo-random function (PRF) family F associated

with [{[seed.sub.k]}.sub.k[member of]N], [{[Dom.sub.k] }.sub.k[member of]N] and {[Rng.sub.k]}.sub.k[member of]N] is indexed by k. When [sigma] is randomly chosen from random seeds [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] maps an element of D to an element of R where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let [A.sup.O] be a probabilistic polynomial-time machine with oracle access to O. The advantage of algorithm AO breaking the PRF function is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and F := [F.sup.k,[SIGMA],D,R], and RF: D [right arrow] R is a truly random function. F is a PRF family if for any probabilistic polynomial-time adversary M, [Adv.sup.PRF.sub.F,M] (k) is negligible in k .

2.4 Pseudo-Random Function with Pairwise Independent Random Sources ([pi] PRF)

Okamoto [6] introduced a specific class of PRF, [pi] PRF. As described in Section 2.3, the traditional PRF takes as input a (truly random) seed and it is reused many times. However, if this is determined by the output of a cryptographic primitive in each invocation, two or more seeds may be correlated. Note that the PRF family is useless in this setting. Nonetheless, [pi] PRF states that if a specific variable [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (associated with 'seed') is pairwise-independent from the other variables, then the output of the function with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is indistinguishable from random.

Suppose that [f.sub.SIGMA] : [I.sub.SIGMA] [right arrow] [X.sub.SIGMA] is a deterministic polynomial-time algorithm, where [X.sub.SIGMA] is a set of random variables and [I.sub.SIGMA] is a set of indices regarding [SIGMA], then this algorithm outputs [[sigma].sub.i] [member of] [X.sub.SIGMA] from i [??][I.sub.SIGMA]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be pairwise independent random variables indexed by ([I.sub.SIGMA], [f.sub.SIGMA]), and each variable be uniformly distributed over [SIGMA]. That is, for any pair of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], for any (x, y) [??] [[SIGMA].sup.2], we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Consider a probabilistic polynomial-time machine [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] that can issue oracle queries. When M sends [q.sub.j] [member of] D and [i.sub.j] [member of] [I.sub.[SIGMA]] to the query, the oracle replies with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for each j = 0,1,...,t(k), where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the same as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] except [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is replaced by a truly random function RF([q.sub.0]). The advantage of algorithm M breaking the n PRF function is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

We say that F is a [pi] PRF family if for any probabilistic polynomial-time adversary M , [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is negligible in k .

Okamoto presented an example of index ([I.sub.[SIGMA]], [f.sub.[SIGMA]]) for the [pi] PRF function. For group G of prime order q,

[I.sub.g] := {(U,V,d)|(U,V,d) [member of] [G.sup.2] x [Z.sub.q]}, (4)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

[f.sub.G] : [I.sub.G] [right arrow] [X.sub.g] (6)

is a pair-wise independent pseudo-random function (See [7]).

2.5 Collision Resistant (CR) Hash Function

Let k [??] N be a security parameter. Collision resistant (CR) hash function family H associated with {[Dom.sub.k]}.sub.k[member of]N] and {[Rng.sub.k]}.sub.k[member of]N] specifies two items:

1. A family of key spaces indexed by k. Each such key space is a probability space on bit strings denoted by K[H.sub.k]. There must be a probabilistic polynomial-time algorithm whose output distribution on input [l.sup.k] is equal to K[H.sub.k].

2. A family of hash functions indexed by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and {[Rng.sub.k]}.sub.k[member of]N] , where each such function [H.sup.k,D,R.sub.h] maps an element of D to an element of R . There must exist a deterministic polynomial-time algorithm that on input [1.sup.k], h and [rho] [member of] D , output [H.sup.k,D,R.sub.h] ([rho]).

We define the advantage of algorithm M breaking the CR hash function as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. H is a CR hash function family if for any probabilistic polynomialtime adversary M, [Adv.sup.CR.sub.H,M] (k) is negligible in k .

3. The Extended Canetti-Krawczyk (eCK) Security Model

The eCK security model was originally introduced by LaMacchia, Lauter and Mityagin [4]. We refer the reader to [4][5] and [13] for more background.

Suppose that there are n parties that are modeled as probabilistic polynomial-time Turing machines. Each party generates a static public/secret key pair and the static public key is certificated by a certification authority. When we consider two parties Alice and Bob, Alice has static public key A and Bob has static public key B. The certified public key, [??] ([??]), binds the identity of the party, the static public key and its certificate. The precise certification procedure is dependent on its implementation, but we assume that if the key exchange protocol explicitly specifies the proof of knowledge for a part of the static public key, each party is required to prove the knowledge of a part of the corresponding static secret key by some method, e.g., by a zero-knowledge proof of knowledge or in an administrative manner, to obtain a certificate of the static public key. Otherwise, the certification authority only checks whether or not the static public key is included in the certain static public key space. As denoted in [13], here we only assume two conditions for the proof of knowledge (we do not assume any specific method for the proof):

1. There exists an efficient (or polynomial-time) measure using the corresponding party as a black-box to extract the secret key (with overwhelming probability).

2. Any adversary obtains (information theoretically) no additional information via the process of the proof of knowledge if the corresponding party is honest (see the definition of 'honest' later).

When a key exchange protocol is executed, each party starts an instance of the protocol called a session. When Alice executes a key exchange protocol with Bob, she is activated by an incoming message: ([??],[??]) or ([??],[??], Y) where Y denotes the ephemeral public key of Bob. If Alice receives ([??],[??]), she is called the initiator. Alice generates ephemeral public/secret key pair (X, x) and sends ([??],[??],X) to Bob. When Bob receives ([??],[??],X) , he is called the responder. Bob generates ephemeral public/static key pair (Y , y) and responds with ([??],[??],X,Y) to Alice. When an execution of the party is finished and outputs the session key, the session is said to be completed. Even if a party concurrently executes many sessions with many parties, each session is uniquely determined by the session identifier. The session identifier is in the form of (role, [??],[??], X, Y), which indicates that owner Alice who is activated as role [member of] {initiator, responder} executes a session with Bob. The ephemeral public key X is included in the first message of the protocol (outgoing or incoming) and Y is included in the second message. If there exists a session identifier in the form of (role', [??],[??],X, Y) against (role, [??],[??], X, Y) where role [not equal to] role', these sessions are said to be matching.

The adversary, M, is modeled as a probabilistic polynomial-time Turing machine and controls all communications. The adversary activates parties with incoming messages via the Send(message), thereby controlling the activation of sessions. Furthermore, M can issue the following queries.

EphemeralKeyReveal(SID)--The adversary obtains the ephemeral secret key for the session SID.

SessionKeyReveal(SID)--The adversary obtains the session key for the completed session SID.

StaticKeyReveal(PID)--The adversary obtains the static secret key of party PID.

EstablishParty( PID, Z)--The adversary registers a static public key Z on behalf of party PID. The party is controlled by the adversary.

If a party PID is established by EstablishParty( PID, Z) then we call the party dishonest. If a party is not dishonest, we call the party honest.

When adversary M issues test query Test(SID*), bit [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is chosen. If b = 1, M receives the actual session key SK * of the test session SID*. Otherwise, M is given random key R* where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Finally, M outputs bit b' [member of] {0,1} for the test query. To define the advantage of M, we need the notation of a fresh session given hereafter.

Definition 1: (fresh session of eCK security) Let SID:= (role, [??], [??], X, Y) be the session identifier executed by honest parties Alice and Bob. We define the matching session of SID as [bar.SID], if it exists.

We define session SID to be fresh if none of the following conditions hold.

1. M issues

--SessionKeyReveal(SID), or

--SessionKeyReveal([bar.SID]) (if [bar.SID] exists).

2. If [bar.SID] exists, then M issues

--Both StaticKeyReveal([??]) and EphemeralKeyReveal(SID), or

--Both StaticKeyReveal([??]) and EphemeralKeyReveal([bar.SID]).

3. If [bar.SID] does not exists, then M issues

--Both StaticKeyReveal([??]) and EphemeralKeyReveal( SID), or

--StaticKeyReveal([??]).

Definition 2: (eCK security) Let test session SID*, where adversary M issues Test (SID*), be fresh. Then, we define the advantage of M by

[Adv.sup.eCK.sub.M](k) := |2 * Pr[b' = b]-1| (8)

A key exchange protocol is eCK-secure if the following conditions hold.

1. If two honest parties complete matching sessions, they compute the same session key.

2. For any probabilistic polynomial-time adversary M, [Adv.sup.eCK.sub.M](k) is negligible in k .

4. The NAXOS Trick

The NAXOS trick is one of the implementation techniques proposed by LaMacchia, Lauter, and Mityagin [4] to construct an eCK-secure key exchange protocol. In a typical key exchange protocol, ephemeral public key X is computed by X := [g.sup.x] and x is the ephemeral secret key. If adversary M issues an ephemeral key reveal query to the session, M can directly obtain x, which is the exponent of X .

On the other hand, the NAXOS trick specifies that ephemeral public key X is computed by X := [g.sup.[bar.x]], where [??] is the hashing of ephemeral secret key x and static secret key a, i.e., [??] := H(x, a). The hashed value, [??], is not stored as the ephemeral secret key but is computed each time when required. So, adversary M cannot directly obtain the exponent of X, even if M issues an ephemeral key reveal query.

This trick is adopted by many of the existing eCK-secure key exchange protocols [4][5][6][7][8]. However, this technique does not work in some realistic settings such as side-channel attacks. For example, [??] with X:= [g.sup.[??]] x may be revealed to an adversary through up-to-date power-analysis. Therefore, an eCK-secure protocol based on the NAXOS trick may be vulnerable (in the sense of the eCK security) to some realistic side-channel attacks.

5. The Proposed Protocol

We propose an eCK-secure key exchange protocol that does not use the "NAXOS trick."

5.1 Protocol

Let k [member of] N be a security parameter and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be a group that has prime order q with |q| = k . Set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let [{H}.sub.k] be a CR hash function family and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be an index of CR hash function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [D.sub.H] := [([[pi].sub.k]).sup.2] x [G.sup.6], [R.sub.H] := [Z.sub.q] and [[pi].sub.k] denotes the space of certified static public keys. Let F be a [pi] PRF family and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [[SIGMA].sub.F] := G, [D.sub.F] := [([[PI].sub.k]).sup.2] x [G.sup.6] and [R.sub.F] := [{0,1}.sup.k] . The system parameter of the proposed AKE protocol is (G,[g.sub.1],[g.sub.2],[H.sub.1],[H.sub.2] ,F).

Party Alice selects static secret key [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and computes static public key [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Similarly, Bob selects static secret key [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and computes static public key [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In this protocol, a party is required to prove the knowledge of a part of the static secret key, from the first component to the fourth component (e.g., ([a.sub.1] ..., [a.sub.4]) (see Section 2 for the proof of knowledge).

When the proposed key exchange protocol between initiator Alice and responder Bob is executed,

Alice performs the following procedure to establish a session key with party Bob.

1. Select ephemeral secret key [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and compute the ephemeral public key

2. Compute ephemeral public key [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

3. Send ([??], [??], [X.sub.1], [X.sub.2], [X.sub.3]) to Bob.

Upon receiving ([??], [??], [X.sub.1], [X.sub.2], [X.sub.3]), Bob checks that([X.sub.1], [X.sub.2], [X.sub.3]) [member of] [G.sup.3] . If the condition holds, Bob executes the following procedure.

1. Select ephemeral secret key [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

2. Compute ephemeral public key [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

3. Send ([??], [??], [X.sub.1], [X.sub.2], [X.sub.3], [Y.sub.1],[Y.sub.2],[Y.sub.3]) to Alice.

Upon receiving (A, B, [X.sub.1], [X.sub.2], [X.sub.3],[Y.sub.1], [Y.sub.2],[Y.sub.3]), Alice checks if she sent ([??], [??], [X.sub.1], [X.sub.2], [X.sub.3]) to Bob and verifies that (7, [Y.sub.2],[Y.sub.3]) [member of] [G.sup.3].

After the verification step, Alice computes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

and outputs session key [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where s := ([??], [??], [X.sub.1], [X.sub.2], [X.sub.3],[Y.sub.1],[Y.sub.2], [Y.sub.3]), [alpha] := [H.sub.1] (s) and [beta] := [H.sub.2] (s). Here, s is specified as the remaining part of the initiator's session identifier except the role part initiator'. In a similar way, Bob computes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

and outputs session key [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (s).

This construction is a variant of the Okamoto protocol [7], but the proposed protocol does not require the NAXOS trick. Instead, we add ([A.sub.3], [A.sub.4], [B.sub.3], [B.sub.4]) to the static public key and use them in the computation for the session key to satisfy the eCK security model. In [13], the authors add more extra information [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to the static public key. The exchanged messages between the two parties are the same as those above but the computation of the session key is more complicated; that is, Alice computes [K.sub.A] as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This computation ensures that Alice's ephemeral secret key x and static secret key a are used for the independent static secret key of Bob ((B1, B2) and (B3, B4)). Instead, the cost for computing the session key is less efficient than the original Okamoto protocol (see Section 6). In contrast, the proposed protocol in this paper does not require such independence and the computational cost for the session key is equivlent to that in the Okamoto protocol. Nonetheless, we show that the proposed protocol is provably secure in the eCK security model.

[FIGURE 1 OMITTED]

5.2 Security

Theorem 1: Suppose that the DDH assumption holds for [{[G.sub.k]}.sub.k[member of]N], F is the [pi] PRF family with index [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]where [I.sub.G] := {(U,V,d) | (U,V,d ) [member of] [G.sup.2] x [Z.sub.q]} and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and His the CR hash function family. Then the proposed AKE protocol is eCK-secure (in the sense of Definition 2).

It is clear that the first condition of Definition 2 holds since we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

Thus, we will prove that the second condition of Definition 2 holds under the assumptions.

We consider that the adversary chooses the test session between owner Alice and Bob. Without loss of generality, we assume the role of Alice at the test session is the initiator and we use the following notation:

--([a.sup.*.sub.1], [a.sup.*.sub.2], [a.sup.*.sub.3], [a.sup.*.sub.4]): the static secret key of Alice

--[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]: the static puclic key of Alice

--[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]: the static public key of Bob

--(x*, [x.sup.*.sub.3]) : the ephemeral secret key of Alice in the test session

--[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]: the ephemeral public key of Alice in the test session

--([Y.sup.*.sub.1], [Y.sup.*.sub.2], [Y.sup.*.sub.3]): the ephemeral public key Alice received during the session

- SID* := (initiator, [??],[??],[X.sup.*.sub.1],[X.sup.*.sub.1],[X.sup.*.sub.3], [Y.sup.*.sub.1], [Y.sup.*.sub.2], [Y.sup.*.sub.3]): the session identifier in the test session

The session key of test session sid* is computed by

1. Set s* := ([??],[??],[X.sup.*.sub.1],[X.sup.*.sub.1],[X.sup.*.sub.3], [Y.sup.*.sub.1], [Y.sup.*.sub.2], [Y.sup.*.sub.3])

2. Compute [alpha]* := [H.sub.1](s*) and [beta]* := [H.sub.2](s).

3. Compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

4. Compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

To estimate the advantage of the adversary, we consider the following cases in which the adversary can obtain the secret information through oracle queries. Note that these cases are sufficient to prove the eCK security.

When there exists a matching session [bar.SID] of test session SID*,

C1. M issues both EphemeralKeyReveal(SID*) and EphemeralKeyReveal([bar.SID]).

C2. M issues both EphemeralKeyReveal(SID*) and StaticKeyReveal( B).

C3. M issues both StaticKeyReveal(A) and EphemeralKeyReveal(SID).

C4. M issues both StaticKeyReveal(A) and StaticKeyReveal (B).

When there exists no matching session SID of test session SID*,

C5. M issues EphemeralKeyReveal(SID*).

C6. M issues StaticKeyReveal(A).

We provide the two propositions to facilitate the security proof of the proposed protocol.

Proposition 1: If adversary M breaks the security of the proposed protocol in Case C3, then there exists adversary M' who can achive a successful attack in Case C2.

Proof. We briefly sketch the security reduction as follows. M' runs M and responds all the oracle queries except the test session. When M issues the test query to SID*, M' selects the matching session [bar.SID]* as the test session. When M' receives the real session key or random key, M' sends it to M . If M outputs a bit, M' outputs the same bit. Note that M' can issue EphemeralKeyReveal(SID*) since SID* is the matching session to the test session from the view point of M'. So M' can correctly respond to all the queries issued by M . Therefore, if M breaks the security of the proposed protocol in Case C3, M' wins the game with non-negligible probability.

Proposition 2: If an adversary M breaks the security of our protocol in Case C1 (C2), then there exists an adversary M' that can successfully attack in Case C5 (C6).

Proof. This proof is similar to the previous one. When M issues the test query to SID*, M' selects the session in the form of SID' := (initiator, [??], [??], [X.sup.*.sub.1], [X.sup.*.sub.2], [X.sup.*.sub.3]*, Y *) where Y* is generated by M'. When M' receives the real session key or random key, M' sends it to M . If M outputs a bit, M' outputs the same bit. M' can respond to any oracle query issued by M since the restricted oracle queries between M and M' are equivalent. Therefore, M' breaks the security of the proposed protocol in Case C5 (C6) if wins the game in Case C1 (C2).

To complete the proof of Theorem 1, we must provide the security proofs for six cases. However, from Propositions 1 and 2, the security proofs for Cases C1, C2 and C3 can be omitted if we can describe the security proofs for Cases C5 and C6. Furthermore, one can easily obtain the security proof for Case 6 if ([A.sup.*.sub.3], [A.sup.*.sub.4]) in the proof for Case 5 is replaced by (X*, X *) in the proof for Case 6, where ([X.sup.*.sub.1], [X.sup.*.sub.2], [B.sup.*.sub.1], [B.sup.*.sub.2]) corresponds to ([A.sup.*.sub.3], [A.sup.*.sub.4], [B.sup.*.sub.1], [B.sup.*.sub.2]) in our proof technique. The other gap between them is that the proof of knowledge used in the proof for Case 5 is not necessary in Case 6, i.e., a game corresponding to Game 2-3 can be omitted in Case 6. The reduction efficiency for Case 6 is almost equivalent to that for Case 5.

Therefore, we prove the advantage of the adversary is negligible in k even if Cases C4 and C5 occur, respectively.

Case C4:

We proceed in games, starting with Game 1-0 which is the original eCK game between a challenger and adversary [M.sub.1], the challenger simulates all honest parties and the answer of the test query. In each Game i, we define Advi as the advantage in which the adversary wins the game.

Game 1-0. This is the original eCK game with adversary [M.sub.1] in Case C4. Hence we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Game 1-1. The challenger proceeds as Game 1-0 but aborts the game if it does not correctly guess the test session.

Game 1-2. We modify Game 1-1 by changing the value of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to a random element [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Game 1-3. We change Game 1-2 to Game 1-3 by changing PRF F to a random function RF for test query Test(SID*).

We evaluate the relations between the game transformations using the following claims.

Claim 1. We have

[Adv.sub.1-0] [less than or equal to] n[(k).sup.2] [q.sub.a] (k) * [Adv.sub.1-1]. (14)

Proof. Suppose that [M.sub.1] activates at most [q.sub.a](k) sessions for each [n.sub.(k)] party. The challenger uniformly selects the owner of test session A and peer B in n(k) parties, and guesses that [??]'s i-th session will be chosen as the test session in advance. Then the probability that the challenger correctly guesses the test session is at least 1/n[(k).sup.2] [q.sub.a](k) . Therefore, [Adv.sub.1-0] [less than or equal to] n[(k).sup.2] [q.sub.a] (k) * [Adv.sub.1-1].

Claim 2. There exists a probabilistic algorithm S1 such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (15)

Proof. If the adversary distinguishes Game 1-2 from Game 1-1 with non-negligible probability, we can construct an algorithm S1 that solves the DDH problem.

For a given DDH instance [rho]:= (G, u,v, w, z), where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [S.sub.1] sets [g.sub.1] := u and chooses all parameters as Game 1-1 except [X.sup.*.sub.3]* and [Y.sup.*.sub.]. [S.sub.1] sets [X.sup.*.sub.3] := v and [Y.sup.*.sub.3] := w as the ephemeral public key at the test session and the matching session, respectively. If [M.sub.1] issues the test session, the challenger responds with the session key using

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

When [M.sub.1] outputs a guess b', [S.sub.1] outputs 1 iff b' = b holds.

If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the advantage of [S.sub.1] in this simulation is equivalent to that in Game 1-1, since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Otherwise, the advantage of [S.sub.1] is the same as that in Game 1-2 because [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] hold. Therefore, we obtain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Claim 3. There exists a probabilistic algorithm S2 such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (17)

Proof. If the adversary distinguishes Game 1-3 from Game 1-2 with non-negligible probability, we can construct algorithm [S.sub.2] that breaks the PRF function (in this case, [pi] PRF property is not needed).

Given oracle access to F or truly random function RF , S2 selects all parameters as Game 1-2 and proceeds with the game except for the computation of test query Test( SID*). When [M.sub.1] issues a test query to SID*, [S.sub.2] issues SID* to the oracle and responds with the value to the adversary. When [M.sub.1] outputs guess b', [S.sub.2] outputs 1 iff b = b holds.

If the oracle is F , the advantage of [S.sub.2] in this simulation is equivalent to that in Game 1-2 because [K.sup.*.sub.A] is uniformly random and the session key of the test session is indistinguishable from that of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Otherwise, the advantage of S2 is the same as that in Game 1-3 because RF is a random function. Therefore, we obtain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It is obvious that [Adv.sub.1-3] = 0, and we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (18)

Case C5:

Before describing the security proof, we consider sessions between [??] and [[??].sup.(i)] (i = 1,..., [q.sub.a] (k)) and we use the following notations.

--([x.sup.(i),[x.sup.(i).sub.3])): [??]'s ephemeral secret key in the session

--[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]: the ephemeral public key of [??] in the session

--([Z.sup.(i).sub.1], [Z.sup.(i).sub.2]), [Z.sup.(i).sub.3]): the ephemeral public key of [??] received during the session

--([C.sup.(i).sub.1], [C.sup.(i).sub.2]), [C.sup.(i).sub.3], [C.sup.(i).sub.4]): [[??].sup.(i)]'s static public key

--SI[D.sup.(i).sub.A]): A's session identifier in the session

The session key at SI[D.sup.(i).sub.A] is computed by using the variables below:

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [[beta].sup.(i).sub.A] := [H.sub.2] ([s.sup.(i).sub.A]) (if [??] is the initiator).

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [[beta].sup.(i).sub.A] := [H.sub.2] ([s.sup.(i).sub.A]) (if [??] is the responder).

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

These variables are used in the game sequence in Game 2-3.

Similarly, we consider sessions between [??] and [[??].sup.(i)] (i = 1,..., [q.sub.a] (k)) and we use the notations below.

--([y.sup.(i)], [y.sup.(i).sub.3]] : [??]'s ephemeral secret key in the session

--[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]: the ephemeral public key of [??] in the session

--([W.sup.(i).sub.1], [W.sup.(i).sub.2], [W.sup.(i).sub.3]): the ephemeral public key [??] received during the session

--([D.sup.(i).sub.1], [D.sup.(i).sub.2], [D.sup.(i).sub.3], [D.sup.(i).sub.4]: [[??.sup.(i)]'s static public key

--SI[D.sup.(i).sub.B]: [??]'s session identifier in the session

The session key at SI[D.sup.(i).sub.B] is computed using the variables below.

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [[beta].sup.(i).sub.B] := [H.sub.2] ([s.sup.(i).sub.B]) (if [??] is the initiator).

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [[beta].sup.(i).sub.B] := [H.sub.2] ([s.sup.(i).sub.A]) (if [??] is the responder).

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now, we proceed in games with adversary [M.sub.2] as follows.

In each Game i, we define [Adv.sub.i] as the advantage in which the adversary wins the game.

Game 2-0. This is the original eCK game with adversary [M.sub.2] in Case C5. Hence we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Game 2-1. The challenger proceeds as Game 2-0 but aborts the game if it does not correctly guess the test session in Game 2-1.

Game 2-2. We modify Game 2-1 to Game 2-2 by changing the value of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in the computation process of k*a .

Game 2-3. We modify Game 2-2 to Game 2-3 by changing the value of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in the computation process of [K.sup.(i).sub.A], where ([c.sup.(i).sub.1], [c.sup.(i).sub.2][c.sup.(i).sub.3], [c.sup.(i).sub.4]) is the static secret key of ([C.sup.(i).sub.1]), [c.sup.(i).sub.2]).

Game 2-4. We modify Game 2-3 to Game 2-4 by changing DH tuple [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to random tuple [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Game 2-5. We proceed as Game 2-4 but abort the game if [M.sub.2] establishes session SI[D.sup.(i).sub.B] such that [H.sub.1](s*) = [H.sub.1]([s.sup.(i).sub.B]) or [H.sub.2](s*) = [H.sub.2] ([s.sup.(i).sub.B]).

Game 2-5. We modify Game 2-5 to Game 2-6 by changing the [pi] PRF function F to a random function RF for test query Test(SID*).

We evaluate the relations between pairs of advantages.

Claim 4. We have

[Adv.sub.2-0] [less than or equal to] n[(k).sup.2] [q.sub.a] (k) * [Adv.sub.2-1]. (19)

Proof. This transformation is the same as that in Game 1-1 in the security proof for Case C4. Then we have [Adv.sub.2-0] [less than or equal to] n[(k).sup.2] [q.sub.a] (k) * [Adv.sub.2-1].

Claim 5. We have

[Adv.sub.2-1] = [Adv.sub.2-2]. (21)

Proof. It is clear that this change is purely conceptual, hence [Adv.sub.2-1] = [Adv.sub.2-2].

Claim 6. We have

[Adv.sub.2-2] = [Adv.sub.2-3] + [epsilon](k) (21)

where [epsilon](k) is negligible in k.

Proof. When [M.sub.2] establishes party [[??].sup.(i)], [M.sub.2] is required to prove the knowledge of ([c.sup.(i).sub.1], [c.sup.(i).sub.2]), [c.sup.(i).sub.3], [c.sup.(i).sub.4]) in the public key certification process. Due to the conditions of the proof of knowledge (Section (), the simulator (challenger) can obtain ([c.sup.(i).sub.1], [c.sup.(i).sub.2]), [c.sup.(i).sub.3], [c.sup.(i).sub.4]) with overwhelming probability.

Since this change is purely conceptual, we obtain [Adv.sub.2-2] = [Adv.sub.2-3] + [epsilon](k) where [epsilon](k) is negligible in k .

Claim 7. There exists a probabilistic polynomial-time algorithm [S.sub.1] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (22)

Proof. If the adversary distinguishes Game 2-4 from Game 2-3 with non-negligible probability, we can construct algorithm [S.sub.1] that solves the DDH problem.

For a given DDH instance [rho]:= (G, u, v, w, z) , where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] sets [g.sub.1] := u , [g.sub.2] := v and chooses all parameters as Game 2-2 except [A.sup.*.sub.3] and [A.sup.*.sub.4]. [S.sub.1] sets [A.sup.*.sub.3] := w and [A.sup.*.sub.4] := z . [S.sub.1] proceeds with the game and outputs 1 iff [M.sub.2] correctly guesses b'.

If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the advantage of [S.sub.1] in this simulation is equivalent to that in Game 2-3. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the advantage of [S.sub.1] in this simulation is equivalent to that in Game 2-4. Therefore, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Claim 8. There exists probabilistic polynomial-time algorithm [S.sub.2] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (23)

Proof. Here we can assume that the matching session of test session SID* does not exists. Hence we have s* [not equal to] [s.sup.(i).sub.B] for any i. Then, if the collision event does not occur, Game 2-5 is equivalent to Game 2-4. When the event does occur, we can easily construct algorithm [S.sub.2] that breaks the CR hash function by outputting (s*, [s.sup.(i).sub.B]) . Hence we obtain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Claim 9. There exists a probabilistic polynomial-time algorithm [S.sub.3] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (24)

Proof. To prove Claim 9, we consider two cases for each session SI[D.sup.(i).sub.B]).

Case (i). (G, [g.sub.1], [g.sub.2], [W.sup.(i).sub.1] [D.sup.(i).sub.3],[W.sup.(i).sub.2] [D.sup.(i).sub.4] [member of] D(k). That is, there exists [w.sup.(i)] [member of] [Z.sub.q] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Case (ii). (G, [g.sub.1], [g.sub.2], [W.sup.(i).sub.1] [D.sup.(i).sub.3],[W.sup.(i).sub.2] [D.sup.(i).sub.4] [not member of] D(k).

The probability that (G, [g.sub.1], [g.sub.2], [W.sup.(i).sub.1] [D.sup.(i).sub.3],[W.sup.(i).sub.2] [D.sup.(i).sub.4] [not member of] D(k) and [g.sub.1] [not equal to] 1, [g.sub.2] [not equal to] 1, [g.sub.1] [not equal to] [g.sub.2] is at least 1 - 4/q because these are uniformly selected from R(k).

Then, ([B.sup.*.sub.1], [B.sup.*.sub.2], [K.sup.*.sub.A], [K.sup.(i).sub.B]) are denoted by the following equations:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (25)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (26)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (27)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (28)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (25) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (25).

If Case (i) occurs, [K.sup.(i).sub.B] is independent from [K.sup.*.sub.A] for any i = 1,...,[q.sub.a](k) since

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (29)

is linearly dependent on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], while [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is linearly independent from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. On the other hand, if Case (ii) occurs, we can obtain 4 x 4 matrix

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (30)

from Eqs. (17)-(20). This 4 x 4 matrix is regular if

[[eta].sup.2] ([a.sup.*.sub.0] - a*)([w.sup.(i).sub.0] - w.sup.(i))([beta]* - [[beta].sup.(i).sub.B] [equivalent to] 0 (mod q) (31)

does not hold, so [K.sup.*.sub.A] is independent from [K.sup.(i).sub.B] since [a.sup.*.sub.0] [not equal to] a*, [w.sup.*.sub.0] [not equal to] [w.sup.(i)] and [beta]* [not equal to] [[beta].sup.(i).sub.B]) hold with probability at least 1 - 4/q .

Now, we construct algorithm [S.sub.3] that breaks [pi] PRF function F with index [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [I.sub.G] := {(U,V,d) | (U,V,d) [member of] [G.sup.2] x [Z.sub.q]} and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if the adversary distinguishes Games 2-5 and 2-6 with non- negligible probability. [S.sub.3] selects all parameters including [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [g.sub.2] = [g.sup.[eta].sub.1], and sets

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Algorithm [S.sub.3] sets ([r.sub.1],[r.sub.2]):= ([b.sup.*.sub.2], [b.sup.*.sub.4]) , and applies the index, [I.sub.G] := {(U,V,d)|(U,V,d) [member of] [G.sup.2] x [Z.sub.q]} and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i = 1,..., [q.sub.a] (k). Then [S.sub.3] sends (U*, V*, [beta]*) and ([U.sub.i], [V.sub.i], [[beta].sup.(i).sub.B])) (i = 1,..., [q.sub.a] (k)) to the oracle (F,[I.sub.G]) or RF . When [M.sub.2] outputs guess b', [S.sub.3] outputs 1 iff b' = b holds.

If the oracle is (F, [I.sub.G]), the simulated game is equivalent to Game 2-5. If the oracle is RF, the simulated game is equivalent to Game 2-6. Therefore, we obtain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It is clear that [Adv.sub.2-6] = 0, and we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (32)

6. Performance

In Table 1, we compare the efficiency and security of the proposed protocol with several existing eCK-secure AKE protocols, CMQV [5], Sarr et. al. [12], Okamoto [6], and Moriyama-Okamoto [13]. In the table, 'exps.' denotes exponentiations in G, 'SK' denotes secret key, 'PK' denotes public key, and 'ROM' denotes the random oracle model.

In evaluating of the computational complexity, we take into account the standard binary method and simultaneous multiple exponentiation algorithm to compute an exponentiation with multiple bases. An exponentiation with l bases costs about [2.sup.l] multiplications for precomputation and q(2 -1/[2.sup.l]) multiplications on average. When we compute [X.sub.1] := [g.sup.x.sub.1] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], it requires less than two exponentiations. Since they can share base [g.sub.1], k square operations [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are also shared in the standard binary method where k = |x| = |[x.sub.3]|. Therefore, the computational costs for [X.sub.1] and [X.sub.3] are equivalent to that of around 1.3 ([approximately equal to]2k/ 1.5k) exponentiations in G .

Here we ignore the cost for the test of whether or not an element is in G , since an elliptic curve (ECC) implementation for the underlying group is the most efficient in practice and the cofactor in the ECC case is usually very small (or nothing).

7. Conclusion

This paper presented an efficient eCK-secure key exchange protocol without random oracles that does not rely on the NAXOS trick. The proposed protocol is faster than that in [13] and each party can compute the common session key as efficient as that in [6], although the protocol in [6] relies on the NAXOS trick.

Received September 15, 2010; revised November 5, 2010; accepted February 22, 2011; published March 31, 2011

References

[1] Mihir Bellare and Phillip Rogaway, "Entity authentication and key distribution," in Proc. of Advances in Cryptology- CRYPTO, pp.232-249, 1993. Article (CrossRefLink).

[2] Ran Canetti and Hugo Krawczyk, "Analysis of key-exchange protocols and their use for building secure channels," in Proc. of Advances in Cryptology--EUROCRYPTO, pp.453-474, 2001. Article (CrossRefLink).

[3] Mihir Bellare, David. Pointcheval and Phillip Rogaway, "Authenticated key exchange secure against dictionary attacks, " in Proc. of Advances in Cryptology--EUROCRYPTO, pp.139-155, 2000. Article (CrossRefLink)

[4] Brian LaMacchia, Kristin Lauter and Anton. Mityagin, "Stronger security of authenticated key exchange," in Proc. of 1st Int. Conference on Provable Security, pp.1-16, 2007. Article (CrossRefLink).

[5] Berkant Ustaoglu, "Obtaining a secure and efficient key agreement protocol from HMQV and NAXOS," in Designs, Codes and Cryptography, vol. 46, no. 3, pp. 329-342, 2008. Article (CrossRefLink).

[6] Tatsuaki Okamoto, "Authenticated key exchange and key encapsulation without random oracles," in Cryptology ePrintArchive, Report 2007/473, 2007. Article (CrossRefLink).

[7] Jooyoung Lee and Je Hong Park, "Authenticated key exchange secure under the computational Diffie-Hellman assumption," in Cryptology ePrint Archive, Report 2008/344, 2008. Article (CrossRefLink).

[8] Jooyoung Lee and Choon Sik Park, "An efficient authenticated key exchange protocol with a tight security reduction," in Cryptology ePrint Archive, Report 2008/345, 2008. Article (CrossRefLink).

[9] Jiang Wu and Berkant Ustaoglu, "Efficient key exchange with tight security reduction," in Cryptology ePrint Archive, Report 2009/288, 2009. Article (CrossRefLink).

[10] Berkant Ustaoglu, "Comparing Session State Reveal and Ephemeral Key Reveal for Diffie-Hellman protocols," in Proc. of 3r Int. Conference on Provable Security, pp. 183-197, Springer, Heidelberg, 2009. Article (CrossRefLink).

[11] Minkyu Kim, Atsushi Fujioka and Berkant Ustaoglu, "Strongly secure authenticated key exchange without NAXOS approach," in Proc. of International Workshop on Security, pp. 174-191, 2009. Article (CrossRefLink).

[12] Augustin P. Sarr, Philippe Elbaz-Vincent and Jean-Claude Bajard, "A secure and efficient authenticated Diffie-Hellman protocol," in Proc. of EUROPKI 2009, pp. 83-998, 2009. Article (CrossRefLink).

[13] Daisuke Moriyama and Tatsuaki Okamoto, "An eCK-secure authenticated key exchange protocol without random oracles," in Proc. of 3rd Int. Conference on Provable Security, pp.154-167, 2009. Article (CrossRefLink).

[14] Hugo Krawczyk, "HMQV: A high-performance secure Diffie-Hellman protocol," in Proc. of Advances in Cryptology--CRYPTO, pp. 546-566, 2005. Article (CrossRefLink).

[15] Ran Canetti, Oded Goldreich and Shai Halevi, "The random oracle model revisited," in Proc. of the 13th Annual ACM Symposium on the Theory of Computing, pp. 209-218, 1998. Article (CrossRefLink).

DOI: 10.3837/tiis.2011.03.009

Daisuke Moriyama (1) and Tatsuaki Okamoto (2)

(1) Institute of Information Security 2-14-1, Tsuruya-cho, Kanagawa-ku, Yokohama-shi, Kanagawa--JAPAN [e-mail: dgs082101@iisec.ac.jp]

(2) NTT, 3-9-11, Midori-cho, Musashino-shi, Tokyo--JAPAN [e-mail: okamoto.tatsuaki@lab.ntt.co.jp]

* Corresponding author: Tatsuaki Okamoto

A preliminary version of this paper appeared in Provsec 2009, November 11-13, Guangzhou, China. This version provides more efficient protocol than the preliminary version and includes a concrete analysis of efficiency with the previous results. We would like to thank Berkant Ustaoglu for invaluable comments on the preliminary version of this paper.

Daisuke Moriyama was born in 1983. He received the B.E. and M.E. degrees in information technology from Chuo University, in 2006 and 2008, respectively. He is a doctorial candidate at the Graduate School of Information Security, Institute of Information Security. His main research interests include information security and cryptography.

Tatsuaki Okamoto was born in 1952. He received the B.E., M.E., and Dr. E. degrees from the University of Tokyo, Tokyo, Japan, in 1976, 1978, and 1988, respectively. He is a Fellow of NTT, Nippon Telegraph and Telephone Corporation. He is presently engaged in research on cryptography and information security. Dr. Okamoto is a guest professor of Kyoto University. His main research interests include information security and cryptography.

Table 1. Comparison with Existing eCK-secure AKE Protocols [5] [12] [6] Static PK 1 element 1 element 2 elements Static SK 1 element 1 element 4 elements Ephemeral PK 1 element 1 element 3 elements Ephemeral SK 1 element 1 element 2 elements Computational 2.0 exps. 2.0 exps. 3.7 exps. complexity Implementation NAXOS -- NAXOS trick Assumptions GDH GDH DDH, CR, [pi] PRF Random orcle Yes Yes No [13] Proposed Static PK 6 elements 4 elements Static SK 9 elements 5 elements Ephemeral PK 3 elements 3 elements Ephemeral SK 2 elements 2 elements Computational 5.0 exps. 3.7 exps. complexity Implementation -- -- trick Assumptions DDH, CR, DDH, CR, [pi] PRF [pi] PRF Random orcle No No

Printer friendly Cite/link Email Feedback | |

Author: | Moriyama, Daisuke; Okamoto, Tatsuaki |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | Mar 1, 2011 |

Words: | 8476 |

Previous Article: | Hybrid no-reference video quality assessment focusing on codec effects. |

Next Article: | Fast macroblock mode selection algorithm for B frames in multiview video coding. |

Topics: |