images
Computer Modeling in Engineering & Sciences
images

DOI: 10.32604/cmes.2023.043589

ARTICLE

Blockchain-Based Certificateless Bidirectional Authenticated Searchable Encryption Scheme in Cloud Email System

Yanzhong Sun1, Xiaoni Du1,*, Shufen Niu2 and Xiaodong Yang2

1College of Mathematics and Statistics, Northwest Normal University, Lanzhou, 730070, China
2College of Computer Science and Engineering, Northwest Normal University, Lanzhou, 730070, China
*Corresponding Author: Xiaoni Du. Email: ymldxn@126.com
Received: 06 July 2023; Accepted: 23 October 2023; Published: 11 March 2024

Abstract: Traditional email systems can only achieve one-way communication, which means only the receiver is allowed to search for emails on the email server. In this paper, we propose a blockchain-based certificateless bidirectional authenticated searchable encryption model for a cloud email system named certificateless authenticated bidirectional searchable encryption (CL-BSE) by combining the storage function of cloud server with the communication function of email server. In the new model, not only can the data receiver search for the relevant content by generating its own trapdoor, but the data owner also can retrieve the content in the same way. Meanwhile, there are dual authentication functions in our model. First, during encryption, the data owner uses the private key to authenticate their identity, ensuring that only legal owner can generate the keyword ciphertext. Second, the blockchain verifies the data owner’s identity by the received ciphertext, allowing only authorized members to store their data in the server and avoiding unnecessary storage space consumption. We obtain a formal definition of CL-BSE and formulate a specific scheme from the new system model. Then the security of the scheme is analyzed based on the formalized security model. The results demonstrate that the scheme achieves multi-keyword ciphertext indistinguishability and multi-keyword trapdoor privacy against any adversary simultaneously. In addition, performance evaluation shows that the new scheme has higher computational and communication efficiency by comparing it with some existing ones.

Keywords: Cloud email system; authenticated searchable encryption; blockchain-based; designated server test; multi-trapdoor privacy; multi-ciphertext indistinguishability

1  Introduction

Email systems have become an essential component of modern communication tools and revolutionized the way we conduct business, education, and personal communication, facilitating effective and efficient communication. However, the widespread usage of email has raised significant concerns regarding email security. Searchable encryption [1], as a promising security solution, has been successfully applied in many fields, including email systems. It can not only provide users with convenient search and data management methods while preserving data privacy and security but also enrich the overall user experience while safeguarding email confidentiality. That is, searchable encryption technology has become an indispensable security protection measure within email systems.

Public key Encryption with Keyword Search (PEKS) is a form of searchable encryption within the asymmetric category proposed by Boneh et al. [2] which optimises the security and privacy of email and improves users’ experience and the system performance. Since then, several PEKS schemes with varying functionality have been proposed including secure channel-free PEKS [3] and certificateless PEKS [4,5]. Although these schemes offer numerous keyword search methods suitable for encrypted email systems, there are still some security issues to be concerned with, specifically the Keyword Guessing Attack (KGA) [6]. In fact, the limited keyword space and low entropy render most PEKS schemes vulnerable to both online and offline KGA.

To defend against KGA, Huang et al. [7] introduced the Public Key Authenticated Encryption with Keyword Search (PAEKS) as a new variant of PEKS in 2017 and proved that the proposed PAEKS scheme achieved Ciphertext Indistinguishability (CI)-secure and Trapdoor Privacy (TP)-secure. Considering against chosen multi-keyword attacks and multi-keyword guessing attacks, Qin et al. [8] presented a new security model as Multi-Ciphertext Indistinguishability (MCI) in 2020 and Pan et al. formalized Multi-Trapdoor Privacy (MTP) in [9], which are the enhancement of CI-secure and TP-secure, respectively.

It is obvious that all PEKS/PAEKS systems cannot avoid the inherent burden of certificate management and key escrow issues due to their reliance on public key infrastructure cryptosystem or identity-based cryptosystem. A common approach to overcome these problems is to incorporate the PEKS/PAEKS system in certificateless public key cryptography (CL-PKC) [10]. As a result, Peng et al. [5] proposed the first certificateless PEKS scheme and He et al. [11] developed the first certificateless PAEKS scheme. However, the CL-PKC scheme still suffers from two types of attackers. The distributed nature of blockchain makes it impossible to tamper the data stored on the chain, which solves the trust problem and guarantees data security. Therefore, in CL-PKC, in order to avoid forgery attacks launched by attackers using public parameters, part of the user’s private key is created by a blockchain smart contract [12].

All of the above improvements to PEKS/PAEKS including the enhancement of security and the introduction of certificateless cryptosystem have significantly optimized their application for protecting the data security and privacy, enhancing user experience and improving system performance. Moreover, Zhang et al. [13] highlighted a crucial aspect of encrypted email systems: users must not only search for encrypted emails received from others but also retrieve encrypted emails sent to others, and they developed a new cryptographic approach named Public-key Encryption with Bidirectional Keyword Search (PEBKS). Inspired by the above ideas, it is imperative to develop a certificateless authenticated bidirectional searchable encryption scheme with a designated server test that can achieve both MCI and MTP security.

1.1 Our Contributions

The following is a list of the main contributions of this paper:

•   Considering the actual application scenario of cloud email system that the data owner also needs to retrieve emails with target keywords. We apply the bidirectional searchable functionality to CL-PAEKS cryptosystem by introducing a trapdoor generation algorithm for the data owner, put forward a cryptographic concept named CL-BSE. This allows the data owner not only to encrypt and send an email to the cloud email server, but also to generate its own trapdoor for specified keyword and retrieve the corresponding email.

•   On the one side, the scheme in this paper achieves bidirectional searchable functionality, on the other side, it establishes dual authentication functions. In the process of generating the ciphertext with the keyword, the data owner not only uses the public key of the data receiver, but also uses his own private key. Similarly, the data receiver uses both his own private key and the public key of the data owner to generate the corresponding trapdoor, which authenticates the identity of the data owner. Meanwhile, the blockchain can also verify the legitimacy of the ciphertexts, which effectively saves the storage space. Furthermore, the scheme satisfies designated server test which makes secure channel free.

•   We formalize the definition of the new cryptographic concept CL-BSE, then give a concrete construction of the scheme under the bilinear pairing. Meanwhile, we formally define the security model of CL-BSE scheme and show that in the random oracle model, it is able to achieve both MCI and MTP security levels against inside KGA under the CBDH hardness assumption. Through the experimental comparison, our scheme has more advantages and higher efficiency in computation and communication costs.

1.2 Organization

The rest of this paper is arranged as follows. The next section presents some basic symbols and notations, including bilinear pairing and hardness assumption. Section 3 illustrates the framework of our scheme including the system model in 3.1, the formalized definition in 3.2 and the formalized security model in 3.3. Section 4 is the concrete construction of our CL-BSE scheme and Section 5 guarantees the security of the new scheme. In Section 6, we analyze the performance by comparing it with existing works. Eventually, we draw a conclusion of the paper in Section 7.

1.3 Related Works

Boneh et al. [2] presented the first PEKS scheme in 2014, which effectively solved the distribution and management of the secret-key in the symmetric searchable encryption (SSE) cryptosystem [14–16]. However, Baek et al. [3] pointed out that the trapdoor transmission channel must be secure in [2], and then proposed a secure channel free PEKS (SCF-PEKS) scheme by giving the server a public/private key pair so that only the designated server could execute the test algorithm. Rhee et al. in [17] improved the trapdoor security of [3] and then constructed a new SCF-PEKS scheme called dPEKS under the new security model. Nevertheless, Byun et al. [6] claimed that both PEKS and SCF-PEKS schemes were vulnerable to (offline) KGA and a variety of improved PEKS and SCF-PEKS schemes [18–20] were proposed to overcome the series security threats in the years including [17]. Unfortunately, it turns out that none of them can really resist the offline KGA [21]. What’s worse is that Yau et al. [22] pointed out that these existing PEKS schemes suffered from another generic attack called online KGA or inside KGA in 2013.

In order to defend against both online KGA and offline KGA, Huang et al. [7] introduced a new primitive of PAEKS and proposed the first PAEKS scheme in 2017. The essence of PAEKS is to insert the data owner’s public/private key pair into PEKS so that it can authenticate the keyword while encrypting it. Meanwhile, they defined the security as TP and CI for trapdoor and ciphertext, respectively. After that, Noroozi et al. [23] pointed out some weaknesses of the previous security in terms of multi-user settings. In 2020, Qin et al. [8] found that the CI & TP security in [7] does not protect the information whether two different files extract identical keywords or the same file contains how many identical keywords so they improved the security model as MCI, and they proposed a PAEKS scheme satisfying MCI instead of MTP. In 2021, Pan et al. claimed that their new scheme in [9] achieved both MCI and MTP secure until Cheng et al. [24] presented an effective attack method on MTP. In addition to the security efforts, contributions to the functionality of PEKS/PAEKS have also been made. Fuhr et al. [25] and Hofheinz et al. [26] inserted the ciphertext decryptable function on PEKS schemes in different types of models. Zhang et al. [13] observed that in practical application, a data owner also needed to retrieve encrypted files containing specified keywords, then proposed a cryptographic system Public-key Encryption with Bidirectional Keyword Search (PEBKS) and constructed a concrete scheme.

All of the above schemes, including PEKS, PAEKS and PEBKS are identity-based cryptosystem with key escrow and certificate management issues. Peng et al. [5] constructed the first PEKS under CL-PKC named CLPEKS. In 2018, Ma et al. [4] proposed an improved CLPEKS scheme and it was improved again in the literature [27], which was been pointed out cannot achieve both MCI and MTP secure and was subsequently improved by Yang et al. [28]. But, the cryptanalysis in [29] demonstrates that these CLPEKS frameworks also suffer from the security vulnerability caused by the keyword guessing attack and in order to remedy these security weakness and provide resistance against both inside and outside keyword guessing attacks, they propose a new CLEKS scheme by embedding the owner’s private key into the calculation of keyword ciphertexts, which actually is CL-PAEKS. Later, combining [4], He et al. [11] proposed a CL-PAEKS scheme, and Shiraly et al. [30] constructed a pairing-free CL-PAEKS. However, their security and functionality still need to be improved and promoted.

2  Preliminaries

2.1 Notations

The symbols and notations used in this paper are presented in the Table 1.

2.2 Bilinear Pairing

Bilinear pairing [31] is an important tool in the construction of many pairing based cryptographic schemes, including our CL-BSE scheme, and we usually construct it using the Weil pairing and the Tate pairing [31–33].

Definition 2.1 (Bilinear Pairing). Let G1 be an additive cyclic group of large prime order q and G2 a multiplicative cyclic group of the same order. A bilinear pairing e^:G1×G1→G2 is a mapping which satisfies the following properties:

Bilinearity: For any P,Q∈G1 and any a,b∈Zq∗, e^(aP,bQ)=e^(P,Q)ab;

Non-Degeneracy: There exists a P∈G1 such that e^(P,P)≠1G2, (where 1G2 denotes the identity in G2). Observe that since G1 and G2 are groups of prime order, so for any generator P∈G1, this statement implies that e^(P,P)∈G2 is a generator of G2;

Computability: For any P,Q∈G1, there is an efficient algorithm to compute e^(P,Q).

2.3 Hardness Assumption

Definition 2.2 (The CBDH Assumption [31]). The Computational Bilinear Diffie-Hellman (CBDH) problem states that given (P,aP,bP,cP)∈G14, a bilinear pairing e^:G1×G1→G2, to compute e^(P,P)abc. The CBDH assumption says that, for any PPT algorithm ℬ, it is hard to compute e^(P,P)abc, given a random instance of the CBDH problem (P,aP,bP,cP)∈G14. That is,

AdvℬCBDH(1k):=Pr[Z=e^(P,P)abc|Z←ℬ(P,aP,bP,cP)]≤negl(1k),(1)

where the probability is taken over the random choices of P∈G1, a,b,c∈Zq∗ and the random coins tossed by ℬ.

3  The Framework

There are three principal works in this section. First, we illustrate the system model of our protocol in this paper based on [13], and then formalise the definition of our CL-BSE scheme. Finally, we define the security model based on [8,9].

3.1 System Model

As shown in Fig. 1, the system model of our protocol includes the following five parties: cloud email server (CS), smart contract-based key generation center (SC-KGC), blockchain (BC), data owner (DO) and data receiver (DR). They are interacting as follows:

Figure 1: System model

•   SC-KGC: Deployed on the blockchain, the smart contract key generation center is a combination of a smart contract and a conventional key generation center. It is responsible for producing and storing the public parameters on the blockchain, generating and distributing partial private keys and the master key to the corresponding parties.

•   Blockchain: To avoid the system public parameters being tampered with, blockchain stores and then transmits them to all clients. The blockchain is also responsible for verifying the validity of the ciphertext, and then transferring the verified ciphertext to the cloud server.

•   Cloud Email Server: The cloud email server plays an “honest but curious” role in the system model, i.e., it stores the real data, retrieves keyword sets by rules and returns the corresponding results correctly. Meanwhile, it may launch keyword guessing attacks on a set of received search tokens. Furthermore, it also performs the test algorithm and then sends the search results to the data receiver.

•   Data Owner: The data owner is a client who wants to store the encrypted data files with keyword indexes in the email server while sending it to the data receiver through the cloud email server, so that he/she can retrieve it by generating a trapdoor using his/her own private key.

•   Data Receiver: The data receiver is one who receives emails from the cloud email server by sending a trapdoor for the keywords he/she interested in using his/her own private key.

3.2 The Definition of CL-BSE

We have formalized the architecture of our certificateless bidirectional authenticated searchable encryption (CL-BSE) scheme for the cloud email system.

Definition 3.1. The CL-BSE scheme consists essentially of nine PPT algorithms: Setup, Extract-PPK, Set-secret-value, Set-private-key, Set-public-key, CL-BSE, Trapdoor-DR, Trapdoor-DO and Test. They are described below:

•   Setup (1k): This algorithm is executed by SC-KGC. Given a security parameter 1k, the algorithm generates the global public parameters Params and the master key Pmas.

•   Extract-PPK (Params): This algorithm is also performed by SC-KGC. It takes as input the global public parameters Params, the master key Pmas and the client identity IDU(U∈{CS,DO,DR}), generates and outputs each client’s partial private key PPKU.

•   Set-secret-value (Params,IDU): This algorithm is run by each client. Input Params and the client identity IDU(U∈{CS,DO,DR}), it generates the secret value SVU for each participant.

•   Set-private-key (Params,SVU,PPKU): Each client runs this algorithm on its own. Entering Params, secret value SVU and partial private key PPKU, it outputs the private key SKU for each client.

•   Set-public-key (Params,SVU): This algorithm is executed by each client. It takes as input Params and the secret value SVU, and outputs the public key PKU for itself.

•   CL-BSE (PKDR,PKCS,SKDO,w): This is the keyword ciphertext generation algorithm and is performed by the data owner. It takes as input PKDR, PKCS, SKDO and keyword w with respect to the encrypted files, outputs a ciphertext Cw.

•   Trapdoor-DR (PKDO,PKCS,SKDR,w ′): This algorithm generates trapdoor for data receiver. When searching the encrypted files containing the keyword w ′ from the cloud email server, it takes as input PKDO, PKCS, SKDR and the keyword w ′, and outputs TDR.

•   Trapdoor-DO (PKDR,PKCS,SKDO,w ′): This algorithm generates trapdoor for data owner. When the client wants to retrieve the encrypted files containing the keyword w ′ from the cloud email server, it takes as input PKDR, PKCS, SKDO and the keyword w ′, outputs TDO.

•   Test (Cw,SKCS,Tw ′=TDO(TDR)): The test algorithm is executed by the cloud email server. It takes Cw and Tw ′ as input and returns “1” if w=w ′ and “0” otherwise.

Correctness. The correctness of our CL-BSE scheme is defined as follows. For any legally registered clients IDU(U∈{DO,DR,CS}) with public/private key pairs (PKU,SKU). Let Cw←CL−BSE(PKDR,PKCS,SKDO,w) be the ciphertext of w, TDO←Trapdoor−DO(PKDR,PKCS,SKDO,w ′) and TDR←Trapdoor−DR(PKDO,PKCS,SKDR,w ′) be the trapdoors of w ′ generated by DO and DR, respectively. Correctness implies

Pr[Test(Params,TDO(w ′),Cw)=1]=Pr[Test(Params,TDR(w ′),Cw)=1]=1.(2)

3.3 Security Model

As with other certificateless cryptosystems [5,10,28,34,35], the CL-BSE scheme considers two types of adversary with different privileges: Type-I adversary 𝒜1 and Type-II adversary 𝒜2. Specifically,

•   Type-I adversary 𝒜1. It plays the part of the malicious user who is available to perform queries including extract partial private key, request public key, extract secret value and replace public key, but does not have access to the master private key Pmas.

•   Type-II adversary 𝒜2. It models an honest-but-curious SC-KGC that has access to the master private key Pmas, but not allowed to replace public key query.

Now, the above queries are listed as follows, which are actually interactions between an adversary 𝒜1(𝒜2) and a challenger 𝒞.

–   Extract-PPK query. When 𝒜1(𝒜2) queries partial private key for identity IDi, 𝒞 executes Extract-PPK algorithm and returns partial private key PPKi.

–   Extract-secret-value query. When 𝒜1(𝒜2) queries secret value for identity IDi, 𝒞 executes Set-secret-value algorithm and returns a secret value SVi.

–   Request-public-key query. When 𝒜1(𝒜2) queries public key for identity IDi, 𝒞 executes Set-public-key algorithm and returns public key PKi.

–   Replace-public-key query. 𝒜1 is permitted to ask 𝒞 to replace the public PKi with a new one PKi ′ for any user IDi.

–   Ciphertext query. When 𝒜1(𝒜2) queries the ciphertext of the keyword w, the challenger 𝒞 returns the matching ciphertext Cw.

–   Data receiver trapdoor query. When 𝒜1(𝒜2) queries the data receiver trapdoor of keyword w ′, 𝒞 returns the matching trapdoor TDR=Tw ′.

–   Data owner trapdoor query. When 𝒜1(𝒜2) queries the data owner trapdoor of keyword w ′, 𝒞 returns the matching trapdoor TDO=Tw ′.

In order to capture chosen multi-keyword attacks and multi-keyword guessing attacks, the security model of our CL-BSE scheme are defined as MCI [8] and MTP [9], which are the enhancement of CI-secure and TP-secure [7], respectively. Their formal definitions are described by the following games, which are interactions between an challenger 𝒞 and an adversary 𝒜1 or 𝒜2.

Game 1: The MCI Security against Adversary 𝒜1.

•   Setup. Given security parameter 1k, 𝒞 generates public parameter Params and system master key Pmas by running Setup algorithm. It then responds only to 𝒜1 Params and keeps master key Pmas secret.

•   Phase 1. 𝒜1 can adaptively perform a series of polynomial times queries, including Extract-PPK query, Extract-secret-value query, Request-public-key query, Replace-public-key query, Ciphertext query, Data receiver trapdoor query and Data owner trapdoor query.

•   Challenge. After 𝒜1 finishes the queries in Phase 1, it selects two challenge keyword sets w0∗={w0,1, w0,2, … , w0,n}, w1∗={w1,1, w1,2 … ,w1,n} which are not queried in Phase 1 and sends them to 𝒞. After that, it first chooses a random bit b∈{0,1}, then computes the searchable ciphertext Cwb∗ with respect to wb∗. Finally, it returns Cwb∗ as a challenge ciphertext.

•   Phase 2. As in Phase 1, 𝒜1 can continue to make series queries for polynomial times and the restriction here is that cannot make ciphertext query and two trapdoor queries on w0∗ and w1∗.

•   Guess. Finally, 𝒜1 outputs its guess b ′∈{0,1} on b, and wins this game if b ′=b.

The following probability equation defines 𝒜1’s advantage in the game,

Adv𝒜1MCI(1k)=|Pr[b ′=b]−12|.(3)

Game 2: The MCI Security against Adversary 𝒜2.

•   Setup. Given security parameter 1k, 𝒞 runs Setup algorithm generates public parameter Params and system master key Pmas, then sends both Params and Pmas to 𝒜2.

•   Phase 1. As in Game 1, 𝒜2 can make Extract-PPK query, Extract-secret-value query, Request-public-key query, Ciphertext query, Data receiver trapdoor query and Data owner trapdoor query, but not available for Replace-public-key query.

•   Challenge. When 𝒜2 completed the Phase 1, it selects w0∗, w1∗ as challenge keywords sets like the steps in Game 1, and sends them to 𝒞. Then 𝒞 chooses a random bit b∈{0,1} and generates the ciphertext Cwb∗ with respect to wb∗. Finally, it returns Cwb∗ to 𝒜2 as a challenge ciphertext.

•   Phase 2. This phase is the same as Game 1, 𝒜2 is not allowed to make ciphertext query and two trapdoor queries on w0∗ and w1∗.

•   Guess. Finally, 𝒜2 outputs its guess b ′∈{0,1} on b, and wins if b ′=b.

The advantage of 𝒜2 in Game 2 is defined by the following probability equation:

Adv𝒜2MCI(1k)=|Pr[b ′=b]−12|.(4)

Definition 3.2 (MCI security). The CL-BSE scheme is said MCI security if for any PPT adversary 𝒜, its advantages Adv𝒜1MCI(1k) and Adv𝒜2MCI(1k) against the challenger 𝒞 in Game 1 and Game 2 are negligible.

Game 3: The MTP Security against Adversary 𝒜1.

•   Setup. The setup algorithm is the same as Game 1, 𝒞 also only sends the public parameter Params to 𝒜1 eventually.

•   Phase 1. Same as process Phase 1 in Game 1.

•   Challenge. When 𝒜1 has finished the Phase 1, do the same as that in Game 1 to obtain two challenge keywords sets w0∗, w1∗ and send them to 𝒞. After that, 𝒞 chooses a random bit b∈{0,1} first, then computes the trapdoor Twb∗ with respect to wb∗. Finally, it returns Twb∗ to 𝒜1 as a challenge trapdoor.

•   Phase 2. Same as process Phase 2 in Game 1.

•   Guess. Finally, 𝒜2 outputs its guess b ′∈{0,1} on b, and wins this game if b ′=b.

The advantage of 𝒜1 in Game 3 is defined by

Adv𝒜1MTP(1k)=|Pr[b ′=b]−12|.(5)

Game 4: The MTP Security against Adversary 𝒜2.

•   Setup. The setup algorithm is the same as Game 2, the challenger 𝒞 sends both the public parameter Params and the master key Pmas to 𝒜2 eventually.

•   Phase 1. Same as process Phase 1 in Game 2.

•   Challenge. After 𝒜2 has finished the Phase 1, do the same as that in Game 3 to obtain two challenge keyword sets w0∗, w1∗ and send them to 𝒞. Then 𝒞 chooses a random bit b∈{0,1} and generates the trapdoor Twb∗ with respect to wb∗. Finally, it returns Twb∗ to 𝒜2 as a challenge trapdoor.

•   Phase 2. Same as process Phase 2 in Game 2.

•   Guess. Finally, 𝒜2 outputs its guess b ′∈{0,1} on b, and it wins this game if b ′=b.

The advantage of 𝒜2 in Game 4 is defined by

Adv𝒜2MTP(1k)=|Pr[b ′=b]−12|.(6)

Definition 3.3 (MTP security). The CL-BSE scheme is said MTP security for both data receiver trapdoor and data owner trapdoor, if for any PPT adversary 𝒜, its advantages Adv𝒜1MTP(1k) and Adv𝒜2MTP(1k) against the challenger 𝒞 in Game 3 and Game 4 are negligible.

4  The Proposed CL-BSE Scheme

In this section, we give a concrete construction as the formal definition of the CL-BSE scheme in Section 3.2 with a designated server, it consists of nine PPT algorithms in five phases: System initialization, Key generation, Keyword encryption, Trapdoor generation and Test.

Phase A. System Initialization.

•   Setup (1k): Given the security parameter 1k, SC-KGC performs the following steps:

(1)   Select a cyclic additive group G1, a cyclic multiplicative group G2 with a large prime order q,(q>2k) and three generators P1, P2 and Q∈G1, generate a bilinear pair e^:G1×G1→G2;

(2)   Pick a random number s←Zq∗, put it as the system master key and store it secretly, then compute Ppub=sP1;

(3)   Define six different cryptographic hash functions Hi(1≤i≤6) as: H1:{0,1}∗→G1, H2:{0,1}∗×G1→Zq∗, H3:{0,1}∗×G1×G1×G1→Zq∗, H4:G1→{0,1}len, where len is the fixed length output, H5:G2→Zq∗, H6:{0,1}logw+len→Zq∗, and logw denotes the length of w;

(4)   Broadcast the public parameters params={1k,e^,G1,G2,q,P1,P2,Q,Ppub,Hi(1≤i≤6)} on the blockchain.

Phase B. Key Generation.

•   Extract-PPK (Params): SC-KGC takes as input the public parameters Params, the master key Pmas and the identity IDU(U∈{CS,DO,DR}), then generates partial private keys for all clients as follows:

(1)   For CS, SC-KGC selects r CS←Zq∗ randomly, computes RCS=r CSP2, α CS=H2(IDCS,RCS) and d CS=r CS+α CSs(mod q), and outputs PPKCS=(RCS,d CS) as its partial private key;

(2)   For U∈{DO,DR}, SC-KGC computes their partial private key as PPKU=DU, where DU=sQU and QU=H1(IDU).

Set-secret-value (Params,IDU): The client U∈{DO,DR} selects x U,y U←Zq∗ randomly and sets SVU=(x U,y U). CS selects a single random number x CS←Zq∗ and sets SVCS=x CS.

Set-private-key (Params,SVU,PPKU): The client U∈{DO,DR} and CS set their own private keys as SKU=(x U,y U,DU) and SKCS=(x CS,d CS), respectively.

Set-public-key (Params,SVU): The client U∈{DO,DR} computes PU=x UP1, YU=y UQ, and assigns its public keys as PKU=(PU,YU), while CS assigns its public key as PKCS=(PCS,RCS), where PCS=x CSP2.

Phase C. Keywords Encryption.

•   CL-BSE (PKDR,PKCS,SKDO,w): When DO wants to encrypt the keyword w extracted from the encrypted emails, he/she enters the relevant parameters params, SKDO, IDDR, PKDR, IDCS, PKCS and performs the following steps:

(1)   Compute α CS=H2(IDCS,RCS),β CS=H3(IDCS,Ppub,PCS,RCS);

(2)   Compute k1=H4(y DOYDR),k2=H5(e^(DDO,QDR));

(3)   Select r←Zq∗ randomly, then compute

C1 =r⋅P2,(7)

C2 =e^(PDR,β CSPCS + RCS + α CSPpub)rx DOH6(w‖k1),(8)

C3 =r⋅k2⋅P1;(9)

(4)   Compute V=DDO+(r⋅k2+x DO)RCS;

(5)   Upload the ciphertext Cw=(C1,C2,C3,V) on the blockchain.

Upon receiving Cw=(C1,C2,C3,V) from the data owner, the blockchain verifies the owner’s legitimacy by the equation

e^(V,P1)=?e^(QDO,Ppub)e^(C3+PDO,RCS).(10)

If and only if the owner is a legal member of the system, the blockchain then stores the verified ciphertexts to the cloud server, which can effectively save storage space.

Phase D. Trapdoor Generation.

Both DR and DO can generate their own trapdoor in the following ways:

•   Trapdoor-DR (PKDO,PKCS,SKDR,w ′): Input parameters Params, SKDR, PKDO and PKCS, when DR searches for the files containing the keyword w ′, it performs the following operations:

(1) Recall α CS,β CS, and k1=H4(y DRYDO), k2=H5(e^(DDR,QDO));

(2) Select a random number t DR←Zq∗ and compute

T1 =t DR(β CSPCS+RCS+α CSPpub),(11)

T2 =t DRk2P1+x DRH6(w ′‖k1)PDO;(12)

(3) Output TDR=(T1,T2).

•   Trapdoor-DO (PKDR,PKCS,SKDO,w ′). Different from other CL-PAEKS models, the bidirectional keyword search functionality in this paper is achieved by introducing DO’s trapdoor generation algorithm. In fact, similar to DR’s trapdoor generation process above, when DO retrieves the data from CS, it does not need to generate any additional variables, but simply uses its own private key SKDO and PKDR, PKCS to generate the trapdoor TDO=(T1,T2). That is,

T1 =t DO(β CSPCS+RCS+α CSPpub),(13)

T2 =t DOk2P1+x DOH6(w ′‖k1)PDR.(14)

Phase E. Test Process.

•   Test (Cw,SKCS,Tw ′=TDO/TDR): Take Cw, SKCS, Tw ′=TDO or TDR as input, CS verifies whether

e^(T2,(β CSx CS+d CS)C1)=?e^(T1,C3)⋅C2(15)

holds. Output “1” if it holds and “0” otherwise.

Actually, from the verification equation it can be seen that since x CS and d CS are private keys secretly held by the cloud email server, then only the server holding the private key can verify the equation above, i.e., our scheme is a bidirectional searchable encryption scheme with secure channel free for designated server verification.

Correctness.

(1)   e^(V,P1)=?e^(QDO,Ppub)e^(C3+PDO,RCS).

e^(V,P1) =e^(DDO+(rk2+x DO)RCS,P1) =e^(DDO,P1)e^((rk2+x DO)RCS,P1) =e^(DDO,P1)e^((rk2+x DO)P1,RCS) =e^(QDO,Ppub)e^(C3+PDO,RCS).

(2) e^(T2,(β CSx CS+d CS)C1)=?e^(T1,C3)⋅C2.

e^(T2,(β CSx CS+d CS)C1) =e^(t DOk2P1+x DOH6(w‖k1)PDR,r(β CSx CS+r CS+sα CS)P2) =e^(t DOk2P1,r(β CSx CS+r CS+sα CS)P2)e^(x DOH6(w‖k1)PDR,r(β CSx CS+r CS+sα CS)P2) =e^(t DOk2P1,r(β CSx CS+r CS+sα CS)P2)e^(x DOH6(w‖k1)x DRP1,r(β CSx CS+r CS+sα CS)P2) =e^(P1,P2)t DOk2r(β CSx CS+r CS+sα CS)e^(P1,P2)rx DOx DRH6(w‖k1)(β CSx CS+r CS+sα CS),

and

e^(T1,C3)⋅C2 =e^(t DO(β CSx CS+r CS+sα CS)P2,rk2P1)e^(PDR,(β CSx CS+r CS+sα CS)P2)rxDOH6(w‖k1) =e^(t DO(β CSx CS+r CS+sα CS)P2,rk2P1)e^(x DRP1,(β CSx CS+r CS+sα CS)P2)rxDOH6(w‖k1) =e^(P1,P2)rt DOk2(β CSx CS+r CS+sα CS)e^(P1,P2)rxDOx DRH6(w‖k1)(β CSx CS+r CS+sα CS).

The verification process described above demonstrates the correctness of the data owner’s trapdoor and ciphertext test, the verification with respect to the data receiver’s trapdoor is similar and we omit it.

5  Security Analysis

Based on the formal definition of security models in Section 3.3 and the CBDH hardness assumption in Section 2.3, we give the security proof of our scheme in this section.

Theorem 5.1 (MCI security). In the random oracle model, our CL-BSE scheme achieves semantically MCI security against outside chosen multi-keyword attacks under the CBDH hardness assumption.

The proof of Theorem 5.1 can be achieved by the following two lemmas.

Lemma 5.1. In the random oracle model, for any PPT adversary 𝒜1, there is an algorithm ℬ that can break the CBDH assumption with advantage

ε ′≥2εq H1(1−1q H1)q E1+q E2+q C+q T(16)

if 𝒜1 wins Game 1 with advantage ε.

Proof. Give a bilinear pair (e^,G1,G2,P1,q) and an instance of CBDH assumption (P1,aP1,bP1,cP1)∈G14, algorithm ℬ calculates e^(P1,P1)abc by taking 𝒜1 as a subroutine as follows:

•   Setup. For a given security parameter 1k, ℬ generates public parameter Params={G1,G2,q,P1,P2=αP1,Q,e^,Ppub,Hi(1≤i≤6)} and system master key Pmas=s∈Zq∗ firstly, then sets PDO=aP1, PDR=bP1, PKCS=(PCS,RCS) and SKCS=(x CS,d CS), chooses IDI(1≤I≤q H1) randomly as the challenge identity. Finally, it only responds (Params,PDO,PDR,PKCS,SKCS) to 𝒜1, and keeps Pmas secretly.

•   Phase 1. 𝒜1 preforms a series of queries with polynomially many times adaptively, they are

–   H1-query. ℬ maintains a list LH1={⟨IDi,λi,Qi⟩} to respond H1-query. For any IDi submitted by 𝒜1, ℬ first checks whether the IDi already exists on LH1 in a tuples ⟨IDi,λi,Qi⟩, outputs corresponding Qi if so, otherwise selects λi←Zq∗ randomly, outputs Qi=λiP1, and adds ⟨IDi,λi,Qi⟩ to LH1.

–   H2-query. ℬ maintains a list LH2={⟨IDi,Ri,αi⟩} to respond H2-query. For any (IDi,Ri)∈{0,1}∗×G1 submitted by 𝒜1, ℬ checks whether (IDi,Ri) already exists on LH2 in a tuples ⟨IDi,Ri,αi⟩ firstly, outputs corresponding αi if so, otherwise selects and outputs αi←Zq∗ randomly, and adds ⟨IDi,Ri,αi⟩ to LH2 at the same time.

–   H3-query. ℬ maintains a list LH3={⟨IDi,Pi,Ri,βi⟩} to respond H3-query. For any (IDi,Pi,Ri) submitted by 𝒜1, ℬ first checks whether the tuples including (IDi,Pi,Ri) already exists on LH3, outputs corresponding βi if so, otherwise selects and outputs βi←Zq∗ randomly, and adds ⟨IDi,Pi,Ri,βi⟩ to LH3 at the same time.

–   H4-query. ℬ maintains a list LH4={⟨Mi,k1i⟩} to respond H4-query. For any Mi∈G1 submitted by 𝒜1, ℬ first checks whether the Mi already exists on LH4 in a tuples ⟨Mi,k1i⟩, outputs k1i if so, otherwise selects k1i←Zq∗ randomly and outputs it, then add ⟨Mi,k1i⟩ to LH4.

–   H5-query. ℬ maintains a list LH5={⟨Ni,k2i⟩} to respond H4-query. For any Ni∈G2 submitted by 𝒜1, ℬ first checks whether the Ni already exists on LH5 in a tuples ⟨Ni,k2i⟩, outputs k2i if so, otherwise selects k2i←Zq∗ randomly and outputs it, then adds ⟨Ni,k2i⟩ to LH5.

–   H6-query. ℬ maintains a list LH6={⟨Ii,ηi⟩} to respond H4-query, where Ii=wi‖k1i∈{0,1}∗, k1i∈LH4. For any Ii submitted by 𝒜1, ℬ first checks whether the Ii already exists on LH6 in a tuples ⟨Ii,ηi⟩, outputs ηi if so, otherwise selects ηi←Zq∗ randomly and outputs it, then adds ⟨Ii,ηi⟩ to LH6.

–   Extract-PPK query. ℬ maintains a list LE1={⟨IDi,Qi,Di⟩} to respond 𝒜1 for the partial private key of IDi. It performs H1-query and gets ⟨IDi,λi,Qi⟩ first and adds them to LH1. If IDi≠IDI, then ℬ computes Di=λiPpub and outputs Di, and adds ⟨IDi,Qi,Di⟩ into LE1, otherwise aborts the query and denotes the event as E1.

–   Request-public-key query. ℬ maintains a list LE2={⟨IDi,xi,yi,Pi,Yi⟩} to respond 𝒜1 for the public key of IDi. It first checks whether IDi already exists on LE2, retrieves PKi=(Pi,Yi) if so, otherwise selects two random numbers xi,yi←Zq∗, computes Pi=xiP1, Yi=yiP1, and outputs PKi=(Pi,Yi), meanwhile, adds ⟨IDi,xi,yi,Pi,Yi⟩ into LE2.

–   Replace-public-key query. When ℬ receives a new public key PKi ′=(Pi ′,Yi ′) of identity IDi queried by 𝒜1, it updates the original tuple ⟨IDi,xi,yi,Pi,Yi⟩ in LE2 with ⟨IDi,⊥,⊥,Pi ′,Yi ′⟩.

–   Extract-private-key query. When the identity IDi is queried by 𝒜1, ℬ checks whether IDi=IDI first. If IDi≠IDI, then it performs as follows, if IDi already exists on LE1 and LE2 in their tuples ⟨IDi,Qi,Di⟩ and ⟨IDi,xi,yi,Pi,Yi⟩ respectively, then ℬ retrieves SKi=(xi,yi,Di) and responds to 𝒜1, otherwise performs Extract-PPK query and Request-public-key query with IDi and retrieves corresponding SKi=(xi,yi,Di). If IDi=IDI, then it aborts and denotes this event as E2.

–   Ciphertext query. Upon ℬ receiving a query (w ′,IDDO ′,IDDR ′,IDCS ′) about ciphertext. If IDDR ′≠IDI, then it selects r ′←Zq∗ randomly, extracts the corresponding value from the above lists, and computes

C1 ′=r ′P1,(17)

C2 ′=e^(PDR ′,β ′PCS ′+RCS ′+α CS ′Ppub)r ′x DO ′ηi ′,(18)

C3 ′=r ′k2i ′P1,(19)

V ′=DDO ′+(r ′k2i ′+x DO ′)RCS ′.(20)

Otherwise ℬ aborts and denotes it as E3. Finally, it outputs Cw ′=(C1 ′,C2 ′,C3 ′,V ′) to 𝒜1.

–   Trapdoor query. No matter the trapdoor is queried to be generated by the data receiver or the data owner. ℬ performs the following steps. Upon receiving a query (w ′,IDDO ′,IDDR ′,IDCS ′) for a trapdoor, it aborts and denotes it as E4 if and only if IDDR ′=IDI. Otherwise ℬ selects t ′←Zq∗ randomly, extracts the corresponding value from the above lists, and computes

T1=t ′(β ′PCS ′+RCS ′+α CS ′Ppub),(21)

T2=t ′k2i ′P1+x DR ′ηi ′PDO ′.(22)

Finally, it outputs Tw ′=(T1 ′,T2 ′) to 𝒜1.

•   Challenge. After 𝒜1 finished Phase 1 queries, it selects w0∗, w1∗ not be queried in Phase 1 as the challenge keywords sets and the challenge identity IDI, then sends them to ℬ, ℬ checks whether IDDR ′=IDI, if not, ℬ aborts and denotes it as E5, and gives a random bit b ′ as a guess of b. Otherwise, it first chooses a random bit b∈{0,1} and a random number r∗←Zq∗, computes C1∗∈G1, C2∗=e^(PDR ′,C3∗)x DO ′ηi ′, C3∗=r∗k2i ′cP1 and V∗∈G1. Finally, it responds 𝒜1 with Cwb∗=(C1∗,C2∗,C3∗,V∗).

•   >Phase 2. As in Phase 1, 𝒜1 can make a series of queries for polynomial times and it can not make ciphertext query and two trapdoor queries on any keyword in w0∗ and w0∗. Denote this event as E6.

•   Guess. Finally, 𝒜1 outputs its guess b ′∈{0,1} on b, and ℬ chooses Cwb∗=(C1∗,C2∗,C3∗,V) to compute (C2∗)1r∗k2i ′ηi ′. If 𝒜1 is correct, then no matter b=0 or b=1, it can compute C2∗=e^(PDR ′,C3∗)x DO ′ηi ′. Furthermore, for unknown a,b,c∈Zq∗, we set PDO ′=aP1, PDR ′=bP1, and C3∗=r∗k2i ′cP1, ℬ can compute e^(P1,P1)abc as

(C2∗)1r∗k2i ′ηi ′ =(e^(PDR ′,C3∗)x DO ′ηi ′)1r∗k2i ′ηi ′ =(e^(PDR ′,r∗k2i ′cP1)x DO ′ηi ′)1r∗k2i ′ηi ′ =e^(PDR ′,x DO ′cP1)=e^(P1,P1)abc.(23)

Now, suppose ℬ can break the CBDH assumption with advantage ε ′, 𝒜1 can make at most q H1, q E1, q E2, q C and q T times queries to H1-query, Extract-PPK query, Request-public-key query, Ciphertext query and Trapdoor query, respectively, then

Pr[¬E1∧¬E2∧¬E3∧¬E4∧¬E5] =(1−1q H1)q E1(1−1q H1)q E2(1−1q H1)q C(1−1q H1)q T1q H1 =(1−1q H1)q E1+q E2+q C+q T1q H1.(24)

Since

Pr[b=b ′] =Pr[b=b ′|E6]Pr[E6]+Pr[b=b ′|¬E6]Pr[¬E6] ≤Pr[b=b ′|E6]Pr[E6]+Pr[¬E6] =12Pr[E6]+Pr[¬E6]=12+12Pr[¬E6],(25)

and

Pr[b=b ′]≥Pr[b=b ′|E6]Pr[E6]=12−12Pr[¬E6],(26)

we have Pr[¬E6]≥2ε. Combing with (24), we get Eq. (16) and the lemma is proved.

Lemma 5.2. In the random oracle model, for any PPT adversary 𝒜2, there is an algorithm ℬ that can break the CBDH assumption with advantage

ε ′≥2εq H1(1−1q H1)q E1+q C+q T(27)

if 𝒜2 wins Game 2 with advantage ε.

Proof. Similar with Lemma 5.1, given an instance of the CBDH assumption (P1,aP1,bP1,cP1)∈G14, ℬ calculates the value e^(P1,P1)abc by taking 𝒜2 as a subroutine as follows:

•   Setup. ℬ generates Params={G1,G2,e^,q,P1,P2=αP1,Q,Ppub,Hi(1≤i≤6)} and Pmas=s∈Zq∗, sets PDO=aP1, PDR=bP1, PKCS=(PCS,RCS) and SKCS=(x CS,d CS), and chooses IDI(1≤I≤q H1) randomly as the challenge identity. Finally, it responds both (Params, PDO, PDR, PKCS, SKCS) and Pmas=s to 𝒜2.

•   Phase 1. 𝒜2 preforms a series of queries with polynomially many times adaptively, they are

–   Hash queries. 𝒜2 can query Hi(1≤i≤6) random oracles. ℬ responds them as same as Lemma 5.1.

–   Request-public-key query. ℬ maintains a list LE2={⟨IDi,xi,yi,Pi,Yi⟩} to respond 𝒜2 for the public key of IDi. The interaction is the same as Phase 1 in Lemma 5.1.

–   Extract-private-key query. When the identity IDi is queried by 𝒜2, ℬ first checks whether IDi=IDI. If not, it performs as follows: if IDi already exists on LH1 and LE2 in the corresponding tuples ⟨IDi,λi,Qi⟩ and ⟨IDi,xi,yi,Pi,Yi⟩, then ℬ responds to 𝒜2 as SKi=(xi,yi,sQi), otherwise performs H1 query and Request-public-key query with IDi and retrieves the corresponding SKi=(xi,yi,sQi). If IDi=IDI, it aborts and denotes this event as E1.

–   Ciphertext query. Upon ℬ receiving a ciphertext query about (w ′,IDDO ′,IDDR ′,IDCS ′). It first checks whether IDDR ′=IDI, if not, selects r ′←Zq∗ randomly, extracts the corresponding value and computes

C1 ′=r ′P2,(28)

C2 ′=e^(PDR ′,β ′PCS ′+RCS ′+α CS ′Ppub)r ′x DO ′ηi ′,(29)

C3 ′=r ′k2i ′P1,(30)

V ′=sQDO ′+(r ′k2i ′+x DO ′)RCS ′,(31)

where k2i ′=H5(e^(QDO ′,QDR ′)s). Otherwise aborts and denotes the event as E2. Finally, it outputs Cw ′=(C1 ′,C2 ′,C3 ′,V ′).

–   Trapdoor query. No matter 𝒜2 makes a data receiver or a data owner trapdoor query. ℬ performs the follows steps. Upon receiving (w ′,IDDO ′,IDDR ′,IDCS ′), ℬ aborts and denote this event as E3 if and only if IDDR ′=IDI. Otherwise it selects t ′←Zq∗ randomly, extracts the corresponding value and computes

T1=t ′(β ′PCS ′+RCS ′+α CS ′Ppub),(32)

T2=t ′k2i ′P1+x DR ′ηi ′PDO ′,(33)

where k2i ′=H5(e^(QDO ′,QDR ′)s). Finally, it outputs Tw ′=(T1 ′,T2 ′) to 𝒜2.

•   Challenge. After 𝒜2 finished the Phase 1 queries, it selects w0∗, w1∗ as the challenge keywords sets not be queried before, and sends them to ℬ with the challenge identity IDI. ℬ checks whether IDDR ′=IDI, if not, it aborts and denotes this event as E4, then gives a random bits b ′ as guess of b. Otherwise chooses a random bit b∈{0,1} and computes ciphertext Cwb∗=(C1∗,C2∗,C3∗,V∗) as follows. First, pick a random number r∗←Zq∗, compute C1∗=r∗cP1, C2∗=e^(PDR ′,C1∗)x DO ′ηi ′, C3∗∈G1 and V∗∈G1. Finally, respond Cwb∗ to 𝒜1.

•   Phase 2. This phase is same as Game 2, 𝒜2 is not allowed to make ciphertext query and two trapdoor queries on w0∗ and w1∗. Denote this event as E5.

•   Guess. Finally, 𝒜2 outputs its guess b ′∈{0,1} on b, meanwhile, ℬ retrieves Cwb∗=(C1∗,C2∗,C3∗,V∗) and computes (C2∗)1r∗ηi ′. If 𝒜2 is correct, then no matter b=0 or b=1, it can compute C2∗=e^(PDR ′,C1∗)x DO ′ηi ′. Furthermore, for unknown a,b,c∈Zq∗, we set PDO ′=aP1, PDR ′=bP1 and P2=cP1, ℬ can compute e^(P1,P1)abc as

(C2∗)1r∗ηi ′ =(e^(PDR ′,C1∗)x DO ′ηi ′)1r∗ηi ′ =(e^(PDR ′,r∗cP1)x DO ′ηi ′)1r∗ηi ′ =e^(PDR ′,x DO ′cP1)=e^(P1,P1)abc.(34)

Now, suppose ℬ breaks the CBDH assumption with advantage ε ′, 𝒜2 can make at most q H1, q E1, q C and q T times queries to H1-query, Request-public-key query, Ciphertext query and Trapdoor query, respectively, thus,

Pr[¬E1∧¬E2∧¬E3∧¬E4] =(1−1q H1)q E1(1−1q H1)q C(1−1q H1)q T1q H1 =(1−1q H1)q E1+q C+q T1q H1.(35)

Since

Pr[b=b ′] =Pr[b=b ′|E5]Pr[E5]+Pr[b=b ′|¬E5]Pr[¬E5] ≤Pr[b=b ′|E5]Pr[E5]+Pr[¬E5] =12Pr[E5]+Pr[¬E5]=12+12Pr[¬E5].(36)

and

Pr[b=b ′]≥Pr[b=b ′|E5]Pr[E5]=12−12Pr[¬E5].(37)

we have Pr[¬E5]≥2ε, so combing with (35), we get Eq. (27) and the lemma is proved.

Theorem 5.2 MTP security. In the random oracle model, our CL-BSE scheme achieves semantically MTP security against inside multi-keywords guessing attacks under the CBDH hardness assumption.

The proof of Theorem 5.2 can be achieved by the following two lemmas:

Lemma 5.3. In the random oracle model, for any PPT adversary 𝒜1, there is an algorithm ℬ can break the CBDH assumption with advantage

ε ′≥2εq H1(1−1q H1)q E1+q E2+q C+q T(38)

if 𝒜1 wins Game 3 with advantage ε.

Proof. The interaction process in the proof is basically the same as Lemma 5.1 except the Challenge phase and the Guess phase. They are

•   Challenge. 𝒜1 still select two sets w0∗, w1∗ as the challenge keywords set and the challenge identity IDI, sends them to ℬ, ℬ checks whether IDDR ′=IDI, if not, then ℬ gives a random bits b ′ as a guess of b. Otherwise, it chooses a random bit b∈{0,1} and a random number t∗←Zq∗, then computes T1∗=t∗(β ′PCS ′+RCS ′+α CS ′Ppub), T2∗=t∗k2i ′P1+x DR ′ηi ′PDO ′. Finally, it responds 𝒜1 with Twb∗=(T1∗,T2∗).

•   Guess. Finally, 𝒜1 outputs its guess b ′∈{0,1} on b, and ℬ chooses Twb∗=(T1∗,T2∗) to compute (e^(T2∗,Ppub)e^(P1,Ppub)t∗⋅k2i ′)1ηi ′. If 𝒜1 is correct, then no matter b=0 or b=1, T2=t∗k2i ′P1+x DR ′ηi ′PDO ′ can be computed. Furthermore, for unknown a,b,c∈Zq∗, we set PDO ′=aP1, PDR ′=bP1 and Ppub=cP1, ℬ computes e^(P1,P1)abc as

(e^(T2∗,Ppub)e^(P1,Ppub)t∗⋅k2i ′)1ηi ′ =(e^(t∗k2i ′P1+x DR ′ηi ′PDO ′,Ppub)e^(t∗k2i ′P1,Ppub))1ηi ′ =(e^(x DR ′ηi ′PDO ′,Ppub))1ηi ′= e^(x DR ′PDO ′,Ppub)=e^(P1,P1)abc.(39)

The analysis process of the advantages ε ′ that ℬ computes the above problem is also same as Lemma 5.1, that is Eq. (38) holds and the lemma is proved.

Lemma 5.4. In the random oracle model, for any PPT adversary 𝒜2, there is an algorithm ℬ can break the CBDH assumption with advantage

ε ′≥2εq H1(1−1q H1)q E1+q C+q T(40)

if 𝒜2 wins Game 4 with advantage ε.

Proof. The interaction process in the proof is basically the same as Lemma 5.2 except the Challenge phase and the Guess phase. They are

•   Challenge. 𝒜2 still selects w0∗, w1∗ as the challenge keywords set and sends them to ℬ together with the challenge identity IDI. ℬ checks whether IDDR ′=IDI, if not, ℬ aborts and gives a random bits b ′ as a guess of b. Otherwise chooses a random bit b∈{0,1} and computes trapdoor Twb∗=(T1∗,T2∗) as follows. First, pick a random number t∗←Zq∗, and then compute T1∗=t∗(β ′PCS ′+RCS ′+α CS ′Ppub),T2∗=t∗k2i ′P1+xDR ′ηi ′PDO ′. Finally, respond to 𝒜1 with Twb∗=(T1∗,T2∗).

Guess. Finally, 𝒜2 outputs its guess b ′∈{0,1} on b, meanwhile, ℬ retrieves Twb∗=(T1∗,T2∗) and computes (e^(T2∗,T1∗)e^(t∗⋅k2i ′⋅P1,T1∗))1t∗ηi ′(β ′x CS ′+d CS ′). If 𝒜2 is correct, then no matter b=0 or b=1, algorithm ℬ can compute T1∗=t∗(β ′PCS ′+RCS ′+α CS ′Ppub), T2∗=t∗k2i ′P1+x DR ′ηi ′PDO ′. Furthermore, for unknown a,b,c∈Zq∗, we set PDO ′=aP1, PDR ′=bP1, and P2=cP1, ℬ can compute e^(P1,P1)abc as following:

(e^(T2∗,T1∗)e^(t∗k2i ′P1,T1∗))1t∗ηi ′(β ′x CS ′+d CS ′) =(e^(t∗k2i ′P1+x DR ′ηi ′PDO ′,t∗(β ′x CS ′+d CS ′)P2)e^(t∗k2i ′P1,t∗ΓCS ′P2))1t∗ηi ′(β ′x CS ′+d CS ′) =(e^(x DR ′ηi ′PDO ′,t∗(β ′x CS ′+d CS ′)P2))1t∗ηi ′(β ′x CS ′+d CS ′) =e^(x DR ′PDO ′,P2)=e^(P1,P1)abc.(41)

The analysis process of the advantages ε ′ that ℬ computes the above problem is also same as Lemma 5.2, that is Eq. (40) holds and the lemma is proved.

6  Performance Analysis

In this section, we analyze the performance of our scheme by comparing it with some existing schemes in [4,5,28–30,36,37].

First, we give some basic operations used in the scheme and the executing times of a single operation in Table 2. These times of operations are averaged over 1000 runs on a personal computer (Lenovo with Windows 10 operating system, Intel (R) Core (TM) i7 −7700 CPU @ 3.60 GHz and 8 GB RAM memory) using the Pairing-Based Cryptography (PBC) library [38] in Ubuntu10.

Figs. 2–5 and Table 3 describe the computation overhead of different algorithms in each scheme. Specifically, the computational overhead in the ciphertext generation (Fig. 3) of our scheme is slightly higher than [30,36]. In trapdoor generation process (Fig. 4), the computational overhead of the scheme is higher than [4,5,30] since the enhanced trapdoor privacy and authentication functionality. In test process (Fig. 5), its computational overhead is slightly higher than in [29,30] because our scheme is server-designated, that is, the public/private key pairs of the server are involved in the operation. However, in terms of total time, the time overhead of our new scheme is only slightly higher than [30]. It has some advantages when DO (or DU) retrieves emails and is more in line with practical application scenarios.

Figure 2: Computation overhead in each phase

Figure 3: Running time of encryption

Figure 4: Running time of trapdoor

Figure 5: Running time of test

Subsequently, we make a comparison in terms of communication costs, including the size of public key |PK|, ciphertext |CT| and trapdoor |TD|, which are presented in Table 4. In the table, the notations |G1|, |G2| and |Zq| denote the bit length size for each element in G1, G2 and Zq, respectively. It is clearly see that the size of ciphertext of our scheme is the same as Yang et al.’s scheme [28] and is smaller than Cheng et al.’s scheme [37], a sightly larger than other schemes; same as Yang et al.’s scheme [28], the size of trapdoor of our scheme is smaller than other schemes except Ma et al.’s scheme [4].

Finally, we present some additional performance comparisons in the Table 5. In the table, SCF denotes designated server test, AUT denotes authenticated function, BSE denotes bidirectional searchable encryption and ASSUM denotes the difficulty assumption of the scheme security depends on. Finally, we find that our scheme is a certificateless authenticated bidirectional searchable encryption scheme with a designated server test that achieves both MCI and MTP security under the CBDH hardness assumption.

7  Conclusion

Based on the certificateless public key authenticated encryption with keyword search (CL-PAEKS) cryptosystem and the bidirectional searchable functionality, this paper proposed a new cryptographic approach named blockchain-based certificateless authenticated bidirectional searchable encryption (CL-BSE). To some extent, it can be regarded as avoiding the key escrow and certificate management problem in the PEBKS scheme, and can also be considered as appending distinctive features which allow a data owner to retrieve the keyword ciphertext from server in the CL-PAEKS cryptosystem. Taking the cloud email system as the actual application scenario, we build a concrete construction of the CL-BSE scheme. The security analysis of the scheme indicates that it can achieve both MCI-secure and MTP-secure against IKGA under the CBDH hardness assumption.

Acknowledgement: The authors wish to express their appreciation to the reviewers for their helpful suggestions which greatly improved the presentation of this paper.

Funding Statement: This work was supported by the National Natural Science Foundation of China (Nos. 62172337, 62241207) and Key Project of Gansu Natural Science Foundation (No. 23JRRA685).

Author Contributions: The authors confirm contribution to the paper as follows: study conception and design: Y. Sun, X. Du; data collection: Y. Sun; analysis and interpretation of results: Y. Sun, X. Du, X. Yang; draft manuscript preparation: Y. Sun, S. Niu. All authors reviewed the results and approved the final version of the manuscript.

Availability of Data and Materials: The authors confirm that the data supporting the findings of this study are available within the article.

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.

References

1. Song, D., Wagner, D., Perrig, A. (2000). Practical techniques for searching on encrypted data. IEEE Symposium on Security and Privacy, pp. 44–55. Berkeley, USA.

2. Boneh, D., di Crescenzo, G., Ostrovsky, R., Persiano, G. (2004). Public key encryption with keyword search. International Conference on the Theory and Applications of Cryptographic Techniquespp, pp. 506–522. Interlaken, Switzerland.

3. Baek, J., Safavi-Naini, R., Susilo, W. (2008). Public key encryption with keyword search revisited. International Conference on Computational Science and its Applications, pp. 1249–1259. Perugia, Italy.

4. Ma, M., He, D., Kumar, N., Choo, K. K. R., Chen, J. (2018). Certificateless searchable public key encryption scheme for industrial Internet of Things. IEEE Transactions on Industrial Informatics, 14(2), 759–767.

5. Peng, Y., Cui, J., Peng, C., Ying, Z. (2014). Certificateless public key encryption with keyword search. China Communications, 11(11), 100–113.

6. Byun, J. W., Rhee, H. S., Park, H., Lee, D. H. (2006). Off-line keyword guessing attacks on recent keyword search schemes over encrypted data. Third VLDB Workshop on Secure Data Management, pp. 75–83. Seoul, Korea.

7. Huang, Q., Li, H. (2017). An efficient public-key searchable encryption scheme secure against inside keyword guessing attacks. Information Sciences, 403(C), 1–14.

8. Qin, B., Chen, Y., Huang, Q., Liu, X., Zheng, D. (2020). Public-key authenticated encryption with keyword search revisited: Security model and constructions. Information Sciences, 516, 515–528.

9. Pan, X., Li, F. (2021). Public-key authenticated encryption with keyword search achieving both multi-ciphertext and multi-trapdoor indistinguishability. Journal of Systems Architecture, 115(C), 102075.

10. Al-Riyami, S. S., Paterson, K. G. (2003). Certificateless public key cryptography. 9th International Conference on the Theory and Application of Cryptology and Information Security, pp. 452–473. Taipei, Taiwan.

11. He, D., Ma, M., Zeadally, S., Kumar, N., Liang, K. (2018). Certificateless public key authenticated encryption with keyword search for industrial internet of things. IEEE Transactions on Industrial Informatics, 14(8), 3618–3627.

12. Yang, X., Wen, H., Liu, L., Ren, N., Wang, C. (2023). Blockchain-enhanced certificateless signature scheme in the standard model. Mathematical Biosciences and Engineering, 20(7), 12718–12730.

13. Zhang, W., Qin, B., Dong, X., Tian, A. (2021). Public-key encryption with bidirectional keyword search and its application to encrypted emails. Computer Standards & Interfaces, 78, 103542.

14. Curtmola, R., Garay, J., Kamara, S., Ostrovsky, R. (2011). Searchable symmetric encryption: Improved definitions and efficient constructions. Journal of Computer Security, 19(5), 895–934.

15. Kamara, S., Papamanthou, C. (2013). Parallel and dynamic searchable symmetric encryption. International Conference on Financial Cryptography and Data Security, pp. 258–274. Okinawa, Japan.

16. Li, J., Huang, Y., Wei, Y., Lv, S., Liu, Z. et al. (2021). Searchable symmetric encryption with forward search privacy. IEEE Transactions on Dependable and Secure Computing, 18(1), 460–474.

17. Rhee, H. S., Park, J. H., Susilo, W., Lee, D. H. (2010). Trapdoor security in a searchable public-key encryption scheme with a designated tester. Journal of Systems and Software, 83(5), 763–771.

18. Chen, R., Mu, Y., Yang, G., Guo, F., Huang, X. et al. (2016). Server-aided public key encryption with keyword search. IEEE Transactions on Information Forensics and Security, 11(12), 2833–2842.

19. Hu, C., Liu, P. (2012). An enhanced searchable public key encryption scheme with a designated tester and its extensions. Journal of Computers, 7(3), 716–723.

20. Tang, Q., Chen, L. (2010). Public-key encryption with registered keyword search. Proceedings of the 6th European Workshop on Public Key Infrastructures, Services and Applications, pp. 163–178. Pisa, Italy.

21. Wu, T. Y., Chen, C. M., Wang, K. H., Pan, J. S., Zheng, W. et al. (2018). Security analysis of Rhee et al.’s public encryption with keyword search schemes: A review. Journal of Network Intelligence, 3(1), 16–25.

22. Yau, W. C., Phan, R. C. W., Heng, S. H., Goi, B. M. (2013). Keyword guessing attacks on secure searchable public key encryption schemes with a designated tester. International Journal of Computer Mathematics, 90(12), 2581–2587.

23. Noroozi, M., Eslami, Z. (2019). Public key authenticated encryption with keyword search: Revisited. IET Information Security, 13(4), 336–342.

24. Cheng, L. X., Meng, F. (2021). Security analysis of Pan et al.’s “Public-key authenticated encryption with keyword search achieving both multi-ciphertext and multi-trapdoor indistinguishability”. Journal of Systems Architecture, 119, 102248.

25. Fuhr, T., Paillier, P. (2007). Decryptable searchable encryption. Proceedings of the First International Conference on Provable Security, pp. 228–236. Wollongong, Australia.

26. Hofheinz, D., Weinreb, E. (2008). Searchable encryption with decryption in the standard model. Cryptology ePrint Archive.

27. Wu, T. Y., Chen, C. M., Wang, K. H., Wu, J. M. T. (2019). Security analysis and enhancement of a certificateless searchable public key encryption scheme for IIoT environments. IEEE Access, 7, 49232–49239.

28. Yang, G., Guo, J., Han, L., Liu, X., Tian, C. (2022). An improved secure certificateless public-key searchable encryption scheme with multi-trapdoor privacy. Peer-to-Peer Networking and Applications, 15(1), 503–515.

29. Lu, Y., Li, J. (2019). Constructing certificateless encryption with keyword search against outside and inside keyword guessing attacks. China Communications, 16(7), 156–173.

30. Shiraly, D., Pakniat, N., Noroozi, M., Eslami, Z. (2022). Pairing-free certificateless authenticated encryption with keyword search. Journal of Systems Architecture, 124, 102390.

31. Boneh, D., Franklin, M. (2003). Identity-based encryption from the weil pairing. SIAM Journal on Computing, 32(3), 586–615.

32. Barreto, P. S. L. M., Kim, H. Y., Lynn, B., Scott, M. (2002). Efficient algorithm for pairing-based cryptosystems. 22nd Annual International Cryptology Conference Santa Barbara, pp. 354–369. California, USA.

33. Joux, A. (2002). The weil and tate pairing as building blocks for public key cryptosystems. 5th International Algorithmic Number Theory Symposium, pp. 20–32. Sydney, Australia.

34. Han, M., Xu, P., Xu, L., Xu, C. (2022). TCA-PEKS: Trusted certificateless authentication public-key encryption with keyword search scheme in cloud storage. Peer-to-Peer Network Appliction, 16(1), 156–169.

35. Uwizeye, E., Wang, J., Cheng, Z., Li, F. (2019). Certificateless public key encryption with conjunctive keyword search and its application to cloud-based reliable smart grid system. Annals of Telecommunications, 74(7), 435–449.

36. Chenam, V. B., Ali, S. T. (2022). A designated cloud server-based multi-user certificateless public key authenticated encryption with conjunctive keyword search against IKGA. Computer Standards & Interfaces, 81(C), 103603.

37. Cheng, L. X., Meng, F. (2023). Certificateless public key authenticated searchable encryption with enhanced security model in IIoT applications. IEEE Internet of Things Journal, 10(2), 1391–1400.

38. PBC Library: The pair-based cryptography library. http://crypto.stanford.edu/pbc/ (accessed on 06/01/2023).

images
This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.