# A Dynamic Searchable Symmetric Encryption Scheme for Multiuser with Forward and Backward Security

Authors: Xi Zhang; Ye Su; Jing Qin
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Dynamic Searchable Symmetric Encryption for Multiuser (M-DSSE) is an advanced form of symmetric encryption. It extends the traditional symmetric encryption to support the operations of adding and deleting the encrypted data and allow an authenticated group of data users to retrieve their respective desired encrypted data in the dynamic database. However, M-DSSE would suffer from the privacy concerns regarding forward and backward security. The former allows an attacker to identify the keywords contained in the added data by lunching file-injection attacks, while the latter allows to utilize the search results and the deleted data to learn the content. To our knowledge, these privacy concerns for M-DSSE have not been fully considered in the existing literatures. Taking account of this fact, we focus on the dynamic searchable symmetric encryption for multiuser meeting the needs of forward and backward security. In order to propose a concrete scheme, the primitives of Pseudorandom Functions (PRF) and the Homomorphic Message Authenticator (HMAC) are employed to construct the inverted index and update the search token. The proposed scheme is proven secure in the random model. And the performance analysis shows that the proposed scheme achieves the enhanced security guarantees at the reasonable price of efficiency.


---

## Body

## 1. Introduction

Searchable encryption (SE) is popular among the various cloud storage services because one can keep the ability to selectively retrieve the encrypted data that he or she stored on the cloud. And there are many traditional works [1–5] focusing on it. However, the traditional works cannot meet the using needs or habits of the clients. It is because frequently clients upload some new data and delete or modify some encrypted data in cloud and many clients often share data with others. For example, a regional medical center needs to update the local Electronic Health Records (EHRs) [6] periodically and share them with other medical institutions to conduct advanced research. This means that the regional medical center should have the ability of updating the encrypted data and authorizing others to search over his data storage in cloud.To address it, some dynamic searchable encryption schemes [7–11] have been proposed to support data updates. These works are designed for the single client that means only the client itself can search on the cloud and cannot meet the requirement to share data. Data sharing is widely used by both individuals and organizations, and we introduce two forms here: one is multiwriter/multireader and the other is single writer/multireader. For ease of exposition, we call the client who owns data the data owner and the clients who share the data the data user. The former means many data owners and many data users, and there have been efforts to design schemes for fine-grained keyword search [12, 13], privacy-preserving attribute-based keyword search [14], and rank keyword search in arbitrary language [15]. The latter means only one data owner and many data users who are especially popular among companies, schools, and medical institutions. It was named as dynamic searchable symmetric encryption for multiuser (M-DSSE), which was also called multiclient in [16], and it is the topic that we are interested in.However, M-DSSE suffers from the privacy concerns regarding forward and backward security. The former is that the adversary can use the file-injection attacks to compromise the privacy of the data and keywords. This attack was proposed by Zhang et al. [17] in 2016. More specifically, one can inject the carefully selected files and trick the client into encrypting them, then identify the keyword by matching the submitted search tokens and injected files, and consequently get all files containing this keyword. This behavior seriously undermines the privacy of data, for example, the disclosure of the patient’s identity information or home address in EHRs that should be kept private. The latter means that, in most searchable encryption schemes, the identifier of the deleted document still can be retrieved by the server in the subsequent search. Then when the regional medical center deletes some EHRs, not only the privacy of the patients will be disclosed, but also the accuracy of the advanced research will be affected.Both attacks are simple but destructive. Therefore, M-DSSE needs stronger security from a practical and safe point of view, that is, Dynamic Searchable Symmetric Encryption for Multiuser with Forward and Backward Security (FBM-DSSE). Although there are many works concentrating on the dynamic symmetric searchable encryption schemes with forward and backward security (FB-DSSE) [18–22], most of them cannot be extended to FBM-DSSE directly. On the one hand, if the method used in FB-DSSE is extended to FBM-DSSE directly, the data owner may need to share the whole key with all users. And users can do more rather than search only. Specifically, users can change client’s data without restrictions and destroy data's integrity and privacy. On the other hand, the existing FB-DSSE schemes adopt some special structures to achieve forward and backward security, which is not suitable to extend to multiuser setting. For example, Li et al. [23] reduce information leakage in SSE by partitioning the inverted index into disjoint partitions and generating subkeyword sets. When searching, the data owner chooses subkeyword according to his own needs and the server needs to delete all the touched blocks after each search. This search method is complex for users in M-DSSE and may get incomplete search results due to untimely updates. Therefore, it is not feasible to directly implement the methods of FB-DSSE in FBM-DSSE, and it is still a problem that how to achieve forward and backward security in M-DSSE.Considering the serious consequences that these security issues may bring and the inflexibility of the methods from FB-DSSE to FBM-DSSE, we believe that solving security problems in FBM-DSSE is of great practical significance. Taking account of it, we focus on the Dynamic Searchable Symmetric encryption schemes supporting multiuser with Forward and Backward Security. In order to achieve this it, we give a concrete FBM-DSSE scheme based on the Pseudorandom Functions (PRF), the Homomorphic Message Authenticator (HMAC) [24], and the bitmap index [25, 26].Our contributions are summarized as follows:The proposed scheme is forward and backward secure. We combine the homomorphic MAC and the bitmap index to achieve secure and efficient updates of the search token and use PRF to hide the specific correspondence between files and indexes to protect the update information from being leaked. Specifically, we use pseudorandom functions to reorder files and the keywords in index and the server could not identify the specific relationship between them so that it could not get any private information except the current search results.The proposed scheme has rich functionality. It is obvious that the proposed scheme supports update operations and multiuser setting. It also supports verifiability and can realize revocation of the user’s access permission. Specifically, if the data owner wants to cancel someone’s access right to the updated file but retain the permission for the previously searched file, he or she is not needed to send the updated search token to the user. Furthermore, our scheme is easily extended to support multifunctional search such as wildcard search [27], similarity search (including hamming distance and edit distance), fuzzy keyword search [28], and disjunctive [29] (or conjunctive [30]) keyword search.The proposed scheme has a comprehensive security analysis. We give the correctness of the scheme and the rigorous security proof of forward and backward security according to the definitions in DSSE. And the security of the proposed scheme can be reduced to the existence of pseudorandom functions and the CPA-secure symmetric encryption system, which provides a concrete implementation favorable guarantee.The paper is organized as follows. Section1 is the introduction. Section 2 introduces the related work. Cryptographic tools and notations are introduced in Section 3. Section 4 presents the system model, security model, and the definition of the forward security and the backward security. Section 5 mainly introduces the proposed scheme and the security analysis. Section 6 shows simply how the proposed scheme can be extended to support multifunctional search. Section 7 gives the experiment result and its analyses. At last, the paper is concluded in Section 8.


## 2. Related Works

Searchable encryption (SE) is popular among various cloud storage services because it protects plaintext information from being leaked to the compromised server while preserving the search functionality. There are two areas in SE: public key encryption with keyword search (PEKS) [2–5] and searchable symmetric encryption (SSE). In our work, we mainly talk about the SSE.The first symmetric searchable encryption (SSE) was proposed by Song et al. [1] in 2000. They proposed a special two-layer encryption scheme. Because this scheme needs to scan the file, the searching time is linear to the length of the files. The followed work is that of Curtmola et al. [31]. They constructed the first inverted index and achieved that the amount of the server’s work is proportional to the number of files containing the queried keyword. There are also many SSE schemes concentrating on rich queries [32–34]. However, those works mainly focused on searchable encryption under static conditions, that is, there is no update of files. Due to the universality of dynamic operation, it is important and necessary to migrate it to the cloud services. Therefore, the dynamic searchable encryption (DSSE) is more in line with the practical situation.In 2012, Kamara et al. [7] constructed a DSSE scheme based on the inverted index technique and achieved sublinear search complexity and CKA2-secure. And then they [8] constructed another dynamic searchable encryption scheme based on the red-black tree index and achieved parallel search of keywords and parallel addition and deletion of files. There are others scheme including Naveed et al. [9] based on the blind storage, Xia et al. [10] based on the tree-based index, and Guo et al. [11] based on the inverted index. At the same time, DSSE schemes leak some information such as search pattern (the pattern in search queries), size pattern [18] (the number of search results), and access pattern (how the encrypted data or indexes are accessed). These attracted people’s attention. Zhang et al. [17] proposed a file-injection attack in 2016, and the attacker can determine the keywords corresponding to the token by injecting files containing different keywords. The effective attack calls for the stronger security of DSSE. The trivial way of downloading and then decrypting the full encrypted files to obtain the needed files contradicts the purpose of search encryption. The ways of using secure two-party computation, fully homomorphic encryption, and oblivious RAM to realize the higher level of security waste more local storage space and acquire high computational and communication complexity. Both of them are very expensive and impractical.In 2014, the term of forward privacy and backward privacy was first proposed by Stefanov et al. [18], and it is the new secure goal that dynamic searchable encryption schemes should meet in the practical level. Since 2014, some schemes have been proposed to achieve it using different methods, including but not limited to Stefanov et al.[18] based on a hierarchical structure of logarithmic levels; Bost [19] based on trapdoor permutations, and then they proposed a forward and backward scheme relying on primitives such as constrained pseudorandom functions and puncturable encryption schemes[35]; Wang et al.[20] based on the proxy server; Sun et al.[21] based on the symmetric puncture encryption primitive; and Kim et al.[22] based on dual dictionary.As for the DSSE for multiusers, some works have been carried out. As for multiwriter/multireader, Nair and Rajasree [13] used a bilinear accumulator to implement a fine-grained multiuser solution for search control and access control; Popa and Zeldovich [36] proposed a method for encrypting different files with different keys. As for single writer/multireader, Curtmola et al. [31] proposed the first scheme structure based on broadcast encryption; Wang et al. [20] proposed a multiuser forward secure dynamic searchable symmetric encryption in 2018; Jarecki et al. [37] used the forgotten PRF to generate keyword trapdoors. However, the research on the Dynamic Searchable Symmetric Encryption for multiusers with Forward and Backward Security (FBM-DSSE) is not enough.


## 3. Cryptographic Tools and Notions

### 3.1. Cryptographic Tools

#### 3.1.1. Pseudorandom Functions

There are security parameterλ and κ polynomial in λ. There are key space K=0,1κ, domain D, and output space ℛ. Let F:K×D⟶ℛ be a keyed function. We define(1)AdvA,FPRFλ=PrAFK⋅1λ=1:K⟵K−PrAϕ⋅y=1,as the advantage of the adversary A against the pseudorandomness of F, where K is a random element in key space and ϕ:D⟶ℛ is chosen in all functions from D to ℛ. If for any PPT adversary A, the advantage AdvA,FPRFλ is a negligible function; then, we say that F is a negligible function.


#### 3.1.2. Homomorphic MAC

In this paper, we will use a construction of a homomorphic message authenticator scheme (HMAC) allowing for homomorphic evaluation and arbitrary composition (i.e., outputs of previously authenticated computations can be used as inputs for new ones). The scheme is simple and efficient and its security relies only on a pseudorandom function.A HMAC is 4-tuple of algorithms working as follows:Setup:1λ⟶sk,ek. For a security parameter 1λ, the algorithm outputs the secret key sk and evaluation key ek needed in the scheme.Auth:sk,τ,m⟶σ. This algorithm inputs the secret key sk, a label τ, and a message m∈M, and it outputs the corresponding tag σ.Ver:sk,m,P,σ⟶0or1. This algorithm inputs the secret key sk, a program P=f,τ1,…,τn, a message m, and its tag σ, and it outputs 0 (reject) or 1 (accept).Eval:ek,f,σ1,…,σn⟶σ. This algorithm inputs the evaluation key sk, a circuit f:Mn⟶M, and σ1,...,σn, and it outputs a new tag σ.We restrict that the arithmetic circuitsf used in the proposed scheme only has the additive gates, so the size of the produced tags will not grow. The concrete description of the HMAC scheme is shown in [24].


#### 3.1.3. Symmetric Encryption

A symmetric encryption consists of the following algorithms:Gen:1λ⟶sk. For a security parameter 1λ, the algorithm outputs the secret key sk needed in the scheme.Enc:sk,m⟶c. This algorithm inputs the secret key sk and a message m∈M, and it outputs the corresponding ciphertext c. Since Enc may be randomized, we write this as c⟵Encskm.Dec:sk,c. This algorithm inputs the secret key sk and ciphertext c, and it outputs mor⊥. We assume that Dec is deterministic, and so write m:=Decskc.CPA-Secure: there is a symmetric encryption Π=Gen,Enc,Dec, and the IND-CPA experiment is shown below.PrivkA,ΠCPAn:(1)
k⟵Gen1n.(2)
Send1n to adversary A, and A can ask the random oracle c⟵Encskm. At last, A outputs m0,m1, where m0=m1.(3)
b⟵R0,1, c⟵Encskmb and send it to A, where c is named to the challenge ciphertext.(4)
A continues to ask the random oracle c⟵Encskm and outputs a bit b′.(5)
Ifb′=b, then PrivkA,ΠCPAn=1, otherwise PrivkA,ΠCPAn=0.Definition 1.
A symmetric encryptionΠ=Gen,Enc,Dec is CPA-Secure only if for all Probability Polynomial adversary A, and there exists a negligible function negl:(2)PrPrivkA,ΠCPAn=1≤12+negln.


### 3.2. Notations

We show some notations used in the proposed scheme in Table1.Table 1
Notations (used in our scheme).
NotationDescriptionP1A secure keyed PRF used to generate the key forHMAC.Auth algorithmP2A secure keyed PRF used to generate the key forHMAC.Eval algorithmRA secure PRF family used to generate the file's columnlMaximum number of files corresponding to security parametersHA secure keyed PRF used to generate the key of columnH1A secure PRF used to generate the keyword's hashQA secure PRF family used to generate the row order of keywordsWThe set of keywords extracted from the fileFThe set of filescTo column c of the index1≤c≤lkcThe key corresponding to column c of the indexCcThe ciphertext of the file corresponding to the cth column of the indexCFThe ciphertext of the set of the filesFCFtThe ciphertext of the set of the files F at timetαitPlaintext of rowi of index at time tτThe input label of HMACF′The file set that does not updatefctAt timet, the plaintext of the file corresponding to column c of indexΔFΔF=f,opfΔWΔW=w,opw


## 3.1. Cryptographic Tools

### 3.1.1. Pseudorandom Functions

There are security parameterλ and κ polynomial in λ. There are key space K=0,1κ, domain D, and output space ℛ. Let F:K×D⟶ℛ be a keyed function. We define(1)AdvA,FPRFλ=PrAFK⋅1λ=1:K⟵K−PrAϕ⋅y=1,as the advantage of the adversary A against the pseudorandomness of F, where K is a random element in key space and ϕ:D⟶ℛ is chosen in all functions from D to ℛ. If for any PPT adversary A, the advantage AdvA,FPRFλ is a negligible function; then, we say that F is a negligible function.


### 3.1.2. Homomorphic MAC

In this paper, we will use a construction of a homomorphic message authenticator scheme (HMAC) allowing for homomorphic evaluation and arbitrary composition (i.e., outputs of previously authenticated computations can be used as inputs for new ones). The scheme is simple and efficient and its security relies only on a pseudorandom function.A HMAC is 4-tuple of algorithms working as follows:Setup:1λ⟶sk,ek. For a security parameter 1λ, the algorithm outputs the secret key sk and evaluation key ek needed in the scheme.Auth:sk,τ,m⟶σ. This algorithm inputs the secret key sk, a label τ, and a message m∈M, and it outputs the corresponding tag σ.Ver:sk,m,P,σ⟶0or1. This algorithm inputs the secret key sk, a program P=f,τ1,…,τn, a message m, and its tag σ, and it outputs 0 (reject) or 1 (accept).Eval:ek,f,σ1,…,σn⟶σ. This algorithm inputs the evaluation key sk, a circuit f:Mn⟶M, and σ1,...,σn, and it outputs a new tag σ.We restrict that the arithmetic circuitsf used in the proposed scheme only has the additive gates, so the size of the produced tags will not grow. The concrete description of the HMAC scheme is shown in [24].


### 3.1.3. Symmetric Encryption

A symmetric encryption consists of the following algorithms:Gen:1λ⟶sk. For a security parameter 1λ, the algorithm outputs the secret key sk needed in the scheme.Enc:sk,m⟶c. This algorithm inputs the secret key sk and a message m∈M, and it outputs the corresponding ciphertext c. Since Enc may be randomized, we write this as c⟵Encskm.Dec:sk,c. This algorithm inputs the secret key sk and ciphertext c, and it outputs mor⊥. We assume that Dec is deterministic, and so write m:=Decskc.CPA-Secure: there is a symmetric encryption Π=Gen,Enc,Dec, and the IND-CPA experiment is shown below.PrivkA,ΠCPAn:(1)
k⟵Gen1n.(2)
Send1n to adversary A, and A can ask the random oracle c⟵Encskm. At last, A outputs m0,m1, where m0=m1.(3)
b⟵R0,1, c⟵Encskmb and send it to A, where c is named to the challenge ciphertext.(4)
A continues to ask the random oracle c⟵Encskm and outputs a bit b′.(5)
Ifb′=b, then PrivkA,ΠCPAn=1, otherwise PrivkA,ΠCPAn=0.Definition 1.
A symmetric encryptionΠ=Gen,Enc,Dec is CPA-Secure only if for all Probability Polynomial adversary A, and there exists a negligible function negl:(2)PrPrivkA,ΠCPAn=1≤12+negln.


## 3.1.1. Pseudorandom Functions

There are security parameterλ and κ polynomial in λ. There are key space K=0,1κ, domain D, and output space ℛ. Let F:K×D⟶ℛ be a keyed function. We define(1)AdvA,FPRFλ=PrAFK⋅1λ=1:K⟵K−PrAϕ⋅y=1,as the advantage of the adversary A against the pseudorandomness of F, where K is a random element in key space and ϕ:D⟶ℛ is chosen in all functions from D to ℛ. If for any PPT adversary A, the advantage AdvA,FPRFλ is a negligible function; then, we say that F is a negligible function.


## 3.1.2. Homomorphic MAC

In this paper, we will use a construction of a homomorphic message authenticator scheme (HMAC) allowing for homomorphic evaluation and arbitrary composition (i.e., outputs of previously authenticated computations can be used as inputs for new ones). The scheme is simple and efficient and its security relies only on a pseudorandom function.A HMAC is 4-tuple of algorithms working as follows:Setup:1λ⟶sk,ek. For a security parameter 1λ, the algorithm outputs the secret key sk and evaluation key ek needed in the scheme.Auth:sk,τ,m⟶σ. This algorithm inputs the secret key sk, a label τ, and a message m∈M, and it outputs the corresponding tag σ.Ver:sk,m,P,σ⟶0or1. This algorithm inputs the secret key sk, a program P=f,τ1,…,τn, a message m, and its tag σ, and it outputs 0 (reject) or 1 (accept).Eval:ek,f,σ1,…,σn⟶σ. This algorithm inputs the evaluation key sk, a circuit f:Mn⟶M, and σ1,...,σn, and it outputs a new tag σ.We restrict that the arithmetic circuitsf used in the proposed scheme only has the additive gates, so the size of the produced tags will not grow. The concrete description of the HMAC scheme is shown in [24].


## 3.1.3. Symmetric Encryption

A symmetric encryption consists of the following algorithms:Gen:1λ⟶sk. For a security parameter 1λ, the algorithm outputs the secret key sk needed in the scheme.Enc:sk,m⟶c. This algorithm inputs the secret key sk and a message m∈M, and it outputs the corresponding ciphertext c. Since Enc may be randomized, we write this as c⟵Encskm.Dec:sk,c. This algorithm inputs the secret key sk and ciphertext c, and it outputs mor⊥. We assume that Dec is deterministic, and so write m:=Decskc.CPA-Secure: there is a symmetric encryption Π=Gen,Enc,Dec, and the IND-CPA experiment is shown below.PrivkA,ΠCPAn:(1)
k⟵Gen1n.(2)
Send1n to adversary A, and A can ask the random oracle c⟵Encskm. At last, A outputs m0,m1, where m0=m1.(3)
b⟵R0,1, c⟵Encskmb and send it to A, where c is named to the challenge ciphertext.(4)
A continues to ask the random oracle c⟵Encskm and outputs a bit b′.(5)
Ifb′=b, then PrivkA,ΠCPAn=1, otherwise PrivkA,ΠCPAn=0.Definition 1.
A symmetric encryptionΠ=Gen,Enc,Dec is CPA-Secure only if for all Probability Polynomial adversary A, and there exists a negligible function negl:(2)PrPrivkA,ΠCPAn=1≤12+negln.


## 3.2. Notations

We show some notations used in the proposed scheme in Table1.Table 1
Notations (used in our scheme).
NotationDescriptionP1A secure keyed PRF used to generate the key forHMAC.Auth algorithmP2A secure keyed PRF used to generate the key forHMAC.Eval algorithmRA secure PRF family used to generate the file's columnlMaximum number of files corresponding to security parametersHA secure keyed PRF used to generate the key of columnH1A secure PRF used to generate the keyword's hashQA secure PRF family used to generate the row order of keywordsWThe set of keywords extracted from the fileFThe set of filescTo column c of the index1≤c≤lkcThe key corresponding to column c of the indexCcThe ciphertext of the file corresponding to the cth column of the indexCFThe ciphertext of the set of the filesFCFtThe ciphertext of the set of the files F at timetαitPlaintext of rowi of index at time tτThe input label of HMACF′The file set that does not updatefctAt timet, the plaintext of the file corresponding to column c of indexΔFΔF=f,opfΔWΔW=w,opw


## 4. System Model and Security Model

### 4.1. System Model and Security Model

As shown in Figure1, the system model consists of three entities: the data owner, data users, and the cloud server.Figure 1
Architecture of our scheme.


#### 4.1.1. Data Owner

The data owner extracts the keywords from files and constructs the plain index. Then, he encrypts all files and the index with different private keys and uploads the encrypted EDB to the cloud server. Besides that, he is also responsible for managing users and updating files. More specifically, he distributes keys, updates tokens to users, and sends the updated encrypted files and index to the cloud server. And the data owner is assumed to be always trusted.


#### 4.1.2. Cloud Server

The main job of the cloud server is to store the encrypted files and index from data owner and perform searches for data users. When receiving the updated information from the data owner, it updates the encrypted database. Upon receiving the search requests from data users, it performs search operation over the index and returns the search results to data users. The cloud server is regarded as an honest but curious entity. That is to say, it performs algorithms honestly but will try its best to get more valuable information. Besides, the cloud server may return invalid or nonupdated search results to the data user because of computation mistakes.


#### 4.1.3. Data Users

Data users are authorized and shared with some keys needed in the scheme by the data owner. When they want to search files containing the interested keyword, they send the search token to cloud server and receive the search results. Furthermore, they can verify the validity of the results with the help of the data owner. The data users are assumed to be always trusted.


### 4.2. Security Model

We use two gamesDSSEREALAΓ1λ and DSSEIDEALA,SΓ1λ to show the security definition of DSSE. The DSSEREALAΓ1λ is the same as the DSSE. And the DSSEIDEALA,SΓ1λ is conducted by simulator S with the leakage of DSSE. The leakage of DSSE is parameterized by a function ℒ=ℒStp,ℒSrch,ℒUpdt, which describes the information leaked to the adversary A. The adversary A will interact with DSSEREALAΓ1λ or DSSEIDEALA,SΓ1λ and guess. If the adversary A can correctly guess the game he interacts only with a negligible advantage, then we can say the DSSE is secure because of the leaked information limited to the leakage function ℒ.DSSEREALAΓ1λ: the adversary A chooses a database DB and inputs it, then this game performs the Setup1λ,DB and outputs EDB. During the search phase, the adversary A runs search query q or update query op,in, where op is the operation and the in is the identifier of the file. The game outputs the search results by performing Searchq or Updateop,in. Eventually, A outputs a bit.DSSEIDEALA,SΓ1λ: the adversary A chooses a database DB and inputs it; then, the simulator S performs the ℒStp1λ,DB and outputs EDB. During the search phase, the adversary A runs search query q or update query op,in. The simulator S outputs the search results by performing the leakage function ℒSrchq or ℒUpdtop,in. Eventually, A outputs a bit.Definition 2.
A DSSE schemeΓis ℒ-adaptively secure only if for every PPT adversaryA, and there exists an efficient simulator S and a negligible function negl such that(3)PDSSEREALAΓ1λ=1−PrDSSEIDEALA,SΓ1λ=1≤negl1λ.


### 4.3. Forward and Backward Security

In 2016, Bost [19] defined the traditional forward privacy that the server cannot link the newly updated files with previously searched keywords. And in Li et al.’s work [23], they further defined the forward update privacy, strong forward search privacy, and weak forward search privacy. The forward update privacy requires that the information leaked in update operation should not be more than the identifier and the number of keywords of newly updated files. And the strong forward search privacy implies fully oblivious search operation, which is a too strong notion to achieve unless using the expensive protocols such as ORAM or PIR. The weak forward search privacy means the leaked information is the list of files containing the keyword w at the time t. Our scheme can achieve forward update privacy and weak forward search privacy, but for the consistent with most studies, we adopt the traditional forward privacy which is defined as follows.Definition 3.
Aℒ-adaptively secure DSSE scheme Γ is forward secure if the update leakage function ℒUpdt can be written as(4)ℒUpdtop,in=ℒ′op,indi,μi,where indi,μi is the set of modified documents paired with number μi of modified keywords for the updated document indi. Specially, the leakage function ℒUpdtop,w,bs=ℒ′bs in this paper.
In 2014, the term of backward privacy was first proposed by Stefanov et al. [18], and it was clearly defined by Bost et al. [35] in 2017. They defined three backward privacy from Type−I to Type−III, and Zuo et al. [26] formulated the most secure definition Type−I− in 2019. Our construction will adopt the latter, which is defined as follows.Definition 4.
Aℒ-adaptively secure DSSE scheme Γ is Type−I− backward private only if the search and update leakage function ℒSrchandℒUpdt can be written as(5)ℒUpdtop,w,ind=ℒ′op,ℒSrchw=ℒ″spw,rpw,Timew,where t is a timestamp, spw=t:t,w∈Q is a search pattern, rpw=bs represents all file identifiers that currently match w, and ℒ′ and ℒ′′ are stateless.


## 4.1. System Model and Security Model

As shown in Figure1, the system model consists of three entities: the data owner, data users, and the cloud server.Figure 1
Architecture of our scheme.


### 4.1.1. Data Owner

The data owner extracts the keywords from files and constructs the plain index. Then, he encrypts all files and the index with different private keys and uploads the encrypted EDB to the cloud server. Besides that, he is also responsible for managing users and updating files. More specifically, he distributes keys, updates tokens to users, and sends the updated encrypted files and index to the cloud server. And the data owner is assumed to be always trusted.


### 4.1.2. Cloud Server

The main job of the cloud server is to store the encrypted files and index from data owner and perform searches for data users. When receiving the updated information from the data owner, it updates the encrypted database. Upon receiving the search requests from data users, it performs search operation over the index and returns the search results to data users. The cloud server is regarded as an honest but curious entity. That is to say, it performs algorithms honestly but will try its best to get more valuable information. Besides, the cloud server may return invalid or nonupdated search results to the data user because of computation mistakes.


### 4.1.3. Data Users

Data users are authorized and shared with some keys needed in the scheme by the data owner. When they want to search files containing the interested keyword, they send the search token to cloud server and receive the search results. Furthermore, they can verify the validity of the results with the help of the data owner. The data users are assumed to be always trusted.


## 4.1.1. Data Owner

The data owner extracts the keywords from files and constructs the plain index. Then, he encrypts all files and the index with different private keys and uploads the encrypted EDB to the cloud server. Besides that, he is also responsible for managing users and updating files. More specifically, he distributes keys, updates tokens to users, and sends the updated encrypted files and index to the cloud server. And the data owner is assumed to be always trusted.


## 4.1.2. Cloud Server

The main job of the cloud server is to store the encrypted files and index from data owner and perform searches for data users. When receiving the updated information from the data owner, it updates the encrypted database. Upon receiving the search requests from data users, it performs search operation over the index and returns the search results to data users. The cloud server is regarded as an honest but curious entity. That is to say, it performs algorithms honestly but will try its best to get more valuable information. Besides, the cloud server may return invalid or nonupdated search results to the data user because of computation mistakes.


## 4.1.3. Data Users

Data users are authorized and shared with some keys needed in the scheme by the data owner. When they want to search files containing the interested keyword, they send the search token to cloud server and receive the search results. Furthermore, they can verify the validity of the results with the help of the data owner. The data users are assumed to be always trusted.


## 4.2. Security Model

We use two gamesDSSEREALAΓ1λ and DSSEIDEALA,SΓ1λ to show the security definition of DSSE. The DSSEREALAΓ1λ is the same as the DSSE. And the DSSEIDEALA,SΓ1λ is conducted by simulator S with the leakage of DSSE. The leakage of DSSE is parameterized by a function ℒ=ℒStp,ℒSrch,ℒUpdt, which describes the information leaked to the adversary A. The adversary A will interact with DSSEREALAΓ1λ or DSSEIDEALA,SΓ1λ and guess. If the adversary A can correctly guess the game he interacts only with a negligible advantage, then we can say the DSSE is secure because of the leaked information limited to the leakage function ℒ.DSSEREALAΓ1λ: the adversary A chooses a database DB and inputs it, then this game performs the Setup1λ,DB and outputs EDB. During the search phase, the adversary A runs search query q or update query op,in, where op is the operation and the in is the identifier of the file. The game outputs the search results by performing Searchq or Updateop,in. Eventually, A outputs a bit.DSSEIDEALA,SΓ1λ: the adversary A chooses a database DB and inputs it; then, the simulator S performs the ℒStp1λ,DB and outputs EDB. During the search phase, the adversary A runs search query q or update query op,in. The simulator S outputs the search results by performing the leakage function ℒSrchq or ℒUpdtop,in. Eventually, A outputs a bit.Definition 2.
A DSSE schemeΓis ℒ-adaptively secure only if for every PPT adversaryA, and there exists an efficient simulator S and a negligible function negl such that(3)PDSSEREALAΓ1λ=1−PrDSSEIDEALA,SΓ1λ=1≤negl1λ.


## 4.3. Forward and Backward Security

In 2016, Bost [19] defined the traditional forward privacy that the server cannot link the newly updated files with previously searched keywords. And in Li et al.’s work [23], they further defined the forward update privacy, strong forward search privacy, and weak forward search privacy. The forward update privacy requires that the information leaked in update operation should not be more than the identifier and the number of keywords of newly updated files. And the strong forward search privacy implies fully oblivious search operation, which is a too strong notion to achieve unless using the expensive protocols such as ORAM or PIR. The weak forward search privacy means the leaked information is the list of files containing the keyword w at the time t. Our scheme can achieve forward update privacy and weak forward search privacy, but for the consistent with most studies, we adopt the traditional forward privacy which is defined as follows.Definition 3.
Aℒ-adaptively secure DSSE scheme Γ is forward secure if the update leakage function ℒUpdt can be written as(4)ℒUpdtop,in=ℒ′op,indi,μi,where indi,μi is the set of modified documents paired with number μi of modified keywords for the updated document indi. Specially, the leakage function ℒUpdtop,w,bs=ℒ′bs in this paper.
In 2014, the term of backward privacy was first proposed by Stefanov et al. [18], and it was clearly defined by Bost et al. [35] in 2017. They defined three backward privacy from Type−I to Type−III, and Zuo et al. [26] formulated the most secure definition Type−I− in 2019. Our construction will adopt the latter, which is defined as follows.Definition 4.
Aℒ-adaptively secure DSSE scheme Γ is Type−I− backward private only if the search and update leakage function ℒSrchandℒUpdt can be written as(5)ℒUpdtop,w,ind=ℒ′op,ℒSrchw=ℒ″spw,rpw,Timew,where t is a timestamp, spw=t:t,w∈Q is a search pattern, rpw=bs represents all file identifiers that currently match w, and ℒ′ and ℒ′′ are stateless.


## 5. The Proposed Scheme

### 5.1. Overview

We mainly consider how to achieve forward and backward security when the cloud server is semihonest and the users are honest (the collusion between the cloud server and the user is not considered here). In order to achieve such a security goal, we use a pseudorandom function to shuffle the order of files so that the cloud server cannot identify the specific relationship between the index and the files from the search results and cannot get any private information.First, it is necessary to ensure that the search token of the keywords will be changed after the update; otherwise, the cloud server will learn whether the newly updated documents match a previously searched keyword or not. Here, in order to reduce the computational complexity of the index update and facilitate the user to update the search token, we adopt the HMAC technology. The plain index is regarded as the messagem and HMAC.Authm is regarded as the symmetric key of the encrypted m. In this case, the data owner only needs to send HMAC.AuthΔm to the user and the user invokes the HMAC.Eval algorithm to get the latest key, which can be used to generate a search token.Second, in order to not let the cloud server obtain the specific relationship between the index and the files, we assign a key to each column. When an update occurs, we use PRF to reorder the columns corresponding to the files and re-encrypt those files with the new key. It can be seen that our scheme is more suitable for scenarios where the ratio of file updated is relatively large.Third, there will still be cases where the file has not been updated and the relationship with the column of the index has not changed. The adversary cannot distinguish them because the index has been updated with the CPA-secure symmetric encryption scheme.


#### 5.1.1. The Bitmap Index

In this article, we use the bitmap index which is an inverted index withO1 search time. Specifically, we first extract keywords from the files. The bitmap index is a matrix of 0 and 1. The columns of the matrix correspond to different files. The rows of the matrix correspond to the keywords. If the number of the ith row and the jth column of the matrix is 1, it means that the keyword is included in the file, otherwise vice versa. The advantage of the bitmap is that it can easily implement the update of the index.Take a simple example for simplicity, and there are 5 files at timet. The index of the keyword w corresponding to the ith row is represented by a binary string 01001, which indicates that the files corresponding to the 2nd and 5th column contain w. At time t+1, the index of w is updated and become 01100, which means that the files corresponding to columns 2 and 3 now contain w, and the file corresponding to column 5 does not contain w any more. In order to update the index and search token, the data owner only needs to change the index from 01100 to 01001, which is an easy operation.


#### 5.1.2. The Homomorphic Message Authenticator

When data updates, the data owner needs to update the search token and send it to data users otherwise they cannot search on cloud any more. In order to explain clearly and simplicity, we still use the above example. The data owner updates the search token by calculating01100−01001and sends the HMAC.Auth01100−01001 to data users. Then, users execute HMAC.Eval and get the new search token. Since only the data users have the evaluation key, the interaction does not need the secret channel. Furthermore, the communication overhead is only a HMAC tag which efficiently reduces the transmission complexity and the whole process is simple.


#### 5.1.3. The Pseudorandom Functions

The Pseudorandom Functions is mainly used to generate the bitmap index. For example, there are 5 filesf1,f2,f3,f4,f5 and 3 keywords w1,w2,w3. And in time t, the files are mapped to 3,4,5,1,2 and the keywords to 3,1,2 by pseudorandom functions. The former means the first column of index indicates f3, the second one is f4, and so on. The latter shows the first row of index indicates w3, the second one is w1, and the last is w2.


### 5.2. Concrete Construction

Now, we are ready to give our dynamic searchable symmetric encryption scheme for multiuser with forward and backward security. See Algorithm1 for more information. Our scheme is based on the framework of DSSE=Setup,Update,Search and calls HMAC=HMAC.Setup,HMAC.Auth,HMAC.Ver,HMAC.Eval and keyed PRF. The scheme is defined by Algorithm 1.Algorithm 1: FBM-DSSE.
Setup:1λ⟶PK,SK(1)
input a security parameterλ(2)
generateP1,P2,R,H,H1,WK,WEK,FK,Q(3)
setPK=P1,P2,H,H1(4)
setSK=WK,WEK,FK,R,QUpdate:SK,EDBt,ΔF,ΔW⟶EDBt+1,Δσwtdata owner:(1)
ift=0 then(2)
extract keywordsW=wn from the files Ft(3)
attach keys with column identifiersc0≤c≤l(4)
for each column identifierc(5)
kc⟵HFK,c(6)
(match files to column identifiers and encrypt files)(7)
for each filef∈Ft(8)
c⟵Rf(9)
Cc⟵Enckcf(10)
ifc that does not match files(11)
rc⟵R0,1∗(12)
Cc⟵Enckcrc(13)
CFt⟵CFt∪Cc(14)
(generate bitmap index)(15)
for each keywordw∈Wt(16)
kw⟵P1WK,H1w(17)
ekw⟵P2WEK,H1w(18)
αwt=aw1,aw2,…,awl:(19)
awc=1⟺w∈fandRf=c(20)
σwt⟵HMAC.Authkw,τ,αwt(21)
βwt⟵Encσwtαwt(22)
i⟵Qtσwt(23)
AtT=α1t,α2t,…,αit,…,αWtT(24)
BtT=β1t,β2t,…,βit,…,βWtT(25)
sendEDBt=t,Bt,CFt,Qt to cloud server(26)
else if(27)
forming theΔF(28)
for each filef∈ΔF(29)
ifopf=add or modify(30)
f⟵the newf(31)
ifopf=del(32)
r⟵R0,1∗(33)
f⟵r(34)
(reorder)(35)
Rt+1⟵R,t+1(36)
Ft+1⟵F′∪ΔF(37)
for each filef∈Ft+1(38)
ct+1⟵Rt+1f(39)
(generate the new index)(40)
for eachw∈ΔW(41)
if theopw=add(42)
Wt+1⟵w∪W(43)
kw⟵P1WEK,H1w(44)
ekw⟵P2WEK,H1w(45)
if theopw=del(46)
Wt+1⟵W−w(47)
Qt+1⟵Q,t+1(48)
for eachw∈Wt+1(49)
αwt+1=aw1,aw2,…,awl(50)
σwt+1⟵HMAC.Authkw,τ,αwt+1(51)
βwt+1⟵Encσwt+1αwt+1(52)
it+1⟵Qt+1σwt+1(53)
Δαwt⟵αwt+1−αwt(54)
Δσwt⟵HMAC.Authkw,τ,Δαwt(55)
AtT=α1t,α2t,…,αit,…,αWt+1tT(56)
BtT=β1t,β2t,…,βit,…,βWt+1tT(57)
EDBt+1⟵t+1,Bt+1,CFt+1,Qt+1(58)
sendEDBt+1 to cloud server(59)
sendΔλwt=w,Δσwt to usersSearch:t,UL,w,EDBt⟶Cwtuser(1)
if there is no updation, then(2)
σwt⟵t,w,λwt(3)
Truw⟵PK.Encσwt(4)
else(5)
ekw⟵P2WEK,H1w(6)
σwt+1⟵HMAC.Evalekw,σwt,Δσwt(7)
Truw⟵PK.Encσwt+1(8)
sendsTruw to cloud servercloud server:(9)
ifu cannot be found in UL, then(10)
output error(11)
else(12)
σwt⟵PK.DecTruw(13)
i⟵Qtσwt(14)
αit⟵Decσwtβit(15)
ifaic=10≤c≤l(16)
Cwt⟵Cwt∪c,Cct(17)
returnsCwt and βit to userSetup:1λ⟶PK,SKThe algorithm is run by the data owner. For a security parameter1λ, the algorithm outputs the PK and SKneeded in the scheme.Update:SK,EDBt,ΔF,ΔW⟶EDBt+1,ΔσwtThe algorithm is run by the data owner too. At the beginning, the initial index and EDB are empty, so whent=0, it means that it is the first time for the data owner to add the file. When t≠0, it means the normal update operations. It should be noted that, in order to be consistent with the DSSE structure, we have omitted the algorithm of adding users in Algorithm 1 FBM-DSSE, and the algorithm is defined as Algorithm 2: Adduser.Algorithm 2: Adduser.
Adduser:u,SK⟶UL and USK(1)
UL⟵UL∪u(2)
USK⟵WEK,P2,H1,FK,λwt=w,σwt(3)
sendsUL=u to cloud serverSearch: t,UL,w,EDBt⟶CwtThis polynomial time algorithm is executed by the cloud server and the users. When data users want to searchw, he runs the line 1 to 8, generates the search token Truw, and sends it to cloud server. Then, the cloud server verifies the legitimacy of the user and performs a search. Finally, the cloud server outputs the search results.Actually, we have omitted the decryption and verification algorithms in Algorithm1 FBM-DSSE for the same reason. And the algorithms are defined as Algorithm 3: Decrypt and Algorithm 4: Verify.Algorithm 3: Decrypt.
Decrypt:Cwt,H,FK⟶Fw(1)
kc⟵HFK,c(2)
fct⟵DeckcCctAlgorithm 4: Verify.
Verify:w,βit,αit′,σwt⟶reject or accept(1)
transformβit to αit′ and send w,βit,αit′,σwt to data owner(2)
if0⟵HMAC.Verkw,αit′,P,σwt+1(3)
returns “reject”(4)
if1⟵HMAC.Verki,σiτ,αit′,P,σwt+1(5)
returns “accept”


### 5.3. Security Analysis

In this section, we first present the correctness of the proposed scheme and then give the security analysis.


#### 5.3.1. Correctness

if the user wants to search for files containing the keywordw at time t, he executes lines 1–8 of the search algorithm and then sends the search token of w to the cloud server. The ciphertext index saved in cloud is generated by the same pseudorandom function, which ensures the correctness of the searched keywords. Secondly, according to the bitmap index generation process and the cloud server being semihonest, the cloud sever will search 1 in the index and return corresponding files, so the returned file does contain the keyword w.


#### 5.3.2. Security analysis

Then, we will show the security analysis of the proposed scheme.Theorem 1 (adaptive security of FBM-DSSE).
LetP1,P2,H be secure PRF, Π1=Setup,Enc,Dec be a CPA-secure symmetric encryption, and Π2=HMAC.Setup,HMAC.Auth,HMAC.Ver,HMAC.Eval be a secure homomorphic message authenticator scheme. We define that(6)ℒFBM−DSSE=ℒFBM−DSSESearch,ℒFBM−DSSEUpdate,where ℒFBM−DSSESearchw=Timew,rpw,spw and ℒFBM−DSSEUpdate=bs. Then, FBM-DSSE is ℒFBM−DSSE-adaptively secure.Proof.
As mentioned above, the server is the semihonest adversaryA who correctly follows the protocol but attempts to use the messages received to learn information that should remain private. The challenger C is responsible for generating EDB and the search tokens of w. The simulator S simulates the view between A and C according to the leakage functions ℒFBM−DSSE.GameG0: G0 is the same as the real world game DSSEREALAFBM−DSSEλ, and there is(7)PrDSSEREALAFBM−DSSEλ=1=PrG0=1.GameG1: in G1, when querying H to generate the key for a column c, the challenger C chooses a new random key if the column c is never queried before and stores it in a table Key. Otherwise, return the key corresponding to w in the table Key. The adversary A cannot be able to distinguish between G0 and G1, otherwise we can build an adversary ℬ1 to distinguish between H and a truly random function. More formally,(8)PrG0=1−PrG1=1≤AdvF,ℬ1PRFλ.GameG2: in G2, we model the R as a table just like H in G1; then, we can build an adversary ℬ2 to distinguish between R and a truly random function, and there is(9)PrG1=1−PrG2=1≤AdvF,ℬ2PRFλ.Similarly, we build theG3 forP1 and G4 for P2.GameG5: in G5, as shown in Algorithm 1, in the update stage, the challenger C randomly picks a string for every keyword w as the updated index and gets the new EDB. Now, we will show that the adversary A gets more things than the new EDB is negligible.(1)
In the update stage,Q changed the order of the keywords in the new index. The two search tokens were σwt and σwt+1. The adversary could not get specific information about the keywords based on them. Even if the index corresponding to the keyword has not changed, HMAC.Auth will generate a corresponding label for a string of 0. Otherwise, it would conflict with the authentication of HMAC.(2)
The probability of using the search token corresponding to the keywordw to decrypt the indexes of other keywords w is negligible. Even if the indexes are the same, because the difference among keywords decides that in corresponding keys, it is impossible to achieve Decσw′tEncσwtαw′t, where w′≠w, otherwise it will contradict the security of symmetric encryption.(3)
Similarly, even if the file has not changed and the corresponding encryption key has not changed, it is impossible for an adversaryA to obtain relevant information about the file based on the ciphertext of the index because symmetric encryption is CPA-secure.(4)
Obviously, for an adversaryA who does not have the ek, even if he obtains Δσwt, he will not be able to obtain a new key. Otherwise, there will be an adversary that can break the security of HMAC.Simulator. We can replace the searched keyword w with spw in G5 to simulate the simulator S. And now we are ready to show that G5 and Simulator S are indistinguishable. For update, it is obvious since we choose new index for each update in G5. For search, S chooses a new search token according to the ℒFBM−DSSESearchw which can be modeled by tables and does the encryption. So,(10)PrG5=1=PrDSSEIDEALA,SFBM−DSSEλ=1.
Finally,(11)PrDSSEREALAFBM−DSSEλ=1−PrDSSEIDEALA,SFBM−DSSEλ=1≤ε,where ε is negligible, which completes the proof.Corollary 1 (adaptive forward privacy of FBM-DSSE).
FBM-DSSE is forward private.Proof.
From Theorem1, we can infer that FBM-DSSE achieves forward privacy because the leakage function ℒFBM−DSSEUpdatew of FBM-DSSE does not leak more information than that defined in Definition 3.Corollary 2 (adaptiveType−I− backward privacy of FBM-DSSE).
FBM-DSSE isType−I− backward private.Proof.
From Theorem1, we can get the conclusion that FBM-DSSE does achieve Type–I backward privacy since the leakage functions of FB-DSSE only leaks the same information as defined in Definition 4.


## 5.1. Overview

We mainly consider how to achieve forward and backward security when the cloud server is semihonest and the users are honest (the collusion between the cloud server and the user is not considered here). In order to achieve such a security goal, we use a pseudorandom function to shuffle the order of files so that the cloud server cannot identify the specific relationship between the index and the files from the search results and cannot get any private information.First, it is necessary to ensure that the search token of the keywords will be changed after the update; otherwise, the cloud server will learn whether the newly updated documents match a previously searched keyword or not. Here, in order to reduce the computational complexity of the index update and facilitate the user to update the search token, we adopt the HMAC technology. The plain index is regarded as the messagem and HMAC.Authm is regarded as the symmetric key of the encrypted m. In this case, the data owner only needs to send HMAC.AuthΔm to the user and the user invokes the HMAC.Eval algorithm to get the latest key, which can be used to generate a search token.Second, in order to not let the cloud server obtain the specific relationship between the index and the files, we assign a key to each column. When an update occurs, we use PRF to reorder the columns corresponding to the files and re-encrypt those files with the new key. It can be seen that our scheme is more suitable for scenarios where the ratio of file updated is relatively large.Third, there will still be cases where the file has not been updated and the relationship with the column of the index has not changed. The adversary cannot distinguish them because the index has been updated with the CPA-secure symmetric encryption scheme.


### 5.1.1. The Bitmap Index

In this article, we use the bitmap index which is an inverted index withO1 search time. Specifically, we first extract keywords from the files. The bitmap index is a matrix of 0 and 1. The columns of the matrix correspond to different files. The rows of the matrix correspond to the keywords. If the number of the ith row and the jth column of the matrix is 1, it means that the keyword is included in the file, otherwise vice versa. The advantage of the bitmap is that it can easily implement the update of the index.Take a simple example for simplicity, and there are 5 files at timet. The index of the keyword w corresponding to the ith row is represented by a binary string 01001, which indicates that the files corresponding to the 2nd and 5th column contain w. At time t+1, the index of w is updated and become 01100, which means that the files corresponding to columns 2 and 3 now contain w, and the file corresponding to column 5 does not contain w any more. In order to update the index and search token, the data owner only needs to change the index from 01100 to 01001, which is an easy operation.


### 5.1.2. The Homomorphic Message Authenticator

When data updates, the data owner needs to update the search token and send it to data users otherwise they cannot search on cloud any more. In order to explain clearly and simplicity, we still use the above example. The data owner updates the search token by calculating01100−01001and sends the HMAC.Auth01100−01001 to data users. Then, users execute HMAC.Eval and get the new search token. Since only the data users have the evaluation key, the interaction does not need the secret channel. Furthermore, the communication overhead is only a HMAC tag which efficiently reduces the transmission complexity and the whole process is simple.


### 5.1.3. The Pseudorandom Functions

The Pseudorandom Functions is mainly used to generate the bitmap index. For example, there are 5 filesf1,f2,f3,f4,f5 and 3 keywords w1,w2,w3. And in time t, the files are mapped to 3,4,5,1,2 and the keywords to 3,1,2 by pseudorandom functions. The former means the first column of index indicates f3, the second one is f4, and so on. The latter shows the first row of index indicates w3, the second one is w1, and the last is w2.


## 5.1.1. The Bitmap Index

In this article, we use the bitmap index which is an inverted index withO1 search time. Specifically, we first extract keywords from the files. The bitmap index is a matrix of 0 and 1. The columns of the matrix correspond to different files. The rows of the matrix correspond to the keywords. If the number of the ith row and the jth column of the matrix is 1, it means that the keyword is included in the file, otherwise vice versa. The advantage of the bitmap is that it can easily implement the update of the index.Take a simple example for simplicity, and there are 5 files at timet. The index of the keyword w corresponding to the ith row is represented by a binary string 01001, which indicates that the files corresponding to the 2nd and 5th column contain w. At time t+1, the index of w is updated and become 01100, which means that the files corresponding to columns 2 and 3 now contain w, and the file corresponding to column 5 does not contain w any more. In order to update the index and search token, the data owner only needs to change the index from 01100 to 01001, which is an easy operation.


## 5.1.2. The Homomorphic Message Authenticator

When data updates, the data owner needs to update the search token and send it to data users otherwise they cannot search on cloud any more. In order to explain clearly and simplicity, we still use the above example. The data owner updates the search token by calculating01100−01001and sends the HMAC.Auth01100−01001 to data users. Then, users execute HMAC.Eval and get the new search token. Since only the data users have the evaluation key, the interaction does not need the secret channel. Furthermore, the communication overhead is only a HMAC tag which efficiently reduces the transmission complexity and the whole process is simple.


## 5.1.3. The Pseudorandom Functions

The Pseudorandom Functions is mainly used to generate the bitmap index. For example, there are 5 filesf1,f2,f3,f4,f5 and 3 keywords w1,w2,w3. And in time t, the files are mapped to 3,4,5,1,2 and the keywords to 3,1,2 by pseudorandom functions. The former means the first column of index indicates f3, the second one is f4, and so on. The latter shows the first row of index indicates w3, the second one is w1, and the last is w2.


## 5.2. Concrete Construction

Now, we are ready to give our dynamic searchable symmetric encryption scheme for multiuser with forward and backward security. See Algorithm1 for more information. Our scheme is based on the framework of DSSE=Setup,Update,Search and calls HMAC=HMAC.Setup,HMAC.Auth,HMAC.Ver,HMAC.Eval and keyed PRF. The scheme is defined by Algorithm 1.Algorithm 1: FBM-DSSE.
Setup:1λ⟶PK,SK(1)
input a security parameterλ(2)
generateP1,P2,R,H,H1,WK,WEK,FK,Q(3)
setPK=P1,P2,H,H1(4)
setSK=WK,WEK,FK,R,QUpdate:SK,EDBt,ΔF,ΔW⟶EDBt+1,Δσwtdata owner:(1)
ift=0 then(2)
extract keywordsW=wn from the files Ft(3)
attach keys with column identifiersc0≤c≤l(4)
for each column identifierc(5)
kc⟵HFK,c(6)
(match files to column identifiers and encrypt files)(7)
for each filef∈Ft(8)
c⟵Rf(9)
Cc⟵Enckcf(10)
ifc that does not match files(11)
rc⟵R0,1∗(12)
Cc⟵Enckcrc(13)
CFt⟵CFt∪Cc(14)
(generate bitmap index)(15)
for each keywordw∈Wt(16)
kw⟵P1WK,H1w(17)
ekw⟵P2WEK,H1w(18)
αwt=aw1,aw2,…,awl:(19)
awc=1⟺w∈fandRf=c(20)
σwt⟵HMAC.Authkw,τ,αwt(21)
βwt⟵Encσwtαwt(22)
i⟵Qtσwt(23)
AtT=α1t,α2t,…,αit,…,αWtT(24)
BtT=β1t,β2t,…,βit,…,βWtT(25)
sendEDBt=t,Bt,CFt,Qt to cloud server(26)
else if(27)
forming theΔF(28)
for each filef∈ΔF(29)
ifopf=add or modify(30)
f⟵the newf(31)
ifopf=del(32)
r⟵R0,1∗(33)
f⟵r(34)
(reorder)(35)
Rt+1⟵R,t+1(36)
Ft+1⟵F′∪ΔF(37)
for each filef∈Ft+1(38)
ct+1⟵Rt+1f(39)
(generate the new index)(40)
for eachw∈ΔW(41)
if theopw=add(42)
Wt+1⟵w∪W(43)
kw⟵P1WEK,H1w(44)
ekw⟵P2WEK,H1w(45)
if theopw=del(46)
Wt+1⟵W−w(47)
Qt+1⟵Q,t+1(48)
for eachw∈Wt+1(49)
αwt+1=aw1,aw2,…,awl(50)
σwt+1⟵HMAC.Authkw,τ,αwt+1(51)
βwt+1⟵Encσwt+1αwt+1(52)
it+1⟵Qt+1σwt+1(53)
Δαwt⟵αwt+1−αwt(54)
Δσwt⟵HMAC.Authkw,τ,Δαwt(55)
AtT=α1t,α2t,…,αit,…,αWt+1tT(56)
BtT=β1t,β2t,…,βit,…,βWt+1tT(57)
EDBt+1⟵t+1,Bt+1,CFt+1,Qt+1(58)
sendEDBt+1 to cloud server(59)
sendΔλwt=w,Δσwt to usersSearch:t,UL,w,EDBt⟶Cwtuser(1)
if there is no updation, then(2)
σwt⟵t,w,λwt(3)
Truw⟵PK.Encσwt(4)
else(5)
ekw⟵P2WEK,H1w(6)
σwt+1⟵HMAC.Evalekw,σwt,Δσwt(7)
Truw⟵PK.Encσwt+1(8)
sendsTruw to cloud servercloud server:(9)
ifu cannot be found in UL, then(10)
output error(11)
else(12)
σwt⟵PK.DecTruw(13)
i⟵Qtσwt(14)
αit⟵Decσwtβit(15)
ifaic=10≤c≤l(16)
Cwt⟵Cwt∪c,Cct(17)
returnsCwt and βit to userSetup:1λ⟶PK,SKThe algorithm is run by the data owner. For a security parameter1λ, the algorithm outputs the PK and SKneeded in the scheme.Update:SK,EDBt,ΔF,ΔW⟶EDBt+1,ΔσwtThe algorithm is run by the data owner too. At the beginning, the initial index and EDB are empty, so whent=0, it means that it is the first time for the data owner to add the file. When t≠0, it means the normal update operations. It should be noted that, in order to be consistent with the DSSE structure, we have omitted the algorithm of adding users in Algorithm 1 FBM-DSSE, and the algorithm is defined as Algorithm 2: Adduser.Algorithm 2: Adduser.
Adduser:u,SK⟶UL and USK(1)
UL⟵UL∪u(2)
USK⟵WEK,P2,H1,FK,λwt=w,σwt(3)
sendsUL=u to cloud serverSearch: t,UL,w,EDBt⟶CwtThis polynomial time algorithm is executed by the cloud server and the users. When data users want to searchw, he runs the line 1 to 8, generates the search token Truw, and sends it to cloud server. Then, the cloud server verifies the legitimacy of the user and performs a search. Finally, the cloud server outputs the search results.Actually, we have omitted the decryption and verification algorithms in Algorithm1 FBM-DSSE for the same reason. And the algorithms are defined as Algorithm 3: Decrypt and Algorithm 4: Verify.Algorithm 3: Decrypt.
Decrypt:Cwt,H,FK⟶Fw(1)
kc⟵HFK,c(2)
fct⟵DeckcCctAlgorithm 4: Verify.
Verify:w,βit,αit′,σwt⟶reject or accept(1)
transformβit to αit′ and send w,βit,αit′,σwt to data owner(2)
if0⟵HMAC.Verkw,αit′,P,σwt+1(3)
returns “reject”(4)
if1⟵HMAC.Verki,σiτ,αit′,P,σwt+1(5)
returns “accept”


## 5.3. Security Analysis

In this section, we first present the correctness of the proposed scheme and then give the security analysis.


### 5.3.1. Correctness

if the user wants to search for files containing the keywordw at time t, he executes lines 1–8 of the search algorithm and then sends the search token of w to the cloud server. The ciphertext index saved in cloud is generated by the same pseudorandom function, which ensures the correctness of the searched keywords. Secondly, according to the bitmap index generation process and the cloud server being semihonest, the cloud sever will search 1 in the index and return corresponding files, so the returned file does contain the keyword w.


### 5.3.2. Security analysis

Then, we will show the security analysis of the proposed scheme.Theorem 1 (adaptive security of FBM-DSSE).
LetP1,P2,H be secure PRF, Π1=Setup,Enc,Dec be a CPA-secure symmetric encryption, and Π2=HMAC.Setup,HMAC.Auth,HMAC.Ver,HMAC.Eval be a secure homomorphic message authenticator scheme. We define that(6)ℒFBM−DSSE=ℒFBM−DSSESearch,ℒFBM−DSSEUpdate,where ℒFBM−DSSESearchw=Timew,rpw,spw and ℒFBM−DSSEUpdate=bs. Then, FBM-DSSE is ℒFBM−DSSE-adaptively secure.Proof.
As mentioned above, the server is the semihonest adversaryA who correctly follows the protocol but attempts to use the messages received to learn information that should remain private. The challenger C is responsible for generating EDB and the search tokens of w. The simulator S simulates the view between A and C according to the leakage functions ℒFBM−DSSE.GameG0: G0 is the same as the real world game DSSEREALAFBM−DSSEλ, and there is(7)PrDSSEREALAFBM−DSSEλ=1=PrG0=1.GameG1: in G1, when querying H to generate the key for a column c, the challenger C chooses a new random key if the column c is never queried before and stores it in a table Key. Otherwise, return the key corresponding to w in the table Key. The adversary A cannot be able to distinguish between G0 and G1, otherwise we can build an adversary ℬ1 to distinguish between H and a truly random function. More formally,(8)PrG0=1−PrG1=1≤AdvF,ℬ1PRFλ.GameG2: in G2, we model the R as a table just like H in G1; then, we can build an adversary ℬ2 to distinguish between R and a truly random function, and there is(9)PrG1=1−PrG2=1≤AdvF,ℬ2PRFλ.Similarly, we build theG3 forP1 and G4 for P2.GameG5: in G5, as shown in Algorithm 1, in the update stage, the challenger C randomly picks a string for every keyword w as the updated index and gets the new EDB. Now, we will show that the adversary A gets more things than the new EDB is negligible.(1)
In the update stage,Q changed the order of the keywords in the new index. The two search tokens were σwt and σwt+1. The adversary could not get specific information about the keywords based on them. Even if the index corresponding to the keyword has not changed, HMAC.Auth will generate a corresponding label for a string of 0. Otherwise, it would conflict with the authentication of HMAC.(2)
The probability of using the search token corresponding to the keywordw to decrypt the indexes of other keywords w is negligible. Even if the indexes are the same, because the difference among keywords decides that in corresponding keys, it is impossible to achieve Decσw′tEncσwtαw′t, where w′≠w, otherwise it will contradict the security of symmetric encryption.(3)
Similarly, even if the file has not changed and the corresponding encryption key has not changed, it is impossible for an adversaryA to obtain relevant information about the file based on the ciphertext of the index because symmetric encryption is CPA-secure.(4)
Obviously, for an adversaryA who does not have the ek, even if he obtains Δσwt, he will not be able to obtain a new key. Otherwise, there will be an adversary that can break the security of HMAC.Simulator. We can replace the searched keyword w with spw in G5 to simulate the simulator S. And now we are ready to show that G5 and Simulator S are indistinguishable. For update, it is obvious since we choose new index for each update in G5. For search, S chooses a new search token according to the ℒFBM−DSSESearchw which can be modeled by tables and does the encryption. So,(10)PrG5=1=PrDSSEIDEALA,SFBM−DSSEλ=1.
Finally,(11)PrDSSEREALAFBM−DSSEλ=1−PrDSSEIDEALA,SFBM−DSSEλ=1≤ε,where ε is negligible, which completes the proof.Corollary 1 (adaptive forward privacy of FBM-DSSE).
FBM-DSSE is forward private.Proof.
From Theorem1, we can infer that FBM-DSSE achieves forward privacy because the leakage function ℒFBM−DSSEUpdatew of FBM-DSSE does not leak more information than that defined in Definition 3.Corollary 2 (adaptiveType−I− backward privacy of FBM-DSSE).
FBM-DSSE isType−I− backward private.Proof.
From Theorem1, we can get the conclusion that FBM-DSSE does achieve Type–I backward privacy since the leakage functions of FB-DSSE only leaks the same information as defined in Definition 4.


## 5.3.1. Correctness

if the user wants to search for files containing the keywordw at time t, he executes lines 1–8 of the search algorithm and then sends the search token of w to the cloud server. The ciphertext index saved in cloud is generated by the same pseudorandom function, which ensures the correctness of the searched keywords. Secondly, according to the bitmap index generation process and the cloud server being semihonest, the cloud sever will search 1 in the index and return corresponding files, so the returned file does contain the keyword w.


## 5.3.2. Security analysis

Then, we will show the security analysis of the proposed scheme.Theorem 1 (adaptive security of FBM-DSSE).
LetP1,P2,H be secure PRF, Π1=Setup,Enc,Dec be a CPA-secure symmetric encryption, and Π2=HMAC.Setup,HMAC.Auth,HMAC.Ver,HMAC.Eval be a secure homomorphic message authenticator scheme. We define that(6)ℒFBM−DSSE=ℒFBM−DSSESearch,ℒFBM−DSSEUpdate,where ℒFBM−DSSESearchw=Timew,rpw,spw and ℒFBM−DSSEUpdate=bs. Then, FBM-DSSE is ℒFBM−DSSE-adaptively secure.Proof.
As mentioned above, the server is the semihonest adversaryA who correctly follows the protocol but attempts to use the messages received to learn information that should remain private. The challenger C is responsible for generating EDB and the search tokens of w. The simulator S simulates the view between A and C according to the leakage functions ℒFBM−DSSE.GameG0: G0 is the same as the real world game DSSEREALAFBM−DSSEλ, and there is(7)PrDSSEREALAFBM−DSSEλ=1=PrG0=1.GameG1: in G1, when querying H to generate the key for a column c, the challenger C chooses a new random key if the column c is never queried before and stores it in a table Key. Otherwise, return the key corresponding to w in the table Key. The adversary A cannot be able to distinguish between G0 and G1, otherwise we can build an adversary ℬ1 to distinguish between H and a truly random function. More formally,(8)PrG0=1−PrG1=1≤AdvF,ℬ1PRFλ.GameG2: in G2, we model the R as a table just like H in G1; then, we can build an adversary ℬ2 to distinguish between R and a truly random function, and there is(9)PrG1=1−PrG2=1≤AdvF,ℬ2PRFλ.Similarly, we build theG3 forP1 and G4 for P2.GameG5: in G5, as shown in Algorithm 1, in the update stage, the challenger C randomly picks a string for every keyword w as the updated index and gets the new EDB. Now, we will show that the adversary A gets more things than the new EDB is negligible.(1)
In the update stage,Q changed the order of the keywords in the new index. The two search tokens were σwt and σwt+1. The adversary could not get specific information about the keywords based on them. Even if the index corresponding to the keyword has not changed, HMAC.Auth will generate a corresponding label for a string of 0. Otherwise, it would conflict with the authentication of HMAC.(2)
The probability of using the search token corresponding to the keywordw to decrypt the indexes of other keywords w is negligible. Even if the indexes are the same, because the difference among keywords decides that in corresponding keys, it is impossible to achieve Decσw′tEncσwtαw′t, where w′≠w, otherwise it will contradict the security of symmetric encryption.(3)
Similarly, even if the file has not changed and the corresponding encryption key has not changed, it is impossible for an adversaryA to obtain relevant information about the file based on the ciphertext of the index because symmetric encryption is CPA-secure.(4)
Obviously, for an adversaryA who does not have the ek, even if he obtains Δσwt, he will not be able to obtain a new key. Otherwise, there will be an adversary that can break the security of HMAC.Simulator. We can replace the searched keyword w with spw in G5 to simulate the simulator S. And now we are ready to show that G5 and Simulator S are indistinguishable. For update, it is obvious since we choose new index for each update in G5. For search, S chooses a new search token according to the ℒFBM−DSSESearchw which can be modeled by tables and does the encryption. So,(10)PrG5=1=PrDSSEIDEALA,SFBM−DSSEλ=1.
Finally,(11)PrDSSEREALAFBM−DSSEλ=1−PrDSSEIDEALA,SFBM−DSSEλ=1≤ε,where ε is negligible, which completes the proof.Corollary 1 (adaptive forward privacy of FBM-DSSE).
FBM-DSSE is forward private.Proof.
From Theorem1, we can infer that FBM-DSSE achieves forward privacy because the leakage function ℒFBM−DSSEUpdatew of FBM-DSSE does not leak more information than that defined in Definition 3.Corollary 2 (adaptiveType−I− backward privacy of FBM-DSSE).
FBM-DSSE isType−I− backward private.Proof.
From Theorem1, we can get the conclusion that FBM-DSSE does achieve Type–I backward privacy since the leakage functions of FB-DSSE only leaks the same information as defined in Definition 4.


## 6. Multifunctional Search

Due to using the bitmap index, our scheme is easily extended to support multifunctional search. Specifically, Hu et al. [29] proposed an efficient and secure multifunctional searchable symmetric encryption schemes which supports wildcard search, similarity search (including hamming distance and edit distance), fuzzy keyword search, and disjunctive keyword search simultaneously. Hu’s scheme builds a bloom filter for every keyword followed by a encryption index I′=Encks,Fw,w,rd, where ks is the symmetric private key and rd is the random value generated by a random function. If one replaces the encryption index in [29] with our bitmap index, the new scheme can achieve all the functional searches in [29].As for the conjunctive keyword search, the primary schemes first search for one keyword at a time and then collect the results together. Our scheme can achieve a more effective way. First, data users provide keywords’ search token to the server; then, the server decrypts the corresponding rows in the bitmap index, conducts the conjunctive operation, and finally returns the result set.


## 7. Performance Analysis

In this section, we first summarize the comparisons between our scheme and prior forward private schemes. See Table2, where F/B in security, respectively, shows the forward privacy/backward privacy, where B1 means Type−I backward privacy, B1− describes Type−I− backward privacy, and B3 indicates Type−III backward privacy. NA/A means the scheme is nonadaptive/adaptive indistinguishability security; D/S in dynamism column describes dynamic or static; S/M shows single/multi; R in the column of computable complexity denotes the round in search phase; Do represents the date owner; D denotes the number of documents in the document collection; N is the number of keyword/file-identifier pairs; aw/dw is the number of added/deleted entries for keyword w; W is the collection of distinct keywords; tma is the computational time of a modular addition; Dw is the number of files currently matching keyword w; m means the number of subkeywords; and uw is the number of the keywords whose Dw has changed.Table 2
Comparison with prior forward private SSE schemes.
SchemesSecurityDynamismMultiuserComputable ComplexityStorageCommunication complexityF/B/CKAD/SS/MCloudRUpdateDoUpdate do to CStefanov et al. [18]FDSOminaw+logN,nwlog3N1Olog2NONαOlogN∑oϕoς [19]FDSOaw+dw1O1OWlogDO1Wang et al. [20]FDMODw2O1orODwO1O1Khons et al. [23]F+B3DSODw2O1OmlogD+DlogWO1Zuo et al. [26]F+B1−DSOawtma1O1tmaOWlogDOWSSE-1 [31]NASSODw1-O1-SSE-2 [31]ASSODw1-O1-M-SSE [31]NASMODw1-O1-Bost [35]F+B1DSOawlogN+log3N3Olog2NO1Olog3NFBM-DSSEF+B1DMO11Ouw+DO1OWThen, we evaluate the performance of the proposed scheme. We implement our scheme using LINUX in Windows 10 with an Intel Core i7-8550U CPU 2.00 GHz processor and 16 GB memory. We simulate the update algorithm and search algorithm on this machine to evaluate the computation overhead time cost of our scheme. In our experiment, the size of each file is 50 kB, the number of the keywords is 5,000, and the symmetric encryption scheme and public key encryption scheme are AES and RSA, respectively. We simulate the number of files on 10,000 to 100,000 by an increase of 10,000 each time.In the update phase, the data owner needsl times (number of columns) symmetric encryption operations, W times index homomorphic message authentication, and W times symmetric encryption; Figure 2 shows the total time required to generate the index.Figure 2
Index generation time.In the search phase, the user only needs to perform the public key encryption operation once, and if there is an update, he needs to perform another homomorphic operation (when only one keyword is searched); Figures3 and 4 illustrate the time cost of search token generation for users and search time for the cloud server.Figure 3
Search token generation time.Figure 4
Search time.In the search phase, the server needs to perform a public key decryption operation and a symmetric decryption operation. Figure5 displays that the time cost of search for server which is mainly in the RSA.Figure 5
The proportion of RSA time search process.These figures illustrate that the effect of the increase in the number of files on the search phase is linear, which is reasonable but an exponential growth for index generation. The crux of our scheme is the update algorithm, so we concluded that the proposed scheme is more suitable for small databases and achieves the enhanced security guarantees at the reasonable price of efficiency.In order to simplify the update algorithm, we propose two more efficient methods for updating at the cost of losing some security. It is a tradeoff between efficiency and security.One is a new update algorithm named thecycleΔt. For files that will not be updated in the short term, the data owner calculates the ciphertext of time t to time t+Δt and Δt is a cycle. When the data owner is updated at timet, he arranges them in the corresponding column in chronological order. If the update time is t′∈t,t+Δt, the data owner only needs to upload the files that need to be changed and a certain amount of dummy data without downloading the files that does not change. Taking t=3 as an example, the specific description is as follows.Suppose there aref1,f2,f3,f4,f5 and the time periods are, respectively, t,t+1,t+2,t+3. Call R in advance from t to t+3 and they are mapped to 1,2,3,4,5,3,4,5,1,2,2,3,4,5,1,4,5,1,2,3. When the data owner updates data at time t, he encrypts the f1 with kc1,kc4,kc5,kc3 (where kci means the i column’s key), the f2 with kc2,kc5,kc1,kc4, the f3 with kc3,kc1,kc2,kc5, the f4 with kc4,kc2,kc3,kc1, and the f5 with kc5,kc3,kc4,kc2 and sends(12)c1:Ekc1,f1Ekc1,f3Ekc1,f2Ekc1,f4,c2:Ekc2,f2Ekc2,f4Ekc2,f3Ekc2,f5,c3:Ekc3,f3Ekc3,f5Ekc3,f4Ekc3,f1,c4:Ekc4,f4Ekc4,f1Ekc4,f5Ekc4,f2,c5:Ekc5,f5Ekc5,f2Ekc5,f1Ekc5,f3,to the server.When the user is searching at timet and the search result is f1,f3,f5, the server just returns Ekc1,f1,Ekc3,f3,Ekc5,f5. This new update algorithm cycleΔt can efficiently reduce the communication complexity of updates during the period.Another method is that the data owner can use a proxy server. The proxy server is semihonest in the sense that it honestly runs the protocols but is curious to obtain privacy information. Additionally, it cannot collude with the cloud server. The proxy server is mainly responsible for the update of the database. Specifically, the data owner calculates the updated ciphertext together with the proxy server and stores it on the proxy server. And then proxy server interacts with the cloud server according to the specified time period and updates the ciphertext. Moreover, it is also responsible for updating the trapdoor. And we are studying further how to construct a FBM-DSSE scheme under a proxy server or a malicious server in the future.


## 8. Conclusions

In this work, we propose a Dynamic Searchable Symmetric encryption scheme for multiuser with Forward and Backward Security (FBM-DSSE). The proposed scheme realizes the Forward and Backward Security in Dynamic Searchable Symmetric encryption for multiuser. More specifically, the proposed scheme adopts a keyed pseudorandom function to hide the correspondence between files and indexes, takes symmetric encryption to improve the efficiency of file encryption and update, and uses HMAC to improve the efficiency of updating search tokens as files are changed. Furthermore, our scheme also supports verifiability and can be extended to multifunctional search. Further research work aims to reduce the computational complexity and communication complexity of the data owner and server. It will also combine access control to achieve fine-grained user management and file search.



---

*Source: 8893016-2020-10-20.xml*