A New Searchable Encryption Scheme with Integrity Preservation Property

Abstract

Searchable encryption schemes allow documents’ owners to store their encrypted documents on servers, search for the desired keyword and then download only the desired encrypted file and then decrypt. Storing files on remote servers can be further developed, which, in addition to allow access to files at any location and at any time, it also gives the data owners the confidence that their files are stored without any change in the servers. This property can be interpreted as the integrity preservation property of encrypted documents in the searchable encryption schemes. Recently, in Yang et al. (Concurr Comput Pract Exp 29:e4211, 2017), Yang et al. proposed a semantic keyword searchable proxy re-encryption scheme and claimed their scheme resists against collusion and provides data privacy. However, in this paper, we show that unfortunately, their searchable encryption scheme does not provide the perfect security and their scheme is vulnerable against integrity contradiction attack. Our proposed attack is implemented in three different scenarios, its success probability of each scenario is one and its complexity is only one run of the scheme. We also improve Yang et al. scheme and show informally and formally that the improved scheme is secure against the attacks presented in this paper and also other known active and passive attacks. Comparisons also showed that the proposed scheme, in addition to the complete security it provides, is acceptable in terms of communication, storage and computational costs.

1 Introduction

One of today’s needs is remote storage resources that can be accessed comprehensively and from everywhere, such as Gmail servers, Yahoo mail, and etc. Users typically encrypt sensitive data on honest-but-curious or semi honest-but-curious servers. Encryption hides all information about the data, and the client must download and decrypt all encrypted documents so that he/she can find the document with the specific keyword. Searchable encryption schemes help the client to only download and then decrypt the specific document of target. In fact, searchable encryption schemes attempt to help the client searchs its document among encrypted files by disclosing minimum information to the server. At the same time, an issue that is often neglected is the integrity preservation of the encrypted documents during the transfer to the server or vice versa. If there is not any protection from encrypted documents, then the data owner or authorized client will never reach the correct and original document. Suppose these documents are related to the hospital patients. If this encrypted information is changed during the transfer to the server for storage or during the transfer to the data owner or the client access after searching a keyword, without the server or data owner or client realizing, it can lead to irreparable risks. For an example, changing patient test results may lead to misdiagnosis, which can have serious complications for the patient. So far, numerous searchable encryption schemes have been proposed [10, 13, 14, 19, 20, 22, 25, 26, 29, 30, 37, 40, 43, 44, 46]. The security analyzes that have been made afterward on the schemes such as [1, 15, 17, 18, 21, 23, 24, 31, 35, 38] have shown that they have not been able to fully achieve their security goals. In this paper, we analyze and improve a recently proposed protocol by Yang et al. [42].

1.1 Problem Statement and Our Contributions

Recently, Yang et al. [42] proposed a new semantic keyword searchable proxy re-encryption based on lattice and claimed their scheme satisfies documents and keywords privacy. However, in this paper, we show that their scheme is vulnerable against integrity contradiction attack. Our attack can be implemented in three different scenarios. In any scenario, the probability of success is equal to one and its complexity is only one run of the scheme. In addition, we improve their scheme and show that the improved scheme is resistant against the attack proposed in this paper and also other known active and passive attacks. Comparing the proposed scheme with other related schemes shows that in addition to providing complete security, it also has acceptable computational, communication and storage costs.

1.2 Related Work

In general, the related work in this paper is divided into three categories of searchable encryption, proxy re-encryption and proxy re-encryption with keyword search that we will explain in each case.

Searchable Encryption Searchable Encryption is the best encryption for cloud servers or databases due to lower cost of data decryption on the server and searchable data. In 2000, Song et al. [34] proposed the first symmetric searchable encryption scheme in which the private key cryptographic structure was used. In the following years, other schemes were presented (see [9, 12, 16]), but the problem was that these structures were suitable for single writer/single reader (S/S) architecture and were not well structured for multi writer/single reader (M/S) projects due to the high cost of building secure channels for private key transfer. In 2004, Boneh et al. [7] provided the first public key searchable encryption scheme called Public key Encryption with Keyword Search (PEKS). Later, a lot of schemes were presented in the field of PEKS that referred to Ma et al.’s scheme [27] (called secure channel free certificateless searchable public key encryption with multiple keywords) that was presented for use in Internet of Things (IoT). The scheme used public channels to transmit messages, but the scheme was vulnerable to keyword guessing attack. In 2018, Wu et al. [37] presented a scheme which, in addition to resistance to the keyword guessing attack, was resistant against file injection attack.

Proxy Re-Encryption Proxy Re-Encryption (PRE) concept, which was introduced by Blaze, Bleumer and Strauss [6] in 1998, refers to that a third party (the same proxy server) converts the data owner encrypted document into the data user encrypted document using his public key, while a proxy server must not obtain any useful and valuable information. This scheme was bidirectional PRE, which means that changing the encrypted document into the opposite direction (i.e., the data user to the data owner) is possible and resistant to the chosen-plaintext attack. In 2006, Ateniese et al. [3] proposed the first unidirectional scheme, which used the basics of cryptography bilinear pairings, and in addition to being safe against chosen-plaintext attack, it had a faster and more efficient structure. The next design created by Canetti and Hohenberger [8] was based on Decisional Bilinear Diffie–Hellman in standard model, which was secure under chosen-ciphertext attack (CCA). Shao and Cao’s scheme [32] was also resistant to collusion, in addition to being secure against the CCA. This was the first scheme of unidirectional PRE proposed schemes with CCA and collusion-resistance features.

Proxy Re-Encryption with keyword search In 2010, Shao et al. [33] introduced a new concept called “proxy re-encryption with keyword search”, in which the user creates a trapdoor using a private key, then by proxy server searches it in the ciphertext without any other information from the proxy server. Since the scheme of [33] suffered from a single keyword restriction, Wang et al. [36] proposed a scheme to address this limitation. Shao et al. [33] and Wang et al. [36] proved their schemes in the random oracle model. In next scheme, Yang et al. [41] proposed a scheme called conjunctive keyword search with designated tester and timing enabled proxy re-encryption function (Re-dtPECK), which gives the user time-dependent encryption scheme that allows the user to access the searching for data and decrypt the encrypted document only at that time period. In their proposed scheme, only a designated server will be able to search query keywords, which makes it safe for keyword guessing attack. Obviously, these time-dependent schemes may not meet all the security needs. In 2017, Yang et al. [42] proposed an unidirectional encryption scheme (i.e. only can convert a delegator ciphertext into the ciphertext for delegatee but not in the opposite direction), suggesting that it is resistant to attacks on quantum computing and computers. Another feature of the scheme was that it was able to search for synonym keywords with the keyword, in addition to searching for a keyword. But their scheme had a drawback that it was not resistant to the integrity contradiction attack. Xu et al. [39] proposed another scheme called time controlled public key encryption with delegated conjunctive keyword search, tc-PEDCKS, which provided the ability to search for conjunctive keywords. This scheme is able to share data of multiple data owners for one data user and provides a certain amount of time to access the data of other data users.

1.3 Organization

The rest of the paper is organized as follows: Sect. 2 is dedicated to the description of Yang et al. searchable encryption scheme. Our proposed integrity contradiction attack is applied on the scheme in Sect. 3. In Sects. 4 and 5, we describe the improved searchable encryption scheme and its security analysis respectively. We also compare the proposed scheme with other related schemes in computational and communication aspects of views in Sect. 7. Finally, the paper concludes in Sect. 8.

Table 1 Notations used in this paper

2 Yang et al.’s Searchable Encryption Scheme

In [42], Yang et al. proposed a new searchable encryption based on lattice which supports semantic keyword search and proxy re-encryption functions. Their searchable encryption scheme includes the following four entities:

• Document Owner (delegator) who wants to store his documents in an encrypted form on the cloud server such that, if necessary, an authorized party (delegatee) should be able to search encrypted documents with the proper keyword.

• Cloud Server responsible for storing encrypted documents and also responsible for searching in the encrypted data to find encrypted files that include the certain keyword.

• Proxy Server responsible for converting data owner secure index $CT_o$ to delegatee secure index $CT_j$.

• Authorized Client (delegatee) who has the permission to receive the data owners encrypted files.

Fig. 1

The Yang et al.’s searchable encryption scheme

It should be noted that the details of scheme’s functions computations do not have any effect on the proposed attack and it is ignored in this paper, the interested reader can refer [42] for more details. Throughout the paper, we use the notations represented in Table 1. As shown in Fig. 1, the Yang et al.’s searchable encryption scheme works as follows:

• 1. New user registration in this phase, the trusted third party TTP considers a new user’s identity and if it is valid, TTP generates public key $pk_i$ and private key $sk_i$ for the user by using $KeyGen(k)\rightarrow (pk_{i}, sk_{i})$.

• 2. Encrypted documents generation in this phase, the document owner, before outsourcing the file to the cloud server, extracts a keyword KW from the file and generates a secure index $CT_o=Enc(pk_o, KW)$ and sends the encrypted file $EF_o=Enc(pk_o, file)$ and $CT_o$ to the cloud server. In this phase, if the data owner (delegator) wants to allow the other (delegatee) to search, it has to generate an encrypted file with the public key of delegatee (j), i.e. $EF_j=Enc(pk_j, file)$, and generate a re-encryption key. By sending that re-encryption key to the proxy server, the proxy server converts $CT_o$ into $CT_j$, which is the secure index of delegatee (j).

• 3. Re-encryption key generation in this phase, if the user o wants to give its search privilege to user j, using $ReKeyGen(sk_{o}, pk_{o},pk_{j} )$, it generates the re-encryption key $rk_{o\rightarrow j}$ which is sent along with $CT_o$ to the proxy server, for secure index transformation. Whenever the proxy server receives $rk_{o\rightarrow j}$ and $CT_o$, it transforms $CT_o$ to $CT_j$ as $ReEnc(rk_{o\rightarrow j}, CT_o)$.

• 4. Secure index transformation in this phase, using $ReEnc(rk_{o\rightarrow j}, CT_o)$, the proxy server transforms $CT_o$ of the user o (delegator) to the $CT_j$ of user j (delegatee).

• 5. Keyword trapdoor generation if an authorized user j wants to find the encrypted documents including keyword KW, generates the trapdoor using his secret key $sk_{j}$ as $Trapdoor({sk_{j}}, {pk_{j}},KW )$ and sends $T_{KW,j}$ to the server.

• 6. Match files retrieving the cloud server upon receipt the keyword trapdoor, searches the encrypted files that include the search keyword or its synonym through following relations:

  $Test(pk_o, CT_o=Enc(pk_{o}, KW), T_{KW,o}=Trapdoor({sk_{o}}, {pk_{o}},KW )){\mathop {=}\limits ^{?}}{1 }$

  $Test(pk_j, CT_j=ReEnc(rk_{o\rightarrow j}, CT_o), T_{KW,j}=Trapdoor({sk_{j}}, {pk_{j}},KW )){\mathop {=}\limits ^{?}}{1 }$

  If at least one of the above relations is satisfied, then the cloud server sends $CT_x$ and $EF_x$ where $x \in \{o,j\}$ to the user.

More details about Yang et al.’s searchable encryption scheme can be found in [42].

3 Security Analysis of Yang et al.’s Searchable Encryption Scheme

In this section, we show that how an adversary A can threaten the security of the Yang et al.’s searchable encryption scheme. Integrity contradiction attack is an attack for which an adversary tries to modify the encrypted files during its transfer without being realized by cloud server, authorized clients or data owner. If the adversary succeeds in changing the encrypted files and the cloud server saves the modified encrypted files, then the data owners or authorized clients will no longer be able to access the original encrypted data that was sent to the server. Given that most of the time, after data transfer, the data owner may clean it from its storage system, the suggested attack is very serious and it is necessary to counter searchable encryption schemes against it. On the other hand, changing the encrypted files during transfer to the data owners or authorized clients from the cloud server causes the data owner or client to receive the modified encrypted file, and this may result in irreparable damage due to incorrect information that reveals from the modified encrypted file.

To apply the integrity contradiction attack in the Yang et al.’s searchable encryption scheme, the adversary can do either of the following three scenarios as shown in Fig. 2:

Fig. 2

The proposed integrity contradiction attack against the Yang et al.’s searchable encryption scheme

Attack Scenario 1: This scenario runs as below:

• 1. A data owner:

  • extracts the keyword $KW\in \{0,1\}^{*}$;

  • generates the secure index $CT_o=Enc(pk_o, KW)$;

  • generates the encrypted document $EF_o=Enc(pk_o, file)$;

  • and sends $CT_o$ and $EF_o$ to the cloud server.

• 2. The adversary:

  • stops $CT_o$ and $EF_o$;

  • changes $CT_o$ to an arbitrary value, e.g. $CT_o{''}$, and also the encrypted file $EF_o$ to an arbitrary file $EF_o{''}$ ;

  • and sends $CT_o{''}$ and $EF_o{''}$ to the cloud server.

• 3. The cloud server receives $CT_o{''}$ and $EF_o{''}$ and stores them without any check which indicates that these files have changed during the transfer.

  Therefore, the modified secure index and modified encrypted file may not output correctly in the keyword search phase, and thus the data owners or allowed clients by searching the keyword, along with the trapdoor, will not access the correct file. The success probability of this attack is one while its complexity is only one run of the scheme.

Attack Scenario 2: Given that the data owner (delegator) wants to allow the other (delegatee) to search, the second scenario to attack Yang et al.’s searchable encryption scheme runs as below:

• 1. The data owner:

  • generates the encrypted document $EF_j=Enc(pk_j, file)$;

  • sends $EF_j$ to the cloud server;

  • generates a re-encryption key $rk_{o\rightarrow j}$ through $ReKeyGen(sk_{o}, pk_{o},pk_{j} )$;

  • and sends $CT_o$ and $rk_{o\rightarrow j}$ to the proxy server in the insecure channel.

• 2. The adversary:

  • stops $CT_o$ and $rk_{o\rightarrow j}$;

  • changes $CT_o$ and $rk_{o\rightarrow j}$ to an arbitrary value, e.g. $CT_o{''}$ and $rk{''}_{o\rightarrow j}$ respectively;

  • and sends $CT_o{''}$ and $rk{''}_{o\rightarrow j}$ to the proxy server.

• 3. The proxy server receives $CT_o{''}$ and $rk{''}_{o\rightarrow j}$ and without any checking transforms $CT_o{''}$ to $CT_j{''}$ using $rk{''}_{o\rightarrow j}$, which is not equal to the intended value of $CT_j$.

  So, the authorized user j after above attack, will never access the correct file. The success probability of above attack is one while its complexity is only one run of the scheme.

Attack Scenario 3: This scenario, given the encrypted files are correctly and without any change stored on the cloud server, runs as below:

• 1. The authorized client i.e. the user j requests cloud server for encrypted file which includes the KW via the trapdoor $T_{KW,j}$;

• 2. After the successful keyword search, the cloud server sends the secure index $CT_j$ along with the encrypted document $EF_j$ for it.

• 3. The adversary:

  • stops $CT_j$ and $EF_j$;

  • changes $CT_j$ to an arbitrary value $CT_j{''}$ and also $EF_j$ to an arbitrary $EF_j{''}$ ;

  • and sends $CT_j{''}$ and $EF_j{''}$ to the delegatee (j).

• 4. Upon receipt $CT_j{''}$ and $EF_j{''}$, the authorized client j:

  • by using its secret key $sk_j$ and through decryption of $CT_j{''}$ and $EF_j{''}$ finds a keyword and a file respectively which are different from original keyword and original file.

  So, according to the above attack scenario, allowed client will not access the correct file. The success probability of above attack is one while its complexity is only one run of the scheme.

Yang et al.’s searchable encryption scheme’s vulnerability to above attack is due to the fact that the integrity of the messages exchanged in the protocol is not checked by the recipients of the messages.

It is worth noting that due to the fact that the communication channel is not secure, it is possible for everyone to eavesdrop. So, the attacker can receive the sent message and even change it and send it again. In fact, this attack is practically possible because there is no integrity check function in the transferred messages between protocol parties for example between the document owner and the cloud server, so that the cloud server does not realize that the message has been changed. Hence, there is a possibility of transferred messages change or manipulation. For example, suppose the first message from the sender (owner of the file) is sent to the server and reaches the server in a matter of seconds without manipulation or interception, and the server saved it. Now suppose that in sending a message from the file owner to the server in one of the intermediate nodes, the attacker saves the message and then changes it (although he/she does not know the contents of the message due to encryption), for example, a few bits are converted from 0 to 1 or 1 to 0 and sends the changed message again. The message eventually reaches the cloud server, but it may take more the time to receive it. Due to the nature of computer networks and the momentary change in network traffic, the cloud server assumes this time increase is due to high network traffic and stores it as a healthy message on the cloud server. So this attack is practically feasible.

4 Improved Yang et al.’s Searchable Encryption

Given that the Yang et al.’s searchable encryption scheme does not guarantee the integrity of the stored data, in the previous section we proposed several efficient attacks against it. In this section, we improve this searchable encryption scheme which is resistant against attacks mentioned in Sect. 3 and the other known active and passive attacks. The attack described above is due to the weakness of the Yang et al.’s searchable encryption scheme, which in it neither the server nor the data owner nor the client checks the integrity of its received encrypted files. If such mechanism can be implemented, which in it before the encrypted file is stored on the cloud server and also upon the data owner or allowed clients receive the encrypted file and before using it, they make sure about the integrity preservation of the encrypted file, then the searchable encryption scheme resists against integrity contradiction attack. The basic idea of our improving is using digital signatures of the secure index and also digital signatures of encrypted documents which along with the secure index and the encrypted document are sent to all desired exchange paths of improved searchable encryption scheme. We used the RSA encryption algorithm, RSA digital signature algorithm, and sha256 hash algorithm in order to encrypt, sign and hash the messages respectively.

The improved Yang et al.’s searchable encryption, as it is shown in Fig. 3, runs as below:

Fig. 3

The proposed searchable encryption scheme

• New user registration in this phase, TTP considers a new user’s identity and if it is valid, the TTP generates public key $pk_i$ and private key $sk_i$ for the user by using $KeyGen(k)\rightarrow (pk_{i}, sk_{i})$.

• Encrypted documents generation in this phase, the data owner, before outsourcing the file to the cloud server generates a random number $n_1$ and signs it with its secret key as $Sign(sk_o,n_1)$ and then encrypts it with public key of cloud server as $Enc(pk_s,Sign(sk_o,n_1))$ and sends it to the cloud server. Cloud server once receives the message decrypts the message and then receives $n_1$ by verifying the signature. If the cloud server is ready to accept files to outscoring, generates another random number $n_2$ and signs $n_1\Vert n_2$ with its secret key as $Sign(sk_o,n_1\Vert n_2)$ and then encrypts it with public key of delegator as $Enc(pk_o,Sign(sk_o,n_1\Vert n_2))$ and sends it to the delegator. Delegator as soon as receives the message, decrypts it and verifies signature and receives $n_1$ and $n_2$, if the received $n_1$ equals with sent $n_1$, then it:

  • extracts a keyword KW from the file;

  • generates a secure index $CT_o$ as $Enc(pk_{o}, KW)$;

  • generates an encrypted document $EF_o$ as $Enc(pk_o, file)$;

  • signs $h(CT_o)\Vert h(EF_o)\Vert n_1\Vert n_2$ by using its secret key $sk_{o}$ as $Sign(sk_{o}, h(CT_o)\Vert h(EF_o)\Vert n_1\Vert n_2)$;

  • and sends $CT_o$, $EF_o$ and $Sign(sk_{o}, h(CT_o)\Vert h(EF_o)\Vert n_1\Vert n_2)$ to the cloud server.

• Encrypted documents integrity check in this phase, upon receipt $CT_o$, $EF_o$ and $Sign(sk_{o}, h(CT_o)\Vert h(EF_o)\Vert n_1\Vert n_2)$, the cloud server:

  • verifies the signature $Sign(sk_{o}, h(CT_o)\Vert h(EF_o)\Vert n_1\Vert n_2)$ by using the public key of owner $pk_o$ through $DeSign(pk_{o}, Sign(sk_{o}, h(CT_o)\Vert h(EF_o)\Vert n_1\Vert n_2))$ and receives $h'(CT_o)\Vert h'(EF_o)\Vert n'_1\Vert n'_2$;

  • checks whether $h'(CT_o){\mathop {=}\limits ^{?}}h(CT_o)$, $h'(EF_o){\mathop {=}\limits ^{?}}h(EF_o)$, $n'_1{\mathop {=}\limits ^{?}}n_1$ and $n'_2{\mathop {=}\limits ^{?}}n_2$. If one of them does not hold, it does not store $CT_o$ and sends an “Error” message to the data owner. If it is ok, stores $CT_o$ and $EF_o$.

• Re-encryption key generation at this phase, if the data owner (delegator) wants to allow the other (delegatee)j to search, it has to:

  • generate a random number $n_3$;

  • generate an encrypted document $EF_j$ as $Enc(pk_j, file)$;

  • sign $h(EF_j)\Vert n_3$ by using its secret key $sk_{o}$ as $Sign(sk_{o}, h(EF_j)\Vert n_3)$;

  • send $EF_j$, $n_3$ along with $Sign(sk_{o}, h(EF_j)\Vert n_3)$ to the cloud server;

  • generate a re-encryption key $rk_{o\rightarrow j}$ as $ReKeyGen(sk_{o}, pk_{o},pk_{j} )$;

  • generate an encryption of re-encryption key $rk_{o\rightarrow j}$ with the public key of proxy server as $ER_{o\rightarrow j}=Enc(pk_{p},rk_{o\rightarrow j})$;

  • sign $h(ER_{o\rightarrow j})\Vert h(CT_o)\Vert n_3$ as $Sign(sk_{o},h(ER_{o\rightarrow j})\Vert h(CT_o)\Vert n_3)$;

  • and send $ER_{o\rightarrow j}$, $CT_o$, $n_3$ and $Sign(sk_{o},h(ER_{o\rightarrow j})\Vert h(CT_o)\Vert n_3)$ to the proxy server.

• Secure index transformation the proxy server when receives the messages:

  • verifies $Sign(sk_{o},h(ER_{o\rightarrow j})\Vert h(CT_o)\Vert n_3)$ with the public key of document owner $pk_o$ through $DeSign(pk_{o}, Sign(sk_{o},h(ER_{o\rightarrow j})\Vert h(CT_o)\Vert n_3) )$ and receives $h'(ER_{o\rightarrow j})\Vert h'(CT_o)\Vert n'_3$;

  • checks whether $h(ER_{o\rightarrow j}){\mathop {=}\limits ^{?}}h'(ER_{o\rightarrow j})$, $h(CT_o){\mathop {=}\limits ^{?}}h'(CT_o)$ and $n_3{\mathop {=}\limits ^{?}}n'_3$. If one of them does not hold, it does not decrypt $ER_{o\rightarrow j}$ and sends an “Error” message to the data owner, otherwise:

    $*$:

    decrypts $ER_{o\rightarrow j}$ with its secret key as $Dec(sk_{p},ER_{o\rightarrow j})= Dec(sk_{p},Enc(pk_{p},rk_{o\rightarrow j}))$ and obtains $rk_{o\rightarrow j}$;

    $*$:

    by using the re-encryption key $rk_{o\rightarrow j}$ transforms $CT_o$ to $CT_j$.

    $*$:

    signs $h(CT_j)\Vert n_3$ as $Sign(sk_{p}, h(CT_j)\Vert n_3)$;

    $*$:

    and sends $CT_j$, $n_3$ and $Sign(sk_{p}, h(CT_j)\Vert n_3)$ to the cloud server.

• Keyword trapdoor generation if an authorized user j wants to find the encrypted documents including keyword KW, produces a random number $n_4$, generates the trapdoor $T_{KW,j}$ using his secret key through $Trapdoor({sk_{j}}, {pk_{j}},KW )$ and sends $T_{KW,j}$ along with $n_4$ to the cloud server.

• Match files retrieving upon receipt the keyword trapdoor, the cloud server:

  • searches the encrypted files that include the search keyword or its synonym through following relations:

  • if $Test(pk_x, CT_x, T_{KW,x})\rightarrow {0}$, where $x\in \{o,j\}$ responds “cannot find the keyword in database”;

  • if $Test(pk_x, CT_x, T_{KW,x})\rightarrow {1}$, where $x\in \{o,j\}$ finds related $CT_x$ and $EF_x$ and signs $h(CT_x)\Vert h(EF_x)\Vert n_4$ with its secret key as $Sign(sk_{s}, h(CT_x)\Vert h(EF_x)\Vert n_4)$ and sends $CT_x$, $EF_x$ and $Sign(sk_{s}, h(CT_x)\Vert h(EF_x)\Vert n_4)$ to the client.

• Check the integrity of received encrypted files the authorized client, when receives $CT_j$, $EF_j$ and $Sign(sk_{s}, h(CT_j)\Vert h(EF_j)\Vert n_4)$:

  • verifies the signature $Sign(sk_{s}, h(CT_j)\Vert h(EF_j)\Vert n_4)$ by using the public key of the cloud server $pk_s$ as $DeSign(pk_s,Sign(sk_{s}, h(CT_j)\Vert h(EF_j)\Vert n_4))$ and receives $h'(CT_j)\Vert h'(EF_j)\Vert n'_4$;

  • checks whether $h'(CT_j){\mathop {=}\limits ^{?}}h(CT_j)$, $h'(EF_j){\mathop {=}\limits ^{?}}h(EF_j)$ and $n'_4{\mathop {=}\limits ^{?}}n_4$.

    $*$:

    If one of them does not hold, does not use the encrypted files and sends another request to the cloud server;

    $*$:

    If it is ok, stores encrypted file $EF_j$ and decrypts it by using its secret key and consequently uses it.

Remark 1

In the proposed scheme, hash of messages is signed instead of signing the message itself, in order to increase the speed of sign operation.

5 Security Analysis of the Improved Searchable Encryption Scheme

In this section, we first informally and then formally show that the improved searchable encryption scheme can provide complete security against different attacks through the Scyther tool [11].

5.1 Informal Analysis

Since the improved searchable encryption scheme is based on the Yang et al.’s scheme, its security against other attacks is the same as the Yang et al.’s scheme security analysis which is presented in [42] and for the sake of brevity we do not explain them here. It is enough to show that the improved searchable encryption scheme resists against the attack represented in this paper.

5.1.1 Resistance to Integrity Contradiction Attack

In the improved searchable encryption scheme, wherever a message was transported, along with that, the signed message, would also be transmitted. Therefore, the recipient of the message could also ensure that the sender of the message is the one claiming and the message during the transfer, has not changed, which is interpreted as data integrity preservation. Hence, the improved searchable encryption scheme can resist against the integrity contradiction attack presented in this paper.

5.1.2 Resistance to Replay Attack

To resist against replay attacks in the proposed scheme, the protocol parties eliminate the possibility of reusing the messages by generating random numbers and using them in signed messages. Therefore, the proposed protocol is safe against a variety of replay attacks.

5.1.3 Resistance to Impersonation Attack

Since in the proposed scheme, each response to a request is signed with the respondent’s private key and also, inside the signed messages, there is a random number sent by the initiator of the communication, so it is not possible for the adversary to impersonate a legitimate party. Therefore, the resistance of the proposed scheme to the all kinds of impersonation attacks is due to the signing of messages that have been randomized by the parties by generating random numbers.

5.2 Formal Analysis Based on Scyther Tool

Today, there are various tools for formal security analysis such as TAMARIN [28], AVISPA [2], Proverif [5], CryptoVerif [4] and Scyther [11]. Here, we consider the security of our proposed scheme in term of security using the Scyther tool. The Scyther is a tool to check the security properties of a protocol based on security claims. The Scyther tool takes the description of the protocol in security protocol description language (SPDL) structure as an input, and can define security claims for each role in the protocol, and check the correctness of claims output. If the claim is not correct, its attack structure is shown in graphical form. We implemented the proposed scheme in SPDL which its code is presented in Appendix A. The results of the automatic security verification of the proposed scheme by the Scyther tool as shown in Fig. 4 are verified OK.

Fig. 4

The security verification results of the improved searchable encryption scheme in the Scyther tool

Table 2 Security properties comparison

6 Security Comparison

In this section, we will briefly compare the security features of our proposed scheme with schemes [27, 37, 39, 41, 42] in Table 2. The notations used in Table 2 are as follows:

• KB (Keyword-based) The designed structures based on keywords are important and their functional capabilities are easy to find all relevant documents from the storing server by using the keyword search.

• KGA (Keyword Guessing Attack) In this attack, the external or internal adversary intends to find the exact amount of keywords by collecting information and eavesdropping on the insecure channels in the searchable encryption schemes.

• FIA (File Injection Attack) This attack was presented by Zhang et al. [45] aiming to discover the keywords associated with the files. In this attack, the attacker injects a certain number of files, each file containing at least the half of the total number of keywords, to the server. Then it tries to guess the keywords by getting the trapdoors from the data users, accessing the Test algorithms, and generating the ciphertext. More precisely, the attacker runs the attack as the following. Assume we have the keyword set KW, each of which is numbered with log|KW| bits from 0 to $|KW|-1$ (where |KW| is the power of 2). The attacker generates a set of $\lceil log|KW| \rceil$ files F for injecting to the server. Each file has $|KW|-1$ bits and contains exactly the half of the keyword set KW. The file i contains the keywords whose the ith most-significant bit is equal to 1. We consider a search results value $R = \{F_1, F_2, \ldots \}_2$, which is a binary number for the returned results from the storage server side. This attack is also called a binary-search attack.

• NI (Non Interactivity) It refers to the fact that two entities of the data user and the data owner do not need to interact with each other and interact with the entities involved in the protocol to generate their own keys.

• ICA (Integrity Contradiction Attack) In the improved searchable encryption scheme, wherever a message was transported, the signed message would also be transmitted along with that. Therefore, the recipient of the message could also ensure that the sender of the message is the one claiming and the message has not changed during the transfer which is interpreted as data integrity preservation. Hence, the improved searchable encryption scheme can resist against integrity contradiction attack.

Fig. 5

The time required for Encryption algorithm in our proposed searchable encryption scheme compared to other related schemes

Fig. 6

The time required for Trapdoor algorithm in our proposed searchable encryption scheme compared to other related schemes

Fig. 7

The time required for Test algorithm in our proposed searchable encryption scheme compared to other related schemes

7 Comparisons

There are many algorithms for doing digital signature, and it is not necessary to detail the implementation in most cases unless a change is made in the process of digital signature algorithm, which leads to propose of a new digital signature algorithm. In our proposed searchable encryption scheme, it does not matter which digital signature algorithm is used. So, we implemented our proposed searchable encryption scheme using RSA encryption, RSA digital signature and sha256 hash algorithms. Implementation results of our proposed searchable encryption scheme compared to other related schemes are shown graphically in Figs. 5, 6,  7 and numerically in Tables 3, 4 and  5.

Table 3 Computational cost comparison

Table 4 Times of operations used in searchable encryption schemes

Table 5 Communication cost comparison where m and l for the schemes of [37, 39, 41], show the size of the keyword set and the size of the encrypted keyword set respectively

The system used for implementation has Intel(R) Core(TM) i5-4210u CPU@1.70GHz 2.40GHz CPU, 6 GB RAM and 1TB Hard. Table 3 shows the computational times of the proposed scheme compared to other schemes. In this table, the value of m (keyword set size) and l (encrypted keyword set size) are considered equal to 5 and 10 for [37, 39] and [41] schemes, respectively. Table 4 shows the types of times used in a variety of searchable encryption schemes where $T_p$, $T_{mtp}$, $T_{sm}$, $T_{exp}$, $T_{mul}$, $T_e$, $T_d$, and $T_h$ denote the required time for doing bilinear paring, doing map to point hash function, scalar multiplication operation, the exponentiation operation, the multiplication operation, the encryption operation, the decryption operation, and the typical hash operation respectively. Table 5 compares the proposed scheme with the related schemes in terms of communication costs. In this table, the communication cost is calculated based on the number of keywords sent in the communication channel. The graphical representation of our proposed scheme compared to other related schemes are shown in Figs. 5, 6 and 7 respectively.

Figure 5 shows that the Wu et al.’s scheme [37], the Yang et al.’s scheme [42] and the proposed scheme, require the least amount of time for their encryption algorithm, respectively. Figure 6 shows that the time required to generate a trapdoor is the same in both the Yang et al.’s scheme [42] and the proposed scheme, which is the lowest possible value compared to other designs. Figure 7 also shows that the proposed scheme and the Yang  et al.’s scheme [42] require the least possible time for the test algorithm, respectively. In general, it can be said that although the total time of the improved searchable encryption scheme is slightly longer than its predecessor, but in contrast to it, it has been able to provide more security.

8 Conclusions

Searchable encryption schemes should have the capability to maintain an exchanged message’s integrity, like any security algorithm or protocol. It means the message recipient can detect if the messages were changed during the transfer. In this paper, we have shown that the Yang et al.’s searchable encryption scheme does not provide the integrity of encrypted files during transfer over an insecure channel between scheme parties. More precisely, we have presented an integrity contradiction attack against this protocol with the success probability of one and the complexity of only one run of the scheme. Then we have proposed a new scheme by using digital signatures and have shown that the improved scheme resists to the attack presented in this paper and the other known active and passive attacks. This paper and the similar researches show that more work is needed in terms of the security of searchable encryption schemes.

SPDL Implementation of the Proposed Scheme