2.1.4.4 Message Authentication Codes

A message authentication code (MAC) allows two parties, who have shared a secret

key in advance, to authenticate their subsequent communication. More formally, a

MAC is a key-based algorithm which associates a tag with every valid message. The

tag for a particular message may be ef¬ciently veri¬ed by the party sharing the key.

Furthermore, an adversary who sees many message/tag pairs is unable to forge a tag

on a new message. We begin with a de¬nition of a MAC algorithm as described in

De¬nition 2.1.17.

De¬nition 2.1.17 (A MAC Scheme) A MAC scheme is given by a triple of algo-

rithms, Π = (K , MAC, V ), where

4 Existential unforgeability is de¬ned to be the property that the adversary, A , is unable to forge

the signature of one message that may not necessarily be the choice of A .

5 In an adaptive chosen-message attack, the adversary, A , is allowed to ask the signer to sign

a number of messages of A ™s choice. The choice of these messages may depend on previously

obtained signatures.

2.1 Mathematical Background 27

• K , the key generation algorithm, is a probabilistic algorithm that takes a secu-

rity parameter k and returns sk.

• G , the tagging algorithm, is a probabilistic algorithm that takes sk and a message

x ∈ {0, 1}— to produce a tag, T .

• V , the veri¬cation algorithm, is a deterministic algorithm which takes a key sk,

a message x ∈ {0, 1}— , and a tag T to indicate whether the tag is valid or invalid.

We require that for all k, all sk which can be output by K (k), all x ∈ {0, 1}— , and for

all T that can be output by Gsk (x), we have that Vsk (x, T ) = Valid. We also require

that K , G , and V can be computed in polynomial time.

We note that there are three types of attacks against MAC schemes [54], namely

known text attack, chosen-message attack, and adaptive chosen-message attack. In

this book, we only consider adaptive chosen-message attack, the strongest of the

three attacks. The formal de¬nitions of a MAC scheme and its security under adap-

tive chosen-message attack exactly parallel those given above for the digital signa-

ture scheme.

De¬nition 2.1.18 (Security under ACMA [48]) Π =(K ,MAC,V ), a MAC scheme,

is secure in the sense of adaptive chosen message attack (ACMA) if for any proba-

bilistic, polynomial time forging algorithms F , the following is negligible (in k):

Pr[(sk) ← K (k); (x, s) ← F Gsk (·) (k) : Vsk (x, T ) = Valid]

2.1.4.5 Cryptographic Hash Functions

A hash function, H , is an ef¬ciently computable algorithm that maps an input x of

arbitrary ¬nite bit-length to an output H (x) of ¬xed bit-length n [54, Chapter 9]. In

other words, hash functions are mappings which allow us to compress arbitrary long

messages to ¬xed length values, and are often employed by cryptographic schemes.

We recall the de¬nition of a Collision Resistant Hash Function (CRHF), H , with

inputs x, x and outputs y, y in the same manner which is given by Damg˚ rd [40, 41]

a

and Preneel [85, De¬nition 2.2], as described in De¬nition 2.1.19.

De¬nition 2.1.19 (Collision Resistant Hash Function (CRHF)) A CRHF is a func-

tion H that satisfy the following underlying requirements:

• The description of H must be publicly known and should not require any secret

information about its operation.

• Preimage resistance: for essentially all pre-speci¬ed outputs, it is computation-

ally infeasible to ¬nd any input which hashes to that output (i.e., to ¬nd any

preimage x such that H (x ) = y when given any y for which a corresponding

input is unknown).

• 2nd-preimage resistance: it is computationally infeasible to ¬nd any second in-

put which has the same output as any speci¬ed input (i.e., given x, to ¬nd a

2nd-preimage x = x such that H (x) = H (x ).

28 2 Background Materials

• Collision resistance: it is computationally infeasible to ¬nd any two distinct in-

puts x, x which hash to the same output (i.e., such that H (x) = H (x )).

Recent work of Rogaway and Shrimpton [87] formalizes the above requirements

into seven different de¬nitions. The implications and separations among these seven

de¬nitions within the concrete security and provable security framework are also

presented.

2.1.4.6 Random Oracles

The de¬nition of random oracle, ¬rst informally introduced by Fiat and Shamir [44]

and later formalized by Bellare and Rogaway [15], represents an idealized view of

hash functions. In other words, hash function is formalized by an oracle which pro-

duces a truly random value for each query. However, if the same query is asked more

than once, identical answers are presented.

Some critics argue that in the real world, no single deterministic polynomial-time

function can provide a good implementation of the random oracle. Consequently,

it is argued that random oracles cannot be realized in practice [31, 65]. However,

recent work of Coron, Dodis, Malinaud, and Puniya [39] shows how a provable se-

cure arbitrary-size random oracle can be constructed from a compression function

viewed as a ¬xed-length random oracle. Several constructions that can be imple-

mentable in practice are also presented.

The random oracle model is analogous to the ideal group model (also known as

the generic group) introduced into cryptography by Shoup [95] and suffers from

the same severe limitations as shown by Canetti, Goldreich, and Halevi [31]. Some

might argue that a proof in the random oracle model is more of a heuristic proof than

a real one. Despite the criticism, no one has yet provided a convincing contradiction

to the practicality of the random oracle model. This model is still widely accepted by

the cryptographic community6 . In many applications, a very ef¬cient protocol with

a heuristic security proof is preferred over a much less ef¬cient one with a complete

security proof [32]. Moreover, as Black [17] observed, no scheme has yet to been

proven secure in the random-oracle model and broken once instantiated with some

hash function, unless that was the goal from the very beginning.

6 In a recent work, Gentry, MacKenzie, and Ramzan [46] proposed the ¬rst practical and provable-

secure oblivious transfer password-based protocol whose proof of security relies on the random

oracle model.

2.2 Key Establishment Protocols and their Basis 29

2.2 Key Establishment Protocols and their Basis

Key establishment, a fundamental building block in cryptography, is de¬ned to be

any process whereby a shared secret key becomes available to two or more par-

ties, for subsequent cryptographic use [54, De¬nition 12.2]. Such a scheme can be

broadly classi¬ed into key agreement or key transport depending on the nature of

the session key (whether input to the session key is required from only one party or

all the participating parties) [27, 54].

The basis of many key establishment protocols relies on the Dif¬e“Hellman key

exchange and RSA algorithm [86]. Some examples of such protocols are as follows.

Dif¬e“Hellman-based Protocols.

• The MQV protocol [73, 80].

• The HMQV protocol of Krawczyk [71] proven secure in the CK2001 model.

• The Uni¬ed Model protocol of Blake-Wilson, Johnson, and Menezes [18, Pro-

tocol 3] proven secure in the Bellare“Rogaway model.

• The OMDHKE protocol of Bresson, Chevassut, and Pointcheval [28] proven

secure in the Bellare“Rogaway model.

• The “Twist-AUgmented” protocol of Chevassut, Fouque, Gaudry, and

Pointcheval [35] proven secure in the Bellare“Rogaway model.

• The key exchange protocols of Katz, Ostrovsky, and Yung [63, 64] proven

secure in the Bellare“Rogaway model.

• The password-based protocols, PPK, PAK, and PAK-Z, of MacKenzie [75]

proven secure in the Bellare“Rogaway model.

• The password-based protocols, EKE and OPKeyX, of Abdalla, Chevassut,

and Pointcheval [1] proven secure in the Bellare“Rogaway model.

• The password-based protocols, SPAKE-1 and SPAKE-2, of Abdalla and

Pointcheval [2] proven secure in the Bellare“Rogaway model.

RSA-based Protocols Proven Secure in the Bellare“Rogaway Model.

• The password-authenticated key exchange protocols, SNAPI and SNAPI-X,

of MacKenzie, Patel, and Swaminathan [76].

• The PEKEP and CEKEP protocols of Zhang [103].

• The QR-EKE protocol of Zhang [104].

However, in recent years, elliptic curve cryptography (ECC) [69, 82] has emerged

as a promising branch of public-key cryptography due to its potential for offering

similar security to established public-key cryptosystems at reduced key sizes. We

observe an emerging trend in the use of identity-based cryptography, such as a large

number of identity-based key agreement protocols based on pairings. Some exam-