Searchable Attribute-Based Encryption with Multi-Keyword Fuzzy Matching for Cloud-Based IoT

1  Introduction

With the rapid development of Internet of Things (IoT), pervasive IoT devices (IoTDs) have become capable of sensing their environments and processing data, thereby bridging the physical and digital worlds. IoT has been widely applied in industrial production, agriculture, public safety monitoring, smart cities, mobile healthcare, and so on. For instance, IoT-enabled medical systems utilize embedded and wearable equipments to collect health-related data for clinical diagnosis [1]. It was predicted that the growth of wearable IoTDs will reach 265.4 USD billion in 2026 [2].

To address the computational and storage limitations of IoTDs, cloud computing has emerged as a cost-effective and scalable solution. In cloud-assisted IoT systems, IoTDs like sensors transmit data to cloud servers via wireless networks. The cloud infrastructure offers abundant storage and computational resources, enabling efficient data processing and reducing the burden on IoTDs. However, outsourcing sensitive IoT data to third-party cloud servers introduces serious privacy leakage and security concerns.

Encrypting IoT data before outsourcing is a simple solution to protecting privacy. However, once data is encrypted and stored, users cannot directly retrieve specific data. Instead, they are forced to download all ciphertexts, which significantly degrades system efficiency. Searchable encryption (SE) scheme [3] was introduced to address this issue. By leveraging keyword matching, users can search encrypted data to retrieve specific information without decrypting the entire dataset. SE schemes typically bind search capabilities to a specific user’s key, limiting their effectiveness in multi-user environments. To achieve fine-grained access control of data, attribute-based encryption (ABE) mechanisms [4] have been introduced. ABE can identify users based on their attribute sets, grant each user unique identity characteristics, and provide flexible representation of access control policies at the expense of increased computational and communication costs compared to traditional encryption techniques. Attribute-based keyword-searchable encryption (ABSE) scheme [5] can address the fine-grained access control and search issue by combining ABE and SE. In ABSE schemes, data users can only retrieve and recover the plaintext if their own attribute set matches the access control policy specified by the data owner. However, most existing ABSE schemes support only exact keyword matching, which may fail to reflect a user’s actual search intent and limits the expressiveness of search strategies.

1.1 Related Work

1.1.1 Searchable Encryption

In 2000, Song et al. [3] introduced searchable encryption, enabling data users to perform keyword searches on encrypted cloud data without decryption. They implemented a symmetric searchable encryption (SSE) scheme based on symmetric cryptography. However, this scheme requires a centralized key management authority to distribute keys to users, leading to complex key distribution and management challenges. After that, although many improved SSE schemes have been introduced and formally proven secure, they are unsuitable for multi-user data-sharing cases. To address this, Boneh et al. [6] in 2004 suggested a public key encryption with keyword search (PEKS) scheme based on identity-based encryption [7] for ciphertext retrieval in public key cryptosystems. PEKS allows a sender to create searchable ciphertext using a keyword and the public key of the receiver. The receiver generates a trapdoor using its private key and sends it to cloud servers. The server returns matching ciphertexts to the user if and only if the keyword in the trapdoor matches the one in the ciphertext. Chen et al. [8] improved multi-keyword PEKS by reducing computational cost and trapdoor sizes. However, their scheme strictly enforces exact-match queries. Any input errors or formatting inconsistencies in user queries will prevent the system from returning valid results, thus severely compromising practical usability. For error-tolerant scenarios, Li et al. [9] first suggested fuzzy search PEKS using wildcards and edit distance. Servers can return results similar to the queried keywords at the expense of significantly increased storage and computational overhead. Dong et al. [10] designed a homomorphic encryption based fuzzy keyword search scheme which is more efficient than [9]. Zhang et al. [11] introduced a scalable fuzzy keyword ranked search scheme over encrypted data to achieve fuzzy keyword search for any similarity threshold with a constant storage size and accurate search results. Jiang et al. [12] proposed a fuzzy keyword searchable encryption scheme based on blockchain. Their scheme leverages blockchain to ensure equitable service payment transactions between users and cloud servers.

Most existing SE schemes exhibit expressive search policies and support only single-keyword or conjunctive keyword queries. To address expressiveness challenges in SE, Lai et al. [5] proposed an expressive PEKS (EPEKS) scheme on composite-order groups with high computational costs. Cash et al. [13] designed a searchable symmetric encryption, which supports boolean queries. Xu et al. [14] developed an efficient multi-keyword search mechanism that operates without predefined keyword fields, utilizing an anti-collusion box to enable boolean search functionality. Li et al. [15] further advanced this domain by proposing a verifiable boolean search protocol over encrypted data within an SSE framework, which guarantees forward privacy and weak backward privacy. Tong et al. [16] proposed a privacy-preserving boolean range query with temporal access control. Their scheme achieves privacy-preserving boolean range query and forward/backward derivation functions. Liu et al. [17] developed a verifiable dynamic encryption with ranked search (VDERS) scheme to secure top-K searches and verifiable results on dynamic document collections.

In terms of search privacy, Li et al. [18] introduced forward search privacy, enabling secure searches on newly added documents without leaking historical query information. Gan et al. [19] introduced a forward private SSE scheme for multiple clients. Their scheme involves no bilinear pairing computation, which has better efficiency on search. Guo et al. [20] designed a verifiable and forward-privacy SSE scheme that achieves sublinear search time and efficient file updates with guaranteed security. Cui et al. [21] proposed a dynamic and verifiable fuzzy keyword search with forward security scheme that adopts uni-gram and locality-sensitive hashing (LSH) to achieve efficient search.

1.1.2 Attributed-Based Encryption

Sahai and Waters [22] first proposed fuzzy identity-based encryption in 2005, laying the foundation for ABE as a means of achieving fine-grained access control. Building on this, Goyal et al. [4] formally defined two principal variants of ABE schemes: key-policy attribute-based encryption (KP-ABE) and ciphertext-policy attribute-based encryption (CP-ABE). In KP-ABE, secret keys are related to access control policies and ciphertexts are associated with attribute sets. CP-ABE inversely links ciphertexts to access control policies while binding secret keys to attribute sets. Bethencourt et al. [23] subsequently proposed the first concrete construction of CP-ABE. However, their implementation employed access trees as policy representation structures, resulting in limited expressive power for complex access control requirements. To improve security, efficiency, and expressiveness, Waters [24] later enhanced CP-ABE by implementing arbitrary monotonic access policies with linear secret sharing scheme (LSSS) matrices. Despite these improvements, these schemes lacked support for attribute negation. Ostrovsky et al. [25] utilized the broadcast revocation mechanism to achieve KP-ABE with negation operations, doubling the size of the ciphertext, keys, and computational costs. Lewko et al. [26] later optimized [25] by reducing public key size with longer ciphertexts.

Extensive ABE works have focused on enhancing ABE schemes. Meng et al. [27] introduced a dual-policy ABME scheme with forward security. However, their scheme requires updating the ciphertext, which is impractical in end-to-end data sharing scenarios. Luo et al. in [28] suggested a hidden policy scheme that relies on the user revocation mechanism on fog nodes, making it vulnerable if those nodes are compromised. Miao et al. [29] introduced a verifiable outsourced ABME scheme, but its lack of cryptographic agility and limited access delegation models restrict its adaptability and flexibility. Duan et al. [30] introduced a muti-authority ABME scheme. This scheme’s security depends on trusted third parties (central/attribute authorities), creating a single point of failure if these entities are compromised. Ruan et al. [31] introduced an ABME scheme that supports attribute and user revocation. However, this scheme lacks public traceability, limiting its ability to identify and trace malicious users.

1.1.3 Attributed-Based Searchable Encryption

To enable searchable encryption as well as multi-user access control, Lai et al. [5] designed a key-policy ABSE scheme combining KP-ABE with PEKS. In 2014, Zheng et al. [32] presented a verifiable attribute-based keyword search (VABKS) scheme that outsources complex search operations to cloud servers. Their design uses Bloom filters and digital signatures to ensure that only authorized users can retrieve cloud data, while enabling verification of the cloud server’s search integrity. Han et al. [33] introduced the concept of weak anonymous ABE and established a generic transformation between ABE and key-policy ABSE schemes. They also proposed a multi-user ABSE scheme for flexible collaborative searches on remotely encrypted data. However, this scheme’s reliance on composite-order groups resulted in low efficiency. Zhang et al. [34] suggested a blockchain-based anonymous ABSE scheme for data sharing. In their scheme, attributes of the access policy are hidden, ensuring the confidentiality of those attributes. In 2021, Ge et al. [35] proposed an ABSE scheme that supports both attribute-based keyword search and data sharing. Notably, this scheme enables keyword updates during the sharing phase without requiring interaction with the private key generator. Ali et al. [36] introduced a verifiable online/offline multi-keyword search (VMKS) scheme that implements outsourced encryption and decryption. In their scheme, the outsourcing part of the encryption and decryption computations significantly reduces the computational cost. Moreover, their scheme supports threshold-based search, where a match succeeds only when the intersection between the keywords in the trapdoor and those in the ciphertext exceeds the specified threshold. Miao et al. [37] designed an optimized verifiable fine-grained keyword search scheme in the static multi-owner setting (VFKSM) to significantly reduce both the ciphertext length and communication overhead. Their scheme achieves ciphertext length linear in the number of keywords, and employs a threshold signature mechanism to convert multiple signatures into a single threshold signature. Huang et al. [38] suggested an expressive multi-keyword ABSE scheme with ranked search results. While their solution supports AND/OR logical search predicates, it incurs substantial communication and computational overhead. To support attribute tracking and multi-keyword search, Huang et al. [39] proposed an ABSE scheme, which employs a new security model in its proof. However, this scheme suffers from a critical design flaw where portions of user private keys are exposed as trapdoors. Chen et al. [40] introduced a fair-and-exculpable-attribute-based searchable encryption with revocation and verifiable outsourced decryption (FE-ABSE-RV) scheme. Their scheme prevents malicious accusations from the client side against the cloud for returning incorrect results, thereby realizing fair exculpability for both ends. Tian et al. [41] designed an attribute-based heterogeneous data privacy sharing (AB-HDPS) scheme. Their scheme leverages the immutability of blockchain to achieve traceability and auditing of user access behaviors, while also implementing attribute revocation by subset-cover trees.

1.2 Contributions

The above ABSE schemes have limited search capabilities, supporting only single-keyword or simple conjunctive keyword searches. Issues on existing ABSE schemes are summarized as follows.

•   Only support exact match. In most existing ABSE schemes, the data owner specifies a set of keywords for their data. The cloud server will return the search ciphertext when keywords in the ciphertext and keywords in the trapdoor match exactly (i.e., both keyword sets are identical or the keyword set in the trapdoor is a subset of the keyword set in the ciphertext). This exact match search method exhibits very poor fault tolerance, as even a single erroneous keyword input (such as a typographical error) will result in failed searches.

•   No forward security. Existing ABSE schemes require data users to create a trapdoor for querying encrypted data stored on cloud servers. However, third-party cloud servers are often untrusted. After completing the search, the cloud server can store these trapdoors and perform unauthorized future searches. The cloud server can verify whether newly added encrypted data matches previous search queries, which may result in the frequency attack issue [42] and expose keyword privacy.

•   High computational and communication costs. In most existing verifiable ABSE schemes, data users needs download the partially decrypted ciphertext to verify the validity of outsourced decryption. This means that even if the cloud server performs search and partial decryption operations, users still need to download the whole ciphertext. This increases the user’s bandwidth and communication overhead, which is not suitable for resource-constrained IoT applications.

To address these challenges, we introduced an attribute-based multi-keyword fuzzy searchable encryption with forward ciphertext search (FCS-ABMSE) scheme. FCS-ABMSE supports multi-keyword fuzzy search based on the number of elements of the intersection keyword sets, forward security, and outsourced decryption and verification. The main functions are listed below.

•   Multi-keyword fuzzy matching: Our scheme allows ciphertext and query keywords to have a certain degree of lexical deviation rather than being restricted to exact matching for search fault tolerance in real-world scenarios.

•   Forward security: Even if query a trapdoor is leaked, the scheme can ensure that attackers cannot access historical encrypted data.

•   Outsourced decryption and verification: Outsourced encryption and verification can reduce the computational cost of data uses, and mitigate the risk of the cloud server tampering with query results or altering data.

1.3 Organization

The rest of this paper is organized as follows. Section 2 outlines cryptographic preliminaries. Section 3 presents the system model. Section 4 explains the proposed FCS-ABMSE scheme with formal security analysis, followed by performance evaluations in Section 5. Section 6 presents an enhanced scheme while Section 7 concludes this paper with future work.

2  Preliminaries

This section describes essential cryptographic preliminaries employed in our scheme.

2.1 Notations

Notations used throughout the paper are defined in Table 1.

2.2 Bilinear Map

Definition 1. Let G1, G2, and GT be three cyclic groups of prime order p, with g1 denoting a generator of G1 and g2 denoting a generator of G2. A map e:G1×G2→GT is said to be a bilinear map if it satisfies the following properties:

•   For any υ,ν∈Zp∗, e(g1υ,g2ν)=e(g1,g2)υν;

•   e(g1,g2)≠1GT, where 1GT denotes the identity of GT;

•   For any υ,ν∈Zp∗, e(g1υ,g2ν) can be computed efficiently.

A bilinear map e:G1×G2→GT is symmetric if G1=G2(=G); Otherwise, it is asymmetric.

2.3 Difficult Problems

The security of the proposed scheme relies on two difficult problems.

Definition 2. Let (G,GT) be prime order cyclic groups. The decisional bilinear Diffie-Hellman (DBDH) problem is to determine if T=e(g,g)abc, for a,b,c∈Zp∗ and T∈GT.

Definition 3. Let (G,GT) be prime order cyclic groups. The decisional q-parallel bilinear Diffie-Hellman (q-parallel-BDHE) problem is to determine whether T=e(g,g)βq+1, for β,s,b1,…,bq∈Zp∗, (g,y~) and T∈GT, where

y~=(g,gs,gβ,…,gβq,g(βq+2),…,g(β2q)∀1≤j≤q,gsbj,ga/bj,…,g(aq/bj),g(aq+2/bj),…,g(a2q/bj)∀1≤j,k≤q,k≠jg(asbk/bj),…,g(aqsbk/bj)).

2.4 Linear Secret Sharing Scheme

Definition 4. A linear secret sharing scheme (LSSS) for a set of participants 𝒫 is considered linear if it can meet the following conditions:

•   Each participant receives a share represented as a vector with components in Zp∗.

•   There exists a matrix M with ℓ rows and n columns. Each row i of M (for i∈[ℓ]) is associated with a participant labeled as xi∈𝒫. To share a secret, select a column vector v→=(s,v2,…,vn), where s∈Zp∗ is the secret and v2,…,vn∈Zp∗ are random elements. The product Mv→ produces ℓ shares of the secret s. Specifically, the share corresponding to participant xi is given by Miv, where Mi denotes the i-th row of M.

2.5 Key Derivation Function

Definition 5. A key derivation function (KDF) accepts a secret k and a length l, and then generates a cryptographic key key∈{0,1}l.

Definition 6. A KDF is said to be secure if the advantage AdvKDF𝒜d=|Pr[𝒜d(KDF(k,l))=1]−Pr[𝒜d(R)=1]| is negligible for any polynomial-time adversary 𝒜d, where R∈{0,1}l is a random cryptographic key chosen from the key space.

2.6 Data Encapsulation Mechanism

Definition 7. A data encapsulation mechanism (DEM) is a symmetric encryption scheme consisting of two algorithms:

•   Enc: Input a symmetric key k∈𝒦 and a message M, output a ciphertext CM, where 𝒦 is the key space.

•   Dec: Input k∈𝒦 and CM, output the decrypted message m or a special symbol ⊥ to indicate a decryption failure.

Definition 8. A DEM Π=(Enc,Dec) is said to achieve indistinguishability under chosen-ciphertext attack (IND-DEM-CCA) security if the following advantage AdvDEMCCA(𝒜d) is negligible for any polynomial-time adversary 𝒜d:

AdvDEMCCA(𝒜d)=|Pr[b=b′:(M0,M1)←𝒜d(1η), b←R{0,1}, K←R𝒦,C←DEM.Enc(K,Mb), b′←𝒜dODec(C)]−12|,

where η is the security parameter and ODec is the decryption oracle.

2.7 Commitment Scheme

Definition 9. A commitment scheme is a cryptographic protocol that is specified by the two following algorithms:

•   Commit: Given an input string s∈{0,1}∗, the algorithm outputs a commitment com and a de-commitment dom;

•   Open: Given a pair (com,dom), the algorithm outputs 1 if the pair is valid, or 0 otherwise.

Definition 10. A commitment scheme Φ=(Commit,Open) is computationally hiding if the following advantage AdvHiding(𝒜d) is negligible for any polynomial-time adversary 𝒜d:

AdvHiding(𝒜d)=|Pr[b=b′: (s0,s1)←𝒜d(1η), b←R{0,1}, com←Commit(sb),b′←𝒜d(com)]−12|,

where η is the security parameter.

2.8 Message Authentication Code

Definition 11. A message authentication code (MAC) is a cryptographic scheme that is specified by the two following algorithms:

•   Mac: Given a symmetric key k∈𝒦 and a message m, the algorithm outputs a MAC mac, where 𝒦 is the key space.

•   MacVrfy: Given a symmetric key k∈𝒦, a message m and a MAC mac, the algorithm outputs 1 if mac=Mac(k,m), or 0 otherwise.

Definition 12. A MAC scheme Ψ=(Mac,MacVrfy) is said to satisfy existential unforgeability under chosen-message attack (EU-CMA) if the following advantage AdvDEMCCA(𝒜d) is negligible for adversary 𝒜d with polynomial-time:

AdvMAC𝒜d=Pr[⟨m′,mac′⟩≠⟨m,mac⟩ ∧ MacVrfy(k,m′,mac′)=1|k←𝒦,m←𝒜d(k),mac=Mac(k,m),⟨m′,mac′⟩←𝒜d(m,mac)], where 𝒦 is the key space.

2.9 0/1—Encoding Approach

In the proposed scheme, we compare two time points t and t′ using the 0/1-encoding approach [43]. The 0/1-encoding approach consists of two encoding algorithms:

•   0-encoding: Given a n-bit binary integer t=tntn−1...t1∈{0,1}n, the algorithm outputs a set St0={tntn−1⋯ti+11|ti=0,i∈[1,n]} that contains at most log2n elements;

•   1-encoding: Given a n-bit binary integer t=tntn−1...t1∈{0,1}n, the algorithm outputs a set St1={tntn−1⋯ti|ti=1,i∈[1,n]} that contains at most log2n elements.

According to [43], for any two integer values t and t′, t′>t holds if and only if St′1∩St0≠∅.

3  System Model, Synax, and Security Definition

This section gives the system model, synax, and security definitions of the FCS-ABMSE scheme in turn.

3.1 System Model

As shown in Fig. 1, the proposed FCS-ABMSE scheme involves the following six different entities:

•   Central Authority (CA): The CA generates the system’s global parameters and master key, and issues attribute keys to users.

•   Sensor’s Owner (SO): The SO encrypts keywords offline and stores offline ciphertexts of keywords onto sensors.

•   Sensors (SN): The SN is responsible for collecting user data, creating searchable ciphertexts, and then sending them to the CS.

•   Data User (DU): The DU retrieves matching ciphertext from the cloud server using a trapdoor, downloads them, and then decrypts the data using their decryption key.

•   Cloud Server (CS): The CS provides ciphertexts storage and retrieval services, while assisting DUs with partial decryption of ciphertexts.

•   System Clock (SC): The SC provides the current system timestamp in ciphertext and trapdoor generation.

Figure 1: System model of FCS-ABMSE

The interaction among the entities proceeds as follows: First, the CA distributes the system’s global parameters to other entities and transmits the attribute keys to the DU. Second, the SC transmits the current system timestamp to the SN and the DU. Third, the SO transmits the offline ciphertext to the SN. Then, the SN transmits the online ciphertext to the CS. After that, the DU transmits the trapdoor to the CS. Last, the CS stores the ciphertexts received from the SN, performs search operations upon receiving trapdoors from the DU, and returns pre-decrypted results to the DU.

3.2 Syntax of FCS-ABMSE

The FCS-ABMSE scheme is defined by the following nine algorithms:

(1) Setup(η,Ua,Uw): The CA executes the algorithm to generate the global parameter set ps. Given a security parameter η, the system global attribute set Ua, and the system global keyword set Uw, this algorithm outputs the global parameter set ps and a master key msk.

(2) ASKGen(ps,msk,attdu): The CA executes the algorithm to issue an attribute key for each DU. Given ps, msk, and an attribute set attdu⊆Ua, this algorithm outputs an attribute key askdu.

(3) DUKeyGen(ps,askdu): The DU executes the algorithm to generate a private key and a ciphertext conversion key. Given ps and an attribute key askdu, this algorithm outputs a private key skdu and a ciphertext conversion key tfdu.

(4) offEncrypt(ps): The SO executes the algorithm to create offline ciphertexts. Given ps, the algorithm outputs an offline ciphertext ctoff.

(5) onEncrypt (ps,m,ctoff,ws,Λ,t): The SN executes the algorithm to create online ciphertexts. Given ps, a message m, the offline ciphertext ctoff, a keyword set ws⊆Uw, an access control policy Λ, and the current system time t, this algorithm outputs an online ciphertext cton.

(6) TrapGen(ps,thd,ws′,skdu,t′): The DU executes the algorithm to create a trapdoor. Given ps, a search threshold thd, a search keyword set ws′⊆Uw, the DU’s private key skdu, and current system time t′, this algorithm outputs a trapdoor td.

(7) Search(ps,cton,td,tfdu): The CS executes the algorithm to make ciphertext searches and pre-decryptions. Given ps, an online ciphertext cton, a trapdoor td, and a ciphertext conversion key tfdu, this algorithm outputs a conversion ciphertext cttrans and a pre-decryption ciphertext pctm if cton matches td; otherwise, it returns ⊥.

(8) ResultVrfy(ps,cttrans,skdu): The DU executes the algorithm to check the validness of the search results and create corresponding decryption keys. Given ps, a conversion ciphertext cttrans, and the DU’s private key skdu, this algorithm outputs a decryption key dk if cttrans is valid; otherwise, it returns an invalid flag ⊥.

(9) Decrypt (ps,dk,pctm): After verifying the validness of cttrans, the DU downloads pctm and executes the algorithm to complete final decryption. Given ps, a decryption key dk, and a pre-decryption ciphertext pctm, this algorithm outputs a message m, or ⊥ if decryption fails.

Definition 13. An FCS-ABMSE scheme is correct if for a message m, keyword number n, DU’s attribute set attdu⊆Uw, search threshold thd, and two keyword sets ws⊆Uw and ws′⊆Uw such that |ws∩ws′|>thd, askdu=ASKGen(ps,mtk,attdu), (skdu,tfdu)=DUKeyGen(ps,askdu), ctoff=offEncrypt(ps),cton= onEncrypt(ps,m,ctoff,ws,Λ,t), td=TrapGen(ps,thd,ws′,skdu,t′), (cttrans,pctm)=Search(ps,cton, td,tfdu), and dk=ResultVrfy(ps,cttrans,skdu), then m=Decrypt(ps,dk,pctm).

3.3 Security Definitions of FCS-ABMSE

An FCS-ABMSE scheme must satisfy the two following security notions: indistinguishability of ciphertext under the chosen keyword attack (IND-CKA) and indistinguishability of ciphertext under the chosen plaintext attack (IND-CPA).

IND-CKA. The security is defined by a game between an adversary 𝒜d and a challenger ℬ:

Initialization. 𝒜d submits an access control policy Λ∗ to ℬ.

Setup. ℬ runs Setup(η,U) to generate ps and msk, and sends ps to 𝒜d.

Phase 1. 𝒜d adaptively queries the oracles with the restriction that attdu does not satisfy Λ∗. ℬ answers as follows:

•   𝒪ask: Given an attribute set attdu, ℬ runs ASKGen(ps,msk,attdu) to generate askdu. Then, it returns askdu to 𝒜d.

•   𝒪tf: Given an attribute set attdu, ℬ runs ASKGen(ps,msk,attdu) to generate askdu, and DUKeyGen(ps,askdu) to generate tfdu. Then, it returns tfdu to 𝒜d.

•   𝒪sk: Given an attribute set attdu, ℬ runs ASKGen(ps,msk,attdu) to generate askdu, and DUKeyGen(ps,askdu) to generate skdu. Then, it returns skdu to 𝒜d.

•   𝒪td: Given a search threshold thd, a keyword set ws′, an attribute set attdu, and a time point t′, ℬ first obtains skdu via 𝒪sk, then runs TrapGen(ps,thd,ws′,skdu,t′) to generate a trapdoor td. Finally, it returns td to 𝒜d.

Challenge. 𝒜d outputs two keyword sets ws0 and ws1 of equal length, a message m∗, and a timestamp t∗. ℬ runs offEncrypt(ps) to generate ctoff∗. Then, ℬ randomly selects v∈{0,1} and runs onEncrypt(ps,m∗,ctoff∗,wsv,Λ∗,t∗) to generate a challenge ciphertext cton∗. Finally, ℬ sends cton∗ to 𝒜d.

Phase 2. This phase is identical to Phase 1.

Guess. 𝒜d outputs a guess v′. If v=v′, it wins the game with advantage Adv𝒜dIND−CKA=|Pr[v=v′]−1/2|.

Definition 14. An FCS-ABMSE scheme is IND-CKA secure if Adv𝒜dIND-CKA is negligible for all polynomial-time adversaries 𝒜d.

IND-CPA. The security is defined by a game between an adversary 𝒜d and a challenger ℬ:

Initialization. Identical to the initialization process in the IND-CKA security game.

Setup. Identical to the setup process in the IND-CKA security game.

Phase 1. Identical to Phase 1 in IND-CKA security game, except that 𝒜d can not make queries to the oracle 𝒪td.

Challenge. 𝒜d outputs two messages m0 and m1 of equal length, a keyword set ws∗ and a time point t∗. ℬ first runs offEncrypt(ps) to generate ctoff∗. ℬ randomly selects v∈{0,1} and runs onEncrypt(ps, mv, ctoff∗, ws∗, Λ∗, t∗) to generate a challenge ciphertext cton∗. ℬ sends cton∗ to 𝒜d.

Phase 2. Same as the IND-CKA security game, except that 𝒜d cannot make queries to the oracle 𝒪td.

Guess. 𝒜d outputs a guess v′. If v=v′, it wins the game with advantage Adv𝒜dIND−CPA=|Pr[v=v′]−1/2|.

Definition 15. An FCS-ABMSE scheme is IND-CPA secure if Adv𝒜dIND-CPA is negligible for all polynomial-time adversaries 𝒜d.

4  The Proposed FCS-ABMSE Scheme

This section presents the concrete construction of the FCS-ABMSE scheme, along with its correctness analysis and security proof.

The proposed FCS-ABMSE scheme is described as follows. (1) Setup(η,Ua,Uw): Given η, Ua and Uw, it is executed as follows:

•   Generate two prime p-order groups (G,GT) and e:G×G→GT;

•   Randomly choose g,g0,g1∈G and α,β,γ∈Zp∗, compute X=gβ, Y=gγ, E1=e(gα,g), E2=e(X,g1), and choose a hash function H:{0,1}∗→Zp∗;

•   For each attribute in Ua, select a random element hi∈G where i∈[1,|Ua|];

•   Choose an IND-DEM-CCA secure data encapsulation scheme Π=(Enc,Dec) with symmetric key space {0,1}l, a computationally hiding commitment scheme Φ=(Commit,Open), an EU-CMA secure message authentication code scheme Ψ=(Mac,MacVrfy) and a secure key derivation function KDF:GT→{0,1}l;

•   Output ps=(p,G,GT,e,g,g0,g1,X,Y,E1,E2,h1,…,h|Ua|,H,Π,Φ,Ψ,KDF) and msk=(α,β,γ).

(2) ASKGen(ps,msk,attdu): Given ps, msk=(α,β,γ) and attdu, it is executed as follows:

•   Randomly select z∈Zp∗, compute k1=gαgβz and k2=gz;

•   For each x∈attdu, compute k0=g1βg0γ∑H(hx) and kx=hxz;

•   Output askdu=(k0,k1,k2,{kx}x∈attdu).

(3) DUKeyGen(ps,askdu): Given askdu=(k0,k1,k2,{kx}x∈attdu), it is executed as follows:

•   Randomly select λ∈Zp∗, compute K1=k1λ=gαλgλβz and K2=k2λ=gλz;

•   For each x∈attdu, compute Kx=kxλ=hxλz;

•   Output skdu=(askdu,λ) and tfdu=(K1,K2,{Kx}x∈attdu).

(4) OffEncryption(ps): Given ps, it is executed as follows:

•   For each j∈[1,n] where n=|Uw|, randomly select uj∈Zp∗, and compute Wj′=E2−uj;

•   Output ctoff=({uj,Wj′}j∈[1,n]).

(5) OnEncryption(ps,m,ctoff,ws,Λ,t): Given ps, m, ctoff=({uj,Wj′}j∈[1,n]), ws={w1,w2,…,wn1}, Λ=(M,ρ) and t where M∈Zprow×col is a row×col matrix and ρ is a function mapping each row of M to an attribute in Ua, it is executed as follows:

•   Randomly select k∈GT and run KDF(k,l) to extract a symmetric key key∈{0,1}l, compute CM=Π.Enc(key,m) and mac=Ψ.Mac(key,CM);

•   Run Φ.Commit(m||k) to generate (com,dom) and compute ccom=Π.Enc(key,dom);

•   Randomly select s,v2,v3,…,vrow∈Zp∗, and set v~=(s,v2,v3,…,vrow)⊥;

•   Compute C1=gs and C2=Ys;

•   Randomly select d∈Zp∗, and compute C3=k⋅E1s and C4=gd;

•   For each i∈[1,row], compute μi=Miv~ and Ci=gβμi⋅hρ(i)−d, where Mi is the i-th row of M;

•   Set CV=(CM,mac,com,Ccom) and C=(C1,C2,C3,C4,{Ci}i∈[1,row]).

•   Run the 0-encoding algorithm to transform t into a set T;

•   For each τ∈T, compute Iτ=g1−sH(τ);

•   For each j∈[1,n1], compute Wj=H(wj)+uj−s;

•   Set I=(T,{Iτ}τ∈T,{Wj,Wj′}j∈[1,n1]);

•   Set cton=(CV,C,I).

(6) TrapGen(ps,thd,ws′,skdu,t′): Given ps, thd, ws′={w1′,w2′,…,wn2′}, skdu=(k0,k1,k2,{kx}x∈attdu,λ) and t′, it is executed as follows:

•   Run 1-encoding algorithm to transform t′ into a set T′;

•   Randomly select κ∈Zp∗ and compute tτ′=k0⋅g1H(τ′)κ for each τ∈T′;

•   Compute t1=gλ, t2=gκ, t3=g0λ, and t4=λκ;

•   For each j∈[1,n2], compute W~j=H(E2H(wj′)+λ);

•   Set td=(thd,T′,t1,t2,t3,t4,{tτ}τ∈T′,{W~j}j∈[1,n2]).

(7) Search&Trans(ps,cton,td,tfdu): Given ps, cton, td and tfdu, it is executed as follows:

•   If attdu associated with tfdu satisfies the access structure in cton and T∩T′≠∅, randomly select y∈T∩T′ and compute: IV=e(C1⋅t1,ty)⋅e(t2,Iy)⋅e(g−t4,g1H(y))e(grΣH(hx),t3)⋅e((C2)ΣH(hx),g0), where x∈attdu;

•   Check whether |{H(IV⋅E2Wj⋅Wj)}j=1n1∩{W~j}j=1n2|>thd;

•   If not, output ⊥; else, for all i∈N where N={i:ρ(i)∈attdu}, find {ωi}∈Zp∗ that satisfy ∑i∈NωiMi=(1,0,0,…,0), compute TF=e(K1,C1)e(∏i∈NCiωi,K2)⋅e(∏i∈NKρ(i)ωi,C4);

•   Output cttrans=(Ccom,com,C3,TF) and pctm=(mac,CM).

(8) ResultVrfy(ps,cttrans): Given ps and cttrans, it is executed as follows:

•   Before downloading the decryption ciphertext pctm=(mac,CM), compute k=C3(TF)1/λ,key=KDF(k,l),dom′=Π.Dec(key,Ccom) and run Φ.Open(com,dom′) to verify whether dom′ and com matches.

•   If Φ.Open outputs 1, it indicates successful validation. Then download decryption ciphertext pctm and output the decryption key dk=key. If Φ.Open outputs 0, output ⊥.

(9) Decrypt(ps,dk,pctm): Given ps, dk, and pctm=(mac,CM), it is executed as follows:

•   Compute m=Π.Dec(dk,CM) and mac′=Ψ.MacVrfy(dk,m,CM);

•   If mac is equal to mac′, output m; otherwise, output ⊥.

4.1 Correctness Analysis

According to the scheme description, we can deduce that

IV=e(C1⋅t1,ty)⋅e(t2,Iy)⋅e(g−t4,g1H(y))e(gγΣH(hx),t3)⋅e((C2)ΣH(hx),g0)=e(gs⋅gλ,g1βg0γΣH(hx)⋅g1H(y)⋅κ)⋅e(gκ,g1−s⋅H(y))⋅e(g−λκ,g1H(y))e(gγ⋅ΣH(hx),g0λ)⋅e(gγs⋅ΣH(hx),g0)=e(gs+λ,g1β⋅g0γΣhx⋅g1H(y)κ)⋅e(gλ+s,g1−κ⋅H(y))e(gγ⋅Σhx,g0λ+s)=e(gβ,g1)s+λ=E2s+λ.(1)

Clearly, if |ws∩ws′|>thd, then we have

|{H(IV⋅E2Wj⋅Wj′)}j=1n1∩{W~j}j=1n2|=|{H(E2s+λ⋅E2H(wj)−s+uj⋅E2−uj)}j=1n1∩{H(E2H(wj)+λ)}j=1n2|=|{H(E2H(wj)+λ)j=1n1∩H(E2H(w~j)+λ)}j=1n2|>thd.(2)

Therefore, keyword search works correctly. In addition, we can deduce that

C3(TF)1/λ=k⋅E1s⋅e(∏i∈NCiωi,K2)1/λ⋅e(∏i∈NKρ(i)ωi,C4)1/λe(K1,C1)1/λ=k⋅E1s⋅e(∏i∈Ngβμi⋅ωi⋅hρ(i)−d⋅ωi,gz)⋅e(∏i∈Nhρ(i)z⋅ωi,gd)e(gα⋅gβz,gs)=k⋅E1s⋅e(gβs,gz)⋅e(∏i∈Nhρ(i)−d⋅ωi,gz)⋅e(∏i∈Nhρ(i)z⋅ωi,gd)e(gα⋅gβz,gs)=k⋅e(g,g)αse(g,g)αs=k.(3)

4.2 Security Proofs

We demonstrate that our FCS-ABMSE scheme meets the IND-CKA and the IND-CPA security.

Theorem 1. If a polynomial-time adversary 𝒜d breaks the IND-CKA security of our scheme with advantage ϵ, there exists an algorithm ℬ solving the DBDH problem with advantage ϵ.

Proof. Given a random instance of the DBDH problem (p,G,GT,e,g,ga,gb,gc,Z), ℬ interacts with 𝒜 to determine whether Z=e(g,g)abc as follows:

Initialization. 𝒜d submits a policy Λ∗=(M∗,ρ∗), where M∗ is a row∗ columns matrix.

Setup. ℬ first sets X=gb, g1=gc, and E2=e(gb,gc). Then, it sets other parameters (g0,Y,E1,h1,…,h|U|,

H,Π,Φ,Ψ,KDF) as in the Setup algorithm. Finally, it returns ps=(p,G,GT,e,g,g0,g1,

X, Y,E1,E2,h1,…,h|U|,H,Π,Φ,Ψ,KDF) to 𝒜d.

Phase 1. ℬ maintains a key list ℒkey={⟨attdu,askdu,tfdu,skdu⟩} and a trapdoor list ℒtd={⟨attdu,ws′,td⟩}, both of which are initially empty. ℬ answers 𝒜d’s queries as follows:

•   𝒪ask: Given an attribute set attdu, ℬ returns askdu if attdu already exists in a record ⟨attdu,askdu,tfdu, skdu⟩ on the list ℒkey. Otherwise, ℬ randomly selects z∈Zp∗, calculates k0=g1bg0γ∑hx,k1=gαgbz, k2=gz, kx=hxz, for all x∈attdu. Finally, ℬ returns the attribute key: askdu=(k0,k1,k2,{kx}x∈attdu) to 𝒜d and adds ⟨attdu,askdu,−,−⟩ to the list ℒkey.

•   𝒪tf: Given an attribute set attdu, ℬ returns tfdu if tfdu already exists in a record ⟨attdu,askdu,tfdu, skdu⟩ on the list ℒkey. Otherwise, ℬ checks the list to see if askdu corresponding to attdu exists. If so, ℬ selects λ∈Zp∗ and calculates: K1=k1λ,K2=k2λ,Kx=kxλ,∀x∈attdu. It generates the conversion key: tf=(K1,K2,{Kx}x∈attdu), and the private key: sk=(ask,λ). If ask does not exist, ℬ first performs 𝒪askdu to obtain askdu, and then generates the corresponding tfdu and sk according to the above steps. Finally, ℬ returns the conversion key tfdu to 𝒜d and adds the tuple ⟨attdu,askdu,tfdu,skdu⟩ to the list ℒkey.

•   𝒪sk: Given an attribute set attdu, ℬ returns tfdu if tfdu already exists in a record ⟨attdu,askdu,tfdu, skdu⟩ on the list ℒkey. Otherwise, ℬ performs 𝒪tf to generate the conversion key: tfdu=(K1,K2,{Kx}x∈attdu), and the private key:sk=(ask,λ). Finally, ℬ returns skdu to 𝒜d, and adds the tuple ⟨attdu,askdu,tfdu,skdu⟩ to the list ℒkey.

•   𝒪trapdoor: Given a threshold value thd, a keyword set ws′={w1′,w2′,…,wn2′}, an attribute set attdu, and time t′, ℬ returns td if td already exists in a record ⟨attdu,ws′,td⟩ on the list ℒtd. Otherwise, ℬ performs 𝒪ask and 𝒪sk to obtain attribute keys askdu and private keys sk. ℬ runs the 1-encoding algorithm to transform the time t′ into a set T′. For each τ′∈T′, ℬ randomly chooses κ∈Zp∗, and computes tτ′=k0⋅g1H(τ′)κ. ℬ computes t1=gλ,t2=gκ,t3=g0λ,t4=λκ. For each j=1,…,n2, it compute:Wj′=H(E2H(wj′)+λ). Finally, it outputs the trapdoor td=(T′,t1,t2,t3,t4,{tτ′}τ′∈T′,thd,{Wj′}1n2) to 𝒜d and adds td to the list ℒtd.

Challenge. 𝒜d outputs two keyword sets with the same number of keywords ws0={w0,1,…,w0,n1} and ws1={w1,1,…,w1,n1}, a message m∗, an access control policy Λ∗=(M∗,ρ∗), and a time t∗, where M∗ is a col∗×row∗ matrix, and ρ∗ is a function that maps the rows of M∗ to attributes. ℬ randomly picks a coin v∈{0,1} and encrypts the keyword set wsv. The following steps are executed: