# Secure Symmetric Keyword Search with Keyword Privacy for Cloud Storage Services

Authors: Taek-Young Youn; Hyun Sook Rhee
Journal: Security and Communication Networks
 (2021)

---

## Abstract

As Internet services are widely used in various mobile devices, the amount of data produced by users steadily increases. Meanwhile, the storage capacity of the various devices is limited to cover the increasing amount of data. Therefore, the importance of Internet-connected storage that can be accessed anytime and anywhere is steadily increasing in terms of storing and utilizing a huge amount of data. To use remote storage, data to be stored need to be encrypted for privacy. The storage manager also should be granted the ability to search the data without decrypting them in response to a query. Contrary to the traditional environment, the query to Internet-connected storage is conveyed through an open channel and hence its secrecy should be guaranteed. We propose a secure symmetric keyword search scheme that provides query privacy and is tailored to the equality test on encrypted data. The proposed scheme is efficient since it is based on prime order bilinear groups. We formally prove that our construction satisfiesciphertext confidentiality and keyword privacy based on the hardness of the bilinear Diffie–Hellman (DH) assumption and the decisional 3-party DH assumption.


---

## Body

## 1. Introduction

According to the development of IT technologies including communications and computations, the use of small devices for daily human life is increasing. Along with the change, the world’s so-called Internet of Everything (for short, IoE) is getting closer to our life. In the IoE world, billions of devices are used for various IT services, including social network websites and applications, which deal with users’ personal data for better IT services [1]. Not all data can be stored and managed in small and low-powered devices, and thus, we need to use Internet-connected storage. Although the use of Internet-connected storage can make it possible to utilize much more data without storing it in local storage, we need to care about the security of data which are stored and managed in remote storage.The main security concern in using Internet-connected storage such as a cloud storage is data privacy [2–4]. The storage inevitably stores and manages the incremental amount of sensitive data on clients. Clients of the storage service must entrust their data to a service provider [5]. Encryption has been the most classical method to provide data privacy. To provide encryption-based access control for clients’ sensitive data, a number of value-added encryption techniques have been studied including attribute encryption techniques [6].A general data protection regulation (GDPR) has forced companies to use encryption of personal data to reduce the probability of a data breach [7]. Accordingly, companies are encrypting, storing. and managing customers’ personal information. When an encryption is used for data privacy, we face another obstacle. The storage server should be given a capability that allows server to identify exactly the documents a client wants to retrieve without decrypting them. As one of the basic steps to resolve this difficulty, secure keyword search over encrypted data is receiving much attention. Secure keyword search enables a user to search the encrypted data with a keyword without revealing any information on the data. When an encrypted document is uploaded to a server, a set of ciphertexts of keywords in the document are appended to the encrypted document. Let CTw denote the ciphertext of keyword w. For a given query (also called trapdoor) Tw′, the server runs the function test with inputs CTw and Tw′ to identify whether or not w=w′. Only the user who can generate query Tw′, such that test CTw,Tw′=1, can retrieve the encrypted documents containing keyword w. Secure keyword search is a primitive to construct various queries and can be extended to the complex queries such as range queries and inner-product queries [8].Secure keyword search systems can be classified into two types: asymmetric and symmetric settings. In the asymmetric setting [9–11], known as public key encryption with keyword search (PEKS), ciphertext CTw of keyword w is generated under a public key and only the owner of the corresponding secret key can generate trapdoor Tw. Hence, PEKS is suitable in a store-and-forward system such as an e-mail system. In the symmetric setting [12–18], ciphertext CTw of keyword w is generated under a symmetric key and only the owner of the key can generate trapdoor Tw using the symmetric key. Here, the symmetric key is not shared but owned by one client. The symmetric setting is suitable to personal storage service as well as a blog and web-hard service, where the same client uploads and downloads his/her data.


### 1.1. Necessity of Keyword Privacy

The formal notion of secure keyword search has considered ciphertext confidentiality, i.e., a semantic security against an attacker who generates the ciphertexts of keywords of her choice. When given a query and a ciphertext of a keyword, the server can decide whether or not the ciphertext is related to the query by running the function test. Therefore, it is not possible to guarantee ciphertext confidentiality without guaranteeing the secrecy of the query (keyword privacy).As stated in [19, 20], it is not possible to provide keyword privacy of the trapdoor in PEKS which is one of the searchable encryptions in asymmetric setting, due to the ciphertext of a guessed keyword. Hence, an adversary can obtain the test result of the ciphertext of the guessed keyword and a given trapdoor. In [11], Rhee et al. firstly defined the notion of a keyword privacy in asymmetric setting. They proposed the enhanced PEKS scheme that the keyword privacy can only be provided in situations where only the server can test whether the ciphertext and trapdoor are related or not. There has been several works providing keyword privacy in the symmetric setting. Shen et al. [20] firstly proposed a symmetric predicate encryption scheme for an inner-product operation of two vectors, which are used in generating a ciphertext and a token (like a trapdoor in PEKS), and considered keyword privacy in a symmetric predicate encryption scheme. Their scheme is constructed on composite-order bilinear groups, which requires 25 times of exponentiations and 30 times of pairing operations of those in prime-order groups [21]. Recently, Blundo et al. [12] proposed a symmetric hidden vector encryption in asymmetric prime-order bilinear groups. However, there exists no efficiently computable morphism between two different groups used and its security depends on the hardness of nonstandard d,m−Q assumption.However, in general, a predicate encryption differs from a searchable encryption in that a decryption occurs at the same time as the test process. Since it is not common to trust the administrator of the server in various cloud environments, it is necessary to separate the decryption and test processes so that the unreliable server cannot perform the decryption. As noted above, the previous results in symmetric predicate encryption and symmetric hidden vector encryption cannot be immediately adopted for symmetric keyword search.Also, the protocols for providing access pattern privacy were proposed in [22, 23]. That is, anyone cannot get which documents contain the keyword. But, access pattern privacy does not provide the keyword privacy from the given queries. The keyword privacy is the more intuitional than the pattern privacy. Once the information of keyword from the queries are revealed, then the privacy of the corresponding ciphertext cannot be guaranteed even though the pattern privacy is guaranteed. Also, the protocols providing access pattern privacy do not satisfy the search correctness. That is, these protocols considering access pattern privacy cause a search error and require the additional efforts for fixing the search error.The comparisons with [20, 21] are shown in Section 4.


### 1.2. Our Contributions

Our contributions in this paper are twofold:(1)
We firstly define the “trapdoor indistinguishability” for keyword privacy in symmetric keyword search against an active adversary who is able to get trapdoors as well as ciphertexts for any nontarget keyword of his choice. This security of a trapdoor guarantees that the keyword does not reveal any information on any keyword.(2)
We construct a practical and secure keyword search, called secure symmetric keyword search (SSKS), which is tailored for Internet-connected storage service. To construct SSKS, we exploit well-known results of PEKS. Moreover, the proposed scheme achieves both ciphertext confidentiality and keyword privacy. Our construction is efficient since it is based on prime-order bilinear groups unlike the scheme in [20]. The security depends on the hardness of standard assumptions. Ciphertext confidentiality is based on the hardness of the bilinear DH and keyword privacy depends on the hardness of the decisional 3-party DH assumption.


## 1.1. Necessity of Keyword Privacy

The formal notion of secure keyword search has considered ciphertext confidentiality, i.e., a semantic security against an attacker who generates the ciphertexts of keywords of her choice. When given a query and a ciphertext of a keyword, the server can decide whether or not the ciphertext is related to the query by running the function test. Therefore, it is not possible to guarantee ciphertext confidentiality without guaranteeing the secrecy of the query (keyword privacy).As stated in [19, 20], it is not possible to provide keyword privacy of the trapdoor in PEKS which is one of the searchable encryptions in asymmetric setting, due to the ciphertext of a guessed keyword. Hence, an adversary can obtain the test result of the ciphertext of the guessed keyword and a given trapdoor. In [11], Rhee et al. firstly defined the notion of a keyword privacy in asymmetric setting. They proposed the enhanced PEKS scheme that the keyword privacy can only be provided in situations where only the server can test whether the ciphertext and trapdoor are related or not. There has been several works providing keyword privacy in the symmetric setting. Shen et al. [20] firstly proposed a symmetric predicate encryption scheme for an inner-product operation of two vectors, which are used in generating a ciphertext and a token (like a trapdoor in PEKS), and considered keyword privacy in a symmetric predicate encryption scheme. Their scheme is constructed on composite-order bilinear groups, which requires 25 times of exponentiations and 30 times of pairing operations of those in prime-order groups [21]. Recently, Blundo et al. [12] proposed a symmetric hidden vector encryption in asymmetric prime-order bilinear groups. However, there exists no efficiently computable morphism between two different groups used and its security depends on the hardness of nonstandard d,m−Q assumption.However, in general, a predicate encryption differs from a searchable encryption in that a decryption occurs at the same time as the test process. Since it is not common to trust the administrator of the server in various cloud environments, it is necessary to separate the decryption and test processes so that the unreliable server cannot perform the decryption. As noted above, the previous results in symmetric predicate encryption and symmetric hidden vector encryption cannot be immediately adopted for symmetric keyword search.Also, the protocols for providing access pattern privacy were proposed in [22, 23]. That is, anyone cannot get which documents contain the keyword. But, access pattern privacy does not provide the keyword privacy from the given queries. The keyword privacy is the more intuitional than the pattern privacy. Once the information of keyword from the queries are revealed, then the privacy of the corresponding ciphertext cannot be guaranteed even though the pattern privacy is guaranteed. Also, the protocols providing access pattern privacy do not satisfy the search correctness. That is, these protocols considering access pattern privacy cause a search error and require the additional efforts for fixing the search error.The comparisons with [20, 21] are shown in Section 4.


## 1.2. Our Contributions

Our contributions in this paper are twofold:(1)
We firstly define the “trapdoor indistinguishability” for keyword privacy in symmetric keyword search against an active adversary who is able to get trapdoors as well as ciphertexts for any nontarget keyword of his choice. This security of a trapdoor guarantees that the keyword does not reveal any information on any keyword.(2)
We construct a practical and secure keyword search, called secure symmetric keyword search (SSKS), which is tailored for Internet-connected storage service. To construct SSKS, we exploit well-known results of PEKS. Moreover, the proposed scheme achieves both ciphertext confidentiality and keyword privacy. Our construction is efficient since it is based on prime-order bilinear groups unlike the scheme in [20]. The security depends on the hardness of standard assumptions. Ciphertext confidentiality is based on the hardness of the bilinear DH and keyword privacy depends on the hardness of the decisional 3-party DH assumption.


## 2. Preliminaries

For giving concrete description, we will use pairing-related operations. So, in this section, we describe some fundamental definitions for pairing, hard problems defined over the operation, and formal definitions for scheme descriptions and security features.


### 2.1. Underlying Mathematical Problems

The pairing operation is defined over an elliptic cubic curve. We will give simple definition of the operation since it is possible to understand our scheme with the knowledge of the property so-called bilinearity of pairing.Definition 1 (bilinear map).
The definition of bilinear groups appears in [9]. Let G and GT be two (multiplicative) cyclic groups of prime order p. We assume that g is a generator of G. e:G×G⟶GT which is a bilinear map with the following properties:(1)
For allu,v∈G and a,b∈ℤ, eua,vb=eu,vab(2)
eg,g≠1 and there is an efficient algorithm to compute map e
To prove the security of our scheme, we use the bilinear Diffie–Hellman assumption and the decision three-party Diffie–Hellman assumption which are defined as follows.Definition 2 (bilinear Diffie–Hellman assumption (BDH)).
The BDH problem [9] is as follows:(1)giveng,ga,gb,gc,Z∈G4×GTas input,computeeg,gabc∈GT.
The BDH assumption is that all polynomial time algorithms have a negligible advantage in solving the BDH problem.Definition 3 (decision 3-party Diffie–Hellman assumption (3-party DH)).
The decision 3-party Diffie–Hellman problem [24] is as follows:(2)giveng,ga,gb,gc,Z∈G5as input, determineifZ=gabcorZis random inG.
The 3-party DH assumption is that all polynomial time algorithms have a negligible advantage in solving the decisional 3-party DH problem.


### 2.2. Formal Definitions for SKSS

We begin by reviewing the formal definition of symmetric keyword search scheme.Definition 4.
A symmetric keyword search scheme (SKSS) can be noted asSSKS= (KG, SEKS, STd, Test) which consists of four algorithms. The algorithms are described as follows:(1)
KGk takes security parameter k∈ℤ+ and generates secret key SK.(2)
SEKSSK,w takes input secret key SK and keyword w∈KW, where KW is a keyword space. It returns ciphertext CTw.(3)
STdSK,w takes input secret key SK and keyword w. It outputs trapdoor Tw.(4)
TestCTw,Tw′ takes input ciphertext CTw and trapdoor Tw′. If W=W′, output “1”; otherwise, output “0.”
For any scheme, it should be guaranteed that it works as intended. More precisely, ifw is identical to w′, then the test algorithm Test, CTw,Tw′ outputs 1. For a SKSS, we define its correctness as follows.Definition 5 (correctness).
For the security parameterk, we define that SSKS algorithm satisfies correctness if there is a SKSS scheme SSKS= (KG, SEKS, STd, Test) which is defined over a keyword space KW and secret key sk←SK; then for any keywords w,w′∈KW,(3)PrTestCTw,Tw′=1−negk,where CTw←SEKSSK,w is valid for a keyword w and Tw′←STdSK,w′ valid for a keyword w′. Here, if neg is negligible, for any constant k, there exists N such that negk<1/nk for n>N.


#### 2.2.1. Ciphertext Confidentiality

Our definition for a ciphertext confidentiality (SEKS-IND-CPA-security) follows the general framework of those given in [9, 12, 13].LetA be an probabilistic polynomial time adversary whose running time is bounded by t, which is a polynomial in a security parameter k. In the experiment of Table 1, A chooses keywords w0 and w1 in the find stage. Given challenge ciphertext CTwb∗ in the guess stage, A tries to correctly guess b. St is used to retain some state information. A is allowed to obtain trapdoors and ciphertexts by querying trapdoor oracle STdSK,w and encryption oracle SEKSSK,w, respectively. But, A is not allowed to obtain the trapdoor of w0 or w1. Otherwise, A could run Test to find out b.OracleSTdSK,wOracleSEKSSK,wSTSet←STSetk∪wCSet←CSetk∪wTw←STdSK,wCTw←SEKSSK,wReturnTwReturnCTwHere, the trapdoor oracleSTdw and the encryption oracle SEKSw are defined as follows.Table 1
Experiment of a ciphertext confidentiality for SSKS.
ExpSSKS,Aseks−ind−cpa−bkSTSet←∅SK←KGkw0,w1,s←ASTdSK;,SEKSSK;findb←0,1CTwb∗←SEKSSK,wbb′←ASTdSK;,SEKSSK;guess,CTwb∗,StIfw0,w1∩STSetk=∅then returnb′ else return 0The advantage ofA attacking a ciphertext confidentiality is defined as follows:(4)AdvSSKS,Aseks−ind−cpak=PrExpSSKS,Aseks−ind−cpa−1k=1−PrExpSSKS,Aseks−ind−cpa−0k=1.Definition 6 (ciphertext confidentiality).
We say thatSSKS scheme satisfies SEKS−IND−CPA-security against an adaptive chosen plaintext attack if for any polynomial adversary A, the advantage AdvSSKS,Aseks−ind−cpak is negligible in security parameter k.


#### 2.2.2. Keyword Privacy

We newly define keyword privacy (KEY-IND-CPA-security) for SSKS. In the experiment of Table2, A tries to correctly guess b of Twb∗. A is allowed to query the trapdoor oracle and the encryption oracle. But, A should not be allowed to obtain the ciphertext of w0 or w1. Otherwise, A could run Test to find out b. A also needs to be restricted in obtaining the trapdoor of w0 or w1. Otherwise, A might find ciphertext CT in the database such that TestCT,Twb  = 1. If the trapdoor of w0 (or w1 is available, A then can easily decide the value of b.Table 2
Experiment of a keyword privacy for SSKS.
ExpSSKS,Akey−ind−cpa−bkSTSet←∅CSet←∅SK←KGkw0,w1,s←ASTdSK;,SEKSSK;findb←0,1;Twb∗←STdSK,wbb′←ASTdSK;,SEKSSK;guess,Twb∗,StIfw0,w1∩STSetk=∅andw0,w1∩CSetk=∅then returnb′ else return 0The advantage ofA attacking a keyword privacy is defined as follows:(5)AdvSSKS,Akey−ind−cpak=PrExpSSKS,Akey−ind−cpa−1k=1−PrExpSSKS,Akey−ind−cpa−0k=1.Definition 7.
(keyword privacy). We say that theSSKS scheme satisfies KEY−IND−CPA-security against an adaptive chosen plaintext attack if for any polynomial adversary A, the advantage AdvSSKS,Akey−ind−cpak is negligible in security parameter k.


## 2.1. Underlying Mathematical Problems

The pairing operation is defined over an elliptic cubic curve. We will give simple definition of the operation since it is possible to understand our scheme with the knowledge of the property so-called bilinearity of pairing.Definition 1 (bilinear map).
The definition of bilinear groups appears in [9]. Let G and GT be two (multiplicative) cyclic groups of prime order p. We assume that g is a generator of G. e:G×G⟶GT which is a bilinear map with the following properties:(1)
For allu,v∈G and a,b∈ℤ, eua,vb=eu,vab(2)
eg,g≠1 and there is an efficient algorithm to compute map e
To prove the security of our scheme, we use the bilinear Diffie–Hellman assumption and the decision three-party Diffie–Hellman assumption which are defined as follows.Definition 2 (bilinear Diffie–Hellman assumption (BDH)).
The BDH problem [9] is as follows:(1)giveng,ga,gb,gc,Z∈G4×GTas input,computeeg,gabc∈GT.
The BDH assumption is that all polynomial time algorithms have a negligible advantage in solving the BDH problem.Definition 3 (decision 3-party Diffie–Hellman assumption (3-party DH)).
The decision 3-party Diffie–Hellman problem [24] is as follows:(2)giveng,ga,gb,gc,Z∈G5as input, determineifZ=gabcorZis random inG.
The 3-party DH assumption is that all polynomial time algorithms have a negligible advantage in solving the decisional 3-party DH problem.


## 2.2. Formal Definitions for SKSS

We begin by reviewing the formal definition of symmetric keyword search scheme.Definition 4.
A symmetric keyword search scheme (SKSS) can be noted asSSKS= (KG, SEKS, STd, Test) which consists of four algorithms. The algorithms are described as follows:(1)
KGk takes security parameter k∈ℤ+ and generates secret key SK.(2)
SEKSSK,w takes input secret key SK and keyword w∈KW, where KW is a keyword space. It returns ciphertext CTw.(3)
STdSK,w takes input secret key SK and keyword w. It outputs trapdoor Tw.(4)
TestCTw,Tw′ takes input ciphertext CTw and trapdoor Tw′. If W=W′, output “1”; otherwise, output “0.”
For any scheme, it should be guaranteed that it works as intended. More precisely, ifw is identical to w′, then the test algorithm Test, CTw,Tw′ outputs 1. For a SKSS, we define its correctness as follows.Definition 5 (correctness).
For the security parameterk, we define that SSKS algorithm satisfies correctness if there is a SKSS scheme SSKS= (KG, SEKS, STd, Test) which is defined over a keyword space KW and secret key sk←SK; then for any keywords w,w′∈KW,(3)PrTestCTw,Tw′=1−negk,where CTw←SEKSSK,w is valid for a keyword w and Tw′←STdSK,w′ valid for a keyword w′. Here, if neg is negligible, for any constant k, there exists N such that negk<1/nk for n>N.


### 2.2.1. Ciphertext Confidentiality

Our definition for a ciphertext confidentiality (SEKS-IND-CPA-security) follows the general framework of those given in [9, 12, 13].LetA be an probabilistic polynomial time adversary whose running time is bounded by t, which is a polynomial in a security parameter k. In the experiment of Table 1, A chooses keywords w0 and w1 in the find stage. Given challenge ciphertext CTwb∗ in the guess stage, A tries to correctly guess b. St is used to retain some state information. A is allowed to obtain trapdoors and ciphertexts by querying trapdoor oracle STdSK,w and encryption oracle SEKSSK,w, respectively. But, A is not allowed to obtain the trapdoor of w0 or w1. Otherwise, A could run Test to find out b.OracleSTdSK,wOracleSEKSSK,wSTSet←STSetk∪wCSet←CSetk∪wTw←STdSK,wCTw←SEKSSK,wReturnTwReturnCTwHere, the trapdoor oracleSTdw and the encryption oracle SEKSw are defined as follows.Table 1
Experiment of a ciphertext confidentiality for SSKS.
ExpSSKS,Aseks−ind−cpa−bkSTSet←∅SK←KGkw0,w1,s←ASTdSK;,SEKSSK;findb←0,1CTwb∗←SEKSSK,wbb′←ASTdSK;,SEKSSK;guess,CTwb∗,StIfw0,w1∩STSetk=∅then returnb′ else return 0The advantage ofA attacking a ciphertext confidentiality is defined as follows:(4)AdvSSKS,Aseks−ind−cpak=PrExpSSKS,Aseks−ind−cpa−1k=1−PrExpSSKS,Aseks−ind−cpa−0k=1.Definition 6 (ciphertext confidentiality).
We say thatSSKS scheme satisfies SEKS−IND−CPA-security against an adaptive chosen plaintext attack if for any polynomial adversary A, the advantage AdvSSKS,Aseks−ind−cpak is negligible in security parameter k.


### 2.2.2. Keyword Privacy

We newly define keyword privacy (KEY-IND-CPA-security) for SSKS. In the experiment of Table2, A tries to correctly guess b of Twb∗. A is allowed to query the trapdoor oracle and the encryption oracle. But, A should not be allowed to obtain the ciphertext of w0 or w1. Otherwise, A could run Test to find out b. A also needs to be restricted in obtaining the trapdoor of w0 or w1. Otherwise, A might find ciphertext CT in the database such that TestCT,Twb  = 1. If the trapdoor of w0 (or w1 is available, A then can easily decide the value of b.Table 2
Experiment of a keyword privacy for SSKS.
ExpSSKS,Akey−ind−cpa−bkSTSet←∅CSet←∅SK←KGkw0,w1,s←ASTdSK;,SEKSSK;findb←0,1;Twb∗←STdSK,wbb′←ASTdSK;,SEKSSK;guess,Twb∗,StIfw0,w1∩STSetk=∅andw0,w1∩CSetk=∅then returnb′ else return 0The advantage ofA attacking a keyword privacy is defined as follows:(5)AdvSSKS,Akey−ind−cpak=PrExpSSKS,Akey−ind−cpa−1k=1−PrExpSSKS,Akey−ind−cpa−0k=1.Definition 7.
(keyword privacy). We say that theSSKS scheme satisfies KEY−IND−CPA-security against an adaptive chosen plaintext attack if for any polynomial adversary A, the advantage AdvSSKS,Akey−ind−cpak is negligible in security parameter k.


## 2.2.1. Ciphertext Confidentiality

Our definition for a ciphertext confidentiality (SEKS-IND-CPA-security) follows the general framework of those given in [9, 12, 13].LetA be an probabilistic polynomial time adversary whose running time is bounded by t, which is a polynomial in a security parameter k. In the experiment of Table 1, A chooses keywords w0 and w1 in the find stage. Given challenge ciphertext CTwb∗ in the guess stage, A tries to correctly guess b. St is used to retain some state information. A is allowed to obtain trapdoors and ciphertexts by querying trapdoor oracle STdSK,w and encryption oracle SEKSSK,w, respectively. But, A is not allowed to obtain the trapdoor of w0 or w1. Otherwise, A could run Test to find out b.OracleSTdSK,wOracleSEKSSK,wSTSet←STSetk∪wCSet←CSetk∪wTw←STdSK,wCTw←SEKSSK,wReturnTwReturnCTwHere, the trapdoor oracleSTdw and the encryption oracle SEKSw are defined as follows.Table 1
Experiment of a ciphertext confidentiality for SSKS.
ExpSSKS,Aseks−ind−cpa−bkSTSet←∅SK←KGkw0,w1,s←ASTdSK;,SEKSSK;findb←0,1CTwb∗←SEKSSK,wbb′←ASTdSK;,SEKSSK;guess,CTwb∗,StIfw0,w1∩STSetk=∅then returnb′ else return 0The advantage ofA attacking a ciphertext confidentiality is defined as follows:(4)AdvSSKS,Aseks−ind−cpak=PrExpSSKS,Aseks−ind−cpa−1k=1−PrExpSSKS,Aseks−ind−cpa−0k=1.Definition 6 (ciphertext confidentiality).
We say thatSSKS scheme satisfies SEKS−IND−CPA-security against an adaptive chosen plaintext attack if for any polynomial adversary A, the advantage AdvSSKS,Aseks−ind−cpak is negligible in security parameter k.


## 2.2.2. Keyword Privacy

We newly define keyword privacy (KEY-IND-CPA-security) for SSKS. In the experiment of Table2, A tries to correctly guess b of Twb∗. A is allowed to query the trapdoor oracle and the encryption oracle. But, A should not be allowed to obtain the ciphertext of w0 or w1. Otherwise, A could run Test to find out b. A also needs to be restricted in obtaining the trapdoor of w0 or w1. Otherwise, A might find ciphertext CT in the database such that TestCT,Twb  = 1. If the trapdoor of w0 (or w1 is available, A then can easily decide the value of b.Table 2
Experiment of a keyword privacy for SSKS.
ExpSSKS,Akey−ind−cpa−bkSTSet←∅CSet←∅SK←KGkw0,w1,s←ASTdSK;,SEKSSK;findb←0,1;Twb∗←STdSK,wbb′←ASTdSK;,SEKSSK;guess,Twb∗,StIfw0,w1∩STSetk=∅andw0,w1∩CSetk=∅then returnb′ else return 0The advantage ofA attacking a keyword privacy is defined as follows:(5)AdvSSKS,Akey−ind−cpak=PrExpSSKS,Akey−ind−cpa−1k=1−PrExpSSKS,Akey−ind−cpa−0k=1.Definition 7.
(keyword privacy). We say that theSSKS scheme satisfies KEY−IND−CPA-security against an adaptive chosen plaintext attack if for any polynomial adversary A, the advantage AdvSSKS,Akey−ind−cpak is negligible in security parameter k.


## 3. New Symmetric Keyword Search with Keyword Privacy

In this section, we give a detailed description for our symmetric keyword search with keyword privacy.Since we use pairing operations for our scheme, we use the following notations. LetG and GT be groups of prime order p, and let e:G×G⟶GT be a bilinear map. We use hash functions H1:0,1∗⟶G and H2:G1⟶0,1logp. Our construction works as follows:KGk takes the security parameter k∈ℤ+ and picks a random exponent α∈ℤp, generator g∈G, and a random value u∈Gu≠g. It outputs secret key(6)SK=K1,K2,K3=α,gα,u.SEKSSK,w takes as input secret key SK and keyword w∈KW, where KW is a keyword space. It picks a random exponent s∈ℤp and returns the ciphertext:(7)CTw=C1,C2,C3=K3s,gs,H2eK2s,H1w.STdSK,w takes as input secret key SK and keyword w. It picks a random exponent r∈ℤp and outputs the corresponding trapdoor:(8)Tw=T1,T2=gr,H1wK1⋅K3r.TestCT,Tw takes as input ciphertext CT and trapdoor Tw and parses CT as C1,C2,C3 and Tw as T1,T2. It checks if the following equality holds:(9)H2eT2,C2eT1,C1=C3.If so, output “1”; otherwise, output “0.”


## 4. Analysis

In this section, we analyze the proposed scheme in terms of security against the security notions discussed in Section2.2. We also compare the proposed scheme with existing schemes to show that our scheme guarantees better security than the existing schemes.


### 4.1. Security

We now prove that our construction satisfies ciphertext confidentiality and keyword privacy. Ciphertext confidentiality is proved as the same manner in [9].Theorem 1.
If thet,ε-decisional BDH assumption holds in G, then our SSKS scheme is SEKS−IND−CPA-secure.Proof.
SupposeA is an adversary that has advantage ϵ in breaking ciphertext confidentiality. We construct ℬ that solves the BDH problem with probability at least ε′=ε/eqTqH2, where e is the base of the natural logarithm and qH2 (resp., qT is the number of hash function H2 queries (resp., the number of trapdoor queries). Given g, u1=ga, u2=gb, and u3=gc∈G, the goal of ℬ is to compute eg,gabc∈GT. ℬ interacts with A as follows:Setup. ℬ picks a random t∈ℤp, and let K2=u1=ga and K3=u=gt.(1)
H1,H2-Queries. As the same manner in [9], ℬ can simulate H1 and H2 queries. If there exists wi,hi,ei,ci∈H1-list, then ℬ responds with hi. Otherwise, ℬ generates a random coin ci∈0,1 so that Prci=0=1/qT+1. If ci=0, then ℬ picks a random ei∈ℤp and sets hi=gb⋅ei∈G. Otherwise, ℬ sets hi=u2ei=gei. ℬ adds the tuple wi,hi,ei,ci to the H1-list and responds to A with H1wi=hi.Similarly, if there existst∈GT such that t,V∈H2-list, then ℬ responds with H2t=V. Otherwise, ℬ responds to a query for H2t by picking a random V∈0,1logp for t and setting H2t=V and adds t,V to the H2-list.Query Phase 1. A makes trapdoor and ciphertext queries as follows:(2)
Trapdoor Queries.ℬ can obtain hj∈G such that H1w=H1wj=hj, where wj,hj,ej,cj∈H1-list such that wj=w. If ci=0, then ℬ reports failure and terminates. Otherwise, since there exists ej∈ℤp such that hj=gej∈G, ℬ picks a random r′∈ℤp and sets K1=gr′ and K2=u1ej⋅ur′. ℬ gives back Tw=K1,K2 for w to A.(3)
Ciphertext Queries.ℬ can obtain hj∈G such that H1w=H1wj=hj, where wj,hj,ej,cj∈H1-list such that wj=w. ℬ picks a random s∈ℤp and sets C1=us, C2=gs and C3=H2eu1s,H1w, where u∈G is the let value in the setup phase. ℬ gives back CT for w to A.Challenge. A outputs challenge keywords w0 and w1. To obtain h0,h1∈G such that H1w0=h0 and H1w1=h1, ℬ queries w0 and w1 to H1-queries. Let wb,hb,eb,cb be the corresponding tuples on the H1-list b=0,1. If both c0=1 and c1=1, then ℬ aborts. Otherwise, since there exists b∈0,1 such that cb=0, ℬ picks a random z∈0,1logp and sets C1∗=u3t, C2∗=u3 and C3∗=z, where t∈ℤp is the selected value in the setup phase. ℬ responds with CT∗=C1∗,C2∗,C3∗.Query Phase 2. ℬ answers the queries in the same manner as phase 1 under the restriction of trapdoor queries of w≠w0,w1.Output. A outputs its guess, b′∈0,1. The value hi=u2ei was set with the probability 1/qT+1 in the setting of the H1 queries. Since A queries the H2 oracle regarding the value of the form eK2,H1wbs=ega,gbceb with the same probability 1/qT+1, there exists one pair of the form eg,gabceb,H2ega,gbceb∈H2-list. Therefore, ℬ picks a random pair t,V∈H2-list and outputs t1/eb as its guess for eg,gabc, where eb is the selected value in the challenge phase. To show that ℬ correctly outputs eg,gabc with probability at least ε′, we should analyze the probability that ℬ does not abort during the simulation.
We define the following events:(1)
Ε1ℬ does not abort as a result of any of A’s trapdoor queries(2)
Ε2ℬ does not abort during challenge phase(3)
Ε3A does not issue a query for either one of(10)H2eK2,H1w0sandH2eK2,H1w1sin the real attack
We can show in the same manner as in [9] that(11)PrΕ1≥1e,PrΕ2≥1qTandPrΕ3≥2ε.
We omit the detailed description.
To prove keyword privacy, we consider a hybrid game which differs on what challenge trapdoorTb∗ is given by the challenger to A. We suppose that Tβ∗ is the real trapdoor Twβ∗β∈0,1, which is the challenge ciphertext given to the adversary during a real security game or is a random R∈G.Theorem 2.
If thet,ε-decisional 3-party DH assumption holds, then our SSKS scheme is KEY−IND−CPA-secure.Proof.
Suppose that there exists at-time adversary A with nonnegligible difference ϵ between its advantage for challenge Tw∗ and its advantage for challenge R∈G. We construct an algorithm ℬ that solves the decisional 3-party DH problem in G. Given a random challenge g,ga,gb,gc,Z, ℬ outputs 1 if Z=gabc and 0 otherwise. ℬ interacts with A as follows:Init. A outputs challenge keywords w0∗,w1∗∈KW. ℬ flips a coin to obtain β∈0,1, internally.Setup. ℬ chooses a random τ∈ℤp and sets unknown secret values K2=gab and K3=gaτ. ℬ chooses random exponents eβ∗, e1,e2,…,eqH1∈ℤp and sets H1wi=Hwβ∗=gceβ∗∈G and H1wi=g1/aei∈Gwi≠w∗.Query Phase 1. A makes trapdoor and ciphertext queries of the form wi≠wβ∗ as follows:(1)
Trapdoor Queries. If wi≠wβ∗, then ℬ chooses a random exponent ri∈ℤp and sets Twi=gri,gbei×uri. If wi=wβ∗, then ℬ aborts.(2)
Ciphertext Queries. If wi=wβ∗, then ℬ aborts. If wi≠wβ∗, then ℬ chooses a random exponent si∈ℤp and sets CTwi=gaτsi,gsi,H2egbsi,gei.Challenge Phase.ℬ chooses a random exponent r∗∈ℤp and outputs the challenge trapdoor for keyword wβ∗ as follows:(12)T∗=gr∗,Zeβ∗×ur∗.Query Phase 2. ℬ answers the queries in the same manner as phase 1 under the restriction of trapdoor and ciphertext queries of w≠w0,w1.Guess. A outputs guess β′∈0,1 in response to the challenge trapdoor. If β=β′, then ℬ outputs 1. Otherwise, ℬ outputs 0.
ℬ’s advantage in solving the decisional 3-party DH problem is directly taken from A’s advantage to distinguish between Twβ∗ and R, except with negligible probability less than or equal to qTqC/p.


### 4.2. Comparison

Since the symmetric searchable encryption scheme is related to symmetric predicate encryption schemes and symmetric searchable encryption providing access pattern privacy, we give the following two categories for correct comparison.


#### 4.2.1. Symmetric Predicate Encryption

There have been several studies providing keyword privacy in the symmetric setting. In [20], symmetric predicate encryption schemes for an inner-product operation of two vectors were proposed and it considered keyword privacy in a symmetric predicate encryption scheme.Their scheme is constructed on composite-order bilinear groups, which requires 25 times of exponentiations and 30 times of pairing operations of those in prime-order groups. Recently, Blundo et al. [12] proposed a symmetric hidden vector encryption in asymmetric prime-order bilinear groups. However, there exists no efficiently computable morphism between two different groups used and its security depends on the hardness of nonstandard d,m−Q assumption. The comparisons with [20, 21] are shown in Table 3. However, as mentioned before, the predicate encryption cannot be immediately adopted for symmetric keyword search on cloud storage services.Table 3
Comparison among symmetric predicate encryptions.
SchemeGroup orderType of pairingHardness assumptionClass of encryptionProposed schemepSymmetricBDH and decision 3-party DHSearchableShen et al. [20]pqrsSymmetricC3DH and DLinear [20]PredicatedBlundo et al. [12]pAsymmetricd,m−Q [12]Predicatedp, q, r, and s: prime values.


#### 4.2.2. Symmetric Searchable Encryption

In the previous works for the symmetric searchable encryption [12–18], only the ciphertext confidentiality was guaranteed. In searchable encryption schemes, if the trapdoor Tw is given, then the server can run the test function with Tw and ciphertext Cw′. When the keyword w from a trapdoor Tw is revealed, the confidentiality of the ciphertext Cw associated with Tw cannot be guaranteed. Once the keyword privacy is ensured, even if we know that the given trapdoor and the ciphertext are associated, we cannot know which keyword is related to the trapdoor and the ciphertext. As shown in Table 4, we firstly defined the keyword privacy in a symmetric searchable encryption scheme and presented an efficient SSKS scheme with ciphertext confidentiality as well as keyword privacy.Table 4
Comparison with symmetric searchable encryptions.
SchemeCTIndKeywordIndSearchingErrorProposed schemeSatisfiedSatisfiedNot relatedWatanabe et al. [18]SatisfiedNot satisfiedRelatedDemertz et al. [17]SatisfiedNot satisfiedRelatedCTInd: ciphertext indistinguishability; KeywordInd: keyword indistinguishability.


#### 4.2.3. Efficiency

Since the access patter privacy is the main security goal of this work, as mentioned in the beginning of Section4.2, we will compare our scheme with predicate encryption schemes. In Table 5, we compare our scheme and the other schemes in terms of functionalities and performances. The table shows that our scheme provides both ciphertext confidentiality and keyword privacy as well as enables to search on encrypted data without any decryption. However, predicate encryption schemes require decryption operations to implement test function in predicate encryption schemes. Therefore, the predicate encryption schemes have the restriction that the test function can be processed by only a trusted party. In comparison with Shen et al.’s scheme and Blundo et al.’s scheme, our scheme requires the similar size in terms of the ciphertext and the smallest size in terms of the trapdoor. Most of all, in the test phase, our scheme needs the smaller computation than other schemes.Table 5
Comparison of security and performance between our scheme and the others.
SchemeFunctionalitiesPerformancesCTIndKeywordIndClassSize (CT)Size (trap)Comp (test)Shen et al. [20]SatisfiedSatisfiedPredicate4G2+2nG2+2ne + DeBlundo et al. [12]SatisfiedSatisfiedPredicate2G2G2p + 2e + DeProposed schemeSatisfiedSatisfiedSearchable2G+logp2G2pCTInd: ciphertext indistinguishability; KeywordInd: keyword indistinguishability; Size (CT): size of PEKS (dPEKS) ciphertext; Size (trap): size of trapdoor (dTrapdoor); Comp (test): computation cost of test (dTest); G: element in G; p: pairings; e: exponentials; De: decryption corresponding to En.


## 4.1. Security

We now prove that our construction satisfies ciphertext confidentiality and keyword privacy. Ciphertext confidentiality is proved as the same manner in [9].Theorem 1.
If thet,ε-decisional BDH assumption holds in G, then our SSKS scheme is SEKS−IND−CPA-secure.Proof.
SupposeA is an adversary that has advantage ϵ in breaking ciphertext confidentiality. We construct ℬ that solves the BDH problem with probability at least ε′=ε/eqTqH2, where e is the base of the natural logarithm and qH2 (resp., qT is the number of hash function H2 queries (resp., the number of trapdoor queries). Given g, u1=ga, u2=gb, and u3=gc∈G, the goal of ℬ is to compute eg,gabc∈GT. ℬ interacts with A as follows:Setup. ℬ picks a random t∈ℤp, and let K2=u1=ga and K3=u=gt.(1)
H1,H2-Queries. As the same manner in [9], ℬ can simulate H1 and H2 queries. If there exists wi,hi,ei,ci∈H1-list, then ℬ responds with hi. Otherwise, ℬ generates a random coin ci∈0,1 so that Prci=0=1/qT+1. If ci=0, then ℬ picks a random ei∈ℤp and sets hi=gb⋅ei∈G. Otherwise, ℬ sets hi=u2ei=gei. ℬ adds the tuple wi,hi,ei,ci to the H1-list and responds to A with H1wi=hi.Similarly, if there existst∈GT such that t,V∈H2-list, then ℬ responds with H2t=V. Otherwise, ℬ responds to a query for H2t by picking a random V∈0,1logp for t and setting H2t=V and adds t,V to the H2-list.Query Phase 1. A makes trapdoor and ciphertext queries as follows:(2)
Trapdoor Queries.ℬ can obtain hj∈G such that H1w=H1wj=hj, where wj,hj,ej,cj∈H1-list such that wj=w. If ci=0, then ℬ reports failure and terminates. Otherwise, since there exists ej∈ℤp such that hj=gej∈G, ℬ picks a random r′∈ℤp and sets K1=gr′ and K2=u1ej⋅ur′. ℬ gives back Tw=K1,K2 for w to A.(3)
Ciphertext Queries.ℬ can obtain hj∈G such that H1w=H1wj=hj, where wj,hj,ej,cj∈H1-list such that wj=w. ℬ picks a random s∈ℤp and sets C1=us, C2=gs and C3=H2eu1s,H1w, where u∈G is the let value in the setup phase. ℬ gives back CT for w to A.Challenge. A outputs challenge keywords w0 and w1. To obtain h0,h1∈G such that H1w0=h0 and H1w1=h1, ℬ queries w0 and w1 to H1-queries. Let wb,hb,eb,cb be the corresponding tuples on the H1-list b=0,1. If both c0=1 and c1=1, then ℬ aborts. Otherwise, since there exists b∈0,1 such that cb=0, ℬ picks a random z∈0,1logp and sets C1∗=u3t, C2∗=u3 and C3∗=z, where t∈ℤp is the selected value in the setup phase. ℬ responds with CT∗=C1∗,C2∗,C3∗.Query Phase 2. ℬ answers the queries in the same manner as phase 1 under the restriction of trapdoor queries of w≠w0,w1.Output. A outputs its guess, b′∈0,1. The value hi=u2ei was set with the probability 1/qT+1 in the setting of the H1 queries. Since A queries the H2 oracle regarding the value of the form eK2,H1wbs=ega,gbceb with the same probability 1/qT+1, there exists one pair of the form eg,gabceb,H2ega,gbceb∈H2-list. Therefore, ℬ picks a random pair t,V∈H2-list and outputs t1/eb as its guess for eg,gabc, where eb is the selected value in the challenge phase. To show that ℬ correctly outputs eg,gabc with probability at least ε′, we should analyze the probability that ℬ does not abort during the simulation.
We define the following events:(1)
Ε1ℬ does not abort as a result of any of A’s trapdoor queries(2)
Ε2ℬ does not abort during challenge phase(3)
Ε3A does not issue a query for either one of(10)H2eK2,H1w0sandH2eK2,H1w1sin the real attack
We can show in the same manner as in [9] that(11)PrΕ1≥1e,PrΕ2≥1qTandPrΕ3≥2ε.
We omit the detailed description.
To prove keyword privacy, we consider a hybrid game which differs on what challenge trapdoorTb∗ is given by the challenger to A. We suppose that Tβ∗ is the real trapdoor Twβ∗β∈0,1, which is the challenge ciphertext given to the adversary during a real security game or is a random R∈G.Theorem 2.
If thet,ε-decisional 3-party DH assumption holds, then our SSKS scheme is KEY−IND−CPA-secure.Proof.
Suppose that there exists at-time adversary A with nonnegligible difference ϵ between its advantage for challenge Tw∗ and its advantage for challenge R∈G. We construct an algorithm ℬ that solves the decisional 3-party DH problem in G. Given a random challenge g,ga,gb,gc,Z, ℬ outputs 1 if Z=gabc and 0 otherwise. ℬ interacts with A as follows:Init. A outputs challenge keywords w0∗,w1∗∈KW. ℬ flips a coin to obtain β∈0,1, internally.Setup. ℬ chooses a random τ∈ℤp and sets unknown secret values K2=gab and K3=gaτ. ℬ chooses random exponents eβ∗, e1,e2,…,eqH1∈ℤp and sets H1wi=Hwβ∗=gceβ∗∈G and H1wi=g1/aei∈Gwi≠w∗.Query Phase 1. A makes trapdoor and ciphertext queries of the form wi≠wβ∗ as follows:(1)
Trapdoor Queries. If wi≠wβ∗, then ℬ chooses a random exponent ri∈ℤp and sets Twi=gri,gbei×uri. If wi=wβ∗, then ℬ aborts.(2)
Ciphertext Queries. If wi=wβ∗, then ℬ aborts. If wi≠wβ∗, then ℬ chooses a random exponent si∈ℤp and sets CTwi=gaτsi,gsi,H2egbsi,gei.Challenge Phase.ℬ chooses a random exponent r∗∈ℤp and outputs the challenge trapdoor for keyword wβ∗ as follows:(12)T∗=gr∗,Zeβ∗×ur∗.Query Phase 2. ℬ answers the queries in the same manner as phase 1 under the restriction of trapdoor and ciphertext queries of w≠w0,w1.Guess. A outputs guess β′∈0,1 in response to the challenge trapdoor. If β=β′, then ℬ outputs 1. Otherwise, ℬ outputs 0.
ℬ’s advantage in solving the decisional 3-party DH problem is directly taken from A’s advantage to distinguish between Twβ∗ and R, except with negligible probability less than or equal to qTqC/p.


## 4.2. Comparison

Since the symmetric searchable encryption scheme is related to symmetric predicate encryption schemes and symmetric searchable encryption providing access pattern privacy, we give the following two categories for correct comparison.


### 4.2.1. Symmetric Predicate Encryption

There have been several studies providing keyword privacy in the symmetric setting. In [20], symmetric predicate encryption schemes for an inner-product operation of two vectors were proposed and it considered keyword privacy in a symmetric predicate encryption scheme.Their scheme is constructed on composite-order bilinear groups, which requires 25 times of exponentiations and 30 times of pairing operations of those in prime-order groups. Recently, Blundo et al. [12] proposed a symmetric hidden vector encryption in asymmetric prime-order bilinear groups. However, there exists no efficiently computable morphism between two different groups used and its security depends on the hardness of nonstandard d,m−Q assumption. The comparisons with [20, 21] are shown in Table 3. However, as mentioned before, the predicate encryption cannot be immediately adopted for symmetric keyword search on cloud storage services.Table 3
Comparison among symmetric predicate encryptions.
SchemeGroup orderType of pairingHardness assumptionClass of encryptionProposed schemepSymmetricBDH and decision 3-party DHSearchableShen et al. [20]pqrsSymmetricC3DH and DLinear [20]PredicatedBlundo et al. [12]pAsymmetricd,m−Q [12]Predicatedp, q, r, and s: prime values.


### 4.2.2. Symmetric Searchable Encryption

In the previous works for the symmetric searchable encryption [12–18], only the ciphertext confidentiality was guaranteed. In searchable encryption schemes, if the trapdoor Tw is given, then the server can run the test function with Tw and ciphertext Cw′. When the keyword w from a trapdoor Tw is revealed, the confidentiality of the ciphertext Cw associated with Tw cannot be guaranteed. Once the keyword privacy is ensured, even if we know that the given trapdoor and the ciphertext are associated, we cannot know which keyword is related to the trapdoor and the ciphertext. As shown in Table 4, we firstly defined the keyword privacy in a symmetric searchable encryption scheme and presented an efficient SSKS scheme with ciphertext confidentiality as well as keyword privacy.Table 4
Comparison with symmetric searchable encryptions.
SchemeCTIndKeywordIndSearchingErrorProposed schemeSatisfiedSatisfiedNot relatedWatanabe et al. [18]SatisfiedNot satisfiedRelatedDemertz et al. [17]SatisfiedNot satisfiedRelatedCTInd: ciphertext indistinguishability; KeywordInd: keyword indistinguishability.


### 4.2.3. Efficiency

Since the access patter privacy is the main security goal of this work, as mentioned in the beginning of Section4.2, we will compare our scheme with predicate encryption schemes. In Table 5, we compare our scheme and the other schemes in terms of functionalities and performances. The table shows that our scheme provides both ciphertext confidentiality and keyword privacy as well as enables to search on encrypted data without any decryption. However, predicate encryption schemes require decryption operations to implement test function in predicate encryption schemes. Therefore, the predicate encryption schemes have the restriction that the test function can be processed by only a trusted party. In comparison with Shen et al.’s scheme and Blundo et al.’s scheme, our scheme requires the similar size in terms of the ciphertext and the smallest size in terms of the trapdoor. Most of all, in the test phase, our scheme needs the smaller computation than other schemes.Table 5
Comparison of security and performance between our scheme and the others.
SchemeFunctionalitiesPerformancesCTIndKeywordIndClassSize (CT)Size (trap)Comp (test)Shen et al. [20]SatisfiedSatisfiedPredicate4G2+2nG2+2ne + DeBlundo et al. [12]SatisfiedSatisfiedPredicate2G2G2p + 2e + DeProposed schemeSatisfiedSatisfiedSearchable2G+logp2G2pCTInd: ciphertext indistinguishability; KeywordInd: keyword indistinguishability; Size (CT): size of PEKS (dPEKS) ciphertext; Size (trap): size of trapdoor (dTrapdoor); Comp (test): computation cost of test (dTest); G: element in G; p: pairings; e: exponentials; De: decryption corresponding to En.


## 4.2.1. Symmetric Predicate Encryption

There have been several studies providing keyword privacy in the symmetric setting. In [20], symmetric predicate encryption schemes for an inner-product operation of two vectors were proposed and it considered keyword privacy in a symmetric predicate encryption scheme.Their scheme is constructed on composite-order bilinear groups, which requires 25 times of exponentiations and 30 times of pairing operations of those in prime-order groups. Recently, Blundo et al. [12] proposed a symmetric hidden vector encryption in asymmetric prime-order bilinear groups. However, there exists no efficiently computable morphism between two different groups used and its security depends on the hardness of nonstandard d,m−Q assumption. The comparisons with [20, 21] are shown in Table 3. However, as mentioned before, the predicate encryption cannot be immediately adopted for symmetric keyword search on cloud storage services.Table 3
Comparison among symmetric predicate encryptions.
SchemeGroup orderType of pairingHardness assumptionClass of encryptionProposed schemepSymmetricBDH and decision 3-party DHSearchableShen et al. [20]pqrsSymmetricC3DH and DLinear [20]PredicatedBlundo et al. [12]pAsymmetricd,m−Q [12]Predicatedp, q, r, and s: prime values.


## 4.2.2. Symmetric Searchable Encryption

In the previous works for the symmetric searchable encryption [12–18], only the ciphertext confidentiality was guaranteed. In searchable encryption schemes, if the trapdoor Tw is given, then the server can run the test function with Tw and ciphertext Cw′. When the keyword w from a trapdoor Tw is revealed, the confidentiality of the ciphertext Cw associated with Tw cannot be guaranteed. Once the keyword privacy is ensured, even if we know that the given trapdoor and the ciphertext are associated, we cannot know which keyword is related to the trapdoor and the ciphertext. As shown in Table 4, we firstly defined the keyword privacy in a symmetric searchable encryption scheme and presented an efficient SSKS scheme with ciphertext confidentiality as well as keyword privacy.Table 4
Comparison with symmetric searchable encryptions.
SchemeCTIndKeywordIndSearchingErrorProposed schemeSatisfiedSatisfiedNot relatedWatanabe et al. [18]SatisfiedNot satisfiedRelatedDemertz et al. [17]SatisfiedNot satisfiedRelatedCTInd: ciphertext indistinguishability; KeywordInd: keyword indistinguishability.


## 4.2.3. Efficiency

Since the access patter privacy is the main security goal of this work, as mentioned in the beginning of Section4.2, we will compare our scheme with predicate encryption schemes. In Table 5, we compare our scheme and the other schemes in terms of functionalities and performances. The table shows that our scheme provides both ciphertext confidentiality and keyword privacy as well as enables to search on encrypted data without any decryption. However, predicate encryption schemes require decryption operations to implement test function in predicate encryption schemes. Therefore, the predicate encryption schemes have the restriction that the test function can be processed by only a trusted party. In comparison with Shen et al.’s scheme and Blundo et al.’s scheme, our scheme requires the similar size in terms of the ciphertext and the smallest size in terms of the trapdoor. Most of all, in the test phase, our scheme needs the smaller computation than other schemes.Table 5
Comparison of security and performance between our scheme and the others.
SchemeFunctionalitiesPerformancesCTIndKeywordIndClassSize (CT)Size (trap)Comp (test)Shen et al. [20]SatisfiedSatisfiedPredicate4G2+2nG2+2ne + DeBlundo et al. [12]SatisfiedSatisfiedPredicate2G2G2p + 2e + DeProposed schemeSatisfiedSatisfiedSearchable2G+logp2G2pCTInd: ciphertext indistinguishability; KeywordInd: keyword indistinguishability; Size (CT): size of PEKS (dPEKS) ciphertext; Size (trap): size of trapdoor (dTrapdoor); Comp (test): computation cost of test (dTest); G: element in G; p: pairings; e: exponentials; De: decryption corresponding to En.


## 5. Conclusions

In this paper, we proposed a practical and secure keyword search, called secure symmetric keyword search (SSKS), which is tailored for cloud storage service. We firstly defined the keyword privacy in a symmetric searchable encryption scheme and presented SSKS scheme that guarantees ciphertext confidentiality as well as keyword privacy. Our SSKS systems and the new security model for key privacy in the symmetric setting can be further exploited to construct symmetric searchable encryption schemes providing extended queries such as conjunctive and inner-product queries [25–27].



---

*Source: 2291470-2021-11-30.xml*