# Private Predicate Encryption for Inner Product from Key-Homomorphic Pseudorandom Function

Authors: Yi-Fan Tseng; Zi-Yuan Liu; Jen-Chieh Hsu; Raylin Tso
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Predicate encryption (PE), formalized by Katz et al., is a new paradigm of public-key encryption that conceptually captures the public-key encryption that supports fine-grained access control policy. Because of the nature of PE, it is used for cloud storage so that users can retrieve encrypted data without revealing any information about the data to cloud servers and other users. Although lots of PE schemes have been studied, the predicate-hiding security is seldom considered; that is, the user’s secret key may leak sensitive information of the predicate. Additionally, the security of the current predicate-hiding PE schemes relies on the discrete logarithm assumption which cannot resist the quantum attacks in the future. In this paper, we propose a generic PE for inner product under symmetric-key setting, called private IPE, from specific key-homomorphic pseudorandom function (PRF). The rigorous proofs are provided to show that the construction is payload-hiding, attribute-hiding, and predicate-hiding secure. With the advantage of the generic construction, if the underlying PRF can resist quantum attacks, then, through our proposed generic construction, a quantum-resistant private IPE can be obtained.


---

## Body

## 1. Introduction

In recent years, cloud computing has become increasingly important as smartphones and Internet of Things devices are widely used in our life. Users typically upload their data to the cloud to achieve efficient computing and reduce storage requirements of their devices. Due to the fact that the uploaded data are sensitive, users may consider using authentication protocol [1–4] and encryption schemes [5, 6] to protect their data privacy in cloud environment. One novel approach is to encrypt data before it is uploaded to the cloud. However, encrypted data loses flexibility in data usage, such as fine-grained control over access to encrypted data. For example, a user may want to search for and download ciphertext that corresponds to certain attributes. If each piece of data is purely encrypted, the only way is to download all the ciphertexts and decrypt them for search. Unfortunately, this approach would be very inefficient. Therefore, how to efficiently control the access to encrypted data and ensure the privacy and security of data is an urgent issue for cloud computing.Predicate encryption (PE) [7], formalized by Katz et al., is a general paradigm that conceptually captures the public-key encryption supporting fine-grained access control policy. In a PE scheme for a predicate function P, a secret key, issued by a trusted authority, is associated with a key attribute y, while the ciphertext is associated with a ciphertext attribute x. Specifically, the ciphertext can be decrypted using the secret key if and only if Px,y=1. Therefore, PE can be used as access control mechanism for the previous cloud storage scenario and provide the flexibility for encryption schemes, which allows sender to encrypt data with more complicated access policy. For example, in a school scenario, the secret keys of each teacher and each student are associated with key attributes “teacher” and “student,” respectively. If the principal wants to encrypt a file that can only be decrypted by each student and teacher, he/she can use a PE supporting “belong to” functionality and encrypt this file with a ciphertext attribute “student or teacher.” Because the key attributes “teacher” and “student” belong to ciphertext attribute “student or teacher,” the secret keys associated with these key attributes can decrypt the ciphertext.Additionally, Katz et al. proposed the first PE supporting inner product predicate, called PE for inner product (IPE), whereas ciphertext can be decrypted if and only if the inner product ofx and y is equal to 0. They further suggested that IPE can be used to build other more flexible schemes, such as (anonymous) identity-based encryption [8], hidden vector encryption [9, 10], CNF/DNF formulas [7], PE schemes supporting polynomial evaluation [11], and exact thresholds [12]. The most basic security requirement of IPE, called payload-hiding, stipulates that a ciphertext does not reveal any information of the plaintext if Px,y=1. A stronger security requirement of PE is attribute-hiding, which stipulates that a ciphertext reveals nothing about the ciphertext attribute. Although a lot of attribute-hiding IPE schemes [13–16] have been studied, seldom schemes [17–19] focus on the predicate-hiding security. In more detail, a secret key may reveal some sensitive information of the predicate that belongs to the key holder. Actually, in public-key cryptosystem, since the encryption algorithm is publicly accessible, any user can adaptively generate a ciphertext. The user who has obtained a secret key can evaluate its predicate with possible ciphertexts; thus it is hard to achieve predicate-hiding in the public-key setting.Shen et al. [18] first considered constructing the IPE under symmetric-key setting, a.k.a. private IPE, to achieve predicate-hiding security requirement. More precisely, in the work, when generating a secret key, generating a ciphertext requires a master secret key, so that not every user can adaptively generate a ciphertext to test which predicate is embedded in the secret key. Compared with IPE under public-key setting, private IPE is more suitable for cloud storage under self-use scenario. For example, as shown in Figure 1, Alice uses the cloud storage service to store her files. For privacy concern, she uses private IPE as an access control mechanism. Alice not only uploads an encrypted file ctFile,i but also uploads another ciphertext ctx,i=EncryptSK,x,M=1 for a specific ciphertext attribute by using private IPE. When Alice wants to retrieve encrypted files, she can send the secret key for some key attribute, that is, sky⟵KeyGenSK,y, to the cloud. The cloud can then evaluate the predicate on each ciphertext by performing decryption. If the predicate is satisfied, that is, 1=?Decryptctx,i,sky, the cloud returns the corresponding encrypted files of those ciphertexts.Figure 1
Private IPE scheme for cloud storage in self-use scenario.After Shen et al.’s pioneering work [18], Yoshino et al. [19] provided a more practical IPE scheme that uses only three groups, whereas [18] required four groups. In addition, Kawai and Takashima [17] then introduced a predicate-hiding IPE, where the security is proven under the decision linear assumption without random oracles. However, the sizes of the secret keys of the above schemes [17–19] are linearly related to the lengths of the key attributes. Due to the fact that users may obtain many secret keys for decrypting different ciphertext, it is important to reduce the key size of secret key. In addition, Shor [20, 21] has shown that existing quantum algorithms can break the discrete logarithm and factoring assumptions. Therefore, the current private IPE schemes [17–19] are susceptible to quantum attack. Hence, how to construct a quantum-resistant private IPE scheme where the secret key is of constant size remains an open issue.


### 1.1. Our Contributions

In this paper, inspired by Alamati et al.’s work [22], we propose a generic private IPE construction by utilizing specific key-homomorphic pseudorandom functions (PRF). By the advantage of the generic construction, the construction enjoys the security properties of the underlying primitives. Therefore, if the underlying key-homomorphic PRF is quantum-resistant, we further obtain a quantum-resistant private IPE scheme. In particular, in our construction, we require the underlying key-homomorphic PRF to have the following property for decryption correctness: the key space K and the output space Y are equal to ℤq, for some prime q.To obtain a private IPE scheme with constant-size secret key, we carefully use the key-homomorphic property of the key-homomorphic PRF to map each predicate attribute to the inner product of master secret key and secret key. That is,sky=∑i=1ℓ∑j=1yiFai,h=Fa,y,h, where y=y1,…,yℓ is a predicate vector and a=a1,…,aℓ,h is the master secret key. Hence, the size of secret key is only log2q, where q is the underlying modulo.In addition, the rigorous security proofs are provided to demonstrate that if the underlying key-homomorphic PRF satisfies pseudorandomness (i.e., the output value of key-homomorphic PRF is indistinguishable from the value randomly chosen fromY), the proposed construction satisfies the criteria of payload-hiding, attribute-hiding, and predicate-hiding privacy. The comparison of our construction with other state-of-the-art private IPE schemes is presented to show that our result is not only more secure but also more efficient with respect to the size of secret key.In summary, this work introduces a generic construction to show how to obtain the first quantum-resistant private IPE scheme with a constant-size secret key.


### 1.2. Paper Organization

The rest of the paper is organized as follows. Section2 recalls the definition of the PRF used in our generic construction. Moreover, Section 3 provides the definition and security requirement of the private PE. Next, Sections 4 and Section 5 introduce and provide the security proofs of our generic constriction, respectively. Section 6 compares our proposed construction with the related private IPE schemes. Finally, Section 7 concludes this study.


## 1.1. Our Contributions

In this paper, inspired by Alamati et al.’s work [22], we propose a generic private IPE construction by utilizing specific key-homomorphic pseudorandom functions (PRF). By the advantage of the generic construction, the construction enjoys the security properties of the underlying primitives. Therefore, if the underlying key-homomorphic PRF is quantum-resistant, we further obtain a quantum-resistant private IPE scheme. In particular, in our construction, we require the underlying key-homomorphic PRF to have the following property for decryption correctness: the key space K and the output space Y are equal to ℤq, for some prime q.To obtain a private IPE scheme with constant-size secret key, we carefully use the key-homomorphic property of the key-homomorphic PRF to map each predicate attribute to the inner product of master secret key and secret key. That is,sky=∑i=1ℓ∑j=1yiFai,h=Fa,y,h, where y=y1,…,yℓ is a predicate vector and a=a1,…,aℓ,h is the master secret key. Hence, the size of secret key is only log2q, where q is the underlying modulo.In addition, the rigorous security proofs are provided to demonstrate that if the underlying key-homomorphic PRF satisfies pseudorandomness (i.e., the output value of key-homomorphic PRF is indistinguishable from the value randomly chosen fromY), the proposed construction satisfies the criteria of payload-hiding, attribute-hiding, and predicate-hiding privacy. The comparison of our construction with other state-of-the-art private IPE schemes is presented to show that our result is not only more secure but also more efficient with respect to the size of secret key.In summary, this work introduces a generic construction to show how to obtain the first quantum-resistant private IPE scheme with a constant-size secret key.


## 1.2. Paper Organization

The rest of the paper is organized as follows. Section2 recalls the definition of the PRF used in our generic construction. Moreover, Section 3 provides the definition and security requirement of the private PE. Next, Sections 4 and Section 5 introduce and provide the security proofs of our generic constriction, respectively. Section 6 compares our proposed construction with the related private IPE schemes. Finally, Section 7 concludes this study.


## 2. Pseudorandom Function (PRF)

In this section, we recall the definition of pseudorandom function from [23].Definition 1.
(pseudorandom functions [23]). A PRF F:K×X⟶Y is a keyed function defined over a key space K, a domain X, and a range Y (these sets may be parameterized by the security parameter λ), whose output is indistinguishable from a truly random value. The security of a PRF can be defined by the two experiments EXP0 and EXP1 with an adversary A. At first, a key k is uniformly randomly chosen from the key space K. Given the description of the PRF, the adversary is then allowed to make queries to the following oracles:(i)
Evaluate. Given x∈X from A, the oracle returns Fk,x to A.(ii)
Challenge. Given x∈X from A, where x has not been queried to evaluate Oracle, if b=1, then the oracle returns Fk,x, and if b=0, then the oracle returns a random y⟵$Y.
Once the adversary is done querying the oracles, it outputs a bitb′∈0,1. For b=0,1, we define Wb as the event where the adversary outputs b′=1 in the experiment EXPb. The advantage of an adversary A is defined as(1)AdvAPRF1λ=PrW1−PrW0.
We say that a PRF is secure if, for all PPT adversaryA, AdvAPRF1λ is negligible.Definition 2.
(key-homomorphic PRF [24]). Let K,∘ and Y,∗ be groups. Then, a keyed function F:K×X⟶Y is a key-homomorphic PRF:(i)
F is a secure PRF.(ii)
For everyk1,k2∈K and every input x∈X, we have(2)Fk1,x∗Fk2,x=Fk1∘k2,x.Definition 3.
(pseudorandom generators [24]). A pseudorandom generator (PRG) is an efficiently computable function G:X⟶Y with the following security, where X,° and Y,∗ are groups. The security of a PRG is secure if, for any PPT algorithm A, is negligible.(3)AdvAPRG1λ=PrAGx=1;x⟵X−PrAR=1;R⟵$Y.


## 3. Private Predicate Encryption

LetP=Pℓℓ∈ℕc for some constant c∈ℕ be a predicate family, where Pℓ:Aℓ×Pℓ⟶0,1 is a predicate function defined over a ciphertext attribute space Aℓ and a key attribute space Pℓ. The family index ℓ specifies the description of a predicate from the family. We would occasionally omit the index ℓ when the context is clear.


### 3.1. System Model

A private PE for predicate functionP:A×P⟶0,1 consists of four algorithms: Setup, KeyGen,Encrypt, and Decrypt. The details of the algorithms are shown as follows:(i)
Setup1λ,1ℓ⟶pp,SK. Given the security parameters and the family index λ,ℓ, the algorithm outputs the system parameter pp and the secret key SK. Note that the description of A and P will be implicitly included in pp.(ii)
Encryptpp,SK,x,M⟶ctx. Given the system parameter pp, a secret key SK, a ciphertext attribute x∈A, and a message M, the algorithm outputs a ciphertext ctx for x.(iii)
KeyGenpp,SK,y⟶sky. Given the system parameter pp, a secret key SK, and a key attribute y∈P, the algorithm outputs the secret key sky for y.(iv)
Decryptpp,ctx,sky⟶M/⊥. Given the system parameter pp, a ciphertext ctx, and a secret key sky, the algorithm outputs a message M or an error symbol ⊥.Definition 4.
(correctness). For allλ,ℓ∈ℕ, x∈A, and y∈P, letting ctx⟵Encryptpp,SK,x,M and sky⟵KeyGenpp,SK,y, we have(4)M⟵Decryptpp,ctx,sky,ifPx,y=1;⊥⟵Decryptpp,ctx,sky,ifPx,y=0,where pp,SK⟵Setup1λ,1ℓ.
In this paper, we construct a private PE scheme supporting inner product predicate function defined overℤqℓ, where q is a large prime. That is,(i)
ℓ denotes the dimension of the vector space.(ii)
A=P=ℤpℓ.(iii)
For allx,y∈ℤqℓ, P:x,y=1 if x,y=0.
Such encryption schemes are called “private PE for inner product” (private IPE), andA=ℤqℓ and P=ℤqℓ are called attribute vector space and predicate vector space, respectively.


### 3.2. Security Definitions

In private PE, there exist three types of adversary that want to retrieve the information of message, ciphertext attribute, and key attribute from ciphertext and secret key. Therefore, we model three security requirements of private PE, payload-hiding, attribute-hiding, and predicate-hiding securities, to model the attacks from these adversaries.The payload-hiding security [7] for predicate function P:A×P⟶0,1 is defined as an interactive game between a challenger C and an adversary A. In payload-hiding models, a ciphertext reveals nothing about the encrypted message, and thus in some literature it is defined as IND-CPA security.


#### 3.2.1. Payload-Hiding Game

(i)
Setup. The challenger C runs Setup1λ,1ℓ to generate a secret key SK and the system parameter pp. Then, it sends the system parameter pp to the adversary A and keeps the secret key SK secretly.(ii)
Query Phase 1. A can query polynomially many times of the oracles described as follows:(i)
KeyGen Oracle: whenA issues a query with y∈P, C returns a secret key sky⟵KeyGenpp,SK,y.(ii)
Encrypt Oracle: whenA issues a query with x∈A and a message M, C returns a ciphertext ctx⟵Encryptpp,SK,x,M.(iii)
Challenge. The adversary A submits x∗∈A such that Px∗,y=0 for all y∈P, which has been queried to KeyGen Oracle in Query Phase 1, and two massages M0,M1 with the same length to the challenger C. Then C randomly chooses b∈0,1 and returns a challenge ciphertext cx∗⟵Encryptpp,SK,x∗,Mb.(iv)
Query Phase 2. This phase is the same as Query Phase 1, except that A is only allowed to make a query to KeyGen Oracle with y∈P such that Px∗,y=0.(v)
Guess. The adversary A outputs a bit b′ and wins the game if b′=b.The advantage of an adversary for winning the payload-hiding game is defined as(5)AdvAPH1λ=Prb′=b−12.Definition 5.
(payload-hiding for private predicate encryption). We say that private PE is payload-hiding if there is no probabilistic polynomial-time adversaryA winning the above payload-hiding game with a nonnegligible advantage.
Next, we define the “attribute-hiding” security for private PE, which can be also extended from the attribute-hiding definition for conventional PE [7]. Attribute-hiding security models that there is no adversary can obtain any information of the ciphertext attribute x from the ciphertext. We then define attribute-hiding via a security game between a challenger C and an adversary A.


#### 3.2.2. Attribute-Hiding Game

(i)
Setup, Query Phase 1, Query Phase 2, and Guess are the same as those in the payload-hiding game.(ii)
Challenge. The adversary A submits two ciphertext attributes x0,x1∈A such that Px0,y=Px1,y for all y∈P, which has been queried to KeyGen Oracle in Query Phase 1, and a massage M with the same length to the challenger C. Then, C randomly chooses b∈0,1 and returns a challenge ciphertext cx∗⟵Encryptpp,SK,xb,M.The advantage of an adversary for winning the attribute-hiding game is defined as(6)AdvAAH1λ=Prb′=b−12.Definition 6.
(attribute-hiding for private predicate encryption). We say that private PE is attribute-hiding, if there is no probabilistic polynomial-time adversaryA winning the above attribute-hiding game with a nonnegligible advantage.
There is another weaker notion, called “weak attribute-hiding” [25]. The weak attribute-hiding game is the same as the above attribute-hiding game, except the following:(i)
The adversary sendsx0,M0,x1,M1 to invoke the Challenge phase.(ii)
The restriction onx0,x1 is modified to “Px0,y=Px1,y=0 for all y∈P which has been queried to KeyGen Oracle in Query Phase 1.”
Furthermore, we define the “predicate-hiding” for private PE scheme via the following game, which models the notion that a secret keysky reveals nothing about the key attribute y.


#### 3.2.3. Predicate-Hiding Game

(i)
Setup, Query Phase 1, Query Phase 2, and Guess are the same as those in the payload-hiding game.(ii)
Challenge. The adversary A submits two key attributes y0,y1∈P to the challenger C, such that Px,y0=Px,y1=0 for all x∈A which has been queried to Encrypt Oracle in Query Phase 1. Then, C randomly chooses b∈0,1 and returns a challenge secret key skyb⟵KeyGenpp,SK,yb.The advantage of an adversary for winning the predicate-hiding game is defined as(7)AdvAPP1λ=Prb′=b−12.Definition 7.
(predicate-hiding for private predicate encryption). We say that private PE achieves predicate-hiding if there is no probabilistic polynomial-time adversaryA winning the above predicate-hiding game with nonnegligible advantage.


## 3.1. System Model

A private PE for predicate functionP:A×P⟶0,1 consists of four algorithms: Setup, KeyGen,Encrypt, and Decrypt. The details of the algorithms are shown as follows:(i)
Setup1λ,1ℓ⟶pp,SK. Given the security parameters and the family index λ,ℓ, the algorithm outputs the system parameter pp and the secret key SK. Note that the description of A and P will be implicitly included in pp.(ii)
Encryptpp,SK,x,M⟶ctx. Given the system parameter pp, a secret key SK, a ciphertext attribute x∈A, and a message M, the algorithm outputs a ciphertext ctx for x.(iii)
KeyGenpp,SK,y⟶sky. Given the system parameter pp, a secret key SK, and a key attribute y∈P, the algorithm outputs the secret key sky for y.(iv)
Decryptpp,ctx,sky⟶M/⊥. Given the system parameter pp, a ciphertext ctx, and a secret key sky, the algorithm outputs a message M or an error symbol ⊥.Definition 4.
(correctness). For allλ,ℓ∈ℕ, x∈A, and y∈P, letting ctx⟵Encryptpp,SK,x,M and sky⟵KeyGenpp,SK,y, we have(4)M⟵Decryptpp,ctx,sky,ifPx,y=1;⊥⟵Decryptpp,ctx,sky,ifPx,y=0,where pp,SK⟵Setup1λ,1ℓ.
In this paper, we construct a private PE scheme supporting inner product predicate function defined overℤqℓ, where q is a large prime. That is,(i)
ℓ denotes the dimension of the vector space.(ii)
A=P=ℤpℓ.(iii)
For allx,y∈ℤqℓ, P:x,y=1 if x,y=0.
Such encryption schemes are called “private PE for inner product” (private IPE), andA=ℤqℓ and P=ℤqℓ are called attribute vector space and predicate vector space, respectively.


## 3.2. Security Definitions

In private PE, there exist three types of adversary that want to retrieve the information of message, ciphertext attribute, and key attribute from ciphertext and secret key. Therefore, we model three security requirements of private PE, payload-hiding, attribute-hiding, and predicate-hiding securities, to model the attacks from these adversaries.The payload-hiding security [7] for predicate function P:A×P⟶0,1 is defined as an interactive game between a challenger C and an adversary A. In payload-hiding models, a ciphertext reveals nothing about the encrypted message, and thus in some literature it is defined as IND-CPA security.


### 3.2.1. Payload-Hiding Game

(i)
Setup. The challenger C runs Setup1λ,1ℓ to generate a secret key SK and the system parameter pp. Then, it sends the system parameter pp to the adversary A and keeps the secret key SK secretly.(ii)
Query Phase 1. A can query polynomially many times of the oracles described as follows:(i)
KeyGen Oracle: whenA issues a query with y∈P, C returns a secret key sky⟵KeyGenpp,SK,y.(ii)
Encrypt Oracle: whenA issues a query with x∈A and a message M, C returns a ciphertext ctx⟵Encryptpp,SK,x,M.(iii)
Challenge. The adversary A submits x∗∈A such that Px∗,y=0 for all y∈P, which has been queried to KeyGen Oracle in Query Phase 1, and two massages M0,M1 with the same length to the challenger C. Then C randomly chooses b∈0,1 and returns a challenge ciphertext cx∗⟵Encryptpp,SK,x∗,Mb.(iv)
Query Phase 2. This phase is the same as Query Phase 1, except that A is only allowed to make a query to KeyGen Oracle with y∈P such that Px∗,y=0.(v)
Guess. The adversary A outputs a bit b′ and wins the game if b′=b.The advantage of an adversary for winning the payload-hiding game is defined as(5)AdvAPH1λ=Prb′=b−12.Definition 5.
(payload-hiding for private predicate encryption). We say that private PE is payload-hiding if there is no probabilistic polynomial-time adversaryA winning the above payload-hiding game with a nonnegligible advantage.
Next, we define the “attribute-hiding” security for private PE, which can be also extended from the attribute-hiding definition for conventional PE [7]. Attribute-hiding security models that there is no adversary can obtain any information of the ciphertext attribute x from the ciphertext. We then define attribute-hiding via a security game between a challenger C and an adversary A.


### 3.2.2. Attribute-Hiding Game

(i)
Setup, Query Phase 1, Query Phase 2, and Guess are the same as those in the payload-hiding game.(ii)
Challenge. The adversary A submits two ciphertext attributes x0,x1∈A such that Px0,y=Px1,y for all y∈P, which has been queried to KeyGen Oracle in Query Phase 1, and a massage M with the same length to the challenger C. Then, C randomly chooses b∈0,1 and returns a challenge ciphertext cx∗⟵Encryptpp,SK,xb,M.The advantage of an adversary for winning the attribute-hiding game is defined as(6)AdvAAH1λ=Prb′=b−12.Definition 6.
(attribute-hiding for private predicate encryption). We say that private PE is attribute-hiding, if there is no probabilistic polynomial-time adversaryA winning the above attribute-hiding game with a nonnegligible advantage.
There is another weaker notion, called “weak attribute-hiding” [25]. The weak attribute-hiding game is the same as the above attribute-hiding game, except the following:(i)
The adversary sendsx0,M0,x1,M1 to invoke the Challenge phase.(ii)
The restriction onx0,x1 is modified to “Px0,y=Px1,y=0 for all y∈P which has been queried to KeyGen Oracle in Query Phase 1.”
Furthermore, we define the “predicate-hiding” for private PE scheme via the following game, which models the notion that a secret keysky reveals nothing about the key attribute y.


### 3.2.3. Predicate-Hiding Game

(i)
Setup, Query Phase 1, Query Phase 2, and Guess are the same as those in the payload-hiding game.(ii)
Challenge. The adversary A submits two key attributes y0,y1∈P to the challenger C, such that Px,y0=Px,y1=0 for all x∈A which has been queried to Encrypt Oracle in Query Phase 1. Then, C randomly chooses b∈0,1 and returns a challenge secret key skyb⟵KeyGenpp,SK,yb.The advantage of an adversary for winning the predicate-hiding game is defined as(7)AdvAPP1λ=Prb′=b−12.Definition 7.
(predicate-hiding for private predicate encryption). We say that private PE achieves predicate-hiding if there is no probabilistic polynomial-time adversaryA winning the above predicate-hiding game with nonnegligible advantage.


## 3.2.1. Payload-Hiding Game

(i)
Setup. The challenger C runs Setup1λ,1ℓ to generate a secret key SK and the system parameter pp. Then, it sends the system parameter pp to the adversary A and keeps the secret key SK secretly.(ii)
Query Phase 1. A can query polynomially many times of the oracles described as follows:(i)
KeyGen Oracle: whenA issues a query with y∈P, C returns a secret key sky⟵KeyGenpp,SK,y.(ii)
Encrypt Oracle: whenA issues a query with x∈A and a message M, C returns a ciphertext ctx⟵Encryptpp,SK,x,M.(iii)
Challenge. The adversary A submits x∗∈A such that Px∗,y=0 for all y∈P, which has been queried to KeyGen Oracle in Query Phase 1, and two massages M0,M1 with the same length to the challenger C. Then C randomly chooses b∈0,1 and returns a challenge ciphertext cx∗⟵Encryptpp,SK,x∗,Mb.(iv)
Query Phase 2. This phase is the same as Query Phase 1, except that A is only allowed to make a query to KeyGen Oracle with y∈P such that Px∗,y=0.(v)
Guess. The adversary A outputs a bit b′ and wins the game if b′=b.The advantage of an adversary for winning the payload-hiding game is defined as(5)AdvAPH1λ=Prb′=b−12.Definition 5.
(payload-hiding for private predicate encryption). We say that private PE is payload-hiding if there is no probabilistic polynomial-time adversaryA winning the above payload-hiding game with a nonnegligible advantage.
Next, we define the “attribute-hiding” security for private PE, which can be also extended from the attribute-hiding definition for conventional PE [7]. Attribute-hiding security models that there is no adversary can obtain any information of the ciphertext attribute x from the ciphertext. We then define attribute-hiding via a security game between a challenger C and an adversary A.


## 3.2.2. Attribute-Hiding Game

(i)
Setup, Query Phase 1, Query Phase 2, and Guess are the same as those in the payload-hiding game.(ii)
Challenge. The adversary A submits two ciphertext attributes x0,x1∈A such that Px0,y=Px1,y for all y∈P, which has been queried to KeyGen Oracle in Query Phase 1, and a massage M with the same length to the challenger C. Then, C randomly chooses b∈0,1 and returns a challenge ciphertext cx∗⟵Encryptpp,SK,xb,M.The advantage of an adversary for winning the attribute-hiding game is defined as(6)AdvAAH1λ=Prb′=b−12.Definition 6.
(attribute-hiding for private predicate encryption). We say that private PE is attribute-hiding, if there is no probabilistic polynomial-time adversaryA winning the above attribute-hiding game with a nonnegligible advantage.
There is another weaker notion, called “weak attribute-hiding” [25]. The weak attribute-hiding game is the same as the above attribute-hiding game, except the following:(i)
The adversary sendsx0,M0,x1,M1 to invoke the Challenge phase.(ii)
The restriction onx0,x1 is modified to “Px0,y=Px1,y=0 for all y∈P which has been queried to KeyGen Oracle in Query Phase 1.”
Furthermore, we define the “predicate-hiding” for private PE scheme via the following game, which models the notion that a secret keysky reveals nothing about the key attribute y.


## 3.2.3. Predicate-Hiding Game

(i)
Setup, Query Phase 1, Query Phase 2, and Guess are the same as those in the payload-hiding game.(ii)
Challenge. The adversary A submits two key attributes y0,y1∈P to the challenger C, such that Px,y0=Px,y1=0 for all x∈A which has been queried to Encrypt Oracle in Query Phase 1. Then, C randomly chooses b∈0,1 and returns a challenge secret key skyb⟵KeyGenpp,SK,yb.The advantage of an adversary for winning the predicate-hiding game is defined as(7)AdvAPP1λ=Prb′=b−12.Definition 7.
(predicate-hiding for private predicate encryption). We say that private PE achieves predicate-hiding if there is no probabilistic polynomial-time adversaryA winning the above predicate-hiding game with nonnegligible advantage.


## 4. A Private IPE from Key-Homomorphic PRF

In the following, we describe how to obtain a private IPE from a key-homomorphic PRF. In our construction, we require thatℛ=ℤq, for some prime q. Additionally, we assume that the decryptor knows the value of predicate vector y of his/her secret key sky.(i)
Setup1λ,1ℓ. Suppose that the message space is 0,1m for some positive integer m=polyλ. Given the security parameters λ,ℓ, where λ,ℓ∈ℕ, the algorithm outputs the system parameter pp and the secret key SK as follows:(i)
Choose a primeq=polyλ.(ii)
Choose a key-homomorphic PRFF:ℛ×X⟶ℛ, where X is the domain and ℛ,+,⋅ is a ring.(iii)
Choosea=a1,…,aℓ∈ℛℓ.(iv)
Choose a pseudorandom generatorG:ℛ⟶0,1m.(v)
Chooseh⟵$X.(vi)
Outputpp=F,G and the secret key SK=a,h. Note that the descriptions of F and G are implicitly included in the system parameter pp.(ii)
Encryptpp,SK,x,M. Given the system parameter pp, a secret key SK, an attribute vector x=x1,…,xℓ∈ℛℓ, and a message M, the algorithm runs the following steps:(i)
Choose randomδ,σ⟵$ℛ.(ii)
ci=F∑j=1δxi+ai,h+σ for i=1,…,ℓ.(iii)
c0=M⊕Gσ.(iv)
Output ciphertextctx=c0,…,cℓ∈0,1m×ℛℓ.(iii)
KeyGenpp,SK,y. Given the system parameter pp, a secret key SK, and a predicate vector y=y1,…,yℓ∈ℛℓ, the algorithm computes the following steps:(i)
sky=∑i=1ℓ∑j=1yiFai,h=Fa,y,h.(ii)
Outputsky.(iv)
Decryptpp,ctx,sky. Given the system parameter pp, a ciphertext ctx, and a secret key sky, the algorithm computes the following steps:(i)
ct′=∑i=1ℓyi⋅ci−sky.(ii)
Computeσ=ct′⋅∑i=1ℓyi−1.(iii)
ComputeM=c0⊕Gσ.Correctness. Let ctx and sky be as above. Then,(8)ct′=∑i=1ℓyi⋅ci−sky=∑i=1ℓyi⋅F∑j=1δxi+ai,h+σ−sky=F∑j=1δx,y+a,y,h+∑i=1ℓyiσ−Fa,y,h.Ifx,y=0, we have(9)ct′=Fa,y,h+∑i=1ℓyiσ−Fa,y,h=∑i=1ℓyiσ.Then, we can computeσ=ct′⋅∑i=1ℓyi−1, and the plaintext can be decrypted by(10)c0⊕Gσ=M⊕Gσ⊕Gσ=M.Our scheme accommodates approximate homomorphism [26], as long as the error term is bounded.


## 5. Security Proofs

### 5.1. Payload-Hiding Security

We prove the payload-hiding security of our scheme using the sequence-of-game approach [27]. Let c0,c1,…,cℓ be the challenge ciphertext given to the adversary in the payload-hiding game. Besides, let R0 be a random element in 0,1m and let R1,…,Rℓ be random elements in ℛ. We define the following hybrid games differing in what challenge ciphertext is sent to the adversary:(i)
Game0. The challenge ciphertext is c0,c1,…,cℓ. It is identical to the original payload-hiding game defined in Section 3.2.(ii)
Gamei,1≤i≤ℓ. The challenge ciphertext is c0,R1,…,Ri,ci+1,…,cℓ.(iii)
Gameℓ+1. The challenge ciphertext is R0,R1,…,Rℓ.We remark that the challenge ciphertext inGameℓ+1 leaks no information about the encrypted message, since it is composed of ℓ+1 random elements, whereas the challenge ciphertext in Game0 is well formed. Therefore, the advantage of the adversary in the last game is 0. We then prove the indistinguishability between the adjacent games in the following lemmas.Lemma 1.
If the underlying PRFF is secure, then Gamek−1 is indistinguishable from Gamek, for k=1,…,ℓ.Proof.
Suppose that there is an adversaryA that is able to distinguish Gamek−1 from Gamek with a nonnegligible advantage. Then we can build a challenger C1 to distinguish the experiment EXP0 from the experiment EXP1 shown in Section 2. After invoking the experiment EXPb and receiving the description of the PRF F, the challenger C1 simulates a hybrid game for an adversary A as follows:
Setup. The challenger first randomly chooses a1,…,ak−1,ak+1,…,aℓ from ℛ and h from X and a pseudorandom generator G and then sends pp=F,G to the adversary. Next, the challenger makes a Challenge query with h to the underlying experiment and obtains f as the response. The value of f will be used in the later simulation for KeyGen and Encryption Oracle.
Query Phase 1. In this phase, the adversary is allowed to make polynomially many queries to the following oracles.(i)
KeyGen Oracle: taking as inputs a vectory=y1,…,yℓ∈ℛℓ, the challenger computes(11)sky=∑j=1y1Fa1,h+⋯+∑j=1yk−1Fak−1,h+∑j=1ykf+∑j=1yk+1Fak+1,h+⋯+∑j=1yℓFaℓ,h=∑i=1i≠kℓyiFai,h+ykf,and returnssky to the adversary. By implicitly setting aj to the chosen key of the underlying experiment, it is easy to verify that sky is a valid secret key for y.(ii)
Encryption Oracle: taking as inputs a vectorx=x1,…,xℓ∈ℛℓ and a message M, the challenger performs as follows:(1)
Randomly chooseδ,σ from ℛ.(2)
Computeck=F∑j=1δxk,h+f+σ=Fδxk,h+f+σ.(3)
Fori=1,…,k−1,k+1,…,ℓ, compute ci the same as in the Encrypt algorithm since the challenger knows a1,…,ak−1,ak+1,…,aℓ,h.(4)
Computec0=M⊕Gσ.(5)
Returnctx=c0,c1,…,cℓ.
Challenge. The adversary submits two messages M0,M1 with the same length and a vector x∗=x1∗,…,xℓ∗, such that x∗,y≠0 for all y queried to KeyGen Oracle. After receiving x∗,M0,M1, the challenger randomly chooses β⟵$0,1 and then can compute the challenge ciphertext ct∗ as follows:(1)
Randomly chooseδ,σ from ℛ.(2)
Fori=1,…,ℓ,(i)
ifi<k, choose a random element Ri⟵$ℛ and set ci=Ri.(ii)
ifi=k, compute(12)ck=F∑j=1δxk∗,h+f+σ=Fδxk∗,h+f+σ.(iii)
ifi>k, compute ci the same way as that in the scheme since the challenger knows ak+1,…,aℓ and h.(3)
Computec0=Mβ⊕Gσ.(4)
Returnct∗=c0,c1,…,cℓ.
Query Phase 2. It is the same as Query Phase 1 except that the adversary is not allowed to make a query to KeyGen Oracle with y such that x∗,y=0.
Guess. The adversary outputs a bit β′. Then the challenger outputs 1 if β′=β and 0 otherwise. Before analyzing the advantages of the challenger in breaking the underlying PRF, we first discuss that the outputs of the oracles are well formed, no matter which experiment the challenger interacts with. Let Si be the event where the adversary makes a right guess in Gamei. First, if the challenger is actually interacting with the experiment EXP0, then f is a random element in ℛ. In this case, the answer to a KeyGen Oracle,(13)sky=∑i=1i≠kℓyiFai,h+ykf,is an element of ℛ and the answer to an Encryption query c0,c1,…,cℓ is a vector in 0,1m×ℛℓ, and(14)∑i=1ℓyi⋅ci−sky=∑i=1i≠kℓyiFδxi+ai,h+σ+ykFδxk,h+f+σ−∑i=1i≠kℓyiFai,h+ykf=∑i=1ℓyiFδxi,h+∑i=1ℓσ=Fδ∑i=1ℓxiyi,h+∑i=1ℓσ=∑i=1ℓσ⟺x,y=0.
Therefore, the answers to KeyGen and Encryption queries are well formed.
Next, we analyze the advantage ofC1 in breaking the underlying PRF. First, if the challenger is interacting with the experiment EXP0, then f is a random element in ℛ. Thus, c1,…,ck in the challenge ciphertext are random elements, and thus we are in Gamek. Thus, the probability that the challenger outputs 1 is(15)PrSk=PrC1outputs1=Prβ′=β=PrW0.
Second, if the challenger is interacting with the experimentEXP1, then f is the output of the PRF with input h. By implicitly setting the encryption key component ak as the chosen key of the underlying experiment, we have f=Fak,h, and thus the challenger answers the KeyGen and Encryption queries correctly. As for the challenge ciphertext, we have that(16)ck=F∑j=1δxk∗,h+f+σ=Fδxk∗,h+Fak,h+σ=Fδxk∗+ak,h+σ,is a valid ciphertext component. Since c1,…,ck−1 are random elements from ℛ, we are in Gamek−1. In this case, the probability that the challenger outputs 1 is(17)PrSk−1=PrC1outputs1=Prβ′=β=PrW1.
Finally, combining the above two cases, we have that(18)PrSk−1−PrSk=PrW1−PrW0=AdvC1PRF1λ,and hence, Gamek−1 is indistinguishable from Gamek, if the underlying pseudorandom function is secure, for k=1,…,ℓ.Lemma 2.
If the underlying PRGG is secure, then Gameℓ is indistinguishable from Gameℓ+1.Proof.
Given the description of the PRGG and a challenge ψ∈0,1m, the challenger C2 simulates the following hybrid game for an adversary A:Setup. The challenger first chooses a key-homomorphic pseudorandom function F:ℛ×X⟶ℛ, a1,…,aℓ from ℛ and h from X and then sends F,G to the adversary.Query Phase 1. The challenger is able to answer the KeyGen (Encryption, resp.) queries by following the KeyGen (Encrypt, resp.) algorithms to generate the secret keys sky (ciphertexts ctx, resp.), since the challenger knows the secret key SK=a1,…,aℓ,h.Challenge. The adversary submits two messages M0,M1 with the same length and a vector x∗, such that x∗,y≠0 for all y queried to KeyGen Oracle. After receiving x∗,M0,M1, the challenger randomly chooses β⟵$0,1 and then can compute the challenge ciphertext ct∗ as follows:(1)
Randomly chooseR1,…,Rℓ⟵$ℛ.(2)
Fori=1,…,ℓ, set ci=Ri.(3)
Computec0=Mβ⊕ψ.(4)
Return the challenge ciphertextct∗=c0,c1,…,cℓ.Query Phase 2. It is the same as Query Phase 1 except that the adversary is not allowed to make a query to KeyGen Oracle with y such that x∗,y=0.Guess. The adversary outputs a bit β′. Then, the challenger outputs 1 if β′=β. Let Si be the event where the adversary makes a right guess in Gamei. If the term ψ=Gσ is generated from the PRG G for some σ, then we are in Gameℓ, and we have(19)PrSℓ=PrC2ψ=Gσ=1.
Ifψ is randomly chosen from 0,1m, then we are in Gameℓ+1, and we have(20)PrSℓ+1=PrC2ψ⟵$0,1m=1.
Finally, we have that(21)PrSℓ−PrSℓ+1=PrC2ψ=Gσ=1−PrC2ψ⟵$0,1m=1=AdvC2PRG1λis negligible.Theorem 1.
The proposed private IPE scheme achieves payload-hiding, if the underlying pseudorandom function is key-homomorphic and secure and the pseudorandom generator is secure.Proof.
By combining Lemmas1 and 2, we have(22)PrS0−PrSℓ+1=∑i=1ℓPrSi−1−PrSi+PrSℓ−PrSℓ+1≤PrS0−PrS1+⋯+PrSℓ−1−PrSℓ+PrSℓ−PrSℓ+1=AdvC1PRF1λ+⋯+AdvC1PRF1λ︸ℓ+AdvC2PRG1λ=ℓ⋅AdvC1PRF1λ+AdvC2PRG1λ.
Note thatPrS0=AdvAPH1λ since Game0 is the payload-hiding game, and PrSℓ+1=0 since ct∗ leaks no information about the encrypted message in Gameℓ+1. Therefore, for any PPT adversary A, there exist algorithms C1,C2 such that(23)AdvAPH1λ=PrS0=PrS0−PrSℓ+1≤ℓ⋅AdvC1PRF1λ+AdvC2PRG1λ.is negligible.


### 5.2. Attribute-Hiding Security

We then prove that our scheme achieves attribute-hiding. The proof is similar to the proof for payload-hiding security, and hence we will omit some content to avoid the unnecessary redundancy. Letc0,c1,…,cℓ be the challenge ciphertext given to the adversary in the attribute-hiding game. Besides, let R1,…,Rℓ be random elements in ℛ and let R0 be a random element in 0,1m. We define the following hybrid games differing in what challenge ciphertext is sent to the adversary:(i)
Game0. The challenge ciphertext is c0,c1,…,cℓ. It is identical to the original attribute-hiding game defined in Section 3.2.(ii)
Gamei,1≤i≤ℓ. The challenge ciphertext is c0,R1,…,Ri,ci+1,…,cℓ.(iii)
Gameℓ+1. The challenge ciphertext is R0,R1,…,Rℓ.In the last game, the challenge ciphertext is composed ofℓ+1 random elements, and hence the adversary obtains no information about the attribute vector from the challenge ciphertext. We then prove that the adjacent games are indistinguishable in the following lemmas.Lemma 3.
If the underlying PRFF is secure, then Gamek−1 is indistinguishable from Gamek, for k=1,…,ℓ.Proof.
Suppose that there is an adversaryA that is able to distinguish Gamek−1 from Gamek with a nonnegligible advantage. Then we can build a challenger C3 to distinguish the experiment EXP0 from the experiment EXP1 shown in Section 2. After invoking the experiment EXPb and receiving the description of the PRF F, the challenger C1 simulates a hybrid game for an adversary A as follows.
For Setup, Query Phase 1, Query Phase 2, and Guess, the challenger performs the same as in the proof of Lemma1.
For Challenge phase, after receivingx0=x10,…,xℓ0,x1=x11,…,xℓ1, and M from the adversary, where(24)x0,y=0=x1,yorx0,y≠0≠x1,y,for all y queried to KeyGen Oracle in Query Phase 1, the challenger performs as follows:(1)
Randomly chooseβ⟵$0,1.(2)
Randomly chooseδ,σ from ℛ.(3)
Fori=1,…,ℓ,(i)
ifi<k, choose a random element Ri⟵$ℛ and set ci=Ri.(ii)
ifi=k, compute the following.(25)ck=F∑j=1δxkβ,h+f+σ=Fδxkβ,h+f+σ.(iii)
ifi>k, compute ci the same way as that in the scheme since the challenger knows ak+1,…,aℓ and h.(4)
Computec0=M⊕Gσ.(5)
Returnct∗=c0,c1,…,cℓ.
The analysis of the correctness of the simulation is similar to that in the proof of Lemma1. Let Si be the event where the adversary makes a right guess in Gamei. If f from the PRF game is a random element in ℛ, then we are in Gamek; otherwise, we are in Gamek−1. Therefore, we have(26)PrSk−1−PrSk=PrW1−PrW0=AdvC3PRF1λ.
That is,Gamek is indistinguishable from Gamek−1, if the underlying pseudorandom function is secure, for k=1,…,ℓ.Lemma 4.
If the underlying PRGG is secure, then Gameℓ is indistinguishable from Gameℓ+1.Proof.
The proof of this lemma is similar to the proof of Lemma2, with the only difference being that the challenger received two vectors x0,x1 with a message M; in Lemma 2, the challenger received two messages M0,M1 with a vector x∗ from the adversary.
Given the description of the PRGG and a challenge ψ∈0,1m, the challenger C4 simulates the following hybrid game for an adversary A.
For Setup, Query Phase 1, Query Phase 2, and Guess, the challenger performs the same as in the proof of Lemma1.
For Challenge phase, after receivingx0,x1, and M from the adversary, where(27)x0,y=0=x1,yorx0,y≠0≠x1,y,for all y queried to KeyGen Oracle in Query Phase 1, the challenger performs as follows:(1)
Randomly chooseR1,…,Rℓ⟵$ℛ.(2)
Fori=1,…,ℓ, set ci=Ri.(3)
Computec0=M⊕ψ.(4)
Return the challenge ciphertextct∗=c0,c1,…,cℓ.
The analysis of the correctness of the simulation is similar to that in the proof of Lemma3. Let Si be the event where the adversary makes a right guess in Gamei. If ψ from the PRG game is a random element in 0,1m, then we are in Gameℓ+1; otherwise, we are in Gameℓ. Therefore, we have that(28)PrSℓ−PrSℓ+1=PrC4ψ=Gσ=1−PrC4ψ⟵$0,1m=1=AdvC4PRG1λ,is negligible. That is, Gameℓ is indistinguishable from Gameℓ+1, if the underlying pseudorandom generator is secure.Theorem 2.
The proposed private IPE scheme achieves attribute-hiding, if the underlying pseudorandom function is key-homomorphic and secure and the pseudorandom generator is secure.Proof.
By combining Lemma3 and Lemma 4, we have(29)PrS0−PrSℓ+1=∑i=1ℓPrSi−1−PrSi+PrSℓ−PrSℓ+1≤PrS0−PrS1+⋯+PrSℓ−1−PrSℓ+PrSℓ−PrSℓ+1=AdvC3PRF1λ+⋯+AdvC3PRF1λ︸ℓ+AdvC4PRG1λ=ℓ⋅AdvC3PRF1λ+AdvC4PRG1λ.
Note thatPrS0=AdvAAH1λ since Game0 is the attribute-hiding game, and PrSℓ+1=0 since ct∗ leaks no information about the encrypted message in Gameℓ+1. Therefore, for any PPT adversary A, there exist algorithms C3,C4 such that(30)AdvAAH1λ=PrS0=PrS0−PrSℓ+1≤ℓ⋅AdvC3PRF1λ+AdvC4PRG1λis negligible.


### 5.3. Predicate-Hiding Security

We first give the intuition for the proof. Lety1,y2,…,yℓ denote the challenge secret key generated using the vector y1,y2,…,yℓ. Besides, let y0=y10,y20,…,yℓ0,y1=y11,y21,…,yℓ1 be the two vectors sent from the adversary in the Challenge phase. To prove the indistinguishability between the cases y10,y20,…,yℓ0 and y11,y21,…,yℓ1 given to the adversary, we define a sequence of games below and show the indistinguishability of any two adjacent games. Each game differs in the challenge secret key given to the adversary. Let y1′,y2′,…,yℓ′ be random elements from ℛ.Game0,i: y1′,y2′,…,yk−1′,yk0,…,yℓ0 is given (k=1,…,ℓ)Game1,i: y1′,y2′,…,yk−1′,yk1,…,yℓ1 is given (k=1,…,ℓ)Note thatGame0,ℓ and Game1,ℓ are identical, and Game0,0 and Game1,0 are the games where y10,…,yℓ0 and y11,…,yℓ1 are given to the adversary, respectively. We then give the following lemma to prove that(31)Game0,0≈Game0,1≈⋯≈Game0,ℓ≈Game1,ℓ≈⋯Game1,1≈⋯≈Game1,0.Lemma 5.
If the underlying PRFF is secure, then Game0,k−1 and Game0,k are indistinguishable, for k=1,…,ℓ.Proof.
Suppose that there is an adversaryA which is able to distinguish Gamek−1 from Gamek with a nonnegligible advantage. Then we can build a challenger C to distinguish the experiment EXP0 from EXP1 shown in Section 2. After invoking the experiment EXPb and receiving the description of the PRF F, the challenger C simulates a hybrid game for an adversary A as follows.
For Setup, Query Phase 1, Query Phase 2, and Guess, the challenger performs the same as in the proof of Lemma1.
For Challenge phase, after receivingy0=y10,…,yℓ0,y1=y11,…,yℓ1 from the adversary, where(32)x,y0=0=x,y1orx,y0≠0≠x,y1,for all x queried to Encrypt Oracle in Query Phase 1, the challenger performs as follows.(1)
Randomly choosey1′,y2′,…,yk−1′ from ℛ.(2)
Compute(33)sk∗=∑j=1y1′Fa1,h+…+∑j=1yk−1′Fak−1,h+∑j=1yk0f+∑j=1yk+10Fak+1,h+⋯+∑j=1yℓ0Faℓ,h.(3)
Returnsk∗.
If the challenger is interacting with the experimentEXP1, then f is the output of the PRF with input h. By implicitly setting the encryption key component ak as the chosen key of the underlying experiment, we have f=Fak,h, and thus we have(34)sk∗=y1′Fa1,h+⋯+yk−1′Fak−1,h+yk0Fak,h+yk+10Fak+1,h+⋯+yℓ0Faℓ,h=y1′,…,yk−1′,yk0,…,yℓ0,and thus we are in Gamek−1. Otherwise, f is a random element in ℛ; then we can rewrite f=Fak,h+R˜ for some random element R˜∈ℛ. Besides, there must exist an element y˜ such that R˜=yk0−1y˜Fak,h. By implicitly setting yk′=yk0+y˜, we have(35)∑i=1yk0f=yk0f=yk0Fak,h+R˜=yk0Fak,h+yk0yk0−1y˜Fak,h=yk0Fak,h+y˜Fak,h=yk0+y˜Fak,h=yk′Fak,h.
Sincef is a random element in ℛ, yk′ is also a random element in ℛ. That means sk∗=y1′,…,yk′,yk+10,…,yℓ0, and thus we are in Gamek. Let Si be the event where the adversary makes a right guess in Gamei. Therefore, we have(36)PrSk−1−PrSk=PrW1−PrW0=AdvCPRF1λ.
That is,Gamek is indistinguishable from Gamek−1, if the underlying PRF is secure, for k=1,…,ℓ.Theorem 3.
The proposed private IPE scheme achieves predicate-hiding, if the underlying pseudorandom function is key-homomorphic and secure and the pseudorandom generator is secure.Proof.
The proof for the indistinguishability betweenGame1,k−1 and Game1,k is the same as that for the indistinguishability between Game0,k−1 and Game0,k, due to the symmetry of the game sequence. This completes the proof of the predicate-hiding.


## 5.1. Payload-Hiding Security

We prove the payload-hiding security of our scheme using the sequence-of-game approach [27]. Let c0,c1,…,cℓ be the challenge ciphertext given to the adversary in the payload-hiding game. Besides, let R0 be a random element in 0,1m and let R1,…,Rℓ be random elements in ℛ. We define the following hybrid games differing in what challenge ciphertext is sent to the adversary:(i)
Game0. The challenge ciphertext is c0,c1,…,cℓ. It is identical to the original payload-hiding game defined in Section 3.2.(ii)
Gamei,1≤i≤ℓ. The challenge ciphertext is c0,R1,…,Ri,ci+1,…,cℓ.(iii)
Gameℓ+1. The challenge ciphertext is R0,R1,…,Rℓ.We remark that the challenge ciphertext inGameℓ+1 leaks no information about the encrypted message, since it is composed of ℓ+1 random elements, whereas the challenge ciphertext in Game0 is well formed. Therefore, the advantage of the adversary in the last game is 0. We then prove the indistinguishability between the adjacent games in the following lemmas.Lemma 1.
If the underlying PRFF is secure, then Gamek−1 is indistinguishable from Gamek, for k=1,…,ℓ.Proof.
Suppose that there is an adversaryA that is able to distinguish Gamek−1 from Gamek with a nonnegligible advantage. Then we can build a challenger C1 to distinguish the experiment EXP0 from the experiment EXP1 shown in Section 2. After invoking the experiment EXPb and receiving the description of the PRF F, the challenger C1 simulates a hybrid game for an adversary A as follows:
Setup. The challenger first randomly chooses a1,…,ak−1,ak+1,…,aℓ from ℛ and h from X and a pseudorandom generator G and then sends pp=F,G to the adversary. Next, the challenger makes a Challenge query with h to the underlying experiment and obtains f as the response. The value of f will be used in the later simulation for KeyGen and Encryption Oracle.
Query Phase 1. In this phase, the adversary is allowed to make polynomially many queries to the following oracles.(i)
KeyGen Oracle: taking as inputs a vectory=y1,…,yℓ∈ℛℓ, the challenger computes(11)sky=∑j=1y1Fa1,h+⋯+∑j=1yk−1Fak−1,h+∑j=1ykf+∑j=1yk+1Fak+1,h+⋯+∑j=1yℓFaℓ,h=∑i=1i≠kℓyiFai,h+ykf,and returnssky to the adversary. By implicitly setting aj to the chosen key of the underlying experiment, it is easy to verify that sky is a valid secret key for y.(ii)
Encryption Oracle: taking as inputs a vectorx=x1,…,xℓ∈ℛℓ and a message M, the challenger performs as follows:(1)
Randomly chooseδ,σ from ℛ.(2)
Computeck=F∑j=1δxk,h+f+σ=Fδxk,h+f+σ.(3)
Fori=1,…,k−1,k+1,…,ℓ, compute ci the same as in the Encrypt algorithm since the challenger knows a1,…,ak−1,ak+1,…,aℓ,h.(4)
Computec0=M⊕Gσ.(5)
Returnctx=c0,c1,…,cℓ.
Challenge. The adversary submits two messages M0,M1 with the same length and a vector x∗=x1∗,…,xℓ∗, such that x∗,y≠0 for all y queried to KeyGen Oracle. After receiving x∗,M0,M1, the challenger randomly chooses β⟵$0,1 and then can compute the challenge ciphertext ct∗ as follows:(1)
Randomly chooseδ,σ from ℛ.(2)
Fori=1,…,ℓ,(i)
ifi<k, choose a random element Ri⟵$ℛ and set ci=Ri.(ii)
ifi=k, compute(12)ck=F∑j=1δxk∗,h+f+σ=Fδxk∗,h+f+σ.(iii)
ifi>k, compute ci the same way as that in the scheme since the challenger knows ak+1,…,aℓ and h.(3)
Computec0=Mβ⊕Gσ.(4)
Returnct∗=c0,c1,…,cℓ.
Query Phase 2. It is the same as Query Phase 1 except that the adversary is not allowed to make a query to KeyGen Oracle with y such that x∗,y=0.
Guess. The adversary outputs a bit β′. Then the challenger outputs 1 if β′=β and 0 otherwise. Before analyzing the advantages of the challenger in breaking the underlying PRF, we first discuss that the outputs of the oracles are well formed, no matter which experiment the challenger interacts with. Let Si be the event where the adversary makes a right guess in Gamei. First, if the challenger is actually interacting with the experiment EXP0, then f is a random element in ℛ. In this case, the answer to a KeyGen Oracle,(13)sky=∑i=1i≠kℓyiFai,h+ykf,is an element of ℛ and the answer to an Encryption query c0,c1,…,cℓ is a vector in 0,1m×ℛℓ, and(14)∑i=1ℓyi⋅ci−sky=∑i=1i≠kℓyiFδxi+ai,h+σ+ykFδxk,h+f+σ−∑i=1i≠kℓyiFai,h+ykf=∑i=1ℓyiFδxi,h+∑i=1ℓσ=Fδ∑i=1ℓxiyi,h+∑i=1ℓσ=∑i=1ℓσ⟺x,y=0.
Therefore, the answers to KeyGen and Encryption queries are well formed.
Next, we analyze the advantage ofC1 in breaking the underlying PRF. First, if the challenger is interacting with the experiment EXP0, then f is a random element in ℛ. Thus, c1,…,ck in the challenge ciphertext are random elements, and thus we are in Gamek. Thus, the probability that the challenger outputs 1 is(15)PrSk=PrC1outputs1=Prβ′=β=PrW0.
Second, if the challenger is interacting with the experimentEXP1, then f is the output of the PRF with input h. By implicitly setting the encryption key component ak as the chosen key of the underlying experiment, we have f=Fak,h, and thus the challenger answers the KeyGen and Encryption queries correctly. As for the challenge ciphertext, we have that(16)ck=F∑j=1δxk∗,h+f+σ=Fδxk∗,h+Fak,h+σ=Fδxk∗+ak,h+σ,is a valid ciphertext component. Since c1,…,ck−1 are random elements from ℛ, we are in Gamek−1. In this case, the probability that the challenger outputs 1 is(17)PrSk−1=PrC1outputs1=Prβ′=β=PrW1.
Finally, combining the above two cases, we have that(18)PrSk−1−PrSk=PrW1−PrW0=AdvC1PRF1λ,and hence, Gamek−1 is indistinguishable from Gamek, if the underlying pseudorandom function is secure, for k=1,…,ℓ.Lemma 2.
If the underlying PRGG is secure, then Gameℓ is indistinguishable from Gameℓ+1.Proof.
Given the description of the PRGG and a challenge ψ∈0,1m, the challenger C2 simulates the following hybrid game for an adversary A:Setup. The challenger first chooses a key-homomorphic pseudorandom function F:ℛ×X⟶ℛ, a1,…,aℓ from ℛ and h from X and then sends F,G to the adversary.Query Phase 1. The challenger is able to answer the KeyGen (Encryption, resp.) queries by following the KeyGen (Encrypt, resp.) algorithms to generate the secret keys sky (ciphertexts ctx, resp.), since the challenger knows the secret key SK=a1,…,aℓ,h.Challenge. The adversary submits two messages M0,M1 with the same length and a vector x∗, such that x∗,y≠0 for all y queried to KeyGen Oracle. After receiving x∗,M0,M1, the challenger randomly chooses β⟵$0,1 and then can compute the challenge ciphertext ct∗ as follows:(1)
Randomly chooseR1,…,Rℓ⟵$ℛ.(2)
Fori=1,…,ℓ, set ci=Ri.(3)
Computec0=Mβ⊕ψ.(4)
Return the challenge ciphertextct∗=c0,c1,…,cℓ.Query Phase 2. It is the same as Query Phase 1 except that the adversary is not allowed to make a query to KeyGen Oracle with y such that x∗,y=0.Guess. The adversary outputs a bit β′. Then, the challenger outputs 1 if β′=β. Let Si be the event where the adversary makes a right guess in Gamei. If the term ψ=Gσ is generated from the PRG G for some σ, then we are in Gameℓ, and we have(19)PrSℓ=PrC2ψ=Gσ=1.
Ifψ is randomly chosen from 0,1m, then we are in Gameℓ+1, and we have(20)PrSℓ+1=PrC2ψ⟵$0,1m=1.
Finally, we have that(21)PrSℓ−PrSℓ+1=PrC2ψ=Gσ=1−PrC2ψ⟵$0,1m=1=AdvC2PRG1λis negligible.Theorem 1.
The proposed private IPE scheme achieves payload-hiding, if the underlying pseudorandom function is key-homomorphic and secure and the pseudorandom generator is secure.Proof.
By combining Lemmas1 and 2, we have(22)PrS0−PrSℓ+1=∑i=1ℓPrSi−1−PrSi+PrSℓ−PrSℓ+1≤PrS0−PrS1+⋯+PrSℓ−1−PrSℓ+PrSℓ−PrSℓ+1=AdvC1PRF1λ+⋯+AdvC1PRF1λ︸ℓ+AdvC2PRG1λ=ℓ⋅AdvC1PRF1λ+AdvC2PRG1λ.
Note thatPrS0=AdvAPH1λ since Game0 is the payload-hiding game, and PrSℓ+1=0 since ct∗ leaks no information about the encrypted message in Gameℓ+1. Therefore, for any PPT adversary A, there exist algorithms C1,C2 such that(23)AdvAPH1λ=PrS0=PrS0−PrSℓ+1≤ℓ⋅AdvC1PRF1λ+AdvC2PRG1λ.is negligible.


## 5.2. Attribute-Hiding Security

We then prove that our scheme achieves attribute-hiding. The proof is similar to the proof for payload-hiding security, and hence we will omit some content to avoid the unnecessary redundancy. Letc0,c1,…,cℓ be the challenge ciphertext given to the adversary in the attribute-hiding game. Besides, let R1,…,Rℓ be random elements in ℛ and let R0 be a random element in 0,1m. We define the following hybrid games differing in what challenge ciphertext is sent to the adversary:(i)
Game0. The challenge ciphertext is c0,c1,…,cℓ. It is identical to the original attribute-hiding game defined in Section 3.2.(ii)
Gamei,1≤i≤ℓ. The challenge ciphertext is c0,R1,…,Ri,ci+1,…,cℓ.(iii)
Gameℓ+1. The challenge ciphertext is R0,R1,…,Rℓ.In the last game, the challenge ciphertext is composed ofℓ+1 random elements, and hence the adversary obtains no information about the attribute vector from the challenge ciphertext. We then prove that the adjacent games are indistinguishable in the following lemmas.Lemma 3.
If the underlying PRFF is secure, then Gamek−1 is indistinguishable from Gamek, for k=1,…,ℓ.Proof.
Suppose that there is an adversaryA that is able to distinguish Gamek−1 from Gamek with a nonnegligible advantage. Then we can build a challenger C3 to distinguish the experiment EXP0 from the experiment EXP1 shown in Section 2. After invoking the experiment EXPb and receiving the description of the PRF F, the challenger C1 simulates a hybrid game for an adversary A as follows.
For Setup, Query Phase 1, Query Phase 2, and Guess, the challenger performs the same as in the proof of Lemma1.
For Challenge phase, after receivingx0=x10,…,xℓ0,x1=x11,…,xℓ1, and M from the adversary, where(24)x0,y=0=x1,yorx0,y≠0≠x1,y,for all y queried to KeyGen Oracle in Query Phase 1, the challenger performs as follows:(1)
Randomly chooseβ⟵$0,1.(2)
Randomly chooseδ,σ from ℛ.(3)
Fori=1,…,ℓ,(i)
ifi<k, choose a random element Ri⟵$ℛ and set ci=Ri.(ii)
ifi=k, compute the following.(25)ck=F∑j=1δxkβ,h+f+σ=Fδxkβ,h+f+σ.(iii)
ifi>k, compute ci the same way as that in the scheme since the challenger knows ak+1,…,aℓ and h.(4)
Computec0=M⊕Gσ.(5)
Returnct∗=c0,c1,…,cℓ.
The analysis of the correctness of the simulation is similar to that in the proof of Lemma1. Let Si be the event where the adversary makes a right guess in Gamei. If f from the PRF game is a random element in ℛ, then we are in Gamek; otherwise, we are in Gamek−1. Therefore, we have(26)PrSk−1−PrSk=PrW1−PrW0=AdvC3PRF1λ.
That is,Gamek is indistinguishable from Gamek−1, if the underlying pseudorandom function is secure, for k=1,…,ℓ.Lemma 4.
If the underlying PRGG is secure, then Gameℓ is indistinguishable from Gameℓ+1.Proof.
The proof of this lemma is similar to the proof of Lemma2, with the only difference being that the challenger received two vectors x0,x1 with a message M; in Lemma 2, the challenger received two messages M0,M1 with a vector x∗ from the adversary.
Given the description of the PRGG and a challenge ψ∈0,1m, the challenger C4 simulates the following hybrid game for an adversary A.
For Setup, Query Phase 1, Query Phase 2, and Guess, the challenger performs the same as in the proof of Lemma1.
For Challenge phase, after receivingx0,x1, and M from the adversary, where(27)x0,y=0=x1,yorx0,y≠0≠x1,y,for all y queried to KeyGen Oracle in Query Phase 1, the challenger performs as follows:(1)
Randomly chooseR1,…,Rℓ⟵$ℛ.(2)
Fori=1,…,ℓ, set ci=Ri.(3)
Computec0=M⊕ψ.(4)
Return the challenge ciphertextct∗=c0,c1,…,cℓ.
The analysis of the correctness of the simulation is similar to that in the proof of Lemma3. Let Si be the event where the adversary makes a right guess in Gamei. If ψ from the PRG game is a random element in 0,1m, then we are in Gameℓ+1; otherwise, we are in Gameℓ. Therefore, we have that(28)PrSℓ−PrSℓ+1=PrC4ψ=Gσ=1−PrC4ψ⟵$0,1m=1=AdvC4PRG1λ,is negligible. That is, Gameℓ is indistinguishable from Gameℓ+1, if the underlying pseudorandom generator is secure.Theorem 2.
The proposed private IPE scheme achieves attribute-hiding, if the underlying pseudorandom function is key-homomorphic and secure and the pseudorandom generator is secure.Proof.
By combining Lemma3 and Lemma 4, we have(29)PrS0−PrSℓ+1=∑i=1ℓPrSi−1−PrSi+PrSℓ−PrSℓ+1≤PrS0−PrS1+⋯+PrSℓ−1−PrSℓ+PrSℓ−PrSℓ+1=AdvC3PRF1λ+⋯+AdvC3PRF1λ︸ℓ+AdvC4PRG1λ=ℓ⋅AdvC3PRF1λ+AdvC4PRG1λ.
Note thatPrS0=AdvAAH1λ since Game0 is the attribute-hiding game, and PrSℓ+1=0 since ct∗ leaks no information about the encrypted message in Gameℓ+1. Therefore, for any PPT adversary A, there exist algorithms C3,C4 such that(30)AdvAAH1λ=PrS0=PrS0−PrSℓ+1≤ℓ⋅AdvC3PRF1λ+AdvC4PRG1λis negligible.


## 5.3. Predicate-Hiding Security

We first give the intuition for the proof. Lety1,y2,…,yℓ denote the challenge secret key generated using the vector y1,y2,…,yℓ. Besides, let y0=y10,y20,…,yℓ0,y1=y11,y21,…,yℓ1 be the two vectors sent from the adversary in the Challenge phase. To prove the indistinguishability between the cases y10,y20,…,yℓ0 and y11,y21,…,yℓ1 given to the adversary, we define a sequence of games below and show the indistinguishability of any two adjacent games. Each game differs in the challenge secret key given to the adversary. Let y1′,y2′,…,yℓ′ be random elements from ℛ.Game0,i: y1′,y2′,…,yk−1′,yk0,…,yℓ0 is given (k=1,…,ℓ)Game1,i: y1′,y2′,…,yk−1′,yk1,…,yℓ1 is given (k=1,…,ℓ)Note thatGame0,ℓ and Game1,ℓ are identical, and Game0,0 and Game1,0 are the games where y10,…,yℓ0 and y11,…,yℓ1 are given to the adversary, respectively. We then give the following lemma to prove that(31)Game0,0≈Game0,1≈⋯≈Game0,ℓ≈Game1,ℓ≈⋯Game1,1≈⋯≈Game1,0.Lemma 5.
If the underlying PRFF is secure, then Game0,k−1 and Game0,k are indistinguishable, for k=1,…,ℓ.Proof.
Suppose that there is an adversaryA which is able to distinguish Gamek−1 from Gamek with a nonnegligible advantage. Then we can build a challenger C to distinguish the experiment EXP0 from EXP1 shown in Section 2. After invoking the experiment EXPb and receiving the description of the PRF F, the challenger C simulates a hybrid game for an adversary A as follows.
For Setup, Query Phase 1, Query Phase 2, and Guess, the challenger performs the same as in the proof of Lemma1.
For Challenge phase, after receivingy0=y10,…,yℓ0,y1=y11,…,yℓ1 from the adversary, where(32)x,y0=0=x,y1orx,y0≠0≠x,y1,for all x queried to Encrypt Oracle in Query Phase 1, the challenger performs as follows.(1)
Randomly choosey1′,y2′,…,yk−1′ from ℛ.(2)
Compute(33)sk∗=∑j=1y1′Fa1,h+…+∑j=1yk−1′Fak−1,h+∑j=1yk0f+∑j=1yk+10Fak+1,h+⋯+∑j=1yℓ0Faℓ,h.(3)
Returnsk∗.
If the challenger is interacting with the experimentEXP1, then f is the output of the PRF with input h. By implicitly setting the encryption key component ak as the chosen key of the underlying experiment, we have f=Fak,h, and thus we have(34)sk∗=y1′Fa1,h+⋯+yk−1′Fak−1,h+yk0Fak,h+yk+10Fak+1,h+⋯+yℓ0Faℓ,h=y1′,…,yk−1′,yk0,…,yℓ0,and thus we are in Gamek−1. Otherwise, f is a random element in ℛ; then we can rewrite f=Fak,h+R˜ for some random element R˜∈ℛ. Besides, there must exist an element y˜ such that R˜=yk0−1y˜Fak,h. By implicitly setting yk′=yk0+y˜, we have(35)∑i=1yk0f=yk0f=yk0Fak,h+R˜=yk0Fak,h+yk0yk0−1y˜Fak,h=yk0Fak,h+y˜Fak,h=yk0+y˜Fak,h=yk′Fak,h.
Sincef is a random element in ℛ, yk′ is also a random element in ℛ. That means sk∗=y1′,…,yk′,yk+10,…,yℓ0, and thus we are in Gamek. Let Si be the event where the adversary makes a right guess in Gamei. Therefore, we have(36)PrSk−1−PrSk=PrW1−PrW0=AdvCPRF1λ.
That is,Gamek is indistinguishable from Gamek−1, if the underlying PRF is secure, for k=1,…,ℓ.Theorem 3.
The proposed private IPE scheme achieves predicate-hiding, if the underlying pseudorandom function is key-homomorphic and secure and the pseudorandom generator is secure.Proof.
The proof for the indistinguishability betweenGame1,k−1 and Game1,k is the same as that for the indistinguishability between Game0,k−1 and Game0,k, due to the symmetry of the game sequence. This completes the proof of the predicate-hiding.


## 6. Comparison and Analysis

To the best of our knowledge, although existing private IPE schemes [17–19] can resist payload-hiding, attribute-hiding, and predicate-hiding security, these schemes cannot resist quantum attacks because their security is based on discrete logarithm assumption. In this section, we compare our scheme with the existing private IPE schemes in terms of security properties and the size of master secret key, secret key, and ciphertext, as shown in Table 1.Table 1
Comparison with other related private IPE schemes [17–19]. Here, the length of ciphertext attribute and key attribute is n. G and m represent size of an element of G and message, respectively. MSK, SK, CT, Qun. Res., GSD, C3DH, and 3FCOBGA stand for master secret key, secret key for some key attribute, ciphertext for some ciphertext attribute, quantum-resistant, general subgroup decision, composite 3-party (decisional) Diffie-Hellman, and 3-factor-based composite-order bilinear groups assumption, respectively.
SSW09 [18]YKNS12 [19]KT13 [17]OursSecuritySelectiveSelectiveAdaptiveAdaptiveOrder ofGCompositeCompositePrime—AssumptionA variant of GSD, C3DH, DLIN3FCOBGADLINPRFMSK size4n+4G4n+4G5nGnlog2qSK size2n+2G2n+2G6nGlog2qCT size2n+2G2n+2G6nGm+nlog2qQun. Res.NoNoNoYes††If the underlying PRF is resistant to quantum attacks, then our proposed scheme is resistant to quantum attacks.The results show that our construction has higher security and efficiency in terms of secret key size because the size is not related to attribute length. In particular, the security of [18, 19] is only selective security; meanwhile that in [17] and our construction is adaptive security, making it more resistant to real attacks. In secret key size, our construction is of constant size, while the secret key sizes of [17–19] are linearly related to the key attribute length. In terms of ciphertext size, the encryption algorithm in schemes [17–19] only encrypts ciphertext predicate, while our proposed construction further encrypts message; therefore, the ciphertext size of our scheme is m+nlog2q, where m is the length of message. Finally, [17–19] are not resistant to quantum attacks, while our construction is resistant to quantum attacks if the underlying PRF is resistant to quantum attacks.


## 7. Conclusions and Future Works

With the development of cloud computing, the privacy of uploaded data needs to be concerned and protected. Private IPE is well suited to cloud computing scenario because it provides encryption for access control. In this paper, we propose a generic private IPE construction that achieves payload-hiding, attribute-hiding, and predicate-hiding security by utilizing specific key-homomorphic PRF. For future works, because the current construction requires that the key space and output space of the underlying key-homomorphic PRF beℤq, how to provide construction with less restriction is an open problem that remains to be solved.



---

*Source: 6678194-2021-02-12.xml*