GT .

q

1 ← A(g, g , g , g , g , · · · , g z/x , V )

xy

It is clear that such a sequence of powers should not provide much information

to the adversary. And thus, for any polynomial-time adversary A, the above

advantage is negligible. In the full version of this paper [18], we provide the

proofs that our two new problems are intractable for generic adversaries.

Previous IBE Schemes

3.3

Let us review several IBE, and see which properties they satisfy. For the sake

of simplicity, for all of them, we review the key encapsulation mechanisms. In

New Anonymity Notions for Identity-Based Encryption 383

several schemes, we will need a deterministic map F from identities onto the

group G, possibly with parameter PK.

R

The Boneh-Franklin Scheme [10]. In this scheme, MK = s ← Zp and

PK = g s . The map F (ID) is independent of PK. This is a function onto G,

modeled as a random oracle in the security analysis. The ciphertext c = g r ∈ G

corresponds to the key K = e(F (ID), PK)r = BDHg (PK, c, F (ID)) = e(uskID , c),

ˆ ˆ

where uskID = F (ID) = co-CDHg,F (ID) (PK) ∈ G.

s

It is quite similar to the ElGamal encryption, and thus the semantic security

relies on the DBDHG,ˆ, but against chosen-plaintext attacks only, in the random

e

oracle model, even with access to the Extract-query, which is similar to the Boneh-

Lynn-Shacham signature [11] (secure against chosen-message attacks under the

CDHG problem).

Since the ciphertext is totally independent of the identity, this scheme is

KwrtA-anonymous, in the information-theoretical sense. Nevertheless, the ba-

sic anonymity is similar to the semantic security, and relies on the DBDHG,ˆ. e

However, since the ciphertext does not involve the identity, it is easy to break

the identity-based non-malleability: knowing r and c = g r , one easily computes

K = BDHg (PK, c, F (ID)) = e(F (ID), PK)r , for any ID of ones choice.

ˆ

R R

The Boneh-Boyen Scheme [8]. In this scheme, ± ← Zp , g, g2 , h ← G, and

PK = (g, g1 = g ± , g2 , h), while MK = g2 . The map FPK is de¬ned by FPK (ID) =

±

ID

g1 · h. The ciphertext c = (g s , FPK (ID)s ) corresponds to the key

K = e(g1 , g2 )s = e(c1 , usk2 )/ˆ(usk1 , c2 ),

ˆ ˆ e

R

if one gets uskID = (g r , MK · FPK (ID)r ), for any r ← Zp .

As above, the semantic security relies on the DBDHG,ˆ assumption, in the

e

standard model, but against selective-ID chosen-plaintext attacks, even with

access to the Extract-query (the underlying signature scheme is selective-forgery

secure against chosen-message attacks under the CBDH assumption).

However, because of the redundancy in the ciphertext, which matches with

one identity only, this scheme is not anonymous: one just has to check, for

a candidate ID, and a ciphertext c = (c1 , c2 ), whether (g, FPK (ID), c1 , c2 ) is a

?

Di¬e-Hellman tuple, by e(c1 , FPK (ID)) = e(c2 , g). Since this attack did not need

ˆ ˆ

a candidate key K, a fortiori, this scheme is not KwrtA-anonymous.

On the other hand, since the ciphertext focuses to a speci¬c recipient, one

has no idea how another ID would decrypt it, because of its randomness r in

the decryption key: for wrong user, with usk = (g r , g2 FPK (ID )r ), and c =

±

(g s , FPK (ID )s ) (s = s since ID is not the intended recipient), K = K — H r ,

for H = 1, and r totally random. Therefore, it is identity-based non-malleable

in the information-theoretical sense.

The Gentry Scheme [16]. In 2006, two schemes have been proposed, with

R R

provable anonymity. Gentry™s scheme is one of them: g, h ← G and ± ← Zp . The

public parameters are PK = (g, g1 = g ± , h) and MK = ±. The map FPK is de¬ned

384 M. Izabach`ne and D. Pointcheval

e

by FPK (ID) = g1 ·g ’ID = g ±’ID . The ciphertext c = (FPK (ID)s , e(g, g)s ) is the en-

ˆ

capsulation of K = e(g, h) , and thus, setting (usk1 , usk2 ) = (r, (hg ’r )1/(±’ID) ),

s

ˆ

R

for any r ← Zp , K = e(c1 , usk2 ) · c2 usk1 .

ˆ

The scheme is semantically secure and anonymous against chosen plaintext

attacks, even with access to the Extract-query, under the truncated decisional

augmented bilinear Di¬e-Hellman exponent assumption (see [16] for details).

However, the scheme is not KwrtA-anonymous, since using bilinear maps com-

bined with the redundancy inside the ciphertext provides a test for any target

identity ID , since knowing ±, A can test whether

?

c2 ±’ID = e(g, g)s(±’ID ) = e(c1 , g) = e(g s(±’ID ) , g).

Since the ciphertext is speci¬c to the recipient, A has no idea how an other ID

decrypts c = (c1 , c2 ), c = (FPK (ID )s , e(g, g)s ), since

K = e(c1 , usk2 ) · c2 usk1 = K · (ˆ(g, g)usk1 /ˆ(g, h))s’s ,

ˆ e e

is a random element in GT . Thus, the scheme is identity-based non-malleable in

the information-theoretical sense.

The Boyen-Waters scheme [13]. Boyen and Waters proposed another prov-

R

ably anonymous scheme: ω, t1 , t2 , t3 and t4 ← Zp are set to be the master secret

key and © = e(g, g)t1 ·t2 ·ω , g, g0 , g1 , v1 = g t1 , v2 = g t2 , v3 = g t3 are the public pa-

ˆ

R

rameters PK, with g a random generator of G and g0 , g1 ← G. The map FPK is

de¬ned by FPK (ID) = g0 · ID. To encrypt a key, one chooses a random s ∈ Zp and

sets K = © s , its encapsulation has the following form: c = (c0 , c1 , c2 , c3 , c4 ), with

s s’s s s’s s

c0 = FPK (ID) , c1 = v1 1 , c2 = v21 , c3 = v3 2 , and c4 = v42 . To decapsulate

the key, one has to compute

K ’1 = © ’s = e(g, g)’ωt1 t2 s

ˆ

= e(c0 , usk0 ) — e(c1 , usk1 ) — e(c2 , usk2 ) — e(c3 , usk3 ) — e(c4 , usk4 )

ˆ ˆ ˆ ˆ ˆ

with uskID = (usk0 , usk1 , usk2 , usk3 , usk4 ), where:

usk0 = g r1 t1 t2 +r2 t3 t4

’r t ’r1 t1

usk1 = g ’ωt2 FPK (ID) 1 2 usk2 = g ’ωt1 FPK (ID)

’r t ’r t

usk3 = FPK (ID) 2 4 usk4 = FPK (ID) 2 3

R

for any r1 , r2 ← Zp . This scheme is semantically secure under DBDHG,ˆ, and e

anonymous under the decision linear assumption (we do not give more details

since this scheme is totally di¬erent from ours below. The reader is refereed

to [13]). However, it is not KwrtA-anonymous: since knowing the master key

and given a ciphertext c = (c0 , c1 , c2 , c3 , c4 ), one can decide for a target identity

whether c0 , c1 , c2 or/and c0 , c3 , c4 is a linear tuple in basis v0 , v1 , v2 and v0 , v3 , v4

respectively.

Since the key is completely independent of the identity and c0 is determined

by the identity (among other elements), the same argument than for the two

New Anonymity Notions for Identity-Based Encryption 385

previous schemes holds: it is identity-based non-malleable in an information-

theoretically sense.

Note that for all the above schemes, the public parameters consist of inde-

pendent elements in appropriate groups. The validity check ValidIBK (PK) is thus

trivial.

3.4 Our Scheme