6.1.3 Security Proof

The proof follows that of Bellare and Rogaway [5] quite closely; differences include

the use of a combined authenticated encryption scheme (as opposed to separate en-

cryption and MAC functions) and the different partnering function used. The general

idea of the security proof is to assume that the protocol adversary can gain an ad-

vantage and use this to break the assumptions about the security of the encryption

algorithm. Since the adversary relies on its oracles to run we simulate the oracles so

1 We remark that the security proof of Protocol 6.1 does not hinge on the dif¬culty of predicting a

valid session identi¬er. In fact, we may assume that session identi¬ers are made publicly available

when the status of the principal becomes “ACCEPTED”. In other words, anyone (including the

adversary, A ) knows what the value of a particular session identi¬er after the associated oracle has

accepted the session key associated with the particular session identi¬er.

6.1 A Provably-Secure Revised Protocol of Boyd 105

that we can supply the answers to all the queries the adversary might ask. We cannot

supply answers which rely on knowledge of the encryption keys that we are trying

to break, so we use the integrity of plaintexts to show that these queries would, al-

most certainly, not be answered by any oracle running the protocol. As long as the

simulation works with non-negligible probability the assumption about the encryp-

tion scheme fails.

Following Bellare and Rogaway [5] we need to extend the de¬nition of a secure en-

cryption scheme to allow the adversary to obtain multiple encryptions of the same

ciphertext under many different independent encryption keys. Such an adversary is

termed a multiple eavesdropper. A multiple eavesdropper, M E , is allowed to ob-

tain encryptions of the same plaintext under two different independent encryption

keys. We can bound the advantage of a multiple eavesdropper by considering it as a

special case of the multi-user setting analysed by Bellare, Boldyreva and Micali [2].

In their notation we have the case of qe = 1, meaning that the adversary can only ob-

tain one encryption for each encryption key. Specialising their main theorem gives

the following.

Lemma 6.1.1 Suppose that an adversary has advantage at most µ(k) for encryption

scheme (E , D). Then a multiple eavesdropper has advantage not more than n · µ(k).

Notice that since an authenticated encryption scheme is also a secure encryption

scheme in the sense de¬ned by this result, it also holds for an authenticated encryp-

tion scheme. This allows us to de¬ne a variant of game G1 which we call G1 . The

only difference between these is that in G1 the adversary is given access to two en-

cryption oracles for two independently generated keys, and its challenge consists of

two encryptions of either m0 or m1 under the two keys.

The idea of the proof is to consider the situation when the adversary at some stage

forges a message successfully. When this occurs we can use the adversary to break

the integrity of the authenticated encryption scheme. When this does not occur we

use the adversary to break the con¬dentiality. More formally, de¬ne forge to be the

event that the protocol adversary, A produces a ciphertext C associated with a un-

corrupted entity U such that DK (C) =⊥ where K is the long term key of entity U.

Noting that

Pr(success) ¤ Pr(forge) + Pr(success|forge)

we can split the proof up by showing that each of the two terms on the right is

negligible.

6.1.3.1 Integrity attacker

Assume that A is an adversary against the protocol. We use A to construct a forger

F for the authenticated encryption scheme S E described in De¬nition 6.1.1. We

will say that the event successF occurs if F wins game G2 against S E .

106 6 An Extension to the Bellare“Rogaway Model

Lemma 6.1.2 There is an ef¬cient algorithm F de¬ned using A such that if forge

occurs with non-negligible probability then successF occurs with non-negligible

probability .

In order to prove Lemma 6.1.2 we describe how F is constructed. When F runs

it receives access to the encryption and veri¬cation oracles of the authenticated en-

cryption scheme S E . Its output must be a forged ciphertext for a message m which

was not previously input to the encryption oracle.

In order to obtain the forgery F runs A by ¬rst choosing a user Ui for i ∈R [1, Q].

This user will be simulated as though its long-term key is the one used in S E . For

all other j ∈ [1, Q] with j = i, F generates the long-term shared key using the key

generation algorithm Kk . This allows F to answer all the oracle queries from A as

follows.

Send(U, s, M) For any well-formed queries to S, F can reply with valid cipher-

texts, by choosing the session key and forming the ciphertexts, either directly

using the known key or using the encryption oracle in the case of Ui . For queries

to initiate a protocol run, F can generate a random nonce and answer appropri-

ately. Finally, consider a query to either an initiator or responder oracle including

a claimed server message (corresponding to protocol messages 2 or 3). The rel-

evant ciphertext can be veri¬ed either directly using the known key or using the

veri¬cation oracle. If the ciphertext is veri¬ed correctly then the oracle accepts

and this information is returned to A .

Reveal(U, s) Since all session keys are known from running the Send(U, s, M)

queries the query can be trivially answered with the correct session key (if ac-

cepted).

Corrupt(U) As long as U = Ui all the private information is available and the

query can be answered. In the case U = Ui then the query cannot be answered

and F will abort and fail.

Test(U, s) Since all the accepted session keys are known from running the Send

queries the query can be trivially answered by identifying the correct session key.

F continues the simulation until a forgery event against S E occurs, or until A

halts. Note that as long as F does not abort then the simulation is perfect. If forge

occurs then the probability that the user involved is Ui equals 1/Q. In this case the

event successF occurs. Futhermore, in this case F does not abort since Ui cannot be

corrupted before the forge event. Therefore we arrive at the following upper bound.

Pr(forge) ¤ Q · Pr(successF ) (6.1)

6.1.3.2 Con¬dentiality attacker

Now assume that A gains an advantage without producing a forgery. This time

we use A to form an algorithm X which has a non-negligible advantage in the

encryption scheme.

6.1 A Provably-Secure Revised Protocol of Boyd 107

Lemma 6.1.3 There is an ef¬cient algorithm X de¬ned using A such that if suc-

cess occurs but forge does not occur, then X wins game G1 .

Two random keys K and K are chosen by the challenger for S E and X is given

access to the encryption oracles for these keys. First X chooses two users Ui and

U j for i, j ∈R [1, Q]. For all other k ∈ [1, Q], X generates the long-term key using

the key generation algorithm Kk . Next A chooses two random session keys K0 and

K1 . The two messages that X asks of the challenger for S E are M0 = (Ui ,U j , K0 )

and M1 = (Ui ,U j , K1 ). The challenger responds with a ciphertext pair Cb ,Cb which

are the authenticated encryptions of either M0 or M1 under the two keys K and

K . Suppose that QS is the maximum number of Send queries that A will ask of

the server and QH is the maximum number of hash queries that A will ask of the

server. X chooses a value s0 randomly in [1, QS ]. The idea is that X will inject

the ciphertexts Cb ,Cb into a random server Send(U, s, M) query. X proceeds to

simulate responses for A as follows.

H (K||SIDk ) For queries H (K||SIDk ), if this query was asked before, then re-

i i

turn the previous answer. Otherwise, return a random value, v ∈R {0, 1}k . In ad-

dition, store this answer together with the query in a list of DH-tuples.

Send(U, s, M) First consider Send queries to the server. X must simulate re-

sponses from the server with ciphertexts for two users A and B. There are three

cases:

• Neither A nor B is equal to Ui . The session key KS is chosen randomly by

X and the required tickets can be generated by X using the long-term keys

chosen.

• One of A or B is equal to Ui and the other is not equal to U j . X chooses the

session key randomly and obtains the ticket for Ui using the encryption oracle

and generates the ticket for the other user with the known long-term key.

• One of A or B is equal to Ui and the other is equal to U j . If s = s0 then A uses

Cb and Cb as the two tickets for Ui and U j . Otherwise X chooses the ses-

sion key randomly and obtains the tickets for Ui and U j using the encryption

oracles.

Now consider Send queries sent to users. Queries to initiate a protocol run are

trivially simulated. Queries that include ciphertexts must be answered by either

accepting or rejecting depending on whether the ciphertext is valid. Because

forge does not occur we know that A cannot form a valid ciphertext unless

it was output as a result of a Send query to the server. Therefore X has seen

every valid ciphertext before and can respond with acceptance when these are

seen. Ciphertexts that X has not seen are rejected.

Reveal(U, s) X knows all session keys that have been accepted, with the possible