# Public Key Encryption with Authorized Equality Test on Outsourced Ciphertexts for Cloud-Assisted IoT in Dual Server Model

Authors: Meng Zhao; Yong Ding; Shijie Tang; Hai Liang; Huiyong Wang
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

In cloud computing, the outsourced data face many privacy and security threats. To allow the cloud server to perform comparison, search, and classification on outsourced ciphertexts while simultaneously providing privacy guarantee, the encryption method that supports the ciphertext equality test is considered as a promising way. Users are able to authorize the cloud server to conduct the ciphertext equality test, so that two ciphertexts can be determined whether they encrypt the same message without being decrypted. In this process, users do not need to retrieve, decrypt, and then perform comparison on data; thus, the computing and communication efficiency can be greatly improved, and the privacy of user data can be guaranteed at the cloud server side. However, existing encryption schemes supporting authorized ciphertext equality test in the single server model cannot resist the keyword guessing attacks, and the solutions in the dual server model do not provide simultaneous authorization on two servers. To address these issues, this paper proposes a public key encryption scheme supporting authorized equality test on ciphertexts in the dual server model (PKE-AUT), where the primary server and secondary server must get the authorization from users before performing a sequential equality test on ciphertexts. Security and performance analysis demonstrate that the proposed PKE-AUT scheme not only guarantees the privacy of user data and authorization but also is practical in cloud-assisted IoT-related applications.


---

## Body

## 1. Introduction

In recent years, the cloud computing and Internet of Things (IoT) technologies have developed rapidly and become widely used. By leveraging the powerful computing capability and massive storage resources of cloud servers, the collected IoT data can be outsourced to cloud servers to save local storage and computing resources [1]. However, to guarantee the privacy of the user’s sensitive information, the data should be encrypted before being outsourced, so that only the data in ciphertext format would be stored at the cloud server [2, 3]. Data encrypted with classic cryptographic schemes does not support equality test, keyword search, calculation, and other operations on ciphertexts, so that users need to download their outsourced data to the local and then complete the corresponding operations after decryption. Thus, this process would bring huge computing and communication burdens to users, while failing to reflect the advantages of cloud computing services [4, 5].To enable equality test on outsourced ciphertexts, many public key encryption schemes [6–8] and identity-based encryption schemes [9–12] have been proposed in the single server model. After the cloud server received the authorization from the user, it is able to perform the equality test on outsourced ciphertexts or some related operations such as encrypted data classification [13, 14] based on the equality test, without decryption. However, since these solutions were proposed in the single cloud server model, the authorized cloud server would be able to launch keyword guessing attacks on outsourced ciphertexts to infer user data [4, 15], which causes damage to the privacy of users. Specifically, the cloud server is able to generate ciphertexts on many messages using the public keys of some users. Note that the cloud server should hold the authentication from these users. In this way, the cloud server can compare the generated ciphertexts with the stored ones, which would leak the message information if some pairs of ciphertexts are matched.To resist the above-mentioned keyword guessing attacks faced by outsourced ciphertexts under the single server model, Wu et al. [15] proposed an identity-based encryption scheme under the dual server model for data classification in the mobile health social network. With their scheme, the user can authorize the primary server to generate relevant intermediate parameters, and the secondary server can further determine whether the two ciphertexts encrypted the same plaintext according to these intermediate parameters. These two servers would not collude to launch the attacks on outsourced user data. During the execution of their solution, the secondary server without obtaining the legal authorization of the user can perform the equality test on ciphertexts from the intermediate results generated by the primary server.


### 1.1. Our Contributions

This paper proposes a public key encryption scheme supporting the authorized equality test on outsourced ciphertexts (PKE-AUT) in the dual server mode. Similar to [15], the primary server and secondary server would not collude for compromising the confidentiality of outsourced data. Without authorization from the data user, both servers are unable to perform any operation on outsourced ciphertexts. After obtaining the same authorization from the data user, the primary server and secondary server sequentially perform the equality test on outsourced ciphertexts; that is, the authorized primary server produces and sends the intermediate parameters to the secondary server, then the authorized secondary server can complete the equality test procedure.In the proposed PKE-AUT scheme, the authorizations generated for two servers are the same. The authorization is encrypted by the data user, so that only the primary server and secondary server are able to decrypt the authorization with their privacy keys, respectively; in this way, the computing costs for producing authorization can be reduced and the privacy of authentication can be protected during transmission. Security analysis shows that the proposed PKE-AUT scheme can guarantee the privacy of outsourced ciphertexts in two phases before and after the primary and secondary servers are authorized. Efficiency analysis demonstrates that the proposed PKE-AUT scheme is suitable for IoT-related applications.


### 1.2. Related Works

Many studies have been conducted on the authorized equality test on ciphertexts in different application scenarios. Yang et al. [6] introduced the first probabilistic public key encryption scheme with equality test on ciphertexts (PKEET), where anyone without authorization was able to check whether the ciphertexts generated with different public keys encrypt the same data. Thus, when deployed in cloud computing, their scheme allows an unauthorized cloud server to compare the outsourced ciphertexts of different users.Since Yang et al.’s work [6], many encryption schemes supporting the authorized equality test on ciphertexts in the single server model have been proposed [7, 16], such that the cloud server can only compare the ciphertexts after being authorized. In [17], Tang designed an all-or-nothing encryption scheme, where the cloud can test the ciphertexts only after being independently authorized by their owners. In [18], Lee et al. analyzed the security of Huang et al.’s construction [19] and presented a security-enhanced scheme. An identity-based encryption scheme with equality test on ciphertexts (IBEET) was constructed in [20], which combines the PKEET and identity-based encryption technologies. Lee et al. [21] studied the semigeneric constructions of PKEET and IBEET and proved their security under the Computational Diffie-Hellman (CDH) and Computational Bilinear Diffie-Hellman (CBDH) assumptions, respectively.The mechanism of the equality test on ciphertexts has been used in equi-join in relational databases and secure deduplication of encrypted data. Pang and Ding [22] investigated equi-join across encrypted tables in the database in private key setting, where for an outsourced database, the user is able to control which data tables the cloud server can perform equi-join according to some data fields by issuing authorization. Then, controlled equi-join for encrypted databases in the public key setting was considered in [23]. Also, the technology of the equality test on ciphertexts was employed by Cui et al. [24] and Yan et al. [25] in achieving secure deduplication on outsourced data in clouds, without sacrificing data privacy.Postquantum encryption schemes supporting the equality test on ciphertexts have also received attention from researchers. Le et al. [26] proposed the first lattice-based signcryption scheme with equality test on ciphertexts in the standard model, which was proven secure against insider attacks. Susilo et al. [27] designed an efficient postquantum IBEET scheme with smaller ciphertext and public key size, which enjoys CCA2 security. Nguyen et al. [10] presented a lattice-based IBEET scheme in the standard model, which supports flexible authorization for equality test so that the user is able to control the comparison of their ciphertexts with others.


### 1.3. Paper Organization

The remainder of this paper is organized as follows. Section2 introduces the preliminaries for the proposed PKE-AUT scheme. Section 3 describes the system model and security requirements for the PKE-AUT system in the dual server model. A description of our PKE-AUT scheme is presented in Section 4, followed by the security and performance analysis in Section 5. Section 6 concludes the paper.


## 1.1. Our Contributions

This paper proposes a public key encryption scheme supporting the authorized equality test on outsourced ciphertexts (PKE-AUT) in the dual server mode. Similar to [15], the primary server and secondary server would not collude for compromising the confidentiality of outsourced data. Without authorization from the data user, both servers are unable to perform any operation on outsourced ciphertexts. After obtaining the same authorization from the data user, the primary server and secondary server sequentially perform the equality test on outsourced ciphertexts; that is, the authorized primary server produces and sends the intermediate parameters to the secondary server, then the authorized secondary server can complete the equality test procedure.In the proposed PKE-AUT scheme, the authorizations generated for two servers are the same. The authorization is encrypted by the data user, so that only the primary server and secondary server are able to decrypt the authorization with their privacy keys, respectively; in this way, the computing costs for producing authorization can be reduced and the privacy of authentication can be protected during transmission. Security analysis shows that the proposed PKE-AUT scheme can guarantee the privacy of outsourced ciphertexts in two phases before and after the primary and secondary servers are authorized. Efficiency analysis demonstrates that the proposed PKE-AUT scheme is suitable for IoT-related applications.


## 1.2. Related Works

Many studies have been conducted on the authorized equality test on ciphertexts in different application scenarios. Yang et al. [6] introduced the first probabilistic public key encryption scheme with equality test on ciphertexts (PKEET), where anyone without authorization was able to check whether the ciphertexts generated with different public keys encrypt the same data. Thus, when deployed in cloud computing, their scheme allows an unauthorized cloud server to compare the outsourced ciphertexts of different users.Since Yang et al.’s work [6], many encryption schemes supporting the authorized equality test on ciphertexts in the single server model have been proposed [7, 16], such that the cloud server can only compare the ciphertexts after being authorized. In [17], Tang designed an all-or-nothing encryption scheme, where the cloud can test the ciphertexts only after being independently authorized by their owners. In [18], Lee et al. analyzed the security of Huang et al.’s construction [19] and presented a security-enhanced scheme. An identity-based encryption scheme with equality test on ciphertexts (IBEET) was constructed in [20], which combines the PKEET and identity-based encryption technologies. Lee et al. [21] studied the semigeneric constructions of PKEET and IBEET and proved their security under the Computational Diffie-Hellman (CDH) and Computational Bilinear Diffie-Hellman (CBDH) assumptions, respectively.The mechanism of the equality test on ciphertexts has been used in equi-join in relational databases and secure deduplication of encrypted data. Pang and Ding [22] investigated equi-join across encrypted tables in the database in private key setting, where for an outsourced database, the user is able to control which data tables the cloud server can perform equi-join according to some data fields by issuing authorization. Then, controlled equi-join for encrypted databases in the public key setting was considered in [23]. Also, the technology of the equality test on ciphertexts was employed by Cui et al. [24] and Yan et al. [25] in achieving secure deduplication on outsourced data in clouds, without sacrificing data privacy.Postquantum encryption schemes supporting the equality test on ciphertexts have also received attention from researchers. Le et al. [26] proposed the first lattice-based signcryption scheme with equality test on ciphertexts in the standard model, which was proven secure against insider attacks. Susilo et al. [27] designed an efficient postquantum IBEET scheme with smaller ciphertext and public key size, which enjoys CCA2 security. Nguyen et al. [10] presented a lattice-based IBEET scheme in the standard model, which supports flexible authorization for equality test so that the user is able to control the comparison of their ciphertexts with others.


## 1.3. Paper Organization

The remainder of this paper is organized as follows. Section2 introduces the preliminaries for the proposed PKE-AUT scheme. Section 3 describes the system model and security requirements for the PKE-AUT system in the dual server model. A description of our PKE-AUT scheme is presented in Section 4, followed by the security and performance analysis in Section 5. Section 6 concludes the paper.


## 2. Preliminaries

This section reviews the bilinear groups, the Computational Diffie-Hellman (CDH) problem and the Computational Bilinear Diffie-Hellman (CBDH) problem.


### 2.1. Bilinear Groups

LetG=g and GT be two cyclic groups of prime order q. The map e^:G×G⟶GT is a bilinear pairing if it satisfies the following conditions:
(i)
Bilinearity: for any g1,g2∈RG and a,b∈RZq∗, we have
(1)e^g1a,g2b=e^g1,g2ab.(ii)
Nondegeneracy: there exists g1,g2∈G such that
(2)e^g1,g2≠1.(iii)
Computability: for g1,g2∈RG, there is an efficient algorithm to compute e^g1,g2


### 2.2. Complexity Assumptions

The security of our construction relies on the following two assumptions.CDH assumption. Let G=g be a cyclic group of prime order q. Given a tuple g,ga,gb where a,b∈RZq∗, there is no probabilistic ploynomial-time algorithm A to compute gab with nonnegligible probability.CBDH assumption. Let G=g and GT be two cyclic groups of prime order q and satisfy bilinear pairing e^:G×G⟶GT. Given a tuple g,ga,gb,gc where a,b,c∈RZq∗, there is no probabilistic ploynomial-time algorithm A to compute e^g,gabc with nonnegligible probability.


## 2.1. Bilinear Groups

LetG=g and GT be two cyclic groups of prime order q. The map e^:G×G⟶GT is a bilinear pairing if it satisfies the following conditions:
(i)
Bilinearity: for any g1,g2∈RG and a,b∈RZq∗, we have
(1)e^g1a,g2b=e^g1,g2ab.(ii)
Nondegeneracy: there exists g1,g2∈G such that
(2)e^g1,g2≠1.(iii)
Computability: for g1,g2∈RG, there is an efficient algorithm to compute e^g1,g2


## 2.2. Complexity Assumptions

The security of our construction relies on the following two assumptions.CDH assumption. Let G=g be a cyclic group of prime order q. Given a tuple g,ga,gb where a,b∈RZq∗, there is no probabilistic ploynomial-time algorithm A to compute gab with nonnegligible probability.CBDH assumption. Let G=g and GT be two cyclic groups of prime order q and satisfy bilinear pairing e^:G×G⟶GT. Given a tuple g,ga,gb,gc where a,b,c∈RZq∗, there is no probabilistic ploynomial-time algorithm A to compute e^g,gabc with nonnegligible probability.


## 3. System Model and Security Requirements

### 3.1. System Model

As shown in Figure1, the PKE-AUT system under the dual server model consists of four types of entities, namely, trusted authority, primary server, secondary server, and users. The trusted authority is responsible for initializing the system, picking the security parameter, and producing public system parameters. Both data sender and data receiver are system users. Before being uploaded to the primary server, the data is encrypted using the public keys of the data receiver and two servers, so that only the data in the ciphertext format is outsourced. The data receiver is able to retrieve the data from the primary server for decryption with his private key and issue the same authorization to the primary and secondary servers, so that the two servers can jointly perform equality test on ciphertexts.Figure 1
System model of PKE-AUT.In the PKE-AUT system, the primary server and secondary server are assumed not to collude. All outsourced data are stored at the primary server in ciphertext format to protect their privacy. After being authorized, the primary server can perform the partial equality test procedure on outsourced ciphertexts, where the intermediate results would be produced and sent to the secondary server for processing. The second server further determines whether the ciphertexts encrypt the same data according to the intermediate results and gives the final equality test result to the data user. This equality test procedure with two phases can be executed in multiuser setting; that is, the primary and secondary servers can perform the equality test on ciphertexts of multiple users according to their authorization.


### 3.2. Security Requirements

In the PKE-AUT system under the dual server model, the primary server and the secondary server are independent and would not collude to attack the outsourced data. A secure PKE-AUT system has to satisfy the following requirements.(i)
Data privacy against the primary server: user data are stored at the primary server. Although the primary server is authorized to perform the equality test on ciphertexts, it cannot obtain the plaintexts from ciphertexts.(ii)
Data privacy against the secondary server: after obtaining the authorization for conducting equality test from users, the secondary server cannot deduce the plaintext information of outsourced data from the received intermediate results.(iii)
Privacy protection on authentication: the authentication generated by the data user can only be decrypted by the primary server and secondary server.


### 3.3. System Framework

A PKE-AUT scheme is composed of nine procedures, namely, the system setup, user key generation, server key generation, data encryption, data decryption, authentication generation, authentication recovery, primary server equality test, and secondary server equality test.System setup: on input of the security parameter 1λ, which is carried out by the trusted authority, outputs the system public parameters Para. We denote Para⟵Setup1λ.User key generation: on input of the system public parameters Para, the user key generation procedure, which is carried out by each user Ui, generates a pair of public key pki and secret key ski. We denote pki,ski⟵UKeyGenPara.Server key generation: on input of the system public parameters Para, the server key generation procedure, which is carried out by each server Sj including the primary server S1 and secondary server S2, generates a pair of public key spkj and secret key sskj. We denote spkj,sskj⟵SKeyGenPara.Data encryption: on input of the public keys pki,spk1,spk2of data receiver Ui, primary server S1 and secondary server S2, and a message m, the data encryption procedure, which is run by the data sender, generates a ciphertext C and outsources it to the primary server S1. We denote C⟵Encryptpki,spk1,spk2,m.Data decryption: on input of the secret key ski of user Ui, the public keys spk1,spk2 of primary server S1 and secondary server S2, and a ciphertext C, the data decryption procedure, which is run by the data receiver, outputs a plaintext m or ⊥ that signifies an error in decryption. We denote m/⊥⟵Decryptski,spk1,spk2,C.Authentication generation: on input of the secret key ski of user Ui and the public keys spk1,spk2 of primary server S1 and secondary server S2, the authentication generation procedure, which is run by user Ui, generates a ciphertext authentication Zi for two servers. Note that two servers have the same ciphertext authentication Zi. We denote Zi⟵AuthGenski,spk1,spk2.Authentication recovery: on input of a ciphertext authentication Zi, the secret key ssk1 of primary server S1 (resp., ssk2 of secondary server S2), and the public key spk2 of secondary server S2 (resp., spk1 of primary server S1), the authentication recovery procedure, which is run by the primary server S1 (resp., secondary server S2), outputs a plaintext authentication ri or ⊥ that signifies an error in recovery. We denote ri/⊥⟵AuthRecZi,ssk1,spk2 or ri/⊥⟵AuthRecZi,ssk2,spk1.Primary server equality test: on input of the authentications ri and rℓ of two users Ui and Uℓ, respectively, their public keys pki and pkℓ, their ciphertexts C and C′, and the secret key ssk1 of the primary server S1, the first equality test procedure, which is run by the primary server S1, outputs an intermediate result Θ and gives it to the secondary server S2. We denote Θ⟵TestS1ri,rℓ,pki,pkℓ,C,C′,ssk1.Secondary server equality test: on input of the authentications ri and rℓ of two users Ui and Uℓ, respectively, their public keys pki and pkℓ, an intermediate result Θ, and the secret key ssk2 of the secondary server S2, the second equality test procedure, which is run by the secondary server S2, outputs 1 if C and C′ encrypt the same message or 0 otherwise. We denote 1/0⟵TestS2ri,rℓ,pki,pkℓ,Θ,ssk2.A PKE-AUT scheme must besound in the sense that (1) each ciphertext produced by the data encryption procedure is decryptable by the data decryption procedure; (2) the ciphertext authentication produced by the authentication generation procedure can be recovered by the authentication recovery procedure; (3) for any two ciphertexts that encrypt the same message, which may be generated by different users, the two equality test procedures must finally output 1; and (4) for any two ciphertexts that encrypt different messages, which may be generated by different users, the two equality test procedures must finally output 0 with overwhelming probability.Definition 1 (soundness).
A PKE-AUT scheme is sound if, for any security parameterλ, any public parameters Para⟵Setup1λ, any public/secret key pairs of two users pki,ski⟵UKeyGenPara and pkℓ,skℓ⟵UKeyGenPara, and any public/secret key pairs of two servers spk1,ssk1⟵SKeyGenPara and spk2,ssk2⟵SKeyGenPara, the following conditions hold:
(i)
For any messagem, Decryptski,spk1,spk2,Encryptpki,spk1,spk2,m=m.(ii)
AuthRecAuthGenski,spk1,spk2,ssk1,spk2=ri and AuthRecAuthGenski,spk1,spk2,ssk2,spk1=ri.(iii)
For any two messagesm,m′ such that C⟵Encryptpki,spk1,spk2,m and C′⟵Encryptpkℓ,spk1,spk2,m′, if m=m′, then TestS2ri,rℓ,pki,pkℓ,Θ,ssk2=1; otherwise, PrTestS2ri,rℓ,pki,pkℓ,Θ,ssk2=1≤ϵ·, where ri=AuthRecAuthGenski,spk1,spk2,ssk1,spk2=AuthRecAuthGenski,spk1,spk2,ssk2,spk1, rℓ=AuthRecAuthGenskℓ,spk1,spk2,ssk1,spk2=AuthRecAuthGenskℓ,spk1,spk2,ssk2,spk1, and Θ⟵TestS1ri,rℓ,pki,pkℓ,C,C′,ssk1, and ϵ· denotes a negligible function.


## 3.1. System Model

As shown in Figure1, the PKE-AUT system under the dual server model consists of four types of entities, namely, trusted authority, primary server, secondary server, and users. The trusted authority is responsible for initializing the system, picking the security parameter, and producing public system parameters. Both data sender and data receiver are system users. Before being uploaded to the primary server, the data is encrypted using the public keys of the data receiver and two servers, so that only the data in the ciphertext format is outsourced. The data receiver is able to retrieve the data from the primary server for decryption with his private key and issue the same authorization to the primary and secondary servers, so that the two servers can jointly perform equality test on ciphertexts.Figure 1
System model of PKE-AUT.In the PKE-AUT system, the primary server and secondary server are assumed not to collude. All outsourced data are stored at the primary server in ciphertext format to protect their privacy. After being authorized, the primary server can perform the partial equality test procedure on outsourced ciphertexts, where the intermediate results would be produced and sent to the secondary server for processing. The second server further determines whether the ciphertexts encrypt the same data according to the intermediate results and gives the final equality test result to the data user. This equality test procedure with two phases can be executed in multiuser setting; that is, the primary and secondary servers can perform the equality test on ciphertexts of multiple users according to their authorization.


## 3.2. Security Requirements

In the PKE-AUT system under the dual server model, the primary server and the secondary server are independent and would not collude to attack the outsourced data. A secure PKE-AUT system has to satisfy the following requirements.(i)
Data privacy against the primary server: user data are stored at the primary server. Although the primary server is authorized to perform the equality test on ciphertexts, it cannot obtain the plaintexts from ciphertexts.(ii)
Data privacy against the secondary server: after obtaining the authorization for conducting equality test from users, the secondary server cannot deduce the plaintext information of outsourced data from the received intermediate results.(iii)
Privacy protection on authentication: the authentication generated by the data user can only be decrypted by the primary server and secondary server.


## 3.3. System Framework

A PKE-AUT scheme is composed of nine procedures, namely, the system setup, user key generation, server key generation, data encryption, data decryption, authentication generation, authentication recovery, primary server equality test, and secondary server equality test.System setup: on input of the security parameter 1λ, which is carried out by the trusted authority, outputs the system public parameters Para. We denote Para⟵Setup1λ.User key generation: on input of the system public parameters Para, the user key generation procedure, which is carried out by each user Ui, generates a pair of public key pki and secret key ski. We denote pki,ski⟵UKeyGenPara.Server key generation: on input of the system public parameters Para, the server key generation procedure, which is carried out by each server Sj including the primary server S1 and secondary server S2, generates a pair of public key spkj and secret key sskj. We denote spkj,sskj⟵SKeyGenPara.Data encryption: on input of the public keys pki,spk1,spk2of data receiver Ui, primary server S1 and secondary server S2, and a message m, the data encryption procedure, which is run by the data sender, generates a ciphertext C and outsources it to the primary server S1. We denote C⟵Encryptpki,spk1,spk2,m.Data decryption: on input of the secret key ski of user Ui, the public keys spk1,spk2 of primary server S1 and secondary server S2, and a ciphertext C, the data decryption procedure, which is run by the data receiver, outputs a plaintext m or ⊥ that signifies an error in decryption. We denote m/⊥⟵Decryptski,spk1,spk2,C.Authentication generation: on input of the secret key ski of user Ui and the public keys spk1,spk2 of primary server S1 and secondary server S2, the authentication generation procedure, which is run by user Ui, generates a ciphertext authentication Zi for two servers. Note that two servers have the same ciphertext authentication Zi. We denote Zi⟵AuthGenski,spk1,spk2.Authentication recovery: on input of a ciphertext authentication Zi, the secret key ssk1 of primary server S1 (resp., ssk2 of secondary server S2), and the public key spk2 of secondary server S2 (resp., spk1 of primary server S1), the authentication recovery procedure, which is run by the primary server S1 (resp., secondary server S2), outputs a plaintext authentication ri or ⊥ that signifies an error in recovery. We denote ri/⊥⟵AuthRecZi,ssk1,spk2 or ri/⊥⟵AuthRecZi,ssk2,spk1.Primary server equality test: on input of the authentications ri and rℓ of two users Ui and Uℓ, respectively, their public keys pki and pkℓ, their ciphertexts C and C′, and the secret key ssk1 of the primary server S1, the first equality test procedure, which is run by the primary server S1, outputs an intermediate result Θ and gives it to the secondary server S2. We denote Θ⟵TestS1ri,rℓ,pki,pkℓ,C,C′,ssk1.Secondary server equality test: on input of the authentications ri and rℓ of two users Ui and Uℓ, respectively, their public keys pki and pkℓ, an intermediate result Θ, and the secret key ssk2 of the secondary server S2, the second equality test procedure, which is run by the secondary server S2, outputs 1 if C and C′ encrypt the same message or 0 otherwise. We denote 1/0⟵TestS2ri,rℓ,pki,pkℓ,Θ,ssk2.A PKE-AUT scheme must besound in the sense that (1) each ciphertext produced by the data encryption procedure is decryptable by the data decryption procedure; (2) the ciphertext authentication produced by the authentication generation procedure can be recovered by the authentication recovery procedure; (3) for any two ciphertexts that encrypt the same message, which may be generated by different users, the two equality test procedures must finally output 1; and (4) for any two ciphertexts that encrypt different messages, which may be generated by different users, the two equality test procedures must finally output 0 with overwhelming probability.Definition 1 (soundness).
A PKE-AUT scheme is sound if, for any security parameterλ, any public parameters Para⟵Setup1λ, any public/secret key pairs of two users pki,ski⟵UKeyGenPara and pkℓ,skℓ⟵UKeyGenPara, and any public/secret key pairs of two servers spk1,ssk1⟵SKeyGenPara and spk2,ssk2⟵SKeyGenPara, the following conditions hold:
(i)
For any messagem, Decryptski,spk1,spk2,Encryptpki,spk1,spk2,m=m.(ii)
AuthRecAuthGenski,spk1,spk2,ssk1,spk2=ri and AuthRecAuthGenski,spk1,spk2,ssk2,spk1=ri.(iii)
For any two messagesm,m′ such that C⟵Encryptpki,spk1,spk2,m and C′⟵Encryptpkℓ,spk1,spk2,m′, if m=m′, then TestS2ri,rℓ,pki,pkℓ,Θ,ssk2=1; otherwise, PrTestS2ri,rℓ,pki,pkℓ,Θ,ssk2=1≤ϵ·, where ri=AuthRecAuthGenski,spk1,spk2,ssk1,spk2=AuthRecAuthGenski,spk1,spk2,ssk2,spk1, rℓ=AuthRecAuthGenskℓ,spk1,spk2,ssk1,spk2=AuthRecAuthGenskℓ,spk1,spk2,ssk2,spk1, and Θ⟵TestS1ri,rℓ,pki,pkℓ,C,C′,ssk1, and ϵ· denotes a negligible function.


## 4. PKE-AUT Construction

### 4.1. Concrete Construction

This section presents our PKE-AUT construction on bilinear groups in the dual server model, where a running procedure is shown in Figure2. The frequently used symbols are summarized in Table 1.Figure 2
A procedure of the proposed PKE-AUT scheme.Table 1
Notations.
SymbolMeaningλSecurity parameterG,GTCyclic groups of prime orderq satisfying bilinear pairing e^:G×G⟶GTH1,H2,H3,H4Cryptographic hash functionsgA generator ofGski=xi,1,xi,2,xi,3Private key of userUipki=χi,1,χi,2,χi,3Public key of userUispk1=ρ1,1,ρ1,2Public key of primary serverS1ssk1=y1,1,y1,2Secret key of primary serverS1spk2=ρ2,1,ρ2,2Public key of secondary serverS2ssk2=y2,1,y2,2Secret key of secondary serverS2δ,βRandom elements inZq∗C=c1,c2,c3Ciphertext of messagemZi=zi,1,zi,2Authentication of userUi in ciphertext formatri,rℓAuthentications of usersUi and UℓΘ=c1,c1′,ωIntermediate result of equality testγ,γ′Temporary elements for computingω


#### 4.1.1. System Setup

With security parameter1λ, the trusted authority picks two cyclic groups G=g and GT of prime order q, which satisfy bilinear mapping e^:G×G⟶GT. It also chooses four cryptographic hash functions H1:G×GT⟶G, H2:G×G⟶0,1τG+logq, H3:GT⟶0,1logq, and H4:0,1τm⟶G, where τG denotes the element size in group G and τm represents the size of messages. The system public parameters are Para=λ,G,GT,q,e^,g,H1,H2,H3,H4.


#### 4.1.2. User Key Generation

Each userUi randomly picks three elements xi,1,xi,2,xi,3∈Zq∗ and computes
(3)χi,1=gxi,1,χi,2=gxi,2,χi,3=gxi,3.Thus, the public key and secret key of userUi are pki=χi,1,χi,2,χi,3 and ski=xi,1,xi,2,xi,3, respectively.


#### 4.1.3. Server Key Generation

The primary serverS1 randomly selects two elements y1,1,y1,2∈Zq∗ and computes
(4)ρ1,1=gy1,1,ρ1,2=gy1,2.Thus, the public key and secret key of primary serverS1 are spk1=ρ1,1,ρ1,2 and ssk1=y1,1,y1,2, respectively. In a similar way, the secondary server S2 is able to generate its public key spk2=ρ2,1,ρ2,2 and secret key ssk2=y2,1,y2,2.


#### 4.1.4. Data Encryption

For a messagem∈0,1τm, the data sender randomly picks δ∈Zq∗ and computes the ciphertext C=c1,c2,c3 as follows:
(5)c1=gδ,c2=H4m·H1χi,1δe^χi,2,ρ1,1δ·H1χi,1δe^χi,2,ρ2,1δ,c3=mδ⊕H2χi,3δH4m,where ∥ denotes the concatenation of strings and ⊕ represents the XOR operation. Then, the ciphertext C=c1,c2,c3 is sent to the primary server S1.


#### 4.1.5. Data Decryption

Given a ciphertextC=c1,c2,c3, the data receiver computes
(6)m′δ′=c3⊕H2c1xi,3Φ, where
(7)Φ=c2H1c1xi,1e^c1,ρ1,1xi,2·H1c1xi,1e^c1,ρ2,1xi,2,then verifies
(8)c1=?gδ′,(9)Φ=?H4m′.If both equalities hold, then the data receiver outputsm′, otherwise ⊥.


#### 4.1.6. Authentication Generation

Data userUi randomly picks an element β∈Zq∗ and computes the ciphertext authentication Zi=zi,1,zi,2 as follows:
(10)zi,1=gβ,zi,2=xi,1⊕H3e^ρ1,2,ρ2,2β.Data userUi sends the ciphertext authentication Zi=zi,1,zi,2 to two servers S1 and S2.


#### 4.1.7. Authentication Recovery

The primary serverS1 computes
(11)xi,1′=zi,2⊕H3e^zi,1,ρ2,2y1,2,and verifies
(12)χi,1=?gxi,1′.If the equality in (12) is satisfied, then the primary server S1 outputs plaintext authentication ri=xi,1′, otherwise outputs symbol ⊥. The secondary server can run the recovery procedure to obtain the same plaintext authentication ri=xi,1′ in the similar way.


#### 4.1.8. Primary Server Equality Test

For ciphertextC=c1,c2,c3 of user Ui and ciphertext C′=c1′,c2′,c3′ of user Uℓ, the primary server S1 generates the intermediate result Θ=c1,c1′,ω according to their authentications ri and rℓ as follows. The primary server S1 computes
(13)γ=c2H1c1rie^χi,2,c1y1,1,γ′=c2′H1c1′rℓe^χℓ,2,c1′y1,1.It continues to compute(14)ω=γγ′.The intermediate resultΘ=c1,c1′,ω is sent to the secondary server S2.


#### 4.1.9. Secondary Server Equality Test

For the received intermediate resultΘ=c1,c1′,ω, the secondary server S2 verifies
(15)ω=?H1c1rie^χi,2,c1y2,1H1c1′rℓe^χℓ,2,c1′y2,1.If the equality in (15) is satisfied, then the secondary server S2 outputs 1; otherwise, it outputs 0.


### 4.2. Soundness

Theorem 1.
The proposed PKE-AUT scheme in the dual server model is sound.Proof.
(1)
For data decryption, since(16)Φ=c2H1c1xi,1e^c1,ρ1,1xi,2·H1c1xi,1e^c1,ρ2,1xi,2=H4m·H1χi,1δe^χi,2,ρ1,1δ·H1χi,1δe^χi,2,ρ2,1δH1c1xi,1e^gδ,ρ1,1xi,2·H1c1xi,1e^gδ,ρ2,1xi,2=H4m·H1c1xi,1e^χi,2,ρ1,1δ·H1c1xi,1e^χi,2,ρ2,1δH1c1xi,1e^χi,2,ρ1,1δ·H1c1xi,1e^χi,2,ρ2,1δ=H4m,we have
(17)m′δ′=c3⊕H2c1xi,3Φ=mδ⊕H2χi,3δH4m⊕H2gδxi,3H4m=mδ⊕H2χi,3δH4m⊕H2χi,3δH4m=mδ.Thus, the equalities in (8) and (9) hold.(2)
For authentication recovery, since(18)xi,1′=zi,2⊕H3e^zi,1,ρ2,2y1,2=xi,1⊕H3e^ρ1,2,ρ2,2β⊕H3e^gβ,ρ2,2y1,2=xi,1⊕H3e^ρ1,2,ρ2,2β⊕H3e^ρ1,2,ρ2,2β=xi,1,the equality in (12) is satisfied.(3)
For equality test on ciphertexts, since(19)γ=c2H1c1rie^χi,2,c1y1,1=H4m·H1χi,1δe^χi,2,ρ1,1δ·H1χi,1δe^χi,2,ρ2,1δH1c1xi,1′e^χi,2,gδy1,1=H4m·H1χi,1δe^χi,2,ρ1,1δ·H1χi,1δe^χi,2,ρ2,1δH1c1xi,1e^χi,2,ρ1,1δ=H4m·H1χi,1δe^χi,2,ρ2,1δ,γ′=c2′H1c1′rℓe^χℓ,2,c1′y1,1=H4m′·H1χℓ,1δ′e^χℓ,2,ρ1,1δ′·H1χℓ,1δ′e^χℓ,2,ρ2,1δ′H1c1′xℓ,1′e^χℓ,2,gδ′y1,1=H4m′·H1χℓ,1δ′e^χℓ,2,ρ1,1δ′·H1χℓ,1δ′e^χℓ,2,ρ2,1δ′H1c1′xℓ,1e^χℓ,2,ρ1,1δ′=H4m′·H1χℓ,1δ′e^χℓ,2,ρ2,1δ′,we have
(20)ω=γ/γ′=H4m·H1χi,1δe^χi,2,ρ2,1δH4m′·H1χℓ,1δ′e^χℓ,2,ρ2,1δ′.
Also, we know(21)H1c1rie^χi,2,c1y2,1H1c1′rℓe^χℓ,2,c1′y2,1=H1gδ′xi,1e^χi,2,gδy2,1H1gδ′x′ℓ,1e^χℓ,2,gδ′y2,1=H1gδxi,1e^χi,2,ρ2,1δH1gδ′xℓ,1e^χℓ,2,ρ2,1δ′=H1χi,1δe^χi,2,ρ2,1δH1χℓ,1δ′e^χℓ,2,ρ2,1δ′.
It can be seen that if and only ifm=m′, the equality in (15) is satisfied.
Therefore, the proposed PKE-AUT scheme in the dual server model is sound.


## 4.1. Concrete Construction

This section presents our PKE-AUT construction on bilinear groups in the dual server model, where a running procedure is shown in Figure2. The frequently used symbols are summarized in Table 1.Figure 2
A procedure of the proposed PKE-AUT scheme.Table 1
Notations.
SymbolMeaningλSecurity parameterG,GTCyclic groups of prime orderq satisfying bilinear pairing e^:G×G⟶GTH1,H2,H3,H4Cryptographic hash functionsgA generator ofGski=xi,1,xi,2,xi,3Private key of userUipki=χi,1,χi,2,χi,3Public key of userUispk1=ρ1,1,ρ1,2Public key of primary serverS1ssk1=y1,1,y1,2Secret key of primary serverS1spk2=ρ2,1,ρ2,2Public key of secondary serverS2ssk2=y2,1,y2,2Secret key of secondary serverS2δ,βRandom elements inZq∗C=c1,c2,c3Ciphertext of messagemZi=zi,1,zi,2Authentication of userUi in ciphertext formatri,rℓAuthentications of usersUi and UℓΘ=c1,c1′,ωIntermediate result of equality testγ,γ′Temporary elements for computingω


### 4.1.1. System Setup

With security parameter1λ, the trusted authority picks two cyclic groups G=g and GT of prime order q, which satisfy bilinear mapping e^:G×G⟶GT. It also chooses four cryptographic hash functions H1:G×GT⟶G, H2:G×G⟶0,1τG+logq, H3:GT⟶0,1logq, and H4:0,1τm⟶G, where τG denotes the element size in group G and τm represents the size of messages. The system public parameters are Para=λ,G,GT,q,e^,g,H1,H2,H3,H4.


### 4.1.2. User Key Generation

Each userUi randomly picks three elements xi,1,xi,2,xi,3∈Zq∗ and computes
(3)χi,1=gxi,1,χi,2=gxi,2,χi,3=gxi,3.Thus, the public key and secret key of userUi are pki=χi,1,χi,2,χi,3 and ski=xi,1,xi,2,xi,3, respectively.


### 4.1.3. Server Key Generation

The primary serverS1 randomly selects two elements y1,1,y1,2∈Zq∗ and computes
(4)ρ1,1=gy1,1,ρ1,2=gy1,2.Thus, the public key and secret key of primary serverS1 are spk1=ρ1,1,ρ1,2 and ssk1=y1,1,y1,2, respectively. In a similar way, the secondary server S2 is able to generate its public key spk2=ρ2,1,ρ2,2 and secret key ssk2=y2,1,y2,2.


### 4.1.4. Data Encryption

For a messagem∈0,1τm, the data sender randomly picks δ∈Zq∗ and computes the ciphertext C=c1,c2,c3 as follows:
(5)c1=gδ,c2=H4m·H1χi,1δe^χi,2,ρ1,1δ·H1χi,1δe^χi,2,ρ2,1δ,c3=mδ⊕H2χi,3δH4m,where ∥ denotes the concatenation of strings and ⊕ represents the XOR operation. Then, the ciphertext C=c1,c2,c3 is sent to the primary server S1.


### 4.1.5. Data Decryption

Given a ciphertextC=c1,c2,c3, the data receiver computes
(6)m′δ′=c3⊕H2c1xi,3Φ, where
(7)Φ=c2H1c1xi,1e^c1,ρ1,1xi,2·H1c1xi,1e^c1,ρ2,1xi,2,then verifies
(8)c1=?gδ′,(9)Φ=?H4m′.If both equalities hold, then the data receiver outputsm′, otherwise ⊥.


### 4.1.6. Authentication Generation

Data userUi randomly picks an element β∈Zq∗ and computes the ciphertext authentication Zi=zi,1,zi,2 as follows:
(10)zi,1=gβ,zi,2=xi,1⊕H3e^ρ1,2,ρ2,2β.Data userUi sends the ciphertext authentication Zi=zi,1,zi,2 to two servers S1 and S2.


### 4.1.7. Authentication Recovery

The primary serverS1 computes
(11)xi,1′=zi,2⊕H3e^zi,1,ρ2,2y1,2,and verifies
(12)χi,1=?gxi,1′.If the equality in (12) is satisfied, then the primary server S1 outputs plaintext authentication ri=xi,1′, otherwise outputs symbol ⊥. The secondary server can run the recovery procedure to obtain the same plaintext authentication ri=xi,1′ in the similar way.


### 4.1.8. Primary Server Equality Test

For ciphertextC=c1,c2,c3 of user Ui and ciphertext C′=c1′,c2′,c3′ of user Uℓ, the primary server S1 generates the intermediate result Θ=c1,c1′,ω according to their authentications ri and rℓ as follows. The primary server S1 computes
(13)γ=c2H1c1rie^χi,2,c1y1,1,γ′=c2′H1c1′rℓe^χℓ,2,c1′y1,1.It continues to compute(14)ω=γγ′.The intermediate resultΘ=c1,c1′,ω is sent to the secondary server S2.


### 4.1.9. Secondary Server Equality Test

For the received intermediate resultΘ=c1,c1′,ω, the secondary server S2 verifies
(15)ω=?H1c1rie^χi,2,c1y2,1H1c1′rℓe^χℓ,2,c1′y2,1.If the equality in (15) is satisfied, then the secondary server S2 outputs 1; otherwise, it outputs 0.


## 4.1.1. System Setup

With security parameter1λ, the trusted authority picks two cyclic groups G=g and GT of prime order q, which satisfy bilinear mapping e^:G×G⟶GT. It also chooses four cryptographic hash functions H1:G×GT⟶G, H2:G×G⟶0,1τG+logq, H3:GT⟶0,1logq, and H4:0,1τm⟶G, where τG denotes the element size in group G and τm represents the size of messages. The system public parameters are Para=λ,G,GT,q,e^,g,H1,H2,H3,H4.


## 4.1.2. User Key Generation

Each userUi randomly picks three elements xi,1,xi,2,xi,3∈Zq∗ and computes
(3)χi,1=gxi,1,χi,2=gxi,2,χi,3=gxi,3.Thus, the public key and secret key of userUi are pki=χi,1,χi,2,χi,3 and ski=xi,1,xi,2,xi,3, respectively.


## 4.1.3. Server Key Generation

The primary serverS1 randomly selects two elements y1,1,y1,2∈Zq∗ and computes
(4)ρ1,1=gy1,1,ρ1,2=gy1,2.Thus, the public key and secret key of primary serverS1 are spk1=ρ1,1,ρ1,2 and ssk1=y1,1,y1,2, respectively. In a similar way, the secondary server S2 is able to generate its public key spk2=ρ2,1,ρ2,2 and secret key ssk2=y2,1,y2,2.


## 4.1.4. Data Encryption

For a messagem∈0,1τm, the data sender randomly picks δ∈Zq∗ and computes the ciphertext C=c1,c2,c3 as follows:
(5)c1=gδ,c2=H4m·H1χi,1δe^χi,2,ρ1,1δ·H1χi,1δe^χi,2,ρ2,1δ,c3=mδ⊕H2χi,3δH4m,where ∥ denotes the concatenation of strings and ⊕ represents the XOR operation. Then, the ciphertext C=c1,c2,c3 is sent to the primary server S1.


## 4.1.5. Data Decryption

Given a ciphertextC=c1,c2,c3, the data receiver computes
(6)m′δ′=c3⊕H2c1xi,3Φ, where
(7)Φ=c2H1c1xi,1e^c1,ρ1,1xi,2·H1c1xi,1e^c1,ρ2,1xi,2,then verifies
(8)c1=?gδ′,(9)Φ=?H4m′.If both equalities hold, then the data receiver outputsm′, otherwise ⊥.


## 4.1.6. Authentication Generation

Data userUi randomly picks an element β∈Zq∗ and computes the ciphertext authentication Zi=zi,1,zi,2 as follows:
(10)zi,1=gβ,zi,2=xi,1⊕H3e^ρ1,2,ρ2,2β.Data userUi sends the ciphertext authentication Zi=zi,1,zi,2 to two servers S1 and S2.


## 4.1.7. Authentication Recovery

The primary serverS1 computes
(11)xi,1′=zi,2⊕H3e^zi,1,ρ2,2y1,2,and verifies
(12)χi,1=?gxi,1′.If the equality in (12) is satisfied, then the primary server S1 outputs plaintext authentication ri=xi,1′, otherwise outputs symbol ⊥. The secondary server can run the recovery procedure to obtain the same plaintext authentication ri=xi,1′ in the similar way.


## 4.1.8. Primary Server Equality Test

For ciphertextC=c1,c2,c3 of user Ui and ciphertext C′=c1′,c2′,c3′ of user Uℓ, the primary server S1 generates the intermediate result Θ=c1,c1′,ω according to their authentications ri and rℓ as follows. The primary server S1 computes
(13)γ=c2H1c1rie^χi,2,c1y1,1,γ′=c2′H1c1′rℓe^χℓ,2,c1′y1,1.It continues to compute(14)ω=γγ′.The intermediate resultΘ=c1,c1′,ω is sent to the secondary server S2.


## 4.1.9. Secondary Server Equality Test

For the received intermediate resultΘ=c1,c1′,ω, the secondary server S2 verifies
(15)ω=?H1c1rie^χi,2,c1y2,1H1c1′rℓe^χℓ,2,c1′y2,1.If the equality in (15) is satisfied, then the secondary server S2 outputs 1; otherwise, it outputs 0.


## 4.2. Soundness

Theorem 1.
The proposed PKE-AUT scheme in the dual server model is sound.Proof.
(1)
For data decryption, since(16)Φ=c2H1c1xi,1e^c1,ρ1,1xi,2·H1c1xi,1e^c1,ρ2,1xi,2=H4m·H1χi,1δe^χi,2,ρ1,1δ·H1χi,1δe^χi,2,ρ2,1δH1c1xi,1e^gδ,ρ1,1xi,2·H1c1xi,1e^gδ,ρ2,1xi,2=H4m·H1c1xi,1e^χi,2,ρ1,1δ·H1c1xi,1e^χi,2,ρ2,1δH1c1xi,1e^χi,2,ρ1,1δ·H1c1xi,1e^χi,2,ρ2,1δ=H4m,we have
(17)m′δ′=c3⊕H2c1xi,3Φ=mδ⊕H2χi,3δH4m⊕H2gδxi,3H4m=mδ⊕H2χi,3δH4m⊕H2χi,3δH4m=mδ.Thus, the equalities in (8) and (9) hold.(2)
For authentication recovery, since(18)xi,1′=zi,2⊕H3e^zi,1,ρ2,2y1,2=xi,1⊕H3e^ρ1,2,ρ2,2β⊕H3e^gβ,ρ2,2y1,2=xi,1⊕H3e^ρ1,2,ρ2,2β⊕H3e^ρ1,2,ρ2,2β=xi,1,the equality in (12) is satisfied.(3)
For equality test on ciphertexts, since(19)γ=c2H1c1rie^χi,2,c1y1,1=H4m·H1χi,1δe^χi,2,ρ1,1δ·H1χi,1δe^χi,2,ρ2,1δH1c1xi,1′e^χi,2,gδy1,1=H4m·H1χi,1δe^χi,2,ρ1,1δ·H1χi,1δe^χi,2,ρ2,1δH1c1xi,1e^χi,2,ρ1,1δ=H4m·H1χi,1δe^χi,2,ρ2,1δ,γ′=c2′H1c1′rℓe^χℓ,2,c1′y1,1=H4m′·H1χℓ,1δ′e^χℓ,2,ρ1,1δ′·H1χℓ,1δ′e^χℓ,2,ρ2,1δ′H1c1′xℓ,1′e^χℓ,2,gδ′y1,1=H4m′·H1χℓ,1δ′e^χℓ,2,ρ1,1δ′·H1χℓ,1δ′e^χℓ,2,ρ2,1δ′H1c1′xℓ,1e^χℓ,2,ρ1,1δ′=H4m′·H1χℓ,1δ′e^χℓ,2,ρ2,1δ′,we have
(20)ω=γ/γ′=H4m·H1χi,1δe^χi,2,ρ2,1δH4m′·H1χℓ,1δ′e^χℓ,2,ρ2,1δ′.
Also, we know(21)H1c1rie^χi,2,c1y2,1H1c1′rℓe^χℓ,2,c1′y2,1=H1gδ′xi,1e^χi,2,gδy2,1H1gδ′x′ℓ,1e^χℓ,2,gδ′y2,1=H1gδxi,1e^χi,2,ρ2,1δH1gδ′xℓ,1e^χℓ,2,ρ2,1δ′=H1χi,1δe^χi,2,ρ2,1δH1χℓ,1δ′e^χℓ,2,ρ2,1δ′.
It can be seen that if and only ifm=m′, the equality in (15) is satisfied.
Therefore, the proposed PKE-AUT scheme in the dual server model is sound.


## 5. Analysis and Comparison

### 5.1. Security Analysis

Theorem 2.
The proposed PKE-AUT scheme in the dual server model can protect the privacy of outsourced data against the primary server.Proof.
The ciphertext in the proposed PKE-AUT scheme has the similar form in Lee et al.’s scheme [18]. The difference lies in that for generating the second element c2 in ciphertext, all the public keys of the data receiver and two servers should be used in the proposed PKE-AUT scheme; in this way, these two servers after being authorized are allowed to jointly perform the equality test on ciphertexts with their private keys. The proof is similar to that of Theorem 4. 1 in [18], except for a small difference in the simulation on the decryption oracle; that is, the proposed PKE-AUT scheme offers the indistinguishability under adaptive chosen ciphertext attacks (IND-CCA) against the primary server assuming the CDH and CBDH assumptions hold.Theorem 3.
The proposed PKE-AUT scheme in the dual server model can protect the privacy of outsourced data against the secondary server.Proof.
In the proposed PKE-AUT scheme, all outsourced ciphertexts are stored at the primary server. During the process of equality test on ciphertexts, only the intermediate resultΘ=c1,γ,c1′,γ′ is delivered to the secondary server by the primary server. Note that the pairs c1,γ and c1′,γ′ have the similar form of Lee et al.’s scheme [18], where the difference lies in that their scheme also has another element for enabling decryption by the user. Thus, the proof is similar to that of Theorem 4.1 in [18]; that is, the proposed PKE-AUT scheme is IND-CCA secure against the secondary server under the CDH and CBDH assumptions.Theorem 4.
The proposed PKE-AUT scheme in the dual server model can protect the privacy of authentication.Proof.
The ciphertext authentication generated by the proposed PKE-AUT scheme has the similar format as the ciphertexts in Boneh and Franklin’s identity-based encryption scheme (Section4 of [28]). The difference is that in the input to the hash function H3, the public keys of two servers are both used in evaluating e^·,·, whereas the user identity and public parameters are used in Boneh and Franklin’s scheme [28]. Thus, the proof is similar to that of Theorem 4.1 in [28]; that is, the authentication in the proposed PKE-AUT scheme enjoys the indistinguishability under chosen plaintext attacks (IND-CPA) assuming the CBDH assumption holds.


### 5.2. Performance Analysis

This section analyzes the performance of the proposed PKE-AUT scheme and compares with existing schemes, where only resource-intensive operations such as exponentiation, bilinear pairing, and map-to-point hash function are considered. The comparison with Wu et al.’s scheme [15] is shown in Table 2, where Pair,Expo,Hash denote the evaluation costs of a bilinear pairing e^·,·, an exponentiation in group G, and a map-to-point hash function, respectively.Table 2
Comparison of computing costs.
ProcedureOur PKE-AUT schemeWu et al.’s scheme [15]UKeyGen3Expo2Expo+1HashSKeyGen2Expo2Expo/1ExpoEncrypt4Expo+2Pair+3Hash5Expo+3Pair+2HashDecrypt4Expo+2Pair+3Hash2Expo+1PairAuthGen2Expo+1Pair—AuthRec2Expo+1Pair—TestS14Expo+2Pair+2Hash2Pair+2HashTestS24Expo+2Pair+2Hash4Pair+2HashIt can be seen from Table2 that, for producing a pair of public and secret keys for each user, our UKeyGen procedure requires 3 exponentiations in group G. Although our UKeyGen procedure has one more exponentiation than Wu et al.’s scheme [15], it does not take any map-to-point hash evaluation. The SKeyGen procedure in our PKE-AUT scheme is executed by the primary server and secondary server, respectively, for generating their public and secret keys. Thus, their key pairs have the same form, where each takes 2 exponentiations in group G. While in Wu et al.’s scheme [15], the two servers run different key generation procedures, which implies their key pairs are in different form and take two and one exponentiation in group G, respectively.In the data encryption phase, the exponentiations in groupGT in our PKE-AUT scheme and Wu et al.’s scheme [15] can be transformed into exponentiations in group G; in this way, the corresponding parameters can be used in multiple steps and the efficiency can be improved. In this case, the Encrypt of our PKE-AUT scheme takes one less bilinear pairing operation than that in Wu et al.’s scheme [15] for encrypting a message. Note that our PKE-AUT scheme is able to concurrently authorize the primary server and secondary server to perform the equality test on ciphertexts, which makes the ciphertext contain more elements than that of Wu et al.’s scheme [15]. Thus, for data decryption, our PKE-AUT scheme should take more computations than Wu et al.’s scheme [15].In our PKE-AUT scheme, the data user is able to generate the ciphertext authentication for two servers; that is, the same ciphertext authentication can be recovered by both the primary server and the secondary server with their respective secret keys. Thus, the computing costs for authentication generation can be reduced compared to issuing an authentication for each server separately. Since the exponentiation in groupGT can be converted to the one in group G, both AuthGen and AuthRec procedures have the same computing costs, that is, two exponentiations in group G and one map-to-point hash evaluation. In Wu et al.’s scheme [15], the privacy of authentication is not considered.With authentication, the primary server and secondary server can cooperatively perform the equality test on ciphertexts. In our PKE-AUT scheme, both equality test procedures for two servers should take4 more exponentiations in group G than Wu et al.’s scheme [15], since the generation of the second element c2 in the ciphertext of our PKE-AUT scheme requires more input parameters for achieving the equality test on the ciphertext by two servers. It can be seen that the two servers in both schemes do not have the same computing costs, since the secondary server needs to run two bilinear pairings in generating the result of the equality test on a pair of ciphertexts.The communication costs of our PKE-AUT scheme and Wu et al.’s scheme [15] are compared in Table 3. In our scheme, each ciphertext has three elements, while the ciphertext in Wu et al.’s scheme [15] contains five elements. Note that the message space of Wu et al.’s scheme [15] is cyclic group G. Thus, when both schemes have the same message space G, the ciphertext size of their scheme would be 2τG more than our PKE-AUT scheme. The authentication token was not encrypted for protecting privacy in Wu et al.’s scheme [15], which only contains one element in group G. For the equality test procedure by the primary server, the generated intermediate result Θ=c1,c1′,ω in our PKE-AUT scheme has three elements in group G, while Wu et al.’s scheme [15] requires six elements in G.Table 3
Comparison of communication costs.
Our PKE-AUT schemeWu et al.’s scheme [15]Ciphertext2τG+τm+logq5τG+logqAuthenticationτG+logqτGIntermediate result3τG6τGMoreover, we analyze the performance of our PKE-AUT scheme and compare with Wu et al.’s scheme [15] in the dual server model according to the experimental results of cryptographic operations in [29, 30]. In [29], the experiments were conducted on a platform with Windows 7 operating system, Intel I7-4700@3.40 GHz CPU and 4 GB memory. Moreover, the MIRACL Cryptographic SDK [31] was invoked with logp=512. The execution time of some cryptographic operations are summarized in Table 4.Table 4
Execution time of cryptographic operations.
OperationExecution time (milliseconds)Pair4.211Expo1.709Hash4.406The performance of all procedures of our PKE-AUT scheme and Wu et al.’s scheme [15] is depicted in Figures 3 and 4, respectively. The case where each procedure is executed once is considered for both schemes. It can be seen that the proposed PKE-AUT scheme is more efficient than Wu et al.’s scheme [15] in encrypting a message. Although the decryption and equality test procedures take more time than Wu et al.’s scheme [15], our PKE-AUT scheme supports strict and symmetric authorization for equality test on ciphertexts. Thus, to achieve this, the public keys of two servers have to be used in generating the ciphertext in our PKE-AUT scheme, which makes the efficiency of decryption and equality test reduced slightly.Figure 3
Performance of each procedure in our PKE-AUT scheme.Figure 4
Performance of each procedure in Wu et al.’s scheme [15].


## 5.1. Security Analysis

Theorem 2.
The proposed PKE-AUT scheme in the dual server model can protect the privacy of outsourced data against the primary server.Proof.
The ciphertext in the proposed PKE-AUT scheme has the similar form in Lee et al.’s scheme [18]. The difference lies in that for generating the second element c2 in ciphertext, all the public keys of the data receiver and two servers should be used in the proposed PKE-AUT scheme; in this way, these two servers after being authorized are allowed to jointly perform the equality test on ciphertexts with their private keys. The proof is similar to that of Theorem 4. 1 in [18], except for a small difference in the simulation on the decryption oracle; that is, the proposed PKE-AUT scheme offers the indistinguishability under adaptive chosen ciphertext attacks (IND-CCA) against the primary server assuming the CDH and CBDH assumptions hold.Theorem 3.
The proposed PKE-AUT scheme in the dual server model can protect the privacy of outsourced data against the secondary server.Proof.
In the proposed PKE-AUT scheme, all outsourced ciphertexts are stored at the primary server. During the process of equality test on ciphertexts, only the intermediate resultΘ=c1,γ,c1′,γ′ is delivered to the secondary server by the primary server. Note that the pairs c1,γ and c1′,γ′ have the similar form of Lee et al.’s scheme [18], where the difference lies in that their scheme also has another element for enabling decryption by the user. Thus, the proof is similar to that of Theorem 4.1 in [18]; that is, the proposed PKE-AUT scheme is IND-CCA secure against the secondary server under the CDH and CBDH assumptions.Theorem 4.
The proposed PKE-AUT scheme in the dual server model can protect the privacy of authentication.Proof.
The ciphertext authentication generated by the proposed PKE-AUT scheme has the similar format as the ciphertexts in Boneh and Franklin’s identity-based encryption scheme (Section4 of [28]). The difference is that in the input to the hash function H3, the public keys of two servers are both used in evaluating e^·,·, whereas the user identity and public parameters are used in Boneh and Franklin’s scheme [28]. Thus, the proof is similar to that of Theorem 4.1 in [28]; that is, the authentication in the proposed PKE-AUT scheme enjoys the indistinguishability under chosen plaintext attacks (IND-CPA) assuming the CBDH assumption holds.


## 5.2. Performance Analysis

This section analyzes the performance of the proposed PKE-AUT scheme and compares with existing schemes, where only resource-intensive operations such as exponentiation, bilinear pairing, and map-to-point hash function are considered. The comparison with Wu et al.’s scheme [15] is shown in Table 2, where Pair,Expo,Hash denote the evaluation costs of a bilinear pairing e^·,·, an exponentiation in group G, and a map-to-point hash function, respectively.Table 2
Comparison of computing costs.
ProcedureOur PKE-AUT schemeWu et al.’s scheme [15]UKeyGen3Expo2Expo+1HashSKeyGen2Expo2Expo/1ExpoEncrypt4Expo+2Pair+3Hash5Expo+3Pair+2HashDecrypt4Expo+2Pair+3Hash2Expo+1PairAuthGen2Expo+1Pair—AuthRec2Expo+1Pair—TestS14Expo+2Pair+2Hash2Pair+2HashTestS24Expo+2Pair+2Hash4Pair+2HashIt can be seen from Table2 that, for producing a pair of public and secret keys for each user, our UKeyGen procedure requires 3 exponentiations in group G. Although our UKeyGen procedure has one more exponentiation than Wu et al.’s scheme [15], it does not take any map-to-point hash evaluation. The SKeyGen procedure in our PKE-AUT scheme is executed by the primary server and secondary server, respectively, for generating their public and secret keys. Thus, their key pairs have the same form, where each takes 2 exponentiations in group G. While in Wu et al.’s scheme [15], the two servers run different key generation procedures, which implies their key pairs are in different form and take two and one exponentiation in group G, respectively.In the data encryption phase, the exponentiations in groupGT in our PKE-AUT scheme and Wu et al.’s scheme [15] can be transformed into exponentiations in group G; in this way, the corresponding parameters can be used in multiple steps and the efficiency can be improved. In this case, the Encrypt of our PKE-AUT scheme takes one less bilinear pairing operation than that in Wu et al.’s scheme [15] for encrypting a message. Note that our PKE-AUT scheme is able to concurrently authorize the primary server and secondary server to perform the equality test on ciphertexts, which makes the ciphertext contain more elements than that of Wu et al.’s scheme [15]. Thus, for data decryption, our PKE-AUT scheme should take more computations than Wu et al.’s scheme [15].In our PKE-AUT scheme, the data user is able to generate the ciphertext authentication for two servers; that is, the same ciphertext authentication can be recovered by both the primary server and the secondary server with their respective secret keys. Thus, the computing costs for authentication generation can be reduced compared to issuing an authentication for each server separately. Since the exponentiation in groupGT can be converted to the one in group G, both AuthGen and AuthRec procedures have the same computing costs, that is, two exponentiations in group G and one map-to-point hash evaluation. In Wu et al.’s scheme [15], the privacy of authentication is not considered.With authentication, the primary server and secondary server can cooperatively perform the equality test on ciphertexts. In our PKE-AUT scheme, both equality test procedures for two servers should take4 more exponentiations in group G than Wu et al.’s scheme [15], since the generation of the second element c2 in the ciphertext of our PKE-AUT scheme requires more input parameters for achieving the equality test on the ciphertext by two servers. It can be seen that the two servers in both schemes do not have the same computing costs, since the secondary server needs to run two bilinear pairings in generating the result of the equality test on a pair of ciphertexts.The communication costs of our PKE-AUT scheme and Wu et al.’s scheme [15] are compared in Table 3. In our scheme, each ciphertext has three elements, while the ciphertext in Wu et al.’s scheme [15] contains five elements. Note that the message space of Wu et al.’s scheme [15] is cyclic group G. Thus, when both schemes have the same message space G, the ciphertext size of their scheme would be 2τG more than our PKE-AUT scheme. The authentication token was not encrypted for protecting privacy in Wu et al.’s scheme [15], which only contains one element in group G. For the equality test procedure by the primary server, the generated intermediate result Θ=c1,c1′,ω in our PKE-AUT scheme has three elements in group G, while Wu et al.’s scheme [15] requires six elements in G.Table 3
Comparison of communication costs.
Our PKE-AUT schemeWu et al.’s scheme [15]Ciphertext2τG+τm+logq5τG+logqAuthenticationτG+logqτGIntermediate result3τG6τGMoreover, we analyze the performance of our PKE-AUT scheme and compare with Wu et al.’s scheme [15] in the dual server model according to the experimental results of cryptographic operations in [29, 30]. In [29], the experiments were conducted on a platform with Windows 7 operating system, Intel I7-4700@3.40 GHz CPU and 4 GB memory. Moreover, the MIRACL Cryptographic SDK [31] was invoked with logp=512. The execution time of some cryptographic operations are summarized in Table 4.Table 4
Execution time of cryptographic operations.
OperationExecution time (milliseconds)Pair4.211Expo1.709Hash4.406The performance of all procedures of our PKE-AUT scheme and Wu et al.’s scheme [15] is depicted in Figures 3 and 4, respectively. The case where each procedure is executed once is considered for both schemes. It can be seen that the proposed PKE-AUT scheme is more efficient than Wu et al.’s scheme [15] in encrypting a message. Although the decryption and equality test procedures take more time than Wu et al.’s scheme [15], our PKE-AUT scheme supports strict and symmetric authorization for equality test on ciphertexts. Thus, to achieve this, the public keys of two servers have to be used in generating the ciphertext in our PKE-AUT scheme, which makes the efficiency of decryption and equality test reduced slightly.Figure 3
Performance of each procedure in our PKE-AUT scheme.Figure 4
Performance of each procedure in Wu et al.’s scheme [15].


## 6. Conclusion

To address the issues of privacy protection and resistance of keyword guessing attacks on outsourced ciphertexts in clouds, this paper presented a public key encryption scheme supporting the authorized equality test on ciphertexts in the dual server mode (PKE-AUT). User data can be only stored at the primary server to save local storage costs. With the same authentication, the primary server and secondary server can jointly carry out the equality test on ciphertexts of the corresponding users. The mechanism of the equality test on ciphertexts can be run in a multiuser setting, such that after being authorized, the two servers can compare the ciphertexts of these multiple users. Security analysis showed that the proposed PKE-AUT scheme guarantees the privacy of outsourced ciphertexts against two servers, as well as the privacy of authentication. Performance analysis and comparison demonstrated the practicality of the proposed PKE-AUT scheme.



---

*Source: 4462134-2022-01-20.xml*