Multi-Recipient encryption with keyword search without pairing for cloud storage

With the rapid development of cloud computing technology and communication technology, cloud storage has become a tool used by people in daily life. Cloud storage service enables users to outsource data to cloud servers and retrieve desired document efficiently. Individual privacy in outsource data are very sensitive and should be prevented from any leakage. Public-key encryption with keyword search (PEKS) scheme resolves this tension, while public-key authentication encryption with keyword search (PAEKS) scheme improve its keyword guessing attacks problem potentially. Whereas, the loss of keyword privacy, the limitation of single user interaction and low efficiency make PEKS/PAEKS schemes far from enough in practical applications.In this paper, we develop a multi-recipient public key encryption scheme with keyword search without pairing (MREKS) for cloud storage under public key infrastructure. The proposed scheme has the merits of supporting multi-recipient keyword search way as well as requiring no expensively bilinear pairing operations under standard model. We present a concrete and efficient construction of MREKS, and prove its security based on discrete logarithm assumptions. Furthermore, we embed the algorithm of data plaintext encryption and decryption into the scheme, which makes the scheme more practical. We show that our scheme enjoys much more efficiency than previous PEKS/PAEKS scheme in the simulation experiment, especially the keyword encryption is optimized by 79.5%.

In recent years, the amount of electronic data generated on various platforms such as the internet has seen an explosive growth. From the view of government, enterprises or individual, the increasing amount of data creates data management issues. To store this data, the user needs to maintain the hardware, software and systems for the data storage locally. It caused great overhead on the user’s server, which has seriously affected the efficiency and flexibility of the user to utilize the data.

Cloud storage services in cloud computing technology alleviate this tension, which means users can obtain and pay for the server resources provided by cloud server without interaction largely and only need management work slightly. Due to the convenience and flexible of cloud service and varied charging properties, users are willing to store their local data in the cloud server. People can upload their data, such as email address, personal health record and financial data, into the cloud for sharing with other person or using it by themselves in anywhere. Moreover, cloud storage services are widely used in medical institutions, enterprises, schools and other application scenarios.

However, cloud storage has an inevitable drawback: users share or store data in the cloud server, so the ownership of the data is held by the cloud server. As a result, the cloud server can inadvertently obtain the data uploaded by users, leading to the divulge of sensitive privacy data without user’s authority. To avoid this case, users can only encrypt and upload document to the cloud. However, if users want to acquire target document, they download all the ciphertext data and decrypt it locally necessarily. It is unfriendly to users with large data storage capacity, which will result in huge resource waste and computing overhead. Moreover, this approach is hardly applicable to users with low broadband networks.

To address the above issue, the concept of searchable encryption has been proposed. As depicted in Fig. 1, a searchable encryption scheme works.

Model of searchable encryption

Full size image

Therefore, the data security and privacy becomes an important issue. To date, many methods are proposed to protect privacy and security of cloud data [1–8].

Based on previous studies by researchers, searchable encryption divide into symmetric and asymmetric searchable encryption (SE). The work of Song et al. [1] is pioneering in constructing a symmetric SE scheme in 2000. His ideas were groundbreaking, but there were inevitable efficiency problems because the efficiency of finding the target document is linear length. Boneh et al. [2] constructed public-key encryption with keyword search, denoted by BDOP-PEKS. It is a branch of SE that keeps the confidentiality of the encrypted data. The BDOP-PEKS scheme is mainly applied in the mail routing scenario, in which three participants, namely the sender, the recipient and the mail server. The sender encrypts the message and keyword corresponding to the message via recipient’s public key, and the recipient generates the search trapdoor via private key by himself. Finally, the mail server performs data retrieval and returns the message ciphertext with corresponding keyword to recipient.

Later, Baek et al. [3] found flaws in PEKS scheme and developed a secure channel free public key encryption with keyword search based on the BDOP-PEKS scheme, denoted by BSS-PKE/PEKS, which solved the issue of supplying secure channel when delivering keywords to the server. BSS-PKE/PEKS scheme performs via public channel, but it’s still subject to a connatural security restriction: suffering off-line keyword guessing attacks (KGA). Specifically, given a keyword trapdoor, an adversary encrypts whole keyword candidates by using the recipient’s public key and identifies the ciphertext which matches the targeted trapdoor, this enables the adversary to recover the keyword hidden in keyword trapdoor to invade the users’ privacy. Public key authentication encryption with keyword search (PAEKS) was first proposed by Huang et al. [9], in which the sender’s secret key is presented into the keyword encryption, so as to achieve the keyword trapdoor privacy and resist the keyword guessing attacks. Soon afterwards, Huang’s scheme was proposed that it could not ensure the keyword ciphertext indistinguishability.

In such an architecture, previous PEKS and PAEKS schemes have been based on bilinear pairings operation, which can greatly restrict efficiency when running on devices with limited communication and computing capacity.

Traditional PEKS schemes for mail routing take into account single-user interactions, especially PAEKS scheme, where sharing data requires generating search trapdoor for the uniform keywords for each receiver. In fact, it will greatly reduce the desire of enterprise practical application, since it still consumes a lot of storage resources to meet this search requirement. At present, the security of most PEKS schemes is not good enough to resist KGA. One reason is that the low-entropy feature of the keywords leads to KGA.

Therefore, we initiated the proposal of MREKS scheme to address the defects mentioned above.

Contribution

In this paper, we put forward a multi-recipient encryption with keyword search scheme without pairing for cloud storage based on public key infrastructure in virtue of the idea of Lu et al. [10](see related work). The proposed scheme not only supports multi-recipient authentication keyword search function, but also does not use the expensively bilinear pairing. We formally define the system model and security for the proposed MREKS and demonstrate the security of its under standard model. More specifically, our contributions are summarized as below:

Functionality: We construct a new multi-recipient PAEKS scheme without pairing for cloud storage under public key infrastructure. Let’s consider a scenario where a user (i.e., a data sender) gathers transaction data and shares them with multiple recipients (e.g., a group of colleague in the company). Most PEKS and PAEKS schemes [2, 3, 9, 11, 12] merely support single recipient. The user has to generate a search trapdoor of same keyword for each recipient individually by using the above scheme. In this case, it will be inefficient and inconvenient awfully. To address the above issues, we create a single keyword encryption for a set of authorized recipients with high efficiency communication and computation.

Practicality: We embed message encryption and decryption to make MREKS scheme more practical. Most of PEKS and PAEKS schemes hardly support message encryption and decryption. In this case, the scheme are incompletely. In consequence, we adds this algorithm to keep the transmission of symmetric key confidentiality in the public channel and avoid transmitting the symmetric key via security channel. It is amicable for us to decrypt ciphertext commodiously. Moreover, the message decryption must match the corresponding keyword to decrypt it, which ensures the privacy of message and keyword in the transmission.

Security: The proposed of MREKS scheme provides privacy-preserving keyword search and data encryption. We prove the scheme prevent keyword guessing from attack successfully under standard model and plaintext privacy security. It is worth noting that we embed the recipient’s private key in the keyword encryption process to avoid the possibility of outside adversary attack. Without the ability to produce valid ciphertext, the adversary is not able to carry out a successful keyword guessing attack. In this way, our scheme provides to resist attacks from adversary.

Efficiency: Our scheme avoids the expensively bilinear pairing. In various application scenarios, the computations are often performed on smart devices with constrained resources, such as telephone or handheld terminals. Most of the previous PEKS and PAEKS schemes [2, 3, 9, 13] were built with the bilinear pairing. If we use the without pairing scheme, the efficiency will be greatly improved. Also, it has more practical significance in the use of equipment with limited communication and computing capacity. We analyze the running overhead of MREKS theoretically and implement it utilizing C language and PBC library [14]. The analysis and experiment results show that our scheme has more efficiency running overhead with previous PEKS and PAEKS schemes.

The first asymmetric SE is presented by Boneh et al. [2] in 2004. Baek et al. addresses the Boneh’s problem of working via security channel in 2008. Soon afterwards, with kinds of functions of PEKS scheme have been proposed. The working of Byun et al. [15] and Yau et al. [16] clearly that the current PEKS program are suffering from a novel attack, calls off-line keyword guessing attack. In their research, the previous program could not resist off-line keyword guessing attacks from the cloud servers. Based on Baek et al’s work, Fang et al. [5] enhance security property and ensure the keyword security of the scheme under standard model. While the work of Fang et al. seems perfect, there are still keyword privacy problems. Therefore, the privacy of keywords in public key encryption with keyword search scheme has become an issue to be addressed by researchers.

The idea of “Trapdoor Indistinguishability” is proposed by Rhee et al. [6]. In their work, trapdoor indistinguishability is a sufficient condition under keyword security. Therefore, KGA under different assumption context is whether the success of determines the security of scheme. Based on various scenarios, we classify attackers as internal attackers or external attackers. In other words, an external adversary’s attacks can be considered online KGA, since the adversary can produce the keyword ciphertext to guess in testing process by intercepting the user’s search trapdoor. Similarly, an internal adversary’s attacks (denotes semi-honest cloud server) can be considered off-line KGA, since the adversary is able to carry out test algorithm. The authority of the semi-honest cloud servers is power than the external attacker due to the cloud servers’ testing executive capability.

Later, Huang et al. [9] constructed a new public key authentication encryption with keyword search to against inside adversary’s attack. Ma et al. [17] put forward to certificateless public key encryption with keyword search in the internet of thing (denote IOT) environment. Lu et al. [18] introduced a search trapdoor via key agreement between sender and receiver, which can resist the known KGA. Later, Ma et al. [19] constructed the scheme of SCF-CLSPE to achieve IND-CKA security for smart healthcare. Noroozi et al. [20] put forward to a generic construction secure against online and offline KGA scheme. Qin et al. [13] aimed at the revisited of the scheme proposed by Huang et al. [9], and introduced that the keyword privacy of Huang et al.’s scheme was insufficient, that is, it could not meet the multi-keyword ciphertext guessing attack securely. A verifiable public key SE was proposed after its improvement, which can achieving multi-keyword ciphertext indistinguishability. Pan et al. [11] has improved the work of Qin et al., and proposed to simultaneously ensure the multi-keyword ciphertext indistinguishability and multi-keyword trapdoor security. Whereafter, Cheng et al. [12] point out the work of Pan et al. a serious mistake in the security proof and Qin et al. [21] improved their multi-keyword ciphertext indistinguishability security model[13].

Chen et al. [22] brought up with a new type of public-key SE that can resist inside adversary’s off-line keyword guessing attacks, namely server-aid public-key SE. In this scheme, blind keyword signature is provided by the server and returned to the user for keyword encryption. The key of blind signature of the server has the merit of key update for each sub-server, which makes the scheme more flexible. Zhang et al. [23] promoted the public key searchable encryption scheme based on the blockchain-based public chain application and was able to resist keyword guessing attacks. He et al. [24] and Li et al. [25] came up with PAEKS into certificateless keyword search and identity based encryption settings, respectively. Li et al. [26] put forward to a new public key searchable encryption scheme for single-user to multi-user interaction under the hierarchical identity mechanism and attribute encryption mechanism, and this scheme designed a public key searchable encryption scheme that supports transparent user access control. The scheme not only protects the privacy of keyword search, but also supports the users with private key to search ciphertext. Lu et al. [10] presented a new multi-recipient cetificateless public key searchable encryption scheme for IIOT, which supporting muti-user interaction function and no costly computation. Based on this contribution, we introduce this contribution into our scheme to better apply to cloud storage in PKI.

In addition to keyword searching, some schemes of public key cryptosystem in PEKS variants are also studied, including fuzzy keyword search [27], verifiable keyword search [28], lattice-based encryption with keyword search [29] and attribute-based keyword search [30].

Complexity assumptions

Definition 1.(Discrete Logarithm(DL) assumption [31]) Let G be a cyclic group of prime order q with a generator g. Select a∈Z_q, for every arbitrary probability ε with a polynomial time t, there exists an algorithm A(t,ε) for solving DL problem, if Pr[A(g,g^a)=a]<ε.

Definition 2. (Hash Diffie-Hellman(HDH) problem [32]) Let G be a cyclic group of prime q and g be a generator of G. H:{0,1}^∗→{0,1}^l is a hash function, where l is a binary number. Given hash function H and tetrad (g,g^a,g^b,Z)∈G³×{0,1}^l where \(a,b\in {Z_{q}^{*}}\) and Z is a random element of {0,1}^l. HDH problem is to judge whether Z=H(g^ab).

Definition 3. (Computational Diffie-Hellman (CDH) Problem [32]) Let G be a cyclic group of prime q and g be a generator of G. Given a binary tuple (g^a,g^b)∈G² for unknown integers \(a,b \in Z_{q}^{*} \), the CDH problem in the group G is to calculate g^ab.

System model of mREKS

The proposed of MREKS model display in Fig. 2, including six polynomial time algorithms:

System model of MREKS

Full size image

1) GlobalSetup(λ): Input a security parameter λ, and output global parameter GP.

2) KeyGen(GP): Input global parameter GP, and output a secret/public key pair (sk_u,pk_u) for user.

3) Encrypt(GP,sk_S,(pk₁,pk₂,...,pk_n)_R,w,M): Input GP, sk_S, multi-recipient’s public key (pk₁,pk₂,...,pk_n)_R, a keyword w and a message M, where n is number of recipient. Outputs ciphertext C=(C_w,C_M), where C_w is keyword ciphertext and C_M is message ciphertext.

4) Trapdoor(GP,sk_R,pk_S,w^′): Input GP, sk_R,pk_S, and a search keyword w^′, and output a keyword trapdoor \(\phantom {\dot {i}\!}T_{w^{\prime }}\).

5) \(\phantom {\dot {i}\!}Test(GP, C_{w}, T_{w^{\prime }})\): Input GP, \(\phantom {\dot {i}\!}C_{w}, T_{w^{\prime }}\), and output a symbol “1” if w=w^′ or “0” otherwise.

6) Decrypt(GP,w^′,C_M,pk_S,sk_R): Input GP, C_M, a keyword w^′,pk_S and sk_R. Output plaintext message M.

Security definition

This section we introduce the security definition of our proposed MREKS scheme. The security definition of ciphertext indistinguishability MREKS under the chosen keyword guessing attacks (denote CMREKS-CKA), trapdoor indistinguishability MREKS under the chosen keyword guessing attacks (denote TMREKS-CKA) and plaintext privacy MREKS against chosen plaintext attacks (denote PP-MREKS-CPA) are as follow:

CMREKS-CKA game

This game is simulated between A and a challenger B, where A is inside or outside adversary.

GlobalSetup: Given security parameters λ, B produces global parameters GP, a sender and recipients’ secret/public key pair (sk_S,pk_S) and (sk_R,pk_R), and sends pk_S,pk_R and GP to A.

Query Phase 1:A does O^Ciphertext,O^Trapdoor and O^Test to B adaptively, then B simulates the corresponding algorithm in MREKS scheme and return the results.

Challenge:A submits two keywords (w₀,w₁) to B, which he/she has not submit to O^Ciphertext in above Query phase 1. Finally, B returns a keyword ciphertext \(\phantom {\dot {i}\!}C_{w_{b}}\) with b∈_R{0,1}.

Query Phase 2:A continues to ask for B adaptively, but with the restrictions that A can not queries w₀ or w₁ in ciphertext or trapdoor.

Guess:A returns b^′∈{0,1} and A wins in this game, if b=b^′.

The advantage of A in CMREKS-CKA Game is defined as follows:

Definition 3. An MREKS scheme achieve the CMREKS-CKA security if no polynomial time adversary can obtain a non-negligible advantage in CMREKS-CKA game.

TMREKS-CKA game

This game is simulated between A and a challenger B, where A is inside or outside adversary.

GlobalSetup: Same as that in CMREKS-CKA Game.

Query Phase 1: Same as that in CMREKS-CKA Game.

Challenge:A submits two keywords (w₀,w₁) to B, which he/she has not submit to O^Ciphertext in above Query phase 1. Finally, B returns a keyword trapdoor \(\phantom {\dot {i}\!}T_{w_{b}}\) with b∈_R{0,1}.

Query Phase 2:A continues to ask for B adaptively, but with the restrictions that A can not queries w₀ or w₁ in ciphertext or trapdoor.

Guess:A returns b^′∈{0,1} and A wins in this game, if b=b^′.

The advantage of A in TMREKS-CKA Game is defined as follows:

Definition 4. An MREKS scheme achieve the TMREKS-CKA security if no polynomial time adversary can obtain a non-negligible advantage in TMREKS-CKA game.

PP-MREKS-CPA game

This game is simulated between A and a challenger B.

Setup: Same as that in CMREKS-CKA Game.

Query Phase 1:A can issue at most q_M queries to the encryption oracle O^M below.

O^M: A submits plaintext M with keyword w to B, and then B returns ciphertext C.

Challenge:A submits a keyword w and two plaintext M₀ and M₁. The constraint is that A cannot be submitted M₀ or M₁ to O^E. B picks a bit b∈{0,1} randomly. Next, B generates a ciphertext C. Finally, B returns ciperhetext C to A.

Query Phase 2:A issues queries to the oracle same as in Query Phase 1 with the constraints that A cannot be submitted M₀ or M₁ with w to O^E.

Guess:A returns a bit b^′ and wins the game if b^′=b.

The advantage of A in PP-MREKS-CPA Game is defined as follows:

Definition 5. An MREKS scheme achieve the PP-MREKS-CKA security if no polynomial time adversary can obtain a non-negligible advantage in PP-MREKS-CKA game.

This section we introduce our MREKS scheme. The scheme is described as follows.

1) GlobalSetup(λ): Given the security parameter 1^λ, trusted servers picks a q-order cyclic group G. Let g is the generator of G. Furthermore, it selects four hash functions \(H_{1}: G \to \{0,1\}^{l}, H_{2}: \{0,1\}^{*}\times \{0,1\}^{l}\to Z_{q}^{*}, H_{3}: G \to Z_{q}^{*}, H_{4}:\{0,1\}^{l}\times \{0,1\}^{*}\times Z_{q}^{*} \times G \times \{0,1\}^{*}\times \{0,1\}^{*}\times Z_{q}^{*}\to \{0,1\}^{l}\), where l is denotes the binary length of hash values. Finally, it outputs the global parameters GP={q,g,G,H₁,H₂,H₃,H₄}.

2) KeyGen(GP): Takes GP as input. The user (including sender and recipients) generates its secret/public key as follow.

• Selects \(\phantom {\dot {i}\!}sk_{u_{1}}, sk_{u_{2}}\in _{R} Z_{q}^{*}\);

• Computes \(\phantom {\dot {i}\!}pk_{u_{1}}=g^{sk_{u_{1}}}\) and \(\phantom {\dot {i}\!}pk_{u_{2}}=g^{sk_{u_{2}}}\);

• Sets \(\phantom {\dot {i}\!}sk_{u}=(sk_{u_{1}},sk_{u_{2}})\) and \(\phantom {\dot {i}\!}pk_{u}=(pk_{u_{1}},pk_{u_{2}})\) as user’s secret/public key pair.

3) Encrypt(GP,pk_S,sk_S,(pk₁,pk₂,...,pk_n)_R,w,M): Takes GP, pk_S,sk_S, a keyword w, multi-recipient’s public key (pk₁,pk₂,...,pk_n)_R and a message M as input, where the subscript S indicates sender, the subscript R indicates recipient and n is the number of recipients. The sender selects \(r\in Z_{q}^{*}, K\in \{0,1\}^{l}\) randomly and encrypt w and M as below:

• Computes \(\phantom {\dot {i}\!}\mu _{i}=H_{1}(pk_{iR_{1}}^{sk_{S_{1}}})\) and \(\phantom {\dot {i}\!}\theta _{i}=H_{1}(pk_{iR_{2}}^{sk_{S_{2}}})\) for each i=1,2,...,n and n is the number of recipients;

• Selects two random integer \(\eta, \gamma \in Z_{q}^{*}\) and then define two polynomial f(x) and g(x) of degree n as follows:

  \(f(x)=\prod \limits _{i=1}^{n}{(x-{v_{i}})}+\gamma ={x^{n}}+{\alpha }_{n-1}{x^{n-1}}+\cdots +{\alpha _{1}}x+{\alpha _{0}}\), where \({\alpha _{i}}\in Z_{q}^{*}\) and \(\phantom {\dot {i}\!}v_{i}=H_{3}(g^{r{H_{2}}(w||\mu _{i})})\) and the operator “ ||” denotes the concatenation of two strings;

  \(g(x)=\prod \limits _{i=1}^{n}{(x-{s_{i}})}+\eta ={x^{n}}+{\beta }_{n-1}{x^{n-1}}+\cdots +{\beta _{1}}x+{\beta _{0}}\), where \({\beta _{i}}\in Z_{q}^{*}\) and \(\phantom {\dot {i}\!}s_{i}=H_{3}\left (pk_{S_{2}}^{(H_{2}(w||\theta _{i})-r)}\right)\);

• Sets

  \(\phantom {\dot {i}\!}C_{1}=K\oplus H_{1}(pk_{S_{2}}^{\eta }),\)

  C₂=AESEnc_K(M),

  \(\phantom {\dot {i}\!}C_{3}=r \cdot sk_{S_{1}}^{-1}\),

  \(\phantom {\dot {i}\!}C_{4}=g^{{-sk_{S_{2}}} \cdot r}\),

  C₅=(α₀,α₁,...,α_n−1),

  C₆=(β₀,β₁,...,β_n−1),

  C₇=H₄(C₁,C₂,C₃,C₄,C₅,C₆,γ);

Outputs the ciphertext C=(C₁,C₂,C₃,C₄,C₅,C₆,C₇).

4) Trapdoor(GP,sk_iR,pk_S,w^′): The recipient executes as below:

• Computes \(\phantom {\dot {i}\!}\mu _{i}'=H_{1}((pk_{S_{1}})^{sk_{iR_{1}}})\);

• Sets \(\phantom {\dot {i}\!}t_{1}=pk_{S_{1}}^{H_{2}(w'||\mu _{i}')}\);

Outputs the search trapdoor \(\phantom {\dot {i}\!}T_{w'}=t_{1}\).

5) \(\phantom {\dot {i}\!}Test(GP, C, T_{w'})\): The cloud sever executes as below:

• Parse C₅ as (α₀,α₁,...,α_n−1) and reconstruct the polynomial f(x)=xⁿ+α_n−1xⁿ⁻¹+⋯+α₁x+α₀;

• Computes \(\phantom {\dot {i}\!}v_{i}'=H_{3}({t_{1}}^{C_{3}})\) and γ^′=f(v_i^′) check whether C₇=H₄(C₁,C₂,C₃,C₄,C₅,C₆,γ^′) holds. If it does, output “1” or “0” otherwise.

6) Decrypt(GP,C,w^′,pk_S,sk_R): The recipient executes as below:

• Parse C₅ as (α₀,α₁,...,α_n−1) and reconstruct the polynomial f(x)=xⁿ+α_n−1xⁿ⁻¹+⋯+α₁x+α₀;

• Computes \(\phantom {\dot {i}\!}v_{i}'=H_{3}({t_{1}}^{C_{3}})\) and γ^′=f(v_i^′) check whether C₇=H₄(C₁,C₂,C₃,C₄,C₅,C₆,γ^′) holds. If it does, turn to next phase or abort otherwise;

• Parse C₆ as (β₀,β₁,...,β_n−1) and reconstruct the polynomial g(x)=xⁿ+β_n−1xⁿ⁻¹+⋯+β₁x+β₀;

• Computes \(\phantom {\dot {i}\!}\theta _{i}'=H_{1}((pk_{S_{2}})^{sk_{iR_{2}}})\).

• Sets \(\phantom {\dot {i}\!}t_{2}=pk_{S_{2}}^{H_{2}(w||\theta _{i}')}\) and si′=H₃(C₄·t₂).

• Computes \(\phantom {\dot {i}\!}\eta '=g({s_{i}^{\prime }})\) and \(\phantom {\dot {i}\!}K=C_{1}\oplus H_{1}(pk_{S_{2}}^{\eta '})\), then returns plaintext M, where M=AESDec_K(C₂).

Remark. The decryption algorithm cannot be performed until the cloud server has passed the test algorithm and returned ciphertext C to the recipient. Otherwise, the decryption algorithm is not performed.

Correctness verification.

If the target keyword w=w^′, then the above equation are equal. Thus, our scheme is correct.

This section we analysis the security of MREKS via game hopping [33].

Lemma 1(Difference Lemma [33]) Let E be some “error event” such that S₁|¬E occurs if and only if S₂|¬E occurs. Then

Theorem 1. The MERKS scheme realizes CMREKS-CKA game security under standard model, if H₁∼H₄ is the collision resistance hash function and HDH assumption is intractable.

Proof 1: Suppose that A is an internal or external adversary against the security of the proposed CMREKS-CKA game in polynomial time, A_H is the adversary of the hash function and A_HDH is the adversary of breaking the HDH assumption.

We prove the theorem 1 via five sub-game programs Game-j (j=0,1,2,3,4), and define Y_j are the events of A guessing correctly, that is b=b^′. Therefore, the game-hopping proof of CMREKS-CKA is as follow:

Game-0: Game-0 is the original attack CMREKS-CKA game, so A have Adv(λ)_A=| Pr[Y₀]−1/2|.

Game-1: In this sub-game, B picks \(\phantom {\dot {i}\!}sk_{S_{2}}, sk_{iR_{2}}, a, {c_{i}}\in Z_{q}^{*}\) randomly to calculate \(\phantom {\dot {i}\!}pk_{S}=(g^{a},g^{sk_{S_{2}}})\) and \(\phantom {\dot {i}\!}pk_{iR}=({g^{c_{i}}},g^{sk_{iR_{2}}})\) for each the number of recipients i=1,2,...,n, where g is the generator of group G. Other parameters is the same as Game-0. Obviously, Game-0 and Game-1 are indistinguishable from A. So, two sub-game is equal with the advantage of Pr[Y₀]= Pr[Y₁].

Game-2: Game-2 is similar to Game-1, except that B transforms to the respond queries and challenge pattern. B does the following queries:

- O^Ciphertext: A submits a keyword w to B, then B picks a random integer \(r\in Z_{q}^{*}\) and returns C=(C₁,C₂,...,C₇) to A.

- O^Trapdoor: A submits a keyword w^′ to B, and returns \(\phantom {\dot {i}\!}T_{w^{\prime }}=pk_{S_{1}}^{H_{2}(w'||\mu _{i}')}\), where \(\phantom {\dot {i}\!}\mu _{i}'=H_{1}\left (pk_{S_{1}}^{sk_{iR_{1}}}\right)\).

- O^Test: A submits C and \(\phantom {\dot {i}\!}T_{w^{\prime }}\) to B, then B returns 1 if \(\phantom {\dot {i}\!}{v_{i}}'=H_{3}({t_{1}}^{C_{3}})\) and \(\phantom {\dot {i}\!}C_{7}=H_{4}(C_{1},C_{2},C_{3},C_{4},C_{5},C_{6},\gamma =f({v_{i}}'))\) or 0 otherwise.

Challenge:A submits two different keywords (w₀,w₁), where w₀ or w₁ are not challenged in previous phase. B chooses \(r^{*} \in _{R} Z_{q}^{*}\) and b∈_R{0,1} and performs as follow:

a) Sets \(C_{3}^{*}=r^{*} \cdot (a^{-1})\) and \(\phantom {\dot {i}\!}C_{4}^{*}=g^{{-sk_{S_{2}}} \cdot r^{*}}\);

b) Computes \(\phantom {\dot {i}\!}\mu _{i}^{*}=H_{1}(({g^{c_{i}}})^{a})\).

c) Selects random integers \(s_{1}^{*}, s_{2}^{*},..., s_{n}^{*}, \eta ^{*}, \gamma ^{*} \in Z_{q}^{*} \) and define two polynomial

where \(\alpha _{i}^{*}\in Z_{q}^{*}\) and \(v_{i}^{*}=H_{3}\left (g^{r^{*}{H_{2}}(w_{b}||\mu _{i}^{*})}\right)\);

where \({\beta _{i}^{*}}\in Z_{q}^{*}\);

d) Selects \(C_{1}^{*}\in \{0,1\}^{l}, C_{2}^{*} \in \{0,1\}^{l}\) randomly

e) Sets

f) Returns \(C^{*}=\left (C_{1}^{*},C_{2}^{*},...,C_{7}^{*}\right)\) to A.

Therefore, the challenge ciphertext \(C^{*}=(C_{1}^{*},...,C_{7}^{*})\) is the effective ciphertext of the keyword w_b.

Game-1 and Game-2 will be uniform, if B asks for queries and challenge correctly. It means that A guesses correctly in both sub-game with the advantage of Pr[Y₂]= Pr[Y₃].

Game-3: Game-3 is the same as Game-2, except that B will abort the sub-game, if the following events occur.

Event E₁: A submits w to B in O^Ciphertext, including the keyword’s input satisfies w≠w_b, but

a. \(f(x)=f^{*}(x)=\prod \limits _{i=1}^{n}{\left (x-v_{i}^{*}\right)}+\gamma ^{*}\) for \(C_{4}=(\alpha _{0}^{*}, \alpha _{1}^{*},...,\alpha _{n-1}^{*})\), where \(\phantom {\dot {i}\!}v_{i}=v_{i_{b}}\) and \(\gamma ^{*}\in Z_{q}^{*}\).

b. \(C_{7}^{*}=H_{4}\left (C_{1}^{*},C_{2}^{*}, C_{3}^{*}, C_{4}^{*}, C_{5}^{*},C_{6}^{*}, \gamma ^{*}\right)\).

Event E₂: A submits w to B in O^Trapdoor, including the keyword’s input satisfies w≠w_b, but \(H_{2}(w||\mu _{i})=H_{2}(w_{b}||\mu _{i}^{*})\).

Remark. In the Event E₁, we do not consider the computation of polynomial function g(x). Even if A calculates the polynomial function \(g(x)=\prod \limits _{i=1}^{n}{\left (x-s_{i}^{*}\right)}+\eta ^{*}\), where \(s_{1}^{*}, s_{2}^{*},...,s_{n}^{*}, \eta ^{*} \in Z_{q}^{*}\), the keyword ciphertext cannot be matched in the cloud server.

Obviously, Game-2 and Game-3 are indistinguishable to A unless the event E₁∨E₂ occurs. Due to Difference Lemma, we have

Furthermore, it will be have A_H, if the event E₁ occurs. Therefore, A_H has the advantage of winning, if

where n is the number of recipient and q is random number of \({Z_{q}^{*}}\).

Similarly, it will be have A_H, if the event E₂ occurs. Therefore, A_H has the advantage of winning, if

Therefore, we induce the equation

Game-4: Game-4 is the same as Game-3, except that B picks a random element Z∈{0,1}^l instead of \(\phantom {\dot {i}\!}H_{1}(g^{a{{c_{i}}}})\) when generating the challenge of ciphertext. Obviously, B responds queries and chanllenge via HDH tuples \(\phantom {\dot {i}\!}(H_{1},g,g^{a},{g^{c_{i}}},Z)\) without revealing the integer of a and c_i. In consequence, Game-3 is equivalent to Game-4. A_HDH distinguish the element of \(\phantom {\dot {i}\!}{\mu _{i}}'=H_{1}(g^{a{{c_{i}}}})\) (for i=1,2,...,n) and Z with non-negligible advantage, if the HDH problem is addressed. Hence, A_HDH has the advantage to win Game-4 with

Z is a random integer of G, so A has the advantage of winning with Pr[Y₄]=1/2.

Next, A can guess correctly in the above sub-games with the advantage

Based on the triangle inequality, the above sub-games induce as follow:

The collision resistance property of the hash function H and the complication of HDH problem is complicated so that Adv(λ)_A is negligible in theorem 1.

Theorem 2. The MERKS scheme realizes TMREKS-CKA game security under standard model, if H₁∼H₄ is the collision resistance hash function and HDH assumption is intractable.

Proof 2: Suppose that A is an internal or external adversary against the security of the proposed TMREKS-CKA game in polynomial time, A_H is the adversary of the hash function and A_HDH is the adversary of breaking the HDH problem.

We prove the theorem 2 via five sub-game programs Game-j(j=0,1,2,3,4), and define Y_j are the events of A guessing correctly, that is b=b^′. Therefore, the game-hopping proof of TMREKS-CKA is as follow:

Game-0: Game-0 is the original attack TMREKS-CKA game, so A have Adv(λ)_A=| Pr[Y₀]−1/2|.

Game-1: This sub-game is the same as the Game-1 of theorem 1.

Game-2: Game-2 is similar to Game-1, except that B transforms to the respond queries and challenge pattern. B does the following queries:

- O^Ciphertext: A submits a keyword w to B, then B picks a integer \(r\in _{R} Z_{q}^{*}\) and returns C=(C₁,C₂,...,C₇) to A.

- O^Trapdoor: A submits a keyword w^′ to B, and returns \(\phantom {\dot {i}\!}T_{w'}=pk_{S_{1}}^{H_{2}(w'||\mu _{i}')}\), where \(\phantom {\dot {i}\!}\mu _{i}'=H_{1}((pk_{S_{1}})^{sk_{iR_{1}}})\).

- O^Test: A submits C and \(\phantom {\dot {i}\!}T_{w'}\) to B, then B returns 1 if \(\phantom {\dot {i}\!}{v_{i}}'=H_{3}\left ({t_{1}}^{C_{3}}\right)\) and C₇=H₄(C₁,C₂,C₃,C₄,C₅,C₆,γ=f(v_i^′)) or 0 otherwise.

Challenge:A submits two different keywords (w₀,w₁) to B, where w₀ and w₁ are not challenged in previous phase. B chooses b∈{0,1} randomly for a keyword trapdoor \(\phantom {\dot {i}\!}T_{w_{b}}=pk_{S_{1}}^{r\cdot H_{2}(w_{b}||\mu _{i}')}\), where \(\phantom {\dot {i}\!}\mu _{i}'=H_{1}(g^{a{{c_{i}}}})\). And then returns them to A.

Therefore, the challenge trapdoor is the effective trapdoor of the keyword w_b.

Game-1 and Game-2 will be uniform, if B asks for queries and challenge correctly. It means that A guesses correctly in both sub-game with the same advantage Pr[Y₂]= Pr[Y₁].

Game-3: This sub-game is the same as the Game-3 of theorem 1.

Therefore, we induce the equation

Game-4: This sub-game is the same as the Game-4 of theorem 1.

Therefore, A has the advantage of winning with Pr[Y₄]=1/2.

Next, A can guess correctly in the above game with the advantage

Based on the triangle inequality, the above sub-games induce as follow:

The collision resistance property of the hash function H and the complication of HDH problem is complicated so that Adv(λ)_A is negligible in theorem 2.

Theorem 3: The MREKS scheme realizes PP-MREKS-CPA game secure if AES encryption is IND-CPA secure and the CDH and DL assumptions holds.

Proof 3: The MREKS scheme leverages the AES to encrypt the plaintext M and hides the session key K into C₁. Hence, if C₁ does not divulge any information about the encryption key K, security of our MREKS will be based on AES. As long as we ensure the security of η is equivalent to ensuring the security of K, that is, we need to keep the keyword’s security, if the hash function is collision resistant. The following game is played between a PPT adversary A and the challenger B. Given a DL instances (G,g,g^a) and CDH instances (H₁,g,g^a,g^η), where \(a,\eta \in Z_{q}^{*}\), B works as follows.

GlobalSetup:B initializes the system to produce GP={q,g,G,H₁,H₂,H₃,H₄}. B sends GP, the public key of senders and recipients \(\phantom {\dot {i}\!}pk_{S}=(g^{sk_{S_{1}}},g^{sk_{S_{2}}})=(g^{sk_{S_{1}}},g^{a})\) and \(\phantom {\dot {i}\!}pk_{iR}=({g^{sk_{iR_{1}}}},g^{sk_{iR_{2}}})\) to A, where g is the generator of group G and each recipient denotes i=1,2,...,n.

Phase 1:A can issue queries to the hash oracle and encryption oracle \(\phantom {\dot {i}\!}O^{H_1}\), \(\phantom {\dot {i}\!}O^{H_3}, O^{H_4}\) and O^Ciphertext, respectively.

-\(\phantom {\dot {i}\!}O^{H_{1}}\): Given an element g^∗∈G, it returns l-bit random number h^∗ as the hash value H₁(g^∗).

-\(\phantom {\dot {i}\!}O^{H_{3}}\): Given an element g^′∈G, it returns a random number \(h' \in Z_{q}^{*}\) as the hash value H₃(g^′).

-\(\phantom {\dot {i}\!}O^{H_{4}}\): Given an arbitrary string length {0,1}^∗, it returns l bit string length {0,1}^l as the hash value H₄({0,1}^∗).

- O^Ciphertext: A submits a keyword w and a plaintext M to B, then B picks a random integer \(r\in Z_{q}^{*}\) and returns C=(C₁,C₂,...,C₇) to A.

Challenge:A submits to B its keyword w and two plaintexts (M₀,M₁). B generates a ciphertext C_b, where the random bit b decides which plaintext is encrypted in this ciphertext. B chooses \(r^{*}\in Z_{q}^{*}, b\in \{0,1\}\) randomly and performs as follow:

a) Selects random integers \(v_{1}^{*}, v_{2}^{*},...,v_{n}^{*}, \gamma ^{*}, {\eta ^{*}} \in Z_{q}^{*}\).

b) Computes \(\phantom {\dot {i}\!}s_{i}^{*}={H_{3}\left (pk_{S_{2}}^{(H_{2}(w_{b}||\theta _{i}^{*})-r^{*})}\right)}\), where \(\phantom {\dot {i}\!}\theta _{i}^{*}=H_{1}(pk_{iR_{2}}^{sk_{S_{2}}})\) and define two polynomial

where \(\alpha _{i}^{*} \in Z_{q}^{*}\);

where \(\beta _{i}^{*} \in Z_{q}^{*}\);

c) Computes

\(\phantom {\dot {i}\!}C_{1}^{*}=K\oplus {H_{1}(pk_{S_{2}}^{\eta ^{*}})}\),

\(C_{2}^{*}=AESEnc_{K}(M_{b})\),

\(\phantom {\dot {i}\!}C_{3}^{*}=(sk_{S_{1}})^{-1}r^{*}\),

\(\phantom {\dot {i}\!}C_{4}^{*}=g^{-ar^{*}}\);

d) Sets

\(C_{5}^{*}=(\alpha _{0}^{*}, \alpha _{1}^{*},...,\alpha _{n-1}^{*})\),

\(C_{6}^{*}=(\beta _{0}^{*}, \beta _{1}^{*},..., \beta _{n-1}^{*})\),

\(C_{7}^{*}=H_{4}(C_{1}^{*},C_{2}^{*}, C_{3}^{*}, C_{4}^{*}, C_{5}^{*}, C_{6}^{*}, \gamma ^{*})\);

f) Returns the ciphertext \(C_{b} = (C_{1}^{*},...,C_{7}^{*})\) to A.

Phase 2:A still can issue queries to the oracles same as in phase 1 except that the ciphertext C_b cannot appears in the decrypt oracle O^D.

Guess:A returns a bit b^′ and wins the game if b^′=b.

We define event E₁ and E₂.

E₁: A issues h^∗ to \(\phantom {\dot {i}\!}O^{H_{1}}\).

E₂: A issues \(\phantom {\dot {i}\!}g'=g^{a(H_{2}(w'||\theta _{i}')-r)}\) to \(\phantom {\dot {i}\!}O^{H_{3}}\),

In case E₁ happens, the challenger B solves the CDH problem via computing g^∗=g^aη.

In case E₂ happens, the challenger B solves the DL problem via computing \(g^{(H_{2}(w'||\theta _{i}')-r)}={g'}^{\frac {1}{a}}\).

If the DL and CDH assumption holds, E₁ and E₂ happens with a negligible probability. That is

where t is a (polynomial) upper bound on the number of queries.

In another case, E₁ and E₂ does not happen, the ciphertext C is random in A’s view and the session key K can be revealed with a negligible probability. That is

Therefore, A’s wining advantage is equal to or less than a negligible probability if AES encryption is IND-CPA secure and the DL and CDH assumption holds in this game.

Notice. We deduce that the computation of η is approximately the computation g^η, since the computation of s_i in the polynomial g(x) is to solve the DL assumption.

This section we evaluates the efficiency computation and communication cost of our scheme.

Now we present the following notions for basic operations in Table 1:

t_h: the cost for computing a map-to-point hash.

t_p: the cost for a bilinear pairing.

t_e: the cost for a modular exponentiation.

n: the number of recipients.

To give a more intuitive comparison, we test the time cost of the compared schemes by employing the PBC library on a laptop running Ubuntu 16.04 with Interl Core i5-4210U CPU @1.7-GHz and 11-GB RAM memory. A Type-A pairing was chosen and used to initialize the system, which owns the same security level as a 1024-bit RSA encryption.

The schemes proposed in [2, 3, 9, 13] are the based on bilinear pairing operation. Let G×G→G_T, where G_T is the bilinear map group.

The computation cost of the keyword encryption algorithm, trapdoor algorithm and test algorithm in MREKS and schemes [2, 3, 9, 13]. See Fig. 3 and Table 2. We run the keyword encryption algorithm 100 times for one keyword and recipient in our scheme’s average is about 1.594 ms. When the number of recipients increases to 10, our scheme costs about 15.42 ms. Compared to scheme [9], the computation cost of MREKS is reduced by 79.5% in keyword encryption phase. If the number of recipients is infinite, the keyword encryption efficiency of MREKS scheme will be more excellent than other PEKS schemes.

Time cost of ten keyword operations

Full size image

In addition, the time cost of trapdoor in our scheme is fast than previous PEKS scheme. We set the recipients is 10 and the time cost of keyword testing in MREKS scheme is about 1.53 ms, while that in [2, 3, 9, 13] is about 2.1 ms, 3.1 ms, 2.9 ms and 2.13 ms, respectively.

Remark. In order to prevent indeterminate and affected by the length of the plaintext as well as making a better comparison with PEKS schemes, the encryption and decryption of AES algorithm are not included in the ciphertext computation and communication.

Communication cost

To visually display the comparison of storage length between different schemes based on PBC library’s parameters, we now describle communication costs in Table 3 with the following notations:

|G|: the 512 bit-size of an element in G.

|G_T|: the 1024 bit-size of element in G_T.

\(|Z_{q}^{*}|\): the 128 bit-size of integer in \(Z_{q}^{*}\).

h: the 256 bit-size of a hash value.

n: the number of recipients.

We clearly have that MREKS scheme is less than the PEKS and PAEKS schemes [2, 3, 9, 13] in the size of keyword encryption algorithm. Especially as the number of recipients n increases, our scheme is relatively more efficient. Furthermore, the size of trapdoor in MREKS scheme is smaller than schemes [2, 3, 9, 13].

PAEKS scheme is a useful cryptographic paradigm that supplies a feasible solution to the issue of encrypted data retrieval for cloud storage. MREKS techniques are used to simultaneously provide authentication, no costly bilinear pairing operations as well as multi-recipient keyword search function. Furthermore, we embed the encryption of message to our scheme, and the decryption needs to match the corresponding keyword information, which ensures the privacy of message and keywords. We formally prove that it ensures keyword security without random oracles and plaintext security. Moreover, we evaluate the performance of the proposed of our scheme with the previous PEKS and PAEKS scheme. The results demonstrate that our scheme is much more efficient than the previous schemes, especially on the computation efficiency. It is expedite for user to search over encrypted data for cloud storage due to the feature.

The datasets generated during and/or analyzed during the current study are available from the corresponding author on reasonable request.

The authors would like to thank to anonymous reviewers for their valuable comments on the manuscript.

This work of Quan Zhou is supported by the National Key Research and Development Program of China (No. 2021YFA1000600). This work of Qiong Huang is supported by National Natural Science Foundation of China (61872152), Guangdong Major Project of Basic and Applied Basic Research (2019B030302008), and the Science and Technology Program of Guangzhou (201902010081). This work of Chunming Tang is supported by National Natural Science Foundation of China (61772147).

Authors and Affiliations

1. School of Mathematics and Information Science, Guangzhou University, Guangzhou, China

   Ningbin Yang, Quan Zhou & Chunming Tang

2. College of Mathematics and Informatics, South China Agricultural University, Guangzhou, China

   Qiong Huang

Contributions

Ningbin Yang put forward the main ideas and drafted the manuscript. Quan Zhou guided the research and participated in the discussion of the manuscript. Qiong Huang and Chunming Tang made suggestions for the article. All authors read and approve the final manuscript. All authors approve to be submitted in “Journal of Cloud Computing-Advances Systems and Applications”.

Corresponding authors

Correspondence to Quan Zhou or Chunming Tang.

Competing interests

The authors declare that they have no competing interests.

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Reprints and permissions