QC

1¤j¤QC

1

≥ Pr[predj (K) = 1] ’ AdvROR (») =

˜ B4 ,KDF

QC

1¤j¤QC

= uncertC (») ’ AdvROR (»)

B,KDF

and thus uncertC (») ¤ AdvROR (») + AdvSUF-CMA (»).

B,KDF D,MAC

B Decisional Di¬e-Hellman (DDH) Problem

We review the de¬nition of the Decisional Di¬e-Hellman (DDH) problem. Let A

be an attacker. Let G be a ¬nite cyclic group generated by g ∈ G. Let p be a prime

order of G, whose size depends on the security parameter ». We de¬ne the DDH

problem using the attacker A™s advantage in distinguishing two distributions:

R R

AdvDDH (») = | Pr[a ← Zp ; b ← Zp : 1 ← A(1» , g a , g b , g ab )]

A,G

R R R

’ Pr[a ← Zp ; b ← Zp ; r ← Zp : 1 ← A(1» , g a , g b , g r )]|.

We say that the DDH problem is hard if AdvDDH (») = maxA AdvDDH (») is

G A,G

negligible for any attacker A.

New Anonymity Notions for

Identity-Based Encryption

Malika Izabach`ne and David Pointcheval

e

Ecole Normale Sup´rieure “ LIENS/CNRS/INRIA, France

e

{Malika.Izabachene,David.Pointcheval}@ens.fr

Abstract. Identity-based encryption is a very convenient tool to avoid

key management. Recipient-privacy is also a major concern nowadays. To

combine both, anonymous identity-based encryption has been proposed.

This paper extends this notion to stronger adversaries (the authority

itself). We discuss this new notion, together with a new kind of non-

malleability with respect to the identity, for several existing schemes.

Interestingly enough, such a new anonymity property has an independent

application to password-authenticated key exchange. We thus come up

with a new generic framework for password-authenticated key exchange,

and a concrete construction based on pairings.

1 Introduction

Motivation. The idea of using identities instead of public keys in order to

avoid the (costly) use of certi¬cates comes from Shamir [20]. He indeed suggested

Identity-based Encryption (IBE), that would allow a user to encrypt a message

using any string, that would specify the recipient, as encryption parameter, such

that this recipient only can decrypt the ciphertext.

Identity-based cryptography thus provides this interesting feature that one

does not need authenticated public keys. Key managament is made simpler.

Note however that a drawback is an authority that is required to generate the

private keys for the users, according to their identities. This authority thus has

the ability to decrypt any ciphertext. Privacy cannot be achieved with respect

to this authority. Nevertheless, privacy of the plaintext is not the unique goal

in cryptography, with encryption schemes. Privacy of the recipient may also

be a requirement. Such a key-privacy notion has already been de¬ned in the

public-key setting in [3]. It has more recently been extended to the identity-

based setting in [1], under the notion of anonymity. However, the security model

in this IBE setting still trusts the authority. Whereas trusting the authority is

intrinsic for privacy of the plaintext, it is not for the privacy of the recipient:

a stronger anonymity notion is possible, with respect to the authority, but is it

achievable for practical IBE?

For e¬ciency reasons, the use of Key Encapsulation Mechanisms KEM have

been shown as a preferable approach [22]. It consists in generating an ephemeral

key and an encrypted version of the latter. The ephemeral key is thereafter

used with a Data Encryption Method DEM to encrypt the message. In such

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 375“391, 2008.

c Springer-Verlag Berlin Heidelberg 2008

376 M. Izabach`ne and D. Pointcheval

e

a context, we are interested in the semantic security of the ephemeral key,

and the anonymity of the recipient. In the identity-based context, Bentahar

et al. [7] de¬ned Identity-based Key Encapsulation Mechanisms IB-KEM. An

anonymity notion with respect to the authority would then be an interesting

feature.

Interestingly enough, this notion of anonymity with respect to the authority

might have side applications. One of them is password-authenticated key ex-

change [6]. Such a protocol allows two players to establish a private channel,

using a short secret as a sole authentication means. The latter is thus sub-

ject to exhaustive search, but such a short secret is very convenient for human

beings.

Related Work. The idea of identity-based encryption is due to Shamir [20],

in 1984. The ¬rst goal was to simplify public key management. However, the

¬rst practical solutions appeared in 2001 only [10,15]. Thereafter, many schemes

have been proposed, based on pairing, factoring and lattices. Since such schemes

were dealing with encryption, the main security notion was the semantic

security [17].

Even if recipient-anonymity had already been addressed for public-key en-

cryption [3] in 2001, anonymity for IBE has been proposed recently by Abdalla

et al. [1], but as a simple extension of the previous public-key setting de¬nition.

In 2006, Gentry [16] and Boyen and Waters [12] presented the ¬rst anonymous

IBE schemes without random oracles.

Our contributions. As already noticed in [1], anonymity might have some

side applications to searchable encryption. In this paper, we deal with anonymity

for IB-KEM, even with respect to the authority, the so-called Key Anonymity

with respect to the Authority and denoted KwrtA-Anonymity: we ¬rst provide a

formal security model, and then we discuss this security notion with existing

schemes. We also consider a new non-malleability notion for the identity, that

we call identity-based non-malleability: if one encrypts a message (or a key) for

user U , one has no idea about the value obtained by another user U , whatever

the relation between U and U (or the identities) is.

Thereafter, we show that these security notions can also have side applica-

tions to password-authenticated key exchange. Such a KwrtA-anonymous and

identity-based non-malleability IB-KEM scheme can indeed be plugged into a

password-authenticated two-party key exchange protocol, in the same vein as the

IPAKE construction [14] did with trapdoor hard-to-invert group isomorphisms.

Our security result holds in a stronger security model than usual (with an adap-

tive selection of passive and active attacks, as in [19]), but the construction still

assumes the random-oracle model [5], as in [14].

Eventually, we provide an IB-KEM, that is both KwrtA-anonymous and

identity-based non-malleable, in addition to the full-identity semantic security,

against chosen-plaintext adversaries. This thus leads to a new password-authent-

icated two-party key exchange protocol.

New Anonymity Notions for Identity-Based Encryption 377

2 Anonymous Identity-Based Encryption

Anonymity for public-key encryption schemes has ¬rst been introduced by Bel-

lare et al. [3], under the key privacy security notion, and has been extended to

identity-based encryption by Abdalla et al. [1].

In these papers, anonymity meant that even if the adversary chooses a message

and two identities (or two public keys), and the challenger encrypts the message

with one of the identities (or keys), the adversary cannot guess which one has

actually been involved in the computation. This notion is quite strong for public-

key encryption, but not that strong in the identity-based setting since it does not

capture anonymity with respect to the authority that knows the master secret

key, and even chooses the public parameters PK.

Unfortunately, the previous de¬nitions cannot be trivially extended: the ad-

versary can easily break anonymity if he knows the expected plaintext, and just

hesitates between two identities, since he can decrypt any ciphertext. Anonymity

can only be expected against the server if the plaintexts follow a non-trivial dis-

tribution. Since we will deal with key-encapsulation mechanisms, this non-trivial

distribution is already implicit for the ephemeral keys.

This enhanced security notion will be called Key Anonymity with respect to

the Authority and denoted KwrtA-Anonymity. This section de¬nes precisely this