ValidIBK (PK). Takes as input the public parameters PK, and checks whether they

satisfy the required properties.

Identity-based Non-Malleability. In the application we will study later, a

new security notion for identity-based encryption will appear. It basically states

that when one sends a ciphertext to a user ID, one has no idea how user ID

will decrypt it, even for identities chosen by the adversary. This means that

when one computes an encapsulation, it provides an ephemeral session key with

a unique recipient, and not several secret keys with several partners. We de¬ne

the identity-based non-malleability game as follows:

Setup: The challenger runs SetupIBK on input 1» to obtain the public param-

eters PK, and the master secret key MK. It publishes PK.

Attack: The adversary A adaptively issues Extract and Decaps queries, and

outputs a ciphertext c, and two pairs (K0 , ID0 ), and (K1 , ID1 ).

The adversary wins this game if the two formal equalities hold:

K0 = DecapsIBK (ID0 , c) and K1 = DecapsIBK (ID1 , c).

We thus de¬ne the success of A in breaking the Identity-based Non-Malleability

of an IB-KEM scheme by:

⎡ ¤

(PK, MK) ← SetupIBK (1» );

Succid-nm (A) = Pr ⎣ ¦.

(c, (K0 , ID0 ), (K1 , ID1 )) ← A(PK) :

IBK

K0 = DecapsIBK (ID0 , c) § K1 = DecapsIBK (ID1 , c)

Note that this security notion is for a normal user, and not for the authority

itself. Indeed, it would clearly be incompatible with KwrtA-Anonymity.

New Anonymity Notions for Identity-Based Encryption 381

Anonymous and Non-malleable IB-KEM

3

Since the ¬rst practical IBE schemes, new features, and new e¬cient/security

criteria have been de¬ned. An e¬cient anonymous IBE with a tight security

proof in the standard model is one of the open problems. In this section, we ¬rst

review some candidates, and then propose a new scheme that satis¬es all the

above requirements: semantic security, various anonymity notions and identity-

based non-malleability.

3.1 Backgrounds on Pairings

Let G1 and G2 be two cyclic groups of large prime order p. We suppose that

these two groups are equipped with a pairing, i.e. a non-degenerated and e¬-

ciently computable bilinear map e : G1 — G2 ’ GT . In the following, we use

ˆ

multiplicative notation for G1 and G2 : e(g1 , g2 ) = e(g1 , g2 )ab , for all a, b ∈ Zp ,

ˆab ˆ

and any g1 ∈ G1 and g ∈ G2 .

For the sake of generality, we consider the asymmetric case, where G1 =

G2 , but most of the schemes below also apply in the symmetric setting, where

G1 = G2 .

3.2 Di¬e-Hellman Assumptions

The co-CDH-Problem. Let g1 and g2 two generators of G1 and G2 respectively.

We de¬ne the co-Di¬e-Hellman value co-CDHg1 ,g2 (u), for u = g1 ∈ G1 , the

x

element v = g2 ∈ G2 .

x

The co-CDHG1 ,G2 problem can be formalized as follows: given g1 , u ∈ G1 and

g2 ∈ G2 , output v = co-CDHg1 ,g2 (u). We de¬ne the success probability of A in

breaking the co-CDHG1 ,G2 -problem as:

Succco’cdh (A) = Pr g1 ← G1 ; g2 ← G2 , x ← Zp ; v ← A(g1 , g2 , g1 ) : v = g2 .

R R R x x

G1 ,G2

Note that when G1 = G2 = G, the co-CDHG,G -problem is exactly the usual Com-

putational Di¬e-Hellman Problem in G, which can still be di¬cult. However,

the decisional version is easy, granted the pairing.

We can indeed de¬ne the co-DHG1 ,G2 -language of the quadruples (a, b, c, d) ∈

G1 — G2 — G1 — G2 , such that d = co-CDHa,b (c).

The Common co-CDH-Problem. Given two elements, it is simple to complete a

co-CDH-quadruple (g1 , g2 , u, v). However, ¬nding two such quadruples with con-

straints may not be simple. We thus de¬ne a new problem, called the Common

co-CDH-Problem, as follows: Given g, h ∈ G, and V ∈ GT , output k0 = k1 ∈ Zp ,

K0 , K1 ∈ GT and a common c ∈ G, such that:

(ghk0 , V, c, K0 ), (ghk1 , V, c, K1 ) ∈ co-DHG,GT .

382 M. Izabach`ne and D. Pointcheval

e

We de¬ne the success of A in breaking the Common-co-CDHG,ˆ-Problem as:e

⎡ ¤

g, h ∈ G; V ∈ GT ; (c, k0 , k1 , K0 , K1 ) ← A(g, h, V ) :

Succcommon-co-cdh (A) = Pr ⎣ k0 = k1 § (ghk0 , V, c, K0 ) ∈ co-DHG,GT ¦

G,ˆ

e

§(gh , V, c, K1 ) ∈ co-DHG,GT

k1

The CBDH-Problem. Di¬e-Hellman variants have been proposed in groups

equipped with pairings, and namely in the symmetric case: let g be a generator

of G. We de¬ne the Bilinear Di¬e-Hellman value of g x , g y , g z , for x, y, z ∈ Zp ,

in base g, the element V = e(g, g)xyz ∈ GT .

ˆ

The CBDHG,ˆ problem can be formalized as follows: given g, X = g x , Y =

e

g , Z = g ∈ G, output V = e(g, g)xyz . We de¬ne the success probability of A

y z

ˆ

in breaking the CBDHG,ˆ-problem as:

e

Succcbdh (A) = Pr g ← G; x, y, z ← Zp ; V ← A(g, g x , g y , g z ) : v = e(g, g)xyz .

R R

ˆ

G,ˆ

e

The DBDH-Problem. The decisional version can then be intractable too: given

g, X = g x , Y = g y , Z = g z ∈ G, and V ∈ GT , decide whether V = e(g, g)xyz , or

ˆ

not. We de¬ne the advantage of A in breaking the DBDHG,ˆ-problem as:

e

Advdbdh (A) = Pr g ← G; x, y, z ← Zp ; V = e(g, g)xyz : 1 ← A(g, g x , g y , g z , V )

R R

ˆ

G,ˆ

e

R R R

’ Pr g ← G; x, y, z ← Zp ; V ← GT : 1 ← A(g, g x , g y , g z , V ) .

The Successive-Power Version. For our scheme to be semantically secure,

we will need a stronger variant of the above DBDH problem, given access to

a sequence of powers, similarly to the Strong Di¬e-Hellman problem [9]: More

2 q

precisely, given g, g x , g y , g z , and g z/x , g z/x , . . . , g z/x , as well as V , from some

V ∈ GT , where q is a parameter, decide whether V = e(g, g)xyz , or a random el-

ˆ

ement. We de¬ne the advantage of A in breaking the q-SP-DBDHG,ˆ-assumption e

as:

R R

Advq-spdbdh(A) = Pr g ← G; x, y, z ← Zp ; V z= z/x g) z/xq

e(g, xyz :

ˆ

G,ˆ

e

1 ← A(g, g , g , g , g , · · · , g

xy

,V )

R R R