# A Novel Model for Lattice-Based Authorized Searchable Encryption with Special Keyword

Authors: Fugeng Zeng; Chunxiang Xu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Data stored in the cloud servers, keyword search, and access controls are two important capabilities which should be supported. Public-keyword encryption with keyword search (PEKS) and attribute based encryption (ABE) are corresponding solutions. Meanwhile, as we step into postquantum era, pairing related assumption is fragile. Lattice is an ideal choice for building secure encryption scheme against quantum attack. Based on this, we propose the first mathematical model for lattice-based authorized searchable encryption. Data owners can sort the ciphertext by specific keywords such as time; data users satisfying the access control hand the trapdoor generated with the keyword to the cloud sever; the cloud sever sends back the corresponding ciphertext. The security of our schemes is based on the worst-case hardness on lattices, called learning with errors (LWE) assumption. In addition, our scheme achieves attribute-hiding, which could protect the sensitive information of data user.


---

## Body

## 1. Introduction

Nowadays, more and more people use service from cloud server [1], which provides scalable and elastic storage and computation resources by the Internet. Outsourcing data services to the cloud enables companies to not only save equipment investment, but also simplify the local IT management. Cloud infrastructures are physically hosted and maintained by the cloud providers. To minimize the risk of data leakage to cloud service providers and protect data security and privacy, data owners choose to encrypt sensitive data, such as health records, and property information, before outsourcing it to the cloud, while retaining the decryption key by itself and other authorized users. However, simple encryption scheme is not enough, because the data owners tend to strengthen the sharing of sensitive data under fine-grained access control. Cloud server cannot be fully trusted by the data owner, so traditional server-based access control methods are no longer suitable solution for cloud computing.In order to address the problem of secure and decentralized access control, Sahai and Waters [2] proposed the concept of ABE by extending identity-based encryption, which achieved flexibility and one-to-many encryption and provided a fine-grained data sharing scheme. Later, there are two kinds of ABE that were put forward: key policy (KP) ABE, which is the ciphertext associated with the attributes and the secret key associated with the decryption policy, and ciphertext policy (CP) ABE, where the secret key associated a list of attributes and the ciphertext associated with access policy. Goyal et al. [3] proposed the first construction of KP-ABE which supported any monotone access policy. After then, the first CP-ABE scheme was provided by Bethencourt et al. [4]; unfortunately the security proof of their scheme was only proved in the generic group model. Subsequently, Ostrovsky et al. broaden the two programs, to support any nonmonotonic structure [5]. The first CP-ABE scheme which could be proved in the standard model was proposed by Cheung and Newport [6] including only AND-gate. Later on, Waters [7] gave the first CP-ABE proved in the standard model supporting fully expressive access structure.All the schemes mentioned above are constructed from pairings. But unluckily, if we move into the era of postquantum, pairing related assumption is fragile. Lattice is an ideal choice for building secure encryption scheme according to two facts: firstly, there is no known algorithm even with the help of quantum computer that can efficiently solve lattice hard problems; secondly, lattice-based cryptographic constructions enjoy several potential advantages: asymptotic efficiency, conceptual simplicity, and security proof based on worst-case hard problem. Recently, ABE from lattice assumptions are ascendant. J. Zhang and Z. Zhang [8] proposed a CP-ABE without pairings scheme, which supports AND-gates access structure. Boyen [9] built a KP-ABE from lattice assumptions and pointed to the future work of the study of CP-ABE as an open problem.ABE resolves the problem of fine-grained access control and provides a one-to-many encryption which can improve the efficiency of the data owner; however, data utilization is still a challenging problem. For example, in order to search some relevant documents amongst an encrypted data set stored in the cloud, one may have to download and decrypt the entire data set. This is apparently impractical when the data volume is large. Thus, mechanisms that allow users to search directly on the encrypted data are of great interest in the era of cloud computing. Based on the traditional plaintext keyword search data services will result in bad quality of service because the data are encrypted. Boneh et al. [10] proposed a public key encryption with keyword search (PEKS) scheme to address the problem of searching encrypted data.There are also many existing searchable encryption schemes from parings. Lai et al. [11] present a more efficient construction based on Lewko et al.’s KP-ABE scheme [12]. However, scheme [11] discloses the searching keywords in the trapdoor, which will let the server learn whether the encrypted data contains the keywords in the trapdoor. Compared with [13], the size of a ciphertext (or a trapdoor) in [11] is linear with the number of keywords. Recently, Lv et al. [14] present an expressive and secure asymmetric searchable encryption scheme, which is the first to simultaneously support conjunctive, disjunctive, and negation search operations. However, there has been no ASE scheme from lattice assumptions so far. In this paper, we integrate CP-ABE with PEKS and propose authorized searchable encryption with attribute-hiding from lattices, which enables only authorized users to perform keyword search and then decrypt ciphertext.Meanwhile, by setting the keyword such as year, month, and day, data owners can sort ciphertext. If data users want to extract the ciphertext from some time point, they only need to submit trapdoor corresponding to keyword the cloud server.Therefore, there are two main contributions of our scheme in detail as follows.(1) To the best of our knowledge, this is the first work that addresses ASE from lattice assumptions.(2) In contrast to previous solutions [11, 14], our scheme achieves attribute-hiding, which could protect sensitive user information from being leaked.The rest of the paper is organized as follows. Section2 states the preliminaries about definitions for ASE, security model for PEKS and CP-ABE, and lattice knowledge. Section 3 describes our ASE with attribute-hiding from lattice assumptions in detail. Section 4 gives the security proof of our scheme. Section 5 presents our conclusion for this paper.


## 2. Preliminaries

### 2.1. Definitions for ASE

We consider ASE in cloud computing. The system architecture is similar to that in [15] which is illustrated as Figure 1. There exist four participants in our system.Figure 1
System architecture of ASE in cloud computing.Trusted Authority (TA). The entity is fully trusted by the other participants of the system. The responsibility of TA is to initialize system parameters, to generate attributed-based private keys, and to generate trapdoor keys for data users.Cloud Services Provider (CSP). The entity provides data storage and retrieval services. It stores the outsourcing data content of the data owner. Only the specified receiver who meets the access policy can search and download the content. We adopt the honest-but-curious model for the cloud server as in [16]. It assumes that the cloud server would honestly follow the designated protocols and procedures to fulfill its service providers role, while it may analyze the information stored and processed on the server in order to learn additional information about its customers.Data Owner (DO). The entity is a cloud storage subscriber who wants to encrypt its data content first and then upload to the cloud storage service. Intended receivers who satisfy the access policy can read the encrypted content. The responsibility of data owner is to create encrypted data and to choose keywords to encrypt.Data User (DU). The entity is another cloud storage subscriber who queries encrypted data from CSP. Only retrievers who satisfy the access policy can have the legal rights to access the encrypted content and read the original message. The responsibility of data users is to choose keywords to create trapdoor for search, to initiate search requests, and to decrypt data.In our setting, a user will be identified by a set of attributes; letS be the users attributes. An ASE scheme consists of six polynomial-time algorithms described as follows.Setup. The setup algorithm is run by TA, which inputs a security parameter k. It outputs the master secret key m
s
k and public system parameters p
a
r
a
m
s which include the description of attribute universe and keyword universe. TA publishes p
a
r
a
m
s and keeps m
s
k secret. We describe it as S
e
t
u
p
(
1
k
)
→
(
p
a
r
a
m
s
,
m
s
k
).ABE-KeyGen. The attribute private key generation algorithm is an interactive protocol implemented between DU and TA. The public input to TA and DU consists of the system public parameters p
a
r
a
m
s, the users attributes set S owned by DU. The private input to TA is the master secret key m
s
k. Finally, DU can extract an attribute private key S
K
S. We describe it as A
B
E
-
K
e
y
G
e
n
p
a
r
a
m
s
,
m
s
k
,
S
→
S
K
S.KS-CPABE. DO runs the encryption algorithm, which inputs the system public parameters p
a
r
a
m
s, an access structure W, and a message m
s
g. The algorithm encrypts m
s
g and produces a ciphertext c
t. Note that, in our ASE, the ciphertext does not contain W, which achieves attribute-hiding. We describe it as E
n
c
r
y
p
t
p
a
r
a
m
s
,
W
,
m
s
g
,
k
w
→
c
t.Trapdoor. The query private key generation algorithm is an interactive protocol implemented between DU and TA. The public input to TA and DU consists of the system public parameters p
a
r
a
m
s, the users attributes set S owned by DU, and a keyword k
w. TA inputs the master secret key m
s
k. In addition, a sequence of random coin tests may be used by TA and DU as private inputs. Finally, DU can extract an attribute trapdoor T
k
w. We describe it as T
r
a
p
d
o
o
r
p
a
r
a
m
s
,
m
s
k
,
S
→
T
k
w. After then, DU sends T
k
w to CSP.Test. The keyword test algorithm is run by CSP, which takes as input system parameters p
a
r
a
m
s and a trapdoor T
k
w corresponding to the keyword k
w from a DU and tests the c
t for keyword set k
w
′. Output 1 if k
w
=
k
w
′ and 0 otherwise.Decrypt. DU runs decryption algorithm, which takes the ciphertext c
t and S
K
S as input. Only if S satisfies the access control W, it will return the message m
s
g.


### 2.2. Security Model for PEKS and CPABE

In this subsection, we introduce the functionality of PEKS and CP-ABE independently.


#### 2.2.1. PEKS

AP
E
K
S scheme includes four polynomial-time algorithms: K
e
y
G
e
n, P
E
K
S, T
r
a
p
d
o
o
r, and T
e
s
t. The algorithm generates a public/private key pair p
k
,
m
s
k. The P
E
K
S algorithm generates a searchable encryption form of keyword k
w corresponding to intended receivers public key. The T
r
a
p
d
o
o
r algorithm produces a trapdoor T
k
w for keyword k
w corresponding to receiver’s private key. And the T
e
s
t algorithm verifies whether a ciphertext matches a trapdoor.The general security property ofP
E
K
S scheme is the indistinguish ability against chosen keyword attack. The P
E
K
S scheme is semantic security if a polynomial adversary has no nonnegligible advantage against the challenger in the following security game [10].Security GameKeyGen. The challenger C runs K
e
y
G
e
n algorithm to generate a key pair p
k
,
s
k and give p
k to the adversary A.Phase 1. A queries the challenger for the trapdoor for any keyword k
w
∈
0,1
* of his choice.Challenge. At some time, A sends the challenger two keywords k
w
0 and k
w
1 which it wishes to challenge. The only restriction is that A has never previously queried the trapdoors T
k
w
0 and T
k
w
1 for k
w
0 and k
w
1, respectively. The challenger selects b
∈
0,1 randomly and sends the adversary C
=
P
E
K
S
p
k
,
k
w
b as the challenge P
E
K
S ciphertext.Phase 2. A can continue to adaptively ask the challenger for the trapdoor for the keyword k
w of his choice which satisfies k
w
≠
k
w
0
,
k
w
1.Guess. In the end, the adversary A outputs b
′
∈
0,1. If b
′
=
b, A wins the game. Define the advantage of A in this game as Pr
⁡
b
′
=
b
-
1
/
2.Definition 1.
A PEKS scheme is(
t
,
Q
t
,
ɛ
) IND-PEKS CPA secure if all t polynomial time adversaries making at most Q
t token queries have at most a negligible advantage ɛ in the above security game.


#### 2.2.2. A CP-ABE Scheme with Attribute-Hiding

The scheme consists of four algorithms [17].Setup. This algorithm inputs a security parameter k and generates the public key P
K and a master secret key m
s
k. P
K is used for encryption; m
s
k is used to generate user secret keys. It is held by the central authority.Encrypt. This algorithm inputs the public key P
K, a message m
s
g, and an access policy W. It outputs the ciphertext c
t. Note that, in CP-ABE supporting attribute-hiding, the ciphertext does not contain W.KeyGen. This algorithm inputs a set of attributes S associated with the user and outputs a secret key S
K
S.Decrypt. This algorithm takes as input the ciphertext c
t and a secret key S
K
S. Only if S satisfies the access policy W, it returns the message m
s
g.Selective Game for CP-ABE with Hiding AttributesInit. The adversary A gives the challenge ciphertext policies W
0, W
1 before setup.Setup. The challenger C runs the setup algorithm and gives P
K to the adversary A.Phase 1. The adversary A submits the attribute list L for a K
e
y
G
e
n query. If L
⊆
W
0
∧
L
⊆
W
1 or L
⊄
W
0
∧
L
⊄
W
1, the challenger gives the adversary the secret key S
K
L. The adversary A can repeat this query polynomial times.Challenge. The adversary A submits messages M
0, M
1 to the challenger. If the adversary obtained the S
K
L whose associated attribute list L satisfies both W
0 and W
1 in Phase 1, then it is required that M
0
=
M
1. The challenger flips a random coin b and passes the ciphertext E
n
c
r
y
p
t
P
K
,
M
b
,
W
b to the adversary.Phase 2. Phase 1 is repeated. If M
0
≠
M
1, the adversary cannot submit L such that L
⊆
W
0
∧
L
⊆
W
1.Guess. The adversary outputs a guess b
′ of b. The advantage of an adversary in this game is defined as Pr
⁡
b
′
=
b
-
1
/
2.Definition 2.
A CP-ABE scheme with hiding attributes is selective CPA secure if all polynomial-time adversaries have at most a negligible advantageɛ in the above security game.


### 2.3. Lattice and Hardness Assumption

#### 2.3.1. Integer Lattices

Definition 3.
LetB
=
b
1
⋯
b
n
∈
Z
n
×
n be an n
×
n matrix which consists of n linearly independent vectors b
1
,
…
,
b
n
∈
Z
n. The n dimensional full-rank lattice Λ generated by B is Λ
=
y
∈
Z
n
∣
y
=
B
c
=
∑
i
=
1
n
‍
c
i
b
i
,
c
∈
Z
n; B is called a basis of the lattice Λ.
For a basisB, let B
~ denote its Gram-Schmidt orthogonalization, defined iteratively as b
~
1
=
b
1, and b
~
i is the component of b
i orthogonal to span b
1
,
…
,
b
i
-
1. B denotes the longest Euclid norm of the column vectors in B.
Given a matrixA
∈
Z
q
n
×
m for a prime q, integers m and n, we consider two kinds of full-rank m-dimensional integer defined by Λ
q
⊥
A
=
e
∈
Z
m
∣
A
e
=
0
(
mod
⁡
q
), Λ
q
A
=
y
∈
Z
m
∣
∃
s
∈
Z
n
,
A
T
s
=
y
(
mod
⁡
q
).Proposition 4 (see [18]).
For any primeq
≥
2 and m
≥
5
n
log
⁡
q, there is a probabilistic polynomial-time algorithm TrapGen(
q
,
n
) that outputs a matrix A
∈
Z
q
n
×
m and a full-rank set T
A
∈
Z
m
×
m such that A is statistically close to uniform over Z
q
n
×
m and T
A is a basis for Λ
q
⊥
A.


#### 2.3.2. Discrete Gaussian

For anys
>
0, the Gaussian function on Λ
⊂
Z
n centered at c with parameter s is defined as ∀
x
∈
Λ, ρ
s
,
c
x
=
exp
⁡
-
π
x
-
c
/
s
2. Let ρ
s
,
c
Λ
=
∑
x
∈
Λ
‍
ρ
s
,
c
x. The discrete Gaussian distribution over Λ with center c and parameter s is defined as ∀
y
∈
Λ, D
Λ
,
s
,
c
y
=
ρ
s
,
c
y
/
ρ
s
,
c
Λ. The subscripts s are taken to be 0 when omitted.Gentry et al. [19] defined and constructed the preimage sampleable functions. Let T
A be a basis for an m-dimensional lattice Λ satisfying s
≥
T
~
A
ω
log
⁡
m, the algorithm samples from the discrete Gaussian distribution D
Λ
,
s
,
c.The preimage sampleable function is defined as follows.S
a
m
p
l
e
p
r
e
A
,
T
A
,
u
,
s. The algorithm takes as input A
∈
Z
q
n
×
m, the short basis T
A for Λ
q
⊥
A, the target image u
∈
Z
q
n, and Gaussian parameters s
≥
T
~
A
ω
log
⁡
m and outputs e
∈
Z
n which is statistically close to D
Λ
q
u
A
,
s.


#### 2.3.3. Learning with Error Problem

Our construction can be reduced to learning with errorsL
W
E problem, which is a classical problem defined by Regev [20].For an integerq
=
q
(
n
) and a distribution χ on Z
q, the goal of the (average case) learning with errors problem L
W
E
q
,
χ is to distinguish the distribution A
s
,
χ for some uniform secret s
∈
Z
q
n and the uniform distribution on Z
q
n
×
Z
q. The hardness of L
W
E problem means the distribution A
s
,
χ is pseudorandom. Regev demonstrated that, for certain modulo q and Gaussian error distributions χ, L
W
E
q
,
χ is as hard as solving several standard worst-case lattice problems using quantum algorithm.Proposition 5 (see [20]).
For anα
∈
0,1 and a prime q
>
2
n
/
α, let ψ
α
¯ denote the distribution over Z
q of the random variable q
X
+
1
/
2

mod
⁡

q, where X is a normal random variable with mean 0 and standard deviation α
/
2
π. If there exists an efficient, possibly quantum, algorithm for deciding the (
Z
q
,
n
,
χ
)-L
W
E problem, then there exists an efficient quantum algorithm for approximating the S
I
V
P and G
a
p
S
V
P problems, to within O
~
n
/
α factors in the l
2 norm, in the worst case.


## 2.1. Definitions for ASE

We consider ASE in cloud computing. The system architecture is similar to that in [15] which is illustrated as Figure 1. There exist four participants in our system.Figure 1
System architecture of ASE in cloud computing.Trusted Authority (TA). The entity is fully trusted by the other participants of the system. The responsibility of TA is to initialize system parameters, to generate attributed-based private keys, and to generate trapdoor keys for data users.Cloud Services Provider (CSP). The entity provides data storage and retrieval services. It stores the outsourcing data content of the data owner. Only the specified receiver who meets the access policy can search and download the content. We adopt the honest-but-curious model for the cloud server as in [16]. It assumes that the cloud server would honestly follow the designated protocols and procedures to fulfill its service providers role, while it may analyze the information stored and processed on the server in order to learn additional information about its customers.Data Owner (DO). The entity is a cloud storage subscriber who wants to encrypt its data content first and then upload to the cloud storage service. Intended receivers who satisfy the access policy can read the encrypted content. The responsibility of data owner is to create encrypted data and to choose keywords to encrypt.Data User (DU). The entity is another cloud storage subscriber who queries encrypted data from CSP. Only retrievers who satisfy the access policy can have the legal rights to access the encrypted content and read the original message. The responsibility of data users is to choose keywords to create trapdoor for search, to initiate search requests, and to decrypt data.In our setting, a user will be identified by a set of attributes; letS be the users attributes. An ASE scheme consists of six polynomial-time algorithms described as follows.Setup. The setup algorithm is run by TA, which inputs a security parameter k. It outputs the master secret key m
s
k and public system parameters p
a
r
a
m
s which include the description of attribute universe and keyword universe. TA publishes p
a
r
a
m
s and keeps m
s
k secret. We describe it as S
e
t
u
p
(
1
k
)
→
(
p
a
r
a
m
s
,
m
s
k
).ABE-KeyGen. The attribute private key generation algorithm is an interactive protocol implemented between DU and TA. The public input to TA and DU consists of the system public parameters p
a
r
a
m
s, the users attributes set S owned by DU. The private input to TA is the master secret key m
s
k. Finally, DU can extract an attribute private key S
K
S. We describe it as A
B
E
-
K
e
y
G
e
n
p
a
r
a
m
s
,
m
s
k
,
S
→
S
K
S.KS-CPABE. DO runs the encryption algorithm, which inputs the system public parameters p
a
r
a
m
s, an access structure W, and a message m
s
g. The algorithm encrypts m
s
g and produces a ciphertext c
t. Note that, in our ASE, the ciphertext does not contain W, which achieves attribute-hiding. We describe it as E
n
c
r
y
p
t
p
a
r
a
m
s
,
W
,
m
s
g
,
k
w
→
c
t.Trapdoor. The query private key generation algorithm is an interactive protocol implemented between DU and TA. The public input to TA and DU consists of the system public parameters p
a
r
a
m
s, the users attributes set S owned by DU, and a keyword k
w. TA inputs the master secret key m
s
k. In addition, a sequence of random coin tests may be used by TA and DU as private inputs. Finally, DU can extract an attribute trapdoor T
k
w. We describe it as T
r
a
p
d
o
o
r
p
a
r
a
m
s
,
m
s
k
,
S
→
T
k
w. After then, DU sends T
k
w to CSP.Test. The keyword test algorithm is run by CSP, which takes as input system parameters p
a
r
a
m
s and a trapdoor T
k
w corresponding to the keyword k
w from a DU and tests the c
t for keyword set k
w
′. Output 1 if k
w
=
k
w
′ and 0 otherwise.Decrypt. DU runs decryption algorithm, which takes the ciphertext c
t and S
K
S as input. Only if S satisfies the access control W, it will return the message m
s
g.


## 2.2. Security Model for PEKS and CPABE

In this subsection, we introduce the functionality of PEKS and CP-ABE independently.


### 2.2.1. PEKS

AP
E
K
S scheme includes four polynomial-time algorithms: K
e
y
G
e
n, P
E
K
S, T
r
a
p
d
o
o
r, and T
e
s
t. The algorithm generates a public/private key pair p
k
,
m
s
k. The P
E
K
S algorithm generates a searchable encryption form of keyword k
w corresponding to intended receivers public key. The T
r
a
p
d
o
o
r algorithm produces a trapdoor T
k
w for keyword k
w corresponding to receiver’s private key. And the T
e
s
t algorithm verifies whether a ciphertext matches a trapdoor.The general security property ofP
E
K
S scheme is the indistinguish ability against chosen keyword attack. The P
E
K
S scheme is semantic security if a polynomial adversary has no nonnegligible advantage against the challenger in the following security game [10].Security GameKeyGen. The challenger C runs K
e
y
G
e
n algorithm to generate a key pair p
k
,
s
k and give p
k to the adversary A.Phase 1. A queries the challenger for the trapdoor for any keyword k
w
∈
0,1
* of his choice.Challenge. At some time, A sends the challenger two keywords k
w
0 and k
w
1 which it wishes to challenge. The only restriction is that A has never previously queried the trapdoors T
k
w
0 and T
k
w
1 for k
w
0 and k
w
1, respectively. The challenger selects b
∈
0,1 randomly and sends the adversary C
=
P
E
K
S
p
k
,
k
w
b as the challenge P
E
K
S ciphertext.Phase 2. A can continue to adaptively ask the challenger for the trapdoor for the keyword k
w of his choice which satisfies k
w
≠
k
w
0
,
k
w
1.Guess. In the end, the adversary A outputs b
′
∈
0,1. If b
′
=
b, A wins the game. Define the advantage of A in this game as Pr
⁡
b
′
=
b
-
1
/
2.Definition 1.
A PEKS scheme is(
t
,
Q
t
,
ɛ
) IND-PEKS CPA secure if all t polynomial time adversaries making at most Q
t token queries have at most a negligible advantage ɛ in the above security game.


### 2.2.2. A CP-ABE Scheme with Attribute-Hiding

The scheme consists of four algorithms [17].Setup. This algorithm inputs a security parameter k and generates the public key P
K and a master secret key m
s
k. P
K is used for encryption; m
s
k is used to generate user secret keys. It is held by the central authority.Encrypt. This algorithm inputs the public key P
K, a message m
s
g, and an access policy W. It outputs the ciphertext c
t. Note that, in CP-ABE supporting attribute-hiding, the ciphertext does not contain W.KeyGen. This algorithm inputs a set of attributes S associated with the user and outputs a secret key S
K
S.Decrypt. This algorithm takes as input the ciphertext c
t and a secret key S
K
S. Only if S satisfies the access policy W, it returns the message m
s
g.Selective Game for CP-ABE with Hiding AttributesInit. The adversary A gives the challenge ciphertext policies W
0, W
1 before setup.Setup. The challenger C runs the setup algorithm and gives P
K to the adversary A.Phase 1. The adversary A submits the attribute list L for a K
e
y
G
e
n query. If L
⊆
W
0
∧
L
⊆
W
1 or L
⊄
W
0
∧
L
⊄
W
1, the challenger gives the adversary the secret key S
K
L. The adversary A can repeat this query polynomial times.Challenge. The adversary A submits messages M
0, M
1 to the challenger. If the adversary obtained the S
K
L whose associated attribute list L satisfies both W
0 and W
1 in Phase 1, then it is required that M
0
=
M
1. The challenger flips a random coin b and passes the ciphertext E
n
c
r
y
p
t
P
K
,
M
b
,
W
b to the adversary.Phase 2. Phase 1 is repeated. If M
0
≠
M
1, the adversary cannot submit L such that L
⊆
W
0
∧
L
⊆
W
1.Guess. The adversary outputs a guess b
′ of b. The advantage of an adversary in this game is defined as Pr
⁡
b
′
=
b
-
1
/
2.Definition 2.
A CP-ABE scheme with hiding attributes is selective CPA secure if all polynomial-time adversaries have at most a negligible advantageɛ in the above security game.


## 2.2.1. PEKS

AP
E
K
S scheme includes four polynomial-time algorithms: K
e
y
G
e
n, P
E
K
S, T
r
a
p
d
o
o
r, and T
e
s
t. The algorithm generates a public/private key pair p
k
,
m
s
k. The P
E
K
S algorithm generates a searchable encryption form of keyword k
w corresponding to intended receivers public key. The T
r
a
p
d
o
o
r algorithm produces a trapdoor T
k
w for keyword k
w corresponding to receiver’s private key. And the T
e
s
t algorithm verifies whether a ciphertext matches a trapdoor.The general security property ofP
E
K
S scheme is the indistinguish ability against chosen keyword attack. The P
E
K
S scheme is semantic security if a polynomial adversary has no nonnegligible advantage against the challenger in the following security game [10].Security GameKeyGen. The challenger C runs K
e
y
G
e
n algorithm to generate a key pair p
k
,
s
k and give p
k to the adversary A.Phase 1. A queries the challenger for the trapdoor for any keyword k
w
∈
0,1
* of his choice.Challenge. At some time, A sends the challenger two keywords k
w
0 and k
w
1 which it wishes to challenge. The only restriction is that A has never previously queried the trapdoors T
k
w
0 and T
k
w
1 for k
w
0 and k
w
1, respectively. The challenger selects b
∈
0,1 randomly and sends the adversary C
=
P
E
K
S
p
k
,
k
w
b as the challenge P
E
K
S ciphertext.Phase 2. A can continue to adaptively ask the challenger for the trapdoor for the keyword k
w of his choice which satisfies k
w
≠
k
w
0
,
k
w
1.Guess. In the end, the adversary A outputs b
′
∈
0,1. If b
′
=
b, A wins the game. Define the advantage of A in this game as Pr
⁡
b
′
=
b
-
1
/
2.Definition 1.
A PEKS scheme is(
t
,
Q
t
,
ɛ
) IND-PEKS CPA secure if all t polynomial time adversaries making at most Q
t token queries have at most a negligible advantage ɛ in the above security game.


## 2.2.2. A CP-ABE Scheme with Attribute-Hiding

The scheme consists of four algorithms [17].Setup. This algorithm inputs a security parameter k and generates the public key P
K and a master secret key m
s
k. P
K is used for encryption; m
s
k is used to generate user secret keys. It is held by the central authority.Encrypt. This algorithm inputs the public key P
K, a message m
s
g, and an access policy W. It outputs the ciphertext c
t. Note that, in CP-ABE supporting attribute-hiding, the ciphertext does not contain W.KeyGen. This algorithm inputs a set of attributes S associated with the user and outputs a secret key S
K
S.Decrypt. This algorithm takes as input the ciphertext c
t and a secret key S
K
S. Only if S satisfies the access policy W, it returns the message m
s
g.Selective Game for CP-ABE with Hiding AttributesInit. The adversary A gives the challenge ciphertext policies W
0, W
1 before setup.Setup. The challenger C runs the setup algorithm and gives P
K to the adversary A.Phase 1. The adversary A submits the attribute list L for a K
e
y
G
e
n query. If L
⊆
W
0
∧
L
⊆
W
1 or L
⊄
W
0
∧
L
⊄
W
1, the challenger gives the adversary the secret key S
K
L. The adversary A can repeat this query polynomial times.Challenge. The adversary A submits messages M
0, M
1 to the challenger. If the adversary obtained the S
K
L whose associated attribute list L satisfies both W
0 and W
1 in Phase 1, then it is required that M
0
=
M
1. The challenger flips a random coin b and passes the ciphertext E
n
c
r
y
p
t
P
K
,
M
b
,
W
b to the adversary.Phase 2. Phase 1 is repeated. If M
0
≠
M
1, the adversary cannot submit L such that L
⊆
W
0
∧
L
⊆
W
1.Guess. The adversary outputs a guess b
′ of b. The advantage of an adversary in this game is defined as Pr
⁡
b
′
=
b
-
1
/
2.Definition 2.
A CP-ABE scheme with hiding attributes is selective CPA secure if all polynomial-time adversaries have at most a negligible advantageɛ in the above security game.


## 2.3. Lattice and Hardness Assumption

### 2.3.1. Integer Lattices

Definition 3.
LetB
=
b
1
⋯
b
n
∈
Z
n
×
n be an n
×
n matrix which consists of n linearly independent vectors b
1
,
…
,
b
n
∈
Z
n. The n dimensional full-rank lattice Λ generated by B is Λ
=
y
∈
Z
n
∣
y
=
B
c
=
∑
i
=
1
n
‍
c
i
b
i
,
c
∈
Z
n; B is called a basis of the lattice Λ.
For a basisB, let B
~ denote its Gram-Schmidt orthogonalization, defined iteratively as b
~
1
=
b
1, and b
~
i is the component of b
i orthogonal to span b
1
,
…
,
b
i
-
1. B denotes the longest Euclid norm of the column vectors in B.
Given a matrixA
∈
Z
q
n
×
m for a prime q, integers m and n, we consider two kinds of full-rank m-dimensional integer defined by Λ
q
⊥
A
=
e
∈
Z
m
∣
A
e
=
0
(
mod
⁡
q
), Λ
q
A
=
y
∈
Z
m
∣
∃
s
∈
Z
n
,
A
T
s
=
y
(
mod
⁡
q
).Proposition 4 (see [18]).
For any primeq
≥
2 and m
≥
5
n
log
⁡
q, there is a probabilistic polynomial-time algorithm TrapGen(
q
,
n
) that outputs a matrix A
∈
Z
q
n
×
m and a full-rank set T
A
∈
Z
m
×
m such that A is statistically close to uniform over Z
q
n
×
m and T
A is a basis for Λ
q
⊥
A.


### 2.3.2. Discrete Gaussian

For anys
>
0, the Gaussian function on Λ
⊂
Z
n centered at c with parameter s is defined as ∀
x
∈
Λ, ρ
s
,
c
x
=
exp
⁡
-
π
x
-
c
/
s
2. Let ρ
s
,
c
Λ
=
∑
x
∈
Λ
‍
ρ
s
,
c
x. The discrete Gaussian distribution over Λ with center c and parameter s is defined as ∀
y
∈
Λ, D
Λ
,
s
,
c
y
=
ρ
s
,
c
y
/
ρ
s
,
c
Λ. The subscripts s are taken to be 0 when omitted.Gentry et al. [19] defined and constructed the preimage sampleable functions. Let T
A be a basis for an m-dimensional lattice Λ satisfying s
≥
T
~
A
ω
log
⁡
m, the algorithm samples from the discrete Gaussian distribution D
Λ
,
s
,
c.The preimage sampleable function is defined as follows.S
a
m
p
l
e
p
r
e
A
,
T
A
,
u
,
s. The algorithm takes as input A
∈
Z
q
n
×
m, the short basis T
A for Λ
q
⊥
A, the target image u
∈
Z
q
n, and Gaussian parameters s
≥
T
~
A
ω
log
⁡
m and outputs e
∈
Z
n which is statistically close to D
Λ
q
u
A
,
s.


### 2.3.3. Learning with Error Problem

Our construction can be reduced to learning with errorsL
W
E problem, which is a classical problem defined by Regev [20].For an integerq
=
q
(
n
) and a distribution χ on Z
q, the goal of the (average case) learning with errors problem L
W
E
q
,
χ is to distinguish the distribution A
s
,
χ for some uniform secret s
∈
Z
q
n and the uniform distribution on Z
q
n
×
Z
q. The hardness of L
W
E problem means the distribution A
s
,
χ is pseudorandom. Regev demonstrated that, for certain modulo q and Gaussian error distributions χ, L
W
E
q
,
χ is as hard as solving several standard worst-case lattice problems using quantum algorithm.Proposition 5 (see [20]).
For anα
∈
0,1 and a prime q
>
2
n
/
α, let ψ
α
¯ denote the distribution over Z
q of the random variable q
X
+
1
/
2

mod
⁡

q, where X is a normal random variable with mean 0 and standard deviation α
/
2
π. If there exists an efficient, possibly quantum, algorithm for deciding the (
Z
q
,
n
,
χ
)-L
W
E problem, then there exists an efficient quantum algorithm for approximating the S
I
V
P and G
a
p
S
V
P problems, to within O
~
n
/
α factors in the l
2 norm, in the worst case.


## 2.3.1. Integer Lattices

Definition 3.
LetB
=
b
1
⋯
b
n
∈
Z
n
×
n be an n
×
n matrix which consists of n linearly independent vectors b
1
,
…
,
b
n
∈
Z
n. The n dimensional full-rank lattice Λ generated by B is Λ
=
y
∈
Z
n
∣
y
=
B
c
=
∑
i
=
1
n
‍
c
i
b
i
,
c
∈
Z
n; B is called a basis of the lattice Λ.
For a basisB, let B
~ denote its Gram-Schmidt orthogonalization, defined iteratively as b
~
1
=
b
1, and b
~
i is the component of b
i orthogonal to span b
1
,
…
,
b
i
-
1. B denotes the longest Euclid norm of the column vectors in B.
Given a matrixA
∈
Z
q
n
×
m for a prime q, integers m and n, we consider two kinds of full-rank m-dimensional integer defined by Λ
q
⊥
A
=
e
∈
Z
m
∣
A
e
=
0
(
mod
⁡
q
), Λ
q
A
=
y
∈
Z
m
∣
∃
s
∈
Z
n
,
A
T
s
=
y
(
mod
⁡
q
).Proposition 4 (see [18]).
For any primeq
≥
2 and m
≥
5
n
log
⁡
q, there is a probabilistic polynomial-time algorithm TrapGen(
q
,
n
) that outputs a matrix A
∈
Z
q
n
×
m and a full-rank set T
A
∈
Z
m
×
m such that A is statistically close to uniform over Z
q
n
×
m and T
A is a basis for Λ
q
⊥
A.


## 2.3.2. Discrete Gaussian

For anys
>
0, the Gaussian function on Λ
⊂
Z
n centered at c with parameter s is defined as ∀
x
∈
Λ, ρ
s
,
c
x
=
exp
⁡
-
π
x
-
c
/
s
2. Let ρ
s
,
c
Λ
=
∑
x
∈
Λ
‍
ρ
s
,
c
x. The discrete Gaussian distribution over Λ with center c and parameter s is defined as ∀
y
∈
Λ, D
Λ
,
s
,
c
y
=
ρ
s
,
c
y
/
ρ
s
,
c
Λ. The subscripts s are taken to be 0 when omitted.Gentry et al. [19] defined and constructed the preimage sampleable functions. Let T
A be a basis for an m-dimensional lattice Λ satisfying s
≥
T
~
A
ω
log
⁡
m, the algorithm samples from the discrete Gaussian distribution D
Λ
,
s
,
c.The preimage sampleable function is defined as follows.S
a
m
p
l
e
p
r
e
A
,
T
A
,
u
,
s. The algorithm takes as input A
∈
Z
q
n
×
m, the short basis T
A for Λ
q
⊥
A, the target image u
∈
Z
q
n, and Gaussian parameters s
≥
T
~
A
ω
log
⁡
m and outputs e
∈
Z
n which is statistically close to D
Λ
q
u
A
,
s.


## 2.3.3. Learning with Error Problem

Our construction can be reduced to learning with errorsL
W
E problem, which is a classical problem defined by Regev [20].For an integerq
=
q
(
n
) and a distribution χ on Z
q, the goal of the (average case) learning with errors problem L
W
E
q
,
χ is to distinguish the distribution A
s
,
χ for some uniform secret s
∈
Z
q
n and the uniform distribution on Z
q
n
×
Z
q. The hardness of L
W
E problem means the distribution A
s
,
χ is pseudorandom. Regev demonstrated that, for certain modulo q and Gaussian error distributions χ, L
W
E
q
,
χ is as hard as solving several standard worst-case lattice problems using quantum algorithm.Proposition 5 (see [20]).
For anα
∈
0,1 and a prime q
>
2
n
/
α, let ψ
α
¯ denote the distribution over Z
q of the random variable q
X
+
1
/
2

mod
⁡

q, where X is a normal random variable with mean 0 and standard deviation α
/
2
π. If there exists an efficient, possibly quantum, algorithm for deciding the (
Z
q
,
n
,
χ
)-L
W
E problem, then there exists an efficient quantum algorithm for approximating the S
I
V
P and G
a
p
S
V
P problems, to within O
~
n
/
α factors in the l
2 norm, in the worst case.


## 3. Authorized Searchable Encryption Scheme

In this section, we put forward our ASE scheme where the access structures include positive and negative attributes based on AND-gates. Define some symbols simply as follows: let the set of attributes beN
=
{
1,2
,
…
,
l
} for a fixed natural number l. Mark attributes i and their negations ¬
i as literals. Consider access structures that consist of an AND-gate policy whose inputs are literals, which is denoted by W
=
∧
i
∈
I
i
¯, where W
⊆
N and every i
¯ is literal (i.e., i or ¬
i). Our construction is defined as follows, which is parameterized by dimension m, Gaussian parameter s, modulus q, and α that determines the error distribution χ.S
e
t
u
p
(
n
,
m
,
q
,
N
). TA chooses a cryptographic secure hash function H, which maps each keyword k
w to a vector in Z
q. Compute (
A
0
,
T
A
0
)
←
T
r
a
p
G
e
n
(
n
,
m
,
q
); then, for each i
∈
N, randomly choose A
i
+
←
Z
q
n
×
m, A
i
-
←
Z
q
n
×
m. Intuitively, the public key elements A
i
+, A
i
- associate with two cases of i: positive and negative. Next, randomly choose a vector u
←
Z
q
n and set public key P
K
=
(
A
0
,
{
A
i
+
,
A
i
-
}
i
∈
R
,
u
,
H
), while keeping the master secret key m
s
k
=
(
P
K
,
T
A
0
).ABE-KeyGen. Denote S as the input attribute set of DU. Every i
∉
S is implicitly as a negative attribute. For each i
∈
N, if i
∈
S, define A
i
¯
=
A
i
+; else define A
i
¯
=
A
i
-; then, for each i
∈
R, randomly choose e
i
←
D
Z
m
,
s, and compute y
=
u
-
∑
i
∈
R
‍
A
i
¯
e
i; finally, compute e
0
←
S
a
m
p
l
e
p
r
e
(
A
0
,
T
A
0
,
s
,
y
), and return secret key S
K
S
=
[
e
0
,
e
1
,
…
,
e
|
l
|
]. Observe that if letting E
=
[
A
0
∥
A
1
¯
∥
⋯
∥
A
|
l
|
¯
], we have E
·
S
K
S
=
u.KS-CPABE. Given a message bit M
∈
{
0,1
} and an AND-gate access structure W
=
∧
i
∈
I
i
¯, let S
+
(
S
-
) be the set of positive (negative) attributes in W, respectively, and denote S
′
=
S
+
∪
S
-; then, for each  i
∈
S
′, if i
∈
S
+, define c
i
1 as a well-formed ciphertext and c
i
2 as a malfunction ciphertext. If i
∈
S
-, the situation is converse; define c
i
2 as a well-formed ciphertext and c
i
1 as a malfunction ciphertext. If i
∈
N
∖
S
′, both c
i
1 and c
i
2 are well-formed ciphertext, and, for each keyword k
w, H
(
k
w
)
∈
Z
q
n. Randomly choose x
∈
Z
q
n, x
c
,
x
p
∈
χ, and x
0
,
x
i
+
,
x
i
-
∈
χ
m as noise distributions; compute c
=
u
T
x
+
x
c
+
M
q
/
2, p
=
H
(
k
w
)
T
x
+
x
p, and c
0
=
A
0
T
x
+
x
0. If i
∈
S
+, c
i
1
=
A
i
+
T
x
+
x
i
+, and c
i
2 is a random m dimension vector and could be achieved by randomly choosing x
i
′
∈
Z
q
n, c
i
2
=
A
i
-
T
x
i
′
+
x
i
-. If i
∈
S
-, c
i
1
=
A
i
+
T
x
i
′
+
x
i
+, c
i
2
=
A
i
-
T
x
+
x
i
-. If i
∈
N
∖
S
′, c
i
1
=
A
i
+
T
x
+
x
i
+, c
i
2
=
A
i
-
T
x
+
x
i
-.Finally, return ciphertextC
=
(
c
,
c
0
,
{
c
i
1
,
c
i
2
}
i
∈
N
) and secure keyword attachment p.Trapdoor. To generate a trapdoor for a keyword, DU must contact with TA. TA enforces the trapdoor generation similar to the process of ABE-KeyGen phase. For each i
∈
N, if i
∈
S, define A
i
¯
=
A
i
+; else define A
i
¯
=
A
i
-; then, for each i
∈
N, randomly choose f
i
←
D
Z
m
,
s and compute z
=
H
(
k
w
)
-
∑
i
∈
R
‍
A
i
¯
f
i; finally, compute f
0
←
S
a
m
p
l
e
p
r
e
(
A
0
,
T
A
0
,
s
,
z
) and return secret key T
k
w
=
[
f
0
,
f
1
,
…
,
f
|
R
|
].Observe that if we letE
=
[
A
0
∥
A
1
¯
∥
⋯
∥
A
|
l
|
¯
], we have E
·
T
k
w
=
H
(
k
w
). TA securely transform the query trapdoor to DU. When users want to download ciphertext related to keywords k
w, DU sends T
k
w
=
[
f
0
,
f
1
,
…
,
f
|
R
|
] and a list L corresponds to attribute positive or negative to CSP; ask the CSP to enforce the search ciphertext. Note that DU does not reveal the attribute name to CSP except the positive or negative information of the attributes.Test. CSP receives the trapdoor T
S and list L about the positive or negative information of attributes; let y
0
=
c
0 if i is a positive attribute, and let y
i
=
c
i
1; else let y
i
=
c
i
2. Define y
=
[
y
0
,
y
1
,
…
,
y
|
R
|
]; compute a
=
T
k
w
T
·
y
=
H
(
k
w
)
T
x
+
x
′; let b
=
p
-
a; if b
<
q
/
4, CSP accepts it as a valid ciphertext and outputs 1, otherwise, CSP refuses it as an invalid ciphertext and outputs 0.Decrypt. After receiving the cipthertext from CSP, DU does the decryption procedure as the test phase. Define y
=
[
y
0
,
y
1
,
…
,
y
|
R
|
] as above; compute f
=
S
K
S
T
·
y
=
u
T
x
+
x
′. Define g
=
c
-
f
=
x
c
-
x
′
+
M
q
/
2. Finally if g
-
q
/
2
<
q
/
4 in Z, return 1; otherwise, return 0.


## 4. Security Proof

In this section, we discuss the security proof of our ASE scheme. Comparing ASE scheme with CP-ABE with attribute-hiding and PEKS scheme, we divide our ASE scheme into two parts. If we only choose setup, ABE-KeyGen, encrypt (do not take over the keyword ciphertextp), and decrypt from ASE scheme, our scheme is a CP-ABE scheme with attribute-hiding. If we only choose setup, encrypt (do not take over the first ciphertext c), trapdoor, and test from ASE scheme, our scheme is a PEKS scheme. So we give our security proof of our ASE schemes by the following two theorems.Theorem 6.
IfL
W
E
q
,
χ is hardness problem, then this CP-ABE scheme with attribute-hiding is secure against selective chosen plaintext attack. It means that if there exists an adversary A that breaks the selective chosen plaintext attack game with advantage ɛ, then there exists an algorithm B cloud solve L
W
E
q
,
χ with probability ɛ.Proof.
AlgorithmB has an oracle O
(
·
), the goal of B is to decide whether the samples output by O
(
·
) is from A
s
,
χ or uniform.   B runs adversary A and simulates A’s view selective chosen plaintext attack game as follows.
Init. Adversary A chooses two challenge ciphertext policies W
0
=
[
S
0,1
,
S
0,2
,
…
,
S
0
,
l
] and W
1
=
[
S
1,1
,
S
1,2
,
…
,
S
1
,
l
] and gives them to B. Let S
+
(
S
-
) be the set of positive (negative) attributes in W
0
∪
W
1 and let S
′
=
S
+
∪
S
-.
Setup. After receiving W
0, W
1, B obtains (
A
0
,
v
0
)
∈
Z
q
n
×
m
×
Z
q
m and (
u
,
v
u
)
∈
Z
q
n
×
Z
q from O
(
·
).
For eachi
∈
R
∖
S
′, B obtains (
A
i
+
,
v
i
+
), (
A
i
-
,
v
i
-
)
∈
Z
q
n
×
m
×
Z
q
m from O
(
·
). For each i
∈
S
+, B obtains (
A
i
+
,
v
i
+
)
∈
Z
q
n
×
m
×
Z
q
m from O
(
·
) and then computes (
A
i
-
,
T
A
i
-
)
←
T
r
a
p
G
e
n
(
n
,
m
,
q
). For each i
∈
S
-, B obtains (
A
i
-
,
v
i
-
)
∈
Z
q
n
×
m
×
Z
q
m from O
(
·
) and then computes (
A
i
+
,
T
A
i
+
)
←
T
r
a
p
G
e
n
(
n
,
m
,
q
).
FinallyB sets public key P
K
=
(
A
0
,
{
A
i
+
,
A
i
-
}
i
∈
R
,
u
), while keeping the master secret key ({
T
A
i
-
,
v
i
+
}
i
∈
S
+
,
{
T
A
i
+
,
v
i
-
}
i
∈
S
-
,
{
v
i
+
,
v
i
-
}
i
∈
R
∖
S
′).
KeyGen Queries. B receives a query from A with attribute sets S
⊆
N. If S satisfies W
0 and W
1, B simply outputs ⊥. Otherwise, for each i
∈
R, if i
∈
S, B lets A
i
¯
=
A
i
+; else it lets A
i
¯
=
A
i
-.
SinceS does not satisfy W
0 and W
1, namely, S
+
∩
S
≠
S
+ or S
-
∩
S
≠
S
-, there must exist a j
∈
R, such that A
j
¯ is generated by TrapGen. Hence, B knows its trapdoor T
A
j
¯.
LetE
=
[
A
0
∥
A
1
¯
∥
⋯
∥
A
|
l
|
¯
]; then, for each i
∈
R
∖
j, randomly choose e
i
←
D
Z
m
,
s and compute y
=
u
-
∑
i
∈
R
‍
A
i
¯
e
i, and B computes e
j
←
S
a
m
p
l
e
p
r
e
(
A
j
¯
,
T
A
j
¯
,
s
,
y
) and returns secret key S
K
S
=
[
e
0
,
e
1
,
…
,
e
|
l
|
] and returns S
K
S to A.
Challenge. The adversary A submits messages M
0, M
1 to the challenger. If the adversary obtained the S
K
L whose associated attribute list L satisfies both W
0 and W
1 in Phase 1, then it is asked that M
0
=
M
1. B randomly chooses b
∈
{
0,1
} and computes c
=
v
u
+
M
b
q
/
2 and c
0
=
v
0. For each i
∈
S
+, let c
i
1
=
v
i
+; c
i
2 is a random vector. For each i
∈
S
-, let c
i
2
=
v
i
-; c
i
1 is a random vector. For each i
∈
N
∖
S
′, let c
i
1
=
v
i
+, c
i
2
=
v
i
-.
Finally,B returns C
*
=
(
c
,
c
0
,
{
c
i
1
,
c
i
2
}
i
∈
l
).
Phase 2.  Phase 2 has similar operations to phase 1. If M
0
≠
M
1, the adversary cannot submit L such that L
⊆
W
0
∧
L
⊆
W
1.
A can make more key generation queries with the limitation that the attribute set S does not satisfy W
0 and W
1. Finally, A outputs a bit b
′ as a guess for b. If b
′
=
b, B outputs 1; else it outputs 0.
On one hand, ifO
(
·
) is a L
W
E oracle for some x
*, C
* is a valid ciphertext; thus the distribution of A’s view is statistically close to that in the real game. On the other hand, if O
(
·
) is chosen from uniform, then the ciphertext c is uniform from Z
q; then the probability that A guesses the right b is exactly 1
/
2. Therefore, if A can break our system, B can solve the L
W
E problem.Theorem 7.
Assuming theL
W
E assumption is hardness, this P
E
K
S scheme is IND-PEKS CPA secure in the random oracle model.Proof.
In the random oracle mode, suppose there is a polynomial-time adversaryA that has nonnegligible advantage ɛ attacking the scheme; let the maximum number of H queries be Q
H, and construct an algorithm B to solve the L
W
E problem. B runs A as a subroutine. B uniformly chooses a random index j
←
[
Q
H
] and interacts with A as follows.
Setup. B sends P
K
=
(
A
0
,
{
A
i
+
,
A
i
-
}
i
∈
R
) to A.
Phase 1. B answers queries of A as follows.
Phase 1: Hash Queries. B keeps a list L which is originally empty. The form of L is (
k
w
,
h
,
T
k
w
). Receiving A’s ith distinct query k
w to H, if i
=
j, then B sets h
=
h
*, S
K
T
=
⊥ and gives h
* to A; else, for i
≠
j, B randomly chooses f
i
←
D
Z
m
,
s and returns secret key T
k
w
=
[
f
0
,
f
1
,
…
,
f
|
l
|
]. Let E
=
[
A
0
∥
A
1
¯
∥
⋯
∥
A
|
l
|
¯
]; we have E
·
T
k
w
=
h, and return h to A.
Phase 1: Trapdoor Queries. When A asks for the trapdoor for a keyword k
w, if A has already queried H about k
w, let (
k
w
,
h
,
T
k
w
) be the corresponding tuple in the list L. If T
k
w
=
⊥, then B aborts; otherwise it gives T
k
w to A.
Challenge. A submits two target keywords k
w
0
,
k
w
1 to B, if A has already queried H about k
w
0
,
k
w
1 and meets H
(
k
w
0
)
≠
h
* and H
(
k
w
1
)
≠
h
*; then B aborts. Otherwise, compute c
0
,
{
c
i
1
,
c
i
2
}
i
∈
N as normal; p is chosen from challenge oracle O; p
=
(
h
*
)
T
x
+
x
p or a random number from Z
q. Finally, return ciphertext c
t
=
(
p
,
c
0
,
{
c
i
1
,
c
i
2
}
i
∈
N
).
Notice that ifO is pseudorandom L
W
E, p is a part of an effective encryption; if O is random L
W
E, p is uniform distribution from Z
q.
Phase 2.  B answers A’s query about k
w
∈
{
0,1
}
* as the phase 1; the only limitation is k
w
≠
k
w
0
,
k
w
1.
Guess. A outputs b
′
∈
{
0,1
}; finally, if b
=
b
′, then B outputs 1; otherwise B outputs 0.
We now analyze the reduction. The probability ofB does not abort in the trapdoor query 1
-
1
/
Q
H. In the phase of challenge, the probability of H
k
w
0
=
h
* or H
k
w
1
=
h
* is 2
/
Q
H, so we can get that the advantage of B solving L
W
E is 2
ɛ
(
Q
H
-
1
)
/
Q
H
2.


## 5. Conclusion

We propose an authorized searchable encryption with attribute-hiding from lattices, which only enables authorized users to perform keyword search and then decrypt ciphertext. We are the first to integrate PEKS with CP-ABE based lattices assumption. In contrast to previous solutions [11, 14], our scheme achieves attribute-hiding, which could prevent the revelation of sensitive user information. The security of our schemes is based on LWE assumption; meanwhile data owners can sort ciphertext. If data users want to extract the ciphertext from some time point, they only need to submit trapdoor corresponding to keyword the cloud server.



---

*Source: 314621-2015-07-28.xml*