# Group Public Key Encryption with Equality Test under Standard Model

Authors: Xiangtian Deng; Haifeng Qian
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Group public key encryption with equality test (G-PKEET) scheme supports group granularity authorization on the equality test. An authorized proxy is able to check whether two ciphertexts belonging to the same group are encrypted from identical plaintext without decrypting them. However, in indistinguishability-based security notion, current existing PKEET and G-PKEET schemes do not allow adversary to invoke equality test as a service. In contrast, under practical circumstance, an adversary is probably able to exploit the equality test service offered by proxy to decipher a ciphertext, leading to unexpected and unwanted privacy leakage. In this paper, we propose a security definition that includes the abovementioned adversary ability. Through extending the functionality of current G-PKEET scheme, we design a concrete scheme that satisfies our new security definition. Furthermore, our G-PKEET scheme is the first G-PKEET scheme whose security properties can be proved under the standard model.


---

## Body

## 1. Introduction

Public key encryption with equality test (PKEET) is originally proposed by Yang et al. [1]. In PKEET scheme, users are able to check the equality of a pair of ciphertext without decrypting them, i.e., whether plaintexts decrypted from the ciphertext pair are equal. The tested ciphertext pairs are unnecessary to be encrypted by same public key. However, in PKEET scheme proposed by Yang et al., any user is allowed to perform equality test on arbitrary ciphertexts. In order for private key holders to manage access to equality test on corresponding ciphertexts, Tang proposes PKEET scheme in [2, 3], which introduces the concepts of “proxy” and “token.” Tokens are generated by private key holders, and proxy can correctly perform equality test on ciphertext pairs only after obtaining corresponding tokens. This concept has been applied in a series of subsequent related works [4–7].In common PKEET scheme, proxy has to request authorization from a user for executing equality test on ciphertexts encrypted by the user’s public key. This authorization mode is referred to in [8] as “user granularity authorization.”To cope with different application scenarios, the concept “group granularity authorization” has been put forward [8, 9]. Under this authorization mode, a normal user can generate group ciphertexts with the permission of group administrator. Meanwhile, token issued by group administrator can be and only be used to conduct equality test on all group ciphertexts within the same group, thus helping to reduce the computational, storage, and communication overheads caused by token issuance. However, current PKEET definitions are not suitable for group granularity authorization in terms of efficiency [8]. Group public key encryption with equality test (G-PKEET) scheme is firstly proposed by Ling et al. [7], which is the first PKEET scheme supporting group granularity authorization. Besides the concepts of “proxy” and “token,” a trustable “group administrator” role is additionally introduced in G-PKEET, in charge of issuing tokens. Each normal user, holding his own key pair, may apply to a “group administrator” for joining his group. With the permission of administrator, user is able to generate group ciphertexts. Similar to the definition of PKE, a group ciphertext can only be successfully decrypted by corresponding private key holder. In order to conduct equality test on group ciphertexts within same group, a proxy only needs to submit an authorization request to the group administrator.We remind readers that the primary feature of another existing definition Group Encryption (GE) [10] is allowing encryptor to conceal a recipient (decryptor) within a group of legitimate receivers. In G-PKEET, the entity of a group is a ciphertext. Detailedly speaking, users generate key pairs on their own and are able to join multiple group with same key pair. The group public key used when generating ciphertext decides which group the ciphertext belongs to, while proxy can only perform equality test on ciphertexts within the same group. In short, GE achieves anonymization of decryptor identity, while G-PKEET aims to save the overhead of communication and storage in aspect of token issuance. The two definitions are similar in naming but far various from each other in functionality.In terms of security, several recently proposed PKEET schemes [4–6] have proved their security properties under standard model. Their security properties are more robust than those relying on random oracle model [11]. Scheme under random oracle model does not always guarantee its security when random oracle is instantiated with real hash function [12]. No G-PKEET scheme has proved to be secure under standard model up till now.Existing works generally classify potential adversaries into two major categories relying on whether adversary is authorized to perform equality test on target user’s ciphertext, i.e., obtaining corresponding token.However, with respect to definition on adversary abilities, almost none of the existing schemes consider the situation where unauthorized adversary can restrictively invoke a proxy able to perform equality test on target user’s ciphertext; i.e., he cannot directly perform equality test on target ciphertext. This gives rise to potential risk that unauthorized adversary exploits this service to arouse unwanted information leakage.On the other hand, PKEET and G-PKEET schemes proposed in related works commonly embed plaintext and corresponding hash values into different components of ciphertext, aiming to make the ciphertext structurally capable of equality test. Thus we propose the definition of “improper ciphertext,” standing for ciphertexts whose embedded plaintext, hash values, and other components are noncorrespondent. These ciphertexts may be submitted by malicious encryptor in order to interfere the correctness of equality test. Once such interference attack is launched in existing G-PKEET scheme, authorized proxy and private key holder have to interact to judge the properness of ciphertext, leading to communication overhead.We use the following example to demonstrate our motivation more concretely: Consider a group based medic social network scenario (G-MHSN) in Figure1.Figure 1
G-MHSN scenario of G-PKEET.The medical cloud server (MS) is responsible for storing encrypted patient information. A medical worker uses patient’s public key to generate ciphertexts of patient information. A Service Provider (SP) owning computation power provides patient information equality test service for medical workers.“Groups” represent different medical databases or different partitions of single medical database, depending on demanding of medical workers. The “group” mechanism allows SPs to request authorization only once to check the equality of ciphertexts belonging to the same group, regardless of whose public key these ciphertexts are encrypted by.The group administrator (GA) is responsible for managing the group, including granting users to generate group ciphertexts and granting SPs to perform equality test on any pair of ciphertexts within the group.Assume patient information of patient A and patient B needs to be tested in form of ciphertext. The workflow of this scenario is as follows: Firstly, the patient information of A and B is encrypted using their respective public keys and group public keys. Both ciphertexts need to belong to the same group. Secondly, the service provider SP requests permission from the group administrator GA to enable itself to perform equality test within this group. Finally, medical worker can invoke SP to perform equality test on patient information of user A and user B.Furthermore, we use the above scenario to describe the security concerns that existing G-PKEET solution can not address.(i)
Service provider (SP): the SP should ensure that patient information equality test service it provides to medic workers does not reveal information other than equality test result.(ii)
Patients: Patients should have the ability to check properness of patient information ciphertext to prevent equality test service from misjudging their ciphertexts.In coping with the security concerns mentioned above, we make extensions on existing G-PKEET definition. The contribution of our proposed scheme is listed as follows:(1)
Our G-PKEET scheme is the first G-PKEET scheme proved to be secure under standard model. Compared with existing G-PKEET scheme, our scheme is no longer dependent on random oracle to prove its security property. Simultaneously, our scheme is acceptable in aspect of communication and storage overhead.(2)
In response to the status that current G-PKEET scheme is incapable of permitting private key holder to verify whether embedded message value and hash value are corresponded, we modify the definition of decryption algorithm. The new definition allows private key holder to check whether components are corresponded and output⊥ in case of incorrespondence. This modification allows private key holder to detect and remove improper ciphertext more efficiently, ensuring correctness of equality test service. Implicitly, we demonstrate that the modification itself would not compromise security properties of our scheme; i.e., adversary cannot exploit this function to arouse information leakage.(3)
Our scheme strengthens the capability of unauthorized adversary, allowing adversaries of this type to invoke equality test oracle. Correspondingly, we prove our scheme to be secure under newly defined security property. This modification would guarantee that the unwanted leakage of plaintext information will not occur even when equality test service would be provided publicly.


## 2. Related Works

### 2.1. G-PKEET

The G-PKEET scheme is first proposed by Ling et al. [7], which introduces a trustable “group administrator” role in charge of a group secret key. Each user, holding their own public/private key pair, can apply to a “group administrator” for joining his group, i.e., obtaining a group public key. With the use of group public key, corresponding user private key, and the other user’s public key, a group ciphertext is generated, able to be decrypted by private key of the other user. In order to test the equality of two group ciphertexts belonging to the same group, a proxy only needs to apply to “group administrator” for a group trapdoor.Furthermore, this scheme is also claimed to be resistant to OMRA attack (offline message recovery attack) proposed by Tang in [13]. In OMRA attack, an attacker authorized by token distributor, who knows the distribution of message space in advance, can recover plaintext from target ciphertext through repeatedly performing equality test between target ciphertext and ciphertext encrypted from guessing message.Ling et al. show that their scheme is resistant to OMRA attack through avoiding group ciphertexts from being generated publicly. This technique is similar to which used by Wu et al. in [14]. Detailedly speaking, only users who are granted with group public keys by the group administrator can generate a group ciphertext. Thus an OMRA attacker can not organize an attack unless he colludes with the group administrator or any user in the group.


### 2.2. PKEET under the Standard Model

Zhang et al. put forward a PKEET scheme in standard model [4], which is based on a specific IND-CCA2 public key encryption scheme [15]. Lee et al. also realize a PKEET scheme in standard model [6]. Their solution is generic, using HIBE and one-time signature as building blocks. Compared with Zhang’s scheme, Lee’s scheme gets rid of relying on specific number theoretic assumptions, at the cost of computational efficiency and dependency on strong cryptography primitive. Recently, Zeng et al. propose a generic PKEET scheme [5] in standard model based on hash proof system [16].


### 2.3. Other Related Works

In terms of refining the security performance of PKEET, Lin et al. put forward PKEET supporting flexible designated authorization (PKEET-FDA) [17]; PKEET-FDA requires proxy to use its secret key together with token to perform equality test, thus preventing attacker from testing ciphertexts with stolen token. Flexibility is embodied in allowing user to authorize multiple testers by once instead of generating specific token for each tester. Zhao and Zeng include access to equality test service within the scope of adversary capabilities and propose a PKEET scheme with corresponding security definition [18]. In aspect of authorization granularity, Lin et al. present PKEET supporting partial authentication (PKEET-PA) [19], where user can adaptively authorize the test right of any number of ciphertexts to a tester by providing constant-size token to tester. With regard to improvement on computation efficiency, several works have explored designing PKEET scheme without relying on bilinear pairing [20, 21].


## 2.1. G-PKEET

The G-PKEET scheme is first proposed by Ling et al. [7], which introduces a trustable “group administrator” role in charge of a group secret key. Each user, holding their own public/private key pair, can apply to a “group administrator” for joining his group, i.e., obtaining a group public key. With the use of group public key, corresponding user private key, and the other user’s public key, a group ciphertext is generated, able to be decrypted by private key of the other user. In order to test the equality of two group ciphertexts belonging to the same group, a proxy only needs to apply to “group administrator” for a group trapdoor.Furthermore, this scheme is also claimed to be resistant to OMRA attack (offline message recovery attack) proposed by Tang in [13]. In OMRA attack, an attacker authorized by token distributor, who knows the distribution of message space in advance, can recover plaintext from target ciphertext through repeatedly performing equality test between target ciphertext and ciphertext encrypted from guessing message.Ling et al. show that their scheme is resistant to OMRA attack through avoiding group ciphertexts from being generated publicly. This technique is similar to which used by Wu et al. in [14]. Detailedly speaking, only users who are granted with group public keys by the group administrator can generate a group ciphertext. Thus an OMRA attacker can not organize an attack unless he colludes with the group administrator or any user in the group.


## 2.2. PKEET under the Standard Model

Zhang et al. put forward a PKEET scheme in standard model [4], which is based on a specific IND-CCA2 public key encryption scheme [15]. Lee et al. also realize a PKEET scheme in standard model [6]. Their solution is generic, using HIBE and one-time signature as building blocks. Compared with Zhang’s scheme, Lee’s scheme gets rid of relying on specific number theoretic assumptions, at the cost of computational efficiency and dependency on strong cryptography primitive. Recently, Zeng et al. propose a generic PKEET scheme [5] in standard model based on hash proof system [16].


## 2.3. Other Related Works

In terms of refining the security performance of PKEET, Lin et al. put forward PKEET supporting flexible designated authorization (PKEET-FDA) [17]; PKEET-FDA requires proxy to use its secret key together with token to perform equality test, thus preventing attacker from testing ciphertexts with stolen token. Flexibility is embodied in allowing user to authorize multiple testers by once instead of generating specific token for each tester. Zhao and Zeng include access to equality test service within the scope of adversary capabilities and propose a PKEET scheme with corresponding security definition [18]. In aspect of authorization granularity, Lin et al. present PKEET supporting partial authentication (PKEET-PA) [19], where user can adaptively authorize the test right of any number of ciphertexts to a tester by providing constant-size token to tester. With regard to improvement on computation efficiency, several works have explored designing PKEET scheme without relying on bilinear pairing [20, 21].


## 3. Preliminaries

Notation 1.
For a finite setS, we denote by s←rS the process of uniformly sampling a random element from S. We say that a function f is negligible if fλ≤1/pλ for all polynomials p⋅ and sufficiently large λs.


### 3.1. Cryptography Primitives

#### 3.1.1. Bilinear Map

LetG1=g1,G2=g2 and GT be cyclic groups of prime order p. A bilinear map e:G1×G2⟶GT satisfies the following properties:(i)
Bilinear: for anyg1∈G1, g2∈G2 and a,b∈Zp∗, eg1a,g2b=eg1,g2ab(ii)
Nondegenerate: for anyg1∈G1, g2∈G2, eg1,g2≠1GT, where 1GT is the generator of GT(iii)
Computable:e is efficiently computableAdditionally, in type-1 bilinear pairingG1=G2, in type-3 bilinear pairing G1≠G2, and there are no efficiently computable homomorphisms between G1,G2 [22].


### 3.2. Cryptography Assumptions

#### 3.2.1. Decisional Bilinear Diffie–Hellman (DBDH) Assumption

A game corresponding to DBDH assumption is constructed as follows, the roles included in which are challengerC and adversary A. We define Gen as a function which takes a security parameter λ as input and outputs a tuple p,G,GT,e,g where G,GT are multiplicative cyclic groups of order p, e is a bilinear map from G×G to GT, and g is a generator of G.FirstlyC obtains a tuple p,G,GT,e,g by executing Genλ. C then randomly selects elements a,b,c from Zp and β from 0,1. If β=1, C randomly selects an element in GT as T; otherwise it sets T=eg,gabc.C passes the challenge tuple g,ga,gb,gc,T to A. A then outputs a guess β′. We define an advantage of A in the above game as Prβ=β′−1/2.The DBDH assumption inG,GT claims that, for any PPT adversary, its advantage in the above game is negligible in the security parameter λ.


#### 3.2.2. External Decisional Diffie–Hellman (XDH) Assumption

This assumption is firstly defined in [23]. Consider the following game between challenger C and the adversary A: Let Gen be an algorithm that takes a security parameter λ as an input and outputs a tuple p,G1,G2,GT,e,g1 where G1,G2,GT are multiplicative cyclic groups of order p, e is a type-3 asymmetric bilinear map from G1×G2 to GT, and g1 is a generator of G1.FirstlyC obtains a tuple p,G1,G2,GT,e,g1 by executing Genλ. C then chooses random elements a,b from Zp and β from 0,1. If β=1, C chooses a random element in G1 to be T; otherwise T=g1ab.C passes the challenge tuple g1,g1a,g1b,T to A. A then outputs a guess β′. We define an advantage of A in the above game as Prβ=β′−1/2.The XDH assumption inG1 claims that, for any PPT adversary, its advantage in the above game is negligible in the security parameter λ.


## 3.1. Cryptography Primitives

### 3.1.1. Bilinear Map

LetG1=g1,G2=g2 and GT be cyclic groups of prime order p. A bilinear map e:G1×G2⟶GT satisfies the following properties:(i)
Bilinear: for anyg1∈G1, g2∈G2 and a,b∈Zp∗, eg1a,g2b=eg1,g2ab(ii)
Nondegenerate: for anyg1∈G1, g2∈G2, eg1,g2≠1GT, where 1GT is the generator of GT(iii)
Computable:e is efficiently computableAdditionally, in type-1 bilinear pairingG1=G2, in type-3 bilinear pairing G1≠G2, and there are no efficiently computable homomorphisms between G1,G2 [22].


## 3.1.1. Bilinear Map

LetG1=g1,G2=g2 and GT be cyclic groups of prime order p. A bilinear map e:G1×G2⟶GT satisfies the following properties:(i)
Bilinear: for anyg1∈G1, g2∈G2 and a,b∈Zp∗, eg1a,g2b=eg1,g2ab(ii)
Nondegenerate: for anyg1∈G1, g2∈G2, eg1,g2≠1GT, where 1GT is the generator of GT(iii)
Computable:e is efficiently computableAdditionally, in type-1 bilinear pairingG1=G2, in type-3 bilinear pairing G1≠G2, and there are no efficiently computable homomorphisms between G1,G2 [22].


## 3.2. Cryptography Assumptions

### 3.2.1. Decisional Bilinear Diffie–Hellman (DBDH) Assumption

A game corresponding to DBDH assumption is constructed as follows, the roles included in which are challengerC and adversary A. We define Gen as a function which takes a security parameter λ as input and outputs a tuple p,G,GT,e,g where G,GT are multiplicative cyclic groups of order p, e is a bilinear map from G×G to GT, and g is a generator of G.FirstlyC obtains a tuple p,G,GT,e,g by executing Genλ. C then randomly selects elements a,b,c from Zp and β from 0,1. If β=1, C randomly selects an element in GT as T; otherwise it sets T=eg,gabc.C passes the challenge tuple g,ga,gb,gc,T to A. A then outputs a guess β′. We define an advantage of A in the above game as Prβ=β′−1/2.The DBDH assumption inG,GT claims that, for any PPT adversary, its advantage in the above game is negligible in the security parameter λ.


### 3.2.2. External Decisional Diffie–Hellman (XDH) Assumption

This assumption is firstly defined in [23]. Consider the following game between challenger C and the adversary A: Let Gen be an algorithm that takes a security parameter λ as an input and outputs a tuple p,G1,G2,GT,e,g1 where G1,G2,GT are multiplicative cyclic groups of order p, e is a type-3 asymmetric bilinear map from G1×G2 to GT, and g1 is a generator of G1.FirstlyC obtains a tuple p,G1,G2,GT,e,g1 by executing Genλ. C then chooses random elements a,b from Zp and β from 0,1. If β=1, C chooses a random element in G1 to be T; otherwise T=g1ab.C passes the challenge tuple g1,g1a,g1b,T to A. A then outputs a guess β′. We define an advantage of A in the above game as Prβ=β′−1/2.The XDH assumption inG1 claims that, for any PPT adversary, its advantage in the above game is negligible in the security parameter λ.


## 3.2.1. Decisional Bilinear Diffie–Hellman (DBDH) Assumption

A game corresponding to DBDH assumption is constructed as follows, the roles included in which are challengerC and adversary A. We define Gen as a function which takes a security parameter λ as input and outputs a tuple p,G,GT,e,g where G,GT are multiplicative cyclic groups of order p, e is a bilinear map from G×G to GT, and g is a generator of G.FirstlyC obtains a tuple p,G,GT,e,g by executing Genλ. C then randomly selects elements a,b,c from Zp and β from 0,1. If β=1, C randomly selects an element in GT as T; otherwise it sets T=eg,gabc.C passes the challenge tuple g,ga,gb,gc,T to A. A then outputs a guess β′. We define an advantage of A in the above game as Prβ=β′−1/2.The DBDH assumption inG,GT claims that, for any PPT adversary, its advantage in the above game is negligible in the security parameter λ.


## 3.2.2. External Decisional Diffie–Hellman (XDH) Assumption

This assumption is firstly defined in [23]. Consider the following game between challenger C and the adversary A: Let Gen be an algorithm that takes a security parameter λ as an input and outputs a tuple p,G1,G2,GT,e,g1 where G1,G2,GT are multiplicative cyclic groups of order p, e is a type-3 asymmetric bilinear map from G1×G2 to GT, and g1 is a generator of G1.FirstlyC obtains a tuple p,G1,G2,GT,e,g1 by executing Genλ. C then chooses random elements a,b from Zp and β from 0,1. If β=1, C chooses a random element in G1 to be T; otherwise T=g1ab.C passes the challenge tuple g1,g1a,g1b,T to A. A then outputs a guess β′. We define an advantage of A in the above game as Prβ=β′−1/2.The XDH assumption inG1 claims that, for any PPT adversary, its advantage in the above game is negligible in the security parameter λ.


## 4. Definition

### 4.1. Definition of G-PKEET

To help understand the relationship between algorithms and entities of G-PKEET, we illustrate execution entities of various algorithms and the interaction specification by Figure2.Figure 2
Interaction specification and function executor entity of G-PKEET.We remind readers that all algorithms of our G-PKEET scheme do not require multiround interaction. Thus we divide involved parties simply into executor and invoker. Invoker provides part of parameters needed for executing function to executor. Then executor, holding remaining secret parameters, executes the function and returns the result to invoker.We describe the definition of G-PKEET functions as follows:(i)
Setup (λ): this nondeterministic function takes a security parameter λ as input and returns public system parameter PP.(ii)
KeyGenuser (PP):this nondeterministic function produces a public/private key pair pk,sk for a normal user.(iii)
KeyGengroup (PP):this nondeterministic function produces a group secret key gsk for a group administrator.(iv)
Joingsk,pki: this nondeterministic function permits a user holding user key pki to join a specific group holding group secret key gsk. If executed properly, this function will generate and output a group public key gpki for user Ui.(v)
Encgpki,ski,gpkj,pkj,m: this nondeterministic function takes in a group public key, its corresponding private key, another group public key, its corresponding public key, and a plaintext m to generate a ciphertext, where indices i,j, respectively, refer to encryptor and decryptor index.(vi)
Decgpki,gpkj,skj,Ci,j: this deterministic function takes in a ciphertext Ci,j, group public key gpki of encryptor Ui and group public key gpkj, and private key skj of decryptor Uj to recover plaintext from ciphertext. The function may output ⊥ representing rejection under certain circumstances.(vii)
Verifygpki,gpkj,skj,Ci,j: this deterministic function takes in the same parameters as function Dec. Verify outputs ⊥ if and only if Dec taking in the same parameters outputs ⊥; otherwise Verify outputs 1 standing for the passing of verification.One key purpose of Verify algorithm is allowing proxy to confirm to private key holder whether ciphertext is proper. Thus it needs to differ from decryption algorithm for not outputting plaintext as a result. On the other hand, Verify helps private key holder to detect improper ciphertext on his own and takes further reaction, such as removing them from the cloud server:(i)
Autgsk: this function generates a group trapdoor tuple gtd used for equality test.(ii)
TestCi,j,Ci′,j′,pkj,pkj′,gpkj,gpkj′,gtd: this deterministic function takes in two ciphertexts Ci,j,Ci′,j′ belonging to the same group, corresponding group trapdoor gtd, group public key, and public key of two decryptors as input. It returns either 0,1 representing result of equality test or ⊥ representing rejection under certain circumstances.Optionally, proxy in advance queries private key holders withVerifygpki,gpkj,skj,Ci,jand Verifygpki′,gpkj′,skj′,Ci′,j′. In such cases, proxy may output ⊥, indicating that the equality test is ceased due to failure on passing ciphertext verification.


#### 4.1.1. Scheme Correctness

Leti,j,k,k′ be distinct user indexes; gsk be group secret key generated by KeyGengroup; pki,ski,pkj,skj,pkk,skk,pkk′,skk′ be corresponding user key pairs; gpki,gpkj,gpkk,gpkk′ be group public keys generated, respectively, by Joingsk,pki,Joingsk,pkj,Joingsk,pkk,Joingsk,pkk′; gtd be group trapdoor generated by Autgsk.Given the aforementioned symbols, G-PKEET scheme achieves correctness if all following statements hold:(1)
Decgpki,gpkj,skj,Encgpki,ski,gpkj,pkj,m=m.(2)
In the following procedure,Test outputs 1 when m=m′; otherwise, it outputs 1 with negligible probability:(1)Ci,k=Encgpki,ski,gpkk,pkk,m,Cj,k′=Encgpkj,skj,gpkk′,pkk′,m′,TestCi,k,Cj,k′,pkk,pkk′,gpkk,gpkk′,gtd.


### 4.2. Security Model

First, we make some foundational assumptions related to adversary’s behavior pattern for simplicity similarly as in [3]:(1)
All users honestly generate their public/private keys(2)
There is no overlap between the user set and the proxy setDue to the functionality of G-PKEET, an adversary who obtains a group token can trivially break the indistinguishability-based security notion of corresponding ciphertexts. Thus we introduce definition on two types of adversary, in the view of an arbitrary userUt and a group administrator GA:(1)
Type-1 adversary: given a target ciphertext, the purpose of type-1 adversary is to guess the plaintext decrypted from it. The adversary has no access to corresponding private key, but he is able to invoke function Dec with this private key as one parameter (in a black-box fashion). Restrictedly, adversary is not allowed to invoke this function to decrypt the target ciphertext. In addition, type-1 adversary obtains the token required to check equality of the target ciphertext.Dect.In practical scenario shown by Figure2, type-1 adversary can be regarded as an adversary stronger than authorized proxy due to its ability to invoke the Dec function black box mentioned above.(2)
Type-2 adversary: given a target ciphertext, the purpose of type-2 adversary is to distinguish which plaintext a target ciphertext is decrypted from. The adversary is assured that target ciphertext is encrypted from either of two plaintexts designated by him. In contrast to type-1 adversary, the adversary has no access to the corresponding token required for equality test on target ciphertext. However, he is able to invoke a specificTest function with this token as a parameter (in a black-box fashion). Similar to the restriction imposed on type-1 adversary, type-2 adversary is not allowed to invoke Test function to check equality of the target ciphertext.In practical scenario shown by Figure2, a type-2 adversary can be regarded as adversary stronger than service user due to its ability to invoke the Dec function black box mentioned above and designate target ciphertext. In existing G-PKEET scheme, type-2 adversary can however be only regarded as an adversary stronger than normal user.As for adversary of different types, corresponding security property is designed as follows (in the view ofUt):(i)
Type-1 adversary: OW-CCA. A type-1 adversary can not recover the plaintext from a ciphertext, even if it is allowed to query the decryption oracle, verification oracle with specific restrictions. This is the best achievable security guarantee considering the equality test functionality.(ii)
Type-2 adversary: IND-CCA. A type-2 adversary is not allowed to obtain equality test token fromGA. But he is allowed to access the decryption oracle, verification oracle, and test oracle with specific restrictions and enables choosing the challenge plaintext pair.We remind readers that, for type-2 adversaries, IND-CCA2 security to be proved in our paper covers OW-CCA2 security. Specifically, the game definition of OW-CCA2 differs from that of IND-CCA2 only in how the challenge ciphertext is generated. Moreover, the proof of OW-CCA2 security can be reduced to IND-CCA2 security.


### 4.3. Security Properties

Definition 1.
A G-PKEET cryptosystem achieves OW-CCA2 security against a type-1 adversary, if, for1≤t≤N, any PPT adversary has only a negligible advantage in the attack game shown in Figure 3, where the advantage is defined to be Prmt′=mt.
We notify our readers that the definition of our scheme is weakened compared to that in the original G-PKEET definition of [7] in aspect of restriction imposed on decryption oracle in Query phase 2. Detailedly, in Ling et al.’s scheme, decryption oracle refuses to execute Dec algorithm only when challenge ciphertext and corresponding encryptor index and corresponding decryptor index are requested together. In our scheme, oracle refuses to execute Dec algorithm when challenge ciphertext and corresponding decryptor index are requested together, no matter what encryptor index is.Figure 3
OW-CCA2 security game.Definition 2.
A G-PKEET cryptosystem achieves IND-CCA2 security against a type-2 adversary, if, for1≤t≤N, any polynomial-time adversary has only a negligible advantage in the attack game shown in Figure 4, where the advantage is defined to be Prb′=b−1/2
We notify our readers that the definition of our scheme is weakened compared to that in the original G-PKEET definition of [7] in aspect of restriction imposed on decryption oracle in Query phase 2 for the reason mentioned above. Corresponding to Oracletest which has not been included in related works, a new precondition is added: Target user and proxy should interact honestly in Verify procedure when proxy intends to conduct equality test on target user’s ciphertext.Figure 4
IND-CCA2 security game.


## 4.1. Definition of G-PKEET

To help understand the relationship between algorithms and entities of G-PKEET, we illustrate execution entities of various algorithms and the interaction specification by Figure2.Figure 2
Interaction specification and function executor entity of G-PKEET.We remind readers that all algorithms of our G-PKEET scheme do not require multiround interaction. Thus we divide involved parties simply into executor and invoker. Invoker provides part of parameters needed for executing function to executor. Then executor, holding remaining secret parameters, executes the function and returns the result to invoker.We describe the definition of G-PKEET functions as follows:(i)
Setup (λ): this nondeterministic function takes a security parameter λ as input and returns public system parameter PP.(ii)
KeyGenuser (PP):this nondeterministic function produces a public/private key pair pk,sk for a normal user.(iii)
KeyGengroup (PP):this nondeterministic function produces a group secret key gsk for a group administrator.(iv)
Joingsk,pki: this nondeterministic function permits a user holding user key pki to join a specific group holding group secret key gsk. If executed properly, this function will generate and output a group public key gpki for user Ui.(v)
Encgpki,ski,gpkj,pkj,m: this nondeterministic function takes in a group public key, its corresponding private key, another group public key, its corresponding public key, and a plaintext m to generate a ciphertext, where indices i,j, respectively, refer to encryptor and decryptor index.(vi)
Decgpki,gpkj,skj,Ci,j: this deterministic function takes in a ciphertext Ci,j, group public key gpki of encryptor Ui and group public key gpkj, and private key skj of decryptor Uj to recover plaintext from ciphertext. The function may output ⊥ representing rejection under certain circumstances.(vii)
Verifygpki,gpkj,skj,Ci,j: this deterministic function takes in the same parameters as function Dec. Verify outputs ⊥ if and only if Dec taking in the same parameters outputs ⊥; otherwise Verify outputs 1 standing for the passing of verification.One key purpose of Verify algorithm is allowing proxy to confirm to private key holder whether ciphertext is proper. Thus it needs to differ from decryption algorithm for not outputting plaintext as a result. On the other hand, Verify helps private key holder to detect improper ciphertext on his own and takes further reaction, such as removing them from the cloud server:(i)
Autgsk: this function generates a group trapdoor tuple gtd used for equality test.(ii)
TestCi,j,Ci′,j′,pkj,pkj′,gpkj,gpkj′,gtd: this deterministic function takes in two ciphertexts Ci,j,Ci′,j′ belonging to the same group, corresponding group trapdoor gtd, group public key, and public key of two decryptors as input. It returns either 0,1 representing result of equality test or ⊥ representing rejection under certain circumstances.Optionally, proxy in advance queries private key holders withVerifygpki,gpkj,skj,Ci,jand Verifygpki′,gpkj′,skj′,Ci′,j′. In such cases, proxy may output ⊥, indicating that the equality test is ceased due to failure on passing ciphertext verification.


### 4.1.1. Scheme Correctness

Leti,j,k,k′ be distinct user indexes; gsk be group secret key generated by KeyGengroup; pki,ski,pkj,skj,pkk,skk,pkk′,skk′ be corresponding user key pairs; gpki,gpkj,gpkk,gpkk′ be group public keys generated, respectively, by Joingsk,pki,Joingsk,pkj,Joingsk,pkk,Joingsk,pkk′; gtd be group trapdoor generated by Autgsk.Given the aforementioned symbols, G-PKEET scheme achieves correctness if all following statements hold:(1)
Decgpki,gpkj,skj,Encgpki,ski,gpkj,pkj,m=m.(2)
In the following procedure,Test outputs 1 when m=m′; otherwise, it outputs 1 with negligible probability:(1)Ci,k=Encgpki,ski,gpkk,pkk,m,Cj,k′=Encgpkj,skj,gpkk′,pkk′,m′,TestCi,k,Cj,k′,pkk,pkk′,gpkk,gpkk′,gtd.


## 4.1.1. Scheme Correctness

Leti,j,k,k′ be distinct user indexes; gsk be group secret key generated by KeyGengroup; pki,ski,pkj,skj,pkk,skk,pkk′,skk′ be corresponding user key pairs; gpki,gpkj,gpkk,gpkk′ be group public keys generated, respectively, by Joingsk,pki,Joingsk,pkj,Joingsk,pkk,Joingsk,pkk′; gtd be group trapdoor generated by Autgsk.Given the aforementioned symbols, G-PKEET scheme achieves correctness if all following statements hold:(1)
Decgpki,gpkj,skj,Encgpki,ski,gpkj,pkj,m=m.(2)
In the following procedure,Test outputs 1 when m=m′; otherwise, it outputs 1 with negligible probability:(1)Ci,k=Encgpki,ski,gpkk,pkk,m,Cj,k′=Encgpkj,skj,gpkk′,pkk′,m′,TestCi,k,Cj,k′,pkk,pkk′,gpkk,gpkk′,gtd.


## 4.2. Security Model

First, we make some foundational assumptions related to adversary’s behavior pattern for simplicity similarly as in [3]:(1)
All users honestly generate their public/private keys(2)
There is no overlap between the user set and the proxy setDue to the functionality of G-PKEET, an adversary who obtains a group token can trivially break the indistinguishability-based security notion of corresponding ciphertexts. Thus we introduce definition on two types of adversary, in the view of an arbitrary userUt and a group administrator GA:(1)
Type-1 adversary: given a target ciphertext, the purpose of type-1 adversary is to guess the plaintext decrypted from it. The adversary has no access to corresponding private key, but he is able to invoke function Dec with this private key as one parameter (in a black-box fashion). Restrictedly, adversary is not allowed to invoke this function to decrypt the target ciphertext. In addition, type-1 adversary obtains the token required to check equality of the target ciphertext.Dect.In practical scenario shown by Figure2, type-1 adversary can be regarded as an adversary stronger than authorized proxy due to its ability to invoke the Dec function black box mentioned above.(2)
Type-2 adversary: given a target ciphertext, the purpose of type-2 adversary is to distinguish which plaintext a target ciphertext is decrypted from. The adversary is assured that target ciphertext is encrypted from either of two plaintexts designated by him. In contrast to type-1 adversary, the adversary has no access to the corresponding token required for equality test on target ciphertext. However, he is able to invoke a specificTest function with this token as a parameter (in a black-box fashion). Similar to the restriction imposed on type-1 adversary, type-2 adversary is not allowed to invoke Test function to check equality of the target ciphertext.In practical scenario shown by Figure2, a type-2 adversary can be regarded as adversary stronger than service user due to its ability to invoke the Dec function black box mentioned above and designate target ciphertext. In existing G-PKEET scheme, type-2 adversary can however be only regarded as an adversary stronger than normal user.As for adversary of different types, corresponding security property is designed as follows (in the view ofUt):(i)
Type-1 adversary: OW-CCA. A type-1 adversary can not recover the plaintext from a ciphertext, even if it is allowed to query the decryption oracle, verification oracle with specific restrictions. This is the best achievable security guarantee considering the equality test functionality.(ii)
Type-2 adversary: IND-CCA. A type-2 adversary is not allowed to obtain equality test token fromGA. But he is allowed to access the decryption oracle, verification oracle, and test oracle with specific restrictions and enables choosing the challenge plaintext pair.We remind readers that, for type-2 adversaries, IND-CCA2 security to be proved in our paper covers OW-CCA2 security. Specifically, the game definition of OW-CCA2 differs from that of IND-CCA2 only in how the challenge ciphertext is generated. Moreover, the proof of OW-CCA2 security can be reduced to IND-CCA2 security.


## 4.3. Security Properties

Definition 1.
A G-PKEET cryptosystem achieves OW-CCA2 security against a type-1 adversary, if, for1≤t≤N, any PPT adversary has only a negligible advantage in the attack game shown in Figure 3, where the advantage is defined to be Prmt′=mt.
We notify our readers that the definition of our scheme is weakened compared to that in the original G-PKEET definition of [7] in aspect of restriction imposed on decryption oracle in Query phase 2. Detailedly, in Ling et al.’s scheme, decryption oracle refuses to execute Dec algorithm only when challenge ciphertext and corresponding encryptor index and corresponding decryptor index are requested together. In our scheme, oracle refuses to execute Dec algorithm when challenge ciphertext and corresponding decryptor index are requested together, no matter what encryptor index is.Figure 3
OW-CCA2 security game.Definition 2.
A G-PKEET cryptosystem achieves IND-CCA2 security against a type-2 adversary, if, for1≤t≤N, any polynomial-time adversary has only a negligible advantage in the attack game shown in Figure 4, where the advantage is defined to be Prb′=b−1/2
We notify our readers that the definition of our scheme is weakened compared to that in the original G-PKEET definition of [7] in aspect of restriction imposed on decryption oracle in Query phase 2 for the reason mentioned above. Corresponding to Oracletest which has not been included in related works, a new precondition is added: Target user and proxy should interact honestly in Verify procedure when proxy intends to conduct equality test on target user’s ciphertext.Figure 4
IND-CCA2 security game.


## 5. Construction

We remind our readers that building a generic G-PKEET scheme through combining an IND-CCA2 secure public key encryption with a OW-CCA2 secure equality test scheme may be able to satisfy G-PKEET definition in aspect of functionality. However, it is difficult to prove its security properties, because trivially combining two schemes together will allow adversary to break security game through decryption oracle.To be detailed, adversary modifies the ciphertext component of target ciphertext which supports equality test (specifically, the component embedded with plaintext hash value) and then submits new ciphertext to decryption oracle. According to game definition, the oracle would work normally by returning decrypted plaintext, leading to a successful attack. Our method adopts specific construction strategy, allowing components respectively embedded with plaintext and plaintext hash value to be bonded together. Consequently, in our scheme the ciphertext modified as mentioned above would be rejected by decryption oracle. It is worth noting that current general PKEET scheme (not G-PKEET) is built upon cryptographic primitives with specific properties, such as IBE and hash proof system. None of these related works adopts abstract PKEET definition to build a general PKEET scheme with special properties.We present our construction for G-PKEET scheme as follows:(i)
Setupλ: this algorithm outputs public parameter PP=p,q,G,GT,G˜,G˜T,g,g˜1,g˜2,e,e˜,H1,H2 as follows.(1)
G,GT are groups of prime order p, satisfying bilinear map e:G×G⟶GT. g is a random generator of G.(2)
G˜1,G˜2,G˜T are groups of prime order q corresponding to size of message space M, satisfying asymmetric bilinear map e˜:G˜1×G˜2⟶G˜T. g˜1,g˜2 are random generators of G˜1,G˜2.(3)
Hash functionsH1, H2, respectively, map M⟶G˜2; GT,G˜1,G˜1,G˜2,G,G˜1,G˜2,G˜2⟶Zp.(ii)
KeyGenuserPP: this algorithm randomly selects x,y,z,α←rZp;g1=gα;g2←rG;χ,ϕ←rZq. The structure of generated key pair is as follows:sk=χ,ϕ,g2α,x,y,z, pk=Z=eg1,g2,u,v,w,g˜1χ,g˜2χ,g˜1ϕ,g˜2ϕ, where u=gx,v=gy,w=gz.(iii)
KeyGengroupPP: this algorithm outputs gsk=θ1,θ2,θ3 where θ1,θ2,θ3←rZq.(iv)
Joingsk,pki: this algorithm outputs group public key for Ui in the following structure: gpki=g˜1χiθ1,g˜2χiθ1,g˜1θ2,g˜1θ3ϕi,g˜1θ3.(v)
Encryptgpki,ski,gpkj,pkj,m: the ciphertext is generated with structure as follows:(2)C1=mγ1γ2encodeZjs,C2=H1mχiγ1g˜1θ2γ2g˜1θ3ϕjγ1,C3=g˜1γ2,C4=g˜2γ1θ1χi,C5=gs,C6=r,C7=ujtvjrwjs,C8=g˜1γ1θ1χi,C9=g˜2γ1ϕj,C10=g˜2γ1,whereγ1,γ2←rZq;s←rZp, t=H2C1,C2,C3,C4,C5,C8,C9,C10. The encoding function and decoding function (to be mentioned later) map between 3-element tuple m,γ1,γ2 and GT. Assume that the message space M is Zq. The definitions of encode and decode are as follows:(1)
encodem,γ1,γ2: this function takes in plaintext element m and 2 group elements γ1,γ2∈Zq. It outputs a group element mγ1γ2encode∈GT.(2)
decodemγ1γ2encode: this function takes in a group element that belongs to GT. It outputs 3 group elements m,γ1,γ2∈Zq or ⊥ to indicate decoding failure.Both of these functions are public, satisfying equationdecodeencodem,γ1,γ2=m,γ1,γ2 for any m,γ1,γ2∈Zq. Note that these two functions impose an implicit restriction on Zp,Zq: the parameter should satisfy the inequality Zq3≤Zp, corresponding to the size of M×Zq×Zq and GT. We will omit subscripts “encode” and “decode” in subsequent formulas for conciseness:(i)
Decryptgpki,gpkj,skj,Ci,j: firstly, decryptor checks whether the following equation stands:(3)eC5,ujtvjC6wj=eC7,g,wheret=H2C1,C2,C3,C4,C5,C8,C9,C10.Decryptor outputs⊥ and aborts decryption procedure if aforementioned equation does not stand; otherwise he continues to execute the following steps:(4)m∗γ1∗γ2∗←C1eC5,g2,jα;,where componentg2,jα is taken from skj.Additionally, decryptor should judge whether the following equations stand:(5)g˜1γ2∗=C3;e˜C2g˜1θ3−ϕjγ1∗,g˜2e˜H1m∗γ1∗,g˜2χi=e˜g˜1θ2,g˜2γ2∗,whereg˜1θ2 is taken from group public key gpki.(6)g˜2θ1χiγ1∗=C4;g˜1θ1χiγ1∗=C8;g˜2γ1∗ϕj=C9;g˜2γ1∗=C10,whereg˜2θ1χi,g˜1θ1χi are taken from gpki.Decryptor returnsm∗ if the above equations stand; otherwise it outputs ⊥. We define ciphertexts which do not satisfy the equations above as “improper ciphertext.”(ii)
Verifygpki,gpkj,skj,Ci,j: this algorithm works the same as Dec except for returning 1 instead of m∗.In terms of concrete construction, private key holder has to check the correspondence of embedded plaintext and hash value by extracting plaintext value from ciphertexte˜g˜1θ3ϕi,C10=e˜g˜1θ3,C9 in advance. Thus the Verify algorithm unavoidably has similar procedure to Dec algorithm. How to allow Verify algorithm to check the properness of ciphertext without needing of extracting plaintext value is an issue that requires further discussion.(iii)
Autgsk: this algorithm returns tuple gtd=θ2,θ3.(iv)
TestCi,j,Ci′,j′,gtd,pki,pki′: firstly, tester needs to verify the correspondence of C9 and C10 through judging whether the following equation stands, where the component of gpki is used:e˜g˜1θ3ϕi,C10=e˜g˜1θ3,C9Similar process will be performed on the other ciphertextCi′,j′. Tester proceeds only when both equations stand; otherwise, it aborts by outputting ⊥.The algorithm outputs 1 if(7)e˜C2/C3θ2,C4′e˜C8′,C9θ3=e˜C2′/C3′θ2,C4e˜C8,C9′θ3.Otherwise, it outputs 0.Optionally, proxy in advance queries private key holders withVerifygpki,skj,Ci,j,Verifygpki′,skj′,Ci′,j′ in order for detecting whether ciphertexts to be tested are proper. In such cases, proxy outputs ⊥ when Verify procedure outputs ⊥, indicating that the equality test is ceased due to improper ciphertext.Theorem 1.
The proposed G-PKEET cryptosystem achieves correctness mentioned on Section 4.4.1.Proof.
As for the two stated statements, we correspondingly have the following:(i)
The first step of decryption judges whether(8)eC5,ujtvjC6wj=eC7,g,corresponds toegsj,ujtvjrwj=eujtvjrwjsj,g, where t=H2C1,C2,C3,C4,C5,C8,C9,C10.The second step of decryption, which calculates(9)m∗γ1∗γ2∗←C1eC5,g2,jα;,corresponds tomγ1γ2Zjs/egs,g2α.In the final step, we have(10)e˜C2g˜1−θ3ϕjγ1∗,g˜2e˜H1m∗γ1∗,g˜2χi=e˜H1m∗γ1∗χi,g˜2e˜g˜1γ2∗θ2,g˜2e˜H1m∗γ1∗χi,g˜2.It is obvious that all aforementioned steps stand if ciphertextc=Encgpki,ski,gpkj,pkj,m is correctly encrypted.(ii)
SetC,C′, respectively, as Encgpki,ski,gpkk,pkk,m and Encgpkj,skj,gpkk′,pkk′,m′. e˜C2/C3θ2,C4′/e˜C8′,C9θ3 can be reduced to(11)e˜H1m,g˜2χiχjγ1γ1′θ1.
Obviously,e˜C2′/C3′θ2,C4/e˜C8,C9′θ3 equals the above formula if m=m′; otherwise the equation stands only when a hash collision happens, the rate of which is negligible.


## 6. Security Analysis

### 6.1. OW-CCA2 Security

Theorem 2.
The proposed G-PKEET cryptosystem achieves OW-CCA2 property against a type-1 PPT adversary in the standard model based on the DBDH assumption onG.Proof.
The main idea of proof is to construct a series of games which are reduced from the original OW-CCA2 game. The adversary unconditionally gains negligible advantage in the last game and is unable to distinguish each pair of games adjacent in reduction.
To complete the proof formally, we need to construct a series of games [24]:Game 0. Challenger behaves the same as OW-CCA2 game in Figure 3.Game 1. In Game 1, challenger modifies component C1 challenge ciphertext Ct∗ consequently altered ciphertext is given as the following structure using corresponding components of pkt,gpki,ski of(12)Invalidmγ1γ2←rGT;C1∗=Invalidmγ1γ2Zts,C2=H1mχiγ1g˜1θ2γ2g˜1θ3ϕtγ1,C3=g˜1γ2,C4=g˜2γ1θ1χi,C5=gs,C6=r,C7=uttvtrwts,C8=g˜1γ1θ1χi,C9=g˜2γ1ϕt,C10=g˜2γ1.Superscriptt=H2C1,C2,C3,C4,C5,C8,C9,C10;s,r←rℤp;γ1,γ2←rℤq.
We will prove that there exists no PPT adversary able to distinguish Game 0 from Game 1 with nonnegligible advantage as long as DBDH assumption holds onG.


#### 6.1.1. Indistinguishability between Game 0 and Game 1

Briefly speaking, we construct an attackerB against DBDH assumption. He simultaneously invokes A as subprocedure, who attempts to distinguish between Game 0 and Game 1; i.e., B will play the role as challenger against A.Setup. After receiving a DBDH tuple g,ga,gb,gc,T, B replaces corresponding elements of public key pkt with DBDH challenge tuple elements as follows:(13)g1=ga,g2=gb,u=gbgyu,v=gbxvgyv,w=gbxwgyw,where yu,xv,yv,xw,yw←rZp. Other unmentioned elements contained in pkt are generated according to our scheme.Correspondingly, the private key tupleskt can be represented as skt=ϕt,χt,gab,x=b+yu,y=bxv+yv,w=bxw+yw, where x,y,z,gab is not known to B.Query Phase 1. (1) Decryption Oracle: when B is queried with user index t, firstly he checks whether the following statement stands:(14)eC5,utvC6w=eC7,g,where superscript t =  H1C1,C2,C3,C4,C5,C8,C9,C10.Ift+rxv+xd=0, B aborts the whole procedure and outputs a random bit to DBDH challenger. Since adversary has no idea of xv and xd, the probability for this type of event is query/p, where query is the times that adversary visits decryption oracle.Otherwise,B begins to extract plaintext from nonchallenge ciphertext, by firstly generating δ←rZp:(15)dC,1=g1−tyu+ryv+yw/t+rxv+xwutvrwδ,dC,2=g1−1t+rxv+xwgδ.Letδ˜=δ−a/t+rxv+xw. Then, we have(16)dC,1=g2autvrdδ˜,dC,2=gδ˜,mγ1γ2=C1edC,1,C5eC7,dC,2.Finally, it checks the consistency of plain text, hash message, and other components embedded in the ciphertext and outputs result of decryption:(17)DecryptionOraclect,sk∗,pk=⊥,if1m,otherwise.where (1) refers to the following statement:(18)g˜1ϕtθ3γ1C3θ2H1mχiγ1≠C2∨g˜2χiθ1γ1≠C4∨g˜1γ2≠C3∨g˜1χiθ1γ1≠C8∨g˜2γ1ϕt≠C9∨g˜2γ1≠C10.(2)
Encryption Oracle: challengerB works the same as mentioned in original G-PKEET scheme, since he knows the value of χt when being required to generate a ciphertext with encryptor index t.(3)
Verification Oracle: challengerB works in the same way as mentioned in Decryption Oracle except for following the description of Verify on output.Challenge. Challenger B selects m←rM and generates challenge ciphertext tuple in the following structure:(19)C1∗=mγ1γ2T,C2∗=H1mχiγ1g˜1θ2γ2g˜1θ3ϕtγ1,C3∗=g˜1γ2,C4∗=g˜2γ1θ1χi,C5∗=gc,C6∗=t∗+xwxv,C7∗=gct∗yu+C6∗yv+yw,C8∗=g˜1γ1θ1χi,C9=g˜2γ1ϕt,C10=g˜2γ1,where superscript t=H1C1,C2,C3,C4,C5,C8,C9,C10;γ1,γ2←rℤq.Query Phase 2. In this phase, decryption oracle is added with new restrictions: (1) challenge ciphertext cannot be requested together with decryptor index “t”; (2) when C≠C∗ and hash value H1C1,C2,C3,C4,C5,C8,C9,C10=t∗, challenger B aborts the whole game and outputs a random bit to DBDH challenger.Verification oracle works the same as mentioned in phase 1 except when being queried with challenge ciphertext andt as decryptor index. More detailedly, output is defined as follows:(20)OracleVerificationct,sk∗,pk=1,ifi=i∗⊥,otherwiseUnder actual circumstances, Verify might output 1 wheni≠i∗, consequently breaking the indistinguishability between Game 2 and actual circumstance. However, this situation happens when and only when a hash collision happens, the rate of which is negligible.Guess Phase. The adversary A outputs 0 or 1 representing the game he recognizes. B outputs the guess T=eg,gabc when A outputs 0, otherwise 1.Similar to [4], the probability that B aborts during the simulation is at most ADVCR+query/p, corresponding to the illustration in Query phases 1,2, where ADVCR refers to the probability of a hash collision.When B does not abort then A’s view is identical to its view in Game 0. Otherwise, his view is identical to that of Game 1. Uniform randomly generatedT=eg,gabc in Game 1 is statistically indistinguishable to Invalidmγ1γ2 when Invalidmγ1γ2∗ when T=eg,gZ. The reason is as follows:(21)T=eg,gzz←rZps.t.T=ega,gbz,m∗γ1∗γ2∗T=m∗γ1∗γ2∗ega,gbcega,gbz−c,=m∗γ1∗γ2∗⋅ega,gbz−cega,gbc,Invalidmγ1γ2∗⇔m∗γ1∗γ2∗⋅ega,gbz−c.Since adversaryA can be invoked to attack DBDH problem, his advantage can be expressed as(22)distinguish0,1≤ϵdbdh+PrAbort≤ϵdbdh+ADVCR+queryp.In Game 1,C1∗ in challenge ciphertext is irrelevant to plaintext message; therefore adversary ’s advantage can be reduced to the success rate of breaking hash function’s preimage properties. Eventually, the advantage of adversary in OW-CCA2 game can be reduced as follows:(23)ϵOW−CCA2=distinguish0,1+ϵGame2≤ϵdbdh+ADVCR+queryp+ADVPI,where ADVPI refers to advantage of adversary in preimage attack on hash function H2. Thus Theorem 2 is proved.


### 6.2. IND-CCA2 Security

Theorem 3.
The proposed G-PKEET cryptosystem achieves IND-CCA2 property against a type-2 PPT adversary in the standard model, as long as DBDH assumption onG and XDH assumption on G˜1 hold.Proof.
Game 0. Challenger behaves the same as in IND-CCA2 game of Figure 4. Game 1. In Game 1, challenger modifies component C1 of challenge ciphertext Ct∗; consequently altered ciphertext is given as the following structure using corresponding components of gpkt,pkt,gpki,ski:(24)Invalidmγ1γ2←rGT,C1∗=Invalidmγ1γ2Zts,C2=H1mχiγ1g˜1θ2γ2g˜1θ3ϕtγ1,C3=g˜1γ2,C4=g˜2γ1θ1χi,C5=gs,C6=r,C7=uttvtrwts,C8=g˜1γ1θ1χi,C9=g˜2γ1ϕt,C10=g˜2γ1.
We will prove that there exists no PPT adversary able to distinguish between Game 0 and Game 1 as long as DBDH assumption holds onG.


#### 6.2.1. Indistinguishability between Game 0 and Game 1

Using similar technique referred to in Section 6.1.1,, we construct an attackerB against DBDH assumption. He simultaneously invokes A as subprocedure, who attempts to distinguish between Game 0 and Game 1; i.e., B will play the role as challenger against A.Setup. After receiving a DBDH tuple g,ga,gb,gc,T, B replaces corresponding elements of public key pkt and private key skt in the same way referred to in Section 6.1.1.Query phase 1.(1)
Decryption Oracle: when Decryption oracle is queried with parameter decryptor indext, B deals with the ciphertext using the same way mentioned in Section 6.1.1.(2)
Encryption Oracle: challengerB works the same as mentioned in original G-PKEET scheme.(3)
Verification Oracle: challengerB works the same as mentioned in Section 6.1.1.(4)
Test Oracle: before performing the computation in procedureTest and outputting result, the test oracle takes corresponding measures according to decryptor index:When decryptor index equalst, the test oracle invokes verification oracle to process queried ciphertext together with decryptor index t. The test oracle refuses to continue the test by outputting ⊥ if verification oracle returns ⊥. This step corresponds to the precondition that user t and the proxy will interact with each other honestly.Otherwise, decryptor will assume submitted ciphertext is proper, corresponding to precondition that other users may not honestly interact with the proxy, i.e., maliciously claiming that an improper ciphertext is proper.Challenge. After receiving plaintext m0,m1 from adversary, challenger B selects b←r0,1 and generates challenge ciphertext tuple in the same way as mentioned in Section 6.1.1.Query Phase 2. Decryption oracle and verification oracle are applied with the same modification referred to in Section 6.1.1.Guess Phase. The adversary A outputs 0 or 1 representing the game he recognizes. B outputs the guess T=eg,gabc when A outputs 0, otherwise 1.Similar to that referred to in Section 6.1.1, the probability that B aborts during the simulation is at mostADVCR+query/p.WhenT=eg,gabc and B does not abort then A’s view is identical to its view in Game 0. Otherwise, his view is identical to that of Game 1.Since adversaryA can be invoked to attack DBDH problem, his advantage is expressed as(25)distinguish0,1≤ϵdbdh+PrAbort≤ϵdbdh+ADVCR+queryp.Game 2. In Game 2, challenger modifies components C2∗,C3∗ of challenge ciphertext Ct∗ on the basis of Game 1. Consequently altered ciphertext is generated using corresponding components of gpkt,pkt,gpki,ski as follows:(26)Invalidmγ1γ2←rGT;C1∗=Invalidmγ1γ2Zts,C2∗=g˜1γ3,C3∗=g˜1γ2,C4∗=g˜2γ1θ1χi,C5∗=gs,C6∗=r,C7∗=uttvtrwts,C8=g˜1γ1θ1χi,C9=g˜2γ1ϕt,C10=g˜2γ1.where γ3,γ2←rZq, superscript t=H1C1∗,C2∗,C3∗,C4∗,C5∗,C8∗,C9∗,C10∗.We will prove that there exists no PPT adversary able to distinguish between Game 1 and Game 2 as long as XDH assumption holds onG˜1.


#### 6.2.2. Indistinguishability between Game 1 and Game 2

We construct an attackerB against XDH assumption. He simultaneously invokes A as subprocedure, who attempts to distinguish between Game 1 and Game 2; i.e., B will play the role as challenger against A.Setup. Challenger B receives a XDH tuple g˜1α,g˜1β,g˜1ζ and sets g˜1θ2=g˜1β; thus he does not know concrete value of θ2 included in gsk. Other public parameters and key pairs are generated in the same way according to our scheme definition.Query phase 1.(1)
Decryption oracle: When being queried with decryptor indext, since challenger B does not know the value of θ2, he has to check THE consistency of C1 and C2 by judging whether(27)C3=g˜1γ2∗;g˜2θ1χiγ1∗=C4.(28)e˜g˜1θ2,g˜2γ2∗=e˜C2g˜1−θ3γ1∗ϕtH1m∗χiγ1,g˜2,wherem∗ and γ1∗,γ2∗ are extracted from C1, which is available to B since he has access to corresponding components of skt.(2)
Encryption Oracle: challengerB works the same as mentioned in original G-PKEET scheme.(3)
Verification Oracle: challengerB works similarly as mentioned in decryption oracle except for following the definition of Verify during output.(4)
Test Oracle: when decryptor index equalst, the test oracle processes submitted ciphertext using corresponding method mentioned in Section 6.2.1.Otherwise, test oracle will handle query by situation. Let ciphertextsC,C′ be queried ciphertexts, one of whose decryptor index is t and the other is not.Situation 1.
The adversary storesγ2′, corresponding to component C3′=g˜1γ2′.
In this situation, the test oracle judges whether the following equation stands:(29)e˜C2/g˜1θ2γ2,C4′e˜C8′,C9θ3=e˜C2′/g˜1θ2γ2′,C4e˜C8,C9′θ3.
If the equation stands, test oracle outputs 1; otherwise, it outputs 0.Situation 2.
The adversary takesg˜1α as C3′.
In this situation, the test oracle judges whether the following equation stands:(30)e˜C2/g˜1θ2γ2,C4′e˜C8′,C9θ3=e˜C2′/g˜1χ,C4e˜C8,C9′θ3.
If the equation stands, test oracle outputs 1; otherwise, it outputs 0.Situation 3.
The adversary himself has no idea of valueγ2′ and directly sets component C3′=g˜1γ2′.
In this situation, the test oracle will directly output 0 as a result if the equality test procedure is not aborted by outputting⊥ in other steps.
Since adversary does not knowγ2′,θ2, according to the definition of CDH assumption, he is also incapable of knowing g˜1γ2′θ2. Thus probability for adversary to find out exact g˜1γ2′ that satisfies the following equation is negligible.(31)e˜C2/g˜1θ2γ2,C4′e˜C8′,C9θ3=e˜C2′/g˜1θ2γ2′,C4e˜C8,C9′θ3.
From the above, we believe that PPT adversary cannot distinguish Game 1 from Game 2 through exploiting inconsistency output which may happen in Situation3.
Challenge. B makes additional modifications to challenge ciphertext of Game 1, embedding the third element of XDH challenge tuple g˜1ζ into it:(32)Invalidmγ1γ2←rGT;C1∗=Invalidmγ1γ2Zts,C2∗=H1mχiγ1g˜1ζg˜1θ3ϕtγ1,C3∗=g˜1α,C4∗=g˜2γ1θ1χi,C5∗=gs,C6∗=r,C7∗=uttvtrwts.Superscript t=H1C1∗,C2∗,C3∗,C4∗,C5∗,C8∗,C9∗,C10∗;γ1←rℤq;r,s←rℤp.
Query Phase 2. Verification oracle is applied with the same change as it is on page 16. The test oracle is supplemented with following rule:ChallengerB aborts and outputs random bit when a ciphertext whose decryptor index is not t (we refer to it by j) satisfies the following formula:(33)e˜g˜1γ1′,g˜2ϕjθ3=e˜g˜1θ3,g˜2γ1∗ϕt,where componentg˜2ϕjθ3 is taken from gpkj, γ1′ is extracted from component C1 of queried ciphertext, and γ1′ corresponds to challenge ciphertext component C2∗.
Since adversary has no idea of valueθ3,γ1∗,ϕt, the probability of abortion owing to the reason above is negligible.
Guess Phase. If A recognizes the current game as Game 1, B outputs guess g˜1ζ=g˜1αβ; otherwise it outputs the opposite guess.
Apparently, wheng˜1ζ=g˜1αβ, A’s view is identical to his view in Game 1. Otherwise, his view is identical to that of Game 2. Since adversary A can be invoked to attack XDH problem, his advantage is expressed as(34)distinguish1,2≤∫xdh.This is negligible when corresponding assumption stands.
In Game 2, the adversary ’s advantage is negligible since the challenge tuple has no relation withmb. Eventually, we can reduce the adversary’s advantage in attacking IND-CCA2 Game as(35)∫IND−CCA2=distinguish0,1+distinguish1,2+∫Game2≤∫dbdh+ADVCR+queryp+∫xdh+0.
Thus, Theorem3 is proved.


## 6.1. OW-CCA2 Security

Theorem 2.
The proposed G-PKEET cryptosystem achieves OW-CCA2 property against a type-1 PPT adversary in the standard model based on the DBDH assumption onG.Proof.
The main idea of proof is to construct a series of games which are reduced from the original OW-CCA2 game. The adversary unconditionally gains negligible advantage in the last game and is unable to distinguish each pair of games adjacent in reduction.
To complete the proof formally, we need to construct a series of games [24]:Game 0. Challenger behaves the same as OW-CCA2 game in Figure 3.Game 1. In Game 1, challenger modifies component C1 challenge ciphertext Ct∗ consequently altered ciphertext is given as the following structure using corresponding components of pkt,gpki,ski of(12)Invalidmγ1γ2←rGT;C1∗=Invalidmγ1γ2Zts,C2=H1mχiγ1g˜1θ2γ2g˜1θ3ϕtγ1,C3=g˜1γ2,C4=g˜2γ1θ1χi,C5=gs,C6=r,C7=uttvtrwts,C8=g˜1γ1θ1χi,C9=g˜2γ1ϕt,C10=g˜2γ1.Superscriptt=H2C1,C2,C3,C4,C5,C8,C9,C10;s,r←rℤp;γ1,γ2←rℤq.
We will prove that there exists no PPT adversary able to distinguish Game 0 from Game 1 with nonnegligible advantage as long as DBDH assumption holds onG.


### 6.1.1. Indistinguishability between Game 0 and Game 1

Briefly speaking, we construct an attackerB against DBDH assumption. He simultaneously invokes A as subprocedure, who attempts to distinguish between Game 0 and Game 1; i.e., B will play the role as challenger against A.Setup. After receiving a DBDH tuple g,ga,gb,gc,T, B replaces corresponding elements of public key pkt with DBDH challenge tuple elements as follows:(13)g1=ga,g2=gb,u=gbgyu,v=gbxvgyv,w=gbxwgyw,where yu,xv,yv,xw,yw←rZp. Other unmentioned elements contained in pkt are generated according to our scheme.Correspondingly, the private key tupleskt can be represented as skt=ϕt,χt,gab,x=b+yu,y=bxv+yv,w=bxw+yw, where x,y,z,gab is not known to B.Query Phase 1. (1) Decryption Oracle: when B is queried with user index t, firstly he checks whether the following statement stands:(14)eC5,utvC6w=eC7,g,where superscript t =  H1C1,C2,C3,C4,C5,C8,C9,C10.Ift+rxv+xd=0, B aborts the whole procedure and outputs a random bit to DBDH challenger. Since adversary has no idea of xv and xd, the probability for this type of event is query/p, where query is the times that adversary visits decryption oracle.Otherwise,B begins to extract plaintext from nonchallenge ciphertext, by firstly generating δ←rZp:(15)dC,1=g1−tyu+ryv+yw/t+rxv+xwutvrwδ,dC,2=g1−1t+rxv+xwgδ.Letδ˜=δ−a/t+rxv+xw. Then, we have(16)dC,1=g2autvrdδ˜,dC,2=gδ˜,mγ1γ2=C1edC,1,C5eC7,dC,2.Finally, it checks the consistency of plain text, hash message, and other components embedded in the ciphertext and outputs result of decryption:(17)DecryptionOraclect,sk∗,pk=⊥,if1m,otherwise.where (1) refers to the following statement:(18)g˜1ϕtθ3γ1C3θ2H1mχiγ1≠C2∨g˜2χiθ1γ1≠C4∨g˜1γ2≠C3∨g˜1χiθ1γ1≠C8∨g˜2γ1ϕt≠C9∨g˜2γ1≠C10.(2)
Encryption Oracle: challengerB works the same as mentioned in original G-PKEET scheme, since he knows the value of χt when being required to generate a ciphertext with encryptor index t.(3)
Verification Oracle: challengerB works in the same way as mentioned in Decryption Oracle except for following the description of Verify on output.Challenge. Challenger B selects m←rM and generates challenge ciphertext tuple in the following structure:(19)C1∗=mγ1γ2T,C2∗=H1mχiγ1g˜1θ2γ2g˜1θ3ϕtγ1,C3∗=g˜1γ2,C4∗=g˜2γ1θ1χi,C5∗=gc,C6∗=t∗+xwxv,C7∗=gct∗yu+C6∗yv+yw,C8∗=g˜1γ1θ1χi,C9=g˜2γ1ϕt,C10=g˜2γ1,where superscript t=H1C1,C2,C3,C4,C5,C8,C9,C10;γ1,γ2←rℤq.Query Phase 2. In this phase, decryption oracle is added with new restrictions: (1) challenge ciphertext cannot be requested together with decryptor index “t”; (2) when C≠C∗ and hash value H1C1,C2,C3,C4,C5,C8,C9,C10=t∗, challenger B aborts the whole game and outputs a random bit to DBDH challenger.Verification oracle works the same as mentioned in phase 1 except when being queried with challenge ciphertext andt as decryptor index. More detailedly, output is defined as follows:(20)OracleVerificationct,sk∗,pk=1,ifi=i∗⊥,otherwiseUnder actual circumstances, Verify might output 1 wheni≠i∗, consequently breaking the indistinguishability between Game 2 and actual circumstance. However, this situation happens when and only when a hash collision happens, the rate of which is negligible.Guess Phase. The adversary A outputs 0 or 1 representing the game he recognizes. B outputs the guess T=eg,gabc when A outputs 0, otherwise 1.Similar to [4], the probability that B aborts during the simulation is at most ADVCR+query/p, corresponding to the illustration in Query phases 1,2, where ADVCR refers to the probability of a hash collision.When B does not abort then A’s view is identical to its view in Game 0. Otherwise, his view is identical to that of Game 1. Uniform randomly generatedT=eg,gabc in Game 1 is statistically indistinguishable to Invalidmγ1γ2 when Invalidmγ1γ2∗ when T=eg,gZ. The reason is as follows:(21)T=eg,gzz←rZps.t.T=ega,gbz,m∗γ1∗γ2∗T=m∗γ1∗γ2∗ega,gbcega,gbz−c,=m∗γ1∗γ2∗⋅ega,gbz−cega,gbc,Invalidmγ1γ2∗⇔m∗γ1∗γ2∗⋅ega,gbz−c.Since adversaryA can be invoked to attack DBDH problem, his advantage can be expressed as(22)distinguish0,1≤ϵdbdh+PrAbort≤ϵdbdh+ADVCR+queryp.In Game 1,C1∗ in challenge ciphertext is irrelevant to plaintext message; therefore adversary ’s advantage can be reduced to the success rate of breaking hash function’s preimage properties. Eventually, the advantage of adversary in OW-CCA2 game can be reduced as follows:(23)ϵOW−CCA2=distinguish0,1+ϵGame2≤ϵdbdh+ADVCR+queryp+ADVPI,where ADVPI refers to advantage of adversary in preimage attack on hash function H2. Thus Theorem 2 is proved.


## 6.1.1. Indistinguishability between Game 0 and Game 1

Briefly speaking, we construct an attackerB against DBDH assumption. He simultaneously invokes A as subprocedure, who attempts to distinguish between Game 0 and Game 1; i.e., B will play the role as challenger against A.Setup. After receiving a DBDH tuple g,ga,gb,gc,T, B replaces corresponding elements of public key pkt with DBDH challenge tuple elements as follows:(13)g1=ga,g2=gb,u=gbgyu,v=gbxvgyv,w=gbxwgyw,where yu,xv,yv,xw,yw←rZp. Other unmentioned elements contained in pkt are generated according to our scheme.Correspondingly, the private key tupleskt can be represented as skt=ϕt,χt,gab,x=b+yu,y=bxv+yv,w=bxw+yw, where x,y,z,gab is not known to B.Query Phase 1. (1) Decryption Oracle: when B is queried with user index t, firstly he checks whether the following statement stands:(14)eC5,utvC6w=eC7,g,where superscript t =  H1C1,C2,C3,C4,C5,C8,C9,C10.Ift+rxv+xd=0, B aborts the whole procedure and outputs a random bit to DBDH challenger. Since adversary has no idea of xv and xd, the probability for this type of event is query/p, where query is the times that adversary visits decryption oracle.Otherwise,B begins to extract plaintext from nonchallenge ciphertext, by firstly generating δ←rZp:(15)dC,1=g1−tyu+ryv+yw/t+rxv+xwutvrwδ,dC,2=g1−1t+rxv+xwgδ.Letδ˜=δ−a/t+rxv+xw. Then, we have(16)dC,1=g2autvrdδ˜,dC,2=gδ˜,mγ1γ2=C1edC,1,C5eC7,dC,2.Finally, it checks the consistency of plain text, hash message, and other components embedded in the ciphertext and outputs result of decryption:(17)DecryptionOraclect,sk∗,pk=⊥,if1m,otherwise.where (1) refers to the following statement:(18)g˜1ϕtθ3γ1C3θ2H1mχiγ1≠C2∨g˜2χiθ1γ1≠C4∨g˜1γ2≠C3∨g˜1χiθ1γ1≠C8∨g˜2γ1ϕt≠C9∨g˜2γ1≠C10.(2)
Encryption Oracle: challengerB works the same as mentioned in original G-PKEET scheme, since he knows the value of χt when being required to generate a ciphertext with encryptor index t.(3)
Verification Oracle: challengerB works in the same way as mentioned in Decryption Oracle except for following the description of Verify on output.Challenge. Challenger B selects m←rM and generates challenge ciphertext tuple in the following structure:(19)C1∗=mγ1γ2T,C2∗=H1mχiγ1g˜1θ2γ2g˜1θ3ϕtγ1,C3∗=g˜1γ2,C4∗=g˜2γ1θ1χi,C5∗=gc,C6∗=t∗+xwxv,C7∗=gct∗yu+C6∗yv+yw,C8∗=g˜1γ1θ1χi,C9=g˜2γ1ϕt,C10=g˜2γ1,where superscript t=H1C1,C2,C3,C4,C5,C8,C9,C10;γ1,γ2←rℤq.Query Phase 2. In this phase, decryption oracle is added with new restrictions: (1) challenge ciphertext cannot be requested together with decryptor index “t”; (2) when C≠C∗ and hash value H1C1,C2,C3,C4,C5,C8,C9,C10=t∗, challenger B aborts the whole game and outputs a random bit to DBDH challenger.Verification oracle works the same as mentioned in phase 1 except when being queried with challenge ciphertext andt as decryptor index. More detailedly, output is defined as follows:(20)OracleVerificationct,sk∗,pk=1,ifi=i∗⊥,otherwiseUnder actual circumstances, Verify might output 1 wheni≠i∗, consequently breaking the indistinguishability between Game 2 and actual circumstance. However, this situation happens when and only when a hash collision happens, the rate of which is negligible.Guess Phase. The adversary A outputs 0 or 1 representing the game he recognizes. B outputs the guess T=eg,gabc when A outputs 0, otherwise 1.Similar to [4], the probability that B aborts during the simulation is at most ADVCR+query/p, corresponding to the illustration in Query phases 1,2, where ADVCR refers to the probability of a hash collision.When B does not abort then A’s view is identical to its view in Game 0. Otherwise, his view is identical to that of Game 1. Uniform randomly generatedT=eg,gabc in Game 1 is statistically indistinguishable to Invalidmγ1γ2 when Invalidmγ1γ2∗ when T=eg,gZ. The reason is as follows:(21)T=eg,gzz←rZps.t.T=ega,gbz,m∗γ1∗γ2∗T=m∗γ1∗γ2∗ega,gbcega,gbz−c,=m∗γ1∗γ2∗⋅ega,gbz−cega,gbc,Invalidmγ1γ2∗⇔m∗γ1∗γ2∗⋅ega,gbz−c.Since adversaryA can be invoked to attack DBDH problem, his advantage can be expressed as(22)distinguish0,1≤ϵdbdh+PrAbort≤ϵdbdh+ADVCR+queryp.In Game 1,C1∗ in challenge ciphertext is irrelevant to plaintext message; therefore adversary ’s advantage can be reduced to the success rate of breaking hash function’s preimage properties. Eventually, the advantage of adversary in OW-CCA2 game can be reduced as follows:(23)ϵOW−CCA2=distinguish0,1+ϵGame2≤ϵdbdh+ADVCR+queryp+ADVPI,where ADVPI refers to advantage of adversary in preimage attack on hash function H2. Thus Theorem 2 is proved.


## 6.2. IND-CCA2 Security

Theorem 3.
The proposed G-PKEET cryptosystem achieves IND-CCA2 property against a type-2 PPT adversary in the standard model, as long as DBDH assumption onG and XDH assumption on G˜1 hold.Proof.
Game 0. Challenger behaves the same as in IND-CCA2 game of Figure 4. Game 1. In Game 1, challenger modifies component C1 of challenge ciphertext Ct∗; consequently altered ciphertext is given as the following structure using corresponding components of gpkt,pkt,gpki,ski:(24)Invalidmγ1γ2←rGT,C1∗=Invalidmγ1γ2Zts,C2=H1mχiγ1g˜1θ2γ2g˜1θ3ϕtγ1,C3=g˜1γ2,C4=g˜2γ1θ1χi,C5=gs,C6=r,C7=uttvtrwts,C8=g˜1γ1θ1χi,C9=g˜2γ1ϕt,C10=g˜2γ1.
We will prove that there exists no PPT adversary able to distinguish between Game 0 and Game 1 as long as DBDH assumption holds onG.


### 6.2.1. Indistinguishability between Game 0 and Game 1

Using similar technique referred to in Section 6.1.1,, we construct an attackerB against DBDH assumption. He simultaneously invokes A as subprocedure, who attempts to distinguish between Game 0 and Game 1; i.e., B will play the role as challenger against A.Setup. After receiving a DBDH tuple g,ga,gb,gc,T, B replaces corresponding elements of public key pkt and private key skt in the same way referred to in Section 6.1.1.Query phase 1.(1)
Decryption Oracle: when Decryption oracle is queried with parameter decryptor indext, B deals with the ciphertext using the same way mentioned in Section 6.1.1.(2)
Encryption Oracle: challengerB works the same as mentioned in original G-PKEET scheme.(3)
Verification Oracle: challengerB works the same as mentioned in Section 6.1.1.(4)
Test Oracle: before performing the computation in procedureTest and outputting result, the test oracle takes corresponding measures according to decryptor index:When decryptor index equalst, the test oracle invokes verification oracle to process queried ciphertext together with decryptor index t. The test oracle refuses to continue the test by outputting ⊥ if verification oracle returns ⊥. This step corresponds to the precondition that user t and the proxy will interact with each other honestly.Otherwise, decryptor will assume submitted ciphertext is proper, corresponding to precondition that other users may not honestly interact with the proxy, i.e., maliciously claiming that an improper ciphertext is proper.Challenge. After receiving plaintext m0,m1 from adversary, challenger B selects b←r0,1 and generates challenge ciphertext tuple in the same way as mentioned in Section 6.1.1.Query Phase 2. Decryption oracle and verification oracle are applied with the same modification referred to in Section 6.1.1.Guess Phase. The adversary A outputs 0 or 1 representing the game he recognizes. B outputs the guess T=eg,gabc when A outputs 0, otherwise 1.Similar to that referred to in Section 6.1.1, the probability that B aborts during the simulation is at mostADVCR+query/p.WhenT=eg,gabc and B does not abort then A’s view is identical to its view in Game 0. Otherwise, his view is identical to that of Game 1.Since adversaryA can be invoked to attack DBDH problem, his advantage is expressed as(25)distinguish0,1≤ϵdbdh+PrAbort≤ϵdbdh+ADVCR+queryp.Game 2. In Game 2, challenger modifies components C2∗,C3∗ of challenge ciphertext Ct∗ on the basis of Game 1. Consequently altered ciphertext is generated using corresponding components of gpkt,pkt,gpki,ski as follows:(26)Invalidmγ1γ2←rGT;C1∗=Invalidmγ1γ2Zts,C2∗=g˜1γ3,C3∗=g˜1γ2,C4∗=g˜2γ1θ1χi,C5∗=gs,C6∗=r,C7∗=uttvtrwts,C8=g˜1γ1θ1χi,C9=g˜2γ1ϕt,C10=g˜2γ1.where γ3,γ2←rZq, superscript t=H1C1∗,C2∗,C3∗,C4∗,C5∗,C8∗,C9∗,C10∗.We will prove that there exists no PPT adversary able to distinguish between Game 1 and Game 2 as long as XDH assumption holds onG˜1.


### 6.2.2. Indistinguishability between Game 1 and Game 2

We construct an attackerB against XDH assumption. He simultaneously invokes A as subprocedure, who attempts to distinguish between Game 1 and Game 2; i.e., B will play the role as challenger against A.Setup. Challenger B receives a XDH tuple g˜1α,g˜1β,g˜1ζ and sets g˜1θ2=g˜1β; thus he does not know concrete value of θ2 included in gsk. Other public parameters and key pairs are generated in the same way according to our scheme definition.Query phase 1.(1)
Decryption oracle: When being queried with decryptor indext, since challenger B does not know the value of θ2, he has to check THE consistency of C1 and C2 by judging whether(27)C3=g˜1γ2∗;g˜2θ1χiγ1∗=C4.(28)e˜g˜1θ2,g˜2γ2∗=e˜C2g˜1−θ3γ1∗ϕtH1m∗χiγ1,g˜2,wherem∗ and γ1∗,γ2∗ are extracted from C1, which is available to B since he has access to corresponding components of skt.(2)
Encryption Oracle: challengerB works the same as mentioned in original G-PKEET scheme.(3)
Verification Oracle: challengerB works similarly as mentioned in decryption oracle except for following the definition of Verify during output.(4)
Test Oracle: when decryptor index equalst, the test oracle processes submitted ciphertext using corresponding method mentioned in Section 6.2.1.Otherwise, test oracle will handle query by situation. Let ciphertextsC,C′ be queried ciphertexts, one of whose decryptor index is t and the other is not.Situation 1.
The adversary storesγ2′, corresponding to component C3′=g˜1γ2′.
In this situation, the test oracle judges whether the following equation stands:(29)e˜C2/g˜1θ2γ2,C4′e˜C8′,C9θ3=e˜C2′/g˜1θ2γ2′,C4e˜C8,C9′θ3.
If the equation stands, test oracle outputs 1; otherwise, it outputs 0.Situation 2.
The adversary takesg˜1α as C3′.
In this situation, the test oracle judges whether the following equation stands:(30)e˜C2/g˜1θ2γ2,C4′e˜C8′,C9θ3=e˜C2′/g˜1χ,C4e˜C8,C9′θ3.
If the equation stands, test oracle outputs 1; otherwise, it outputs 0.Situation 3.
The adversary himself has no idea of valueγ2′ and directly sets component C3′=g˜1γ2′.
In this situation, the test oracle will directly output 0 as a result if the equality test procedure is not aborted by outputting⊥ in other steps.
Since adversary does not knowγ2′,θ2, according to the definition of CDH assumption, he is also incapable of knowing g˜1γ2′θ2. Thus probability for adversary to find out exact g˜1γ2′ that satisfies the following equation is negligible.(31)e˜C2/g˜1θ2γ2,C4′e˜C8′,C9θ3=e˜C2′/g˜1θ2γ2′,C4e˜C8,C9′θ3.
From the above, we believe that PPT adversary cannot distinguish Game 1 from Game 2 through exploiting inconsistency output which may happen in Situation3.
Challenge. B makes additional modifications to challenge ciphertext of Game 1, embedding the third element of XDH challenge tuple g˜1ζ into it:(32)Invalidmγ1γ2←rGT;C1∗=Invalidmγ1γ2Zts,C2∗=H1mχiγ1g˜1ζg˜1θ3ϕtγ1,C3∗=g˜1α,C4∗=g˜2γ1θ1χi,C5∗=gs,C6∗=r,C7∗=uttvtrwts.Superscript t=H1C1∗,C2∗,C3∗,C4∗,C5∗,C8∗,C9∗,C10∗;γ1←rℤq;r,s←rℤp.
Query Phase 2. Verification oracle is applied with the same change as it is on page 16. The test oracle is supplemented with following rule:ChallengerB aborts and outputs random bit when a ciphertext whose decryptor index is not t (we refer to it by j) satisfies the following formula:(33)e˜g˜1γ1′,g˜2ϕjθ3=e˜g˜1θ3,g˜2γ1∗ϕt,where componentg˜2ϕjθ3 is taken from gpkj, γ1′ is extracted from component C1 of queried ciphertext, and γ1′ corresponds to challenge ciphertext component C2∗.
Since adversary has no idea of valueθ3,γ1∗,ϕt, the probability of abortion owing to the reason above is negligible.
Guess Phase. If A recognizes the current game as Game 1, B outputs guess g˜1ζ=g˜1αβ; otherwise it outputs the opposite guess.
Apparently, wheng˜1ζ=g˜1αβ, A’s view is identical to his view in Game 1. Otherwise, his view is identical to that of Game 2. Since adversary A can be invoked to attack XDH problem, his advantage is expressed as(34)distinguish1,2≤∫xdh.This is negligible when corresponding assumption stands.
In Game 2, the adversary ’s advantage is negligible since the challenge tuple has no relation withmb. Eventually, we can reduce the adversary’s advantage in attacking IND-CCA2 Game as(35)∫IND−CCA2=distinguish0,1+distinguish1,2+∫Game2≤∫dbdh+ADVCR+queryp+∫xdh+0.
Thus, Theorem3 is proved.


## 6.2.1. Indistinguishability between Game 0 and Game 1

Using similar technique referred to in Section 6.1.1,, we construct an attackerB against DBDH assumption. He simultaneously invokes A as subprocedure, who attempts to distinguish between Game 0 and Game 1; i.e., B will play the role as challenger against A.Setup. After receiving a DBDH tuple g,ga,gb,gc,T, B replaces corresponding elements of public key pkt and private key skt in the same way referred to in Section 6.1.1.Query phase 1.(1)
Decryption Oracle: when Decryption oracle is queried with parameter decryptor indext, B deals with the ciphertext using the same way mentioned in Section 6.1.1.(2)
Encryption Oracle: challengerB works the same as mentioned in original G-PKEET scheme.(3)
Verification Oracle: challengerB works the same as mentioned in Section 6.1.1.(4)
Test Oracle: before performing the computation in procedureTest and outputting result, the test oracle takes corresponding measures according to decryptor index:When decryptor index equalst, the test oracle invokes verification oracle to process queried ciphertext together with decryptor index t. The test oracle refuses to continue the test by outputting ⊥ if verification oracle returns ⊥. This step corresponds to the precondition that user t and the proxy will interact with each other honestly.Otherwise, decryptor will assume submitted ciphertext is proper, corresponding to precondition that other users may not honestly interact with the proxy, i.e., maliciously claiming that an improper ciphertext is proper.Challenge. After receiving plaintext m0,m1 from adversary, challenger B selects b←r0,1 and generates challenge ciphertext tuple in the same way as mentioned in Section 6.1.1.Query Phase 2. Decryption oracle and verification oracle are applied with the same modification referred to in Section 6.1.1.Guess Phase. The adversary A outputs 0 or 1 representing the game he recognizes. B outputs the guess T=eg,gabc when A outputs 0, otherwise 1.Similar to that referred to in Section 6.1.1, the probability that B aborts during the simulation is at mostADVCR+query/p.WhenT=eg,gabc and B does not abort then A’s view is identical to its view in Game 0. Otherwise, his view is identical to that of Game 1.Since adversaryA can be invoked to attack DBDH problem, his advantage is expressed as(25)distinguish0,1≤ϵdbdh+PrAbort≤ϵdbdh+ADVCR+queryp.Game 2. In Game 2, challenger modifies components C2∗,C3∗ of challenge ciphertext Ct∗ on the basis of Game 1. Consequently altered ciphertext is generated using corresponding components of gpkt,pkt,gpki,ski as follows:(26)Invalidmγ1γ2←rGT;C1∗=Invalidmγ1γ2Zts,C2∗=g˜1γ3,C3∗=g˜1γ2,C4∗=g˜2γ1θ1χi,C5∗=gs,C6∗=r,C7∗=uttvtrwts,C8=g˜1γ1θ1χi,C9=g˜2γ1ϕt,C10=g˜2γ1.where γ3,γ2←rZq, superscript t=H1C1∗,C2∗,C3∗,C4∗,C5∗,C8∗,C9∗,C10∗.We will prove that there exists no PPT adversary able to distinguish between Game 1 and Game 2 as long as XDH assumption holds onG˜1.


## 6.2.2. Indistinguishability between Game 1 and Game 2

We construct an attackerB against XDH assumption. He simultaneously invokes A as subprocedure, who attempts to distinguish between Game 1 and Game 2; i.e., B will play the role as challenger against A.Setup. Challenger B receives a XDH tuple g˜1α,g˜1β,g˜1ζ and sets g˜1θ2=g˜1β; thus he does not know concrete value of θ2 included in gsk. Other public parameters and key pairs are generated in the same way according to our scheme definition.Query phase 1.(1)
Decryption oracle: When being queried with decryptor indext, since challenger B does not know the value of θ2, he has to check THE consistency of C1 and C2 by judging whether(27)C3=g˜1γ2∗;g˜2θ1χiγ1∗=C4.(28)e˜g˜1θ2,g˜2γ2∗=e˜C2g˜1−θ3γ1∗ϕtH1m∗χiγ1,g˜2,wherem∗ and γ1∗,γ2∗ are extracted from C1, which is available to B since he has access to corresponding components of skt.(2)
Encryption Oracle: challengerB works the same as mentioned in original G-PKEET scheme.(3)
Verification Oracle: challengerB works similarly as mentioned in decryption oracle except for following the definition of Verify during output.(4)
Test Oracle: when decryptor index equalst, the test oracle processes submitted ciphertext using corresponding method mentioned in Section 6.2.1.Otherwise, test oracle will handle query by situation. Let ciphertextsC,C′ be queried ciphertexts, one of whose decryptor index is t and the other is not.Situation 1.
The adversary storesγ2′, corresponding to component C3′=g˜1γ2′.
In this situation, the test oracle judges whether the following equation stands:(29)e˜C2/g˜1θ2γ2,C4′e˜C8′,C9θ3=e˜C2′/g˜1θ2γ2′,C4e˜C8,C9′θ3.
If the equation stands, test oracle outputs 1; otherwise, it outputs 0.Situation 2.
The adversary takesg˜1α as C3′.
In this situation, the test oracle judges whether the following equation stands:(30)e˜C2/g˜1θ2γ2,C4′e˜C8′,C9θ3=e˜C2′/g˜1χ,C4e˜C8,C9′θ3.
If the equation stands, test oracle outputs 1; otherwise, it outputs 0.Situation 3.
The adversary himself has no idea of valueγ2′ and directly sets component C3′=g˜1γ2′.
In this situation, the test oracle will directly output 0 as a result if the equality test procedure is not aborted by outputting⊥ in other steps.
Since adversary does not knowγ2′,θ2, according to the definition of CDH assumption, he is also incapable of knowing g˜1γ2′θ2. Thus probability for adversary to find out exact g˜1γ2′ that satisfies the following equation is negligible.(31)e˜C2/g˜1θ2γ2,C4′e˜C8′,C9θ3=e˜C2′/g˜1θ2γ2′,C4e˜C8,C9′θ3.
From the above, we believe that PPT adversary cannot distinguish Game 1 from Game 2 through exploiting inconsistency output which may happen in Situation3.
Challenge. B makes additional modifications to challenge ciphertext of Game 1, embedding the third element of XDH challenge tuple g˜1ζ into it:(32)Invalidmγ1γ2←rGT;C1∗=Invalidmγ1γ2Zts,C2∗=H1mχiγ1g˜1ζg˜1θ3ϕtγ1,C3∗=g˜1α,C4∗=g˜2γ1θ1χi,C5∗=gs,C6∗=r,C7∗=uttvtrwts.Superscript t=H1C1∗,C2∗,C3∗,C4∗,C5∗,C8∗,C9∗,C10∗;γ1←rℤq;r,s←rℤp.
Query Phase 2. Verification oracle is applied with the same change as it is on page 16. The test oracle is supplemented with following rule:ChallengerB aborts and outputs random bit when a ciphertext whose decryptor index is not t (we refer to it by j) satisfies the following formula:(33)e˜g˜1γ1′,g˜2ϕjθ3=e˜g˜1θ3,g˜2γ1∗ϕt,where componentg˜2ϕjθ3 is taken from gpkj, γ1′ is extracted from component C1 of queried ciphertext, and γ1′ corresponds to challenge ciphertext component C2∗.
Since adversary has no idea of valueθ3,γ1∗,ϕt, the probability of abortion owing to the reason above is negligible.
Guess Phase. If A recognizes the current game as Game 1, B outputs guess g˜1ζ=g˜1αβ; otherwise it outputs the opposite guess.
Apparently, wheng˜1ζ=g˜1αβ, A’s view is identical to his view in Game 1. Otherwise, his view is identical to that of Game 2. Since adversary A can be invoked to attack XDH problem, his advantage is expressed as(34)distinguish1,2≤∫xdh.This is negligible when corresponding assumption stands.
In Game 2, the adversary ’s advantage is negligible since the challenge tuple has no relation withmb. Eventually, we can reduce the adversary’s advantage in attacking IND-CCA2 Game as(35)∫IND−CCA2=distinguish0,1+distinguish1,2+∫Game2≤∫dbdh+ADVCR+queryp+∫xdh+0.
Thus, Theorem3 is proved.


## 7. Comparison

### 7.1. Theoretical Analysis

In Table1, we list out the security model and functionality of related PKEET schemes and G-PKEET schemes, showing that our scheme is the first G-PKEET scheme under standard model. All listed schemes obtain IND-CCA2 security against unauthorized users and OW-CCA2 security against authorized users except [1], since it does not introduce token mechanism and is only able to obtain OW-CCA2 security.Table 1
Scheme properties.
SchemeSecurity modelFunctionalityYang et al. [1]ROPKEETTang [2]ROPKEETZhang et al. [4]SMPKEETZeng et al. [5]SMPKEETLee et al. [6]SMPKEETLing et al. [7]ROG-PKEETOursSMG-PKEETNote. RO: random oracle model. SM: standard model.In Table2, we compare the computational efficiency of our schemes with related PKEET schemes and G-PKEET schemes. The second to fourth column show the computational cost of Enc algorithm, Dec algorithm, and Test algorithm. In the aspect of computational efficiency, our scheme is acceptable comparing with other schemes listed.Table 2
Computational efficiency.
SchemeEncDecTestCommunication round(s) of testYang et al. [1]3Exp3Exp2P1Tang [2]5Exp2Exp4Exp1Zhang et al. [4]6Exp2BP+1Exp2P1Zeng et al. [5]4Exp4Exp4Exp1Lee et al. [6]1P+14Exp9P+11Exp6P+10Exp1Ling et al. [7]5Exp2Exp2P+2Exp1Ours9Exp9Exp+3P+3P36Exp+6P32Note. Exp: the exponent computation. P: the type-1 bilinear pairing computation. P3: the type-3 bilinear pairing computation.The reason why computational cost of our scheme is higher than existing G-PKEET scheme [7] is that we add more ciphertext components to ensure our scheme satisfies new security and functional definition. And correspondingly, we have to supply decrypt, test algorithm with corresponding verification steps on these components. These verification steps guarantee scheme security at cost of increasing computational complexity.Through the fifth column of the table, we remind readers that security properties of our scheme rely on a prerequisite that proxy should interact with user on whether the ciphertext to be tested is proper. This prerequisite implicitly requires a two-round communication for equality test service, i.e., the algorithm Test; otherwise the security properties cannot be completely guaranteed.As for two generic PKEET schemes, we employed [25, 26] to instantiate Lee et al.’s scheme and use DDH assumption to construct hash proof system, on which Zeng et al.’s scheme is based.


### 7.2. Experimental Evaluation

We implement experimental performance analysis by using Java Pairing Based Cryptography (jPBC 2.0.0) as underlying cryptographic library [27]. The JDK version is Oracle jdk1.8.0_121. More detailedly, we, respectively, choose type-A curve and type-F curve provided by jPBC to perform symmetric bilinear pairing and asymmetric bilinear pairing. The field size bit length of all curves is at least 256. Our machine is equipped with Intel Core i7-10510U CPU 2.30 GHz processor and 16 GB RAM, running Ubuntu 16.04.We compare time consumption between our scheme and Ling et al. [7] in aspect of three algorithms: Enc algorithm, Dec algorithm, and Test algorithm. For each algorithm, we run it for ten times and calculate its average time cost. The result is shown as in Table 3.Table 3
Time consumption (ms).
SchemeEncDecTestLing et al. [7]823759Ours1724953895The gap between two schemes on computation time consumption reflects, on one hand, the gap in theory time complexity. On the other hand, type-A curve pairing operation provided in jPBC takes 10% of the time required by type-F curve pairing operation. Furthermore, the implicit restriction on public parameters in our scheme makes the field size bit length ofG larger than 256 ∗ 3, three times as that of G˜, and the computation time is equally increased. We conclude that constructing a more efficient G-PKEET scheme with equivalent security property is an issue that requires further discussion.


## 7.1. Theoretical Analysis

In Table1, we list out the security model and functionality of related PKEET schemes and G-PKEET schemes, showing that our scheme is the first G-PKEET scheme under standard model. All listed schemes obtain IND-CCA2 security against unauthorized users and OW-CCA2 security against authorized users except [1], since it does not introduce token mechanism and is only able to obtain OW-CCA2 security.Table 1
Scheme properties.
SchemeSecurity modelFunctionalityYang et al. [1]ROPKEETTang [2]ROPKEETZhang et al. [4]SMPKEETZeng et al. [5]SMPKEETLee et al. [6]SMPKEETLing et al. [7]ROG-PKEETOursSMG-PKEETNote. RO: random oracle model. SM: standard model.In Table2, we compare the computational efficiency of our schemes with related PKEET schemes and G-PKEET schemes. The second to fourth column show the computational cost of Enc algorithm, Dec algorithm, and Test algorithm. In the aspect of computational efficiency, our scheme is acceptable comparing with other schemes listed.Table 2
Computational efficiency.
SchemeEncDecTestCommunication round(s) of testYang et al. [1]3Exp3Exp2P1Tang [2]5Exp2Exp4Exp1Zhang et al. [4]6Exp2BP+1Exp2P1Zeng et al. [5]4Exp4Exp4Exp1Lee et al. [6]1P+14Exp9P+11Exp6P+10Exp1Ling et al. [7]5Exp2Exp2P+2Exp1Ours9Exp9Exp+3P+3P36Exp+6P32Note. Exp: the exponent computation. P: the type-1 bilinear pairing computation. P3: the type-3 bilinear pairing computation.The reason why computational cost of our scheme is higher than existing G-PKEET scheme [7] is that we add more ciphertext components to ensure our scheme satisfies new security and functional definition. And correspondingly, we have to supply decrypt, test algorithm with corresponding verification steps on these components. These verification steps guarantee scheme security at cost of increasing computational complexity.Through the fifth column of the table, we remind readers that security properties of our scheme rely on a prerequisite that proxy should interact with user on whether the ciphertext to be tested is proper. This prerequisite implicitly requires a two-round communication for equality test service, i.e., the algorithm Test; otherwise the security properties cannot be completely guaranteed.As for two generic PKEET schemes, we employed [25, 26] to instantiate Lee et al.’s scheme and use DDH assumption to construct hash proof system, on which Zeng et al.’s scheme is based.


## 7.2. Experimental Evaluation

We implement experimental performance analysis by using Java Pairing Based Cryptography (jPBC 2.0.0) as underlying cryptographic library [27]. The JDK version is Oracle jdk1.8.0_121. More detailedly, we, respectively, choose type-A curve and type-F curve provided by jPBC to perform symmetric bilinear pairing and asymmetric bilinear pairing. The field size bit length of all curves is at least 256. Our machine is equipped with Intel Core i7-10510U CPU 2.30 GHz processor and 16 GB RAM, running Ubuntu 16.04.We compare time consumption between our scheme and Ling et al. [7] in aspect of three algorithms: Enc algorithm, Dec algorithm, and Test algorithm. For each algorithm, we run it for ten times and calculate its average time cost. The result is shown as in Table 3.Table 3
Time consumption (ms).
SchemeEncDecTestLing et al. [7]823759Ours1724953895The gap between two schemes on computation time consumption reflects, on one hand, the gap in theory time complexity. On the other hand, type-A curve pairing operation provided in jPBC takes 10% of the time required by type-F curve pairing operation. Furthermore, the implicit restriction on public parameters in our scheme makes the field size bit length ofG larger than 256 ∗ 3, three times as that of G˜, and the computation time is equally increased. We conclude that constructing a more efficient G-PKEET scheme with equivalent security property is an issue that requires further discussion.


## 8. Conclusion

In this paper, we firstly broaden the current existing security notion of G-PKEET by granting specific adversaries restricted access to the equality test service. The new security notion ensures that unexpected privacy leakage can be avoided even when proxy may provide equality service to malicious users. To construct a solution that matches our definition, we secondly extend the functionality of G-PKEET scheme by allowing private key holder to detect whether a ciphertext is proper while proxy can optionally request private key holder to verify a ciphertext, before he conducts equality test on it. Eventually, our new G-PKEET scheme is acceptable in aspect of computational efficiency and proved to be OW-CCA2 secure against adversary authorized by group administrator and IND-CCA2 secure against unauthorized adversary. Furthermore, our scheme is the first G-PKEET proved to be secure under standard model.



---

*Source: 4605685-2022-07-07.xml*