# Public Key Encryption with Keyword Search from Lattices in Multiuser Environments

Authors: Daini Wu; Xiaoming Wang; Qingqing Gan
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

A public key encryption scheme with keyword search capabilities is proposed using lattices for applications in multiuser environments. The proposed scheme enables a cloud server to check if any given encrypted data contains certain keywords specified by multiple users, but the server would not have knowledge of the keywords specified by the users or the contents of the encrypted data, which provides data privacy as well as privacy for user queries in multiuser environments. It can be proven secure under the standard learning with errors assumption in the random oracle model.


---

## Body

## 1. Introduction

Cloud storage has established itself as a widely used service for businesses and individuals; however, it comes with inherent challenges including security risks, reliable data storage, and data accessibility. The fact that data owners lose full control over their data brings about concerns with regard to privacy, data integrity, and confidentiality. Data owners have no way to prevent unauthorized individuals or even the party hosting the cloud servers to access or tamper with their data. To ensure data confidentiality and privacy, any sensitive data would need to be encrypted before it is sent to a cloud sever. Unfortunately, data encryption greatly restricts the ability of cloud servers to handle user access requests. A typical example is that of an encrypted document; the encryption changes the contents of the document, making it very hard to search/sort documents using keywords.To resolve this problem, the notion of the public key encryption with keyword search (PEKS) was proposed by Boneh et al. [1]. The construction of this scheme was inspired by identity-based encryption (IBE) and aims to allow a user to search for encrypted keywords without decryption. In the PEKS scheme, a sender uploads an encrypted email to a server along with an encrypted list of keywords. The receiver sends the desired keyword (denoted as a trapdoor) to the email server, which then tests the encrypted emails for the presence of this trapdoor. Soon afterwards, Waters et al. [2] demonstrated that a PEKS scheme can be used in a wide range of practical applications such as building encrypted and searchable audit logs. Subsequently, many intuitions have been proposed to improve upon this construction (e.g., [3–8]).The security of most PEKS schemes and their variants are based on the hard problems of number theory such as large integer factorization, the discrete logarithm problem, and bilinear mapping with the Diffie-Hellman problems. However, Shor [9] has discovered a function which can effectively solve the discrete logarithm problem, as well as an algorithm for quantum factoring. This means that quantum computers are a threat to the security of these cryptosystems.One possible solution that has undergone rapid development in recent years is lattice-based cryptographic schemes. So far, there has been no quantum algorithm which can effectively solve this class of problems, which makes them an attractive candidate for robust encryption. Ajtai [10] first presented the proof of the hardness of lattice problems, and following this work, many new constructions with lattices have been proposed (e.g., [11–14]). However, there have only been two PEKS schemes from lattices proposed in the literature so far, and these schemes were constructed in a single-user environment. Notably, there is currently no similar work available in the literature for PEKS scheme, which means that there is no a PEKS system constructed using lattices in multiuser environment. It is very clear that the schemes proposed for use in a single-user environment cannot be directly and effectively used in multiuser environments because of the increased requirements of the latter. In PEKS schemes constructed in a single-user environment, data owner can only share his data with a single user and also only permit a single user to search for the encrypted keywords on the encrypted data. While in multiuser environments, such as cloud storage, data owners hope to share their data with multiple users and also permit the multiple users to search over the owner’s shared data on the cloud server side. Therefore, PEKS schemes constructed in a single-user environment can not satisfy the characteristics of cloud environment.In order to solve this problem, a public key encryption scheme with keyword search is proposed using lattices for applications in multiuser environments, which is called PEKSL scheme. In the proposed scheme, cloud server can translate a keyword encrypted under one public key into the same keyword encrypted under another public key, so that it checks if any given encrypted data contains certain keywords specified by multiple users but learns nothing else about the data. This provides data privacy as well as privacy for user queries in multiuser environments. Furthermore, it can be proven secure under the hardness of the standard learning with errors problem in the random oracle model.


### 1.1. Related Work

To enable users search over encrypted outsourced data through keywords without decrypting the data at first, the notion of public key encryption with keyword search (PEKS) was first put forth by Boneh et al. [1] and its construction makes use of the construction of identity-based encryption (IBE). This construction was later improved by several schemes using the bilinear pairing. Waters et al. [2] demonstrated that these PEKS schemes could be useful to build encrypted and searchable audit logs. Abdalla et al. [4] presented an improved universal transformation from anonymous IBE to PEKS, and Baek et al. [6] proposed a PEKS scheme with a designated server to remove a secure channel. Golle et al. [3] defined the first security model for conducting conjunctive keyword searches to achieve a combinable multikeyword search. Subsequently, Boneh and Waters [5] extended the PEKS scheme to support conjunctive, subset, and range comparisons over the supplied keywords. Camenisch et al. [7] proposed oblivious generation of the keyword search trapdoor to maintain the privacy of the keyword against a curious trapdoor generator, and Cao et al. [8] presented ranked searches using multikeywords over encrypted cloud data and established a variety of privacy requirements.Nowadays, lattice-based cryptographic schemes have a more fast development, and many new constructions with lattices have been proposed. Ajtai [10] first presented the proof of the hardness of lattice problems, and following this work, many new constructions with lattices have been proposed. These include group signature schemes (e.g., [11, 12]), hierarchical identity-based encryption schemes (e.g., [13, 14]), broadcast encryption on lattice schemes (e.g., [15, 16]), attribute-based encryption (e.g., [17]), and fully homomorphic encryption schemes (e.g., [18, 19]). Notably, there were only two public key encryption with keyword search schemes from lattice [20, 21] so far in the literature, and their schemes were constructed in a single-user environment.


### 1.2. Paper Organization

The following sections are described briefly as follows. We review the basic concepts about integer lattices, discrete Gaussians, learning with errors problem, the formal models, and a security model of PEKSL in Section2. We give the specific construction about the PEKSL in a multiuser environment and then prove our scheme under the security model in Section 3. Finally, we conclude this paper in Conclusion.


## 1.1. Related Work

To enable users search over encrypted outsourced data through keywords without decrypting the data at first, the notion of public key encryption with keyword search (PEKS) was first put forth by Boneh et al. [1] and its construction makes use of the construction of identity-based encryption (IBE). This construction was later improved by several schemes using the bilinear pairing. Waters et al. [2] demonstrated that these PEKS schemes could be useful to build encrypted and searchable audit logs. Abdalla et al. [4] presented an improved universal transformation from anonymous IBE to PEKS, and Baek et al. [6] proposed a PEKS scheme with a designated server to remove a secure channel. Golle et al. [3] defined the first security model for conducting conjunctive keyword searches to achieve a combinable multikeyword search. Subsequently, Boneh and Waters [5] extended the PEKS scheme to support conjunctive, subset, and range comparisons over the supplied keywords. Camenisch et al. [7] proposed oblivious generation of the keyword search trapdoor to maintain the privacy of the keyword against a curious trapdoor generator, and Cao et al. [8] presented ranked searches using multikeywords over encrypted cloud data and established a variety of privacy requirements.Nowadays, lattice-based cryptographic schemes have a more fast development, and many new constructions with lattices have been proposed. Ajtai [10] first presented the proof of the hardness of lattice problems, and following this work, many new constructions with lattices have been proposed. These include group signature schemes (e.g., [11, 12]), hierarchical identity-based encryption schemes (e.g., [13, 14]), broadcast encryption on lattice schemes (e.g., [15, 16]), attribute-based encryption (e.g., [17]), and fully homomorphic encryption schemes (e.g., [18, 19]). Notably, there were only two public key encryption with keyword search schemes from lattice [20, 21] so far in the literature, and their schemes were constructed in a single-user environment.


## 1.2. Paper Organization

The following sections are described briefly as follows. We review the basic concepts about integer lattices, discrete Gaussians, learning with errors problem, the formal models, and a security model of PEKSL in Section2. We give the specific construction about the PEKSL in a multiuser environment and then prove our scheme under the security model in Section 3. Finally, we conclude this paper in Conclusion.


## 2. Preliminaries

We describe some preliminaries and other useful concepts that are used in our approach in this section.


### 2.1. Integer Lattices

Definition 1 (see [20]).
Givenn linearly independent vectors b1,b2,…,bn∈Rm, the lattice Λ generated by them is denoted L(b1,b2,…,bn) and define (1)Lb1,b2,…,bn=∑i=1nxibi∣xi∈Z.The vectors (b1,b2,…,bn) are called the basis of lattice.
For primeq and A∈Zqn×m and u∈Zqn, define (2)Λq⊥A=e∈Zm∣A·e=0mod⁡q,ΛquA=e∈Zm∣A·e=umod⁡q.


### 2.2. The Gram-Schmidt Norm of Basis

LetS~=s~1,s~2,…,s~k⊂Rm denote the Gram-Schmidt orthogonalization of the set of linearly independent vectors S=s1,s2,…,sk in Rm. It is defined as follows: s~1=s1 and s~1 is the component of si orthogonal to span (s1,s2,…,si), where 2≤i≤k. We refer to S~ as the Gram-Schmidt norm of S.Lemma 2 (see [14]).
LetΛ be an m-dimensional lattices. There is a deterministic polynomial-algorithm that, given an arbitrary basis of Λ and a full-rank set S=s1,s2,…,sm in Λ, returns a basis T of Λ satisfying (3)T≤S~,T≤Sm2.Theorem 3 (see [22]).
Letn and m be positive integers and let q be a prime, with q≥3 and m=6nlog2⁡q; there is a probabilistic polynomial time algorithm TrapGen(q,n) that outputs a pair (A∈Zqn×m,TA∈Zqm×m) such that A is statistically close to a uniform matrix in Zqn×m and TA is a basis for Λq⊥(A) satisfying (4)T~A≤Onlog2⁡q,TA≤Onlog2⁡qwith all but negligible probability in n.


### 2.3. Discrete Gaussians

Definition 4.
Choose a subsetL⊆Zm. For any positive parameter σ∈R>0 and any vector c∈Rm define (5)ρσ,cx=exp⁡-πx-c2σ2,ρσ,cL=∑x∈Lρσ,cx.The discrete Gaussians distribution over L with parameter σ and center c is (6)DL,σ,cy=ρσ,cyρσ,cL,∀y∈L.Lemma 5 (see [23]).
Letq≥2 and A be a matrix in Zqn×m with m>n. Let TA be a basis for Λq⊥(A) and σ≥T~Aωlog⁡m. Then for c∈Rm and u∈Zqn, (i)
there is a PPT algorithmSampleGaussian(A,TA,σ,c) that returns x∈Λq⊥(A) drawn from a distribution statically close to DΛ,σ,c,(ii)
there is a PPT algorithmSamplePre(A,TA,σ,c) that returns x∈Λqu(A) drawn from a distribution statically close to DΛ,σ,c, whenever Λqu(A) is not empty.Theorem 6 (see [14]).
DefineσR=nlog⁡qωlog⁡m. Dm×m stands for the distribution on matrices in Zm×m defined as (DZm,σR)m conditioned on the resulting matrix being Zq-invertible. There are some important algorithms: (i)
AlgorithmSampleR(1m). The following simple algorithm samples matrices in Zm×m from a distribution that is statistically close to Dm×m.
(a)
LetT be the canonical basis of the lattice Zm.(b)
Fori=1,2,…,m, do ri←RSampleGaussian(Zm,T,σR,0).(c)
IfR is Zq-invertible, output R; otherwise repeat step 2.(ii)
AlgorithmBasisDel(A,R,TA,σ). Input a rank n matrix A∈Zqn×m, a Zq-invertible matrix R in Zqn×m sampled from Dm×m (or a product of such), a basis TA for Λq⊥(A), and a parameter σ>T~AσRmω(log2/3⁡m).
(a)
LetTA={a1,a2,…,am}⊆Zm×m and calculate TB′={Ra1,Ra2,…,Ram}⊆Zm×m. Observe that TB′ is a set of independent vectors in Λq⊥(B), where B=AR-1 in Zqn×m.(b)
ConvertTB′ into a basis TB′′ of Λq⊥(B) whose Gram-Schmidt norm is no more than that of TB′.(c)
CallRandBasis(TB′′,σ) and output the resulting basis TB of Λq⊥(B).


### 2.4. LWE Problem

Definition 7 (see [20]).
Consider a primeq, a positive integer n, and a distribution χ over Zq, all public. (Zq,n,χ)-LWE problem instance consists of access to an unspecified challenge oracle Ψ, being either a noisy pseudorandom sample Ψs carrying some constant random secret key s∈Zqn or a truly random sampler Ψϕ, whose behaviors are respectively as follows: (i)
Ψs: output noisy pseudorandom sample of the form (ui,vi)=(ui,uiT·s+xi)∈Zqn×Zq, where s∈Zqn is an uniformly distributed persistent value invariant across invocations, xi∈Zq is a fresh randomness from χ, and ui is uniform in Zqn.(ii)
Ψϕ: output truly uniform random sample from Zqn×Zq.The(Zq,n,χ)-LWE problem allows repeat queries to the challenge oracle Ψ. We say that an algorithm A decides the (Zq,n,χ)-LWE problem if Pr⁡AΨs=1-Pr⁡AΨϕ=1 is nonnegligible for a random s∈Zqn.


## 2.1. Integer Lattices

Definition 1 (see [20]).
Givenn linearly independent vectors b1,b2,…,bn∈Rm, the lattice Λ generated by them is denoted L(b1,b2,…,bn) and define (1)Lb1,b2,…,bn=∑i=1nxibi∣xi∈Z.The vectors (b1,b2,…,bn) are called the basis of lattice.
For primeq and A∈Zqn×m and u∈Zqn, define (2)Λq⊥A=e∈Zm∣A·e=0mod⁡q,ΛquA=e∈Zm∣A·e=umod⁡q.


## 2.2. The Gram-Schmidt Norm of Basis

LetS~=s~1,s~2,…,s~k⊂Rm denote the Gram-Schmidt orthogonalization of the set of linearly independent vectors S=s1,s2,…,sk in Rm. It is defined as follows: s~1=s1 and s~1 is the component of si orthogonal to span (s1,s2,…,si), where 2≤i≤k. We refer to S~ as the Gram-Schmidt norm of S.Lemma 2 (see [14]).
LetΛ be an m-dimensional lattices. There is a deterministic polynomial-algorithm that, given an arbitrary basis of Λ and a full-rank set S=s1,s2,…,sm in Λ, returns a basis T of Λ satisfying (3)T≤S~,T≤Sm2.Theorem 3 (see [22]).
Letn and m be positive integers and let q be a prime, with q≥3 and m=6nlog2⁡q; there is a probabilistic polynomial time algorithm TrapGen(q,n) that outputs a pair (A∈Zqn×m,TA∈Zqm×m) such that A is statistically close to a uniform matrix in Zqn×m and TA is a basis for Λq⊥(A) satisfying (4)T~A≤Onlog2⁡q,TA≤Onlog2⁡qwith all but negligible probability in n.


## 2.3. Discrete Gaussians

Definition 4.
Choose a subsetL⊆Zm. For any positive parameter σ∈R>0 and any vector c∈Rm define (5)ρσ,cx=exp⁡-πx-c2σ2,ρσ,cL=∑x∈Lρσ,cx.The discrete Gaussians distribution over L with parameter σ and center c is (6)DL,σ,cy=ρσ,cyρσ,cL,∀y∈L.Lemma 5 (see [23]).
Letq≥2 and A be a matrix in Zqn×m with m>n. Let TA be a basis for Λq⊥(A) and σ≥T~Aωlog⁡m. Then for c∈Rm and u∈Zqn, (i)
there is a PPT algorithmSampleGaussian(A,TA,σ,c) that returns x∈Λq⊥(A) drawn from a distribution statically close to DΛ,σ,c,(ii)
there is a PPT algorithmSamplePre(A,TA,σ,c) that returns x∈Λqu(A) drawn from a distribution statically close to DΛ,σ,c, whenever Λqu(A) is not empty.Theorem 6 (see [14]).
DefineσR=nlog⁡qωlog⁡m. Dm×m stands for the distribution on matrices in Zm×m defined as (DZm,σR)m conditioned on the resulting matrix being Zq-invertible. There are some important algorithms: (i)
AlgorithmSampleR(1m). The following simple algorithm samples matrices in Zm×m from a distribution that is statistically close to Dm×m.
(a)
LetT be the canonical basis of the lattice Zm.(b)
Fori=1,2,…,m, do ri←RSampleGaussian(Zm,T,σR,0).(c)
IfR is Zq-invertible, output R; otherwise repeat step 2.(ii)
AlgorithmBasisDel(A,R,TA,σ). Input a rank n matrix A∈Zqn×m, a Zq-invertible matrix R in Zqn×m sampled from Dm×m (or a product of such), a basis TA for Λq⊥(A), and a parameter σ>T~AσRmω(log2/3⁡m).
(a)
LetTA={a1,a2,…,am}⊆Zm×m and calculate TB′={Ra1,Ra2,…,Ram}⊆Zm×m. Observe that TB′ is a set of independent vectors in Λq⊥(B), where B=AR-1 in Zqn×m.(b)
ConvertTB′ into a basis TB′′ of Λq⊥(B) whose Gram-Schmidt norm is no more than that of TB′.(c)
CallRandBasis(TB′′,σ) and output the resulting basis TB of Λq⊥(B).


## 2.4. LWE Problem

Definition 7 (see [20]).
Consider a primeq, a positive integer n, and a distribution χ over Zq, all public. (Zq,n,χ)-LWE problem instance consists of access to an unspecified challenge oracle Ψ, being either a noisy pseudorandom sample Ψs carrying some constant random secret key s∈Zqn or a truly random sampler Ψϕ, whose behaviors are respectively as follows: (i)
Ψs: output noisy pseudorandom sample of the form (ui,vi)=(ui,uiT·s+xi)∈Zqn×Zq, where s∈Zqn is an uniformly distributed persistent value invariant across invocations, xi∈Zq is a fresh randomness from χ, and ui is uniform in Zqn.(ii)
Ψϕ: output truly uniform random sample from Zqn×Zq.The(Zq,n,χ)-LWE problem allows repeat queries to the challenge oracle Ψ. We say that an algorithm A decides the (Zq,n,χ)-LWE problem if Pr⁡AΨs=1-Pr⁡AΨϕ=1 is nonnegligible for a random s∈Zqn.


## 3. PEKSL Scheme in a Multiuser Environment

### 3.1. Intuition behind the Construction

In PEKS scheme, a sender (Bob) sends an encrypted email to the email gateway using a receiver’s (Alice’s) public key appended with some encrypted keywords. When Alice gives the email gateway a trapdoor associated with searching keywords, it tests if the keywords are relevant to the email and learns nothing else. Since the ciphertext encrypted with receiver’s public key can only be tested by a trapdoor given by Alice and cannot be tested by a trapdoor obtained from another user, such as Charles, PEKS scheme is constrained to be used in a single-user environment where the receiver can only be a single user. In order to meet the need that multiple users can execute encrypted keyword searches over the encrypted files, we add aRe-KeyGen algorithm in the definition of PEKS and construct PEKSL scheme, which is inspired by the concept of proxy reencryption. TheRe-KeyGen algorithm is used to convert a keyword encrypted by a public key into the same keyword encrypted under another public key. More precisely, given a special information (i.e., a reencryption key), theRe-KeyGen algorithm enables cloud server to convert the encrypted keyword with Alice’s public key in the ciphertext of the same keyword for Charles so that cloud server can check if the encrypted keywords are relevant to an email upon a trapdoor generated by Charles. Based on the above idea, we construct our PEKSL scheme using lattices for a multiuser environment, where multiple users can execute encrypted keyword searches over the data uploaded by data owner to the cloud server.


### 3.2. Definition

A PEKSL scheme includes a trust center (TC), data owners, cloud servers, and data users. TC is trusted and is responsible for generating system parameters. The data owners refer to a special type of users who create the private/confidential data and then outsource them to cloud servers in an encrypted form so it can be shared with authorized users. The cloud servers are responsible for producing query results on the encrypted data and then sending these results to the users. Users generally refer to those who are authorized to search for encrypted keywords in the encrypted data. In this paper we consider the users to be from the public domain.A PEKSL scheme for a multiuser environment involves the following six algorithms:(i)
Setup(1λ). After input a secure parameter λ, theSetup algorithm outputs a global public/private key pair (mpk,msk) hold by TC.(ii)
KeyGen(msk,mpk,i). TheKeyGen algorithm takes as input (mpk,msk) and a user’s identity label i and then generates a public key pki, a private key ski for user i, and a secret key ki for TC.(iii)
Re-KeyGen(ki,kj). After input a key pair (ki,kj), theRe-KeyGen algorithm produces a reencryption key RKi↔j.(iv)
PEKSL(w,pki). ThePEKS algorithm produces a searchable encryption CT of keyword w with user’s public key pki.(v)
Trapdoor(w,skj,pkj). The trapdoor algorithm generates a trapdoor Tw for keyword w with a public/private key pair (pkj,skj).(vi)
Test(CT,Tw,RKi↔j). The Test algorithm verifies whether a ciphertext matches a trapdoor.


### 3.3. Security Game

The security of PEKSL scheme for a multiuser environment is indistinguishable against chosen keyword attack. According to the rules of the security game, an adversary can get the most of trapdoors except those which are relevant to two specified keywords. Yet, it can not distinguish which keyword appended with to a given PEKS ciphertext.In the following game, a PEKSL scheme for a multiuser environment is indistinguishable against chosen keyword attack if an adversaryF has a negligible advantage against a challenger C in polynomial time.Security Game (i)
Setup. C calls Setup algorithm to produce a key pair (mpk,msk) and sends mpk to F. (ii)
Phase 1. F makes the following queries:
(a)
Uncorrupted key generation oracle: return a fresh key pair(pki,ski); give pki to F. (b)
Corrupted key generation oracle: return a fresh key pair(pki,ski); F is given (pki,ski). (c)
Trapdoor Oracle: after input(pki,w) by F, return the trapdoor Tw=Trapdoor(ski,pki,w), where ski is the secret key that corresponds to pki. (d)
Reencryption key generation oracle: returnF a reencryption key RKi↔j. Noting that correspondent pki and pkj are from uncorrupted key generation oracle or corrupted key generation oracle as in [24], that is, the reencryption key queries are not allowed between uncorrupted oracle and corrupted oracle. (iii)
Challenge. F gives C two keywords w0,w1 that it hopes to be challenged on. The only limitation is that F have not queried for the trapdoors Tw0 or Tw1. C chooses a random b∈0,1 and sends F a PEKSL ciphertext CT∗=PEKS(w,pki) as the challenge ciphertext. (iv)
Phase 2. F adaptively queries C for the trapdoor Tw for any keyword w he wants again, and it is important to note that the w must satisfy w≠w0,w1. (v)
Guess. Finally, F gives b′∈{0,1}. If b′=b, F wins the game.In this game, we define the advantage of F that is Pr⁡b′=b-1/2.


### 3.4. Construction

Choose two positive integersn, m, a prime q, satisfying m>6nlog⁡q and q≥3, and a hash function H:0,1∗→Zqn. Construction of PEKSL scheme in a multiuser environment is described as follows:(i)
Setup(1n). Take a secure parameter n as input, TC invokes TrapGen(q,n) to produce a randomly uniform matrix A∈Zqn×m along with a short basis TA∈Zqm×m for Λq⊥(A), and output the global public key mpk=A as well as global private key msk=TA.(ii)
KeyGen(msk,mpk,i). After input (mpk,msk) and a user identity label i, TC invokes firstly AlgorithmSampleR(1m) to generate a Zq-invertible matrix Ri in Zqm×m sampled from Dm×m, where m is a security parameter. Then TC invokes AlgorithmBasisDel(A,Ri,TA,σ) to generate a basis Ti of Λq⊥(ARi-1), and output the user’s public key pki=ARi-1 in Zqn×m and private key ski=Ti and a secret key ki=Ri. TC sends ski to the user i by a security way and saves a list of (pki,ki).(iii)
Re-KeyGen(ki,kj). TC gets (ki=Ri,kj=Rj) from the list of (pki,ki) and computes RKi↔j=RiRj-1. TC sends RKi↔j to the cloud server by a security way.(iv)
PEKS(w,pki). The data owner computes u=H(w) and chooses r←RZqn uniformly and computes c1=rTpki and c2=uTr+x, where x←Rχ is a noise vector. Output the ciphertext CT=(c1,c2).(v)
Trapdoor(w,skj,pkj). A user computes u=H(w) and invokes AlgorithmSamplePre(pkj,skj,u,σ) to generate z∈Zqm, where σ is a Gaussian parameter. Note that pkjz=u in Zqn. Output z as a trapdoor; that is Tw=z.(vi)
Test(CT,Tw,RKi↔j). The cloud server computes (7)c1^=c1×RKi↔j=rT×pki×RKi↔j=rT×ARi×RiRj-1=rTARj-1=rTpkjthen let b=c2-zTc1^T. If b<q/4, return 1; otherwise, return 0.


### 3.5. Security Analysis

We show the security analysis of PEKSL scheme for a multiuser environment in this section. In the random oracle model, supposing that there is an adversaryF that has a nonnegligible advantage to attack our mechanism in polynomial time, we are able to construct a polynomial time algorithm S having a probability ε/2eQH to solve the LWE assumption, where QH denotes the query times of which F queries the random oracle H(·).Proof.
With the adversaryF, we construct the algorithm S as follows.
S requests from Ψ (Ψ is a pseudorandom LWE oracle) and receives a fresh pair (ui,vi)∈Zqn×Zq for each i=0,1,2,…,m and selects a random integer Q∗∈[1,QH]. (i)
Setup. Given LWE samples, S assembles the random matrix A∈Zqn×m from m, more exactly, making the ith column of A be the vector ui(i=1,2,3,…,m), and gives the public key A to F.(ii)
Phase  1. S answers queries of F as follows:
(a)
Uncorrupted key generation oracle: after input an indexi, if this i is uncorrupted, S runs AlgorithmSampleR(1m) to obtain a Zq-invertible matrix Ri in Zqn×m and computes pki=ARi, corruptedi=0. Finally S saves the tuple (i,pki,Ri,corruptedi=0) in PK-List. S sends pki to F.(b)
Corrupted key generation oracle: after input an indexi, if this i is corrupted, S runs firstly AlgorithmSampleR(1m) to obtain a Zq-invertible matrix Ri∈Zqn×m and then AlgorithmBasisDel(A,Ri,TA,σ) to get a basis Ti for pki. Finally S responds to F with (pki,ski=Ti) and records the tuple (i,pki,Ri,ski,corrupted=1) in PK-List.(c)
H Oracle: to answer H queries, S saves the tuples (pki,wi,ui,zi) in a H-list, which is initially empty. For the Qth query, F sends wi∈0,1∗ to H and S answers as follows:
(1)
If this query is the query numberQ∗ (i.e., Q=Q∗), S defines H(wi)=u0, pk∗=pki satisfying corrupted∗=0, and returns H(wi).(2)
Otherwise, if this query(pki,wi) has saved in the H-list, then S responds to H(wi)=ui. If the query (pki,wi) does not appears on the H-list and the corresponding corruptedi=0 in PK-List, S chooses zi←RDZm,r and computes ui=pkizi. Finally S saves the quadruple (pki,wi,ui,zi) in H-list for future use and returns H(wi)=ui to F.(d)
Trapdoor Oracle: for inputwi∈0,1∗ and pki, if H(wi)=u0, S aborts and fails. Otherwise, S retrieves the saved quadruple (pki,wi,ui,zi) from the H-list. Here we assume that a trapdoor query on wi is preceded by a H(·) query with wi. By construction, zi is the trapdoor for the keyword wi. S return zi as the trapdoor to F.(e)
Reencryption key generation oracle: after input(pki,pkj), S checks whether both pki and pkj occur in PK-List, if not, S aborts. Otherwise, S does the following operations:
(1)
Ifcorruptedi=corruptedj, S responds to F with RiRj-1.(2)
Ifcorruptedi≠corruptedj, S aborts.(iii)
Challenge. F sends two keywords w0,w1 with a pk it wants to challenge on, when it decides to finish Phase  1. S calls the algorithm mentioned above to answer H(·) queries twice with input (pk,w0),(pk,w1). If pk≠pk∗, then S aborts; if both H(w0)≠u0 and H(w1)≠u0, then S aborts either. Otherwise, supposing H(wb)=u0, S retrieves (v0,v1,v2,…,vm)∈Zq from the LWE instance and sets c1=[v1,v2,…,vm]T∈Zqm and c2=v0∈Zq. S responds with challenge ciphertext (c1,c2). Note that when Ψ is a pseudorandom LWE oracle and for the random r←RZqn and the noise value x∈χm, then c1=rTpki and c2=u0Tr+x is valid encryption for wb. While Ψ is a random oracle, (c1,c2) is uniformly sampled from Zqm×Zq.(iv)
Phase  2. S answers queries of F the same way it does in Phase 1 if pk≠pk∗, w≠w0≠w1, and the pk is from uncorrupted key generation oracle.(v)
Guess. At last F guesses b′∈0,1. S returns 1 if b=b′; otherwise S returns 0.if S does not halt, the distribution of both the challenge ciphertext and the public parameters is identical to its distribution in the real system. If S aborts the challenge ciphertext will be independently randomly sampled from Zqm×Zq. That is, if S does not abort, the advantage of S in solving LWE is identical to F’s advantage to attack this mechanism.Probability Analysis. We now analyze the situations that S did not come to a halt in the simulation. There are two independent situations:(i)
ε1: S did not report failure during any F’s trapdoor queries.(ii)
ε2: S did not report failure during any F’s challenge queries.The trapdoor of the same keyword is supposed not to be queried twice byF. And because Q∗ is chosen randomly in 1 and QH, S does not abort in the simulation of Trapdoor(·) with probability (1-1/QH)QH; that is, Pr⁡[ε1]=1-1/(QH+1)QH≥1/e.The only situation whereS reports failure during challenge phase is that H(w0)≠u0 and H(w1)≠u0. The probability that H(w0)=u0 or H(w1)=u0 is 1-(1-1/(QH+1))2. Hence, we have Pr⁡[ε2]=1-(1-1/(QH+1))2≥1/QH.So we have the probability ofS in solving LWE which is at least 1/2+ε/2eQH.


## 3.1. Intuition behind the Construction

In PEKS scheme, a sender (Bob) sends an encrypted email to the email gateway using a receiver’s (Alice’s) public key appended with some encrypted keywords. When Alice gives the email gateway a trapdoor associated with searching keywords, it tests if the keywords are relevant to the email and learns nothing else. Since the ciphertext encrypted with receiver’s public key can only be tested by a trapdoor given by Alice and cannot be tested by a trapdoor obtained from another user, such as Charles, PEKS scheme is constrained to be used in a single-user environment where the receiver can only be a single user. In order to meet the need that multiple users can execute encrypted keyword searches over the encrypted files, we add aRe-KeyGen algorithm in the definition of PEKS and construct PEKSL scheme, which is inspired by the concept of proxy reencryption. TheRe-KeyGen algorithm is used to convert a keyword encrypted by a public key into the same keyword encrypted under another public key. More precisely, given a special information (i.e., a reencryption key), theRe-KeyGen algorithm enables cloud server to convert the encrypted keyword with Alice’s public key in the ciphertext of the same keyword for Charles so that cloud server can check if the encrypted keywords are relevant to an email upon a trapdoor generated by Charles. Based on the above idea, we construct our PEKSL scheme using lattices for a multiuser environment, where multiple users can execute encrypted keyword searches over the data uploaded by data owner to the cloud server.


## 3.2. Definition

A PEKSL scheme includes a trust center (TC), data owners, cloud servers, and data users. TC is trusted and is responsible for generating system parameters. The data owners refer to a special type of users who create the private/confidential data and then outsource them to cloud servers in an encrypted form so it can be shared with authorized users. The cloud servers are responsible for producing query results on the encrypted data and then sending these results to the users. Users generally refer to those who are authorized to search for encrypted keywords in the encrypted data. In this paper we consider the users to be from the public domain.A PEKSL scheme for a multiuser environment involves the following six algorithms:(i)
Setup(1λ). After input a secure parameter λ, theSetup algorithm outputs a global public/private key pair (mpk,msk) hold by TC.(ii)
KeyGen(msk,mpk,i). TheKeyGen algorithm takes as input (mpk,msk) and a user’s identity label i and then generates a public key pki, a private key ski for user i, and a secret key ki for TC.(iii)
Re-KeyGen(ki,kj). After input a key pair (ki,kj), theRe-KeyGen algorithm produces a reencryption key RKi↔j.(iv)
PEKSL(w,pki). ThePEKS algorithm produces a searchable encryption CT of keyword w with user’s public key pki.(v)
Trapdoor(w,skj,pkj). The trapdoor algorithm generates a trapdoor Tw for keyword w with a public/private key pair (pkj,skj).(vi)
Test(CT,Tw,RKi↔j). The Test algorithm verifies whether a ciphertext matches a trapdoor.


## 3.3. Security Game

The security of PEKSL scheme for a multiuser environment is indistinguishable against chosen keyword attack. According to the rules of the security game, an adversary can get the most of trapdoors except those which are relevant to two specified keywords. Yet, it can not distinguish which keyword appended with to a given PEKS ciphertext.In the following game, a PEKSL scheme for a multiuser environment is indistinguishable against chosen keyword attack if an adversaryF has a negligible advantage against a challenger C in polynomial time.Security Game (i)
Setup. C calls Setup algorithm to produce a key pair (mpk,msk) and sends mpk to F. (ii)
Phase 1. F makes the following queries:
(a)
Uncorrupted key generation oracle: return a fresh key pair(pki,ski); give pki to F. (b)
Corrupted key generation oracle: return a fresh key pair(pki,ski); F is given (pki,ski). (c)
Trapdoor Oracle: after input(pki,w) by F, return the trapdoor Tw=Trapdoor(ski,pki,w), where ski is the secret key that corresponds to pki. (d)
Reencryption key generation oracle: returnF a reencryption key RKi↔j. Noting that correspondent pki and pkj are from uncorrupted key generation oracle or corrupted key generation oracle as in [24], that is, the reencryption key queries are not allowed between uncorrupted oracle and corrupted oracle. (iii)
Challenge. F gives C two keywords w0,w1 that it hopes to be challenged on. The only limitation is that F have not queried for the trapdoors Tw0 or Tw1. C chooses a random b∈0,1 and sends F a PEKSL ciphertext CT∗=PEKS(w,pki) as the challenge ciphertext. (iv)
Phase 2. F adaptively queries C for the trapdoor Tw for any keyword w he wants again, and it is important to note that the w must satisfy w≠w0,w1. (v)
Guess. Finally, F gives b′∈{0,1}. If b′=b, F wins the game.In this game, we define the advantage of F that is Pr⁡b′=b-1/2.


## 3.4. Construction

Choose two positive integersn, m, a prime q, satisfying m>6nlog⁡q and q≥3, and a hash function H:0,1∗→Zqn. Construction of PEKSL scheme in a multiuser environment is described as follows:(i)
Setup(1n). Take a secure parameter n as input, TC invokes TrapGen(q,n) to produce a randomly uniform matrix A∈Zqn×m along with a short basis TA∈Zqm×m for Λq⊥(A), and output the global public key mpk=A as well as global private key msk=TA.(ii)
KeyGen(msk,mpk,i). After input (mpk,msk) and a user identity label i, TC invokes firstly AlgorithmSampleR(1m) to generate a Zq-invertible matrix Ri in Zqm×m sampled from Dm×m, where m is a security parameter. Then TC invokes AlgorithmBasisDel(A,Ri,TA,σ) to generate a basis Ti of Λq⊥(ARi-1), and output the user’s public key pki=ARi-1 in Zqn×m and private key ski=Ti and a secret key ki=Ri. TC sends ski to the user i by a security way and saves a list of (pki,ki).(iii)
Re-KeyGen(ki,kj). TC gets (ki=Ri,kj=Rj) from the list of (pki,ki) and computes RKi↔j=RiRj-1. TC sends RKi↔j to the cloud server by a security way.(iv)
PEKS(w,pki). The data owner computes u=H(w) and chooses r←RZqn uniformly and computes c1=rTpki and c2=uTr+x, where x←Rχ is a noise vector. Output the ciphertext CT=(c1,c2).(v)
Trapdoor(w,skj,pkj). A user computes u=H(w) and invokes AlgorithmSamplePre(pkj,skj,u,σ) to generate z∈Zqm, where σ is a Gaussian parameter. Note that pkjz=u in Zqn. Output z as a trapdoor; that is Tw=z.(vi)
Test(CT,Tw,RKi↔j). The cloud server computes (7)c1^=c1×RKi↔j=rT×pki×RKi↔j=rT×ARi×RiRj-1=rTARj-1=rTpkjthen let b=c2-zTc1^T. If b<q/4, return 1; otherwise, return 0.


## 3.5. Security Analysis

We show the security analysis of PEKSL scheme for a multiuser environment in this section. In the random oracle model, supposing that there is an adversaryF that has a nonnegligible advantage to attack our mechanism in polynomial time, we are able to construct a polynomial time algorithm S having a probability ε/2eQH to solve the LWE assumption, where QH denotes the query times of which F queries the random oracle H(·).Proof.
With the adversaryF, we construct the algorithm S as follows.
S requests from Ψ (Ψ is a pseudorandom LWE oracle) and receives a fresh pair (ui,vi)∈Zqn×Zq for each i=0,1,2,…,m and selects a random integer Q∗∈[1,QH]. (i)
Setup. Given LWE samples, S assembles the random matrix A∈Zqn×m from m, more exactly, making the ith column of A be the vector ui(i=1,2,3,…,m), and gives the public key A to F.(ii)
Phase  1. S answers queries of F as follows:
(a)
Uncorrupted key generation oracle: after input an indexi, if this i is uncorrupted, S runs AlgorithmSampleR(1m) to obtain a Zq-invertible matrix Ri in Zqn×m and computes pki=ARi, corruptedi=0. Finally S saves the tuple (i,pki,Ri,corruptedi=0) in PK-List. S sends pki to F.(b)
Corrupted key generation oracle: after input an indexi, if this i is corrupted, S runs firstly AlgorithmSampleR(1m) to obtain a Zq-invertible matrix Ri∈Zqn×m and then AlgorithmBasisDel(A,Ri,TA,σ) to get a basis Ti for pki. Finally S responds to F with (pki,ski=Ti) and records the tuple (i,pki,Ri,ski,corrupted=1) in PK-List.(c)
H Oracle: to answer H queries, S saves the tuples (pki,wi,ui,zi) in a H-list, which is initially empty. For the Qth query, F sends wi∈0,1∗ to H and S answers as follows:
(1)
If this query is the query numberQ∗ (i.e., Q=Q∗), S defines H(wi)=u0, pk∗=pki satisfying corrupted∗=0, and returns H(wi).(2)
Otherwise, if this query(pki,wi) has saved in the H-list, then S responds to H(wi)=ui. If the query (pki,wi) does not appears on the H-list and the corresponding corruptedi=0 in PK-List, S chooses zi←RDZm,r and computes ui=pkizi. Finally S saves the quadruple (pki,wi,ui,zi) in H-list for future use and returns H(wi)=ui to F.(d)
Trapdoor Oracle: for inputwi∈0,1∗ and pki, if H(wi)=u0, S aborts and fails. Otherwise, S retrieves the saved quadruple (pki,wi,ui,zi) from the H-list. Here we assume that a trapdoor query on wi is preceded by a H(·) query with wi. By construction, zi is the trapdoor for the keyword wi. S return zi as the trapdoor to F.(e)
Reencryption key generation oracle: after input(pki,pkj), S checks whether both pki and pkj occur in PK-List, if not, S aborts. Otherwise, S does the following operations:
(1)
Ifcorruptedi=corruptedj, S responds to F with RiRj-1.(2)
Ifcorruptedi≠corruptedj, S aborts.(iii)
Challenge. F sends two keywords w0,w1 with a pk it wants to challenge on, when it decides to finish Phase  1. S calls the algorithm mentioned above to answer H(·) queries twice with input (pk,w0),(pk,w1). If pk≠pk∗, then S aborts; if both H(w0)≠u0 and H(w1)≠u0, then S aborts either. Otherwise, supposing H(wb)=u0, S retrieves (v0,v1,v2,…,vm)∈Zq from the LWE instance and sets c1=[v1,v2,…,vm]T∈Zqm and c2=v0∈Zq. S responds with challenge ciphertext (c1,c2). Note that when Ψ is a pseudorandom LWE oracle and for the random r←RZqn and the noise value x∈χm, then c1=rTpki and c2=u0Tr+x is valid encryption for wb. While Ψ is a random oracle, (c1,c2) is uniformly sampled from Zqm×Zq.(iv)
Phase  2. S answers queries of F the same way it does in Phase 1 if pk≠pk∗, w≠w0≠w1, and the pk is from uncorrupted key generation oracle.(v)
Guess. At last F guesses b′∈0,1. S returns 1 if b=b′; otherwise S returns 0.if S does not halt, the distribution of both the challenge ciphertext and the public parameters is identical to its distribution in the real system. If S aborts the challenge ciphertext will be independently randomly sampled from Zqm×Zq. That is, if S does not abort, the advantage of S in solving LWE is identical to F’s advantage to attack this mechanism.Probability Analysis. We now analyze the situations that S did not come to a halt in the simulation. There are two independent situations:(i)
ε1: S did not report failure during any F’s trapdoor queries.(ii)
ε2: S did not report failure during any F’s challenge queries.The trapdoor of the same keyword is supposed not to be queried twice byF. And because Q∗ is chosen randomly in 1 and QH, S does not abort in the simulation of Trapdoor(·) with probability (1-1/QH)QH; that is, Pr⁡[ε1]=1-1/(QH+1)QH≥1/e.The only situation whereS reports failure during challenge phase is that H(w0)≠u0 and H(w1)≠u0. The probability that H(w0)=u0 or H(w1)=u0 is 1-(1-1/(QH+1))2. Hence, we have Pr⁡[ε2]=1-(1-1/(QH+1))2≥1/QH.So we have the probability ofS in solving LWE which is at least 1/2+ε/2eQH.


## 4. Conclusion

A public key encryption with keyword search scheme is first presented using lattices for multiuser environment. Fruitful lattice-based cryptographic schemes have been proposed before, but as far as we know, it is the first lattice-based public key encryption with keyword search scheme targeted towards applications in multiuser environments. Its security can be proven based on the standard LWE assumption in the random oracle model.



---

*Source: 6549570-2016-11-23.xml*