Efficient Proxy Re-encryption with Private Keyword Searching in Untrusted Storage

Published Online March 2011 in MECS

Cloud computing is an important trend which is beginning to fulfill the early promise of the Internet and creating unanticipated change in computing paradigm. However, a significant barrier to the adoption of cloud computing is that data owners fear of confidential data leakage and lose of privacy in the cloud [1]. These concerns originate from the fact that cloud providers are usually operated by commercial providers which are very likely to be outside of the trusted domain of the users. Data confidentialty against cloud providers is hence frequently desired when users outsource data for storage in the cloud [2].

Our work is motivated by the following scenario. Data owners, cloud storage providers and data users are separated geographically. A data owner stores his files in an encrypted form in the untrusted cloud, and retrieves them wherever and whenever he wants. What’s more, he wants to share his files with other data users. The user sends a query for files containing certain keywords to the cloud provider. The desired requirements are: 1) The user can decrypt the files uploaded by the data owner with his private key; 2) The cloud provider can search whether the encrypted files contain some keywords; 3) The cloud provider ought to keep blind to the files content and the query keywords of the user; 4) The user could finish query and decryption with a thin client which demands computing overhead as small as possible. We call such kind of problem as “Private Searching on Encrypted Data” (PSED for short).

• A.    Related work

Proxy Re-Encryption (PRE). PRE is a cryptographic primitive, where a (potentially untrusted) proxy is given a re-encryption key ^{rk 1 → 2} that allows it to translate a message ^m encrypted under public key ^{pk 1} into a cipher texts under a public key ^{pk 2} , without being able to see anything about the encrypted messages. In [3], Ateniese et al. proposed a single-use, unidirectional, but not transparent Proxy Re-Encryption schemes based on bilinear maps.

Public key encryption with keyword search (PEKS) . In PEKS scheme, Alice creates a trapdoor with her private key and a keyword, and sends it to S. S uses a test algorithm with inputting encrypted keyword, trapdoor and user’s public key. If matches, it outputs 1 and 0 otherwise. PEKS supports that a user could search for some files containing certain keywords in untrusted storage servers, and at the same time, the servers keep blind to the privacy of file and the keyword. In [4], Boneh et al. proposed a public key encryption with keyword search scheme.

Dual receiver cryptosystem. Diament et al [5] first introduced the notion of an efficient dual receiver cryptosystem, which enables a cipher text to be decrypted by two independent receivers. The main disadvantage of the dual receiver cryptosystem is that the server needs to send an auxiliary private key to a client for decrypting a partial cipher text, which is insecure in the real environment [6].

Liu et al. [6] improved the PEKS by inspiring the idea of dual receiver cryptosystem, and proposed an efficient privacy preserving keyword search scheme. However, this scheme exists an inherent problem. It is one specific case applicable in the setting that the data owner and data user is the same one. Shao et al. [7] introduced the concept of proxy re-encryption with keyword search (PRES), in particular the concept of bidirectional PRES, against the chosen cipher text attack. Their scheme is based on the techniques for PRE in [8] and the IBE schemes in [9]. Note that the third party is trusted and this scheme improved the security level with the sacrifice of efficiency.

Note that there are further related work [10][11] and the latest work in Structured Encryption [12], which also considered the problem of private querying on encrypted data, i.e. enabling user efficiently query and retrieve the encrypted files containing specific keywords.

• B.    Our contributions

Main contributions of this paper can be summarized as follows.

• 1)    We proposed a new cryptographic primitive, Proxy Re-encryption with Private Searching (PRPS), and the new PRPS construction combines technologies from PRE, PEKS and dual receiver cryptosystem. The PRPS scheme is able to protect the data privacy and the users’ queries privacy simultaneously during the search process. And it is provably secure under the BDH assumption in random oracle model.

• 2)    The PRPS scheme enables the decrease of computing overhead for the user.

• 3)    It reduces the modification of encrypted sharing file storage when different users accessing the cloud provider.

The rest of this paper is organized as follows. Section II discusses some preliminaries. Section III provides the Proxy Re-encryption with Private Searching model and its security definition. Section IV introduces the construction for PRPS. In Section V, we analyze the PRPS scheme in terms of its security and efficiency. We conclude this paper in Section VI.

• II.    PRELIMINARIES

Let ^{G 1} and ^{G 2} be two cyclic groups of some large prime order ^q . We view ^{G 1} as an additive group and ^{G 2} as a multiplicative group.

Definition 2.1 (Bilinear Maps): We call e a bilinear map if e: G1 x G1 ^ G2 is a map with the following properties:

• 1)    Computable: given g ^, h ^G G¹ , there is a polynomial time algorithms to compute e ( g ^, h ) ^G G ².

• 2)    Bilinear: for any integers x ^, y ^{g [1,} q ] , we have e ( g ^x , g ^y ) = e ( g , g ) ^xy .

• 3)    Non-degenerate: if ^g is a generator of ^{G 1} , then ^{e ( g , g )} is a generator of ^{G 2} .

Definition 2.2 (BDH Parameter Generator): We say that a randomized algorithm ^IG is a BDH parameter generator if ^IG takes a sufficiently large security parameter K >  0 , runs in polynomial time in K , and outputs the description of two groups ^{G 1} and ^{G 2} of the same prime order ^q and the description of a bilinear map e : G i x G i ^ G 2 .

Definition 2.3 (BDH Problem): Given a random element g G G1 , as well as g ,g and g , for x, y, z G Z *              e (g, g) xyz G G, some q , compute            2 .

Definition 2.4 (BDH Assumption): If ^IG is a BDH parameter generator, the advantage Adv Ic ^{( B )} that an algorithm ^B has in solving the BDH problem is defined to be the probability that ^B outputs ^{e ( g , g} ) on inputs ^{G 1, G 2, e , g , gx , gy , gz} ,where ^{( G 1, G 2, e )} is the output of ^IG for a sufficiently large security parameter ^K , ^g is a random generator of ^{G 1} , and ^{x , y , z} are random elements of Z q . The BDH assumption is that Adv IG ^{( B )} is negligible for any efficient ^B .

• III.    PROXY RE-ENCRYPTION WITH PRIVATE SEARCHING

Definition 3.1 Proxy Re-encryption with Private Searching (PRPS) scheme consists of seven randomized polynomial time algorithms as follows:

• •    Key Generation (KG): takes a sufficiently large security parameter ^{K 1} as input, and produces a key pair ^{( Apub , Apriv )} for a data owner ^A , where A , A

pub priv are public key and private key respectively. We write KG(K 1) (A pub, Apiv) . Let K2 be a sufficiently large security parameter, we write   KG(K2) (Spub,Spriv)    for the cloud provider S , where Spub,Spriv are public/private key respectively. Let K3 be a sufficiently large . KG(K) = (U „,U . ) security parameter, we write 3     pub priv for the data user U , where Upub,Upriv are public/private key respectively.

• •    Encryption (E): this algorithm is performed by data owner A to encrypt the keyword W ⁽ i ^G Z ) and message ^m . Correspondingly, two parts, KWEnc and EMBEnc constitutes Encryption.

• 1)    KWEnc: is a public key encryption

A algorithm that takes a public key pub and a key word W (i G Z ) as inputs, and produces W ’s

• ■ . _{+ +} C_w g C„ „,    ₄ KWEnc ( A„„ ₆, W ) = C

cipher text ^{Wi    w} .We write           ^{pub i     Wi} .

• 2)    EMBEnc: is a public key encryption

algorithm that takes public keys Spub , Apub and message m∈ M as inputs, and produces m's cipher text Cm .We writeEMBEnc(Spub, Apub, m) = Cm . Re-Encryption Key Generation (RG): A data owner takes a public key Upub and private key Apriv as inputs, and produces the re-encryption keyrkA→U. We writeRG(Apriv,Upub) = rkA→U .

• •    TCompute ： User takes private key ^{U priv} and a W +                   W

keyword ^{j ( j ∈ Z )} as inputs, and produces ^j ’s

TW trapdoor Wj . We write

TCompute ( U_priv , W_j ) = T_Wj

• •    Re-Encryption(R): The cloud provider takes re- rk                C

encryption key ^{A → U} , cipher text ^m and some intermediate result ^θ as the inputs, and produces

CC cipher text m ’s re-encrypted cipher text U . We writeRe-Encryption(θ,rkA→U,Cm) =CU.

• •    Test ： The cloud provider takes re-encryption key ^{rkA → U} , an encrypted keyword ^CWi and a

TW trapdoor Wj as inputs, and produces “1” if

W=W ijor “0” otherwise. This algorithm is to

C check whether the cipher text Wi matches the

T_W trapdoor ^j

.

• •    Decryption (D): The user takes private key UC

^priv and re-encrypted cipher text ^U as inputs, and outputs the plaintext ^m .

Note. RG algorithm implies that the PRPS scheme is non-interactive, which means re-encryption keys can be generated by a data owner via the user's public key. No trusted third party or interaction is required.

We define security for the PRPS scheme in the sense of semantic security. Semantic security captures the intuition that given a cipher text, the adversary learns nothing about the corresponding plaintext, thus we also say that a semantically secure scheme is IND-CPA secure [9]. We first define semantic security for KWEnc and EMBEnc, and then give the definition of semantically secure PRPS scheme.

Definition 3.2 (Semantic Security of KWEnc): Given a public key encryption algorithm KWEnc which AΑ encrypts keywords using pub , let 1 be a polynomial time IND-CPA adversary that can adaptively ask for the trapdoor TWi for any keyword Wi ∈ W of its choice. Α1

first chooses two keywords W0 and W1 , which are not to be asked for trapdoors previously, and sends them to KWEnc. And then KWEnc picks a random element b ∈ {0,1}

1 and gives

^{Α 1}    the cipher text

C W = KWEnc ( A pub , W b ) Α

• ^{W b 1 pub b 1} . Finally, ¹ outputs a guess ^{b 1 ∈ {0,1}} for ^{b 1} . We define the advantage of ^{Α 1} in breaking KWEnc as

  Adv _{Α 1} ( k ) =

  
  

  Pr[ b 1 = b 1 ^' ] - ¹ ₂

  
  

KWEnc is semantically secure if for any polynomial time adversary ^{Α 1} , ^{Adv Α 1 ( k )} is negligible.

Definition 3.3 (Semantic Security of EMBEnc): Given a public key encryption algorithm EMBEnc which encrypts the message using ^Apub and ^Spub . Let ^{Α 2} be a polynomial time IND-CPA adversary that can adaptively ask for the cipher text for any message ^{mi ∈ M} of its choice. We use subscript ^T to denote the target user, ^x to denote the adversarial users, and ^h to denote the honest users (other than ^T ). The input marked with a ‘*’ is optional. ^{Α 2} first chooses two messages ^{m 0} and ^{m 1} , which are not to be asked for the cipher text previously, and sends them to EMBEnc. And then EMBEnc picks a random ^{b 2 ∈ {0,1}} and gives ^{Α 2} the cipher text

C_{mb 2} = EMBEnc ( A_pub , S_pub , m_{b 2}) .

Finally, ^{Α 2} outputs a guess ^{b 2 ∈ {0,1}} for ^{b 2} . That is, for

A all PPT algorithms ^k ,

Pr[( pk T , sk T ) ← KG (1 ^k ),{( pk x , sk x ) ← KG (1 ^k )},

{rkx→T← RG(pkx, skx, pkT, skT*)}, {(pkh, skh) ←KG(1k)}, {rkT→h←RG(pkT,skT,pkh,skh*)}, {rkh→T←RG(pkh,skh,pkT,skT*)}, (m0,m1,α) ←Ak(pkT,{(pkx,skx)},{pkh},{rkx→T},{rkT→h},{rkT→D}), b2←{0,1},b2' ←Ak(α,EMBEnc(pkT,mb)) : b2=b2' ]<1/2+1/poly(k)

Α

We define the advantage of 2 in breaking EMBEnc as

Adv _{Α 2}( k ) =

Pr[ b 2 = b 2^' ] - ¹ ₂

We say that EMBEnc is semantically secure if for any polynomial time adversary ^{Α 2} , ^{Adv Α 2 ( k )} is negligible.

Definition 3.4 (Semantic Security of PRPS): Given an

PRPS scheme consisting of KWEnc and EMBEnc, it takes a security parameter K as input and runs the key generation algorithm Keygen to generate the public/ private key pairs(Apub,Apriv), (Spub,Spriv) and (Upub,Upriv). Given an adversary Α consisting of two polynomial time Α ΑΑ algorithms 1 and 2 , 1 initiates attacks on KWEnc and Α2 initiates attacks on EMBEnc. We say that the PRPS Scheme is semantically secure if for any adversary

Adv ( k ) = Adv ( k ) + Adv ( k )

• ^Α    ,    ^{ΑΑ 1 Α 2}   is negligible.

• IV. CONSTRUCTION FOR PRPS

We assume that the scheme is composed of the following parties, the data owner, data users, and cloud providers. To access data files shared by the data owner, data users download data files of their interest from cloud providers and then decrypt. The users are assumed to have the only access privilege of data file reading. The cloud providers are assumed to have abundant storage capacity and computation power.

In this work, cloud providers are viewed as “ honest but curious ”, which means they follow the proposed protocol in general, but try to find out as much secret information as possible. More specifically, we assume cloud providers are more interested in file contents and user access privilege information than other secret information. Cloud providers might collude with malicious users for the purpose of harvesting file contents when it is highly beneficial. Communication channel between the data owner/users and cloud providers are assumed to be secured. Users may work independently or cooperatively. In addition, each party is preloaded with a public/private key pair and the public key can be easily obtained by other parties when necessary.

The main design goal is to help the data users achieve efficient private querying and downloading the encrypted files stored in cloud providers. The data owner won’t need to re-encrypt the files in cloud provider for different users. We also want to prevent cloud providers from being able to learn both the data file contents and user queries information.

The details of construction are as follows:

Suppose data owner A is about to store an encrypted file with keywords W1,...Wl on a cloud storage S , where l e Z . Keywords may be words in headline or stored date, and are relatively small. A encrypts the file A message using his public key pub , the cloud storage’s public key Spub . And then A encrypts keywords W1,...Wl A using his public key pub . The file deposited in the cloud storage S by the data owner A is as follows:

MSG u 2 5 = [ EMBEnc ( A pub , S pub , m ), KWEnd(. A ,.» , W),..., KWEnc ( A pub , W )] Where ^EMBEnc , ^KWEnc are public key encryption algorithms. Finally, ^A appends to the encrypted file message with all the encrypted keywords and sends ^{MSGU 2 S} to ^S .

Given a sufficiently large security parameter K ^{e Z +} , it runs ^IG to generate a prime ^q , two groups ^{G 1} and ^{G 2} of prime order q , and a bilinear map ^e ' G ^{1 x} G ¹ ^ ^{G 2} , g , h e G,  Z = e ( g , g ) e G,    ,     g ■                   G G,

• ¹    ,               ² , where ^g is a generator of ¹ .

Then it chooses two hash functions ^H 1 , ^{H 3} : ^{{ 0,1 }} ^ G ¹

log q

,

hash function 2 ' 2 ^{ ’ ^}      , and hash function

H4' G2 ^{0,1} for some n , where H 1,H2,H3 and H4 are random oracles. Finally, it picks three random elements

*

a , b , c e Z,

L

ab

c

ac q and computes g ,g and g .The plaintext space includes M e{0,1} and W e{0,1} . The cipher text

. . ,    CM = G* x{0,1} n     ,CW e G space includes M 1 and W 2

.

• Key Generation (KG): The data owner A ’s public a pub g

A key is key A priv

= a

;

b is pub g provider S ’s

with the corresponding private the user ^U ’s public/private key

^{Upriv b} respectively. The cloud

5 , = g^c public key is ^pub

.    5 . = c corresponding private key priv

.

• Encryption (E): This encryption consists of KWEnc and EMBEnc.

with the

algorithm The data

„       . .            .       .          r e Z *

owner first picks a random element ^q

.

• ^{2 , 1 i} , where ^{i 1 k} , sets the

■ . _{+ +} C_w = H ( e ( g a , H A W ) ) ^r ) cipher text ^{Wi   21 i}

.

• 2 ) EMBEnc( ^{E 2} ): To encrypt the file message ^m under data owner’s public key ^ga , cloud provider’s public key ^gc and random element ^r , it

pe{0,1} n, picks a random element         and computes u1 = h, u 2 = p e H4( e (ha, gc)r), uз = m • e(Hз(p), ga)) , and sets the cipher text Cm (u 1,u2,u3)

.

• Re-Encryption KeyGeneration (RG): Data owner

A delegates to user U by publishing the re,     rk. . = = g“br encryption key A^u 5

public key ^g .

• Tcompute: To retrieve keyword W ^{( j e} Z + ) , user

, computed with ^U ’s

the file containing computes the trapdoor

T W = h 1 ( W ) 1/ ^b   .      .                      U = = b

Wj     1 j using his/her private key priv , then sends the trapdoor to the cloud provider.

• •    Re-Encryption( R ): to change the cipher text C m = ^{( u} 1 , ^u 2 , ^u 3 )    for A into a cipher text

C u = ^{( u} 3 , ^u 4 ) for U under the re-encryption key rk., = = g abr

A^u b , it computes u 4 = e (Hз( p), rkA ^u) = e (Hз( P), gab)

.

C

The cloud provider sends ^U to the user.

Note. Since

ρ=u2⊕H4(e(ha,gc)r)=u2⊕H4(e(ga,hr)c) , the cloud provider can compute the intermediate value ρ with its private key c .

• •    Test ： To determine whether a given file contains

W keyword j , the cloud provider tests whether CWi= H2(e(rkA→U,TWj)) .

Test ( rk_{A → U} , C_W , T_W )

If so,                  ^{i j} outputs 1, and 0

otherwise.

W = W C = H ( e ( g ^a , H ( W ) ) ^r )

Note. If ^ij , since ^{Wi   21 i} , then

C W_i = H 2 ( e ( g^a , H 1 ( W j )) ^r ) = H 2 ( e ( g^abr , H 1 ( W j )^{1/ b} )) = H 2 ( e ( rk A → U , T W_j ))

• •    Decryption(D) : Given the cipher text

• ^{CU = ( u 3, u 4)}         , it computes

1 ₁ m = u /( u ) ^Upriv = u /( u ) ^{b 34     34} to recover the message

m

.

Note that:

u 3 ₌ m ⋅ e ( H 3 ( ρ ), g ^a ) ^r ₌ m ⋅ e ( H 3 ( ρ ), g ^a ) ^r ₌ m ( u 4 ) ^b ( e ( H 3 ( ρ ), g ^ab ) ^r ) ^b e ( H ³ ( ^ρ ), g ^a ) ^r

.

• V.    ANALYSIS

• A.    Security Analysis

• 1)    Privacy for Keyword

Lemma 5.1 (Privacy for Keyword) Let H1 be a random oracle from {0,1} to G1 and H2 be a random oracle from G2 to {0,1} ogq . Suppose Α1 be an IND-CPA adversary that has the advantage ε1 in breaking KWEnc. Suppose Α1 makes at most qH2 > 0 hash queries to H2 and at most qT > 0 trapdoor queries. Then there is an algorithm B1 that solves the BDH problem with the ε=2ε/{e⋅q ⋅(1+q)} advantage at least 11     H2     T, and a running timeO(time(Α1)).

Proof. The proof is similar to Lemma 4.2 in [6].

Privacy for Keyword guarantees the user's query privacy, namely, the cloud provider learns nothing about what the user’s querying for in this process. In our scheme, the file is encrypted with the data owner’s public key before its storage in the untrusted cloud. A user sends a trapdoor with inputting encrypted keyword to query for a file which including the encrypted keyword. The cloud provider will have no knowledge of the file’s keyword, only if it obtains the private key of the data owner.

• 2)    Privacy for Message

Our security definition quantifies over all encryption algorithms; in this case, we have two algorithms EMBEnc( E2 )and Re-Encryption( R ), where an E2 cipher text takes the formu3=m⋅e(H3(ρ),g). This construction is equivalent to R cipher text of the form u4= e(H3(ρ),g). Now, it is clear if the E2 cipher text of the form u3=m⋅e(H3(ρ),g) is secure, then so is the R version, since E2 cipher texts reveal more information. Thus, it suffices to argue the security of the E2 cipher texts only.

Next, we show that EMBEnc is a semantically secure public key encryption if the BDH assumption holds. It is worth noticing that the outer attackers couldn’t calculate ^ρ if the BDH assumption holds. Without loss of generality, we suppose that an IND-CPA adversary ^{Α 2} has already known ^ρ and could issue ^{H 3} queries at any time.

Lemma 5.2 (Privacy for Message) Let H3 be a random oracle from {0,1}* to G1 and H4 be a random oracle from G2 to {0,1}n . Let Α2 be an IND-CPA adversary that has εΑ the advantage 2 against EMBEnc. Suppose 2 makes qH3 > 0 hash function queries to H3 and qR > 0 queries to Request . Then there is an algorithm B2 that solves the BDH problem with the advantage at leastε2= 2ε2/qH3qR

O ( time ( Α ))

and a running time 2 .

Proof . See Appendix A.

• 3)    Security for PRPS

We will study the security for our PRPS scheme according to Definition 3.4. The following theorem shows that PRPS is semantically secure if the BDH problem is hard.

Theorem 5.1 (Security for PRPS). Suppose the hash functions ^{H 1, H 2, H 3} and ^{H 4} are random oracles. Let ^Α be an IND-CPA adversary consisting of two polynomial time algorithms ^{Α 1} and ^{Α 2} . Let ^{Α 1} be an IND-CPA adversary that has the advantage ^{ε 1} in breaking KWEnc. Suppose ^{Α 1} makes ^{qT >  0} trapdoor queries and ^{qH 2 >  0} hash queries to ^{H 2} . Let ^{Α 2} be an IND-CPA adversary that has the advantage ^{ε 2} against EMBEnc. Suppose ^{Α 2} makes ^{qH 3 >  0} hash function queries to ^{H 3} and ^{qR >  0} queries to ^Request . Let ^Α be an IND-CPA adversary that has the advantage ^{ε = ε 1 + ε 2} against the PRPS scheme. Then there is an algorithm ^Β that solves the BDH problem with the advantage at least: Adv ≥ 2 ε /{ e ⋅ q ⋅ (1 + q )} + 2 ε / q q

^{Β 1 H 2 T 2 H 3 R} That means the PRPS scheme is semantically secure under the BDH problem. Here ^{e ≈ 2.71} is the base of the natural logarithm. The running time of ^Β is ^{O ( time ( Α ))}.

Proof. PRPS includes two public key encryption algorithms, i.e. EMBEnc and KWEnc. Therefore, the proof follows directly from Lemma 5.1 and Lemma 5.2.

• B.    Efficiency Analysis

This section evaluates the efficiency of the PRPS scheme in terms of the computation overhead introduced by each operation. We use computation time to denote the computation overhead of the algorithm operated by different roles (for example, the data owner, the user). Encryption (KWEnc, EMBEnc) and Re-Encryption Key Generation are operated by the data owner; ReEncryption and Test are operated by the cloud provider and the user’s operation are Tcompute and Decryption.

Suppose the runtime of exponent arithmetic (EXP) TT is e , the runtime of hash arithmetic (Hash) is h and the runtime of arithmetic of bilinear pairings (Pairing) is Tb .

TABLE I.

C omputation efficiency of PRPS

		EXP	Hash	Pairing	Total
Data owner	Encryption	5 T e	4 T h	3 T b	6 T e + 4 T h + 3 T b
	Re-Encryption KeyGeneration	T e
Cloud Provid er	Re-Encryption	2 T e	2 T h	2 T b	2 T + 3 T + 3 T ehb
	Test		Th	Tb
User	Tcompute		T h		T e + T h
	Decryption	T e

The comparison in the runtimes for the cryptographic operations in PRPS scheme is given in TABLE I. These results indicate that the runtimes of hash arithmetic and exponent arithmetic operated by a user are much less than the ones of cloud provider’s and data owner’s operations. The scheme transfers most computation cost from the user to the cloud provider decrease the computation overhead and enhance the efficiency of the user. That makes sense to the application of cloud computing with thin clients.

Note. In our scheme, a data owner takes his own private key, the user's public key and a random element as the inputs, and produces re-encryption r=(gb)ar=gabr key A→U             . Thus, there is no need to deliver the user’s private key to the data owner or interact with the third party for the re-encryption key, which implies that our PRPS scheme is non-interactive.

• VI.    CONCLUSIONS

In this paper, we propose an efficient proxy reencryption with private searching (PRPS) scheme in the untrusted cloud. We exploit proxy re-encryption and uniquely combining it with techniques of public key encryption with keyword search and dual receiver cryptosystem. PRPS allows users and data owners to query and access files storage in untrusted cloud provider, while maintaining query privacy and data privacy. It allows user to decrypt the files efficiently. The PRPS scheme is proven semantically secure in the random oracle model. We indicate that the challenging “Private Searching on Encrypted Data” problem is of independent interest and deserved further study.

A PPENDIX A PROOF OF LEMMA 5.2

Proof. ^{B 2} Is given ^{ρ ∈ {0,1} n} , ^{µ 0 = g , µ 1 = g 2, µ 2 = g 2 , µ 3 = g 2 ∈ G 1}, where ^{α 2, β 2, γ 2} are random

Z*                          D=(    )α2β2γ2 G elements in q . Its goal is to output 2,           2.

• ^{Β 2} finds ^{D 2} by interacting with ^{Α 2} as follows:

Keygen: ^{Β 2} sends ^{( µ 0, µ 1)} as the public key to ^{Α 2} .

H - Queries Β

• ³            :    ² maintains a list of tuples

called H3 - List, in which each entry is a tuple of the form ( ρj , fj )                                       Α form . The list is initially empty. When 2 issues a query toH3 , Β2 checks if ρi is already on H3 - List in the form of ( ρj , fj . If so Β2 responds to Α2 with H3(ρi)= fi. Otherwise, Β2 picks a random d∈ Zq , computes fi =µ2.g=g2 .g ∈G1 adds the tuple < ρi, fi ) to H3 - List, and responds to Α2 with H3(ρi)= fi.

H - Queries Β

• ⁴            :    ² maintains a list of tuples

called H4 - List, in which each entry is a tuple of the form rj , j . The list is initially empty. When Α2 issues a query to H4 , Β2 checks if ri is already on H4 - List in the form of ( ri,li . If so, Β2 responds to Α2 with H4(ri) = li. Otherwise, Β2 picks a random string li ∈{0,1} , adds the tuple ri,li to H4 -List, and responds to Α2 with H4(ri)=li.

^Request : Next, for ^{i = 1} up to ^{poly ( k )}, ^{A 2} can request:

• a.    ^{rkx → T} , a delegation to ^T from a party corrupted by ^{A 2} . ^{A 2} can generate these delegations for as many corrupted users as it likes internally by running ( pk , sk ) ← KG (1 ^k )                    rk    = ( g ^{α 2} ) ^skx

^{x , x}            and computing    ^{x → T}          .

• b.    ^{rkT → h} , a delegation from ^T to an honest party ^h . The simulator randomly selects one values ^{rh ← Ζ q} , sets rk_{T → h} = ( µ ₀) ^h = g ^h And pk_h = g ^h , and sends ( pk_h , rk_{T → h} ) to ^{A 2} . The corresponding secret key is ^{skh = rh} .

• c.    ^{rkh → T} , a delegation to ^T from an honest party ^h .

The simulator uses either the recorded value rh from the previous step if the honest party already exists, or generates fresh random values for a new party, and rk = (gα2 )rh computes h→T .

Challenge. ^{Α 2} outputs two messages ^{m 0} and ^{m 1} on which it wishes to be challenged. ^{Β 2} randomly picks ^{b 2 ∈ {0,1}} and a random string ^{S 2 ∈ {0,1}} , and gives the cipher text ^{C 2 = ( µ 3, S 2)}to ^{Α 2} . Note that the decryption of the cipher text is:

µ 3 = m ⋅ ( e ( H 3 ( ρ ), µ 1 ) ^{γ 2} ) = m ⋅ ( e ( H 3 ( ρ ), g ^{α 2} ) ^{γ 2} ) = m ⋅ ( e ( g ^{β 2} . g ^d , g ^{α 2} ) ^{γ 2} ) = m ⋅ ( e ( g , g ) ^{α 2 γ 2( β 2 + d )} )

Hence, ^{C 2} is a valid cipher text for ^{mb 2} as required.

Guess: ^{Α 2} outputs its guess ^{b 2 ∈ {0,1}} for ^{b 2} , ^{Β 2} picks a random pair ^{ρ j , fj} from ^{H 3 - List} and outputs ^fj as the solution to the given instance of BDH.

Let ^{Q 2} be the event that ^{Α 2} issues a query for ^f .

Pr[ Q ] ≥ 2 ε

From proof of Lemma 5.1, we know that 22.

That means Α2 will issue a query for f with the probability at least 2ε2 . Β2 will choose the correct pair with the probability at least 1/qH3 and succeed in Request with the probability at least 1/ qR , thus Β2 produces the correct answer with the probability at least ε2= 2ε2/qH3 qR as required. If Α2 has the advantage ε2 against EMBEnc, then Β2 succeeds with probability ε2= 2ε2/qH3qR .This contradicts the BDH assumption.

• [9]    D. Boneh and M. Franklin. “Identity Based Encryption from the Weil Pairing,” SIAM J. of Computing , 32 (3): 586-615, 2003.

• [10]    D. Song, D. Wagner, A. Perrig, “Practical techniques for searching on encrypted data”. IEEE Symp. On Research in Security and Privacy 2000 , IEEE. 2000. pp.44–55

• [11]    Y. Chang, M. Mitzenmacher, “Privacy preserving keyword searches on remote encrypted data”. Proceedings of ACNS2005 . Lecture Notes in Computer Science 3531, Springer-Verlag . 2005. pp.442–455.

• [12]    Melissa Chase, Seny Kamara, “Structured Encryption and Controlled Disclosure”. Proceedings of ASIACRYPT 2010, Lecture Notes in Computer Science 6477, Springer-Verlag . 2010. pp. 577–594.

  
  
  

Xi Chen is currently pursuing the M.S degree with Department of Information and Communication Engineering in Beijing Jiaotong University. Her research interests include cryptographic protocols and information security.

Acknowledgment

This work is partially supported by National High Technology Research and Development Program of China (863 Program) under Grant No. 2009AA01Z423 and the Fundamental Research Funds for the Central Universities under Grant No. 2009JBM004.