The success of A in G is quanti¬ed in terms of A ™s advantage in distinguish-

ing whether A receives the real key or a random value. A wins if, after asking

i

a Test(Uu ,Uv , i) query, where ΠUu ,Uv is fresh and has accepted, A ™s guess bit b

equals the bit b selected during the Test(Uu ,Uv , i) query.

Let the advantage function of A be denoted by AdvA (k), where

AdvA (k) = |2 — Pr[b = b ]| ’ 1.

2.3.4 The Bellare“Rogaway Models

An important difference between the three variants of the Bellare“Rogaway model

is in the way partner oracles are de¬ned (i.e., the de¬nition of partnership). The

de¬nition of partnership is used in the de¬nition of security to restrict the adversary™s

2.3 The Computational Complexity Approach 43

Reveal and Corrupt queries to oracles that are not partners of the oracle whose key

the adversary is trying to guess. In other words, the de¬nition of security depends

on the partnership mechanism and the notion of indistinguishability. These will be

described in sections that follow.

2.3.4.1 The BR93 Model

The BR93 model de¬nes partnership using the notion of matching conversations,

where a conversation is de¬ned to be the sequence of messages sent and received by

an oracle. The sequence of messages exchanged only during the Send oracle queries

is recorded in the transcript, T . At the end of a protocol run, T will contain the record

of the Send queries and the responses as shown in Figure 2.2. De¬nition 2.3.2 gives

a simpli¬ed de¬nition of matching conversations for the case of the protocol shown

in Figure 2.2.

time „0

˜start™

±1

time „1

±1

β1

j

i

ΠA,B ΠB,A

time „2

β1

±2

time „3

±2

*

Fig. 2.2 Matching conversation

De¬nition 2.3.2 (Matching Conversations [14]) Let nS be the maximum number

of sessions between any two parties in the protocol run. Run the protocol shown

in Figure 2.2 in the presence of a malicious adversary A and consider an initia-

j

i

tor oracle ΠA,B and a responder oracle ΠB,A who engage in conversations CA and

j

i

CB respectively. ΠA,B and ΠB,A are said to be partners if they both have matching

conversations, where

44 2 Background Materials

CA = („0 , ˜start , ±1 ), („2 , β1 , ±2 )

CB = („1 , ±1 , β1 ), („3 , ±2 , —), for „0 < „1 < . . .

This sequence encodes that

i

• at time „0 , oracle ΠA,B was asked ˜start and responded with ±1 .

j

• At a later time, „1 > „0 , oracle ΠB,A was asked ±1 and responded with β1 .

i

• Oracle ΠA,B was asked β1 and responded with ±2 at time „2 > „1 .

j

• Finally, at time „3 > „2 , oracle ΠB,A was asked ±1 and responded with —.

Note that the construction of the conversation shown in De¬nition 2.3.2 depends on

i

the number of parties and the number of message ¬‚ows. Informally, both ΠA,B and

j

ΠB,A are said to be BR93 partners if each one responded to a message that was sent

unchanged by its partner with the exception of perhaps the ¬rst and last messages.

De¬nition 2.3.3 describes security for the BR93 model.

De¬nition 2.3.3 (BR93 Security [14]) A protocol is secure in the BR93 model if,

for all probabilistic, polynomial time adversaries A ,

j

i

Validity. If uncorrupted oracles ΠA,B and ΠB,A complete with matching conversa-

tions, then both oracles accept and have the same session key.

Indistinguishability. For all probabilistic, polynomial time adversaries, A , the

advantage of A , AdvA (k), in game G is negligible.

Requirement 1 of De¬nition 2.3.3 implies entity authentication. Entity authentica-

tion is said to be violated if some fresh oracle terminates with no partner.

2.3.4.2 The BR95 Model

Partnership in the BR95 model is de¬ned using the notion of a partner function,

which uses the transcript containing the record of all Send oracle queries to deter-

mine the partner of an oracle. No explicit de¬nition of partnership, however, was

provided in the original paper since there is no single partner function ¬xed for any

protocol. Instead, security is de¬ned predicated on the existence of a suitable partner

function. De¬nition 2.3.4 describes partnership for the BR95 model.

De¬nition 2.3.4 (BR95 Partner Function [16]) A partner function f in the BR95

model is a polynomial-time mapping between an initiator oracle and a partnering

responder oracle (if such a partner exists), which uses the transcript T to determine

the partner of an oracle.

Let A and B be some initiator and responder principals, and also i and j be some

i

instances of A and B respectively. The notation fA,B (T ) = j denotes that the partner

j j

i i

oracle of ΠA,B is ΠB,A . The initial values fA,B (T ) = — and fB,A (T ) = — mean that

2.3 The Computational Complexity Approach 45

j

i

neither ΠA,B nor ΠB,A has a partner. Two oracles are BR95 partners if, and only if,

the speci¬c partner function in use says they are.

Such a partner de¬nition can easily go wrong. One such example is the partner

function described in the original BR95 paper for the 3PKD protocol [16], which

was later found to be ¬‚awed as described in Chapter 3.

De¬nition 2.3.5 describes security for the BR95 model.

De¬nition 2.3.5 (BR95 De¬nition of Security [16]) A protocol is secure in the BR95

model if both the following requirements are satis¬ed:

j

i

When the protocol is run between two oracles ΠA,B and ΠB,A in the ab-

Validity.

j

i

sence of a malicious adversary, both ΠA,B and ΠB,A accept and hold the same

session key, and

Indistinguishability. For all probabilistic, polynomial time adversaries, A , the

advantage of A , AdvA (k), in game G is negligible.