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

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.