Generic Combination of Public Key Encryption with Keyword Search and Public Key Encryption

Rui Zhang and Hideki Imai

Research Center for Information Security (RCIS) National Institute of Advanced Industrial Science and Technology (AIST) {r-zhang,h-imai}@aist.go.jp.

Abstract. In this paper, we study the problem of secure integrating public key encryption with keyword search (PEKS) with public key data encryption (PKE). We argue the previous security model is not complete regarding keyword privacy and the previous constructions are secure only in the random oracle model. We solve these problems by ?rst de?ning a new security model, then give a generic construction which is secure in the new security model without random oracles. Our construction is based on secure PEKS and tag-KEM/DEM schemes and achieves modular design. We also give some applications and extensions for our construction. For example, instantiate our construction with proper components, we have a concrete scheme without random oracles, whose performance is even competitive to the previous schemes with random oracles.

1

Introduction

Public key encryption with key word search (PEKS) [7] is very useful to provide the functionality of “searching on encrypted data” for public key cryptosystems. For instance, it can be used to build a gateway to route an encrypted email without knowing the content. We brie?y review this mechanism here. Let (pk, sk) be Alice’s public/secret key pair. Bob encrypts his message (email body) m with a public key encryption (PKE) scheme under Alice’s public key pk and let’s call the encrypted email σ. Bob also encrypts a keyword w using PEKS, under Alice’s public key pk and let’s call the encrypted keyword τ . The resulting ciphertext c = τ ||σ will be sent to Alice’s email server. Alice is able to specify a few keywords, and upon receiving a trapdoor tw associated with a keyword w from Alice, the server can check whether τ encrypts w. Then if the keyword is “urgent”, the server sends c to Alice’s mobile phone, and if the keyword is “lunch”, the server sends c to Alice’s desktop to be read later. The security of PEKS is that the server should not know anything beyond the keyword. Readers are recommended to refer [7] and the references thereafter for details. The security requirements discussed in [7, 1] have considered semantic security of encryption of keywords against a powerful adversary that adaptively corrupts gateways. Since a PEKS scheme cannot be used alone but have to be paired with a public key encryption (PKE) scheme, we have to consider the security of the whole system rather than separate components. Hereafter we refer the integrated scheme as PEKS/PKE. Unfortunately, secure PEKS and secure PKE schemes may not remain secure when they are composed together, which was pointed out by Baek, Safavi-Naini and Susilo [3]. Basically, they gave a counterexample as follows: When an adversary observes a PEKS/PKE ciphertext τ ||σ, it can produce

another valid ciphertext τ ′ ||σ, where τ ′ is a valid tag under di?erent keyword. Querying τ ′ ||σ to a decryption oracle, the adversary obtains the plaintext m. We remark that the above attack is realistic in practice, since for most encrypted email systems, headers of an email remain even after routing, and the decryption is done without integrity check on the header. On the other hand, for keyword privacy, nothing was considered against chosen keyword/ciphertext attack before this work. Known Solutions and Their Limitations. As mentioned in [3], a trivial solution may be simply appending an authentication tag generated from a message authentication code (MAC), with a shared key between the sender and receiver. While it works, the solution destroys the asymmetric nature of public key encryption. Another possible solution is to attach a signature on the ciphertext. However, this requires the sender has a pair of veri?cation/signing keys, which is not applicable for many practical scenarios. Additionally, two solutions were given in [3], assuming that a MAC is provided by the PKE component. One is based on the Boneh-Franklin identity based encryption (IBE) [8] as a PEKS [7] with ElGamal [16] as a PKE. The other is a generic construction based on a PEKS and a PKE with a MAC. The intuition behind both constructions is borrowed from REACT [22], where a MAC is used to protect the integrity of both parts of the ciphertext. However, to prove their security, the authors of [3] have to assume the hash functions are random oracles [6] and the underlying PKE is secure against plaintext checking attack (PCA), which is inherent in all variants of REACT. These requirements may be too stringent, and it is desirable to have other solutions, better without random oracles. 1.1 Our Contributions

Formal Security Model of PEKS/PKE. Authors of [3] have given a security model on data privacy of PEKS/PKE against adaptive chosen keyword attack and chosen ciphertext attack, however, it is not clear which attack model is posed on keyword privacy. Actually, no concrete discussions were given regarding this point in [3]. Here we show an example with no keyword privacy at all when the attack model of [3] is considered. To see this, one just appends the keyword as a part of the ciphertext of data encryption scheme. It is easily veri?ed that this doesn’t violate the data privacy of the PEKS/PKE scheme, as long as the keyword is chosen independent from the encrypted message, but the scheme is not a secure PEKS/PKE scheme since it leaks the information of the keyword. It seems that keyword privacy has been assumed to remain even after compositions by [3]. We thus conclude the previous security model of PEKS/PKE is not complete regarding keyword privacy, however, we emphasize that the two concrete constructions proposed in [3] are secure. In this paper, we formalize the requirement of keyword privacy for secure PEKS/PKE schemes. Generic Construction of PEKS/PKE. Principally, the design of PEKS/PKE schemes without assuming random oracles is not new, e.g., one ?rst put together PEKS and PKE

components (each without random oracles), then applies non-interactive zero-knowledge proof of “well-formness” for this integration, but this is only theoretical and very ine?cient. When speaking of practical schemes, all known constructions have to assume random oracles. It is well-known that a scheme with a security proof in the random oracle model implies no security in the real world [11], therefore, it is desirable to build proofs without random oracles. In this paper, we present such a generic construction. Interesting Extensions. We also give some applications and extensions of the generic construction. For example, instantiating the above construction with concrete components, one obtains various PEKS/PKE schemes with many good properties. For instance, combining a PEKS scheme from the Gentry IBE [18], and the Kurosawa-Desmedt tag-KEM/DEM [20], we have a PEKS/PKE scheme secure without random oracles. The scheme is quite e?cient, which is even comparable to previous constructions with random oracles. In fact, a secure PEKS/PKE is achievable from a variety of assumptions, e.g., from the Waters IBE [28] using asymmetric pairing [10], however, our scheme from the Gentry IBE provides better e?ciency.

1.2

Related Work

Public key encryption (PKE) is an important primitive in modern cryptography which guarantees privacy of communications. The standard security notion for PKE is indistinguishability against adaptively chosen ciphertext attack (IND-CCA) [19, 21, 23, 15, 5]. While it is comparatively easy to build CCA-secure schemes assuming random oracles [6], to have CCAsecure schemes such that security reduction without random oracles is not easy. Only theoretical constructions of CCA-secure PKE schemes [21, 15, 24] were known before Cramer and Shoup gave the ?rst practical solution [14]. Another recent approach was proposed by Boneh, Canetti, Halevi and Katz [12, 9] based on identity based encryption (IBE). An IBE scheme is a public key encryption scheme where any string can be the public key of a user, say, the identity of a user. It was advocated by Shamir [25], whose original intuition was to simplify the management of public key certi?cates. It has been an open problem to construct full-?edged IBE schemes for many years until [8], when Boneh and Franklin proposed the ?rst IBE scheme based on pairings. Cocks [13] independently proposed another IBE scheme based on decisional quadratic residue problem. Public key encryption with keyword search (PEKS) was proposed in [7]. It was shown that to build a PEKS with exponential keyword space is at least as hard as build an identity based encryption (IBE) [7]. Another security notion for public key encryption is key privacy [4], which captures an adversary’s inability to know a receiver’s identity from a given ciphertext. For identity based encryption, this was studied under the name “anonymity” [1] (the precise de?nition postponed to Appendix A). Basically, public key encryption schemes with key privacy provides the functionality of PEKS, however, currently anonymous PKE schemes only provide polynomially bounded keyword space [7, 1], and one may need anonymous IBE schemes for a keyword space of exponential size.

2

Preliminary

In this section, we give some notations and de?nitions. Notations. If x is a string, let |x| denotes its length, while if S is a set then |S| denotes its size. If S is a set then s ← S denotes the operation of picking an element s of S uniformly at random. We write z ← A(x, y, . . .) to indicate that A is an algorithm with inputs (x, y, . . .) and an output z. Denote x||y as the string concatenation of x and y. If k ∈ N, a function f (k) is negligible if ? k0 ∈ N, ? k > k0 , f (k) < 1/kc , where c > 0 is a constant. 2.1 Public Key Encryption

A public key encryption scheme consists of three algorithms PKE = (PKEkg, PKEenc, PKEdec). PKEkg: a randomized algorithm, taking a security parameter k as input, generates a public key pk and a corresponding secret key sk, denoted as (pk, sk) ← PKEkg(1k ). PKEenc: a possibly randomized algorithm, taking a public key pk, and a plaintext m taken from the message space as input, with internal coin ?ipping, outputs a ciphertext c, denoted as c ← PKEenc(pk, m). PKEdec: a deterministic algorithm, taking a secret key sk and a ciphertext c as input, outputs the corresponding m, or “⊥” (indicating invalid ciphertext), denoted as m ← PKEdec(sk, c). We require a PKE scheme should satisfy the standard correctness requirement, namely for all (pk, sk) ← PKEkg(1k ) and all m, PKEdec(sk, PKEenc(pk, m)) = m. Data Privacy. We say a public key encryption scheme is (?, q, T )-IND-CCA secure, if the advantage of any adversary A with at most q queries to a decryption oracle DO, is at most ? within time T in the following experiment. Advind-cca (k) = |Pr[(pk, sk) ← PKEkg(1k ); (m0 , m1 , s) ← ADO (pk); PKE,A b ← {0, 1}; c? ← PKEenc(pk, mb ); b′ ← ADO (c? , s) : b′ = b] ? 1/2| where DO returns the corresponding decryption result on a query on ciphertext c, whereas A is forbidden to query c? to DO. We say a PKE scheme is IND-CCA-secure, if for polynomially bounded q and T , ? is negligible. 2.2 Tag-KEM/DEM

Shoup introduced key encapsulation mechanism (KEM) and data encapsulation mechanism (DEM) [27], to deal with e?cient hybrid encryption. Tag-KEM/DEM is a form of KEM which also takes as input a tag, which was introduced in [2]. A tag-KEM is a generalization of KEM/DEM, and together with a passively secure DEM, it can be easily be extended to threshold settings.

Tag-KEM. Our de?nition of tag-KEM runs parallel with [2]. A tag-KEM consists of four algorithms TK = (TKkg, TKkey, TKenc, TKdec). TKkg: a randomized algorithm, taking a security parameter k as input, generates a public key pk and a secret key sk, denoted as (pk, sk) ← TKkg(1k ). TKkey: a randomized algorithm, taking a public key pk as input, outputs a random session key dk ∈ KD , where KD is a key space, and internal state information η, denoted as (dk, η) ← TKkey(pk). TKenc: a possible randomized algorithm, taking the internal state η and a tag λ as input, encrypts dk (embedded in η) into ψ, denoted as ψ ← TKenc(η, λ). TKdec: a deterministic algorithm, taking a secret key sk, a ciphertext ψ and a tag λ as input, recovers dk from ψ and λ, denoted as dk ← TKdec(sk, ψ, λ). We require TKdec(ψ, λ) = dk must hold for any sk, dk, ψ and λ, associated by the above three algorithms. The algorithm outputs “⊥” when encountering an error. Additionally, we require that given a public key pk, a tag λ, and an internal state η for the encryption algorithm TKenc, the session key dk of a tag-KEM should be uniquely decided. We call this property uniqueness of tag-KEM/DEM. Security Notion. We de?ne the security of tag-KEM as indistinguishability against adaptive chosen ciphertext attack (IND-TK-CCA). We say a tag-KEM scheme is (?, q, T )-IND-TKCCA secure, if the advantage of any adversary A with at most q queries to a decryption oracle DO, is at most ? within time T in the following experiment.

Advind-tk-cca (k) = |Pr[(pk, sk) ← TKkg(1k ); b ← {0, 1}; TK,A dk0 ← KD ; (η, dk1 ) ← TKkey(pk); (λ? , s) ← ADO (pk, dkb ); ψ ? ← TKenc(η, λ? ); b′ ← ADO (ψ ? , s) : b′ = b] ? 1/2| where DO returns corresponding dk on input (ψ, λ), and A cannot query (ψ ? , λ? ) to DO. We say a tag-KEM is IND-TK-CCA-secure, if for polynomially bounded q and T , ? is negligible. DEM. A DEM consists of two deterministic algorithms, DEM = (DEMenc, DEMdec), which is associated with a key space and a plaintext space de?ned by a security parameter k. DEMenc: taking a symmetric key dk ∈ KD , where KD is de?ned by k and a plaintext m ∈ {0, 1}? as input, outputs a ciphertext χ, denoted as χ ← DEMenc(dk, m). DEMdec: taking a symmetric key dk ∈ KD and a ciphertext χ as input, outputs a plaintext m, denoted as m ← DEMdec(dk, χ). We require that for all m and all dk, DEMdec(dk, DEMenc(dk, m)) = m.

Semantic Security. We only require passive security for DEM. We say a DEM scheme is (?, T )-semantically secure, if the advantage of any adversary A, is at most ? within time T in the following experiment.

k Advss DEM,A (k) = |Pr[b ← {0, 1}; dk ← KD ; (m0 , m1 , s) ← A(1 );

χ ← DEMenc(dk, mb ); b′ ← A(χ, s) : b′ = b] ? 1/2| We say a DEM scheme is (?, T )-semantically secure, if for polynomially bounded T , ? is negligible. 2.3 PEKS

A public key encryption with keyword search (PEKS) scheme [7, 1] consists of four algorithms PEKS = (PEKSkg, PEKSenc, PEKStd, PEKStest). PEKSkg: a randomized algorithm, taking a security parameter k as input, the probabilistic key generation algorithm generates a public key pk and a secret key sk, denoted as (pk, sk) ← PEKSkg(1k ). PEKSenc: a possibly randomized algorithm, taking a public key pk and a keyword w as input, computes a ciphertext τ , denoted as τ ← PEKSenc(pk, w). PEKStd: a possibly randomized algorithm, taking a secret key sk and a keyword w as input, computes a trapdoor tw , denoted as tw ← PEKStd(sk, tw ). PEKStest: a deterministic algorithm, taking a trapdoor tw and a ciphertext τ as input, tests whether c encrypts w and outputs a bit b, with 1 meaning “yes” and 0 meaning “no”, denoted as b ← PEKStest(tw , τ ). Here we assume there is only one receiver (one public key) in the system, and it is straightforward to extend the above de?nitions to multi-user settings. Consistency. Several ?avors of consistency were discussed in [1], and we only de?ne computational consistency here, since this notion su?ces for most practical applications. A PEKS scheme is said to be computationally consistent, if the advantage is negligible for all computationally bounded adversary A in the following experiment. Advpeks-consist (k) = Pr[(pk, sk) ← PEKSkg(1k ); (w, w′ ) ← A(pk); PEKS,A tw′ ← PEKStd(sk, w′ ); τ ? ← PEKSenc(pk, w) : PEKStest(tw′ , c? ) = 1] Keyword Privacy. We de?ne indistinguishability of keywords against adaptive chosen keywords attack (IK-CKA), as considered in [7, 1]. We say a PEKS scheme is (?, q, T )-IK-CKA secure, if the advantage of any adversary A with at most q queries to a trapdoor generation oracle T O, is at most ? within time T in the following experiment.

AdvPEKS,A (k) = |Pr[(pk, sk) ← PEKSkg(1k ); (w0 , w1 , s) ← AT O (pk); b ← {0, 1}; τ ? ← PEKSenc(pk, wb ); b′ ← AT O (τ ? , s) : b′ = b] ? 1/2| where T O is a trapdoor oracle, returns the corresponding trapdoor tw upon a query on keyword w, whereas A cannot query w0 or w1 to T O. A PEKS scheme is said to be IK-CKAsecure, if for polynomially bounded q and T , ? is negligible. 2.4 Bilinear Groups

ik-cka/cca

We review some facts about bilinear groups for future use. Let G1 and GT be two multiplicative cyclic groups of prime order p and g be a generator of G1 . A bilinear map e : G1 × G1 → GT satis?es the following properties: (i) Bilinearity: For all x, y ∈ G1 and a, b ∈ Z, e(xa , y b ) = e(x, y)ab . (ii) Non-degeneracy: e(g, g) = 1. (iii) Computability: There is an e?cient algorithm to compute e(x, y) for any x, y ∈ G1 .

3

Our Model of PEKS/PKE

In this section, we give the syntax and security de?nitions for PEKS/PKE schemes. The advantage of our model is that we have notational convenience to de?ne keyword privacy and data privacy. 3.1 PEKS/PKE

We focus on the integration of PEKS/PKE. A PEKS/PKE scheme consists of ?ve algorithms PEKS/PKE = (Kg, Enc, Dec, Td, Test). Kg: a randomized algorithm, taking a security parameter k as input, generates a public key pk and a secret key sk, denoted as (pk, sk) ← Kg(1k ). Enc: a possibly randomized algorithm, taking a public key pk, a keyword w and a plaintext m as input, outputs a PEKS/PKE ciphertext c, denoted as c ← Enc(pk, w, m). Dec: a deterministic algorithm, taking a secret key sk and a PEKS/PKE ciphertext c, outputs the decryption result m (or “⊥” if c is invalid). We denote this as m ← Dec(sk, c). Td: a possibly randomized algorithm, taking a secret key sk and a keyword w as input, computes a trapdoor tw for keyword w, denoted as tw ← Td(sk, w). Test: a deterministic algorithm, tests whether a given PEKS/PKE ciphertext c encrypts keyword w, and outputs a bit b, with 1 meaning “yes” and 0 meaning “no”, denoted as b ← Test(tw , c). Our model simpli?es the one in [3]. In the encryption algorithm Enc, we don’t explicitly require a tag in the ciphertext, since otherwise the security de?nition should additionally consider the tag. We remark the model is general enough because the tag can be regarded as a part of the ciphertext.

Consistency. A PEKS/PKE scheme is said to be computationally consistent, if the advantage is negligible for all computationally bounded adversary A in the following experiment. AdvPEKS/PKE,A (k) = Pr[(pk, sk) ← Kg(1k ); (w, w′ , m) ← A(pk); tw′ ← Td(sk, w′ ); c? ← Enc(pk, m, w) : Test(tw′ , c? ) = 1] 3.2 Security Notions

peks/pke-consist

We consider two security requirements, keyword privacy, namely, indistinguishability of keywords against adaptive chosen keyword attack and chosen ciphertext attack (IK-CKA/CCA), and data privacy, namely, indistinguishability of ciphertexts against adaptive chosen keyword attack and chosen ciphertext attack (IND-CKA/CCA). Note that in a PEKS/PKE scheme, PEKS and PKE are both regarded as components of the whole system. Principally, the adversary is given two oracles, a trapdoor generation oracle T O, that on a keyword w, generates the corresponding trapdoor tw and a decryption oracle that on a ciphertext c, returns the corresponding plaintext m. Keyword Privacy. We say a PEKS/PKE scheme is (?, qt , qd , T )-IK-CKA/CCA secure, if the advantage of any adversary A with at most qt queries to a trapdoor generation oracle T O, at most qd queries to a decryption oracle DO, is at most ? within time T in the following experiment. AdvPEKS/PKE,A (k) = |Pr[(pk, sk) ← Kg(1k ); (w0 , w1 , m, s) ← AT O,DO (pk); b ← {0, 1}; c? ← Enc(pk, m, wb ); b′ ← AT O,DO (c? , s) : b′ = b] ? 1/2| where T O is a trapdoor oracle, upon a query on keyword w returns the corresponding trapdoor tw , and DO is a decryption oracle, upon a query on ciphertext c returns the corresponding plaintext, whereas A cannot query w0 or w1 to T O. We say a PEKS/PKE is IK-CKA/CCA-secure, if for polynomially bounded qt , qd and T , ? is negligible. Data Privacy. We say a PEKS/PKE scheme is (?, qt , qd , T )-IK-CKA/CCA secure, if the advantage of any adversary A with at most qt queries to a trapdoor generation oracle T O, at most qd queries to a decryption oracle DO, is at most ? within time T in the following experiment. AdvPEKS/PKE,A (k) = |Pr[(pk, sk) ← Kg(1k ); (w, m0 , m1 , s) ← AT O,DO (pk); b ← {0, 1}; c? ← Enc(pk, w, mb ); b′ ← AT O,DO (c? , s) : b′ = b] ? 1/2| where T O is a trapdoor oracle, upon a query on keyword w returns the corresponding trapdoor tw , and DO is a decryption oracle, upon a query on ciphertext c returns the corresponding plaintext, whereas A cannot query c? to DO. We say a PEKS/PKE is IK-CKA/CCA-secure, if for polynomially bounded qt , qd and T , ? is negligible.

ind-cka/cca ik-cka/cca

4

A Generic Construction of Secure PEKS/PKE

We need two ingredients for our generic construction, one is an IK-CKA secure PEKS scheme, and the other is an IND-TK-CCA secure tag-KEM/DEM. The main idea is to regard the ciphertext of PEKS as a proportion of the tag for tag-KEM/DEM. The tag-KEM/DEM framework covers almost all the known PEK schemes (see [2] for details), and can be built ?exibly from a variety of assumptions. Since a tag is a natural component for a tag-KEM/DEM scheme, the structures of both parts persist. Another advantage of our methodology is that a tag-KEM/DEM can be easily extended to threshold settings, since the DEM only require passive security. We give our construction in Figure 1.

Kg(1k ) Dec(sk, c) sk = (sk1 , sk2 ); (pk1 , sk1 ) ← PEKSkg(1k ); c = (τ, ψ, χ); (pk2 , sk2 ) ← TKkg(1k ); dk ← TKdec(sk2 , ψ, τ ||χ); pk = (pk1 , pk2 ); m ← DEMdec(dk, χ); sk = (sk1 , sk2 ); return m; return (pk, sk); Td(sk, w) Enc(pk, w, m) sk = (sk1 , sk2 ); pk = (pk1 , pk2 ); tw ← PEKStd(sk1 , w); τ ← PEKSenc(pk1 , w); return tw ; (dk, η) ← TKkey(pk2 ); χ ← DEMenc(dk, m); Test(tw , c) λ ← (τ ||χ); c = (τ, ψ, χ); ψ ← TKenc(η, λ); b ← PEKStest(tw , τ ); c ← (τ, ψ, χ); return b; return c; For each algorithm of PEKS/PKE, we require it should terminate and return “⊥” (denoting “abnormal termination”), if any of its sub-algorithms terminates abnormally. Fig. 1. Generic Construction of PEKS/PKE

It is easily veri?ed that if both the PEKS and PKE used in the construction are consistent, the resulting PEKS/PKE is consistent. We focus on the keyword privacy and data privacy of the construction. Theorem 1. The construction of PEKS/PKS shown in Figure 1 is IK-CKA/CCA-secure and IND-CKA/CCA secure, provided that the underlying PEKS scheme is IK-CKA-secure, the tagKEM scheme is IK-TK-CCA-secure and the DEM scheme is semantically secure. Intuitions. First, notice that a PEKS scheme aims at providing keywords privacy, while “naturally”, ciphertext χ of the tag-KEM/DEM will not leak information of the keywords. By uniqueness property of tag-KEM, ψ is determined once the public key pk2 , the tag λ = (ψ||χ) and internal state η of the tag-KEM are determined, and will be independent from a keyword w if τ doesn’t leak information on w. Moreover, because dk only depends on pk2 and internal random coin-?ipping of TKkey, and the algorithm DEMenc is deterministic, we have χ is also

independent from w. Finally, we conclude, if τ doesn’t leak information on w, neither will ψ and χ. On the other hand, from our construction, τ does not depend on m, thus leaks no information on m. Additionally, taking τ as a part of the tag provides integrity guarantee also for τ , i.e., any adversary cannot gain advantage in obtaining knowledge on a plaintext m by modifying this part. Otherwise, the adversary breaks indistinguishability of session key for the tag-KEM. We elaborate the above discussions in two lemmas. Lemma 1. The construction shown in Figure 1 is (?K + ?D , qt , qd , TK + TD )-IND-CKA/CCA secure, provided that the tag-KEM scheme is (?K , qd , TK )-IK-TK-CCA-secure and the DEM scheme is (?D , TD )-semantically secure. Proof. First, notice that τ is independent from mb from the encryption algorithm. Assume there is an IND-CKA/CCA adversary A, we can build an adversary B against IND-TKCKA/CCA of tag-KEM or semantic security of DEM. A ?ips a fair coin, and runs in either of the following modes. Mode 0 (Adversary against tag-KEM/DEM): A generates a pair of public/secret keys for PEKS. Since A has the secret key, trapdoor queries are handled perfectly. Decryption queries are forwarded to A’s own decryption oracle and are also handled perfectly. For challenge, after receiving a pair of plaintext (m0 , m1 ) and a keyword w from B and dkb from its own challenger, A chooses uniformly β ← {0, 1} and computes τ = PEKSenc(pk1 , w), and computes χ ← DEMenc(dkb , mβ ), where b ← {0, 1}. A then sets λ = (τ, χ) as the tag to its challenger. After receiving its challenge ψ, A gives B the challenge c = (τ, ψ, χ). When B outputs a guess on β, A checks whether this equals to β. A outputs 1 if yes and otherwise, 0. It is easily veri?ed when dkb is the real session key, then the challenge for B is valid and A will succeed at least the probability as B. If dkb is a random session key, β is perfectly hiding from B, and B’s probability in guessing b is exactly 1/2. Summarize above discussions, we have the success probability of A is at least that of B. Mode 1 (Adversary against DEM): For setup, A generates a pair of public/secret keys for PEKS and tag-KEM. Trapdoor oracle queries and decryption oracle queries can perfectly simulated, since A has the secret keys. After receiving a pair of plaintext (m0 , m1 ) and a keyword w from B, A outputs (m0 , m1 ) to its challenger. After obtains a challenge χ? from its challenger, A computes a ciphertext τ of PEKS and a ciphertext ψ with some random dk ∈ KD from a tag λ = (τ ||ψ). After B stops and outputs a guess, A also outputs the same bit. Since neither τ or ψ contains information on b, B can only gain advantage by inferring b from χ. One case to mention is that if B is able to distinguish ψ is not a valid ciphertext, then the result of B cannot be utilized and A should abort. However, in this case, we can construct an attack against the tag-KEM. However, according to our assumption, this happens at most ?K . We then have in this case A’s success probability breaking the DEM is at least that of B plus ?K . Summarizing the above two cases, we see the advantage of A is upper-bounded by ?K +?D and the queries and the running time of A are exactly the same as the claim. ? ?

Lemma 2. The construction shown in Figure 1 is (?P , qt , qd , TP )-IK-CKA/CCA-secure, provided that the PEKS scheme is (?P , qt , TP )-IK-CKA-secure. Proof Sketch. The proof for the lemma is quite simple and we only give the sketch. From the algorithms shown in Figure 1, only τ depends on a keyword w, since the tag-KEM/DEM does not even take w as an input. a PEKS adversary A generates the public/secret keys (pk2 , pk2 ) for the tag-KEM/DEM scheme and sets the public key as pk = (pk1 , pk2 ), where pk1 is the public key of its target PEKS scheme. Since A knows the the secret key of the tag-KEM scheme, all decryption queries from a PEKS/PKE adversary B can be answered perfectly. For B’s challenge query, A forwards (w0 , w1 ) to its own trapdoor oracle and extracts τ ? from its challenge as the challenge for B, it is easy to verify that τ ? is a valid challenge for B. Then A’s success probability is exactly the same as B. This proves our claim. ? ? Theorem 1 follows Lemma 1 and Lemma 2 naturally.

5

Applications and Extensions

In this section, we give some possible extensions of our generic construction. In particular, we show a concrete PEKS/PKE scheme, whose security can be proven without random oracles. 5.1 A Concrete Instantiation without Random Oracles

We instantiate our generic construction with an anonymous IBE by Gentry [18], and the Kurosawa-Desmedt tag-KEM/DEM [20]. The resulting PEKS/PKE is secure without random oracles. The scheme is given in Figure 2. The notion of anonymous IBE is reviewed in Appendix A. The consistency condition is easy veri?ed to be met since it is a straightforward instantiation of BDOP construction of PEKS (based Gentry IBE) and a secure tag-KEM/DEM scheme. Theorem 2. The PEKS/PKE scheme shown in Figure 2 is IND-IK-CKA/CCA-secure, provided that the Kurosawa-Desmedt tag-KEM/DEM is secure and the Gentry IBE is anonymous. The above proof is easily derived from Theorem 1 and known results [2, 18]. Performance. Though our scheme relies on the DADHE assumption that seems strong, however, the scheme is quite e?cient in of key size and computation cost. Note that the previous schemes have to adopt a large key size to compensate security loss due to loose security reductions. Moreover, our scheme needs no Map-to-Point computations [8], and it can be further optimized with a trick mentioned in [17] and pre-computations. Consider all these and the fact that our scheme is without random oracles, we conclude our scheme is e?cient. PEKS/PKE without MACs. Our instantiation of tag-KEM/DEM is based on KurosawaDesmedt, where a MAC is inevitable. One can use other tag-KEM schemes, e.g., CramerShoup tag-KEM [14, 2], or OAEP+ [26, 2], such that the MAC is not explicitly needed.

Kg(1k ) g, h ← G1 ; z ← e(g1 , g2 ); α ← Zp ; g1 ← g α ; pk1 ← (g, g1 , h); sk1 ← α; z1 , z2 ← G2 ; x 1 , x 2 , y 1 , y 2 ← Zp ; x x c ← z1 1 z2 2 ; y1 y2 d ← z1 z2 ; pk2 ← (c, d, G, F, H); sk2 ← (x1 , x2 , y1 , y2 ); pk ← (pk1 , pk2 ); sk ← (sk1 , sk2 ); return (pk, sk);

Enc(pk, w, m) s1 , s 2 ← Zp ; s u1 ← g11 g ?s1 w ; u2 ← e(g, g)s1 ; u3 ← H(e(g, h)?s1 ); c1 ← (u1 , u2 , u3 ); s v1 ← z12 ; s v2 ← z22 ; s2 s2 H(u1 ,u2 ) K←c d ; (K1 , K2 ) ← F (K); v3 ← G(K2 ) ⊕ m; v4 ← Mac(K2 , v3 ||c1 ); c ← (c1 , c2 ); return c; Td(sk, w) r w ← Zp ; dw ← hg rw ; tw ← (rw , dw ); return tw ;

Dec(sk, c) c = (c1 , c2 ), where c1 = (u1 , u2 , u3 ) and c2 = (v1 , v2 , v3 ); Test(tw , c) x +y H(v ,v ) x +y H(v1 ,v2 ) c = (c1 , c2 ), where c1 = (u1 , u2 , u3 ) f ← v1 1 1 1 2 v2 1 1 ; and c2 = (v1 , v2 , v3 ); (K1 , K2 ) ← F (K); if u3 = H(e(u1 , dw )urw ); if v4 = Mac(K1 , v3 ||c1 ); 2 return 1; return “⊥”; otherwise m ← v3 ⊕ G(K2 ); return 0; return m; ? Let e : G1 × G1 → G2 be a bilinear group pair with prime order p. MAC = (Mac, Vrfy) is a message authentication code. F is a key derivition function (KDF) [27], G is a pseudorandom generator and H is a collision resistant hash function. Without further descriptions, we simply assume the input domain and output domain match. Fig. 2. A Concrete Instantiation without Random Oracles

5.2

Other Extensions

PEKS/PKE from General Assumptions. Our generic construction has implicitly assumed an exponential keyword space, thus the constructions of PEKS is restricted to anonymous IBE schemes. In fact, it is possible to base the PEKS on general assumptions, e.g., existence of trapdoor one-way functions, with relaxation to a polynomial keywords space [7]. Randomness Reuse. We have required that the encryption algorithms of PEKS and PKE choose independent randomness in our generic construction, however, one can actually reuse the randomness without harming the security of the scheme. The technique is standard, and the details are omitted here due to space limitation. PEKS/PKE with Threshold Decryption. Since a tag-KEM can be easily extended to the threshold setting, it is natural to follow the strategy of [2] to have non-interactive threshold decryption for PEKS/PKE.

Multi-Keyword and Multi-Receiver PEKS/PKE. PEKS/PKE with multi-keywords and multi-receivers have been considered in [3]. We remark the same problem of keyword privacy occurs when considering the ciphertext of PKE leaks information on keyword. It is not hard to generate all our above discussions to these settings. The techniques are quite standard, and again, we omit the details here.

Acknowledgement

We thank the anonymous referees of CANS’07 for many helpful comments.

References

1. M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, T. Kohno, T. Lange, J. Malone-Lee, G. Neven, P. Pallier, and H. Shi. Searchable Encryptino Revisited: Consistnecy Properties, Relation to Anonymous IBE, and Extensions. In Crypto’05, volume 3621 of LNCS, pages 205–222. Springer, 2005. 2. M. Abe, R. Gennaro, and K. Kurosawa. Tag-KEM/DEM: A New Framework for Hybrid Encryption. Cryptology ePrint Archive, http://eprint.iacr.org/2005/027/, 2005. 3. J. Baek, R. Safavi-Naini, and W. Susilo. On the Integration of Public Key Data Encryption and Public Key Encryption with Keyword Search. In ISC’06, volume 4176 of LNCS, pages 217–232. Springer, 2006. 4. M. Bellare, A. Boldyreva, A. Desai, and D. Pointcheval. Key-Privacy in Public-Key Encryption. In Asiacrypt’01, volume 2248 of LNCS, pages 566–582. Springer, 2001. 5. M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway. Relations among notions of security for public key encryption schemes. In Crypto’98, volume 1462 of LNCS, pages 26–45. Springer, 1998. 6. M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing e?cient protocols. In ACM CCS’93, pages 62–73. ACM Press, 1993. 7. D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano. Public Key Encryption with Keyword Search. In Eurocrypt’04, volume 3027 of LNCS, pages 506–522, 2004. 8. D. Boneh and M. Franklin. Identity-Based Encryption from the Weil Pairing. In CRYPTO’01, volume 2139 of LNCS, pages 213–229. Springer, 2001. 9. D. Boneh and J. Katz. Improved E?ciency for CCA-Secure Cryptosystems Built Using Identity-Based Encryption. In CT-RSA’05, volume 3376, pages 87–103. Springer, 2005. 10. X. Boyen and B. Waters. Anonymous Hierarchical Identity Based Encryption (without Random Oracles). In CRYPTO’06, volume 4117 of LNCS, pages 290–307, 2006. 11. R. Canetti, O. Goldreich, and S. Halevi. The Random Oracle Methodology, Revisited. In STOC’98, pages 557 – 594. ACM, 1998. Full availabe at http://eprint.iacr.org/1998/011.pdf. 12. R. Canetti, S. Halevi, and J. Katz. Chosen-Ciphertext Security from Identity-Based Encryption. In EUROCRYPT’04, volume 3027 of LNCS, pages 207–222. Springer, 2004. 13. C. Cocks. An Identity Based Encryption Scheme Based on Quadratic Residues. In the 8th IMA international INPROCEEDINGS on cryptography and coding, volume 2260 of LNCS, pages 360–363. Springer, 2001. 14. R. Cramer and V. Shoup. A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack. In Crypto’98, volume 1462 of LNCS, pages 13–25. Springer, 1998. 15. D. Dolev, C. Dwork, and M. Naor. Non-Malleable Cryptography. In STOC’91, pages 542–552. ACM, 1991. 16. T. ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEE Transactions on Information Theory, 31(4):469–472, 1985. 17. R. Gennaro and V. Shoup. A Note on An Encryption Scheme of Kurosawa and Desmedt. Eprint Report 2004/194. Available at http://eprint.iacr.org/2004/194, 2004. 18. C. Gentry. Practical Identity-Based Encryption Without Random Oracles. In EUROCRYPT’06, volume 4004 of LNCS, pages 445–464. Springer, 2006.

19. S. Goldwasser and S. Micali. Probabilistic Encryption. Journal of Computer and System Sciences, 28(2):270–299, 1984. 20. K. Kurosawa and Y. Desmedt. A New Paradigm of Hybrid Encryption Scheme. In CRYPTO’04, volume 3152 of LNCS, pages 426–442. Springer, 2004. 21. M. Naor and M. Yung. Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. In STOC’90, pages 427–437. ACM, 1990. 22. T. Okamoto and D. Pointcheval. REACT: Rapid Enhanced-security Asymmetric Cryptosystem Transform. In CT-RSA’01, volume 159-175 of LNCS, pages 159–175. Springer, 2001. 23. C. Racko? and D.R. Simon. Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack. In CRYPTO’91, volume 576 of LNCS, pages 433–444. Springer, 1991. 24. A. Sahai. Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security. In FOCS’99, pages 543–553. IEEE Computer Society, 1999. 25. A. Shamir. Identity-Based Cryptosystems and Signature Schemes. In CRYPTO’84, volume 196 of LNCS, pages 47–53. Springer, 1984. 26. V. Shoup. OAEP Reconsidered. In Crypto’01, volume 2139 of LNCS, pages 239–259. Springer, 2001. 27. V. Shoup. ISO 18033-2: An Emerging Standard for Public-Key Encryption (committee draft). Available at http://shoup.net/iso/, June 2004. 28. B. Waters. E?cient Identity-Based Encryption Without Random Oracles. In EUROCRYPT’05, volume 3494 of LNCS, pages 114–127. Springer, 2005.

A

Identity Based Encryption

An identity based encryption (IBE) can be regarded as a special public key encryption, where the receiver’s public key can be any string. Compared with traditional public key encryption, an IBE scheme is equipped with an additional extraction algorithm, with a master secret key and an identity as input, outputs a secret key that is capable to decrypt ciphertext corresponding to this identity. An IBE scheme consists of four algorithms IBE = (IBEkg, IBEext, IBEenc, IBEdec). IBEkg: a randomized algorithm, taking a security parameter k as the input, outputs a public parameter params and a master secret key msk, denoted as (params, msk) ← TBEkg(1k ). IBEext: a possibly randomized algorithm, takes inputs of params, msk and an identity id, outputs a secret key skid for id, denoted as skid ← IBEext(params, msk, id), in brief skid ← IBEext(msk, id). IBEext: a possibly randomized algorithm, taking params, an identity id and a plaintext m taken from the message space as input, with internal coin ?ipping r, outputs a ciphertext c, which is denoted as c ← IBEenc(params, id, m, r), in brief c ← IBEenc(params, id, m). IBEdec: a deterministic algorithm, taking a secret key skid , an identity id and a ciphertext c as input, outputs a plaintext m, or a special symbol “⊥”, which is denoted m ← IBEdec(skid , id, c). We require for all (params, msk) ← IBEkg(1k ), skid ← IBEext(msk, id) and all m, we have IBEdec(skid , id, IBEenc(params, id, m)) = m.

Anonymity. We consider anonymity of receiver against adaptively chosen-ID and chosen plaintext attack (AONT-ID-CPA) [1]. We say an identity based encryption is (?, q, T )-INDsID-CPA-secure if the advantage of any adversary A is at most ?, with access q times to an extraction oracle EO within time T in the following experiment. Advaont-id-cpa (k) = Pr[(params, msk) ← IBEkg(1k ); IBE,A (id0 , id1 , m, s) ← AEO (params); b ← {0, 1}; c? ← IBEenc(params, idb , m); b′ ← AEO (c? , s) : b′ = b] ? 1/2 where EO returns the corresponding secret key on a query on identity id, whereas A is forbidden to query (id0 , id1 ) at EO. We say an IBE is AONT-ID-CPA-Secure, if for polynomially bounded q and T , ? is negligible.

- Public Key Encryption with keyword
- Public Key Encryption with Keyword Search Revisited
- public-Key Encryption with registered keyword search
- Public-Key Encryption with Masking
- Public Key Encryption with conjunctive field keyword search
- Public Key Encryption and Digital Signature
- An_Efficient_RSA_Public_Key_Encryption_Scheme
- A forward-secure public-key encryption scheme
- 08 Public Key Encryption
- Worry-free encryption _ functional encryption with public keys

- Generic Combination of Public Key Encryption with Keyword Search and Public Key Encryption
- 会计毕业实*工作计划
- 2018年张贤淼-社会管理现状社会实践调查报告word版本 (6页)
- 元学*文章汇总||文章分类总结||阅读线索
- 东莞市圣泰建筑工程有限公司企业信用报告-天眼查
- *凡的世界高二读后感范文2021
- 会计学-第一章会计学的基本概念
- 成武县城乡建设工程质量检测中心企业信用报告-天眼查
- 缓控释药物制剂给药系统.ppt
- python遇到 Segmentation fault (core dumped) 错误
- 女性减脂塑形最佳运动
- who是什么从句
- 男人一生的补药
- [精品]最新部编四年级语文上册 21 古诗三首 教学反思2(1)
- 人教版小学语文六年级下册教学计划(新教材)
- 初一叙事作文：描写春节家乡*俗_3000字
- iOS开发技巧6-iOS libc++abi.dylib: handler threw exception
- 公司差旅费报销管理制度
- 教科版五四制小学四年级语文上册教案军犬黑子
- 广州莱欧捷仪器仪表有限公司(企业信用报告)
- 苏教版语文二年级上册《孔繁森》PPT课件7

- (个人礼仪)职场女性着装有哪些技巧
- 城市农民工住房问题分析
- 二十年后的一天记叙文
- 学术英文简历范文免费模板
- 新课标下初中语文作文教学新议
- 董事会关于转让上海氯碱化工房产开发经营有限公司49%股权的关联交易公告
- 20XX年学年度第一学期小学教导处教学工作计划
- 百丽鞋业(北京)有限公司第三十六分公司企业信息报告-天眼查
- 模具基础知识培训资料资料
- 基于PMU量测的线路参数辨识算法
- 中国马克思主义大众化面临的困境及对策
- SST华塑：八届董事会第四次临时会议决议公告 2011-03-31
- 玛卡是什么？玛咖为什么是“人间天堂”的神奇果
- 大三怎么度过
- 旅游局自查报告2篇
- 玛咖和玛卡是不是同一种
- 刀塔传奇游戏画面卡顿是什么原因
- 新课程初中数学课兴趣教学之我见
- 干电剃毛器项目可行性研究报告(目录)
- 2020年外贸年度工作总结
- 2019年秋七年级英语人教版上册课件：Unit 1 重难点题组训练和Self Check (共13张PPT)教育精品.ppt
- 食品化学8-风味物质
- 广东省广州市天河区2019高考英语二轮复习 非谓语动词02专题训练(含解析)
- 【全国百强校】江西省新余市第四中学2015-2016学年高三上学期第一次段考化学试题
- 水力扩孔技术在深井石门揭煤防突中的应用
- 湖北翰墨星文化传媒有限公司企业信用报告-天眼查
- 最无悔的遇见作文700字(高分作文)
- 保险十大真相1
- 我渴望信任重点初中生精选作文
- 初二随笔：爱情是那么不堪一击
- 国际英语新闻:UK PM to chair cabinet meeting as Brexit deal agreed
- ui界面测试方法要点
- 北师大版英语九年级Unit 3 Creativity Lesson 7 A Famous Inventor 第一课时课件
- 【工作总结】中学田径运动会工作总结
- 高考英语一轮复习 Unit 1 Great scientists课件 新人教版必修5 (2)
- 初中体育教学中意志力的培养
- 网络工程与综合布线复*题目(答案)
- 最新整理某镇安全生产检查活动月工作计划.docx
- 中考英语作文素材：保护眼睛
- 医药代理合同
- 哮喘饮食需要注意什么哮喘饮食的6大注意事项
- 千牛可以两个手机同时登录吗