based non-malleability. In this section, we describe our scheme, and show that

it achieves all the security properties: semantic security, anonymity, KwrtA-

anonymity and identity-based non-malleability. For the sake of simplicity, we use

a symmetric pairing:

SetupIBK . The setup algorithm chooses two random generators g, h ∈ G, and a

random exponent ω ∈ Zp . It keeps this exponent as the master key MK = ω.

The corresponding system parameters are: PK = (g, g1 = g ω , h). It de¬nes

the identity-function: F (ID) = g1 · g ID = g ω+ID .

Note that, as above, the public parameters consist of independent elements

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

ExtractIBK (MK, ID). To issue a private key for identity ID, the key extraction

authority computes the private key, uskID = h1/(ω+ID) .

EncapsIBK (PK, ID). In order to generate an ephemeral key with an identity ID,

the algorithm chooses a random exponent r ∈ Zp , and creates the ciphertext

as: c = F (ID)r , that corresponds to the key K = e(g, h)r .

ˆ

DecapsIBK (uskID , c). The decryption algorithm extracts the ephemeral key K

from a ciphertext c by computing: K = e(uskID , c).

ˆ

Correctness. Let us check the decryption process:

K = e(uskID , c) = e(h1/(ω+ID) , g r(ω+ID) ) = e(h, g)r .

ˆ ˆ ˆ

Semantic Security. It is worth to precise that we do not require to be able

to simulate any oracle for making use of IB-KEM schemes in the next section.

The weak semantic security will be enough:

Theorem 3. The weak semantic security of our scheme (under selective-ID,

chosen-plaintext and no-identity attacks) relies on the DBDHG,ˆ-problem, in the

e

standard model.

Proof. Given u, A = ua , B = ub , C = uc , and V ∈ GT the input to the DBDHG,ˆ-

e

—

Problem, and the target identity ID , we set g = A = u , h = C = u = g ,

a c c/a

— —

g1 = ut · A’ID = ut’aID , and c = B. This implicitly de¬nes MK = t/a ’ ID— , for

— — —

a randomly chosen t ← Zp . Therefore, FPK (ID— ) = g1 g ID = ut ·A’ID ·AID = ut ,

R

and the randomness r of the challenge ciphertext c = FPK (ID— )r = utr = ub = B

is r = b/t. The corresponding encapsulated key should thus be

K = e(h, g)r = e(uc , ua )b/t = e(u, u)abc/t .

ˆ ˆ ˆ

386 M. Izabach`ne and D. Pointcheval

e

By letting (V 1/t , c) be the output of the challenger, an adversary able to break

the semantic security (without Extract-queries) helps us to decide whether V is

the Bilinear Di¬e-Hellman value or not.

In order to show the usual semantic security (under full-ID, but chosen-plaintext

attacks), we have to be able to simulate the Extract-oracle, which thus requires

additional inputs. But ¬rst, we modify a little bit the scheme, by using H(ID),

instead of ID in the above description, where H is a random oracle [5] onto Zp .

Theorem 4. The semantic security of our scheme (by using H(ID), instead

of ID) under full-ID and chosen-plaintext (no Decaps queries) relies on the

successive-power version, in the random oracle model.

i

Proof. Given u, A = ua , B = ub , C = uc , Ci = C 1/a , for i = 1, . . . , q, and

V ∈ GT the input to the q-SP-DBDHG,ˆ-problem, we ¬rst compute {Vi =

e

bc/ai

}i=0...q , since V0 = e(B, C), and Vi = e(B, Ci ), for i = 1, . . . , q. Then,

e(u, u)

ˆ ˆ ˆ

— R

we set g = A = ua and g1 = ut · A’x , for randomly chosen t, x— ← Zp . This im-

R

plicitly de¬nes MK = t/a’x— . We also choose random elements x1 , . . . , xq ← Z— ,

p

and set P (X) = (tX + xi ), a polynomial of degree q, where the number of

random oracle queries is q + 1. We then set h = C P (1/a) = g cP (1/a) , which can

be easily computed granted C, C1 , . . . , Cq .

First, all the random oracle queries will be answered by an x— + xi , or x— (for

a unique randomly chosen query): we hope to assign x— to H(ID— ), the target

identity, which happens with probability 1/q. Let us assume this situation:

— — —

“ By de¬nition, as above, FPK (ID— ) = g1 g H(ID ) = ut · A’x · Ax = ut ;

“ For all the other identities, H(IDj ) = xj , and then uskj can be computed as

— —

h1/(MK+x +xj )

= C P (1/a)/(MK+x +xj )

= C P (1/a)/(t/a+xj ) = C Pj (1/a) ,

where Pj is a polynomial of degree q ’ 1. Then uskj can be easily computed

granted C, C1 , . . . , Cq’1 . Hence the simulation of the Extract-oracle.

As above, the challenge ciphertext is set c = B = ub = FPK (ID— )r for r = b/t.

The corresponding encapsulated key should thus be

K = e(g, h)r = e(ua , ucP (1/a) )b/t = (ˆ(u, u)abc )P (1/a)/t .

ˆ ˆ e

i=q

pi X i , and then

Let us expand P (X) = i=0

i=q i=q

bc/ai’1 ·pi /t abc p0 /t p /t

— — i

abc·p0 /t

K = e(u, u)

ˆ e(u, u)

ˆ = e(u, u)

ˆ Vi’1 .

i=1 i=1

p /t

i=q

If V = e(u, u)abc , the correct key is V p0 /t — i=1 Vi’1 . In the random case,

i

ˆ

the same computation leads to a totally random key (note that p0 = xi =

pi /t

i=q

— i=1 Vi’1 , c) be the output of the challenger,

p0 /t

0 mod p). Then, by letting (V

an adversary able to break the semantic security helps us to decide whether V

is the Bilinear Di¬e-Hellman value or not. We thus break the q-SP-DBDHG,ˆ- e

problem.

New Anonymity Notions for Identity-Based Encryption 387

Anonymity. The usual anonymity notion relies on the same assumption as

the semantic security. Since the ciphertext consists of c = F (ID)r , a random

element in G, whatever the identity ID. It is thus clearly KwrtA-anonymous, in

the information-theoretical sense.

Theorem 5. Our scheme is unconditionally KwrtA-anonymous.

Idendity-based Non-Malleability. Let us consider the ciphertext c, and

its decryption with respect to IDi for i ∈ {0, 1}. In the following, ri is formally

de¬ned by c = F (IDi )ri , and Ki = e(g, h)ri . Thus, the identity-based non-

ˆ

malleability relies on the intractability of ¬nding c, {IDi , Ki }, with ID0 = ID1

such that ri = loge(g,h) (Ki ) = logF (IDi ) (c). This thus leads to a solution of the

ˆ

Common co-CDH-Problem.

Theorem 6. The identity-based non-malleability of our scheme relies on the

Common co-CDH-Problem in groups G and GT .

IBK ’ PAKE: Our Password-Authenticated Key

4

Exchange Protocol

The previous sections focused on identity-based key encapsulation mechanisms,

and new anonymity properties. We now show how a weakly semantically secure

IB-KEM, that is both KwrtA-anonymous and identity-based non-malleable, can

be used to build a password-authenticated key exchange.

4.1 Description of Our Scheme

Our new scheme is generic. It basically consists in generating the session key

using this IB-KEM, under the common password as the identity, see Figure 1.

The other party can easily recover the session key. Security notions for semantic