# Multiuser Searchable Encryption with Token Freshness Verification

Authors: Dhruti Sharma; Devesh C. Jinwala
Journal: Security and Communication Networks
 (2017)

---

## Abstract

A Multiuser Searchable Encryption (MUSE) can be defined with the notion of Functional Encryption (FE) where a user constructs a search token from a search key issued by an Enterprise Trusted Authority (ETA). In such scheme, a user possessing search key constructs search token at any time and consequently requests the server to search over encrypted data. Thus, an FE based MUSE scheme is not suitable for the applications where a log of search activities is maintained at the enterprise site to identify dishonest search query from any user. In addition, none of the existing searchable schemes provides security against token replay attack to avoid reuse of the same token. In this paper, therefore we propose an FE based scheme, Multiuser Searchable Encryption with Token Freshness Verification (MUSE-TFV). In MUSE-TFV, a user prepares one-time usable search token in cooperation with ETA and thus every search activity is logged at the enterprise site. Additionally, by verifying the freshness of a token, the server prevents reuse of the token. With formal security analysis, we prove the security of MUSE-TFV against chosen keyword attack and token replay attack. With theoretical and empirical analysis, we justify the effectiveness of MUSE-TFV in practical applications.


---

## Body

## 1. Introduction

With the cloud storage infrastructure, one can easily share data with multiple users at a low cost. However, maintaining security and privacy of such data located on the untrusted remote server is nontrivial [1–3]. Therefore, a common trend is to upload the encrypted data onto a third-party cloud server. However, extraction of partial information from the stored encrypted data is indeed difficult. The notion of Searchable Encryption (SE) is used to resolve the issue. In SE, a Data Owner prepares a ciphertext by associating a list of encrypted keywords (to be searched) with an encrypted payload message and uploads it onto the Storage Server. Subsequently, a Data User asks the server to search over encrypted data by issuing a search token (of keyword(s)). The server applies a token over available ciphertexts and extracts the data containing that keyword(s) (Figure 1). However, the server learns nothing else about the data while searching. Here, a payload message is encrypted using any standard encryption algorithm, whereas keywords are encrypted with the defined Searchable Encryption algorithm.Figure 1
System model of Searchable Encryption (SE). Steps:(1) Data Owner uploads a ciphertext C (i.e., encrypted payload message + list of encrypted keywords) onto the Storage Server; (2) Data User constructs a search token T using a secret key; (3) Data User sends T to the server; (4) Storage Server applies T on C; (5) Storage Server returns the result to the requesting user.There exist numerous Searchable Encryption schemes for a single user [4–8] as well as for multiple users [9–13]. Practically, any single-user Searchable Encryption scheme can be adapted to define a multiuser Searchable Encryption scheme at the cost of a ciphertext size linear to the number of users in the system. Formally, when a single-user searchable scheme is extended to support multiple users, its ciphertext size becomes O(U) for U users that subsequently raises to OD·U for D=d1,d2,…,dm data items in the system. This ultimately outputs an impractical system with O(|D|·U) computational overhead at the Data Owner site and OD·U storage overhead at the server site. As solution, several Searchable Encryption schemes in [9, 10, 14–20] with a built-in support of multiple users are devised in recent years. Amongst them, the scheme proposed by Hwang and Lee [9] is a simple extension of a single-user Searchable Encryption with the ciphertext size OD+W·U, where W is the number of keywords to be searched. However, this scheme works for the prefixed set of users. In contrast, the schemes in [10, 14–16] support the dynamic groups of users where joining/leaving a group by a member is entirely controlled by a Data Owner. In addition, the recent schemes in [17–20] provide Multiuser Searchable Encryption with the notion of Functional Encryption (FE) (Section 2.1) where an Enterprise Trusted Authority (ETA) is responsible for the System Setup and a master public key setup. The most notable characteristic of FE is that a system’s master public key is utilized to prepare the searchable ciphertexts and a single ciphertext can serve multiple search tokens (may be issued by different users). Therefore, such FE based searchable schemes can support multiple users in the system with the optimal storage-computational overhead (i.e., OD) for the ciphertexts. Additionally, in the schemes [17–20], a separate search key (related to the master public key) is issued (either by an ETA or by a Data Owner) to each user. Subsequently, a user constructs a search token with an available search key. The downside is that once a user has a search key, he can prepare a search token at any time. As a result, a dishonest user colluding with the untrusted cloud server can maliciously search the valid data and the system administrator (i.e., ETA) is completely unaware about such adversarial activity. Moreover, with the existing Searchable Encryption mechanisms, there is no provision for the token freshness checking at the server site. As a result, if an unauthorized user masquerading as an authorized user has a valid token, he can use the token to make search queries in the future. In practice, there exist applications wherein every search query from the users should be logged to the enterprise trusted site in order to identify any dishonest activity performed by any user (authorized or unauthorized). In addition, there should be a provision against token replay attack to avoid misuse of a valid token. Let us take one of such applications as an example.(i)
Consider an Online Banking System, where the customers’ transaction records are stored at the Bank’s cloud Storage Server. Practically, these records are utilized by several official users (i.e., managers, officers, clerks, etc.) of the Bank. Let us assume that the Bank’s centralized processing server (trusted authority) uses any of the existing FE based searchable schemes and accordingly issues a separate search key to each authorized user of the Bank.
In such a setup, let us take a case of a manager who is responsible for generating a daily report for the ATM transactions with a specific ATM-ID. To perform this activity, every day the manager constructs a search token (using his search key) for a query, that is, “list all ATM transactions for ATM-ID today.” He issues this token to the server and collects the result. In this scenario, what happens if a peon steals the search token and masquerades as an officer to send this token to the server? In any FE based searchable scheme, the server only checks the authorization of a user. In this case, since a peon impersonates an authorized officer of the Bank, he passes the authorization test conducted by the server and gets the search result. In fact, performing such token replay attack (by reusing the token) and leaking the information about ATM transactions to the intruder (outsider) on a daily basis, the peon may provoke the criminal activities near that ATM.From the above scenario, we say that, in the Banking system, since every search result involves critical financial information, the search activity by each user should be logged at the Bank’s centralized processing server. In addition, to avoid misuse of any valid token, it is desirable to prevent token replay attack in such system.With the existing FE based searchable schemes [17–20], a user possessing a search key can ask the server to execute a search operation at any time and therefore the search activity of a user cannot be tracked. The problem can be resolved by an interactive scheme where a search token is constructed by the centralized trusted authority on request from an authorized user. However, such solution raises the demand of secure token transmission along the entire path from the trusted authority up to the server through a user. Moreover, a token replay attack should be prevented by verifying the freshness of each search token at the server site. In addition, it is desirable to have a search operation with the support of conjunctive queries in such system.


### 1.1. Related Work

The notion of Searchable Encryption is introduced by Song et al. in [4] where the authors consider search over encrypted keywords within a file. However, this first practical scheme leaks the search keywords to the server and suffers from the communication overhead linear to the file size. In fact, the scheme in [4] is not secure against statistical analysis across multiple queries. To resolve the problems, Goh et al. [5] and Chang and Mitzenmacher [24] in their separate work construct the secure searchable schemes by proposing an encrypted index for a document. Though the schemes in [4, 5, 24] perform efficient search operations, they introduce storage overhead linear to the size of an index for each document. Curtmola et al. [25] propose the first symmetric searchable encryption scheme with a formal security model. The first public key Searchable Encryption scheme is given by Boneh et al. [6] wherein a user with his private key can search over data encrypted with the corresponding public key. However, none of the schemes [4–6, 24] support conjunctive keyword search.Conjunctive Keyword Searchable Schemes. To narrow down the scope of searching and get optimal results, several searchable schemes exist with conjunctive keyword search operation. In the symmetric key settings, Golle et al. [26] have constructed two schemes for a conjunctive keyword search. However, in the first construction of [26], the size of a capability (search token) is linear to the number of documents available on the server and so the scheme is impractical. On the other hand, the second construction of [26] is practical with a constant size capability. The other constructions based on the secret sharing and bilinear map are given by Ballard et al. [27] but they are still inefficient in terms of a size of a token linear to the number of documents being searched. In public key settings, a first conjunctive keyword searchable scheme is defined by Park et al. [8]. Subsequently, the schemes with the improved communication and storage efficiency are proposed in [9, 28]. Boneh and Waters have given a generalized scheme [29] for conjunction as well as for subset queries. Later on, a scheme with a refined form of a token (that is independent of specifying the keyword field position) is devised by Wang et al. [13]. Subsequently, B. Zhang and F. Zhang [21] have improved the security flaws of [13] and defined a conjunctive-subset keyword search. Other efficient constructions with the support of conjunctive keyword search operation are given in [22, 23, 30].Multiuser Searchable Schemes. In public key settings, Hwang and Lee [9] have first introduced a storage efficient multiuser scheme. Subsequently, several other schemes [10, 11, 13, 14, 16] have proposed managing a group of users. However, a scheme in [11] supports the static groups of users, whereas the schemes discussed in [10, 13, 14] work for the dynamic groups of users. Apart from this, the scheme in [14] provides a single keyword search whereas the schemes in [10, 13] handle the conjunctive search queries. Recently, a multiuser multikeyword search scheme is proposed by Huang et al. [16] but its inverted index based construction cannot support an efficient conjunctive search. In addition, a scheme in [16] leaks user access control information to the server. Few other multiuser schemes [17–20] are based on the notion of FE wherein an ETA is responsible for the System Setup and a master public key setup. In these schemes, a ciphertext is prepared by a Data Owner using a master public key. A search token is constructed by a user with his own search key issued either by the ETA as in [18–20] or by the Data Owner as in [17]. A scheme in [17] offers a constant size ciphertext and a constant size token. However, the scheme [17] is computationally inefficient since, to encrypt an index for a document, the encryption algorithm involves a computational complexity linear to the number of authorized users for that document. In a scheme of [18], the Storage Server has a list of authorized users (U_List), and thus each enrollment/revocation of a user is known to the server. This indeed leaks information about users (i.e., a number of users in the system, the users’ activity) to the Storage Server. The other two schemes [19, 20] use CPABE (Ciphertext Policy Attribute Based Encryption) to manage access control of users. However, amongst all these schemes, only the schemes in [9, 10, 13, 16] support multikeyword (specifically conjunctive) search and multiple users at the same time. There is no FE based scheme proposing a conjunctive keyword based search.Secure Channel-Free Searchable Schemes. There exist searchable schemes in [7, 31, 32] with secure channel-free architecture for a token transmission. However, these schemes support a single keyword search. The most recent conjunctive search schemes [30, 33] provide a secure channel-free token transmission.To the best of our knowledge, none of the existing schemes define a secure channel-free conjunctive keyword based Searchable Encryption that prevents token replay attack in multiuser environment.


### 1.2. Our Contributions

In this paper, we propose a Multiuser Searchable Encryption with Token Freshness Verification (MUSE-TFV). In MUSE-TFV, a user constructs a search token in cooperation with the ETA and thus every search activity from each user is logged at the enterprise trusted site. Moreover, each search token is one-time usable token. The server avoids reuse of the same token by verifying the freshness of the token using a verification key given by the ETA. Our main contributions are as follows.(i)
Multiuser Support. Utilizing the notion of FE, we devise a Searchable Encryption scheme that supports multiple users, with a constant size ciphertext (i.e., independent of the number of users). Our scheme has an optimal computational overhead at the Data Owner site and an optimal storage overhead at the server site.(ii)
Token Freshness Verification. We propose a token freshness verification at the server site by adapting Haller’s S/Key One-Time Password System [34] and prevent token replay attack from the system.(iii)
Conjunctive Keyword Search. With the proposed scheme, we offer a conjunctive keyword search with a constant sized search token.(iv)
Secure Channel-Free Architecture. We offer a secure channel-free architecture to transfer a token securely via any public channel without channel setup overhead.(v)
Theoretical Analysis and Empirical Evaluation. We present a detailed theoretical analysis to show the efficiency of the proposed scheme. Additionally, with experimental evaluation of MUSE-TFV for different size system (with a different number of keywords) and different number of users, we justify its effectiveness.


### 1.3. Organization of the Rest of the Paper

The rest of the paper is organized as follows: In Section2, we briefly discuss the preliminaries required for the proposed scheme. In Section 3, we define the formal model of MUSE-TFV, the proposed algorithms, and the attack model with security definition. We elaborated the algorithms with a detailed security analysis in Section 4. Further, in Section 5, we present a theoretical analysis and empirical evaluation of MUSE-TFV. Finally, we put the concluding remarks in Section 6.


## 1.1. Related Work

The notion of Searchable Encryption is introduced by Song et al. in [4] where the authors consider search over encrypted keywords within a file. However, this first practical scheme leaks the search keywords to the server and suffers from the communication overhead linear to the file size. In fact, the scheme in [4] is not secure against statistical analysis across multiple queries. To resolve the problems, Goh et al. [5] and Chang and Mitzenmacher [24] in their separate work construct the secure searchable schemes by proposing an encrypted index for a document. Though the schemes in [4, 5, 24] perform efficient search operations, they introduce storage overhead linear to the size of an index for each document. Curtmola et al. [25] propose the first symmetric searchable encryption scheme with a formal security model. The first public key Searchable Encryption scheme is given by Boneh et al. [6] wherein a user with his private key can search over data encrypted with the corresponding public key. However, none of the schemes [4–6, 24] support conjunctive keyword search.Conjunctive Keyword Searchable Schemes. To narrow down the scope of searching and get optimal results, several searchable schemes exist with conjunctive keyword search operation. In the symmetric key settings, Golle et al. [26] have constructed two schemes for a conjunctive keyword search. However, in the first construction of [26], the size of a capability (search token) is linear to the number of documents available on the server and so the scheme is impractical. On the other hand, the second construction of [26] is practical with a constant size capability. The other constructions based on the secret sharing and bilinear map are given by Ballard et al. [27] but they are still inefficient in terms of a size of a token linear to the number of documents being searched. In public key settings, a first conjunctive keyword searchable scheme is defined by Park et al. [8]. Subsequently, the schemes with the improved communication and storage efficiency are proposed in [9, 28]. Boneh and Waters have given a generalized scheme [29] for conjunction as well as for subset queries. Later on, a scheme with a refined form of a token (that is independent of specifying the keyword field position) is devised by Wang et al. [13]. Subsequently, B. Zhang and F. Zhang [21] have improved the security flaws of [13] and defined a conjunctive-subset keyword search. Other efficient constructions with the support of conjunctive keyword search operation are given in [22, 23, 30].Multiuser Searchable Schemes. In public key settings, Hwang and Lee [9] have first introduced a storage efficient multiuser scheme. Subsequently, several other schemes [10, 11, 13, 14, 16] have proposed managing a group of users. However, a scheme in [11] supports the static groups of users, whereas the schemes discussed in [10, 13, 14] work for the dynamic groups of users. Apart from this, the scheme in [14] provides a single keyword search whereas the schemes in [10, 13] handle the conjunctive search queries. Recently, a multiuser multikeyword search scheme is proposed by Huang et al. [16] but its inverted index based construction cannot support an efficient conjunctive search. In addition, a scheme in [16] leaks user access control information to the server. Few other multiuser schemes [17–20] are based on the notion of FE wherein an ETA is responsible for the System Setup and a master public key setup. In these schemes, a ciphertext is prepared by a Data Owner using a master public key. A search token is constructed by a user with his own search key issued either by the ETA as in [18–20] or by the Data Owner as in [17]. A scheme in [17] offers a constant size ciphertext and a constant size token. However, the scheme [17] is computationally inefficient since, to encrypt an index for a document, the encryption algorithm involves a computational complexity linear to the number of authorized users for that document. In a scheme of [18], the Storage Server has a list of authorized users (U_List), and thus each enrollment/revocation of a user is known to the server. This indeed leaks information about users (i.e., a number of users in the system, the users’ activity) to the Storage Server. The other two schemes [19, 20] use CPABE (Ciphertext Policy Attribute Based Encryption) to manage access control of users. However, amongst all these schemes, only the schemes in [9, 10, 13, 16] support multikeyword (specifically conjunctive) search and multiple users at the same time. There is no FE based scheme proposing a conjunctive keyword based search.Secure Channel-Free Searchable Schemes. There exist searchable schemes in [7, 31, 32] with secure channel-free architecture for a token transmission. However, these schemes support a single keyword search. The most recent conjunctive search schemes [30, 33] provide a secure channel-free token transmission.To the best of our knowledge, none of the existing schemes define a secure channel-free conjunctive keyword based Searchable Encryption that prevents token replay attack in multiuser environment.


## 1.2. Our Contributions

In this paper, we propose a Multiuser Searchable Encryption with Token Freshness Verification (MUSE-TFV). In MUSE-TFV, a user constructs a search token in cooperation with the ETA and thus every search activity from each user is logged at the enterprise trusted site. Moreover, each search token is one-time usable token. The server avoids reuse of the same token by verifying the freshness of the token using a verification key given by the ETA. Our main contributions are as follows.(i)
Multiuser Support. Utilizing the notion of FE, we devise a Searchable Encryption scheme that supports multiple users, with a constant size ciphertext (i.e., independent of the number of users). Our scheme has an optimal computational overhead at the Data Owner site and an optimal storage overhead at the server site.(ii)
Token Freshness Verification. We propose a token freshness verification at the server site by adapting Haller’s S/Key One-Time Password System [34] and prevent token replay attack from the system.(iii)
Conjunctive Keyword Search. With the proposed scheme, we offer a conjunctive keyword search with a constant sized search token.(iv)
Secure Channel-Free Architecture. We offer a secure channel-free architecture to transfer a token securely via any public channel without channel setup overhead.(v)
Theoretical Analysis and Empirical Evaluation. We present a detailed theoretical analysis to show the efficiency of the proposed scheme. Additionally, with experimental evaluation of MUSE-TFV for different size system (with a different number of keywords) and different number of users, we justify its effectiveness.


## 1.3. Organization of the Rest of the Paper

The rest of the paper is organized as follows: In Section2, we briefly discuss the preliminaries required for the proposed scheme. In Section 3, we define the formal model of MUSE-TFV, the proposed algorithms, and the attack model with security definition. We elaborated the algorithms with a detailed security analysis in Section 4. Further, in Section 5, we present a theoretical analysis and empirical evaluation of MUSE-TFV. Finally, we put the concluding remarks in Section 6.


## 2. Preliminaries

In this section, we present an overview of a Functional Encryption, a cryptographic primitive (i.e., Bilinear Map), and a hardness assumption associated with the proposed scheme.


### 2.1. Functional Encryption (FE)

FE is a generalization of the existing access control mechanisms, namely, Identity Based Encryption (IBE) [35, 36], Attribute Based Encryption (ABE) [37–39], and Predicate Encryption (PE) [29, 40]. In FE, apart from the Data Owner, Data User, and the Storage Server, there exists an additional centralized trusted authority (TA) that is responsible for the System Setup and generation of a master public-private key pair. A Data Owner prepares the ciphertexts with a master public key and stores them to the Storage Server. To execute a predefined function at the server site, a user asks the TA for the corresponding token. In response, the TA constructs a token utilizing a master private key and issues it to the user. The server runs the function on the availability of a token from a user and sends the result to the user (Figure 2). In such a setup, any user who possesses a token can ask the server for the function execution. Since the server could use the same set of ciphertexts to execute a function with different tokens (may be from different users), we say that the FE supports multiple users in the system.Figure 2
System model of Functional Encryption (FE). Steps:(1) Data Owner uploads ciphertext C onto the Storage Server; (2) Data User requests TA for a token of a function (F); (3) TA issues a token TF to the user; (4) Data User sends TF to the Storage Server; (5) Storage Server runs F on available C; (6) Storage Server forwards the result RF to the user.


### 2.2. Bilinear Map

Bilinear map is a mathematical tool for pairing based cryptography. It is defined using suitable cryptographic groups. LetG1 and G2 be two multiplicative cyclic groups of prime order p. For these groups, a bilinear map e: G1×G1→G2 must satisfy the following properties:(1)
Bilinear: given random P,Q∈G1 and a,b∈Zp∗ we have e(aP,bQ)=e(P,Q)ab.(2)
Nondegenerate: if P is a generator of G1, then e(P,P) is a generator of G2.(3)
Computable: given P,Q∈G1, there exists a polynomial time algorithm to compute e(P,Q)∈G2.


### 2.3. Hardness Assumption

Decisional Diffie-Hellman (DDH) Assumption. Let G1 be a cyclic group of prime order p and P is a generator of G1. TheDecisional Diffie-Hellman problem is to distinguish the tuple (aP,bP,abP) from (aP,bP,cP) for any random a,b,c∈Zp∗. Let us assume that the DDH problem is (ϵ,t)-hard in G1. Then there does not exist any polynomial time (t) adversary A that can solve the DDH problem with a nonnegligible advantage ϵ, if PrAaP,bP,abP-PrAaP,bP,cP≤ϵ.


## 2.1. Functional Encryption (FE)

FE is a generalization of the existing access control mechanisms, namely, Identity Based Encryption (IBE) [35, 36], Attribute Based Encryption (ABE) [37–39], and Predicate Encryption (PE) [29, 40]. In FE, apart from the Data Owner, Data User, and the Storage Server, there exists an additional centralized trusted authority (TA) that is responsible for the System Setup and generation of a master public-private key pair. A Data Owner prepares the ciphertexts with a master public key and stores them to the Storage Server. To execute a predefined function at the server site, a user asks the TA for the corresponding token. In response, the TA constructs a token utilizing a master private key and issues it to the user. The server runs the function on the availability of a token from a user and sends the result to the user (Figure 2). In such a setup, any user who possesses a token can ask the server for the function execution. Since the server could use the same set of ciphertexts to execute a function with different tokens (may be from different users), we say that the FE supports multiple users in the system.Figure 2
System model of Functional Encryption (FE). Steps:(1) Data Owner uploads ciphertext C onto the Storage Server; (2) Data User requests TA for a token of a function (F); (3) TA issues a token TF to the user; (4) Data User sends TF to the Storage Server; (5) Storage Server runs F on available C; (6) Storage Server forwards the result RF to the user.


## 2.2. Bilinear Map

Bilinear map is a mathematical tool for pairing based cryptography. It is defined using suitable cryptographic groups. LetG1 and G2 be two multiplicative cyclic groups of prime order p. For these groups, a bilinear map e: G1×G1→G2 must satisfy the following properties:(1)
Bilinear: given random P,Q∈G1 and a,b∈Zp∗ we have e(aP,bQ)=e(P,Q)ab.(2)
Nondegenerate: if P is a generator of G1, then e(P,P) is a generator of G2.(3)
Computable: given P,Q∈G1, there exists a polynomial time algorithm to compute e(P,Q)∈G2.


## 2.3. Hardness Assumption

Decisional Diffie-Hellman (DDH) Assumption. Let G1 be a cyclic group of prime order p and P is a generator of G1. TheDecisional Diffie-Hellman problem is to distinguish the tuple (aP,bP,abP) from (aP,bP,cP) for any random a,b,c∈Zp∗. Let us assume that the DDH problem is (ϵ,t)-hard in G1. Then there does not exist any polynomial time (t) adversary A that can solve the DDH problem with a nonnegligible advantage ϵ, if PrAaP,bP,abP-PrAaP,bP,cP≤ϵ.


## 3. Proposed Multiuser Searchable Encryption with Token Freshness Verification (MUSE-TFV)

We list out the notations used throughout the paper in Notations section. We include a system model, the associated algorithms, and the attack model with the security definition for the proposed scheme.


### 3.1. System Model

The proposed MUSE-TFV involves four entities: (i) Data Owner (DO), (ii) Data User (DU), (iii) Storage Server (SS), and (iv) Enterprise Trusted Authority (ETA) (Figure3).Figure 3
System model of MUSE-TFV.The interactive actions amongst these entities are as follows:(1)
Initially, the ETA sets up the system’s public parameters and a master secret key.(2)
Using public parameters, the SS computes a public-private key pair (Y,y) and publishes Y while keeping y secret.(3)
Using public parameters, the DU computes a public-private key pair (X,x) and publishes X while keeping x secret.(4)
A DO prepares a ciphertext (C) by associating an encrypted payload (M′) with a list W of encrypted keywords and uploads it onto the SS. All the keywords in the list are encrypted with anEncryption() algorithm of proposed MUSE-TFV.(5)
To execute a search operation, the DO requests the ETA for a token of a conjunctive query.(6)
The ETA computes a token (PT′) and corresponding token verification keys (TVK1,TVK2). The ETA issues a partial token PT=(PT′,TVK1) to the DU and TVK2 to the SS.(7)
The DU constructs a search token (T′) from PT′ and issues a final token T=(T′,TVK1) to the SS over a public channel.(8)
The proposedSearch() algorithm is executed on the server SS. With the available (TVK1,TVK2), the SS checks the token freshness. The SS applies the fresh token T′ on the available C. If C satisfies the token T, the algorithm outputs a result R=EyEXM′; otherwise it outputs ⊥. The algorithm applies T on all available C and generates the corresponding R.Note. Steps (2), (3), and (4) can run in parallel.Assumptions. (i) The payload M′=Ekey(M), where E is any symmetric encryption cipher with a symmetric key key. (ii) All DUs are authorized by the ETA. At the time of authorization, ETA issues (pp,key) to the DU. (iii) Before issuing a partial token PT, the ETA checks the authenticity of a DU with any standard authentication protocol. (iv) The SS is a semihonest server; that is, it follows the system protocol but tries to breach data privacy. (v) There exists a secure channel between the ETA and the SS. (vi) The TVK2 is stored in a system table of the SS. The size of the system table is linear to the number of DUs.


### 3.2. Algorithms

The proposed MUSE-TFV involves the following polynomial time algorithms:(1)
Setup(α,n). TheSetup algorithm runs by the ETA. The algorithm takes a security parameters α and n as inputs. The algorithm outputs the system’s public parameter pp and a master secret key msk. It defines a keyword space KS for n keywords.(2)
SKeyGen(pp). TheServer Key Generation algorithm runs by the server SS. The algorithm takes the system’s public parameter pp as inputs. It selects a random y∈Zp∗ and computes the public-private key pair (Y,y) for the server SS.(3)
UKeyGen(pp). TheUser Key Generation algorithm runs by the DU. The algorithm takes the system’s public parameter pp as inputs. It selects a random x∈Zp∗ and computes the public-private key pair (X,x) for the Data User, DU.(4)
Encryption(pp,W,Y,M′). TheEncryption algorithm runs by the DO. The algorithm constructs a ciphertext C′ from the list of keywords W=w1,w2,…,wn using pp and Y. It associates C′ with an encrypted payload M′ and outputs a ciphertext C=(C′,M′).(5)
TokGen(pp,msk,Q,X,x,Y). TheToken Generation is an interactive algorithm where initially a DU supplies a conjunctive query Q=W′,I′ to the ETA. Here, W′=w1′,w2′,…,wt′ is a set of keywords and I′=I1,I2,…,It shows their positions in KS. For each new query, the ETA assigns a unique token identification string (TOKID) in order to generate the token verification keys (TVK1,TVK2). Subsequently, the ETA constructs a token PT′ using msk and X. The ETA then issues a partial token PT=(PT′,TVK1) to the DU and (TVK2) to the SS. With an available PT, the DU constructs T′ and outputs a final token T=(T′,TVK1).(6)
Search(C,T,y). TheSearch algorithm runs by the SS. The algorithm utilizes (TVK1,TVK2) to verify the freshness of T. If T is fresh, the algorithm performs a conjunctive search using T′,C′,y. It returns the result R=EyEXM′ to the DU if C′ satisfies the conjunctive query Q within T′; otherwise it returns ⊥. The algorithm applies T′ on all the ciphertexts. At last, the algorithm updates the system table entry of TVK2 for the requesting DU to prevent a token replay attack.The algorithms involved in the verification key generation and token verification as well as system table update are discussed in Section4.2.


### 3.3. Flowchart

To show the process of the proposed MUSE-TFV, we define four phases: (i) System Setup, (ii) Data Upload, (iii) Token Generation, and (iv) Search. The sequence of the proposed algorithms utilized by the entities (i.e., ETA, DO, DU, SS) during each of these phases is given as a flowchart in Figure4. As shown in Figure 4(a), all four entities are involved in System Setup phase where a public parameter (pp) and various keys (i.e., msk,key,(X,x),(Y,y)) are defined. On the other hand, Data Upload phase (Figure 4(b)) includes only DO and SS since, during this phase, a DO prepares a ciphertext C and uploads it on to the SS. The interactive steps amongst DU, ETA, and SS during Token Generation phase are shown in Figure 4(c) wherein initially a DU sends a conjunctive query Q to the ETA. In response, the ETA sends a partial token along with a token verification key (i.e., (PT,TVK1)) to the DU. In addition, the ETA sends a token verification key (i.e., TVK2) to the SS. With the available (PT,TVK1), the DU prepares a final token T. During Search phase, the DU sends T to the SS as shown in Figure 4(d). In response, the SS finds the results R for the available ciphertexts and forwards these results to the DU.Figure 4
Flowchart of MUSE-TFV.
(a)
(b)
(c)
(d)


### 3.4. Attack Model and Security Definitions

First, we reemphasize that the principal motivation of the proposed MUSE-TFV is to overcome the limitation in the existing Searchable Encryption schemes that allow replay of tokens and thus lack verification of token freshness. Thus, MUSE-TFV is aimed at supporting a Searchable Encryption scheme with the novel provision for verification of the token freshness and thereby avoiding replay attacks. Therefore in the attack model described here we consider only token replay attacks and assume that any other attack against the scheme can be mitigated by using already existing mitigation approaches.We assume that an adversaryA has the capabilities to perform the following attacks:(1)
The server SS as an adversaryA can perform chosen keyword attack to deduce the plaintext (keywords) from the available ciphertexts (lists of encrypted keywords) and tokens.(2)
The Data User, DU, as an adversaryA can perform token replay attack to reuse the maliciously captured token.With SS as an adversary, we define semantic security (a.k.a. indistinguishability against chosen keyword attack (IND-CKA)) for the proposed conjunctive keyword search scheme based on the security game ICLR (Indistinguishability of Ciphertext from Limited Random) [26, 41] as follows.Definition 1 (ICLR).
LetA be a polynomial bounded adversary and B be a challenger. With ICLR, when A has issued a keyword set W and a subset T⊆1,2,…,n, B responds with two encrypted keyword sets associated with T in such a way that A cannot distinguish the encrypted keyword sets created with T. Thus, with this game, we achieve our security goal where we require that A should not be able to deduce the plaintext from other keyword sets. The following are the steps for the game ICLR [26, 41].(1)
A adaptively requests B for the Encryption (pp,Wi,Y,M′) of any keyword set Wi and any search token.(2)
A selects a keyword set W, a subset T⊆1,2,…,n, and t∈T in such a way that none of the tokens given in Step (1) are distinguishing for Rand(W,T) and Rand(W,T-t). Here, Rand(W,T) outputs a set W where the keywords indexed by T (i.e., the set wi∣i∈T) are replaced by random values. A then sends (W,T,t) to the challenger B.(3)
B constructs two keyword sets W0=Rand(W,T-t) and W1=Rand(W,T). B then randomly chooses b∈0,1 and returns Encryption (pp,Wb,Y,M′) to A.(4)
A again makes requests for encrypted keyword sets and search tokens, with the restriction that he cannot ask for the token that is distinguishing for W0 and W1.(5)
A outputs a bit b′∈0,1 and wins the ICLR game if b′=b.We say that the polynomial time adversaryA has an advantage ϵ in this attack game, if(1)AdvA1α=Pr⁡b′=b-12>ϵ.Additionally, we define the security against token replay attack based on the following actions performed by a Data User, DU, as an adversary A.(1)
A intercepts a token T=(T′,c=EY(TVK1)) transmitted from the ETA to the DU (or from a DU to the SS) and stores it.(2)
To reuse the tokenT, A replaces its verification key part, that is, c=EY(TVK1), with c′ in such a way that the SS considers a forged T=T′,c′ as a fresh token and returns a result R.(3)
A repeats Step (2) till he does not receive the result R.We say that an adversaryA is successful in token replay attack if he gets the result R using a forged value of c.


## 3.1. System Model

The proposed MUSE-TFV involves four entities: (i) Data Owner (DO), (ii) Data User (DU), (iii) Storage Server (SS), and (iv) Enterprise Trusted Authority (ETA) (Figure3).Figure 3
System model of MUSE-TFV.The interactive actions amongst these entities are as follows:(1)
Initially, the ETA sets up the system’s public parameters and a master secret key.(2)
Using public parameters, the SS computes a public-private key pair (Y,y) and publishes Y while keeping y secret.(3)
Using public parameters, the DU computes a public-private key pair (X,x) and publishes X while keeping x secret.(4)
A DO prepares a ciphertext (C) by associating an encrypted payload (M′) with a list W of encrypted keywords and uploads it onto the SS. All the keywords in the list are encrypted with anEncryption() algorithm of proposed MUSE-TFV.(5)
To execute a search operation, the DO requests the ETA for a token of a conjunctive query.(6)
The ETA computes a token (PT′) and corresponding token verification keys (TVK1,TVK2). The ETA issues a partial token PT=(PT′,TVK1) to the DU and TVK2 to the SS.(7)
The DU constructs a search token (T′) from PT′ and issues a final token T=(T′,TVK1) to the SS over a public channel.(8)
The proposedSearch() algorithm is executed on the server SS. With the available (TVK1,TVK2), the SS checks the token freshness. The SS applies the fresh token T′ on the available C. If C satisfies the token T, the algorithm outputs a result R=EyEXM′; otherwise it outputs ⊥. The algorithm applies T on all available C and generates the corresponding R.Note. Steps (2), (3), and (4) can run in parallel.Assumptions. (i) The payload M′=Ekey(M), where E is any symmetric encryption cipher with a symmetric key key. (ii) All DUs are authorized by the ETA. At the time of authorization, ETA issues (pp,key) to the DU. (iii) Before issuing a partial token PT, the ETA checks the authenticity of a DU with any standard authentication protocol. (iv) The SS is a semihonest server; that is, it follows the system protocol but tries to breach data privacy. (v) There exists a secure channel between the ETA and the SS. (vi) The TVK2 is stored in a system table of the SS. The size of the system table is linear to the number of DUs.


## 3.2. Algorithms

The proposed MUSE-TFV involves the following polynomial time algorithms:(1)
Setup(α,n). TheSetup algorithm runs by the ETA. The algorithm takes a security parameters α and n as inputs. The algorithm outputs the system’s public parameter pp and a master secret key msk. It defines a keyword space KS for n keywords.(2)
SKeyGen(pp). TheServer Key Generation algorithm runs by the server SS. The algorithm takes the system’s public parameter pp as inputs. It selects a random y∈Zp∗ and computes the public-private key pair (Y,y) for the server SS.(3)
UKeyGen(pp). TheUser Key Generation algorithm runs by the DU. The algorithm takes the system’s public parameter pp as inputs. It selects a random x∈Zp∗ and computes the public-private key pair (X,x) for the Data User, DU.(4)
Encryption(pp,W,Y,M′). TheEncryption algorithm runs by the DO. The algorithm constructs a ciphertext C′ from the list of keywords W=w1,w2,…,wn using pp and Y. It associates C′ with an encrypted payload M′ and outputs a ciphertext C=(C′,M′).(5)
TokGen(pp,msk,Q,X,x,Y). TheToken Generation is an interactive algorithm where initially a DU supplies a conjunctive query Q=W′,I′ to the ETA. Here, W′=w1′,w2′,…,wt′ is a set of keywords and I′=I1,I2,…,It shows their positions in KS. For each new query, the ETA assigns a unique token identification string (TOKID) in order to generate the token verification keys (TVK1,TVK2). Subsequently, the ETA constructs a token PT′ using msk and X. The ETA then issues a partial token PT=(PT′,TVK1) to the DU and (TVK2) to the SS. With an available PT, the DU constructs T′ and outputs a final token T=(T′,TVK1).(6)
Search(C,T,y). TheSearch algorithm runs by the SS. The algorithm utilizes (TVK1,TVK2) to verify the freshness of T. If T is fresh, the algorithm performs a conjunctive search using T′,C′,y. It returns the result R=EyEXM′ to the DU if C′ satisfies the conjunctive query Q within T′; otherwise it returns ⊥. The algorithm applies T′ on all the ciphertexts. At last, the algorithm updates the system table entry of TVK2 for the requesting DU to prevent a token replay attack.The algorithms involved in the verification key generation and token verification as well as system table update are discussed in Section4.2.


## 3.3. Flowchart

To show the process of the proposed MUSE-TFV, we define four phases: (i) System Setup, (ii) Data Upload, (iii) Token Generation, and (iv) Search. The sequence of the proposed algorithms utilized by the entities (i.e., ETA, DO, DU, SS) during each of these phases is given as a flowchart in Figure4. As shown in Figure 4(a), all four entities are involved in System Setup phase where a public parameter (pp) and various keys (i.e., msk,key,(X,x),(Y,y)) are defined. On the other hand, Data Upload phase (Figure 4(b)) includes only DO and SS since, during this phase, a DO prepares a ciphertext C and uploads it on to the SS. The interactive steps amongst DU, ETA, and SS during Token Generation phase are shown in Figure 4(c) wherein initially a DU sends a conjunctive query Q to the ETA. In response, the ETA sends a partial token along with a token verification key (i.e., (PT,TVK1)) to the DU. In addition, the ETA sends a token verification key (i.e., TVK2) to the SS. With the available (PT,TVK1), the DU prepares a final token T. During Search phase, the DU sends T to the SS as shown in Figure 4(d). In response, the SS finds the results R for the available ciphertexts and forwards these results to the DU.Figure 4
Flowchart of MUSE-TFV.
(a)
(b)
(c)
(d)


## 3.4. Attack Model and Security Definitions

First, we reemphasize that the principal motivation of the proposed MUSE-TFV is to overcome the limitation in the existing Searchable Encryption schemes that allow replay of tokens and thus lack verification of token freshness. Thus, MUSE-TFV is aimed at supporting a Searchable Encryption scheme with the novel provision for verification of the token freshness and thereby avoiding replay attacks. Therefore in the attack model described here we consider only token replay attacks and assume that any other attack against the scheme can be mitigated by using already existing mitigation approaches.We assume that an adversaryA has the capabilities to perform the following attacks:(1)
The server SS as an adversaryA can perform chosen keyword attack to deduce the plaintext (keywords) from the available ciphertexts (lists of encrypted keywords) and tokens.(2)
The Data User, DU, as an adversaryA can perform token replay attack to reuse the maliciously captured token.With SS as an adversary, we define semantic security (a.k.a. indistinguishability against chosen keyword attack (IND-CKA)) for the proposed conjunctive keyword search scheme based on the security game ICLR (Indistinguishability of Ciphertext from Limited Random) [26, 41] as follows.Definition 1 (ICLR).
LetA be a polynomial bounded adversary and B be a challenger. With ICLR, when A has issued a keyword set W and a subset T⊆1,2,…,n, B responds with two encrypted keyword sets associated with T in such a way that A cannot distinguish the encrypted keyword sets created with T. Thus, with this game, we achieve our security goal where we require that A should not be able to deduce the plaintext from other keyword sets. The following are the steps for the game ICLR [26, 41].(1)
A adaptively requests B for the Encryption (pp,Wi,Y,M′) of any keyword set Wi and any search token.(2)
A selects a keyword set W, a subset T⊆1,2,…,n, and t∈T in such a way that none of the tokens given in Step (1) are distinguishing for Rand(W,T) and Rand(W,T-t). Here, Rand(W,T) outputs a set W where the keywords indexed by T (i.e., the set wi∣i∈T) are replaced by random values. A then sends (W,T,t) to the challenger B.(3)
B constructs two keyword sets W0=Rand(W,T-t) and W1=Rand(W,T). B then randomly chooses b∈0,1 and returns Encryption (pp,Wb,Y,M′) to A.(4)
A again makes requests for encrypted keyword sets and search tokens, with the restriction that he cannot ask for the token that is distinguishing for W0 and W1.(5)
A outputs a bit b′∈0,1 and wins the ICLR game if b′=b.We say that the polynomial time adversaryA has an advantage ϵ in this attack game, if(1)AdvA1α=Pr⁡b′=b-12>ϵ.Additionally, we define the security against token replay attack based on the following actions performed by a Data User, DU, as an adversary A.(1)
A intercepts a token T=(T′,c=EY(TVK1)) transmitted from the ETA to the DU (or from a DU to the SS) and stores it.(2)
To reuse the tokenT, A replaces its verification key part, that is, c=EY(TVK1), with c′ in such a way that the SS considers a forged T=T′,c′ as a fresh token and returns a result R.(3)
A repeats Step (2) till he does not receive the result R.We say that an adversaryA is successful in token replay attack if he gets the result R using a forged value of c.


## 4. Construction of MUSE-TFV

In this section, we give the formal construction for the proposed algorithms of MUSE-TFV. We also present a token verification procedure used in the design of the MUSE-TFV. Additionally, we provide a security analysis for the proposed scheme.


### 4.1. Formal Construction

The concrete constructions for the proposed algorithms are as follows.(1)
Setup(α,n). Let G1 and G2 be bilinear groups of prime order p where a security parameter α defines the group size. Let e:G1×G1→G2 be a bilinear pairing and H1:0,1∗→Zp∗ is a hash function. Let H:0,1∗→0,1b be any standard hash function (e.g., SHA2) that outputs a message digest of b bits. Let P be a generator of G1. The algorithm initializes the keyword space KS of total n keywords. For each jth keyword, it randomly selects kj∈Zp∗ and computes Kj=kjP. Finally, the algorithm sets the public parameter pp=H1,H,G1,G2,P,e,Kj1≤j≤n and a master secret key msk = kj1≤j≤n.(2)
SKeyGen(pp). The algorithm selects a random y∈Zp∗ and computes Y=yP. It sets the public-private key pair for the server SS as (Y,y).(3)
UKeyGen(pp). The algorithm selects a random x∈Zp∗ and computes X=xP. It sets the public-private key pair for the user DU as (X,x).(4)
Encryption(pp,W,Y,M′). The algorithm takes as input a list of keywords W=w1,w2,…,wn. It chooses a random r1∈Zp∗ and constructs a ciphertext C′=C1j,C21≤j≤n, where C1j=r1(H1(wj)P+Kj)+r1Y, C2=r1P. Finally, it outputs a ciphertext C=C′,M′, where M′ is an encrypted payload.(5)
TokGen(pp,msk,Q,X,x,Y). This interactive algorithm works in 3 phases.
(a)
A DU sends a conjunctive queryQ=W′,I′ to the ETA where W′=w1′,w2′,…,wt′ is a set of keywords and I′=I1,I2,…,It is a set of positions of keywords in KS.(b)
In response, the ETA chooses a unique token identification stringTokID∈0,1l and a secret random integer N. The ETA uses TokVerKey(TokID,N,H())→(TVK1,TVK2) algorithm to construct the token verification keys. The ETA selects t1∈Zp∗ randomly. It uses msk and X to construct a token component PT′=PT1,PT2, where PT1=t1(∑j=I1It‍(H1(wj)+kj))P+t1X, PT2=t1P. At last, the ETA sends a partial token PT=(PT′,EY(TVK1)) to the DU. At the same time, it forwards (EY(TVK2)) to the SS.(c)
The DU selects a random elementa′∈Zp∗. Using x and Y, the DU computes T′=T1,T2,T3,T4 as follows:T1=τ+a′Y, T2=PT2=t1P, T3=a′P, T4=I′ Where τ=PT1-xPT2=t1(∑j=I1It‍(H1(wj)+kj))P.Finally, the algorithm outputs a tokenT=(T′,EY(TVK1)).(6)
Search(C,T,y). The algorithm applies Dy(EY(TVK1)) and Dy(EY(TVK2)) to get the original verification key (TVK1,TVK2) from the encrypted values using a private key y of the SS. The algorithm then calls TokVer(TVK1, TVK2) to verify the freshness of the input token T. If a token is fresh (i.e., TokVer(·)→1), it applies T′ of T on an available ciphertext C′ from C as follows.The algorithm computes(2)τ1=∑j=I1ItC1j-yC2=∑j=I1Itr1H1wjP+Kj+r1Y-yr1P=r1∑j=I1ItH1wjP+Kj,τ2=T1-yT3=t1∑j=I1ItH1wj+kjP+a′Y-ya′P=t1∑j=I1ItH1wj+kjP.Then, it checks the following correctness:(3)eτ1,T2=eτ2,C2.If (3) is satisfied, then the algorithm outputs the associated payload message M′; as a result R=Ey(EX(M′)). Here, encryption with a public key X of DU provides confidentiality and signature with the private key y of SS maintains integrity of a result R during transit. The algorithm repeatedly applies T′ on each available ciphertext at the server SS. At last, the algorithm updates the current entry of TVK2 in the system table with TUpdate(TVK2,TVK1).Note. (i) The algorithms TokVerKey(), TokVer(), and TUpdate() are described in Section 4.2. (ii) The query Q from a DU to the ETA is in plaintext format. It does not impact the security of token as even if any unauthorized DU maliciously captures a partial token, he is unable to construct a final token unless having secret key x. (iii) The E/D for the verification keys is any standard encryption/decryption cipher. The encryption of the verification keys with the public key Y of SS prevents their modification by a malicious DU.Correctness. LHS of (3):(4)eτ1,T2=er1∑j=I1ItH1wjP+Kj,t1P=e∑j=I1ItH1wjP+Kj,Pr1t1=e∑j=I1ItH1wjP+kjP,Pr1t1=eP,Pr1t1Δ.RHS of (3):(5)eτ2,C2=et1∑j=I1ItH1wj+kjP,r1P=eP,Pr1t1Δ.Here, Δ=∑j=I1It‍(H1(wj)+kj). From (4) and (5), the correctness is proved.


### 4.2. Token Verification Procedure

To define a token verification procedure, we borrow the idea from Haller’s S/Key One-Time Password System [34]. The S/Key scheme provides a technique to construct a one-time password at the client site and its verification at the host site. The scheme works on 3 parameters (s,RN,H()), where s is a secret string, RN represents the number of times the hash is applied on s, and H() is any standard cryptographic hash function. We adopt similar parameters to define a token verification procedure for the proposed MUSE-TFV. The token freshness verification involves three algorithms:(1)
TokVerKey(s,RN,H()): thetoken verification key generation algorithm outputs two keys (K1,K2), where K1=HRN(s) and K2=HRN-1(s).(2)
TokVer(K1,K2): thetoken verification algorithm verifies the freshness of a token by checking K1=H(K2). If condition is true, the algorithm outputs “1” otherwise “0.”(3)
TUpdate(K1,K2): thetoken update algorithm updates the current memory location of K1 with K2; that is, it performs K1=K2.The original S/Key mechanism is defined with the traditional hash function, that is, MD4. For MUSE-TFV, we prefer SHA-2 to avoid collision attack.


### 4.3. Security Analysis

We analyze the semantic security of MUSE-TFV against chosen keyword attack (IND-CKA) under DDH assumption. Additionally, we prove that the proposed MUSE-TFV provides security against token replay attack.Theorem 2.
The proposed MUSE-TFV is semantically secure against a server SS as an adversary according to the game ICLR, assuming DDH is intractable.Proof.
Let us assume a server SS as an adversaryA can attack the proposed scheme in a polynomial time. Suppose A makes at most qk token queries where qk<p and has the advantage ϵ in solving DDH problem in G1. Let G1 and G2 be two groups of prime order p and P be the generator of G1. We build a simulator B as a challenger that has the advantage ϵ′=ϵ/enqkn to simulate the game where e is base of natural logarithm.
Suppose an instance(aP,bP,cP) of the DDH problem in G1 is the B’s challenge information where a,b,c∈Zp∗. The goal of B is to distinguish cP=abP from random element in G1. One restriction is that the random element z is independent of the location t selected in ICLR game; then the simulation game is demonstrated as follows.(1)
Setup. An adversary A randomly selects y∈Zp∗ and computes Y=yP. A then defines a public-private key pair (Y,y). Let (X=xP,x) be the B’s public-private key pair.(2)
Encryption Queries. An adversary A issues the queries for the ciphertext of the keyword set Wi=wi1,wi2,…,win. In response, challenger B simulatesEncryption(pp,Wi,Y) as follows.
(i)
B selects γj∈Zp∗ for each keyword wij∈Wi, where 1≤j≤n.(ii)
B chooses a random value r1i∈Zp∗ and constructs a ciphertext Ci = {(C1j)i,(C2)i}1≤j≤n, where(6)C11i=r1iγ1P+K1+r1iYC12i=r1iγ2P+K2+r1iY⋮C1zi=br1iγzP+Kz+r1iY⋮C1ni=r1iγnP+Kn+r1iYC2i=r1iP.(3)
Token Queries. To evaluateSearch() algorithm, A issues the token queries by sending Qi=(Wi′,Ii′), where Wi′={wiI1′,wiI2′,…,wiIt′} and Ii′=I1,I2,…,It to B. B takes a partial token PT′=PT1,PT2 from the ETA where PT1=t1(∑j=I1It‍(H1(wj)+kj))P+t1X, PT2=t1P. B then selects a random a′∈Zp∗ and computes final token Ti=T1i,T2i,T3i,T4i as follows.T1i=τ+a′Y, T2i=t1P, T3i=a′P, T4i=I′, where τ=PT1-xPT2=t1(∑j=I1It‍(H1(wj)+kj))P.At last,B sends this token Ti to A.(4)
Challenge. A issues a tuple (Wi,T,t) to B where T⊆1,n and t∈T.Ifz≠t, B sends a random guess as the response to the DDH challenge.Ifz=t, B responses are as follows.
(a)
It first setsht=c(γtP+Kt)+cY.(b)
It setsh1j=lj, for j≠t, j∈T, where lj∈Zp∗.(c)
It setsh1j=a(γjP+Kj)+aY, for j≠t, j∉T.(d)
It setsh2=aP.Finally,B sends h1j,h2 for 1≤j≤n as challenge ciphertext to A.Ifz=t, then B wins the security game. The ciphertext for every position j∉T is the encryption of W and ciphertext in position t where c=ab is also an encryption of W. Otherwise, for other position, it is not.(5)
More Queries. A queries encryption of other keyword sets and tokens that A has not asked before. B responds in the same way as in Step (2) and Step (3). The restriction is that A cannot issue the aforementioned queries for location t.(6)
Guess. At the end, A outputs the guess b′∈0,1. If b′=1 and B outputs “Yes,” then (aP,bP,cP) is considered as a DDH tuple. Thus, for z = t, we can prove that (aP,bP,cP) is a DDH tuple as follows.We know from (3) that(7)eτ1,T2=eτ2,C2.This can be represented as(8)eτ1,T2=ebr1τzP+Kz,t1P=eP,Pbr1τz+Kzt1,eτ2,C2=et1H1wz+kzP,r1P=eP,Pr1H1wz+kzt1.From (8), we get(9)eP,Pbr1τz+Kzt1=eP,Pr1H1wz+kzt1.Now, from the challenge ciphertext,(10)eτ1,T2=ecτtP+Kt,t1P=eP,Pcτt+Ktt1,eτ2,C2=et1H1wt+ktP,aP=eP,PaH1wt+ktt1.From (10), we get(11)eP,Pcτt+Ktt1=eP,PaH1wt+ktt1.Now, from (9) and (11)(12)eP,Pbr1τz+Kzt1eP,Pr1H1wz+kzt1=eP,Pcτt+Ktt1eP,PaH1wt+ktt1∴eP,Pbr1τz+Kzt1eP,PaH1wt+ktt1=eP,Pcτt+Ktt1eP,Pr1H1wz+kzt1∴eP,Pabr1τz+Kzt1eP,PH1wz+kzt1=eP,Pcr1τz+Kzt1eP,PH1wz+kzt1eP,Pabr1τz+Kzt1=eP,Pcr1τz+Kzt1eP,abP=eP,cPab=c.On the other hand, ifb′=0, we cannot prove that the challenge (cP,bP,cP) is a DDH tuple, since encryption at position j is random and it cannot confirm (12). However, the advantage of A to win the game ICLR is same as that of the B which solves the DDH challenge.Now, the following are the two simulations ofB’s advantages.
(i)
S1: B responds to the search token queries for n keyword issued by A.(ii)
S2: B is not aborted in the challenge phase.For large enoughqk, the probability of S1 and S2 can be defined as(13)Pr⁡S1=1en,Pr⁡S2=1qkn.Thus, theB’s advantage ϵ′ in solving the DDH problem is ϵ′=ϵ·Pr[S1∩S2]≥ϵ/enqkn.
According to Propositions1 and 2 of [26], if there exists an adversary with nonnegligible advantage to win ICC game, then there exists another adversary with a nonnegligible advantage to win the ICLR game. However, as per the above proof, the advantage of B is ϵ/enqkn∈[0,1/2enqkn] which is negligible. Thus, the proposed MUSE-TFV scheme is at least (1-1/2enqkn) secure under the ICLR game if DDH assumption is intractable. This completes the proof for Theorem 2.Theorem 3.
The proposed MUSE-TFV provides security against token replay attack.Proof.
Let us assume a DU as an adversaryA can perform a token replay attack as follows.(1)
An adversaryA maliciously captures a valid token T=(T′,c=EY(TVK1)) and stores it.(2)
To reuse the tokenT, an adversary A replaces its verification key part, that is, c=EY(TVK1), with c′ in such a way that the further execution ofTokVer() (at the site of SS) outputs “1” and so the SS returns a result R.
IfCsize is the size of a ciphertext generated by an encryption algorithm E, then an adversary A required 2Csize attempts to forge a value “c.” With any standard secure algorithm (i.e., 160-bit ECEL (ECC based Elgamal Encryption) (as public key Y of SS is an element from a group of points of an elliptic curve, any ECC based encryption algorithm must be used)), the probability of an adversary A to guess a valid (c′=c) is 1/(2160).Additionally, the adversaryA is completely unaware about the other verification key TVK2 available at the site of the SS. Thus, a token with the replaced verification key, that is, T=T′,c′, must be issued to the SS to check the output of TokVer(TVK1,TVK2) algorithm. Denoting CC as a communication cost (from a DU to SS) of a single message, we find O(CC·2160) communication complexity in the system for 2160 attempts potentially performed by an adversary A to forge a value of c.However, with a communication link of 100 Mbps and a Maximum Transmission Unit (MTU) of 1500 bytes (Ethernet), it requires about57·1030 years to attempt all the possible values of c. Thus, for any adversary A, the probability of getting the result R by forging the value c is negligible.
Thus, we say that the proposed scheme MUSE-TFV is secure against token replay attack.


## 4.1. Formal Construction

The concrete constructions for the proposed algorithms are as follows.(1)
Setup(α,n). Let G1 and G2 be bilinear groups of prime order p where a security parameter α defines the group size. Let e:G1×G1→G2 be a bilinear pairing and H1:0,1∗→Zp∗ is a hash function. Let H:0,1∗→0,1b be any standard hash function (e.g., SHA2) that outputs a message digest of b bits. Let P be a generator of G1. The algorithm initializes the keyword space KS of total n keywords. For each jth keyword, it randomly selects kj∈Zp∗ and computes Kj=kjP. Finally, the algorithm sets the public parameter pp=H1,H,G1,G2,P,e,Kj1≤j≤n and a master secret key msk = kj1≤j≤n.(2)
SKeyGen(pp). The algorithm selects a random y∈Zp∗ and computes Y=yP. It sets the public-private key pair for the server SS as (Y,y).(3)
UKeyGen(pp). The algorithm selects a random x∈Zp∗ and computes X=xP. It sets the public-private key pair for the user DU as (X,x).(4)
Encryption(pp,W,Y,M′). The algorithm takes as input a list of keywords W=w1,w2,…,wn. It chooses a random r1∈Zp∗ and constructs a ciphertext C′=C1j,C21≤j≤n, where C1j=r1(H1(wj)P+Kj)+r1Y, C2=r1P. Finally, it outputs a ciphertext C=C′,M′, where M′ is an encrypted payload.(5)
TokGen(pp,msk,Q,X,x,Y). This interactive algorithm works in 3 phases.
(a)
A DU sends a conjunctive queryQ=W′,I′ to the ETA where W′=w1′,w2′,…,wt′ is a set of keywords and I′=I1,I2,…,It is a set of positions of keywords in KS.(b)
In response, the ETA chooses a unique token identification stringTokID∈0,1l and a secret random integer N. The ETA uses TokVerKey(TokID,N,H())→(TVK1,TVK2) algorithm to construct the token verification keys. The ETA selects t1∈Zp∗ randomly. It uses msk and X to construct a token component PT′=PT1,PT2, where PT1=t1(∑j=I1It‍(H1(wj)+kj))P+t1X, PT2=t1P. At last, the ETA sends a partial token PT=(PT′,EY(TVK1)) to the DU. At the same time, it forwards (EY(TVK2)) to the SS.(c)
The DU selects a random elementa′∈Zp∗. Using x and Y, the DU computes T′=T1,T2,T3,T4 as follows:T1=τ+a′Y, T2=PT2=t1P, T3=a′P, T4=I′ Where τ=PT1-xPT2=t1(∑j=I1It‍(H1(wj)+kj))P.Finally, the algorithm outputs a tokenT=(T′,EY(TVK1)).(6)
Search(C,T,y). The algorithm applies Dy(EY(TVK1)) and Dy(EY(TVK2)) to get the original verification key (TVK1,TVK2) from the encrypted values using a private key y of the SS. The algorithm then calls TokVer(TVK1, TVK2) to verify the freshness of the input token T. If a token is fresh (i.e., TokVer(·)→1), it applies T′ of T on an available ciphertext C′ from C as follows.The algorithm computes(2)τ1=∑j=I1ItC1j-yC2=∑j=I1Itr1H1wjP+Kj+r1Y-yr1P=r1∑j=I1ItH1wjP+Kj,τ2=T1-yT3=t1∑j=I1ItH1wj+kjP+a′Y-ya′P=t1∑j=I1ItH1wj+kjP.Then, it checks the following correctness:(3)eτ1,T2=eτ2,C2.If (3) is satisfied, then the algorithm outputs the associated payload message M′; as a result R=Ey(EX(M′)). Here, encryption with a public key X of DU provides confidentiality and signature with the private key y of SS maintains integrity of a result R during transit. The algorithm repeatedly applies T′ on each available ciphertext at the server SS. At last, the algorithm updates the current entry of TVK2 in the system table with TUpdate(TVK2,TVK1).Note. (i) The algorithms TokVerKey(), TokVer(), and TUpdate() are described in Section 4.2. (ii) The query Q from a DU to the ETA is in plaintext format. It does not impact the security of token as even if any unauthorized DU maliciously captures a partial token, he is unable to construct a final token unless having secret key x. (iii) The E/D for the verification keys is any standard encryption/decryption cipher. The encryption of the verification keys with the public key Y of SS prevents their modification by a malicious DU.Correctness. LHS of (3):(4)eτ1,T2=er1∑j=I1ItH1wjP+Kj,t1P=e∑j=I1ItH1wjP+Kj,Pr1t1=e∑j=I1ItH1wjP+kjP,Pr1t1=eP,Pr1t1Δ.RHS of (3):(5)eτ2,C2=et1∑j=I1ItH1wj+kjP,r1P=eP,Pr1t1Δ.Here, Δ=∑j=I1It‍(H1(wj)+kj). From (4) and (5), the correctness is proved.


## 4.2. Token Verification Procedure

To define a token verification procedure, we borrow the idea from Haller’s S/Key One-Time Password System [34]. The S/Key scheme provides a technique to construct a one-time password at the client site and its verification at the host site. The scheme works on 3 parameters (s,RN,H()), where s is a secret string, RN represents the number of times the hash is applied on s, and H() is any standard cryptographic hash function. We adopt similar parameters to define a token verification procedure for the proposed MUSE-TFV. The token freshness verification involves three algorithms:(1)
TokVerKey(s,RN,H()): thetoken verification key generation algorithm outputs two keys (K1,K2), where K1=HRN(s) and K2=HRN-1(s).(2)
TokVer(K1,K2): thetoken verification algorithm verifies the freshness of a token by checking K1=H(K2). If condition is true, the algorithm outputs “1” otherwise “0.”(3)
TUpdate(K1,K2): thetoken update algorithm updates the current memory location of K1 with K2; that is, it performs K1=K2.The original S/Key mechanism is defined with the traditional hash function, that is, MD4. For MUSE-TFV, we prefer SHA-2 to avoid collision attack.


## 4.3. Security Analysis

We analyze the semantic security of MUSE-TFV against chosen keyword attack (IND-CKA) under DDH assumption. Additionally, we prove that the proposed MUSE-TFV provides security against token replay attack.Theorem 2.
The proposed MUSE-TFV is semantically secure against a server SS as an adversary according to the game ICLR, assuming DDH is intractable.Proof.
Let us assume a server SS as an adversaryA can attack the proposed scheme in a polynomial time. Suppose A makes at most qk token queries where qk<p and has the advantage ϵ in solving DDH problem in G1. Let G1 and G2 be two groups of prime order p and P be the generator of G1. We build a simulator B as a challenger that has the advantage ϵ′=ϵ/enqkn to simulate the game where e is base of natural logarithm.
Suppose an instance(aP,bP,cP) of the DDH problem in G1 is the B’s challenge information where a,b,c∈Zp∗. The goal of B is to distinguish cP=abP from random element in G1. One restriction is that the random element z is independent of the location t selected in ICLR game; then the simulation game is demonstrated as follows.(1)
Setup. An adversary A randomly selects y∈Zp∗ and computes Y=yP. A then defines a public-private key pair (Y,y). Let (X=xP,x) be the B’s public-private key pair.(2)
Encryption Queries. An adversary A issues the queries for the ciphertext of the keyword set Wi=wi1,wi2,…,win. In response, challenger B simulatesEncryption(pp,Wi,Y) as follows.
(i)
B selects γj∈Zp∗ for each keyword wij∈Wi, where 1≤j≤n.(ii)
B chooses a random value r1i∈Zp∗ and constructs a ciphertext Ci = {(C1j)i,(C2)i}1≤j≤n, where(6)C11i=r1iγ1P+K1+r1iYC12i=r1iγ2P+K2+r1iY⋮C1zi=br1iγzP+Kz+r1iY⋮C1ni=r1iγnP+Kn+r1iYC2i=r1iP.(3)
Token Queries. To evaluateSearch() algorithm, A issues the token queries by sending Qi=(Wi′,Ii′), where Wi′={wiI1′,wiI2′,…,wiIt′} and Ii′=I1,I2,…,It to B. B takes a partial token PT′=PT1,PT2 from the ETA where PT1=t1(∑j=I1It‍(H1(wj)+kj))P+t1X, PT2=t1P. B then selects a random a′∈Zp∗ and computes final token Ti=T1i,T2i,T3i,T4i as follows.T1i=τ+a′Y, T2i=t1P, T3i=a′P, T4i=I′, where τ=PT1-xPT2=t1(∑j=I1It‍(H1(wj)+kj))P.At last,B sends this token Ti to A.(4)
Challenge. A issues a tuple (Wi,T,t) to B where T⊆1,n and t∈T.Ifz≠t, B sends a random guess as the response to the DDH challenge.Ifz=t, B responses are as follows.
(a)
It first setsht=c(γtP+Kt)+cY.(b)
It setsh1j=lj, for j≠t, j∈T, where lj∈Zp∗.(c)
It setsh1j=a(γjP+Kj)+aY, for j≠t, j∉T.(d)
It setsh2=aP.Finally,B sends h1j,h2 for 1≤j≤n as challenge ciphertext to A.Ifz=t, then B wins the security game. The ciphertext for every position j∉T is the encryption of W and ciphertext in position t where c=ab is also an encryption of W. Otherwise, for other position, it is not.(5)
More Queries. A queries encryption of other keyword sets and tokens that A has not asked before. B responds in the same way as in Step (2) and Step (3). The restriction is that A cannot issue the aforementioned queries for location t.(6)
Guess. At the end, A outputs the guess b′∈0,1. If b′=1 and B outputs “Yes,” then (aP,bP,cP) is considered as a DDH tuple. Thus, for z = t, we can prove that (aP,bP,cP) is a DDH tuple as follows.We know from (3) that(7)eτ1,T2=eτ2,C2.This can be represented as(8)eτ1,T2=ebr1τzP+Kz,t1P=eP,Pbr1τz+Kzt1,eτ2,C2=et1H1wz+kzP,r1P=eP,Pr1H1wz+kzt1.From (8), we get(9)eP,Pbr1τz+Kzt1=eP,Pr1H1wz+kzt1.Now, from the challenge ciphertext,(10)eτ1,T2=ecτtP+Kt,t1P=eP,Pcτt+Ktt1,eτ2,C2=et1H1wt+ktP,aP=eP,PaH1wt+ktt1.From (10), we get(11)eP,Pcτt+Ktt1=eP,PaH1wt+ktt1.Now, from (9) and (11)(12)eP,Pbr1τz+Kzt1eP,Pr1H1wz+kzt1=eP,Pcτt+Ktt1eP,PaH1wt+ktt1∴eP,Pbr1τz+Kzt1eP,PaH1wt+ktt1=eP,Pcτt+Ktt1eP,Pr1H1wz+kzt1∴eP,Pabr1τz+Kzt1eP,PH1wz+kzt1=eP,Pcr1τz+Kzt1eP,PH1wz+kzt1eP,Pabr1τz+Kzt1=eP,Pcr1τz+Kzt1eP,abP=eP,cPab=c.On the other hand, ifb′=0, we cannot prove that the challenge (cP,bP,cP) is a DDH tuple, since encryption at position j is random and it cannot confirm (12). However, the advantage of A to win the game ICLR is same as that of the B which solves the DDH challenge.Now, the following are the two simulations ofB’s advantages.
(i)
S1: B responds to the search token queries for n keyword issued by A.(ii)
S2: B is not aborted in the challenge phase.For large enoughqk, the probability of S1 and S2 can be defined as(13)Pr⁡S1=1en,Pr⁡S2=1qkn.Thus, theB’s advantage ϵ′ in solving the DDH problem is ϵ′=ϵ·Pr[S1∩S2]≥ϵ/enqkn.
According to Propositions1 and 2 of [26], if there exists an adversary with nonnegligible advantage to win ICC game, then there exists another adversary with a nonnegligible advantage to win the ICLR game. However, as per the above proof, the advantage of B is ϵ/enqkn∈[0,1/2enqkn] which is negligible. Thus, the proposed MUSE-TFV scheme is at least (1-1/2enqkn) secure under the ICLR game if DDH assumption is intractable. This completes the proof for Theorem 2.Theorem 3.
The proposed MUSE-TFV provides security against token replay attack.Proof.
Let us assume a DU as an adversaryA can perform a token replay attack as follows.(1)
An adversaryA maliciously captures a valid token T=(T′,c=EY(TVK1)) and stores it.(2)
To reuse the tokenT, an adversary A replaces its verification key part, that is, c=EY(TVK1), with c′ in such a way that the further execution ofTokVer() (at the site of SS) outputs “1” and so the SS returns a result R.
IfCsize is the size of a ciphertext generated by an encryption algorithm E, then an adversary A required 2Csize attempts to forge a value “c.” With any standard secure algorithm (i.e., 160-bit ECEL (ECC based Elgamal Encryption) (as public key Y of SS is an element from a group of points of an elliptic curve, any ECC based encryption algorithm must be used)), the probability of an adversary A to guess a valid (c′=c) is 1/(2160).Additionally, the adversaryA is completely unaware about the other verification key TVK2 available at the site of the SS. Thus, a token with the replaced verification key, that is, T=T′,c′, must be issued to the SS to check the output of TokVer(TVK1,TVK2) algorithm. Denoting CC as a communication cost (from a DU to SS) of a single message, we find O(CC·2160) communication complexity in the system for 2160 attempts potentially performed by an adversary A to forge a value of c.However, with a communication link of 100 Mbps and a Maximum Transmission Unit (MTU) of 1500 bytes (Ethernet), it requires about57·1030 years to attempt all the possible values of c. Thus, for any adversary A, the probability of getting the result R by forging the value c is negligible.
Thus, we say that the proposed scheme MUSE-TFV is secure against token replay attack.


## 5. Theoretical Analysis and Empirical Evaluation

In this section, we first present theoretical analysis of the proposed MUSE-TFV. Subsequently, we show the performance efficiency of MUSE-TFV with a detailed empirical evaluation.


### 5.1. Theoretical Analysis

We highlight the significant characteristics of MUSE-TFV in comparison with the existing multiuser searchable schemes [9, 17–19] and conjunctive search schemes [21–23] in Table 1. As the other multiuser searchable schemes [10, 11, 13, 16] utilize inverted index search structure (in inverted index based Searchable Encryption, a single common index (list of keywords) is defined for the entire set of encrypted documents), their comparison with the simple index based MUSE-TFV (in simple index searchable scheme, a separate index of keywords is associated with each encrypted document) is inapplicable here.Table 1
Comparative analysis: significant characteristics.
Schemes
MU
MKC
MKQ
SCF
TFV
Hwang and Lee 2007 [9]
✓
✓
✓
×
×
Kiayias et al. 2016 [17]
✓
×
×
×
×
Zhang et al. 2016 [18]
✓
✓
×
×
×
Wang et al. 2016 [19]
✓
×
×
×
×
B. Zhang and F. Zhang 2011 [21]
×
✓
✓
×
×
Ding et al. 2012 [22]
×
✓
✓
✓
×
Chen et al. 2012 [23]
×
✓
✓
×
×
MUSE-TFV
✓
✓
✓
✓
✓
MU: multiuser support, MKC: multiple keywords in ciphertext, MKQ: multiple keywords in query, SCF: secure channel-free architecture, and TFV: token freshness verification.From Table1, we observe that no scheme amongst the listed multiuser schemes provides a secure channel-free architecture for a token transmission. On the other hand, a conjunctive search scheme discussed in [22] offers such architecture, but it does not support multiple users in the system. In contrast, the proposed MUSE-TFV provides a conjunctive keyword based search with secure channel-free token transmission in multiuser settings. Additionally, MUSE-TFV has provision to verify the freshness of token to prevent token replay attack.We compare the performance of MUSE-TFV with the existing schemes in terms of the storage overhead (i.e., size of a ciphertext (excluding payload) and size of a token) and computational overhead (for the proposedEncryption(),TokGen(), andSearch() algorithms) in Table 2.Table 2
Comparative analysis: storage-computational complexity.
Schemes
Storage overhead
Computational overhead
Ciphertext
Token
Encryption()
TokGen()
Search()
Hwang and Lee 2007 [9]
(
n
+
u
)
G
1
3
G
1
(
2
+
2
n
+
u
)
E
+
P
2
t
M
′
+
3
E
t
M
′
+
3
P
Kiayias et al. 2016 [17]
10
G
1
5
G
1
22
E
+
4
+
2
u
k
M
′
+
2
P
8
M
′
+
13
E
1
+
u
k
M
′
+
3
P
Zhang et al. 2016 [18]
n
H
G
1
2
E
+
(
1
+
n
)
P
1
E
E
+
2
P
+
U
Wang et al. 2016 [19]
(
q
+
C
)
n
1
H
2
n
E
+
2
n
P
1
E
1
P
+
n
D
B. Zhang and F. Zhang 2011 [21]
(
1
+
n
)
G
1
+
G
2
(
2
+
t
)
G
1
(
2
+
2
n
)
E
+
P
(
2
+
3
t
)
E
(
1
+
2
t
)
P
Ding et al. 2012 [22]
(
1
+
n
)
G
1
G
1
(
2
+
2
n
)
M
M
+
E
3
M
+
2
P
Chen et al. 2012 [23]
5
G
1
4
G
2
(
4
+
n
)
E
4
E
4
P
MUSE-TFV
(
1
+
n
)
G
1
3
G
1
+
V
(
2
+
2
n
)
M
6
M
2
M
+
2
P
n: number of keywords in the system, t: number of keywords in a query, u: number of users in the system, uk: number of users accessing an associated file, H: size of a message digest output by the used hash function, (G1,G2): size of an element from bilinear groups G1 and G2, V: ciphertext size of the used encryption routine, q: size of a random integer, P: pairing, E: exponentiation, M: scalar multiplication, M′: modular multiplication, D: data comparison, and U: set union operation.


#### 5.1.1. Storage Complexity

To show the storage overhead, we present the ciphertext/token size in terms of the size of an element from the bilinear groups (G1,G2). Observing Table 2, we say that the constructions given in [17, 23] are storage efficient with the constant ciphertext and token size (i.e., O(1)). In contrast, the proposed MUSE-TFV has a ciphertext size linear to the number of keywords in the system (i.e., (O(n)) that is same as ciphertext storage complexity of the existing schemes [18, 19, 21, 22].The significant characteristic of MUSE-TFV is its constant (i.e.,O(1)) token storage complexity. This constant overhead makes the proposed scheme as efficient as the existing schemes [9, 17, 18, 22]. In fact, the actual token size for the MUSE-TFV is three times higher than the token constructed by the schemes [18, 22]. However, with such increased token size, we offer a secure token transmission over any public channel without channel setup overhead. Moreover, with an added component V to the token (where V is the size of a ciphertext for an encrypted verification key TVK1), we prevent the token replay attack.


#### 5.1.2. Computational Complexity

We present the computational overhead in terms of the major operations, namely, modular multiplication (M′), scalar multiplication (M), exponentiation (E), and pairing (P) involved in the listed schemes. From our experiments, we observe that a scalar multiplication, an exponentiation, and a pairing operation are costlier (involving more CPU cycles) than a modular multiplication operation. Therefore, from Table 2, we say that the computational cost of the proposedEncryption() algorithm (i.e., (2+2n)M) is almost same as the encryption cost of the listed multikeyword schemes [9, 21, 22]. We note that this encryption overhead is double as compared to the encryption overhead involved in the schemes [18, 23].On the other hand, similar to the scheme in [18], MUSE-TFV has a constant computational complexity, i.e., (O(n)) (independent of the number of users u), forEncryption() algorithm. Such computational cost is far more better than the existing schemes [9, 17] with O(n+u) and O(uk) encryption overhead, respectively. Therefore, we say that with moderate computational overhead for the proposedEncryption() algorithm MUSE-TFV supports multiple keyword based search as well as multiple users in the system.From Table2, we observe that the computational complexity of the proposedTokGen() algorithm of MUSE-TFV is same as the token construction cost of the existing schemes [18, 22, 23], i.e., O(1). With such constant computational overhead, MUSE-TFV performs better than the existing schemes [9, 21] having O(t) token construction overhead. Additionally, we note thatTokGen() algorithm of MUSE-TFV consumes more CPU cycles as compared to the Token Generation algorithm of the schemes [18, 22, 23] due to its interactive token construction steps. However, with such added overhead, MUSE-TFV supports multiple users in the system.We also note that the computational cost of aSearch() algorithm of MUSE-TFV (i.e., (2M+2P)) is almost same as the existing schemes [18, 22, 23]. This constant search complexity (i.e., O(1)) is better than the search complexity (i.e., O(t)) involved in [9, 21]. Moreover, as a multiuser scheme, the MUSE-TFV offers constant computational cost O(1) (i.e., independent from u) during search phase. This cost is much more better than the search computational overhead (i.e., O(uk)) involved in the scheme [17]. It is worth noting that, with similar search complexity as the existing schemes [18, 22, 23], the proposed MUSE-TFV provides an additional token freshness verification feature.


#### 5.1.3. Communication Complexity

In Table3, we present the communication complexity of the proposed MUSE-TFV duringData Upload,Token Generation, andSearch phases, as compared to the existing multiuser schemes [9, 17–19]. We note that, with S as a message, a scheme in [19] suffers with the highest communication overhead (i.e., 3cS for c ciphertexts) duringData Upload phase wherein uploading of a single ciphertext involves three messages (i.e., a preindex message from a Data Owner to the server, an index parameter message from the server to the Data Owner, and a ciphertext message from the Data Owner to the server). In contrast, the proposed MUSE-TFV has an optimal communication overhead of a single message per ciphertext (i.e., cS messages for c ciphertexts) from a Data Owner to the server. With such overhead, the proposed scheme performs similar to the existing schemes discussed in [9, 17, 18].Table 3
Comparative analysis: communication complexity.
Schemes
Data Upload
Token Generation
Search
Hwang and Lee 2007 [9]
c
S
—
(
1
+
c
)
S
Kiayias et al. 2016 [17]
c
S
—
(
3
+
c
)
S
Zhang et al. 2016 [18]
c
S
—
2
S
Wang et al. 2016 [19]
3
c
S
—
(
1
+
c
)
S
MUSE-TFV
c
S
2
q
S
(
1
+
c
)
S
S: a message, c: number of ciphertexts available at the server, and q: number of queries.A scheme in [17] uses two servers (Smain and Said) to perform a search operation where a communication overhead is (3+c)S messages (i.e., a token message from a user to Smain, a token message from a user to Said, an additional message from Said to Smain, and c result messages from Smain to the requesting user). In contrast, the proposed MUSE-TFV involves (1+c)S messages (i.e., a token message from a user to the Storage Server and c result messages from the server to the user) duringSearch phase. The scheme of [18] has the lowest communication overhead during search operation, that is, 2S (a token message from a user to the server and a result message from the server to the user). However, in the scheme [18], the server suffers with the additional computational overhead (for set union operations) in order to incorporate c result messages into a single message.Table3 shows that theToken Generation phase of the proposed MUSE-TFV suffers with the communication overhead of 2qS for q queries. This overhead is due to the interactive Token Generation algorithm that involves two message exchanges between a DU and the ETA, that is, a Token Request message from a DU and a response message from the ETA. However, with such added communication overhead, we achieve a more secure system wherein every Token Generation activity is logged at the trusted site and thus any dishonest activity from a DU can easily be tracked. Moreover, with such interactive Token Generation algorithm, the proposed scheme provides a token freshness verification to prevent a token replay attack. Thus, MUSE-TFV is indeed an effective multiuser scheme for the applications where security of each search activity is a prime requirement.


### 5.2. Empirical Evaluation

To evaluate the performance, we conduct the experiments on 32-bit, 2.10 GHz Pentium Core 2 Duo CPU with Windows 7 machine using Java Pairing based Cryptographic (JPBC) Library [42]. From JPBC Library, we utilize Type A pairing (i.e., G1×G1→G2) which is based on an elliptic curve E(Fq):y2=x3+x. Here, the group G1 is a subgroup of E(Fq), and the cyclic group G2 is a subgroup of E(Fq)2 where q is a large prime number. The group order of G1 is 160 bits, and the base field is 512 bits.To systematically compare the performance of the MUSE-TFV with other schemes, we consider three significant parameters, that is, (i) number of keywords in the system (n), (ii) number of keywords in a query (t), and (iii) number of users in the system (u) (Table 4). We perform experiments for different size systems with n∈50,100,150,200,250,300. For each system, we simulate theEncryption(),TokGen(), andSearch() algorithms multiple times and consider their average results. To show the efficiency of MUSE-TFV as a multiuser scheme, we consider a different number of users, that is, u∈1000,2000,3000,4000,5000 in the system. Additionally, during Token Generation experiments, we select the conjunctive queries with the variable number of keywords, that is, t∈10,20,30,40,50. As a large number of keywords in conjunction make a query complex and impractical, we select comparatively small values for t.Table 4
Simulation parameters.
Parameters
Values for simulation
n
50,100,150,200,250,300
u
1000,2000,3000,4000,5000
t
10,20,30,40,50From Table2, we identify that the computational cost ofEncryption() algorithms for all multikeyword schemes(MKC) [21–23] depends upon n whereas for all multiuser schemes [9, 17, 18], it depends upon n, or u or uk. Thus, we simulateEncryption() algorithms for all the listed schemes with different values of n and u separately and show their responses in Figures 5(a) and 5(b), respectively. Note that for simulation purpose we consider the worst case scenario for a scheme [17], where uk=u.Figure 5
Simulation results forEncryption() algorithm.
(a)
(b)From the results in Figure5(a), we note that the encryption time of the proposed MUSE-TFV is linearly increasing with the number of keywords (i.e., n). However, this time overhead is same as the encryption time overhead of [9, 21, 22] but larger than the overhead involved in [18, 23]. Additionally, from Figure 5(b), we observe that the existence of multiple users in the system does not affect the time consumption of encryption algorithm of MUSE-TFV. This characteristic makes the MUSE-TFV more practical than the existing multiuser schemes [9, 17] where the encryption time overhead is linearly increasing with the number of users. Here, we say that with the constant encryption overhead (i.e., independent of the number of users (u)) theEncryption() algorithm of MUSE-TFV supports multiple keywords in a ciphertext and multiple users in the system.We present the empirical results forTokGen() algorithm of MUSE-TFV and other multikeyword (MKQ) schemes in Figure 6. From these results, we say that the MUSE-TFV takes almost constant time to construct a token regardless of the number of keywords in a query. With this characteristic, MUSE-TFV resembles the schemes [22, 23] and performs better than the other multikeyword schemes [9, 21] having O(t) token computational overhead. However, MUSE-TFV takes more time as compared to [22, 23] because of its interactive nature.Figure 6
Simulation results forTokGen() algorithm.According to Table2, the computational overhead for theSearch() algorithm of the listed schemes is either constant or otherwise depending upon t or uk. Thus, we simulate the listed schemes for theirSearch() algorithm with different values of t and u separately and show their responses in Figures 7(a) and 7(b), respectively.Figure 7
Simulation results forSearch() algorithm.
(a)
(b)Observing the results in Figure7(a), we note that the search time overhead for MUSE-TFV is almost constant and independent of the number of keywords in a query (t). With this characteristic, the MUSE-TFV performs a conjunctive search with much less computational time as compared to the existing conjunctive search schemes [9, 21] where the search time is affected by the number of keywords in query (t). From the results in Figure 7(b), we note that, with constant search time overhead, the proposed MUSE-TFV supports multiple users in the system as efficiently as the scheme [18]. In addition, we say that with the search time linear to the number of users (u) the scheme of [17] is indeed less practical. In contrast, with the constant search time overhead, the MUSE-TFV performs a conjunctive keyword search in response to a query coming from any user in the multiuser settings.At last we claim that our empirical results are completely in accordance with the theoretically measured computational complexity presented in Table2. From the theoretical analysis and empirical evaluation, we conclude that, with the moderate storage-computational overhead, the proposed MUSE-TFV is an elegant multiuser searchable scheme with a provision of conjunctive keyword search and token freshness verification.


## 5.1. Theoretical Analysis

We highlight the significant characteristics of MUSE-TFV in comparison with the existing multiuser searchable schemes [9, 17–19] and conjunctive search schemes [21–23] in Table 1. As the other multiuser searchable schemes [10, 11, 13, 16] utilize inverted index search structure (in inverted index based Searchable Encryption, a single common index (list of keywords) is defined for the entire set of encrypted documents), their comparison with the simple index based MUSE-TFV (in simple index searchable scheme, a separate index of keywords is associated with each encrypted document) is inapplicable here.Table 1
Comparative analysis: significant characteristics.
Schemes
MU
MKC
MKQ
SCF
TFV
Hwang and Lee 2007 [9]
✓
✓
✓
×
×
Kiayias et al. 2016 [17]
✓
×
×
×
×
Zhang et al. 2016 [18]
✓
✓
×
×
×
Wang et al. 2016 [19]
✓
×
×
×
×
B. Zhang and F. Zhang 2011 [21]
×
✓
✓
×
×
Ding et al. 2012 [22]
×
✓
✓
✓
×
Chen et al. 2012 [23]
×
✓
✓
×
×
MUSE-TFV
✓
✓
✓
✓
✓
MU: multiuser support, MKC: multiple keywords in ciphertext, MKQ: multiple keywords in query, SCF: secure channel-free architecture, and TFV: token freshness verification.From Table1, we observe that no scheme amongst the listed multiuser schemes provides a secure channel-free architecture for a token transmission. On the other hand, a conjunctive search scheme discussed in [22] offers such architecture, but it does not support multiple users in the system. In contrast, the proposed MUSE-TFV provides a conjunctive keyword based search with secure channel-free token transmission in multiuser settings. Additionally, MUSE-TFV has provision to verify the freshness of token to prevent token replay attack.We compare the performance of MUSE-TFV with the existing schemes in terms of the storage overhead (i.e., size of a ciphertext (excluding payload) and size of a token) and computational overhead (for the proposedEncryption(),TokGen(), andSearch() algorithms) in Table 2.Table 2
Comparative analysis: storage-computational complexity.
Schemes
Storage overhead
Computational overhead
Ciphertext
Token
Encryption()
TokGen()
Search()
Hwang and Lee 2007 [9]
(
n
+
u
)
G
1
3
G
1
(
2
+
2
n
+
u
)
E
+
P
2
t
M
′
+
3
E
t
M
′
+
3
P
Kiayias et al. 2016 [17]
10
G
1
5
G
1
22
E
+
4
+
2
u
k
M
′
+
2
P
8
M
′
+
13
E
1
+
u
k
M
′
+
3
P
Zhang et al. 2016 [18]
n
H
G
1
2
E
+
(
1
+
n
)
P
1
E
E
+
2
P
+
U
Wang et al. 2016 [19]
(
q
+
C
)
n
1
H
2
n
E
+
2
n
P
1
E
1
P
+
n
D
B. Zhang and F. Zhang 2011 [21]
(
1
+
n
)
G
1
+
G
2
(
2
+
t
)
G
1
(
2
+
2
n
)
E
+
P
(
2
+
3
t
)
E
(
1
+
2
t
)
P
Ding et al. 2012 [22]
(
1
+
n
)
G
1
G
1
(
2
+
2
n
)
M
M
+
E
3
M
+
2
P
Chen et al. 2012 [23]
5
G
1
4
G
2
(
4
+
n
)
E
4
E
4
P
MUSE-TFV
(
1
+
n
)
G
1
3
G
1
+
V
(
2
+
2
n
)
M
6
M
2
M
+
2
P
n: number of keywords in the system, t: number of keywords in a query, u: number of users in the system, uk: number of users accessing an associated file, H: size of a message digest output by the used hash function, (G1,G2): size of an element from bilinear groups G1 and G2, V: ciphertext size of the used encryption routine, q: size of a random integer, P: pairing, E: exponentiation, M: scalar multiplication, M′: modular multiplication, D: data comparison, and U: set union operation.


### 5.1.1. Storage Complexity

To show the storage overhead, we present the ciphertext/token size in terms of the size of an element from the bilinear groups (G1,G2). Observing Table 2, we say that the constructions given in [17, 23] are storage efficient with the constant ciphertext and token size (i.e., O(1)). In contrast, the proposed MUSE-TFV has a ciphertext size linear to the number of keywords in the system (i.e., (O(n)) that is same as ciphertext storage complexity of the existing schemes [18, 19, 21, 22].The significant characteristic of MUSE-TFV is its constant (i.e.,O(1)) token storage complexity. This constant overhead makes the proposed scheme as efficient as the existing schemes [9, 17, 18, 22]. In fact, the actual token size for the MUSE-TFV is three times higher than the token constructed by the schemes [18, 22]. However, with such increased token size, we offer a secure token transmission over any public channel without channel setup overhead. Moreover, with an added component V to the token (where V is the size of a ciphertext for an encrypted verification key TVK1), we prevent the token replay attack.


### 5.1.2. Computational Complexity

We present the computational overhead in terms of the major operations, namely, modular multiplication (M′), scalar multiplication (M), exponentiation (E), and pairing (P) involved in the listed schemes. From our experiments, we observe that a scalar multiplication, an exponentiation, and a pairing operation are costlier (involving more CPU cycles) than a modular multiplication operation. Therefore, from Table 2, we say that the computational cost of the proposedEncryption() algorithm (i.e., (2+2n)M) is almost same as the encryption cost of the listed multikeyword schemes [9, 21, 22]. We note that this encryption overhead is double as compared to the encryption overhead involved in the schemes [18, 23].On the other hand, similar to the scheme in [18], MUSE-TFV has a constant computational complexity, i.e., (O(n)) (independent of the number of users u), forEncryption() algorithm. Such computational cost is far more better than the existing schemes [9, 17] with O(n+u) and O(uk) encryption overhead, respectively. Therefore, we say that with moderate computational overhead for the proposedEncryption() algorithm MUSE-TFV supports multiple keyword based search as well as multiple users in the system.From Table2, we observe that the computational complexity of the proposedTokGen() algorithm of MUSE-TFV is same as the token construction cost of the existing schemes [18, 22, 23], i.e., O(1). With such constant computational overhead, MUSE-TFV performs better than the existing schemes [9, 21] having O(t) token construction overhead. Additionally, we note thatTokGen() algorithm of MUSE-TFV consumes more CPU cycles as compared to the Token Generation algorithm of the schemes [18, 22, 23] due to its interactive token construction steps. However, with such added overhead, MUSE-TFV supports multiple users in the system.We also note that the computational cost of aSearch() algorithm of MUSE-TFV (i.e., (2M+2P)) is almost same as the existing schemes [18, 22, 23]. This constant search complexity (i.e., O(1)) is better than the search complexity (i.e., O(t)) involved in [9, 21]. Moreover, as a multiuser scheme, the MUSE-TFV offers constant computational cost O(1) (i.e., independent from u) during search phase. This cost is much more better than the search computational overhead (i.e., O(uk)) involved in the scheme [17]. It is worth noting that, with similar search complexity as the existing schemes [18, 22, 23], the proposed MUSE-TFV provides an additional token freshness verification feature.


### 5.1.3. Communication Complexity

In Table3, we present the communication complexity of the proposed MUSE-TFV duringData Upload,Token Generation, andSearch phases, as compared to the existing multiuser schemes [9, 17–19]. We note that, with S as a message, a scheme in [19] suffers with the highest communication overhead (i.e., 3cS for c ciphertexts) duringData Upload phase wherein uploading of a single ciphertext involves three messages (i.e., a preindex message from a Data Owner to the server, an index parameter message from the server to the Data Owner, and a ciphertext message from the Data Owner to the server). In contrast, the proposed MUSE-TFV has an optimal communication overhead of a single message per ciphertext (i.e., cS messages for c ciphertexts) from a Data Owner to the server. With such overhead, the proposed scheme performs similar to the existing schemes discussed in [9, 17, 18].Table 3
Comparative analysis: communication complexity.
Schemes
Data Upload
Token Generation
Search
Hwang and Lee 2007 [9]
c
S
—
(
1
+
c
)
S
Kiayias et al. 2016 [17]
c
S
—
(
3
+
c
)
S
Zhang et al. 2016 [18]
c
S
—
2
S
Wang et al. 2016 [19]
3
c
S
—
(
1
+
c
)
S
MUSE-TFV
c
S
2
q
S
(
1
+
c
)
S
S: a message, c: number of ciphertexts available at the server, and q: number of queries.A scheme in [17] uses two servers (Smain and Said) to perform a search operation where a communication overhead is (3+c)S messages (i.e., a token message from a user to Smain, a token message from a user to Said, an additional message from Said to Smain, and c result messages from Smain to the requesting user). In contrast, the proposed MUSE-TFV involves (1+c)S messages (i.e., a token message from a user to the Storage Server and c result messages from the server to the user) duringSearch phase. The scheme of [18] has the lowest communication overhead during search operation, that is, 2S (a token message from a user to the server and a result message from the server to the user). However, in the scheme [18], the server suffers with the additional computational overhead (for set union operations) in order to incorporate c result messages into a single message.Table3 shows that theToken Generation phase of the proposed MUSE-TFV suffers with the communication overhead of 2qS for q queries. This overhead is due to the interactive Token Generation algorithm that involves two message exchanges between a DU and the ETA, that is, a Token Request message from a DU and a response message from the ETA. However, with such added communication overhead, we achieve a more secure system wherein every Token Generation activity is logged at the trusted site and thus any dishonest activity from a DU can easily be tracked. Moreover, with such interactive Token Generation algorithm, the proposed scheme provides a token freshness verification to prevent a token replay attack. Thus, MUSE-TFV is indeed an effective multiuser scheme for the applications where security of each search activity is a prime requirement.


## 5.1.1. Storage Complexity

To show the storage overhead, we present the ciphertext/token size in terms of the size of an element from the bilinear groups (G1,G2). Observing Table 2, we say that the constructions given in [17, 23] are storage efficient with the constant ciphertext and token size (i.e., O(1)). In contrast, the proposed MUSE-TFV has a ciphertext size linear to the number of keywords in the system (i.e., (O(n)) that is same as ciphertext storage complexity of the existing schemes [18, 19, 21, 22].The significant characteristic of MUSE-TFV is its constant (i.e.,O(1)) token storage complexity. This constant overhead makes the proposed scheme as efficient as the existing schemes [9, 17, 18, 22]. In fact, the actual token size for the MUSE-TFV is three times higher than the token constructed by the schemes [18, 22]. However, with such increased token size, we offer a secure token transmission over any public channel without channel setup overhead. Moreover, with an added component V to the token (where V is the size of a ciphertext for an encrypted verification key TVK1), we prevent the token replay attack.


## 5.1.2. Computational Complexity

We present the computational overhead in terms of the major operations, namely, modular multiplication (M′), scalar multiplication (M), exponentiation (E), and pairing (P) involved in the listed schemes. From our experiments, we observe that a scalar multiplication, an exponentiation, and a pairing operation are costlier (involving more CPU cycles) than a modular multiplication operation. Therefore, from Table 2, we say that the computational cost of the proposedEncryption() algorithm (i.e., (2+2n)M) is almost same as the encryption cost of the listed multikeyword schemes [9, 21, 22]. We note that this encryption overhead is double as compared to the encryption overhead involved in the schemes [18, 23].On the other hand, similar to the scheme in [18], MUSE-TFV has a constant computational complexity, i.e., (O(n)) (independent of the number of users u), forEncryption() algorithm. Such computational cost is far more better than the existing schemes [9, 17] with O(n+u) and O(uk) encryption overhead, respectively. Therefore, we say that with moderate computational overhead for the proposedEncryption() algorithm MUSE-TFV supports multiple keyword based search as well as multiple users in the system.From Table2, we observe that the computational complexity of the proposedTokGen() algorithm of MUSE-TFV is same as the token construction cost of the existing schemes [18, 22, 23], i.e., O(1). With such constant computational overhead, MUSE-TFV performs better than the existing schemes [9, 21] having O(t) token construction overhead. Additionally, we note thatTokGen() algorithm of MUSE-TFV consumes more CPU cycles as compared to the Token Generation algorithm of the schemes [18, 22, 23] due to its interactive token construction steps. However, with such added overhead, MUSE-TFV supports multiple users in the system.We also note that the computational cost of aSearch() algorithm of MUSE-TFV (i.e., (2M+2P)) is almost same as the existing schemes [18, 22, 23]. This constant search complexity (i.e., O(1)) is better than the search complexity (i.e., O(t)) involved in [9, 21]. Moreover, as a multiuser scheme, the MUSE-TFV offers constant computational cost O(1) (i.e., independent from u) during search phase. This cost is much more better than the search computational overhead (i.e., O(uk)) involved in the scheme [17]. It is worth noting that, with similar search complexity as the existing schemes [18, 22, 23], the proposed MUSE-TFV provides an additional token freshness verification feature.


## 5.1.3. Communication Complexity

In Table3, we present the communication complexity of the proposed MUSE-TFV duringData Upload,Token Generation, andSearch phases, as compared to the existing multiuser schemes [9, 17–19]. We note that, with S as a message, a scheme in [19] suffers with the highest communication overhead (i.e., 3cS for c ciphertexts) duringData Upload phase wherein uploading of a single ciphertext involves three messages (i.e., a preindex message from a Data Owner to the server, an index parameter message from the server to the Data Owner, and a ciphertext message from the Data Owner to the server). In contrast, the proposed MUSE-TFV has an optimal communication overhead of a single message per ciphertext (i.e., cS messages for c ciphertexts) from a Data Owner to the server. With such overhead, the proposed scheme performs similar to the existing schemes discussed in [9, 17, 18].Table 3
Comparative analysis: communication complexity.
Schemes
Data Upload
Token Generation
Search
Hwang and Lee 2007 [9]
c
S
—
(
1
+
c
)
S
Kiayias et al. 2016 [17]
c
S
—
(
3
+
c
)
S
Zhang et al. 2016 [18]
c
S
—
2
S
Wang et al. 2016 [19]
3
c
S
—
(
1
+
c
)
S
MUSE-TFV
c
S
2
q
S
(
1
+
c
)
S
S: a message, c: number of ciphertexts available at the server, and q: number of queries.A scheme in [17] uses two servers (Smain and Said) to perform a search operation where a communication overhead is (3+c)S messages (i.e., a token message from a user to Smain, a token message from a user to Said, an additional message from Said to Smain, and c result messages from Smain to the requesting user). In contrast, the proposed MUSE-TFV involves (1+c)S messages (i.e., a token message from a user to the Storage Server and c result messages from the server to the user) duringSearch phase. The scheme of [18] has the lowest communication overhead during search operation, that is, 2S (a token message from a user to the server and a result message from the server to the user). However, in the scheme [18], the server suffers with the additional computational overhead (for set union operations) in order to incorporate c result messages into a single message.Table3 shows that theToken Generation phase of the proposed MUSE-TFV suffers with the communication overhead of 2qS for q queries. This overhead is due to the interactive Token Generation algorithm that involves two message exchanges between a DU and the ETA, that is, a Token Request message from a DU and a response message from the ETA. However, with such added communication overhead, we achieve a more secure system wherein every Token Generation activity is logged at the trusted site and thus any dishonest activity from a DU can easily be tracked. Moreover, with such interactive Token Generation algorithm, the proposed scheme provides a token freshness verification to prevent a token replay attack. Thus, MUSE-TFV is indeed an effective multiuser scheme for the applications where security of each search activity is a prime requirement.


## 5.2. Empirical Evaluation

To evaluate the performance, we conduct the experiments on 32-bit, 2.10 GHz Pentium Core 2 Duo CPU with Windows 7 machine using Java Pairing based Cryptographic (JPBC) Library [42]. From JPBC Library, we utilize Type A pairing (i.e., G1×G1→G2) which is based on an elliptic curve E(Fq):y2=x3+x. Here, the group G1 is a subgroup of E(Fq), and the cyclic group G2 is a subgroup of E(Fq)2 where q is a large prime number. The group order of G1 is 160 bits, and the base field is 512 bits.To systematically compare the performance of the MUSE-TFV with other schemes, we consider three significant parameters, that is, (i) number of keywords in the system (n), (ii) number of keywords in a query (t), and (iii) number of users in the system (u) (Table 4). We perform experiments for different size systems with n∈50,100,150,200,250,300. For each system, we simulate theEncryption(),TokGen(), andSearch() algorithms multiple times and consider their average results. To show the efficiency of MUSE-TFV as a multiuser scheme, we consider a different number of users, that is, u∈1000,2000,3000,4000,5000 in the system. Additionally, during Token Generation experiments, we select the conjunctive queries with the variable number of keywords, that is, t∈10,20,30,40,50. As a large number of keywords in conjunction make a query complex and impractical, we select comparatively small values for t.Table 4
Simulation parameters.
Parameters
Values for simulation
n
50,100,150,200,250,300
u
1000,2000,3000,4000,5000
t
10,20,30,40,50From Table2, we identify that the computational cost ofEncryption() algorithms for all multikeyword schemes(MKC) [21–23] depends upon n whereas for all multiuser schemes [9, 17, 18], it depends upon n, or u or uk. Thus, we simulateEncryption() algorithms for all the listed schemes with different values of n and u separately and show their responses in Figures 5(a) and 5(b), respectively. Note that for simulation purpose we consider the worst case scenario for a scheme [17], where uk=u.Figure 5
Simulation results forEncryption() algorithm.
(a)
(b)From the results in Figure5(a), we note that the encryption time of the proposed MUSE-TFV is linearly increasing with the number of keywords (i.e., n). However, this time overhead is same as the encryption time overhead of [9, 21, 22] but larger than the overhead involved in [18, 23]. Additionally, from Figure 5(b), we observe that the existence of multiple users in the system does not affect the time consumption of encryption algorithm of MUSE-TFV. This characteristic makes the MUSE-TFV more practical than the existing multiuser schemes [9, 17] where the encryption time overhead is linearly increasing with the number of users. Here, we say that with the constant encryption overhead (i.e., independent of the number of users (u)) theEncryption() algorithm of MUSE-TFV supports multiple keywords in a ciphertext and multiple users in the system.We present the empirical results forTokGen() algorithm of MUSE-TFV and other multikeyword (MKQ) schemes in Figure 6. From these results, we say that the MUSE-TFV takes almost constant time to construct a token regardless of the number of keywords in a query. With this characteristic, MUSE-TFV resembles the schemes [22, 23] and performs better than the other multikeyword schemes [9, 21] having O(t) token computational overhead. However, MUSE-TFV takes more time as compared to [22, 23] because of its interactive nature.Figure 6
Simulation results forTokGen() algorithm.According to Table2, the computational overhead for theSearch() algorithm of the listed schemes is either constant or otherwise depending upon t or uk. Thus, we simulate the listed schemes for theirSearch() algorithm with different values of t and u separately and show their responses in Figures 7(a) and 7(b), respectively.Figure 7
Simulation results forSearch() algorithm.
(a)
(b)Observing the results in Figure7(a), we note that the search time overhead for MUSE-TFV is almost constant and independent of the number of keywords in a query (t). With this characteristic, the MUSE-TFV performs a conjunctive search with much less computational time as compared to the existing conjunctive search schemes [9, 21] where the search time is affected by the number of keywords in query (t). From the results in Figure 7(b), we note that, with constant search time overhead, the proposed MUSE-TFV supports multiple users in the system as efficiently as the scheme [18]. In addition, we say that with the search time linear to the number of users (u) the scheme of [17] is indeed less practical. In contrast, with the constant search time overhead, the MUSE-TFV performs a conjunctive keyword search in response to a query coming from any user in the multiuser settings.At last we claim that our empirical results are completely in accordance with the theoretically measured computational complexity presented in Table2. From the theoretical analysis and empirical evaluation, we conclude that, with the moderate storage-computational overhead, the proposed MUSE-TFV is an elegant multiuser searchable scheme with a provision of conjunctive keyword search and token freshness verification.


## 6. Concluding Remarks

In this paper, we discuss the proposed MUSE-TFV: a Multiuser Searchable Encryption with Token Freshness Verification that is based on the concept of Functional Encryption. Unlike the existing Functional Encryption based multiuser searchable schemes wherein a user generates a search token using his own search key, in the proposed MUSE-TFV, a Data User, DU, constructs a search token in cooperation with the ETA. With such interactive Token Generation mechanism, every search activity of each DU is logged at the enterprise trusted site and thus dishonest activity can be easily captured. Moreover, in the MUSE-TFV, each constructed token is valid for one-time use and its freshness is checked at the SS using a verification key issued by the ETA. Such token verification procedure prevents the reuse of the same token and so the MUSE-TFV avoids token replay attack. Additionally, we provide a secure channel-free token transmission as well as a conjunctive keyword search with the proposed scheme.With a security analysis, we prove the correctness of the proposed MUSE-TFV against chosen keyword attack and token replay attack. With a detailed theoretical analysis, we justify the efficiency of the proposed scheme. Additionally, we evaluate the performance of the proposed scheme based on three significant parameters: number of users, number of keywords in the system, and the number of keywords in conjunctive query. Our experimental evaluation shows that, with almost same computational-storage overhead as the existing conjunctive keyword search schemes, the proposed MUSE-TFV provides the additional features of multiuser support and token freshness verification.



---

*Source: 6435138-2017-11-26.xml*