# Password-Only Authenticated Three-Party Key Exchange with Provable Security in the Standard Model

Authors: Junghyun Nam; Kim-Kwang Raymond Choo; Junghwan Kim; Hyun-Kyu Kang; Jinsoo Kim; Juryon Paik; Dongho Won
Journal: The Scientific World Journal
 (2014)

---

## Abstract

Protocols for password-only authenticated key exchange (PAKE) in the three-party setting allow two clients registered with the same authentication server to derive a common secret key from their individual password shared with the server. Existing three-party PAKE protocols were proven secure under the assumption of the existence of random oracles or in a model that does not consider insider attacks. Therefore, these protocols may turn out to be insecure when the random oracle is instantiated with a particular hash function or an insider attack is mounted against the partner client. The contribution of this paper is to present the first three-party PAKE protocol whose security is proven without any idealized assumptions in a model that captures insider attacks. The proof model we use is a variant of the indistinguishability-based model of Bellare, Pointcheval, and Rogaway (2000), which is one of the most widely accepted models for security analysis of password-based key exchange protocols. We demonstrated that our protocol achieves not only the typical indistinguishability-based security of session keys but also the password security against undetectable online dictionary attacks.


---

## Body

## 1. Introduction

Authenticated key exchange is one of the most fundamental problems in cryptography and network security. In 1992, Bellovin and Merritt [1] introduced encrypted key exchange (or EKE) protocols, which allowarbitrary two parties, who share only a low-entropy password, to establish a common high-entropy secret key (called a session key) over an insecure public network.Since the work of Bellovin and Merritt [1], password-only authenticated key exchange (PAKE) protocols have attracted much greater attention mainly due to the persistent popularity of passwords as a practical (and cheap) authentication method [2]. Since the publication of the first EKE protocol (with only heuristic security arguments), many provably secure PAKE protocols have been published. Recent examples include the protocol of Katz and Vaikuntanathan [3], which enjoys both round optimality and provable security in the standard model (i.e., without random oracles and ideal ciphers).A major challenge in designing PAKE protocols is to protect passwords from adictionary attack, in which an adversary enumerates all possible passwords while testing each one against known password verifiers in order to determine the correct one. The design of two-party PAKE protocols secure against dictionary attacks has been extensively studied over the past two decades and is now fairly well understood. However, three-party PAKE protocols have received far less attention and preventing dictionary attacks is more challenging in the three-party setting. Unlike the two-party setting that assumes the same password is shared between the two parties, the three-party setting assumes that the two parties (commonly known asclients) wishing to establish a session key do not share the same password but hold their individual password shared only with a trusted server. This implies that in the three-party setting, a malicious client can attempt to mount an insider dictionary attack against its partner client. Indeed, many published three-party PAKE protocols were subsequently found to be vulnerable to an insider online/offline dictionary attack (e.g., [4–10]).It is widely regarded that the design of key exchange protocols (including PAKE protocols) is notoriously hard, and conducting security analysis for such protocols is time-consuming and error-prone [11–13]. The many flaws discovered in published protocols have promoted the use of formal models and rigorous security proofs [14–16]. In the provable security paradigm for protocol analysis, a deductive reasoning process is adopted whereby emphasis is placed on a proven reduction from the problem of breaking the protocol to another problem believed to be computationally hard. A complete mathematical proof with respect to cryptographic definitions provides a strong assurance that a protocol is behaving as desired. It is now standard practice for protocol designers to provide security proofs in a well-defined formal model in order to assure protocol implementers about the security properties of protocols.Over the past decade, we have seen a number of PAKE protocols proposed in the three-party setting [4–8, 17–29]. Many of these published protocols either did not have a proof of security [5, 6, 17, 22–25] or were subsequently found to be flawed [4–10, 12, 23, 24, 27, 30–36]. There are only a handful of provably secure three-party PAKE protocols [4, 7, 8, 21] whose claimed security properties have not been invalidated. However, there are limitations in the security proof of these protocols. For example, the protocols of [7, 8] are proven secure in the random oracle model. Although a proof of security in the random oracle model is definitely better than having no proof, it may not guarantee security in the real world (currently an open question). The protocols of [4, 21] are proven secure in a restricted model where the adversary is not allowed to corrupt protocol participants. Note that a protocol proven secure in such a restricted model cannot guarantee its security against attacks by malicious clients including insider online/offline dictionary attacks. (Readers who are unfamiliar with formal security models are referred to Section 2.1.) Although Yang and Cao [37] proposed a new three-party key exchange protocol that was proven secure in the standard model, the protocol is based on the ElGamal encryption scheme and thus requires a server's public key as well as clients' passwords to be preestablished before the protocol is ever executed. We refer the readers to [33, 38–44] for other recently published protocols designed to work in a “hybrid” setting where a cryptographic key is required in addition to passwords.To the best of our knowledge, there is no published three-party PAKE protocol whose security is proven secure in the standard model that allows an adversary to corrupt protocol participants. In this work, we present the first three-party PAKE protocol that achieves provable security in the standard model against an active adversary with the corruption capability. We prove the security of session keys for our protocol in the widely accepted indistinguishability-based model of Bellare, Pointcheval, and Rogaway [14]—this model is, probably, one of the most popular proof models in the provable security paradigm for key exchange protocols. However, the indistinguishability-based security of session keys proven in the Bellare-Pointcheval-Rogaway model (and several other standard models) does not imply the security of passwords against undetectable online dictionary attacks, in which each guess on the password is checked undetectably via an online transaction with the server (see Section 2.3 for more details). We address this problem by providing a separate proof of security for the protocol against undetectable online dictionary (UDOD) attacks. This second proof is compact and elegant and does not rely upon idealized assumptions about the cryptographic primitives. Table 1 compares our protocol against other provably secure three-party PAKE protocols in terms of security proofs.Table 1
Security proof comparison.
Protocol
Idealized assumption
Adversary capability
Resistance to UDOD attacks†
Our protocol
None
Not restricted
Proven
GPAKE [21]
None
Restricted from corrupting parties
No [4]
NGPAKE [4]
None
Not proven
Lin and Hwang [7]
Random oracles
Not restricted
Not proven
Wu et al. [8]
Random oracles
Not restricted
Not proven
†Resistance to undetectable online dictionary attacks.The remainder of this paper is structured as follows. Section2 describes a formal proof model along with the associated definitions of security. Section 3 presents our proposed three-party PAKE protocol. In Section 4, we prove that the proposed protocol achieves not only the typical indistinguishability-based security of session keys but also the password security against undetectable online dictionary attacks. We conclude the paper in Section 5.


## 2. Formal Setting

In this section, we(1)
first describe a security model adapted from the Bellare-Pointcheval-Rogaway 2000 model [14],
(2)
define a typical indistinguishability-based security of session keys, which we call theSK security,
(3)
provide a simple and intuitive definition of security against undetectable online dictionary attacks.


### 2.1. The Security Model

Protocol Participants. Let 𝒞 be the set of all clients registered with the trusted authentication server S. Clients C
,
C
′
∈
𝒞 who are both registered with S may run a three-party PAKE protocol P at any point in time to establish a session key. Let 𝒰
=
𝒞
∪
{
S
}. A party U
∈
𝒰 may have several instances involved in distinct, possibly concurrent, executions of protocol P. We use Π
U
i to denote the ith instance of party U. A client instance Π
C
i is said toaccept when it successfully computes its session key sk
C
i in a protocol execution.Long-Term Keys. Each client C
∈
𝒞 chooses a password pw
C from a fixed dictionary  PW and shares it with the server S via a secure channel. Accordingly, S holds all the passwords {
pw
C
∣
C
∈
𝒞
}. Each password pw
C is used as the long-term secret key of C and S.Partnership. The notion of partnership is a key element in defining the security of the protocol. Two instances arepartners if both participate in a protocol execution and establish a (shared) session key. We define the partnership relations between instances using the notions of session identifiers and partner identifiers (see [45] on the role and the possible construct of session and partner identifiers as a form of partnering mechanism that enables the right session key to be identified in concurrent protocol executions.). A session identifier (sid) is a unique identifier of a protocol session and is defined as a function of the messages transmitted in the protocol session. We use sid
U
i to denote the sid of instance Π
U
i. A partner identifier (pid) is the set of participants of a specific protocol session. Instances should receive as input a pid before they can run the protocol. By pid
U
i, we denote the pid given to instance Π
U
i. Notice that pid
C
i consists of three participants: server S, client C, and another client C
′ with whom Π
C
i believes it runs the protocol. We say that any two instances Π
C
i and Π
C
′
j arepartners if (1) both Π
C
i and Π
C
′
j have accepted, (2)  s
i
d
C
i
=
s
i
d
C
′
j, and (3)  p
i
d
C
i
=
p
i
d
C
′
j.Adversary. In the model, the probabilistic polynomial-time (ppt) adversary, 𝒜, controls all the communications that take place between parties via a predefined set of oracle queries. For example, the adversary can ask participants to reveal session keys and passwords using Reveal and Corrupt queries as described below.(i)
Execute(Π
C
i
,
Π
C
′
j
,
Π
S
k). This query models passive eavesdropping of a protocol execution. It prompts an honest execution of the protocol between the instances Π
C
i, Π
C
′
j and Π
S
k. The transcript of the protocol execution is returned as the output of the query.
(ii)
Send(Π
U
i
,
m). This query models active attacks against the protocol. It sends message m to instance Π
U
i and returns the message that Π
U
i sends out in response to m. A query of the form Send(Π
C
i, start : (
C
,
C
′
,
S
)) prompts Π
C
i to initiate the protocol with p
i
d
C
i
=
(
C
,
C
′
,
S
).
(iii)
Reveal(Π
C
i). This query returns the session key sk
C
i. This query captures the notion of known key security (and it is often reasonable to assume that the adversary will be able to obtain session keys from any session different from the one under attack). Any client, Π
C
i, upon receiving such a query and if it has accepted and holds some session key, will send this session key back to 𝒜. However, the adversary is not allowed to ask this query if it has already made a Test query to the instance Π
C
i or its partner instance (see below for explanation of the Test oracle).
(iv)
Corrupt(U). This query captures not only the notion of forward secrecy but also unknown key share attacks and insider attacks. The query provides the adversary with U’s password pw
U. Notice that a Corrupt query does not result in the release of the session keys since the adversary already has the ability to obtain session keys through Reveal queries. If U
=
S (i.e., the server is corrupted), all clients’ passwords stored by the server will be returned.
(v)
Test(Π
C
i). This query is the only oracle query that does not correspond to any of the adversary’s abilities. If  Π
C
i has accepted with some session key and is being asked a Test(Π
C
i) query, then depending on a randomly chosen bit b, the adversary is given either the actual session key (when b
=
1) or a session key drawn randomly from the session key distribution (when b
=
0). The adversary can access the Test oracle as many times as necessary. All the queries to the oracle are answered using the same value of the hidden bit b. Namely, the keys returned by the Test oracle are either all real or all random. But, we require that for each different set of partners, the adversary should access the Test oracle only once.We represent the number of queries used by an adversary as an ordered sequence of five nonnegative integers, Q
=
(
q
ex
,
q
se
,
q
re
,
q
co
⁡
,
q
te
), where the five elements refer to the numbers of queries that the adversary made, respectively, to its Execute,  Send,  Reveal,  Corrupt, and  Test oracles. We call this usage of queries by an adversary thequery complexity of the adversary.


### 2.2. Session Key (SK) Security

We now define the basic security, called the SK security, of a 3-party PAKE protocol. As usual, we define the SK security via the notion offreshness. Intuitively, a fresh instance is one that holds a session key which should not be known to the adversary 𝒜, and an unfresh instance is one whose session key (or some information about the key) can be known by trivial means. The formal definition of freshness is explained in Definition 1.Definition 1.
An instanceΠ
C
i is fresh if none of the following occurs: (1) 𝒜 queries  Reveal
(
Π
C
i
) or  Reveal
(
Π
C
′
j
), where Π
C
′
j is the partner of Π
C
i and (2) 𝒜 queries C
o
r
r
u
p
t
(
U
), for some U
∈
p
i
d
C
i, before Π
C
i or its partner Π
C
′
j accepts.The SK security of a 3-party PAKE protocolP is defined in the context of the following two-stage experiment.Stage 1.
𝒜 makes any oracle queries at will except that:(i)
𝒜 is not allowed to ask the Test(Π
C
i) query if the instance Π
C
i is unfresh.
(ii)
𝒜 is not allowed to ask the Reveal(Π
C
i) query if it has already made a Test query to Π
C
i or Π
C
′
j, where Π
C
′
j is the partner of Π
C
i.Stage 2.
Once𝒜 decides that Phase 1 is over, it outputs a bit b
′ as a guess on the hidden bit b chosen by the  Test oracle. 𝒜 is said to succeed if b
=
b
′.
LetSucc be the event that 𝒜 succeeds in this experiment. Then we define the advantage of 𝒜 in breaking the SK security of protocol P as
(1)
A
d
v
P
sk
(
𝒜
)
=
2
·
Pr
[
S
u
c
c
]
-
1
,
A
d
v
P
sk
(
t
,
Q
)
=
max
⁡
𝒜
{
A
d
v
P
sk
(
𝒜
)
}
,
where the maximum is over all  ppt adversaries 𝒜 with time complexity at most t and query complexity at most Q.Definition 2.
A 3-party PAKE protocolP isSK-secure if, for anyppt adversary 𝒜 asking at most q
se  Send queries, A
d
v
P
sk
(
𝒜
) is only negligibly larger than c
·
q
se
/
|
P
W
|, where c is a very small constant (usually around 2 or 4) when compared with |
P
W
|.


### 2.3.  Modelling Undetectable Online Dictionary Attacks

The SK security does not imply security against undetectable online dictionary attacks. In other words, a 3-party PAKE protocol that is not secure against an undetectable online dictionary attack may be rendered SK-secure. To see this, suppose that a 3-party PAKE protocolP is susceptible to undetectable online dictionary attacks whereby an attacker A can find out the password of any registered client B. Then, we can construct an adversary 𝒜 who attacks protocol P with advantage 1 as follows.Corruption. If A is a registered client, 𝒜 queries  Corrupt
(
A
) to obtain the password pw
A. Otherwise, 𝒜 skips this step.Undetectable Online Dictionary Attacks. Next, 𝒜 runs the protocol P in the same way as A conducts its undetectable online dictionary attacks against client B. Note that 𝒜 can perfectly simulate A’s attack by using the disclosed password pw
A and by asking oracle queries appropriately. At the end of this step, 𝒜 will obtain the password pw
B as a result of the attacks.Impersonation.
𝒜 then initiates a new protocol session by querying  Send
(
Π
C
i,  start
:
(
B
,
C
,
S
)
), where Π
C
i is an unused instance of an uncorrupted client C. 𝒜 runs this session as per the protocol specification, but simulating by itself all the actions of B (by using pw
B). At the end of the session, the instance Π
C
i will accept with its session key sk
C
i.Test. The instance Π
C
i is fresh as (1) no  Reveal query has been made on Π
C
i or its partner (which does not exist) and (2) no  Corrupt query has been made against any of B, C, and S. Thus, 𝒜 may ask the  Test(Π
C
i) query. Since 𝒜 can compute the session key sk
C
i by itself, it follows that Pr
P
,
𝒜
[
S
u
c
c
]
=
1 and thus A
d
v
P
sk
(
𝒜
)
=
1.Since verifying the correctness of a password guess may require more than oneSend queries to be asked, 𝒜 may have to ask  Send queries as many times as d
·
|
P
W
|, for some integer d
≥
1, to correctly determine the password pw
A. Then, even if A
d
v
P
sk
(
𝒜
)
=
1, the following holds for some c
≥
1:
(2)
A
d
v
P
sk
(
𝒜
)
≤
c
d
|
P
W
|
|
P
W
|
,
and the protocol P is rendered SK-secure by Definition 2.This result is not surprising since we call a protocol SK-secure if mounting an online dictionary attack by askingSend queries is the best an adversary can do. However, we want to be able to distinguish undetectable online dictionary attacks from detectable online dictionary attacks, and ensure that the best an adversary can do is to mount a detectable online dictionary attack. The following new definitions together provide a simple and intuitive way of capturing security against undetectable online dictionary attacks.Definition 3.
TheSend
(
Π
S
k
,
m
) query models anonline dictionary attack if both the following are true at the time of the termination of instance Π
S
k: (1) m was not output by a previous  Send query asked to an instance of C by which, Π
S
k believes, m was sent and (2) the adversary 𝒜 queried neither  Corrupt
(
S
) nor  Corrupt
(
C
).In Definition3, the first condition implies that a straightforward delivery of a message between instances is not considered as an online dictionary attack while the second condition implies that, when C
′ is the (assumed) peer of client C, the adversary 𝒜 can corrupt the peer client C
′ to mount an (insider) online dictionary attack. Note that our definition of an online dictionary attack does not impose any restriction on asking  Reveal queries.Consider the two-stage experiment described in the previous section. LetUndet be the event that in the experiment, a server instance terminates normally when an online dictionary attack was mounted against the instance. We say that the adversary 𝒜 succeeds in mounting an undetectable online dictionary attack if the event  Undet occurs.Definition 4.
A 3-party PAKE protocolP is secure against an undetectable online dictionary attack if, for anyppt adversary 𝒜 asking at most q
se  Send queries, P
r
P
,
𝒜[Undet] is only negligibly larger than c
·
q
se
/
|
P
W
|, where c is as in Definition 2.


## 2.1. The Security Model

Protocol Participants. Let 𝒞 be the set of all clients registered with the trusted authentication server S. Clients C
,
C
′
∈
𝒞 who are both registered with S may run a three-party PAKE protocol P at any point in time to establish a session key. Let 𝒰
=
𝒞
∪
{
S
}. A party U
∈
𝒰 may have several instances involved in distinct, possibly concurrent, executions of protocol P. We use Π
U
i to denote the ith instance of party U. A client instance Π
C
i is said toaccept when it successfully computes its session key sk
C
i in a protocol execution.Long-Term Keys. Each client C
∈
𝒞 chooses a password pw
C from a fixed dictionary  PW and shares it with the server S via a secure channel. Accordingly, S holds all the passwords {
pw
C
∣
C
∈
𝒞
}. Each password pw
C is used as the long-term secret key of C and S.Partnership. The notion of partnership is a key element in defining the security of the protocol. Two instances arepartners if both participate in a protocol execution and establish a (shared) session key. We define the partnership relations between instances using the notions of session identifiers and partner identifiers (see [45] on the role and the possible construct of session and partner identifiers as a form of partnering mechanism that enables the right session key to be identified in concurrent protocol executions.). A session identifier (sid) is a unique identifier of a protocol session and is defined as a function of the messages transmitted in the protocol session. We use sid
U
i to denote the sid of instance Π
U
i. A partner identifier (pid) is the set of participants of a specific protocol session. Instances should receive as input a pid before they can run the protocol. By pid
U
i, we denote the pid given to instance Π
U
i. Notice that pid
C
i consists of three participants: server S, client C, and another client C
′ with whom Π
C
i believes it runs the protocol. We say that any two instances Π
C
i and Π
C
′
j arepartners if (1) both Π
C
i and Π
C
′
j have accepted, (2)  s
i
d
C
i
=
s
i
d
C
′
j, and (3)  p
i
d
C
i
=
p
i
d
C
′
j.Adversary. In the model, the probabilistic polynomial-time (ppt) adversary, 𝒜, controls all the communications that take place between parties via a predefined set of oracle queries. For example, the adversary can ask participants to reveal session keys and passwords using Reveal and Corrupt queries as described below.(i)
Execute(Π
C
i
,
Π
C
′
j
,
Π
S
k). This query models passive eavesdropping of a protocol execution. It prompts an honest execution of the protocol between the instances Π
C
i, Π
C
′
j and Π
S
k. The transcript of the protocol execution is returned as the output of the query.
(ii)
Send(Π
U
i
,
m). This query models active attacks against the protocol. It sends message m to instance Π
U
i and returns the message that Π
U
i sends out in response to m. A query of the form Send(Π
C
i, start : (
C
,
C
′
,
S
)) prompts Π
C
i to initiate the protocol with p
i
d
C
i
=
(
C
,
C
′
,
S
).
(iii)
Reveal(Π
C
i). This query returns the session key sk
C
i. This query captures the notion of known key security (and it is often reasonable to assume that the adversary will be able to obtain session keys from any session different from the one under attack). Any client, Π
C
i, upon receiving such a query and if it has accepted and holds some session key, will send this session key back to 𝒜. However, the adversary is not allowed to ask this query if it has already made a Test query to the instance Π
C
i or its partner instance (see below for explanation of the Test oracle).
(iv)
Corrupt(U). This query captures not only the notion of forward secrecy but also unknown key share attacks and insider attacks. The query provides the adversary with U’s password pw
U. Notice that a Corrupt query does not result in the release of the session keys since the adversary already has the ability to obtain session keys through Reveal queries. If U
=
S (i.e., the server is corrupted), all clients’ passwords stored by the server will be returned.
(v)
Test(Π
C
i). This query is the only oracle query that does not correspond to any of the adversary’s abilities. If  Π
C
i has accepted with some session key and is being asked a Test(Π
C
i) query, then depending on a randomly chosen bit b, the adversary is given either the actual session key (when b
=
1) or a session key drawn randomly from the session key distribution (when b
=
0). The adversary can access the Test oracle as many times as necessary. All the queries to the oracle are answered using the same value of the hidden bit b. Namely, the keys returned by the Test oracle are either all real or all random. But, we require that for each different set of partners, the adversary should access the Test oracle only once.We represent the number of queries used by an adversary as an ordered sequence of five nonnegative integers, Q
=
(
q
ex
,
q
se
,
q
re
,
q
co
⁡
,
q
te
), where the five elements refer to the numbers of queries that the adversary made, respectively, to its Execute,  Send,  Reveal,  Corrupt, and  Test oracles. We call this usage of queries by an adversary thequery complexity of the adversary.


## 2.2. Session Key (SK) Security

We now define the basic security, called the SK security, of a 3-party PAKE protocol. As usual, we define the SK security via the notion offreshness. Intuitively, a fresh instance is one that holds a session key which should not be known to the adversary 𝒜, and an unfresh instance is one whose session key (or some information about the key) can be known by trivial means. The formal definition of freshness is explained in Definition 1.Definition 1.
An instanceΠ
C
i is fresh if none of the following occurs: (1) 𝒜 queries  Reveal
(
Π
C
i
) or  Reveal
(
Π
C
′
j
), where Π
C
′
j is the partner of Π
C
i and (2) 𝒜 queries C
o
r
r
u
p
t
(
U
), for some U
∈
p
i
d
C
i, before Π
C
i or its partner Π
C
′
j accepts.The SK security of a 3-party PAKE protocolP is defined in the context of the following two-stage experiment.Stage 1.
𝒜 makes any oracle queries at will except that:(i)
𝒜 is not allowed to ask the Test(Π
C
i) query if the instance Π
C
i is unfresh.
(ii)
𝒜 is not allowed to ask the Reveal(Π
C
i) query if it has already made a Test query to Π
C
i or Π
C
′
j, where Π
C
′
j is the partner of Π
C
i.Stage 2.
Once𝒜 decides that Phase 1 is over, it outputs a bit b
′ as a guess on the hidden bit b chosen by the  Test oracle. 𝒜 is said to succeed if b
=
b
′.
LetSucc be the event that 𝒜 succeeds in this experiment. Then we define the advantage of 𝒜 in breaking the SK security of protocol P as
(1)
A
d
v
P
sk
(
𝒜
)
=
2
·
Pr
[
S
u
c
c
]
-
1
,
A
d
v
P
sk
(
t
,
Q
)
=
max
⁡
𝒜
{
A
d
v
P
sk
(
𝒜
)
}
,
where the maximum is over all  ppt adversaries 𝒜 with time complexity at most t and query complexity at most Q.Definition 2.
A 3-party PAKE protocolP isSK-secure if, for anyppt adversary 𝒜 asking at most q
se  Send queries, A
d
v
P
sk
(
𝒜
) is only negligibly larger than c
·
q
se
/
|
P
W
|, where c is a very small constant (usually around 2 or 4) when compared with |
P
W
|.


## 2.3.  Modelling Undetectable Online Dictionary Attacks

The SK security does not imply security against undetectable online dictionary attacks. In other words, a 3-party PAKE protocol that is not secure against an undetectable online dictionary attack may be rendered SK-secure. To see this, suppose that a 3-party PAKE protocolP is susceptible to undetectable online dictionary attacks whereby an attacker A can find out the password of any registered client B. Then, we can construct an adversary 𝒜 who attacks protocol P with advantage 1 as follows.Corruption. If A is a registered client, 𝒜 queries  Corrupt
(
A
) to obtain the password pw
A. Otherwise, 𝒜 skips this step.Undetectable Online Dictionary Attacks. Next, 𝒜 runs the protocol P in the same way as A conducts its undetectable online dictionary attacks against client B. Note that 𝒜 can perfectly simulate A’s attack by using the disclosed password pw
A and by asking oracle queries appropriately. At the end of this step, 𝒜 will obtain the password pw
B as a result of the attacks.Impersonation.
𝒜 then initiates a new protocol session by querying  Send
(
Π
C
i,  start
:
(
B
,
C
,
S
)
), where Π
C
i is an unused instance of an uncorrupted client C. 𝒜 runs this session as per the protocol specification, but simulating by itself all the actions of B (by using pw
B). At the end of the session, the instance Π
C
i will accept with its session key sk
C
i.Test. The instance Π
C
i is fresh as (1) no  Reveal query has been made on Π
C
i or its partner (which does not exist) and (2) no  Corrupt query has been made against any of B, C, and S. Thus, 𝒜 may ask the  Test(Π
C
i) query. Since 𝒜 can compute the session key sk
C
i by itself, it follows that Pr
P
,
𝒜
[
S
u
c
c
]
=
1 and thus A
d
v
P
sk
(
𝒜
)
=
1.Since verifying the correctness of a password guess may require more than oneSend queries to be asked, 𝒜 may have to ask  Send queries as many times as d
·
|
P
W
|, for some integer d
≥
1, to correctly determine the password pw
A. Then, even if A
d
v
P
sk
(
𝒜
)
=
1, the following holds for some c
≥
1:
(2)
A
d
v
P
sk
(
𝒜
)
≤
c
d
|
P
W
|
|
P
W
|
,
and the protocol P is rendered SK-secure by Definition 2.This result is not surprising since we call a protocol SK-secure if mounting an online dictionary attack by askingSend queries is the best an adversary can do. However, we want to be able to distinguish undetectable online dictionary attacks from detectable online dictionary attacks, and ensure that the best an adversary can do is to mount a detectable online dictionary attack. The following new definitions together provide a simple and intuitive way of capturing security against undetectable online dictionary attacks.Definition 3.
TheSend
(
Π
S
k
,
m
) query models anonline dictionary attack if both the following are true at the time of the termination of instance Π
S
k: (1) m was not output by a previous  Send query asked to an instance of C by which, Π
S
k believes, m was sent and (2) the adversary 𝒜 queried neither  Corrupt
(
S
) nor  Corrupt
(
C
).In Definition3, the first condition implies that a straightforward delivery of a message between instances is not considered as an online dictionary attack while the second condition implies that, when C
′ is the (assumed) peer of client C, the adversary 𝒜 can corrupt the peer client C
′ to mount an (insider) online dictionary attack. Note that our definition of an online dictionary attack does not impose any restriction on asking  Reveal queries.Consider the two-stage experiment described in the previous section. LetUndet be the event that in the experiment, a server instance terminates normally when an online dictionary attack was mounted against the instance. We say that the adversary 𝒜 succeeds in mounting an undetectable online dictionary attack if the event  Undet occurs.Definition 4.
A 3-party PAKE protocolP is secure against an undetectable online dictionary attack if, for anyppt adversary 𝒜 asking at most q
se  Send queries, P
r
P
,
𝒜[Undet] is only negligibly larger than c
·
q
se
/
|
P
W
|, where c is as in Definition 2.


## 3. Our Proposed Protocol

As we have earlier claimed, our proposed protocol presented in this section is the first three-party PAKE protocol proven secure in the standard model against an active adversary who has the corruption ability.


### 3.1. Preliminaries

We begin by reviewing some cryptographic primitives which underlie the security of our protocol.Decisional Diffie-Hellman (DDH) Assumption. Let 𝔾 be a cyclic (multiplicative) group of prime order q. Since the order of 𝔾 is prime, all the elements of 𝔾, except 1, are generators of 𝔾. Let g be a random fixed generator of 𝔾 and let x
,
y
,
z be randomly chosen elements in ℤ
q where z
≠
x
y. Informally stated, the DDH problem for 𝔾 is to distinguish between the distributions of (
g
x
,
g
y
,
g
x
y
) and (
g
x
,
g
y
,
g
z
), and the DDH assumption is said to hold in 𝔾 if it is computationally infeasible to solve the DDH problem for 𝔾. More formally, we define the advantage of 𝒟 in solving the DDH problem for 𝔾 as A
d
v
𝔾
ddh
(
𝒟
)
=
|
Pr
[
𝒟
(
𝔾
,
g
,
g
x
,
g
y
,
g
x
y
)
=
1
]
-
Pr
[
𝒟
(
𝔾
,
g
,
g
x
,
g
y
,
g
z
)
=
1
]
|. We say that the DDH assumption holds in 𝔾 if A
d
v
𝔾
ddh
(
𝒟
) is negligible for allppt algorithms 𝒟. We denote by A
d
v
𝔾
ddh
(
t
) the maximum value of A
d
v
𝔾
ddh
(
𝒟
) over all algorithms 𝒟 running in time at most t.Message Authentication Codes. Let Σ
=
(
G
e
n
,
M
a
c
,
V
e
r
) be a message authentication code (MAC) scheme. The key generation algorithm  Gen takes as input a security parameter 1
ℓ and outputs a key k chosen uniformly at random from {
0,1
}
ℓ. The MAC generation algorithm  Mac takes as input a key k and a message m and outputs a MAC (also known as a tag) σ. The MAC verification algorithm  Ver takes as input a key k, a message m, and a MAC σ and outputs 1 if σ is valid for m under k or outputs 0 if σ is invalid. Let A
d
v
Σ
euf-cma
(
𝒜
) be the probability that an adversary 𝒜 succeeds in breaking the existential unforgeability of Σ under adaptive chosen message attacks. We say that the MAC scheme Σ is secure if A
d
v
Σ
euf-cma
(
𝒜
) is negligible for every ppt adversary 𝒜. We use A
d
v
Σ
euf-cma
(
t
,
q
mac
,
q
ver
) to denote the maximum value of A
d
v
Σ
euf-cma
(
𝒜
) over all ppt adversaries 𝒜 running in time at most t and asking at most q
mac and q
ver queries to its MAC generation and verification oracles, respectively.Two-Party PAKE Protocols. Let  2PAKE be a two-party PAKE protocol that outputs session keys distributed in {
0,1
}
ℓ. We assume that  2PAKE is SK-secure against an adversary who is given access to all the oracles:  Send,  Execute,   Reveal,  Corrupt, and  Test. Let  A
d
v
2PAKE
sk
(
𝒜
) be the advantage of an adversary 𝒜 in breaking the SK security of  2PAKE. We require that, for all pptadversaries 𝒜 making at most q
se  Send queries,  A
d
v
2PAKE
sk
(
𝒜
) is only negligibly larger than q
se
/
|
PW
|. We denote by ADV
2PAKE
sk
(
t
,
Q
) the maximum value of Adv
2PAKE
sk
(
𝒜
) over all ppt adversaries 𝒜 with time complexity at most t and query complexity at most Q.


### 3.2. Protocol Description

LetA and B be two clients who wish to establish a session key, and let S be a trusted server with which A and B have secretly shared their respective passwords pw
A and pw
B. Our protocol proceeds as follows.Step 1.
A and S establish a shared secret key k
A
S by running the two-party protocol  2PAKE. Likewise, B and S establish a shared secret key k
B
S.Step 2.
A (resp., B and S) selects a nonce n
A (resp., n
B and n
S) at random from ℤ
q and sends A
∥
n
A (resp., B
∥
n
B and S
∥
n
S) to the other two parties. All the parties (A, B, and S) define their session identifiers as  sid
A
=
sid
B
=
sid
S
=
A
∥
n
A
∥
B
∥
n
B
∥
S
∥
n
S.Step 3.
A chooses a random x
∈
ℤ
q, computes X
=
g
x and  σ
A
S
=
Mac
k
A
S
(
A
∥
X
∥
sid
A
), and sends A
∥
X
∥
σ
A
S to S. Meanwhile, B chooses a random y
∈
ℤ
q, computes Y
=
g
y and  σ
B
S
=
Mac
k
B
S
(
B
∥
Y
∥
sid
B
), and sends B
∥
Y
∥
σ
B
S to S.Step 4.
S checks that  Ver
k
A
S
(
A
∥
X
∥
sid
S
,
σ
A
S
)
=
1 and  Ver
k
B
S
(
B
∥
Y
∥
sid
S
,
σ
B
S
)
=
1. If either of these is untrue, S aborts the protocol. Otherwise, S computes  σ
S
A
=
Mac
k
A
S
(
S
∥
Y
∥
sid
S
) and  σ
S
B
=
Mac
k
B
S
(
S
∥
X
∥
sid
S
) and sends S
∥
Y
∥
σ
S
A and S
∥
X
∥
σ
S
B to A and B, respectively.Step 5.
A computes the session key sk
=
Y
x if  Ver
k
A
S
(
S
∥
Y
∥
sid
A
,
σ
S
A
)
=
1, while B computes the session key sk
=
X
y if  Ver
k
B
S
(
S
∥
X
∥
sid
B
,
σ
S
B
)
=
1. A and B abort the protocol if their verification fails.The operation of this protocol is illustrated in Figure1. Steps 1 and 2 of the protocol are independent and can be performed in parallel. The session-key computation in the protocol is the same as in the Diffie-Hellman key exchange protocol (i.e., sk
=
g
x
y). Hence, it is straightforward to verify the correctness of the protocol.Figure 1
The proposed three-party PAKE protocol.


## 3.1. Preliminaries

We begin by reviewing some cryptographic primitives which underlie the security of our protocol.Decisional Diffie-Hellman (DDH) Assumption. Let 𝔾 be a cyclic (multiplicative) group of prime order q. Since the order of 𝔾 is prime, all the elements of 𝔾, except 1, are generators of 𝔾. Let g be a random fixed generator of 𝔾 and let x
,
y
,
z be randomly chosen elements in ℤ
q where z
≠
x
y. Informally stated, the DDH problem for 𝔾 is to distinguish between the distributions of (
g
x
,
g
y
,
g
x
y
) and (
g
x
,
g
y
,
g
z
), and the DDH assumption is said to hold in 𝔾 if it is computationally infeasible to solve the DDH problem for 𝔾. More formally, we define the advantage of 𝒟 in solving the DDH problem for 𝔾 as A
d
v
𝔾
ddh
(
𝒟
)
=
|
Pr
[
𝒟
(
𝔾
,
g
,
g
x
,
g
y
,
g
x
y
)
=
1
]
-
Pr
[
𝒟
(
𝔾
,
g
,
g
x
,
g
y
,
g
z
)
=
1
]
|. We say that the DDH assumption holds in 𝔾 if A
d
v
𝔾
ddh
(
𝒟
) is negligible for allppt algorithms 𝒟. We denote by A
d
v
𝔾
ddh
(
t
) the maximum value of A
d
v
𝔾
ddh
(
𝒟
) over all algorithms 𝒟 running in time at most t.Message Authentication Codes. Let Σ
=
(
G
e
n
,
M
a
c
,
V
e
r
) be a message authentication code (MAC) scheme. The key generation algorithm  Gen takes as input a security parameter 1
ℓ and outputs a key k chosen uniformly at random from {
0,1
}
ℓ. The MAC generation algorithm  Mac takes as input a key k and a message m and outputs a MAC (also known as a tag) σ. The MAC verification algorithm  Ver takes as input a key k, a message m, and a MAC σ and outputs 1 if σ is valid for m under k or outputs 0 if σ is invalid. Let A
d
v
Σ
euf-cma
(
𝒜
) be the probability that an adversary 𝒜 succeeds in breaking the existential unforgeability of Σ under adaptive chosen message attacks. We say that the MAC scheme Σ is secure if A
d
v
Σ
euf-cma
(
𝒜
) is negligible for every ppt adversary 𝒜. We use A
d
v
Σ
euf-cma
(
t
,
q
mac
,
q
ver
) to denote the maximum value of A
d
v
Σ
euf-cma
(
𝒜
) over all ppt adversaries 𝒜 running in time at most t and asking at most q
mac and q
ver queries to its MAC generation and verification oracles, respectively.Two-Party PAKE Protocols. Let  2PAKE be a two-party PAKE protocol that outputs session keys distributed in {
0,1
}
ℓ. We assume that  2PAKE is SK-secure against an adversary who is given access to all the oracles:  Send,  Execute,   Reveal,  Corrupt, and  Test. Let  A
d
v
2PAKE
sk
(
𝒜
) be the advantage of an adversary 𝒜 in breaking the SK security of  2PAKE. We require that, for all pptadversaries 𝒜 making at most q
se  Send queries,  A
d
v
2PAKE
sk
(
𝒜
) is only negligibly larger than q
se
/
|
PW
|. We denote by ADV
2PAKE
sk
(
t
,
Q
) the maximum value of Adv
2PAKE
sk
(
𝒜
) over all ppt adversaries 𝒜 with time complexity at most t and query complexity at most Q.


## 3.2. Protocol Description

LetA and B be two clients who wish to establish a session key, and let S be a trusted server with which A and B have secretly shared their respective passwords pw
A and pw
B. Our protocol proceeds as follows.Step 1.
A and S establish a shared secret key k
A
S by running the two-party protocol  2PAKE. Likewise, B and S establish a shared secret key k
B
S.Step 2.
A (resp., B and S) selects a nonce n
A (resp., n
B and n
S) at random from ℤ
q and sends A
∥
n
A (resp., B
∥
n
B and S
∥
n
S) to the other two parties. All the parties (A, B, and S) define their session identifiers as  sid
A
=
sid
B
=
sid
S
=
A
∥
n
A
∥
B
∥
n
B
∥
S
∥
n
S.Step 3.
A chooses a random x
∈
ℤ
q, computes X
=
g
x and  σ
A
S
=
Mac
k
A
S
(
A
∥
X
∥
sid
A
), and sends A
∥
X
∥
σ
A
S to S. Meanwhile, B chooses a random y
∈
ℤ
q, computes Y
=
g
y and  σ
B
S
=
Mac
k
B
S
(
B
∥
Y
∥
sid
B
), and sends B
∥
Y
∥
σ
B
S to S.Step 4.
S checks that  Ver
k
A
S
(
A
∥
X
∥
sid
S
,
σ
A
S
)
=
1 and  Ver
k
B
S
(
B
∥
Y
∥
sid
S
,
σ
B
S
)
=
1. If either of these is untrue, S aborts the protocol. Otherwise, S computes  σ
S
A
=
Mac
k
A
S
(
S
∥
Y
∥
sid
S
) and  σ
S
B
=
Mac
k
B
S
(
S
∥
X
∥
sid
S
) and sends S
∥
Y
∥
σ
S
A and S
∥
X
∥
σ
S
B to A and B, respectively.Step 5.
A computes the session key sk
=
Y
x if  Ver
k
A
S
(
S
∥
Y
∥
sid
A
,
σ
S
A
)
=
1, while B computes the session key sk
=
X
y if  Ver
k
B
S
(
S
∥
X
∥
sid
B
,
σ
S
B
)
=
1. A and B abort the protocol if their verification fails.The operation of this protocol is illustrated in Figure1. Steps 1 and 2 of the protocol are independent and can be performed in parallel. The session-key computation in the protocol is the same as in the Diffie-Hellman key exchange protocol (i.e., sk
=
g
x
y). Hence, it is straightforward to verify the correctness of the protocol.Figure 1
The proposed three-party PAKE protocol.


## 4. Security Proofs

In this section we prove that our three-party PAKE protocol is SK-secure and is resistant to undetectable online dictionary attacks. The proofs of both properties rely on neither random oracles nor ideal ciphers. Therefore, if2PAKE is instantiated with a protocol proven secure in the standard model (e.g., [3, 49]), our three-party PAKE protocol would also be provably secure in the standard model. Hereafter, we denote our protocol by  3PAKEsm (“sm” for “standard model”).


### 4.1. Proof of SK Security

We first claim that, if the underlying two-party protocol2PAKE is SK-secure, then the  3PAKEsm protocol is SK-secure as well under the DDH assumption in 𝔾 and the security of the MAC scheme Σ.Theorem 5.
LetQ
=
(
q
ex
,
q
se
,
q
re
,
q
co
⁡
,
q
te
). For any adversary with query complexity at most Q and time complexity at most t, its advantage in attacking protocol  3PAKEsm is bounded by
(3)
A
d
v
3
P
A
K
E
s
m
s
k
(
t
,
Q
)
≤
2
·
A
d
v
2
P
A
K
E
s
k
(
t
′
,
Q
′
)
+
(
q
se
+
q
ex
)
2
|
𝔾
|
+
2
·
q
se
·
A
d
v
Σ
e
u
f
-
c
m
a
(
t
′
,
4,4
)
+
4
·
A
d
v
𝔾
d
d
h
(
t
′
)
,
where Q
′
=
(
2
q
ex
,
q
se
,
0
,
q
co
⁡
,
2
q
ex
+
q
se
) and t
′ is the maximum time required to perform an entire experiment involving an adversary who attacks protocol 3PAKEsm with time complexity t.Proof.
Assume an adversary𝒜 attacking protocol  3PAKEsm with time complexity t and query complexity Q
=
(
q
ex
,
q
se
,
q
re
,
q
co
⁡
,
q
te
). We prove Theorem 5 by introducing a sequence of experiments E
x
p
r
0
,
…
,
E
x
p
r
5 and bounding the difference in 𝒜's advantage between two consecutive experiments. E
x
p
r
0 is the original experiment (described in Section 2.2) in which 𝒜 attacks the actual protocol, and E
x
p
r
5 is the experiment in which the advantage of 𝒜 is 0. Let  Succ
i be the event that 𝒜 correctly guesses the hidden bit b (chosen by the Test oracle) in experiment E
x
p
r
i. By definition, we get  Adv
3
PAKEsm
sk
(
𝒜
)
=
2
·
Pr
[
Succ
0
]
-
1.
Before providing details of the proof, we first define the notion of anuncorrupted instance.Definition 6.
We say an instanceΠ
U
i is clean if no one in  pid
U
i has been asked a  Corrupt query. Otherwise, we say it is unclean.Experiment
E
x
p
r
1. We modify the experiment so that each different MAC key is chosen uniformly at random from {
0,1
}
ℓ for all clean instances. The difference in 𝒜's success probability between E
x
p
r
0 and E
x
p
r
1 is bounded byClaim 1.
(4)
|
Pr
[
S
u
c
c
1
]
-
Pr
[
S
u
c
c
0
]
|
≤
A
d
v
2
P
A
K
E
sk
(
t
′
,
Q
′
)
.Proof.
Assume that the advantage of𝒜 in attacking protocol  3PAKEsm is different between two experiments E
x
p
r
0 and E
x
p
r
1. Then we prove the claim by constructing, from 𝒜, an adversary  𝒜
2PAKE attacking protocol  2PAKE with time complexity t
′ and query complexity Q
′.
𝒜
2PAKE begins by choosing a bit b uniformly at random.  𝒜
2PAKE then invokes 𝒜 as a subroutine and answers the oracle queries of 𝒜 on its own as follows.
Execute
Queries.  𝒜
2PAKE answers  Execute queries of 𝒜 by making  Execute and  Test queries to its own oracles. Specifically,  𝒜
2PAKE handles each  Execute(Π
A
i, Π
B
j, Π
S
k) query as follows.(i)
If anyone in{
A
,
B
,
S
} has been corrupted, then  𝒜
2PAKE answers the  Execute query as in experiment E
x
p
r
0.
(ii)
Otherwise,𝒜
2PAKE first makes two queries  Execute(Π
A
i
,
Π
S
k) and  Execute(Π
B
j
,
Π
S
k
′). Let  T2PAKE and  T
2
PAKE
′ be two transcripts returned in response to the  Execute queries. Next,  𝒜
2PAKE makes the queries  Test(Π
A
i) and  Test(Π
B
j) and receives in return two keys k
¯
A
S and k
¯
B
S (either real or random).  𝒜
2PAKE then generates the messages of Steps 2–4 of protocol  3PAKEsm, using k
¯
A
S and k
¯
B
S as the MAC keys. Finally,  𝒜
2PAKE returns these messages prepended by  T2PAKE and  T
2
PAKE
′.
Send
Queries. At a high level, the simulation of the  Send oracle is similar to that of the  Execute oracle. Specifically,  𝒜
2PAKE handles each  Send(Π
U
i, m) query as follows. (i)
If the instanceΠ
U
i is clean or the message m belongs to Step 2 or later steps, then  𝒜
2PAKE answers the query as in experiment E
x
p
r
0.
(ii)
Otherwise,𝒜
2PAKE answers it by making the same query to its own  Send oracle. If the query causes Π
U
i to accept, then  𝒜
2PAKE also makes a  Test(Π
U
i) query (if it had not previously asked a  Test query to the partner of Π
U
i). As in the simulation of the  Execute oracle,  𝒜
2PAKE uses the output of this  Test query as the MAC key in generating the messages of Steps 2–4 of protocol  3PAKEsm.
Reveal
Queries. These queries are answered in the obvious way. Namely,  𝒜
2PAKE responds to the query  Reveal(Π
C
i) by returning the session key sk
C
i.
Corrupt
Queries. When 𝒜 queries  Corrupt(U),  𝒜
2PAKE makes the same query to its own  Corrupt oracle and simply forwards the output to 𝒜.
Test
Queries.  𝒜
2PAKE answers these queries according to the bit b chosen at the beginning of the simulation. That is,  𝒜
2PAKE returns real session keys, which it has computed on its own, if b
=
1, and otherwise returns random keys chosen uniformly at random from 𝔾.
Now at some point in time, when𝒜 terminates and outputs its guess b
′,  𝒜
2PAKE outputs 1 if b
=
b
′ and outputs 0 otherwise.
From the simulation above, it is easy to see that𝒜
2PAKE has at most time complexity t
′ and query complexity Q
′. The advantage of  𝒜
2PAKE in attacking protocol  2PAKE is immediate if we notice the following. (i)
The probability that𝒜
2PAKE outputs 1 when its  Test oracle returns real session keys is equal to Pr
[
Succ
0
], the probability that 𝒜 correctly guesses the bit b in experiment E
x
p
r
0.
(ii)
The probability that𝒜
2PAKE outputs 1 when its  Test oracle returns random keys is equal to Pr
[
Succ
1
], the probability that 𝒜 correctly guesses the bit b in experiment E
x
p
r
1. This means that  Adv
2
PAKE
sk
(
𝒜
2PAKE
) =|
Pr
[
Succ
1
]
-
Pr
[
Succ
0
]
|. Claim 1 then follows.Experiment
E
x
p
r
2
. Let  Repeat be the event that a nonce selected by an instance of a party is selected again by another instance of the same party. The experiment E
x
p
r
2 is aborted, and the adversary does not succeed, if the event  Repeat occurs. This is the only difference between E
x
p
r
1 and E
x
p
r
2. By a straightforward calculation, we get the following.Claim 2.
(5)
|
Pr
[
S
u
c
c
2
]
-
Pr
[
S
u
c
c
1
]
|
≤
(
q
se
+
q
ex
)
2
2
|
𝔾
|
.Experiment
E
x
p
r
3. Let  Forge be the event that the adversary 𝒜 makes a  Send query of the form  Send(Π
U
i, V
∥
*
∥
σ) before querying  Corrupt
(
W
), for some  W
∈
pid
U
i, such that (1) σ is a valid tag on V
∥
*
∥
sid
U
i and (2) no oracle had not previously generated a tag on V
∥
*
∥
sid
U
i. If Forge occurs, this experiment is aborted and the adversary does not succeed. Then we have the following.Claim 3.
(6)
|
Pr
[
S
u
c
c
3
]
-
Pr
[
S
u
c
c
2
]
|
≤
q
se
·
A
d
v
Σ
euf-cma
(
t
′
,
4,4
)
.Proof.
Assuming that the eventForge occurs, we construct, from 𝒜, an algorithm ℱ who outputs, with a nonnegligible probability, a forgery against the MAC scheme Σ. The algorithm ℱ is given oracle access to  Mac
k
(
·
) and  Ver
k
(
·
). The goal of ℱ is to produce a message/tag pair (
m
,
σ
) such that (1) σ is a valid tag on the message m (i.e.,  Ver
k
(
m
,
σ
)
=
1
) and (2) ℱ had not previously queried its oracle  Mac
k
(
·
) on the message m.
Letn be the number of all active sessions that 𝒜 initiates by asking a  Send query. First, ℱ chooses a random α
∈
{
1
,
…
,
n
}. ℱ then simulates the oracle calls of 𝒜 as in experiment E
x
p
r
2; except that in the αth session, it answers  Send queries by accessing its MAC generation and verification oracles. If  Forge occurs in the αth session, ℱ halts and outputs the message/tag pair generated by 𝒜 as its forgery. Otherwise, ℱ halts and outputs a failure indication. This simulation is perfect unless the adversary 𝒜 makes a  Corrupt query against a participant of the αth session. But note that the event of 𝒜 making such a  Corrupt query should not happen if  Forge occurs in the αth session.
From the simulation, it is immediate thatA
d
v
Σ
euf-cma
(
ℱ
)
=
Pr
⁡
[
F
o
r
g
e
]
/
n. Since n
≤
q
se, we get   Pr[
F
o
r
g
e
]
≤
q
se
·
A
d
v
Σ
euf-cma
(
ℱ
). Then, Claim 3 follows by noticing that ℱ has at most time complexity t
′ and makes at most 4 queries to   M
a
c
k
(
·
) and   V
e
r
k
(
·
).Experiment
E
x
p
r
4. This experiment is different from E
x
p
r
3 in that the session key sk of each pair of instances partnered via an  Execute query is chosen uniformly at random from 𝔾 instead of being computed as sk
=
g
x
y
=
X
y
=
Y
x. As the following claim states, the difference in 𝒜’s advantage between E
x
p
r
3 and E
x
p
r
4 is negligible if the DDH assumption holds in 𝔾.Claim 4.
(7)
|
Pr
[
S
u
c
c
4
]
-
Pr
[
S
u
c
c
3
]
|
≤
A
d
v
𝔾
ddh
(
t
′
)
.Proof.
Assume that the advantage of𝒜 is nonnegligibly different between E
x
p
r
3 and E
x
p
r
4. We prove the claim by constructing, from 𝒜, a distinguisher 𝒟 that solves the DDH problem in 𝔾. Let (
g
1
,
g
2
,
g
3
)
∈
𝔾
3 be an instance of the DDH problem given as input to 𝒟. 𝒟 begins by choosing a bit b uniformly at random. 𝒟 then invokes 𝒜 as a subroutine and proceeds to simulate the oracles. 𝒟 answers all the oracle queries of 𝒜 as in experiment E
x
p
r
3, except that it handles each  Execute(Π
A
i
,
Π
B
j, Π
S
k) query by (1)
selecting two randoma
i
,
b
i
∈
ℤ
q,
(2)
computingX
′
=
g
1
a
i and Y
′
=
g
2
b
i,
(3)
returning a transcript generated withX
′ and Y
′ in place of X and Y,
(4)
then settingsk
A
i
=
sk
B
j
=
g
3
a
i
b
i. Let b
′ be the output of 𝒜. 𝒟 outputs 1 if b
=
b
′ and outputs 0, otherwise.
Then, the following is clear:(i)
The probability that𝒟 outputs 1 on a true Diffie-Hellman triple is exactly the probability that 𝒜 correctly guesses the bit b in experiment E
x
p
r
3.
(ii)
The probability that𝒟 outputs 1 on a random triple is exactly the probability that 𝒜 correctly guesses the bit b in experiment E
x
p
r
4. This completes the proof of Claim 4.Experiment
E
x
p
r
5. In this experiment, the session key sk
C
i of each instance Π
C
i activated by a  Send query is chosen uniformly at random from 𝔾 if no one in    p
i
d
C
i has been corrupted before Π
C
i determines its session identifier   s
i
d
C
i. The difference in 𝒜’s advantage between E
x
p
r
4 and E
x
p
r
5 is bounded by the following.Claim 5.
(8)
|
Pr
[
S
u
c
c
5
]
-
Pr
[
S
u
c
c
4
]
|
≤
A
d
v
𝔾
ddh
(
t
′
)
.Proof.
The proof of this claim is essentially similar to that of Claim4. From the adversary 𝒜 whose advantage is nonnegligibly different between E
x
p
r
4 and E
x
p
r
5, we construct a distinguisher 𝒟 that solves the DDH problem in 𝔾. Let (
g
1
,
g
2
,
g
3
)
∈
𝔾
3 be an instance of the DDH problem given as input to 𝒟. 𝒟 begins by selecting a bit b uniformly at random and generating a list  DDHList which is used to link an instance of the DDH problem to a session identifier, 𝒟 then runs 𝒜 as a subroutine and simulates the oracles. It handles all the queries of 𝒜 as in experiment E
x
p
r
4 except for  Send queries.
Consider a query of the formS
e
n
d
(
Π
C
i
,
U
∥
n
U
) which delivers a random nonce n
U to instance Π
C
i. Whenever such a query is made, 𝒟 answers it as follows. (i)
Ifn
U is not the last nonce that Π
C
i is expected to receive, 𝒟 simply waits for the next nonce.
(ii)
Otherwise,𝒟 defines   s
i
d
C
i and checks that anyone in   p
i
d
C
i was corrupted.
(a)
If so,𝒟 responds to the query as in experiment E
x
p
r
4.
(b)
If not,𝒟 checks if the list  DDHList contains an entry of the form   (
s
i
d
C
i
,
X
′
,
Y
′
,
Z
′
), where X
′
,
Y
′
,
Z
′
∈
𝔾.
(1)
If it does,𝒟 computes   σ
CS
=
M
a
c
k
CS
(
C
∥
Y
′
∥
s
i
d
C
i
) and returns C
∥
Y
′
∥
σ
CS in response to the query.
(2)
Otherwise,𝒟 selects two random a
i
,
b
i
∈
ℤ
q, computes X
′
=
g
1
a
i, Y
′
=
g
2
b
i, Z
′
=
g
3
a
i
b
i, and   σ
CS
=
M
a
c
k
CS
(
C
∥
X
′
∥
s
i
d
C
i
), returns C
∥
X
′
∥
σ
CS to 𝒜, and finally adds the tuple   (
s
i
d
C
i
,
X
′
,
Y
′
,
Z
′
) to  DDHList.
When𝒜 makes a Send query that causes an instance Π
C
i to accept, 𝒟 checks if  DDHList contains an entry of the form  (
sid
C
i
,
X
′
,
Y
′
,
Z
′
). If so, 𝒟 sets sk
C
i
=
Z
′. Otherwise, 𝒟 computes sk
C
i as in experiment E
x
p
r
4. For all other Send queries of 𝒜, 𝒟 answers them as in experiment E
x
p
r
4. Now when 𝒜 terminates and outputs its guess b
′, 𝒟 outputs 1 if b
=
b
′ and outputs 0 otherwise.
One can easily see the following.(i)
The probability that𝒟 outputs 1 on a true Diffie-Hellman triple is exactly the probability that 𝒜 correctly guesses the bit b in experiment E
x
p
r
4.
(ii)
The probability that𝒟 outputs 1 on a random triple is exactly the probability that 𝒜 correctly guesses the bit b in experiment E
x
p
r
5.This implies Claim 5.In experimentE
x
p
r
5, the session keys of all fresh instances are chosen uniformly at random from 𝔾 and thus the adversary 𝒜 obtains no information on the bit b chosen by the  Test oracle. Therefore, it follows that   Pr
[
S
u
c
c
5
]
=
1
/
2. This result combined with the previous claims yields the statement of Theorem 5.


### 4.2. Proof of Resistance to Undetectable Online Dictionary Attacks

We now claim that3PAKEsm is secure against undetectable online dictionary attacks as long as the  2PAKE protocol is SK-secure.Theorem 7.
LetUndet be as defined in Section 2.3 and assume that for anyppt adversary 𝒜
′ asking at most q
se   Send queries,  Adv
2
PAKE
sk
(
𝒜
′
) is only negligibly larger than  q
se
/
|
PW
|. Then, for any  ppt adversary 𝒜 asking at most q
se  Send queries,  Pr
3PAKEsm
,
𝒜
[
Undet
] is only negligibly larger than  2
·
q
se
/
|
PW
|.Proof.
Let𝒜 be a ppt adversary who asks q
se  Send queries in mounting an undetectable online dictionary attack against  3PAKEsm. Consider the experiment E
x
p
r
1 described in the proof of Theorem 5 (see Section 4.1). By  Undet
1 (resp.,  Undet
0), we denote the event  Undet defined in experiment E
x
p
r
1 (resp., E
x
p
r
0). We prove Theorem 7 by first proving Claim 6 and then Claim 7.Claim 6.
|
Pr
3PAKEsm
,
𝒜
[
Undet
1
]
-
Pr
3PAKEsm
,
𝒜
[
Undet
0
]
| is only negligibly larger than  q
se
/
|
PW
|.Claim 7.
Pr
3PAKEsm
,
𝒜
[
Undet
1
] is only negligibly larger than  q
se
|
PW
|.Proof of Claim6.
We prove the claim by constructing an adversary𝒜
′ who attacks the SK security of  2PAKE witfh advantage equal to  |
Pr
3PAKEsm
,
𝒜
[
Undet
1
]
-
Pr
3PAKEsm
,
𝒜
[
Undet
0
]
|.
𝒜
′ chooses a random bit b
∈
{
0,1
} and invokes the adversary 𝒜 as a subroutine. 𝒜
′ then simulates the oracles for 𝒜 in the exactly same way as in the simulation for the proof of Claim 1. 𝒜
′ outputs 1 if  Undet occurs and 0 otherwise. From the way the oracles are simulated, it is easy to see the following. (i)
The probability that𝒜
′  outputs 1 when its  Test oracle returns real session keys is equal to the probability that the event  Undet occurs in experiment E
x
p
r
0.
(ii)
The probability that𝒜
′ outputs 1 when its  Test oracle returns random keys is equal to the probability that the event  Undet occurs in experiment E
x
p
r
1. Since 𝒜
′ makes at most q
se  Send queries, we obtain the statement of Claim 6.Proof of Claim7.
Assume thatPr
3PAKEsm
,
𝒜
[
Undet
1
] is nonnegligibly larger than  q
se
/
|
PW
|. Given the adversary 𝒜, we construct an adversary 𝒜
′ against  2PAKE who asks at most q
se  Send queries but has an advantage nonnegligibly larger than  q
se
/
|
PW
|.
𝒜
′ runs 𝒜 as a subroutine while simulating the oracles on its own. 𝒜
′ handles all the oracle queries of 𝒜 as in the experiment E
x
p
r
1 except for  Send queries. When 𝒜 makes a  Send(Π
U
i, m) query, 𝒜
′ checks if m is a message for initiating a new session (of  3PAKEsm) or the  Send query belongs to an execution of  2PAKE. (1)
If both are untrue,𝒜
′ responds to the query as in experiment E
x
p
r
1.
(2)
Otherwise,𝒜
′ answers it by making the same query to its own  Send oracle. If the query prompts Π
U
i to accept, then 𝒜
′ checks if Π
U
i is clean.
(a)
If so,𝒜
′ sets the MAC key of Π
U
i to be a random key drawn uniformly from {
0,1
}
ℓ.
(b)
Otherwise,𝒜
′ makes a  Reveal(Π
U
i) query and sets the MAC key of Π
U
i to be the output of this  Reveal query.
LetΠ
S
t be any server instance against which 𝒜 has mounted an online dictionary attack. Let k
S
t be the session key (i.e., the MAC key) that the instance Π
S
t has computed in its execution of  2PAKE. In order for the instance Π
S
t to terminate normally, the adversary 𝒜 has to make a query of the form  Send(Π
S
t, C
∥
*
∥
σ
CS) such that   V
e
r
k
S
t
(
C
∥
*
∥
s
i
d
S
t
,
σ
CS
)
=
1. When 𝒜 makes such a   Send query (i.e., when the event Undet
1 occurs), 𝒜
′ makes a  Test query against the instance Π
S
t. Note that the instance Π
S
t is fresh as (
1
) it is partnered with no instance and (
2
)
S and C must have not been corrupted. Let k
¯
S
t be the key returned in response to the  Test query. 𝒜
′ outputs 1 if   V
e
r
k
¯
S
t
(
C
∥
*
∥
s
i
d
S
t
,
σ
CS
)
=
1 and outputs 0, otherwise. If  Undet
1 does not occur, 𝒜
′ outputs a random bit. Then, it is not hard to see that
(9)
A
d
v
2
P
A
K
E
sk
(
𝒜
′
)
=
2
·
Pr
2
P
A
K
E
,
𝒜
′
[
S
u
c
c
]
-
1
=
2
·
(
1
2
Pr
3
P
A
K
E
s
m
,
𝒜
[
U
n
d
e
t
1
]
+
1
2
(
1
-
Pr
3
P
A
K
E
s
m
,
𝒜
[
U
n
d
e
t
1
]
)
)
-
1
=
Pr
3
P
A
K
E
s
m
,
𝒜
[
U
n
d
e
t
1
]
.
This completes the proof of Claim 7.Theorem7 immediately follows from Claims 6 and 7.


## 4.1. Proof of SK Security

We first claim that, if the underlying two-party protocol2PAKE is SK-secure, then the  3PAKEsm protocol is SK-secure as well under the DDH assumption in 𝔾 and the security of the MAC scheme Σ.Theorem 5.
LetQ
=
(
q
ex
,
q
se
,
q
re
,
q
co
⁡
,
q
te
). For any adversary with query complexity at most Q and time complexity at most t, its advantage in attacking protocol  3PAKEsm is bounded by
(3)
A
d
v
3
P
A
K
E
s
m
s
k
(
t
,
Q
)
≤
2
·
A
d
v
2
P
A
K
E
s
k
(
t
′
,
Q
′
)
+
(
q
se
+
q
ex
)
2
|
𝔾
|
+
2
·
q
se
·
A
d
v
Σ
e
u
f
-
c
m
a
(
t
′
,
4,4
)
+
4
·
A
d
v
𝔾
d
d
h
(
t
′
)
,
where Q
′
=
(
2
q
ex
,
q
se
,
0
,
q
co
⁡
,
2
q
ex
+
q
se
) and t
′ is the maximum time required to perform an entire experiment involving an adversary who attacks protocol 3PAKEsm with time complexity t.Proof.
Assume an adversary𝒜 attacking protocol  3PAKEsm with time complexity t and query complexity Q
=
(
q
ex
,
q
se
,
q
re
,
q
co
⁡
,
q
te
). We prove Theorem 5 by introducing a sequence of experiments E
x
p
r
0
,
…
,
E
x
p
r
5 and bounding the difference in 𝒜's advantage between two consecutive experiments. E
x
p
r
0 is the original experiment (described in Section 2.2) in which 𝒜 attacks the actual protocol, and E
x
p
r
5 is the experiment in which the advantage of 𝒜 is 0. Let  Succ
i be the event that 𝒜 correctly guesses the hidden bit b (chosen by the Test oracle) in experiment E
x
p
r
i. By definition, we get  Adv
3
PAKEsm
sk
(
𝒜
)
=
2
·
Pr
[
Succ
0
]
-
1.
Before providing details of the proof, we first define the notion of anuncorrupted instance.Definition 6.
We say an instanceΠ
U
i is clean if no one in  pid
U
i has been asked a  Corrupt query. Otherwise, we say it is unclean.Experiment
E
x
p
r
1. We modify the experiment so that each different MAC key is chosen uniformly at random from {
0,1
}
ℓ for all clean instances. The difference in 𝒜's success probability between E
x
p
r
0 and E
x
p
r
1 is bounded byClaim 1.
(4)
|
Pr
[
S
u
c
c
1
]
-
Pr
[
S
u
c
c
0
]
|
≤
A
d
v
2
P
A
K
E
sk
(
t
′
,
Q
′
)
.Proof.
Assume that the advantage of𝒜 in attacking protocol  3PAKEsm is different between two experiments E
x
p
r
0 and E
x
p
r
1. Then we prove the claim by constructing, from 𝒜, an adversary  𝒜
2PAKE attacking protocol  2PAKE with time complexity t
′ and query complexity Q
′.
𝒜
2PAKE begins by choosing a bit b uniformly at random.  𝒜
2PAKE then invokes 𝒜 as a subroutine and answers the oracle queries of 𝒜 on its own as follows.
Execute
Queries.  𝒜
2PAKE answers  Execute queries of 𝒜 by making  Execute and  Test queries to its own oracles. Specifically,  𝒜
2PAKE handles each  Execute(Π
A
i, Π
B
j, Π
S
k) query as follows.(i)
If anyone in{
A
,
B
,
S
} has been corrupted, then  𝒜
2PAKE answers the  Execute query as in experiment E
x
p
r
0.
(ii)
Otherwise,𝒜
2PAKE first makes two queries  Execute(Π
A
i
,
Π
S
k) and  Execute(Π
B
j
,
Π
S
k
′). Let  T2PAKE and  T
2
PAKE
′ be two transcripts returned in response to the  Execute queries. Next,  𝒜
2PAKE makes the queries  Test(Π
A
i) and  Test(Π
B
j) and receives in return two keys k
¯
A
S and k
¯
B
S (either real or random).  𝒜
2PAKE then generates the messages of Steps 2–4 of protocol  3PAKEsm, using k
¯
A
S and k
¯
B
S as the MAC keys. Finally,  𝒜
2PAKE returns these messages prepended by  T2PAKE and  T
2
PAKE
′.
Send
Queries. At a high level, the simulation of the  Send oracle is similar to that of the  Execute oracle. Specifically,  𝒜
2PAKE handles each  Send(Π
U
i, m) query as follows. (i)
If the instanceΠ
U
i is clean or the message m belongs to Step 2 or later steps, then  𝒜
2PAKE answers the query as in experiment E
x
p
r
0.
(ii)
Otherwise,𝒜
2PAKE answers it by making the same query to its own  Send oracle. If the query causes Π
U
i to accept, then  𝒜
2PAKE also makes a  Test(Π
U
i) query (if it had not previously asked a  Test query to the partner of Π
U
i). As in the simulation of the  Execute oracle,  𝒜
2PAKE uses the output of this  Test query as the MAC key in generating the messages of Steps 2–4 of protocol  3PAKEsm.
Reveal
Queries. These queries are answered in the obvious way. Namely,  𝒜
2PAKE responds to the query  Reveal(Π
C
i) by returning the session key sk
C
i.
Corrupt
Queries. When 𝒜 queries  Corrupt(U),  𝒜
2PAKE makes the same query to its own  Corrupt oracle and simply forwards the output to 𝒜.
Test
Queries.  𝒜
2PAKE answers these queries according to the bit b chosen at the beginning of the simulation. That is,  𝒜
2PAKE returns real session keys, which it has computed on its own, if b
=
1, and otherwise returns random keys chosen uniformly at random from 𝔾.
Now at some point in time, when𝒜 terminates and outputs its guess b
′,  𝒜
2PAKE outputs 1 if b
=
b
′ and outputs 0 otherwise.
From the simulation above, it is easy to see that𝒜
2PAKE has at most time complexity t
′ and query complexity Q
′. The advantage of  𝒜
2PAKE in attacking protocol  2PAKE is immediate if we notice the following. (i)
The probability that𝒜
2PAKE outputs 1 when its  Test oracle returns real session keys is equal to Pr
[
Succ
0
], the probability that 𝒜 correctly guesses the bit b in experiment E
x
p
r
0.
(ii)
The probability that𝒜
2PAKE outputs 1 when its  Test oracle returns random keys is equal to Pr
[
Succ
1
], the probability that 𝒜 correctly guesses the bit b in experiment E
x
p
r
1. This means that  Adv
2
PAKE
sk
(
𝒜
2PAKE
) =|
Pr
[
Succ
1
]
-
Pr
[
Succ
0
]
|. Claim 1 then follows.Experiment
E
x
p
r
2
. Let  Repeat be the event that a nonce selected by an instance of a party is selected again by another instance of the same party. The experiment E
x
p
r
2 is aborted, and the adversary does not succeed, if the event  Repeat occurs. This is the only difference between E
x
p
r
1 and E
x
p
r
2. By a straightforward calculation, we get the following.Claim 2.
(5)
|
Pr
[
S
u
c
c
2
]
-
Pr
[
S
u
c
c
1
]
|
≤
(
q
se
+
q
ex
)
2
2
|
𝔾
|
.Experiment
E
x
p
r
3. Let  Forge be the event that the adversary 𝒜 makes a  Send query of the form  Send(Π
U
i, V
∥
*
∥
σ) before querying  Corrupt
(
W
), for some  W
∈
pid
U
i, such that (1) σ is a valid tag on V
∥
*
∥
sid
U
i and (2) no oracle had not previously generated a tag on V
∥
*
∥
sid
U
i. If Forge occurs, this experiment is aborted and the adversary does not succeed. Then we have the following.Claim 3.
(6)
|
Pr
[
S
u
c
c
3
]
-
Pr
[
S
u
c
c
2
]
|
≤
q
se
·
A
d
v
Σ
euf-cma
(
t
′
,
4,4
)
.Proof.
Assuming that the eventForge occurs, we construct, from 𝒜, an algorithm ℱ who outputs, with a nonnegligible probability, a forgery against the MAC scheme Σ. The algorithm ℱ is given oracle access to  Mac
k
(
·
) and  Ver
k
(
·
). The goal of ℱ is to produce a message/tag pair (
m
,
σ
) such that (1) σ is a valid tag on the message m (i.e.,  Ver
k
(
m
,
σ
)
=
1
) and (2) ℱ had not previously queried its oracle  Mac
k
(
·
) on the message m.
Letn be the number of all active sessions that 𝒜 initiates by asking a  Send query. First, ℱ chooses a random α
∈
{
1
,
…
,
n
}. ℱ then simulates the oracle calls of 𝒜 as in experiment E
x
p
r
2; except that in the αth session, it answers  Send queries by accessing its MAC generation and verification oracles. If  Forge occurs in the αth session, ℱ halts and outputs the message/tag pair generated by 𝒜 as its forgery. Otherwise, ℱ halts and outputs a failure indication. This simulation is perfect unless the adversary 𝒜 makes a  Corrupt query against a participant of the αth session. But note that the event of 𝒜 making such a  Corrupt query should not happen if  Forge occurs in the αth session.
From the simulation, it is immediate thatA
d
v
Σ
euf-cma
(
ℱ
)
=
Pr
⁡
[
F
o
r
g
e
]
/
n. Since n
≤
q
se, we get   Pr[
F
o
r
g
e
]
≤
q
se
·
A
d
v
Σ
euf-cma
(
ℱ
). Then, Claim 3 follows by noticing that ℱ has at most time complexity t
′ and makes at most 4 queries to   M
a
c
k
(
·
) and   V
e
r
k
(
·
).Experiment
E
x
p
r
4. This experiment is different from E
x
p
r
3 in that the session key sk of each pair of instances partnered via an  Execute query is chosen uniformly at random from 𝔾 instead of being computed as sk
=
g
x
y
=
X
y
=
Y
x. As the following claim states, the difference in 𝒜’s advantage between E
x
p
r
3 and E
x
p
r
4 is negligible if the DDH assumption holds in 𝔾.Claim 4.
(7)
|
Pr
[
S
u
c
c
4
]
-
Pr
[
S
u
c
c
3
]
|
≤
A
d
v
𝔾
ddh
(
t
′
)
.Proof.
Assume that the advantage of𝒜 is nonnegligibly different between E
x
p
r
3 and E
x
p
r
4. We prove the claim by constructing, from 𝒜, a distinguisher 𝒟 that solves the DDH problem in 𝔾. Let (
g
1
,
g
2
,
g
3
)
∈
𝔾
3 be an instance of the DDH problem given as input to 𝒟. 𝒟 begins by choosing a bit b uniformly at random. 𝒟 then invokes 𝒜 as a subroutine and proceeds to simulate the oracles. 𝒟 answers all the oracle queries of 𝒜 as in experiment E
x
p
r
3, except that it handles each  Execute(Π
A
i
,
Π
B
j, Π
S
k) query by (1)
selecting two randoma
i
,
b
i
∈
ℤ
q,
(2)
computingX
′
=
g
1
a
i and Y
′
=
g
2
b
i,
(3)
returning a transcript generated withX
′ and Y
′ in place of X and Y,
(4)
then settingsk
A
i
=
sk
B
j
=
g
3
a
i
b
i. Let b
′ be the output of 𝒜. 𝒟 outputs 1 if b
=
b
′ and outputs 0, otherwise.
Then, the following is clear:(i)
The probability that𝒟 outputs 1 on a true Diffie-Hellman triple is exactly the probability that 𝒜 correctly guesses the bit b in experiment E
x
p
r
3.
(ii)
The probability that𝒟 outputs 1 on a random triple is exactly the probability that 𝒜 correctly guesses the bit b in experiment E
x
p
r
4. This completes the proof of Claim 4.Experiment
E
x
p
r
5. In this experiment, the session key sk
C
i of each instance Π
C
i activated by a  Send query is chosen uniformly at random from 𝔾 if no one in    p
i
d
C
i has been corrupted before Π
C
i determines its session identifier   s
i
d
C
i. The difference in 𝒜’s advantage between E
x
p
r
4 and E
x
p
r
5 is bounded by the following.Claim 5.
(8)
|
Pr
[
S
u
c
c
5
]
-
Pr
[
S
u
c
c
4
]
|
≤
A
d
v
𝔾
ddh
(
t
′
)
.Proof.
The proof of this claim is essentially similar to that of Claim4. From the adversary 𝒜 whose advantage is nonnegligibly different between E
x
p
r
4 and E
x
p
r
5, we construct a distinguisher 𝒟 that solves the DDH problem in 𝔾. Let (
g
1
,
g
2
,
g
3
)
∈
𝔾
3 be an instance of the DDH problem given as input to 𝒟. 𝒟 begins by selecting a bit b uniformly at random and generating a list  DDHList which is used to link an instance of the DDH problem to a session identifier, 𝒟 then runs 𝒜 as a subroutine and simulates the oracles. It handles all the queries of 𝒜 as in experiment E
x
p
r
4 except for  Send queries.
Consider a query of the formS
e
n
d
(
Π
C
i
,
U
∥
n
U
) which delivers a random nonce n
U to instance Π
C
i. Whenever such a query is made, 𝒟 answers it as follows. (i)
Ifn
U is not the last nonce that Π
C
i is expected to receive, 𝒟 simply waits for the next nonce.
(ii)
Otherwise,𝒟 defines   s
i
d
C
i and checks that anyone in   p
i
d
C
i was corrupted.
(a)
If so,𝒟 responds to the query as in experiment E
x
p
r
4.
(b)
If not,𝒟 checks if the list  DDHList contains an entry of the form   (
s
i
d
C
i
,
X
′
,
Y
′
,
Z
′
), where X
′
,
Y
′
,
Z
′
∈
𝔾.
(1)
If it does,𝒟 computes   σ
CS
=
M
a
c
k
CS
(
C
∥
Y
′
∥
s
i
d
C
i
) and returns C
∥
Y
′
∥
σ
CS in response to the query.
(2)
Otherwise,𝒟 selects two random a
i
,
b
i
∈
ℤ
q, computes X
′
=
g
1
a
i, Y
′
=
g
2
b
i, Z
′
=
g
3
a
i
b
i, and   σ
CS
=
M
a
c
k
CS
(
C
∥
X
′
∥
s
i
d
C
i
), returns C
∥
X
′
∥
σ
CS to 𝒜, and finally adds the tuple   (
s
i
d
C
i
,
X
′
,
Y
′
,
Z
′
) to  DDHList.
When𝒜 makes a Send query that causes an instance Π
C
i to accept, 𝒟 checks if  DDHList contains an entry of the form  (
sid
C
i
,
X
′
,
Y
′
,
Z
′
). If so, 𝒟 sets sk
C
i
=
Z
′. Otherwise, 𝒟 computes sk
C
i as in experiment E
x
p
r
4. For all other Send queries of 𝒜, 𝒟 answers them as in experiment E
x
p
r
4. Now when 𝒜 terminates and outputs its guess b
′, 𝒟 outputs 1 if b
=
b
′ and outputs 0 otherwise.
One can easily see the following.(i)
The probability that𝒟 outputs 1 on a true Diffie-Hellman triple is exactly the probability that 𝒜 correctly guesses the bit b in experiment E
x
p
r
4.
(ii)
The probability that𝒟 outputs 1 on a random triple is exactly the probability that 𝒜 correctly guesses the bit b in experiment E
x
p
r
5.This implies Claim 5.In experimentE
x
p
r
5, the session keys of all fresh instances are chosen uniformly at random from 𝔾 and thus the adversary 𝒜 obtains no information on the bit b chosen by the  Test oracle. Therefore, it follows that   Pr
[
S
u
c
c
5
]
=
1
/
2. This result combined with the previous claims yields the statement of Theorem 5.


## 4.2. Proof of Resistance to Undetectable Online Dictionary Attacks

We now claim that3PAKEsm is secure against undetectable online dictionary attacks as long as the  2PAKE protocol is SK-secure.Theorem 7.
LetUndet be as defined in Section 2.3 and assume that for anyppt adversary 𝒜
′ asking at most q
se   Send queries,  Adv
2
PAKE
sk
(
𝒜
′
) is only negligibly larger than  q
se
/
|
PW
|. Then, for any  ppt adversary 𝒜 asking at most q
se  Send queries,  Pr
3PAKEsm
,
𝒜
[
Undet
] is only negligibly larger than  2
·
q
se
/
|
PW
|.Proof.
Let𝒜 be a ppt adversary who asks q
se  Send queries in mounting an undetectable online dictionary attack against  3PAKEsm. Consider the experiment E
x
p
r
1 described in the proof of Theorem 5 (see Section 4.1). By  Undet
1 (resp.,  Undet
0), we denote the event  Undet defined in experiment E
x
p
r
1 (resp., E
x
p
r
0). We prove Theorem 7 by first proving Claim 6 and then Claim 7.Claim 6.
|
Pr
3PAKEsm
,
𝒜
[
Undet
1
]
-
Pr
3PAKEsm
,
𝒜
[
Undet
0
]
| is only negligibly larger than  q
se
/
|
PW
|.Claim 7.
Pr
3PAKEsm
,
𝒜
[
Undet
1
] is only negligibly larger than  q
se
|
PW
|.Proof of Claim6.
We prove the claim by constructing an adversary𝒜
′ who attacks the SK security of  2PAKE witfh advantage equal to  |
Pr
3PAKEsm
,
𝒜
[
Undet
1
]
-
Pr
3PAKEsm
,
𝒜
[
Undet
0
]
|.
𝒜
′ chooses a random bit b
∈
{
0,1
} and invokes the adversary 𝒜 as a subroutine. 𝒜
′ then simulates the oracles for 𝒜 in the exactly same way as in the simulation for the proof of Claim 1. 𝒜
′ outputs 1 if  Undet occurs and 0 otherwise. From the way the oracles are simulated, it is easy to see the following. (i)
The probability that𝒜
′  outputs 1 when its  Test oracle returns real session keys is equal to the probability that the event  Undet occurs in experiment E
x
p
r
0.
(ii)
The probability that𝒜
′ outputs 1 when its  Test oracle returns random keys is equal to the probability that the event  Undet occurs in experiment E
x
p
r
1. Since 𝒜
′ makes at most q
se  Send queries, we obtain the statement of Claim 6.Proof of Claim7.
Assume thatPr
3PAKEsm
,
𝒜
[
Undet
1
] is nonnegligibly larger than  q
se
/
|
PW
|. Given the adversary 𝒜, we construct an adversary 𝒜
′ against  2PAKE who asks at most q
se  Send queries but has an advantage nonnegligibly larger than  q
se
/
|
PW
|.
𝒜
′ runs 𝒜 as a subroutine while simulating the oracles on its own. 𝒜
′ handles all the oracle queries of 𝒜 as in the experiment E
x
p
r
1 except for  Send queries. When 𝒜 makes a  Send(Π
U
i, m) query, 𝒜
′ checks if m is a message for initiating a new session (of  3PAKEsm) or the  Send query belongs to an execution of  2PAKE. (1)
If both are untrue,𝒜
′ responds to the query as in experiment E
x
p
r
1.
(2)
Otherwise,𝒜
′ answers it by making the same query to its own  Send oracle. If the query prompts Π
U
i to accept, then 𝒜
′ checks if Π
U
i is clean.
(a)
If so,𝒜
′ sets the MAC key of Π
U
i to be a random key drawn uniformly from {
0,1
}
ℓ.
(b)
Otherwise,𝒜
′ makes a  Reveal(Π
U
i) query and sets the MAC key of Π
U
i to be the output of this  Reveal query.
LetΠ
S
t be any server instance against which 𝒜 has mounted an online dictionary attack. Let k
S
t be the session key (i.e., the MAC key) that the instance Π
S
t has computed in its execution of  2PAKE. In order for the instance Π
S
t to terminate normally, the adversary 𝒜 has to make a query of the form  Send(Π
S
t, C
∥
*
∥
σ
CS) such that   V
e
r
k
S
t
(
C
∥
*
∥
s
i
d
S
t
,
σ
CS
)
=
1. When 𝒜 makes such a   Send query (i.e., when the event Undet
1 occurs), 𝒜
′ makes a  Test query against the instance Π
S
t. Note that the instance Π
S
t is fresh as (
1
) it is partnered with no instance and (
2
)
S and C must have not been corrupted. Let k
¯
S
t be the key returned in response to the  Test query. 𝒜
′ outputs 1 if   V
e
r
k
¯
S
t
(
C
∥
*
∥
s
i
d
S
t
,
σ
CS
)
=
1 and outputs 0, otherwise. If  Undet
1 does not occur, 𝒜
′ outputs a random bit. Then, it is not hard to see that
(9)
A
d
v
2
P
A
K
E
sk
(
𝒜
′
)
=
2
·
Pr
2
P
A
K
E
,
𝒜
′
[
S
u
c
c
]
-
1
=
2
·
(
1
2
Pr
3
P
A
K
E
s
m
,
𝒜
[
U
n
d
e
t
1
]
+
1
2
(
1
-
Pr
3
P
A
K
E
s
m
,
𝒜
[
U
n
d
e
t
1
]
)
)
-
1
=
Pr
3
P
A
K
E
s
m
,
𝒜
[
U
n
d
e
t
1
]
.
This completes the proof of Claim 7.Theorem7 immediately follows from Claims 6 and 7.


## 5. Conclusion

In this work, we have presented a three-party PAKE protocol whose security does not rely on the existence of random oracles. The model that we used to prove the security of our protocol allows the adversary to askCorrupt queries and thus captures insider attacks as well as forward secrecy. It is a known fact that proving the security of protocols in such a model is of particular importance in the three-party setting as insider dictionary attacks are most serious threats to three-party PAKE protocols. To the best of our knowledge, our protocol is the first three-party PAKE protocol proven secure against insider, active adversaries in the standard model (i.e., without random oracles and ideal ciphers). Another advantage our protocol has over previously published protocols is that it also achieves provable security against undetectable online dictionary attacks. The latter property is also significant as designing three-party PAKE protocol secure against undetectable online dictionary attacks is an ongoing challenge (as evidenced by the number of three-party PAKE protocols found to be vulnerable to an undetectable online dictionary attack). We leave it as a future work to design a three-party PAKE protocol that achieves not only provable security in the standard model but is more efficient than our protocol.



---

*Source: 825072-2014-04-14.xml*