Flexible and Efficient Multi-Keyword Ranked Searchable Attribute-Based Encryption Schemes

Abstract

Currently, cloud computing has become increasingly popular and thus, many people and institutions choose to put their data into the cloud instead of local environments. Given the massive amount of data and the fidelity of cloud servers, adequate security protection and efficient retrieval mechanisms for stored data have become critical problems. Attribute-based encryption brings the ability of fine-grained access control and can achieve a direct encrypted data search while being combined with searchable encryption algorithms. However, most existing schemes only support single-keyword or provide no ranking searching results, which could be inflexible and inefficient in satisfying the real world’s actual needs. We propose a flexible multi-keyword ranked searchable attribute-based scheme using search trees to overcome the above-mentioned problems, allowing users to combine their fuzzy searching keywords with AND–OR logic gates. Moreover, our enhanced scheme not only improves its privacy protection but also goes a step further to apply a semantic search to boost the flexibility and the searching experience of users. With the proposed index-table method and the tree-based searching algorithm, we proved the efficiency and security of our schemes through a series of analyses and experiments.

1. Introduction

1.1. Motivations

Cloud and IoT [1] services have become increasingly popular because of the rise in streaming services [2] and the development of machine learning, especially in the era of COVID-19. Outsourcing data to the cloud saves space for local storage and brings convenience so that users can access and share their data without any space and time limitations. However, since cloud service providers, or cloud servers for short, are not fully trustable, directly uploading sensitive data to the cloud is dangerous and undermines user privacy. Encrypting data and then uploading them seems a safer approach. Nevertheless, in many situations, traditional public key encryption (PKE) [3] schemes can only achieve secrecy but lack proper access controllability. For example, in some cases, we want to authorize files to only a specified group of people. Under PKE, we must copy files many times and encrypt them, respectively. Moreover, the management of secret keys is increasingly cumbersome and difficult. This challenge is specifically severe for medical and financial data because users have the right to decide who can review their sensitive medical and financial records. With attribute-based encryption (ABE) [4,5,6,7,8,9], we can make fine-grained access control much more manageable by only allowing some people with specified attributes (i.e., conditions) to access and view the files.

In addition to the access control, how to fetch the required data rapidly among the massive data stored in the cloud is also a critical issue. Downloading and decrypting all the data and then performing a search can reach the target, but it is not feasible because a massive amount of computation and storage is required on the user end. Apart from the excessive time overhead, these operations may be unsafe. Searchable encryption (SE) algorithms [10,11,12,13,14,15] bring reasonable solutions to this problem. Go a step further; combining the ABE and SE schemes allows users to have fine-grained access controls and searching capabilities regarding encrypted data.

Many searchable attribute-based encryption schemes (ABS) [16,17,18,19,20,21,22,23,24] have provided fine-grained access control, dynamic updates, and attribute revocations. However, searching capabilities could be more potent in most schemes to fulfill actual needs. Usually, they can embed only a single keyword into ciphertexts, which could be inconvenient and make searching more cumbersome. Although some schemes allow for combining multiple keywords and provide ranked search results, users can only fetch files containing all the keywords. More complicated relationships between keywords such as disjunctive logic “OR” can usually not be expressed. In addition, some advanced designs in searchable encryption algorithms have rarely been implemented on such systems. We summarize the standard advanced searching modes in Figure 1. The basic search mode is the keyword rank search which does the exact match of single or multiple keywords. However, in practice, the user’s input commonly contains some typos or uses synonyms. As a result, two high-level search modes, fuzzy search and semantic search, are induced to allow users to obtain the results without using the exact keyword.

To tackle the problems listed above, we proposed two flexible and efficient multi-keyword ranked searchable attribute-based encryption schemes (FEMRSABE), which are especially suitable for E-health applications. In our basic scheme, we designed a search tree data structure to enhance the expressiveness of the search, as shown in Figure 2. The server matches the trapdoors in leaf nodes with index files, traversing the tree and inducing the searching results of parent nodes by union or intersection. Finally, the aggregated search result of the root node is the final result, sorted according to the associated relevance score. The cloud server can only read the user-inputted logic structure but knows nothing about what users have searched. In addition, inspired by [25], we built an index table to boost search efficiency. We replaced the encryption mechanism from symmetric key encryption with pure attribute-based encryption. Data owners do not need to exchange keys with users in advance, making the scheme more realistic. It shows that the search speed is much faster than the case without the index table through experiments. We also provide fuzzy keyword searching ability by calculating the fingerprints of keywords. We refer to the generating method and the similarity score in [11] to ensure the search range is manageable.

Moreover, in our enhanced scheme, we reorganized the system architecture to minimize possible data leakages, such as the logical structure of search trees and the file list of a particular keyword. We further implemented the semantic search functionality with WordNet’s help [26]. As a consequence, we considered the actual semantics of the keywords. Users only need to express their intention of searching without considering the constraints on the data owners’ actual keywords and their perfect spellings. These advanced search modes make the search procedure more flexible and easier to use. The functionality comparisons in later sections show that our scheme has more desirable searching capabilities than other benchmarking searchable attribute-based encryption schemes.

Flexible and efficient multi-keyword ranked searchable attribute-based encryption schemes (FEMRSABE) target the E-health use case. Users, who are equipped with IoT devices that can collect body data such as heart rate and body temperature, can upload their data to the server in encryption form. Doctors or other healthcare professionals can access the data with appropriate permission. Most importantly, the system does not require the accessor to input the exact identical keyword used for encryption. With the benefit of fuzzy and semantic search, FEMRSABE can automatically match and discover the possible meaning and search. This brings flexibility in that IoT providers and healthcare professionals do not need to negotiate the keyword beforehand, and the different IoT devices’ cross-time can also pick up a suitable keyword rather than be limited to the previous choice.

In the security aspect, our FEMRSABE system can defend against selective cipher-text-policy and chosen-plaintext attack (IND-SCP-CPA) by building it on the general bilinear map cryptographic techniques and the associated assumptions.

1.2. Contributions of This Work

We proposed a flexible and efficient scheme, FEMRSABE. The possible contributions of this work include the following:

Flexible Access and Searching Structure: We used linear secret-sharing schemes (LSSS) to build the basic data access structure, allowing data owners to express their data access policy by combining AND–OR logic gates as their wish. Furthermore, the conventional multi-keyword scheme can only find documents containing all the searching keywords. We designed a much more flexible tree structure so that users can express what they want to search by both conjunctive and disjunctive logic.

Ranked Searching Results: Following the techniques presented in [25], we built an index-table structure that can diminish the searching time and make ordered searching results possible. Users can obtain the most desired search results as soon as possible, avoiding unnecessary file decryption or filtering among many matched results.

Fuzzy and Semantic Search Mode: We further included advanced search mechanisms into the enhanced scheme, such as fuzzy and semantic search, by integrating with fingerprints introduced by [11]. Query keywords can now be inaccurate or have spelling errors, making it easier for users to obtain what they want.

Multi-Authority: Allowing the central authority to take over all the jobs of generating user keys is neither efficient nor secure. If the central authority shuts down, the whole system will be affected, which is called the “single-point” failure. We set up multiple attribute authorities to spread the traffic and generate intermediate user keys to solve this problem and shorten the key-generating time.

1.3. Organization

This paper is organized as follows. We review some related attribute-based and searchable encryption schemes in Section 2. Some preliminaries and cryptography backgrounds are addressed in Section 3. Section 4 defines the problem formally and depicts the proposed architecture, while Section 5 addresses our concrete constructions in detail. We present our schemes’ performances and security levels through a series of experiments in Section 6. Finally, Section 7 concludes this write-up.

2. Related Work

2.1. Attribute-Based Encryption

Attribute-based encryption (ABE) is a technique that allows data owners to declare their access policies such as: “(Doctor OR Researcher) AND (Chest OR Surgery)”. Only data users who meet the policy’s attribute requirements are qualified to access the files. For instance, users with the attributes “Doctor and Surgery” can read the text, but ones with “Doctor and Researcher” cannot. Most ABE schemes can be categorized into the following two classes: ciphertext-policy attribute-based encryption (CP-ABE) and key-policy attribute-based encryption (KP-ABE). Wang et al. [27] proposed a constant-size ciphertext KP-ABE scheme, while Water et al. [4] proposed the first practical CP-ABE scheme. The main difference between KP-ABE and CP-ABE is that CP-ABE puts the access policy into ciphertexts while KP-ABE puts it into the users’ secret keys. In CP-ABE schemes, data owners can easily decide who can access the files, so it is more suitable for cloud storage applications. Hence, we adopted it to construct our systems. Over time, more powerful ABE schemes have been developed. Li [7] proposed an attribute-revocable scheme, and Chi et al. [5] proposed a policy-hiding scheme to protect data owners’ privacy further. In addition, most ABE schemes involve bilinear pairing operations, which are very time-expensive, especially for resource-restricted devices such as mobiles and IoT devices. Han et al. [6] proposed a decentralized scheme to reduce the burden of data users by outsourcing the corresponding computational tasks.

2.2. Searchable Encryption

The main characteristic of searchable encryption (SE) is it allows users to search over many encrypted data without the decrypting of the documents in the dataset. High-level concepts of SE are that data owners extract keywords from plaintext files to build a “Secure Index” and then encrypt plaintexts with symmetric encryption schemes. Data owners transform searching keywords into corresponding trapdoors afterward. Finally, cloud servers match the Secure Indexes with the trapdoors to produce search results containing the target keywords the user longs for.

For this purpose, there are many ways to build the pre-described Secure Index. Most of the existing SE schemes involve calculating the term frequency-index document frequency (TF-IDF) values of keywords. Cao et al. [28] and Tzouramanis et al. [12] both use the K-nearest neighbors (KNN) method to build the Secure Index. It is effective; however, the associated neighborhood-related matrix will be too large, and therefore, the associated operations become time-consuming when too many keywords are involved in the system. Other methods include secure random masking, tree-based, and secure linked-list ones. The scheme proposed by Zhang et al. [25] used the secure linked-list method to build an index table, which we also adopted in our work for its efficiency.

Many functional search schemes have been developed to provide a more powerful search capability. For example, Wang et al. [13] proposed a tree-based method to provide range search. It is especially suitable for numerical datasets such as financial records. Aritomo et al. [29] and Fu et al. [10] both achieved semantic-based searching, while Zhang et al. [15] provided an efficient predicate search. Liu et al. [11] proposed a robust scheme combining semantic and fuzzy searches using fingerprint methods, which will also be adopted in our schemes. However, this scheme did not take any access control mechanism into account. They used fully homomorphic encryption (FHE) schemes [30,31,32] to encrypt the index table instead. Due to complexity considerations, our work has not considered FHE schemes in our current system implementation. However, FHE schemes have lots of potential for constructing effective ABE schemes if the required complexity can be handled properly. An FHE-based ABE approach is exciting and can reduce the storage requirement of ciphertexts. We choose to put it into our future investigations.

2.3. Searchable ABE Schemes

Many ABE schemes have searching abilities. For this kind of scheme, it is crucial to allow only the qualified files to be searched. Otherwise, malicious users may launch keyword attacks to guess the contents of files and breach privacy. On the other hand, it is a waste of time for users to decrypt those unqualified files with failure. Sun et al. [22] proposed a famous searchable attribute scheme (ABKS) to hide the access policy. However, they use AND GATE as the access structure for policy hiding, which limits the access policy’s expressiveness. Wang et al. [23] proposed a scheme that is aimed at E-health applications. They achieve a constant computational overhead, constant storage overhead, and policy hiding by hashing user attributes and keywords. However, the access policy’s flexibility and searching are restricted due to its data structures. Moreover, they directly embed keyword hashes into ciphertexts, so it takes much time to match search results when there are many files in the dataset or only a single keyword can be used at a time. Miao et al. [21] and Sun et al. [33] proposed ABKS schemes with the ability for attribute revocations. Nevertheless, the searching capabilities of these schemes are weak because users can only use a single keyword once without any modifications to protocols.

3. Preliminaries

3.1. Bilinear Pairing

Following the definitions in [33], let $\mathbf{G}$ and ${\mathbf{G}}_{\mathbf{T}}$ be two multiplicative cyclic finite groups of prime order $p$. Let $\mathbf{g}$ be a generator in $\mathbf{G}$. The following equations hold to fulfill the definition of the bilinear pairing equations.

• Bilinearity: For all $x, y\in \mathbf{G}$ and all $s,t\in {\mathit{Z}}_{\mathit{p}},e\left(x^s,y^t\right)=e{\left(x, y\right)}^{st}$ holds. That is, the exponentiation operations inside pairings can be moved outside directly.
• Non-degeneracy: $e\left(g,g\right)\ne 1.$
• Computability: For all $x,y\in \mathbf{G},e\left(x,y\right)$ and any additive or multiplicative operations on it can be efficiently computed.

3.2. Access Structure

By definition in [4]: Let ${\{\mathrm{P}}_1{, \mathrm{P}}_2{, \dots , \mathrm{P}}_{\mathrm{n}}\}$ be a set of parties. A collection $\mathbf{A}\subseteq 2^{\left\{{\mathrm{P}}_1, {\mathrm{P}}_2, \dots , {\mathrm{P}}_{\mathrm{n}}\right\}}$ is monotone if $\forall \mathbf{B}, \mathbf{C}$: if $\mathbf{B}\in \mathbf{A}$ and $\mathbf{B}\subseteq \mathbf{C}$ then $\mathbf{C}\in \mathbf{A}$. An access structure (respectively, monotone access structure) is a collection (respectively, monotone collection), A, of non-empty subsets of ${\{\mathrm{P}}_1{, \mathrm{P}}_2{, \dots , \mathrm{P}}_{\mathrm{n}}\}$, i.e., $\mathbf{A}\subseteq 2^{\left\{{\mathrm{P}}_1{, \mathrm{P}}_2{, \dots , \mathrm{P}}_{\mathrm{n}}\right\}}/\varnothing$. The sets in $\mathbf{A}$ are called the authorized sets, and the sets not in $\mathbf{A}$ are called the unauthorized sets.

3.3. Linear Secret-Sharing Schemes

We choose the linear secret-sharing schemes as our access structure due to their full expressiveness in the access policy. Some papers [16,18,19,22,23] use the AND gate to bring efficiencies and policy-hiding capabilities. However, they do not apply to disjunctive operators. Thus, the flexibility of the access policy is quite limited.

The definition of a linear secret-sharing scheme can be found in [34]:

Definition 1.

Linear Secret-Sharing Schemes (LSSS)

A secret-sharing scheme  $\mathit{\Pi }$ over a set of parties  $\mathit{P}$ is called linear over (${\mathit{Z}}_{\mathit{p}}$) if

• The shares for each party form a vector over ${\mathit{Z}}_{\mathit{p}}$.
• There exists a matrix $\mathit{M}$ with is the vector of rows and $n$ columns called the share-generating matrix for $\mathit{\Pi }$. For the i-th row of M, we let the function $\rho$ define the party labeling row $i$, for all $i=1, \dots , l,$ as $\rho \left(i\right)$. When we consider the column vector $v=\left(s,r_2,\dots ,r_n\right)$, where $s\in {\mathit{Z}}_{\mathit{p}}$ is the secret to be shared, and $r_2, \dots , r_n\in {\mathit{Z}}_{\mathit{p}}$ are randomly chosen, then $M·\mathit{v}$ is the vector representing the $l$ shares of the secret $s$ according to the scheme $\mathit{\Pi }$. The share ${\left(\mathit{M}·\mathit{v}\right)}_i$ belongs to party $\rho \left(i\right)$.

3.4. Relevance Score

We use the TFxIDF measurement to express the relevance between the keyword, $w,$ and the document, $F$, which has been widely adopted in many data mining and searchable encryption schemes. Term frequency (TF) represents the frequency of a keyword in the file. Nevertheless, only TF values are insufficient because some common words, such as prepositions, usually differ from what users want to search for, even if they have high occurrence frequencies in the text. Index document frequency (IDF) brings the solution. Engaged readers can find the definitions of TF and IDF in [11].

4. Problem Definitions

4.1. Threat Model

There are several players (or parties) in the investigated systems. Their role and the threat model are listed below.

Central Authority (CA): The central authority (CA) sets up the system and verifies intermediate user keys obtained from attribute authorities. After that, the CA produces the final user keys based on the master key generated by itself. In addition, the CA delivers the public key to the other parties. Notice that the CA is believed to be entirely trustworthy in most schemes and our systems.

Attribute Authority (AA): An attribute authority (AA) is equipped with some necessary cryptographic techniques, accepting the request of data users to generate user keys. They verify and generate intermediate user keys according to the attributes the data users provided. Their behavior is also honest so that they do not misbehave in the process of KeyGen and will not collide with data users.

Data Owner (DO): Data owners may be patients in a medical application. They extract some keywords from their medical records to build the Secure Index. After that, they upload encrypted data and the Secure Index to the cloud server. We also assume that DOs are fully credible. They will correctly extract keywords and perform succeeding encryption to the accessible files themselves.

Cloud Server (CSP): The cloud server provides storage to the encrypted files and performs encryption-domain searches. Their threat model is assumed to be honest but curious once again. They will honestly execute protocols but may attempt to obtain documents and keywords in plaintext form through statistical analyses. They are also interested in finding trapdoors uploaded by users, trying to guess what users are searching for, and tracing their search records.

Data User (DU): Data users may be doctors or researchers in an E-health application scenario. They request the encrypted files by transforming the searching keywords into respective trapdoors to perform searching. They may want to access or guess the contents of unqualified data by selective keyword attacks. However, they do not leak decrypted data to other unauthorized users.

4.2. System Architecture

Figure 3 shows the players, the functional blocks, and the detailed information flow of the proposed system. From Figure 3, nine polynomial-time algorithms (PTAs), as listed below, compose our system.

Table 1. The symbols and their corresponding definitions.

Symbols	Description	Symbols	Description
$\mathrm{MK}$	Master secret key	$\mathrm{w}$	Searching keyword
$\mathrm{PK}$	Public key	$\mathrm{W}$	Keyword set
${\mathrm{MK}}_{\mathrm{Auth}}$	Authority master key	$\mathrm{PF}$	Plaintext files
${\mathrm{PK}}_{\mathrm{Auth}}$	Authority public key	$\mathrm{F}$	A document
$uk$	User secret key	$\mathrm{FP}$	Fingerprint
$ik$	Intermediate user secret key	$\mathrm{CT}$	Ciphertexts
${\mathrm{sk}}_{\mathrm{f}}$	Session key	${\mathrm{R}}_{\mathrm{Score}}$	Relevance score
$U$	The universe of user attributes	${\mathrm{Str}}_{\mathrm{Search}}$	Search condition string
$\mathrm{S}$	User attribute set	${\mathrm{T}}_{\mathrm{FP}}$	Fingerprint table
$x$	An attribute	$\mathrm{Td}$	Trapdoor
$H(.)$	Hash function	${\mathrm{Tree}}_{\mathrm{p}}$	Search tree (plaintext)
$\mathrm{P}$	Access policy	${\mathrm{Tree}}_{\mathrm{e}}$	Search tree (encrypted)
$\mathrm{uid}$	User id	$k$	Maximum size of searching results
$\mathrm{aaid}$	Attribute authority id	$\mathrm{SR}$	Searching results
$\mathrm{Ind}$	Secure index	${\mathrm{SR}}_{\mathrm{Ranked}}$	Ranked searching results

demonstrates the symbols used in this write-up.

Setup $\left(1\mathrm{K},\mathrm{U}\right)\to \left(\mathrm{PK},\mathrm{MK}\right)$: The CA runs the setup algorithm and generates the master key pair. It delivers the public key, $\mathrm{PK},$ to the other parties and keeps the master key, $\mathrm{MK},$ for itself.

Authority Setup $\left(\mathrm{aaid}, \mathrm{MK}\right)\to \left({\mathrm{MK}}_{\mathrm{Auth}}{, \mathrm{PK}}_{\mathrm{Auth}}\right)$: The CA executes the authority setup algorithm to set up all the AAs. It grants authority to the master key, ${\mathrm{MK}}_{\mathrm{Auth},}$ and authority to the public key, ${\mathrm{PK}}_{\mathrm{Auth}},$ for each AA.

IntermediateKeyGen $\left({\mathrm{PK}, \mathrm{uid}, \mathrm{S}, \mathrm{MK}}_{\mathrm{Auth}}{, \mathrm{PK}}_{\mathrm{Auth}}\right)\to ik$: The AA verifies the user attribute set, $\mathrm{S},$ and runs the intermediate key generation algorithm to generate the intermediate user secret key, $ik,$ using its authority keypair.

KeyGen $\left(\mathrm{PK}, \mathrm{MK}, \mathrm{S},ik\right)\to uk$: The CA verifies the validity of the intermediate user key, $ik,$ and then generates the final user secret key, $uk,$ by the key generation algorithm.

BuildIndex $\left(\mathrm{PK}, \mathrm{W}\right)\to \left(\mathrm{Ind}, \mathrm{TF} \mathrm{P}\right)$: DOs build an index table for each keyword, $w,$ in the keyword set, $\mathrm{W}$. In addition, they run a fingerprint generation algorithm to support fuzzy matching and build a fingerprint lookup table as one of the outputs. Figure 4 shows the data structure used to construct our index table.

Encrypt $\left({\mathrm{PK}, \mathrm{P}, \mathrm{W}, \mathrm{sk}}_{\mathrm{f}}{, \mathrm{sk}}_{\mathrm{t}}\right)\to \mathrm{Ct}$: DOs extract keywords from the plaintext to obtain the keyword list, W, and then input the public key, $\mathrm{PK}$, access policy, $\mathrm{P}$, and the session key, ${\mathrm{sk}}_{\mathrm{f}}$, to the encrypted algorithm for generating the ciphertext. Finally, it encrypts the tables with ${\mathrm{sk}}_{\mathrm{t}}$. DUs recover the session keys and decrypt files and tables associated with this ciphertext.

GenTrapdoor $\left({\mathrm{PK}, \mathrm{Str}}_{\mathrm{Search}},uk\right)\to \mathrm{Td}$: DUs use the user key, $uk$, the public key, $\mathrm{PK}$, and the search condition, ${\mathrm{Str}}_{\mathrm{Search},}$ to generate the trapdoor, $\mathrm{Td},$ based on the trapdoor-generating algorithm. This algorithm has two phases: DUs obtain the hash values of the most proper keywords using the fingerprint-matching algorithm in the first phase. A search tree, ${\mathrm{Tree}}_{\mathrm{p}},$ is constructed according to ${\mathrm{Str}}_{\mathrm{Search}}$ and the hash values. Each keyword, ${\mathrm{W}}^{\prime }$, in ${\mathrm{Tree}}_{\mathrm{p}}$ is converted into a corresponding trapdoor, $\mathrm{Td}$. In the second phase, all leaf nodes in ${\mathrm{Tree}}_{\mathrm{p}}$ are replaced by $\mathrm{Td}$ to become an encrypted search tree, ${\mathrm{Tree}}_{\mathrm{e}}$.

Search $\left({\mathrm{Tree}}_{\mathrm{e}}, \mathrm{Ind},k\right)\to {\mathrm{SR}}_{\mathrm{ranked}}$: The CSP parses the encrypted search tree, ${\mathrm{Tree}}_{\mathrm{e}}$, and executes the search algorithm to match $Td$ with $Ind$ to obtain the searching result, SR. The CSP sorts SR and outputs the top-k files as the final search result, ${\mathrm{SR}}_{\mathrm{ranked}}$. In our enhanced scheme, the CSP only matches the trapdoor, leaving the jobs of traversing searching trees and ranking for DUs to ensure better data privacy.

Decrypt $\left(uk{, \mathrm{Ct}, \mathrm{SR}}_{\mathrm{ranked}}\right)\to \mathrm{PF}$: DUs input their user key, $uk$, ciphertext, $\mathrm{Ct}$, and the ranked searching result, ${\mathrm{SR}}_{\mathrm{ranked}},$ to the decryption algorithm to obtain the plaintext files, PFs.

4.3. Security Model

The security model of the proposed system is built on general bilinear map cryptographic techniques and the associated assumptions. As addressed in the following paragraphs, we designed a security game to explore our system’s security level. It shows that our system can defend against selective ciphertext-policy and chosen-plaintext attack (IND-SCP-CPA).

The Ciphertext-domain Keyword Privacy Game.

Init: Firstly, A delivers the challenge access matrix $A^{*}$ to $B$.

Setup: $B$ runs the same setup algorithm in the keyword private game.

Phase I: $B$ provides an oracle, $O_{S{K}_u},$ for a query. Furthermore, $B$ builds a secret key list, $Ls{t}_{SK,}$ to hold the query results. The oracle functions as follows:

$O_{SK}\left(uid,S\right)$: $A$ submits $uid$ and the user attribute set, $S,$ to obtain the corresponding user key, $S{K}_{uid,S}$. Notice that $S$ sent by $A$ cannot satisfy the access structure, $A^{*}$. If $S{K}_{uid,S}$ has been in the keyword list, $Ls{t}_{SK}$, $B$ looks up the list and returns the result directly. Otherwise, $B$ executes the key-generating algorithm and inserts the result into the list.

Challenge: $A$ prepares two equal-length messages, $m_0$ and $m_1,$ for the challenge. $B$ then decides on a random bit, $b\in 0,1,$ and encrypts them under $A^{*}$. Finally, $B$ sends back the ciphertext, $C{T}^{*}$, to $A$.

Phase II: $B$ can continue to query for ciphertexts after receiving $C{T}^{*}$. The operation is the same as Phase I.

Guess: $A$ makes a guess, $b^{\prime }$, for if the bit, $b,$ is $0$ or $1$. If $b=b^{\prime }$, A wins the security game.

The advantage of A to win the security game is $Ad{v}_A=\left|Pr\left[b^{\prime }=b\right]-\frac{1}{2}\right|$. Our system is IND-SCP-CPA secure if all polynomial-time adversaries only have negligible advantages at most in the security game above.

5. Concrete Construction

Construction of the Basic FERMSABE Scheme

With the pre-described nine PTAs, the basic FERMSABE system can be constructed as follows.

Step 1. The CA sets up the security parameter, $\mathrm{K},$ and the global parameters $\left(G_1,G_T,e\right)$, where pairing operations e: $G_1\times G_1\to G_T$. Then, the CA generates three generators, $g$, $g_0$, and $g_1$, for the finite group, $G_1$. The Setup algorithm randomly chooses $a_0$, $a_1$, $b_0$, and $x$ from the group ${\mathit{Z}}_{\mathit{p}}$ and chooses $v_x$ for each attribute in the universe. The rest of the public and the master keys are organized as follows.

$$PKg, g_0, g_1, Y=e {\left(g, g\right)}^x, A=g_0^a, B=g_0^b, {\left\{H_x=g^{b_0·v_x}\right\}}_{x\in U}$$

$$MK: a_0, a_1, b_{0}x, {\left\{v_x\right\}}_{x\in U}$$

After that, the CA publishes the master key pair to other parties. The CA further defines a hash function, $H\left(x\right):{\left\{0,1\right\}}^{*}\to {\mathit{Z}}_{\mathit{p}}$, to map keywords into elements of ${\mathit{Z}}_{\mathit{p}}$.

Step 2. The CA sets up each AA and grants the authority key pair, $P{K}_{Auth}$ and $M{K}_{Auth},$ to the authority with an identifier, $aaid$. The AuthoritySetup algorithm generates a random element, t, from ${\mathit{Z}}_{\mathit{p}}$ while the authority key pair comprises $P{K}_{Auth}\triangleq g^t$ and $M{K}_{Auth}\triangleq t$.

Step 3. When a user requests the user key, the corresponding AA runs the IntermediateKeyGen algorithm to generate the intermediate user keys using his authority key pair. The AA randomly picks an $\alpha$ from ${\mathit{Z}}_{\mathit{p}}$ and sends this value to the CA. The intermediate user key, $ik,$ is generated as: $ik \triangleq K_0^{\prime }={\left(g^t\right)}^{a_0}$and $K_1^{\prime }={\left(g^t\right)}^{\alpha }$. The AA sends this value to the CA to generate the final user key.

Step 4. The CA verifies the validity of the intermediate user key, $ik,$ and then uses it to run the KeyGen algorithm for generating the final user secret key set, $uk$, which is composed of seven components. Then, the CA chooses ${\mu }_0$ and $u$ from ${\mathit{Z}}_{\mathit{p}}$. The first six components of $uk$ are:

$$K_0=g^{x_1}·K_0^{\prime }, K_1={\left(K_1^{\prime }\right)}^{\left(1/\alpha \right)·u}, K_2=g^{{\mu }_0}, K_3=u, K_4=g^{x_2/u}, \mathrm{and} K_5=g_0^{a_0}.g_1^{{\mu }_0}$$

Notice that $x_1$ and $x_2$ are random elements taken from $Z_p$ such that $x_1+x_2=x$. The CA generates $K_x$ for each attribute in $S$, that is $K_x=H_x^{{\mu }_0}$. The final user key = $K_0,K_1,K_2,K_3,K_4,K_5,{\left\{K_x\right\}}_{x\in S}$ and will be sent back to the data user.

Step 5. DOs build an index table, Ind, based on keywords extracted from plaintext files. Our BuildIndex algorithm is founded on the approach presented in [35] to build our Ind. Figure 4 depicts the data structure of our index table, where each field in blocks of the linked list represents:

−

$\mathrm{Id}\left(F_j\right)$: The identifier of the file, $j$, which contains the keyword, $i$.

−

${\mathrm{S}}_{ij}$: The relevance score of the keyword, $i,$ and the file, $j$. Notice that the blocks will not be sorted according to this score for confusion.

−

$r_{ij}$: Random strings of the same length. We use this field to prevent producing two identity blocks.

−

Padding values: We add padding values to every linked list to make them of the same size. This setting implies that some linked lists composed of all padding values may also be appended to the table.

Furthermore, DOs build a fingerprint table to support fuzzy search. Figure 5 illustrates the structure of our fingerprint table, and the corresponding generation algorithm can be found in [15]. We store the hash value of a keyword instead of itself to prevent DUs from knowing the keywords of DOs directly. Only the hash value is enough for the subsequent matching and searching tasks.

In addition to these tables, the DO needs to put some extra data into the headers of Ind to allow the cloud server to perform matchings. We list the additional information in the following:

$$I_0=g_1^s, I_2=e{\left(A_0, g_0\right)}^s, {\left\{I_{1,x}=H_x^{\left(\frac{1}{H\left(w\right)}\right)}\right\}}_{x\in \rho \left(i\right)} , \mathrm{and} I_3=B^{s/H\left(w\right)}.$$

(1)

Finally, the DO uploads the encrypted Ind and ciphertexts to the cloud server.

Step 6. DOs extract keywords from the plaintext files, PF, to build the keyword list, $\mathrm{W},$ and input the public key, $\mathrm{PK}$, access policy, $\mathrm{P}$, and the session keys, ${\mathrm{sk}}_{\mathrm{f}}$ and ${\mathrm{sk}}_{\mathrm{t}},$ to the Encrypt

Algorithm. The former is used to encrypt PF, and the latter is used to encrypt ${\mathbf{T}}_{\mathbf{FP}}$ by symmetric encryption algorithms such as AES. They choose two elements, $s$ and $s^{\prime },$ from $Z_p$ for supporting secret sharing and, respectively, build the secret sharing vectors, ${\lambda }_x$ and ${\lambda }_x^{\prime },$ for $x\in \rho \left(i\right)$ by LSSS schemes as follows. They further compute

$C_0=s{k}_f·e{\left(g,g\right)}^{x·s}$, $C_1=g^s$, ${\left\{C_x=g^{a_0·{\lambda }_x}\right\}}_{x\in \rho \left(i\right)}$, $C_2=s{k}_t·e{\left(g,g\right)}^{x·s^{\prime }}$, $C_3=g^{s^{\prime }}$, and ${\left\{D_x=g^{a_0·{\lambda }_x^{\prime }}\right\}}_{x\in \rho \left(i\right)}$. Finally, DOs upload $\{\left\{{\mathrm{CT}=C}_0{, C}_1{, C}_2{, C}_3{, \{C}_{\mathrm{x}}{\}, \{\mathrm{D}}_{\mathrm{x}}\}\right\}$, ${\mathrm{Enc}}_{{\mathrm{sk}}_{\mathrm{f}}}\left(\mathbf{PF}\right)$, ${\mathrm{Enc}}_{{\mathrm{sk}}_{\mathrm{t}}}\left({\mathbf{TF}}_{\mathbf{P}}\right)$, ${\mathrm{Enc}}_{{\mathrm{sk}}_{\mathrm{t}}}\left(\mathbf{Ind}\right)\}$ to CSP.

Step 7. DUs first download the ciphertext pack from CSP and decrypt Ind and ${\mathrm{T}}_{\mathrm{FP}}$ with uk by the Decrypt algorithm. If DUs own the right user key, $s{k}_t$ can be obtained to decrypt these tables correctly. Otherwise, the algorithm halts. By using a fuzzy matching algorithm, DUs can find the fingerprint that best matches the fingerprint of the input keyword, where we adopt the fuzzy matching algorithm presented in [15] to realize this function. Nevertheless, we additionally set a matching threshold to 0.7. Suppose the relevance score between the best-matched fingerprint and the query fingerprint is lower than this threshold, the match will be discarded, and the corresponding leaf node will be removed to prevent fetching unrelated documents. Second, DUs look up ${\mathbf{TF}}_{\mathrm{P}}$ to obtain the best-matching hash value, $H\left(w^{\prime }\right)$. After that, DUs parse ${\mathbf{Str}}_{\mathbf{Search}}$ to build a search tree, as shown in Figure 6. Finally, DU chooses a random element, ${\gamma }_u$, from $Z_p$ to disturb all the values on the leaf nodes. That is, using the GenTrapdoor algorithm, we compute

$$T_0=K_2·g^{{\gamma }_u} \mathrm{and} T_1=K_{5·g_1^{{\gamma }_u}}·{\sum }_{x\in S}{\left(K_x·H_x\right)}^{1/H\left(w’\right)}$$

DUs replace the plaintext domain to-be-searched keywords with these two values at the corresponding locations to produce ${\mathbf{T}}_{\mathbf{W}}$ for searching. Eventually, DUs provide ${\mathbf{T}}_{\mathbf{W}}$ and the decrypted Ind to the cloud server.

Step 8. The CSP first parses the encrypted search tree, ${\mathbf{Tree}}_{\mathbf{e}}$. Then, it matches each Td in ${\mathbf{Tree}}_{\mathbf{e}}$ with each header information in $\mathbf{Ind}$. In other words, it compares whether $I_2·e\left(T_0,I_0·{\Pi }_{x\in S}{I}_{1,x}\right)=e\left(C_1,T_1\right)$? If any index satisfies the previous condition, all the document indexes stored in the latter linked list will be appended to the tree node. Notice that we only need to compute the right-hand side term once because it is fixed. Therefore, our Search algorithm is quite efficient. After all the leaf nodes are searched, the CSP takes the intersection or union of the search results’ leaf nodes to become the final search results of the parent nodes depending on whether their parents are AND node or OR node. Finally, the CSP sorts the searching results, SR, in the root node and outputs the top-k files as the final searching result, ${\mathbf{SR}}_{\mathbf{ranked}}$. Then, ${\mathbf{SR}}_{\mathbf{ranked}}$ will be sent back to the DUs.

Step 9. In the final phase, DUs use their user keys, $uk$, to match with the ciphertext, Ct, for finding the decryption keys. DUs will compute $E=\frac{{{\displaystyle \prod }}_{x\in S}e{\left(C_x,K_1\right)}^{{\omega }_x}}{e\left(C_1,K_4\right)}=\frac{e{\left(g,g\right)}^{\frac{{\alpha }_{st}}{\mu }}}{e{\left(g,g\right)}^{\frac{s{x}_2}{\mu }}}$.

Using $E$, they further compute $R=\frac{C_0·E^{K_3}}{e\left(g^s,K_0\right)}$.

Suppose the user key satisfies the access policy. In that case, R will be identical to the final decryption key, ${\mathrm{sk}}_{\mathrm{f}}$. Finally, DUs can use this key to decrypt encrypted data retrieved in the previous step and obtain the plaintext files. We will present the correctness proofs of searching and decryption in the next Section.

6. Analyses

6.1. Security Analyses

In this section, we explore the proofs of the security model as mentioned above and other functional modules of our system.

Theorem 1: Assume the $q$-parallel bilinear Diffie–Hellman ($q$-BDHE) assumptions hold in both $\mathbf{G}$ and ${\mathbf{G}}_{\mathrm{T}}$ groups. There is no probability that any polynomial-time adversary, A, can break the security of our schemes with a non-negligible advantage.

Proof: Assume the advantage of distinguishing a valid ciphertext from a random element for $A$ is ${\epsilon }_1=Ad{v}^{IND-sCP-CPA}$. We built a simulator, B, that can break the $q$-BDHE assumption with a non-negligible advantage ${\epsilon }_1/2$.

The $q$-BDHE challenger, $\mathrm{C}$, first selects random elements $a$, $s$, $b_1$,…, $b_q$ from ${\mathit{Z}}_{\mathit{p}}$ and sets $\phi =\left(g,g^s,\dots ,g^{a^q},g^{a^{q+2}},\dots ,g^{a^{2q}},g^{s·b_j},g^{a/b_j},g^{a^{q/b_j}},g^{a^{q+2/b_j}},\dots ,g^{a^{2q/b_j}},g^{a·s·b_i/b_j},\dots ,g^{a^q·s·b_i/b_j}\right)$. According to the definition of $q$-BDHE, A is still hard to distinguish $e{\left(g, g\right)}^{a^{q+1}·s}$ even if he knows the above arguments. Then, C chooses a random bit, $\gamma \in 0,1$. If $\gamma =0$, C sets $T=e{\left(g, g\right)}^{a^{q+1}·s}$. Otherwise, $T$ is set to a random element in ${\mathrm{G}}_{\mathrm{T}}$.

Init: The simulator, B, received a $q$-BDHE challenge instance $\left(\phi ,T\right)$. The adversary, A, announces a challenge access structure $\left(M^{*},{\rho }^{*}\right)$ and sends it to B, where $M^{*}$ is an $l^{*}\times n^{*}$ matrix and $l^{*}, n^{*}<q$.

Setup: B selects an element, $x^{\prime }$, in $Z_p$ randomly and sets $e{\left(g, g\right)}^x=e\left(g^a,g^{a^q}\right)$. $e{\left(g, g\right)}^{x^{\prime }}$ which implicitly makes $x=x^{\prime }+a^{q+1}$. In addition, B initializes a $v_x$ for each attribute by choosing $v_x\in Z_p$ at random, and also randomly selects an element, $b_0$, from the same group. Finally, B sets $H_x=g^{b_0·v_x}$ and gives the partial public key parameters to A.

Phase I: B keeps a list of the tuple $\left(uid,S,SK\right)$ represented as ${\mathrm{Lst}}_{\mathrm{SK}}$. Initially, the list is empty. A can query the following oracle in the polynomial form:

−

$O_{SK}\left(uid,S\right)$: Assume that B received a secret key query for $\left(uid,S\right)$, in which $S$ does not match the access structure $\left(M^{*},{\rho }^{*}\right)$. B performs the following operations: if A has previously asked for $S$, B retrieves $SK$ from the list, ${\mathrm{Lst}}_{\mathrm{SK}}$, directly and returns it to A.

Otherwise, B chooses a vector, $\gamma =\left({\gamma }_1,\dots ,{\gamma }_{N^{*}}\right)\in Z_p$, such that ${\gamma }_1=-1$ and $M_i^{*}·\gamma =0$ for all $i,{\rho }^{*}\left(i\right)\in S$. This matrix must exist according to the properties of LSSS. Then, B randomly picks $\sigma \in Z_p$ and represents t as: $t=\sigma +{\gamma }_1{a}^q+{\gamma }_2{a}^{q-1}+\dots +{\gamma }_n{a}^{q+1-n^{*}}·B$ further selects $x_1^{\prime }, x_2^{\prime }\in Z_p$ at random, such that $x_1^{\prime }+x_2^{\prime }=x^{\prime }$ mod $p$, and sets $x_1=x_1^{\prime }+a^{q+1}$ and $x_2=x_2^{\prime }$. Then, B, respectively, calculates $K_1$ and $K_4$ as: $K_1=g^{\frac{\sigma }{\mu }}·{\displaystyle \prod }_{i=1,\dots ,n^{*}}{\left(g^{a^{q+1-i}}\right)}^{\frac{r_i}{\mu }}=g^{\frac{t}{\mu }}$ and $K_4=g^{x_2/u}=g^{x_2^{\prime }/u}$. Through the definition of $t$, we noticed that $g^{at}$ contains a term of $g^{a^{q+1}}$, which can be ignored with the unknown terms in $g^{x_1}$ when calculating $K_0$. That is, B computes $K_0$ as: $K_0=g^{x_1^{\prime }}{g}^{\alpha \sigma }·{\displaystyle \prod }_{i=2,\dots ,n^{*}}{\left(g^{a^{q+2-i}}\right)}^{{\gamma }_i}=g^{x_1}·g^{at}$. Notice that $K_5$ and $K_x$ are irrelevant to $t$, $x_1^{\prime }$, and $x_2^{\prime }$, so we omit the generation of them here. Finally, B puts $SK=\left\{K_0,K_1,K_2,K_3,K_4,K_5,{\left\{K_x\right\}}_{x\in S}\right\}$ into ${\mathrm{Lst}}_{\mathrm{SK}}$ and sends the keys to A.

Challenge: A prepares two equal-length messages, $m_0$ and $m_1$, for the challenge. B then decides on a random bit, $b\in 0,1$, and encrypts them under $M^{*}·B$ computes $C_0^{*}$ as $C_0^{*}=m_b·T·e\left(g^s,g^x\right)$, and $C_1^{*}$ is generated as $C_1^{*}=g^s$.

It is hard for B to simulate $C_x^{*}$ since it includes the term $g^{a^{j}s}$. To overcome this difficulty, B splits the secret to eliminate the above-mentioned terms. That is, B selects $y_2^{\prime }, \dots , y_{n^{*}}^{\prime }\in {\mathit{Z}}_{\mathit{p}}$ randomly, and then shares the secret vector, $\mathrm{V}=\left(s,sa+y_2^{\prime },s{a}^2+y_3^{\prime }+\dots +s{a}^{n^{*-1}}+y_{n^{*}}^{\prime }\right)\in {\mathit{Z}}_{\mathit{p}}$, with A. For $i\in \left[1,l\right]$, we describe $Q_i$ as the set of all $k\ne i$ making ${\rho }^{*}\left(i\right)={\rho }^{*}\left(k\right)$. B calculates $C_{x^{*}}$ as: $C_{x^{*}}={\displaystyle \prod }_{i=2,\dots ,n^{*}}{\left(g^a\right)}^{M_{i,k}^{*}·y_k}·{\displaystyle \prod }_{x\in Q_l,k=1,\dots ,n^{*}}{\left(g^{\frac{a_{j}s{b}_i}{b_l}}\right)}^{-M_{i,k}^{*}}$.

We produce $C_2^{*}$, $C_3^{*}$, and $D_x^{*}$ in the similar way. Finally, B returns the challenge ciphertext, $C_T^{\prime }=\left\{C_0^{*},C_1^{*},C_2^{*},C_3^{*},{\left\{C_i^{*}, D_i^{*}\right\}}_{i\in \left[1,l\right]}\right\}$, to A.

Phase II: A continues to make queries similar to Phase I.

Guess T: A outputs $b^{\prime }$ which is a guess of $b$. If $b^{\prime }=b$, B returns $\gamma =0$ to guess $T=e{\left(g,g\right)}^{a^{q+1}·s}$. Otherwise, B returns $\gamma =1$, indicating that $T$ is a random element chosen from $G_T$. In this case, A won the security game and obtained an effective ciphertext. Now, the advantage of A is $Pr\left[b^{\prime }=b|\gamma =0\right]=1/2+{\epsilon }_1$. Conversely, A cannot obtain any information about b and the ciphertext; thus, $Ad{v}_B=1/2$. In conclusion, the advantage of A in winning the IND-SCP-CPA security game is: $\frac{1}{2}\left(\frac{1}{2}+{\epsilon }_1\right)+\frac{1}{2}·\frac{1}{2}-\frac{1}{2}=\frac{{\epsilon }_1}{2}$. Since A only has a negligible advantage in solving the $q$-DBHE problem, hence no polytime adversary, A can break the security of our schemes with a non-negligible advantage.

As for the keyword privacy, we will prove that any polytime adversary, A, cannot guess the input keyword, w, from the Secure Index, $\mathrm{I}$, nor forge it.

Firstly, because the secret value, s, masked the term $I_3=g^{\frac{\left(b_0·s\right)}{H\left(w\right)}}$. Even if A has produced the value $g^{1/H\left(w\right)}$ on its own, the only term which contains $b_0$ is $I_{1,x}=g^{\frac{\left(b_0·v_x\right)}{H\left(w\right)}}$. A cannot obtain the value, $v_x$, because it is one of the components of the master key, $MK$, to tell or forge the Secure Indices. To change the keyword of a trapdoor, A needs to modify $T_1=K_5·g_1^{{\gamma }_u}·{\displaystyle \prod }_{x\in S}{\left(K_x·H_x^{{\gamma }_u}\right)}^{1/H\left({\omega }^{\prime }\right)}$. However, it is hard due to the difficulty in solving the discrete log problem.

In summary, the unmalleability of the index and trapdoor of our scheme has now been proved.

6.2. Functional Comparisons

We compared some existing ABKS schemes with ours in terms of access control, keyword search, multi-keyword, ranked result, fuzzy search, and semantic search capabilities, as shown in

Table 2. Functional Comparison between the proposed and the benchmarked ABKS schemes.

Function	MABKS [21]	MSDVABE [33]	FSSE [11]	Ours
Access control	$✓$	$✓$	-	$✓$
Keyword search	$✓$	$✓$	$✓$	$✓$
Multi-keyword	-	$✓$	$✓$	$✓$
Ranked result	-	-	$✓$	$✓$
Fuzzy search	-	-	$✓$	$✓$
Semantic search	-	-	$✓$	$✓$

. We use the symbol “$✓$ “ to mean that the scheme has the indicated function, while the symbol “-“represents the lack of this kind of function. Our scheme is the most functional from the table, providing fine-grained access control and supporting a multi-keyword ranked search result with various powerful search modes.

6.3. Computational Complexity Analyses

Table 3. Comparisons of Theoretical Computational Costs Between Our Scheme and the Benchmarked Ones.

Function	MABKS [21]	MSDVABE [33]	OABRSE [11]	Ours
Setup	$\left(\left|U\right|+3\right)E+P+E_T$	$\left(\left|U\right|+4\right)E+P$	$\left(\left|U\right|+2\right)E+P+E_T$	$\left(\left|U\right|+2\right)E+P+E_T$
KeyGen	$\left(3\left|S\right|+8\right)E$	$\left(\left|S\right|+4\right)E$	$\left(\left|S\right|+4\right)E$	$\left(\left|E\right|+5\right)E$
Enc	$\left(4\left|L\right|+3\right)E+P+2E_T$	$\left(3\left|L\right|+1\right)E+E_r$	$\left(\left|L\right|+1\right)E+1E_T$	$\left(2\left|L\right|+2\right)E+2E_T$
Trap	$\left(2\left|S\right|+2\right)E$	$3E$	$4E$	$\left(2\left|S\right|+2\right)E$
Search	$2P$	$3P$	$3P$	$2P$
Dec	$\left(2\left|S\right|+1\right)P+\left|S\right|E_T$	$\left(2\left|S\right|+1\right)P+2\left|S\right|E_T$	$\left(\left|S\right|+2\right)P+\left(\left|S\right|+1\right)E_T$	$\left(\left|S\right|+2\right)P+\left(\left|S\right|+1\right)E_T$

compares the theoretical computation costs with some recent ABKS schemes and ours. Let $\left|\mathrm{U}\right|$ denote the universe size and $\left|\mathrm{S}\right|$ the size of user attributes, while we use $\left|\mathrm{L}\right|$ to represent the number of attributes the DO used in the access policy. We use $\mathrm{P}$ to symbolize pairing operations. $\mathrm{E}$ and ${\mathrm{E}}_{\mathrm{t}}$ represent the exponentiation operations in groups $G$ and $G_T$. Hash functions are excluded from our comparison because they are much more efficient than exponentiation and pairing operations. The table shows that our scheme is the most efficient one most of the time, especially for searching.

We concluded our theoretical storage costs compared with the above-mentioned schemes in

Table 4. Comparisons of Theoretical Storage Costs Between Our Scheme and the Benchmarked Ones.

Function	MABKS [21]	MSDVABE [33]	OABRSE [11]	Ours
Master keypair	$\left(\left|U\right|+6\right)\left|G\right|+\left|G_T\right|+\left(\left|U\right|+3\right)\left|Z_p\right|$	$\left(\left|U\right|+5\right)\left|G\right|+\left|G_T\right|+\left(\left|U\right|+1\right)\left|Z_p\right|$	$\left(\left|U\right|+3\right)\left|G\right|+\left|G_T\right|+\left(\left|U\right|+2\right)\left|Z_p\right|$	$\left(\left|U\right|+5\right)\left|G\right|+\left|G_T\right|+\left(\left|U\right|+3\right)\left|Z_p\right|$
User key	$\left(3\left|S\right|+4\right)\left|G\right|$	$\left(\left|S\right|+4\right)\left|G\right|+\left|Z_p\right|$	$\left(\left|S\right|+4\right)\left|G\right|+\left|Z_p\right|$	$\left(\left|S\right|+5\right)\left|G\right|+\left|Z_p\right|$
Ciphertext	$\left(2\left|L\right|+1\right)\left|G\right|+2\left|G_T\right|$	$\left(2\left|L\right|+2\right)\left|G\right|$	$\left(2\left|L\right|+1\right)\left|G\right|+\left|G_T\right|$	$\left(2\left|L\right|+2\right)\left|G\right|+2\left|G_T\right|$
Index	$\left(\left|S\right|+2\right)\left|G\right|+\left|G_T\right|$	$3\left|G\right|$	$3\left|G\right|$	$\left(\left|S\right|+2\right)\left|G\right|+\left|G_T\right|$
Trapdoor	$2\left|G\right|+\left|Z_p\right|$	$3\left|G\right|$	$3\left|G\right|$	$2\left|G\right|$

. $\left|G\right|$, $\left|G_T\right|$, and $\left|Z_p\right|$ are bit lengths required to store an element in the respective finite group. Our theoretical storage costs are similar to the MABKS [17] scheme. However, our scheme has lower constant terms and has little relevance to the user attribute size. Furthermore, our trapdoor size is quite reasonable compared with the other schemes. We put extra data into ciphertexts to eliminate the need for DOs to exchange keys with DUs. Even so, the space complexity of ciphertexts is still acceptable in actual cases.

6.4. Experimental Analyses

We designed a series of experiments to simulate the actual performance of our schemes. We used the real Enron email dataset [35] for testing. Moreover, we tested our schemes on a Windows machine with 2.80 GHz Intel(R) Core(TM) i7-1165G7 @ 2.80 GHz CPU and 8 GB ROM. We used JPBC (Java Pairing-Based Cryptography) as the pairing operation library and executed the programs on Java SDK 17 and JPBC 2.0.0. According to the most popular setting, we set $\left|Z_p\right|=160$ bit and $\left|\mathbf{G}\right|=\left|{\mathbf{G}}_{\mathrm{T}}\right|=1024$ bit, and the Type-A elliptic curve: $y^2=x^3+x$ is picked. For practical uses, the universe size is between [20, 100], and the user attribute size is between [3, 100]. In the subsequent experiments, we assumed at least one authorized document for DUs to retrieve.

Figure 7a–d shows the simulation results of our basic scheme compared with others. The universe and the user attribute sizes have been mentioned above. Because some of these schemes do not support multi-keyword ranked search, we only examined one document and one searching condition for ease of simulations. However, it is sufficient to express the effectiveness of the proposed scheme. Figure 7a shows the setup time, demonstrating a linear dependency on the size of the system attributes. While the encryption time is irrelevant to the size of the system attributes, as shown in Figure 7b, our setup time is similar to the other benchmarking schemes, but we use a much shorter time for encryption. Our scheme shows superiority in decryption and user-key generation time, as demonstrated in Figure 7c,d. Notice that the required key-generation time is proportional to the size of the user attributes rather than that of the universe. Clearly, our scheme has more advantages when massive user attributes are required. Our approaches are the most efficient compared to the MABKS [21] and MSDVABE [33] schemes.

We constructed a practical system for the implementation of our enhanced scheme. Figure 8a–e shows this system’s actual data retrieval and index-table building times. For ease of simulations, we realized the same extensions on the other benchmarked schemes to support more powerful searching modes. In these experiments, we set the universe size to 27, and the user attributes size to 3 for simulating real scenarios. These attributes are categorized into position, subject, and level classes. This setting does not affect the experiment results in any case. In Figure 8a, we fixed the size of the keywords.

We set the number of Provided by DOs to 30 and the number of search conditions selected by DUs to 5. Furthermore, we set the size of the document database to vary from 20 to 100. In this circumstance, our search time is almost constant and is similar to that of MABKS [21]; both are better than the MSDVABE [33]. In Figure 8b, the keyword size varies from 20 to 100 while the database size and searching conditions are fixed to 100 and 5, respectively. Our searching time is linearly proportional to the size of the keywords, while that of the MSDVABE [33] scheme varies more dramatically than ours. The same conclusion can be drawn from Figure 8. When the search conditions increase from 5 to 30, our scheme performs better than the others.

Figure 8d–f demonstrates the actual consuming times for building an index table. Although the MSDVABE [33] scheme takes the shortest time in this experiment, it has a poor performance on searching. With a similar opinion to MABKS [21], we conducted one pairing operation in the index-building phase to prevent performing too many pairing operations in the searching phase. Therefore, some of the performance on building index tables is sacrificed. However, data owners usually build index tables only once, but data users may search the database many times. Therefore, our schemes are most realistic and practical in actual use. Furthermore, these two schemes take much more time, even making it impossible to perform fuzzy and semantic keyword-ranked searches combined with multiple keywords without our extensions. We proved that our schemes are efficient, flexible, and universal to apply to other performance-oriented AMKS schemes.

7. Conclusions

In this paper, we showed that the proposed FEMRSABE scheme has a powerful search capability that can satisfy most users’ needs. Even if the user inputs do not fully match the keywords set up by the DO or have some minor spelling errors, users can still obtain the desired and most-related documents. Our basic protocol competes with the state-of-the-art schemes through the performance analyses given in the previous Section.

The state-of-the-art takes much more time to search and does not perform fuzzy and semantic keyword ranked searches which is the main contribution of our work.

Moreover, the enhanced one brings many more functionalities with a slight efficiency loss, which is tolerable in real-world scenarios. Moreover, we proved that our scheme is secure under the IND-SCP-CPA and the IND-CKA security requirements. However, there are some limitations in our system as well. For example, the attributes of users may frequently vary in the real world, while fine-grained attribute revocation and updating mechanisms are needed but are not included in our work currently. Furthermore, we tackle the single-point failure problem by setting up multiple attribute authorities, but there are probably malicious attribute authorities that can determine users’ privacy by mis-operations.

We plan to add the attribute revocation and verification mechanisms mentioned above to make the system more steady and secure.