Open AccessArticle

Identity-Based Matchmaking Encryption with Equality Test

Zhen Yan

Xijun Lin

Xiaoshuai Zhang

Jianliang Xu

and

Haipeng Qu

College of Computer Science and Technology, Ocean University of China, Qingdao 266100, China

Author to whom correspondence should be addressed.

Entropy 2024, 26(1), 74; https://doi.org/10.3390/e26010074

Submission received: 19 November 2023 / Revised: 31 December 2023 / Accepted: 8 January 2024 / Published: 15 January 2024

(This article belongs to the Special Issue Advances in Information Sciences and Applications II)

Download

Browse Figures

Versions Notes

Abstract

The identity-based encryption with equality test (IBEET) has become a hot research topic in cloud computing as it provides an equality test for ciphertexts generated under different identities while preserving the confidentiality. Subsequently, for the sake of the confidentiality and authenticity of the data, the identity-based signcryption with equality test (IBSC-ET) has been put forward. Nevertheless, the existing schemes do not consider the anonymity of the sender and the receiver, which leads to the potential leakage of sensitive personal information. How to ensure confidentiality, authenticity, and anonymity in the IBEET setting remains a significant challenge. In this paper, we put forward the concept of the identity-based matchmaking encryption with equality test (IBME-ET) to address this issue. We formalized the system model, the definition, and the security models of the IBME-ET and, then, put forward a concrete scheme. Furthermore, our scheme was confirmed to be secure and practical by proving its security and evaluating its performance.

Keywords:

matchmaking encryption; equality test; confidentiality; authenticity; anonymity

1. Introduction

The swift progress in cloud computing featured by the outsourcing of data to the cloud has given rise to a growing trend among organizations and individuals, enabling entities to benefit from the ultra-large capacity and calculating services provided by cloud providers. The maintenance of data confidentiality is a fundamental security requirement of cloud storage, which is generally achieved by employing existing cryptographic mechanisms. Nonetheless, how to perform efficient searches on ciphertexts is a practical problem. In order to protect data confidentiality and, meanwhile, support privacy-preserving keyword searching on ciphertexts, public key encryption with keyword search (PEKS) has been presented [1]. Nevertheless, PEKS is limited to searching on ciphertexts generated under a single public key, rendering it unsuitable for cloud storage scenarios involving multiple users.

To provide privacy-preserving equality searching on ciphertexts encrypted under distinct public keys without losing the data confidentiality, Yang et al. [2] put forward an extension of PEKS known as the public key encryption with equality test (PKEET). However, in Yang et al.’s construction, anyone can conduct the equality test without authorization, which infringes on the data owner’s privacy. Hence, the authorization mechanism was introduced into the PKEET to guarantee that no one except the data owner can enable the cloud server to test its ciphertexts with the others’.

Subsequently, Ma [3] proposed the identity-based encryption with equality test (IBEET) to eliminate the certificate management problem of the PKEET. In this primitive, the identities of the sender and receiver were exploited to denote the public keys, eliminating the need for certificate management. Owing to the equality test function, the IBEET has been applied in various practical applications, such as personal health record (PHR) systems [4,5] and Internet of Vehicles (IoV) road monitoring [6].

Ensuring the authenticity of data is another fundamental security requirement of cloud storage. For the sake of the confidentiality and authenticity of data while supporting the privacy-preserving equality test for ciphertexts generated from different identities, Xiong et al. [7] presented the identity-based signcryption with equality test (IBSC-ET). Afterwards, several related signcryption schemes supporting the equality test have been conceived of. Nevertheless, the existing studies have not considered the anonymity of the sender and the receiver, which leads to the potential leakage of sensitive personal information.

1.1. Motivation

As depicted in Figure 1, in a PHR system, the patients’ PHRs contain as much relevant health data as possible from various healthcare providers over their lifetime. To ensure patients’ privacy, it is essential to store the health data in the cloud in ciphertext form. To find patients having similar illnesses, a patient (e.g., Alice or Bob) can authorize the cloud server to compare his/her ciphertexts sent by a specified healthcare provider with the others’ ciphertexts, so that the patients can help each other by sharing their experiences or mental processes.

However, by employing the existing signcryption schemes with equality test (to guarantee the confidentiality and authenticity of health data while supporting the privacy-preserving equality test on ciphertexts), the patients are unable to prevent sensitive personal information from being leaked to the cloud server. That is because the existing schemes do not consider the anonymity of the sender and receiver of the ciphertext. Consequently, the cloud server can know the healthcare provider of the ciphertext, e.g., MD Anderson Cancer Center. Likewise, from the ciphertext and the authorization trapdoor, the cloud server can learn whose identity the ciphertext is encrypted under, namely who is the receiver of the ciphertext, in this way to identify the patient associated with the ciphertext. Obviously, this seriously infringes upon the patient’s privacy.

Hence, during the equality testing procedure, there are three security aspects that should be guaranteed against the cloud server:

Confidentiality: The cloud server has no knowledge about the health data concealed in the ciphertext.
Authenticity: The cloud server is unable to fake any legitimate ciphertext pertaining to the sender and the receiver.
Anonymity: The cloud server has no knowledge about the identities of the sender and the receiver concealed in the ciphertext.

Therefore, we propose a new primitive, which not only offers the confidentiality, authenticity, and anonymity of data stored in the cloud, but also provides equality test functionality for ciphertexts generated under different identities without losing the confidentiality, authenticity, and anonymity of the data.

1.2. Related Works

Search on ciphertexts: Searchable encryption (SE) [8] was put forward to offer secure search functionality over ciphertexts encrypted under single public key. There are two categories of SE: public key encryption with keyword search (PEKS) [1,9,10] and symmetric searchable encryption (SSE) [11,12]. PEKS was conceived of by Boneh et al. [1] to support keyword searching over ciphertexts in public key settings by using the corresponding trapdoors without retrieving messages. After that, a variety of PEKS schemes have been presented for enhanced functionalities and different application requirements [9,10]. However, SE cannot offer equality test functionality for ciphertexts generated under different identities, which differs from our proposal.

Equality test on ciphertexts: The primitive of the PKEET was put forward to verify whether the identical message is concealed in two ciphertexts, where the ciphertexts may be encrypted under distinct public keys [2]. Then, the authorization mechanisms were introduced into the PKEET, and a series of PKEET schemes supporting various authorizations were proposed [13,14]. Ma [3] first introduced the primitive of the IBEET, to eliminate the certificate management problem of the traditional PKEET. A semi-generic IBEET scheme was conceived of by Lee et al. [15] to achieve CCA security. Then, several IBEET schemes supporting various authorizations were introduced [16,17]. Although the above schemes offer equality test functionality while preserving the confidentiality, the data authenticity is not guaranteed. To address this challenge, Xiong et al. [7] established the notion of the IBSC-ET by combining identity-based signcryption (IBSC) [18] and the IBEET. Afterwards, several signcryption schemes with equality test functionality for heterogeneous systems were proposed [19,20,21]. However, the existing studies have not considered the anonymity of the sender and the receiver, which leads to the potential leakage of sensitive personal information, which differs from our proposal.

Identity-based matchmaking encryption: In CRYPTO 2019, Ateniese et al. [22] put forward the primitive of identity-based matching encryption (IB-ME) to logically ensure the confidentiality, authenticity, and anonymity of data in one step. The guarantee of IB-ME is as follows: the recipient obtains the message when the match happens (both parties’ identities match the identity specified by the other party); in case the match does not happen, no information is disclosed other than the fact of the mismatch. Then, by extending IB-ME, a secure access control scheme was conceived of by Xu et al. [23] for cloud–fog computing, and a secure access control scheme was suggested by Sun et al. [24] for cloud-enabled industrial IoT healthcare systems. Chen et al. [25] suggested an IB-ME scheme on the basis of standard assumptions. Wu et al. [26] conceived of a Fuzzy IB-ME scheme. Yan et al. [27] conceived of an IB-ME scheme supporting proxy decryption. Sun et al. [28] suggested an IB-ME scheme supporting a broadcast mechanism. However, although IB-ME can ensure the confidentiality, authenticity, and anonymity of data, all of these related schemes cannot offer equality test functionality for ciphertexts without losing the confidentiality, authenticity, and anonymity of the data, which differs from our proposal.

1.3. Contributions

We emphasize here again that the existing cryptographic schemes with the equality test do not consider the anonymity of the sender and the receiver, which leads to the potential leakage problem of sensitive personal information. Hence, we put forward a novel primitive, called the identity-based matchmaking encryption with equality test (IBME-ET), by combining IB-ME and the IBEET. This primitive not only offers the confidentiality, authenticity, and anonymity of data stored in the cloud, but also provides equality test functionality for ciphertexts generated under different identities without losing the confidentiality, authenticity, and anonymity of the data.

Our proposed IBME-ET can advance the anonymity of existing applications. For example, in a PHR system [4,5], the patient can permit the cloud server to compare his/her encrypted health data sent by a specified healthcare provider with the others’, in this way to make friends with the patients having a similar illness. Our proposal can simplify the leakage problem of the real identities of the healthcare provider and the patient, which exists in current cryptographic schemes with the equality test, thereby guaranteeing the confidentiality, authenticity, and anonymity of the patients’ health data.

The equality testing process in the IBME-ET can be succinctly outlined as follows: Let

C_{(σ_{A}, {r c v}_{A})}

denote a ciphertext generated on

(e k_{σ_{A}}, {r c v}_{A}, m_{A})

and

C_{(σ_{B}, {r c v}_{B})}

denote a ciphertext generated on

(e k_{σ_{B}}, {r c v}_{B}, m_{B})

, where

e k_{σ_{A}}

and

e k_{σ_{B}}

are the encryption keys of the senders with identities

σ_{A}

and

σ_{B}

and

r c v_{A}

and

r c v_{B}

are the identities of the specified receivers, respectively. Furthermore, let

t d_{(s n d_{A}, ρ_{A})}

be a trapdoor generated on

(s n d_{A}, d k_{ρ_{A}})

and

t d_{(s n d_{B}, ρ_{B})}

be a trapdoor generated on

(s n d_{B}, d k_{ρ_{B}})

, where

s n d_{A}

and

s n d_{B}

are the identities of the specified senders and

d k_{ρ_{A}}

and

d k_{ρ_{B}}

are the decryption keys of the receivers with identities

ρ_{A}

and

ρ_{B}

, respectively. Given

(C_{(σ_{A}, {r c v}_{A})}, t d_{(s n d_{A}, ρ_{A})})

and

(C_{(σ_{B}, {r c v}_{B})}, t d_{(s n d_{B}, ρ_{B})})

, two conditions are involved:

Match (i.e., $σ_{A} = {s n d}_{A} \land {r c v}_{A} = ρ_{A} \land σ_{B} = {s n d}_{B} \land {r c v}_{B} = ρ_{B} \land m_{A} = m_{B}$ ): the cloud server returns 1, and no further information is revealed other than the fact that the match happened, that is the cloud server learns neither the messages $m_{A} = m_{B}$ nor the identities $σ_{A} = {s n d}_{A}$ , ${r c v}_{A} = ρ_{A}$ , $σ_{B} = {s n d}_{B}$ , ${r c v}_{B} = ρ_{B}$ .
Mismatch (i.e., $σ_{A} \neq {s n d}_{A} \lor {r c v}_{A} \neq ρ_{A} \lor σ_{B} \neq {s n d}_{B} \lor {r c v}_{B} \neq ρ_{B} \lor m_{A} \neq m_{B}$ ): the cloud server returns 0, and no further information is revealed other than the fact of the mismatch, that is the cloud server learns neither the messages $m_{A}$ , $m_{B}$ nor the identities $σ_{A}$ , ${s n d}_{A}$ , ${r c v}_{A}$ , $ρ_{A}$ , $σ_{B}$ , ${s n d}_{B}$ , ${r c v}_{B}$ , $ρ_{B}$ .

The principal contributions can be succinctly outlined as follows:

We present the notion of the IBME-ET, which not only offers the confidentiality, authenticity, and anonymity of data stored in the cloud, but also provides equality test functionality for ciphertexts generated under different identities without losing the confidentiality, authenticity, and anonymity of the data.
We put forward the system model and definition of the IBME-ET. With respect to the confidentiality, authenticity, and anonymity, we formulated four security models for the IBME-ET by taking four types of adversaries into account.
We constructed a concrete IBME-ET scheme on the basis of the BDH assumption and the Gap-BDH assumption. Our scheme was confirmed to be secure and practical by proving its security and evaluating its performance.

1.4. Organization

In general: Section 2 introduces the preliminaries while Section 3 presents IBME-ET by displaying its system, definition and four security models. Section 4 and Section 5, respectively, focus on the detailed scheme and analysis of security. Then, Section 6 focuses on performance evaluation, Section 7 arrives at a conclusion.

2. Preliminaries

2.1. Asymmetric Bilinear Groups

G, \hat{G}

, and

G_{T}

indicate three multiplicative cyclic groups with prime order q. g and

\hat{g}

are the generators of

G

and

\hat{G}

, respectively. An asymmetric bilinear map

e : G \times \hat{G} \to G_{T}

includes the following characteristics:

Bilinearity: $\forall x \in G$ , $\forall y \in \hat{G}$ and $\forall u, v \in Z_{q}^{*}$ , $e (x^{u}, y^{v}) =$ $e {(x, y)}^{u v}$ .
Non-degeneracy: $\exists g \in G$ , $\hat{g} \in \hat{G}$ , $e (g, \hat{g}) \neq 1$ .

Note that the group operations and asymmetric bilinear map e can be computed efficiently. However, if no efficiently computable isomorphisms are found between

G

and

\hat{G}

, then

G, \hat{G}

and

G_{T}

do not possess efficiently computable isomorphisms.

2.2. Assumptions

Bilinear Diffie–Hellman (BDH) assumption: When a tuple $(g, g^{a}, g^{c}, \hat{g},$ ${\hat{g}}^{a}, {\hat{g}}^{b}) \in G^{3} \times {\hat{G}}^{3}$ is given, no PPT algorithm $A$ calculates $e {(g, \hat{g})}^{a b c} \in G_{T}$ with non-negligible advantage. Define $A$ ’s advantage as

$A d v_{B D H}^{A} (λ) = \Pr [A (g, g^{a}, g^{c}, \hat{g}, {\hat{g}}^{a}, {\hat{g}}^{b}) = e {(g, \hat{g})}^{a b c}] .$
Gap-bilinear Diffie–Hellman (Gap-BDH) assumption: When a tuple $(g, g^{a}, g^{c}, \hat{g}, {\hat{g}}^{a}, {\hat{g}}^{b}) \in G^{3} \times {\hat{G}}^{3}$ is given, even with the decision BDH oracle $O_{DBDH}$ , no PPT algorithm $A$ calculates $e {(g, \hat{g})}^{a b c} \in$ $G_{T}$ with non-negligible advantage [29]. Tuples of the form $(g, g^{a}, g^{c},$ $\hat{g}, {\hat{g}}^{a}, {\hat{g}}^{b}, e {(g, \hat{g})}^{a b c})$ are known as “BDH tuples”. With $(g, g^{a},$ $g^{c}, \hat{g}, {\hat{g}}^{a}, {\hat{g}}^{b}, T)$ , $O_{DBDH}$ is able to check $T = e {(g, \hat{g})}^{a b c}$ or not. $O_{DBDH}$ outputs 1 when $T = e {(g, \hat{g})}^{a b c}$ ; otherwise, $O_{DBDH}$ outputs 0. Define $A$ ’s advantage as

$A d v_{G a p - B D H}^{A} (λ) = \Pr [A (g, g^{a}, g^{c}, \hat{g}, {\hat{g}}^{a}, {\hat{g}}^{b}, O_{DBDH}) = e {(g, \hat{g})}^{a b c}] .$

3. Definitions of IBME-ET

3.1. System Model

In Figure 2, our proposed IBME-ET comprises four distinct entities.

KGC: This entity’s responsibility is to securely generate and distribute encryption keys and decryption keys.
Sender: This entity’s responsibility is to generate ciphertexts, ensuring the confidentiality, authenticity, and anonymity of the data.
Receiver: This entity is responsible for collecting and outsourcing ciphertexts from potential senders secretly. It permits the cloud server to test ciphertexts sent by a specific sender without compromising the confidentiality, authenticity, and anonymity of the data.
Cloud server: This entity’s responsibility is to store the ciphertexts and perform equality tests based on the receivers’ authorizations.

Our workflow is succinctly outlined as follows:

The KGC utilizes the algorithm SKGen to calculate the encryption key $e k_{σ}$ in accordance with the identity of the sender $σ$ and securely delivers this to the sender. Similarly, the KGC utilizes the algorithm RKGen to calculate the decryption key $d k_{ρ}$ in accordance with the identity of the receiver $ρ$ and securely delivers this to the receiver.
A sender identified as $σ$ executes the algorithm Enc to conceal the message m using encryption key $e k_{σ}$ along with a target receiver’s identity $r c v$ , delivering it to the receiver with the ciphertext $C_{(σ, r c v)}$ .
A receiver identified as $ρ$ executes the algorithm Decc to decrypt the ciphertexts by employing the receiver’s decryption key $d k_{ρ}$ and the identity of the target sender $s n d$ , delivering the desirable ciphertexts to the cloud server. Specifically, given $C_{(σ, r c v)}$ , $d k_{ρ}$ , and $s n d$ , the guarantee in the decryption procedure is as follows:
- Match (i.e., $σ = s n d \land ρ = r c v$ ): the message m is obtained by the receiver.
- Mismatch (i.e., $σ \neq s n d \lor ρ \neq r c v$ ): the receiver obtains neither the message m nor the identities $σ$ , $r c v$ .
To test the ciphertexts offered by a target sender, the receiver identified as $ρ$ executes the algorithm Auth to calculate a trapdoor $t d_{(s n d, ρ)}$ with the identity of the target sender $s n d$ and its decryption key $d k_{ρ}$ and delivers the trapdoor to the cloud server.
Utilizing the receivers’ trapdoors, the cloud server executes the algorithm Test to test the ciphertexts sent by the specified senders without learning the messages and identities. Specifically, given $(C_{(σ_{A}, {r c v}_{A})}, t d_{(s n d_{A}, ρ_{A})})$ and $(C_{(σ_{B}, {r c v}_{B})}, t d_{(s n d_{B}, ρ_{B})})$ , the guarantee in equality testing procedure is as follows:
- Match (i.e., $σ_{A} = {s n d}_{A} \land {r c v}_{A} = ρ_{A} \land σ_{B} = {s n d}_{B} \land {r c v}_{B} = ρ_{B} \land m_{A} = m_{B}$ ): the cloud server returns 1, and the cloud server learns neither the messages $m_{A} = m_{B}$ nor the identities $σ_{A} = {s n d}_{A}$ , ${r c v}_{A} = ρ_{A}$ , $σ_{B} = {s n d}_{B}$ , ${r c v}_{B} = ρ_{B}$ .
- Mismatch (i.e., $σ_{A} \neq {s n d}_{A} \lor {r c v}_{A} \neq ρ_{A} \lor σ_{B} \neq {s n d}_{B} \lor {r c v}_{B} \neq ρ_{B} \lor m_{A} \neq m_{B}$ ): the cloud server returns 0, and the cloud server learns neither the messages $m_{A}$ , $m_{B}$ nor the identities $σ_{A}$ , ${s n d}_{A}$ , ${r c v}_{A}$ , $ρ_{A}$ , $σ_{B}$ , ${s n d}_{B}$ , ${r c v}_{B}$ , $ρ_{B}$ .

3.2. IBME-ET Definition

An IBME-ET scheme comprises the subsequent algorithms:

$S e t u p (λ) \to (p p, m k)$ : The system parameters $p p$ along with the master key $m k$ are answered.
$S K G e n (p p, m k, σ) \to e k_{σ}$ : The encryption key $e k_{σ}$ for the sender identified as $σ$ is answered.
$R K G e n (p p, m k, ρ) \to d k_{ρ}$ : The decryption key $d k_{ρ}$ for the receiver identified as $ρ$ is answered.
$E n c (p p, e k_{σ}, r c v, m) \to C$ : Given the system parameters $p p$ , an encryption key of the sender $e k_{σ}$ , and an identity of the target receiver $r c v$ along with the message m, the corresponding ciphertext C is answered.
$D e c (p p, d k_{ρ}, s n d, C) \to m / ⊥$ : Given the system parameters $p p$ , a decryption key of the receiver $d k_{ρ}$ , and an identity of the target sender $s n d$ along with the ciphertext C, the corresponding message m is answered or the symbol ⊥ to signal the failure of the decryption is answered.
$A u t h (p p, s n d, d k_{ρ}) \to t d_{(s n d, ρ)}$ : Given the system parameters $p p$ and an identity of the target sender $s n d$ along with a decryption key of the receiver $d k_{ρ}$ , the corresponding trapdoor $t d_{(s n d, ρ)}$ is answered.
$T e s t (p p, C_{(σ_{A}, {r c v}_{A})}, t d_{({s n d}_{A}, ρ_{A})}, C_{(σ_{B}, {r c v}_{B})}, t d_{({s n d}_{B}, ρ_{B})}) \to 0 / 1$ : Given the system parameters $p p$ , two pairs of ciphertext/trapdoors $(C_{(σ_{A}, {r c v}_{A})}, t d_{({s n d}_{A}, ρ_{A})})$ and $(C_{(σ_{B}, {r c v}_{B})}, t d_{({s n d}_{B}, ρ_{B})})$ , if $σ_{A} = {s n d}_{A} \land {r c v}_{A} = ρ_{A} \land σ_{B} = {s n d}_{B} \land {r c v}_{B} = ρ_{B} \land C_{(σ_{A}, {r c v}_{A})}$ and $C_{(σ_{B}, {r c v}_{B})}$ are generated using the identical message, it answers 1. Otherwise, it answers 0.

Correctness: An IBME-ET scheme is correct when the subsequent conditions are met:

When $σ = s n d$ $\land ρ = r c v$ , $D e c (p p, d k_{ρ}, s n d, E n c (p p,$ $e k_{σ}, r c v, m)) = m$ always holds.
Let $C_{(σ_{A}, {r c v}_{A})} = E n c (p p, e k_{σ_{A}}, {r c v}_{A}, m_{A})$ , $C_{(σ_{B}, {r c v}_{B})} = E n c (p p, e k_{σ_{B}}, {r c v}_{B}, m_{B})$ , $t d_{(s n d_{A}, ρ_{A})} = A u t h (p p, s n d_{A}, d k_{ρ_{A}})$ , and $t d_{(s n d_{B}, ρ_{B})} = A u t h (p p, s n d_{B}, d k_{ρ_{B}})$ . If $σ_{A} = {s n d}_{A} \land {r c v}_{A} = ρ_{A}$ $\land σ_{B} = {s n d}_{B} \land {r c v}_{B} = ρ_{B}$ $\land m_{A} = m_{B}$ , $T e s t (p p, C_{(σ_{A}, {r c v}_{A})}$ , $t d_{(s n d_{A}, ρ_{A})}, C_{(σ_{B}, {r c v}_{B})}, t d_{(s n d_{B}, ρ_{B})}) = 1;$ otherwise, $\Pr [T e s t (p p, C_{(σ_{A}, {r c v}_{A})}, t d_{(s n d_{A}, ρ_{A})}$ , $C_{(σ_{B}, {r c v}_{B})}, t d_{(s n d_{B}, ρ_{B})}) = 1]$ is negligible.

3.3. Security Definitions

With respect to the confidentiality, authenticity, and anonymity of the IBME-ET, it is crucial to consider four distinct types of adversaries:

Type-I adversary $A_{1}$ : Without the trapdoor and decryption key of the receiver, $A_{1}$ is unable to determine which message the challenge ciphertext is computed from. For $A_{1}$ , define the security model IND-ID-CCA.
Type-II adversary $A_{2}$ : Without the decryption key of the receiver, $A_{2}$ is unable to obtain the message concealed in the challenge ciphertext. For $A_{2}$ , define the security model OW-ID-CCA.
Type-III adversary $A_{3}$ : Without the decryption key of the receiver and the encryption key of the sender, $A_{3}$ is unable to determine the corresponding sender and receiver, even if $A_{3}$ has the trapdoor. For $A_{3}$ , define the security model ANON-ID-CCA.
Type-IV adversary $A_{4}$ : Without the decryption key of the receiver and the encryption key of the sender, $A_{4}$ is unable to fake any legitimate ciphertext delivered by the sender to the receiver, even if $A_{4}$ has the trapdoor. For $A_{4}$ , define the security model sUF-ID-CMA.

Let

C

be the challenger. We have the following oracles:

$O_{S K G e n} (σ_{i})$ : Once the identity of the sender $σ_{i}$ is received, $C$ answers the encryption key $e k_{σ_{i}}$ .
$O_{R K G e n} (ρ_{j})$ : Once the identity of the receiver $ρ_{j}$ is received, $C$ answers the decryption key $d k_{ρ_{j}}$ .
$O_{E n c} (σ_{i}, r c v, m)$ : Once the identity of the sender $σ_{i}$ , the identity of the target receiver $r c v$ , and a message m are received, $C$ answers the result of $E n c (p p, e k_{σ_{i}}, r c v, m)$ .
$O_{D e c} (ρ_{j}, s n d, C)$ : Once the identity of the receiver $ρ_{j}$ , the identity of the target sender $s n d$ , and a ciphertext C are received, $C$ answers the result of $D e c (p p, d k_{ρ_{j}}, s n d, C)$ .
$O_{A u t h} (s n d, ρ_{j})$ : Once the identity of the target sender $s n d$ and the identity of the receiver $ρ_{j}$ are received, $C$ answers the corresponding trapdoor $t d_{(s n d, ρ_{j})} = A u t h (p p, s n d, d k_{ρ_{j}})$ .

Definition 1

(IND-ID-CCA). Regarding

A_{1}

, the IBME-ET scheme meets IND-ID-CCA security when no PPT

A_{1}

is winning the game below with a non-negligible advantage:

1.: Setup: $C$ utilizes the algorithm $S e t u p$ to calculate the master key $m k$ and the system parameters $p p$ and delivers $p p$ to $A_{1}$ .
2.: Phase 1: $A_{1}$ can issue queries to the oracles: $O_{S K G e n}$ , $O_{R K G e n}$ , $O_{A u t h}$ , $O_{D e c}$ .
3.: Challenge: $A_{1}$ sends identities $σ^{*}, {r c v}^{*}$ and equal-length messages $m_{0}^{*}, m_{1}^{*}$ to $C$ . Subsequently, $C$ randomly selects $x \in {0, 1}$ and answers $A_{1}$ with the challenge ciphertext $C^{*} = E n c (p p, e k_{σ^{*}}, {r c v}^{*}, m_{x}^{*})$ .
4.: Phase 2: $A_{1}$ makes queries like in $P h a s e$ 1.
5.: Guess: $A_{1}$ answers a guess $x^{'} \in {0, 1}$ and is winning when $x = x^{'}$ . $A_{1}$ ’s advantage is defined as $A d v_{I B M E - E T, A_{1}}^{I N D - I D - C C A} (λ) = |$ Pr $[x = x^{'}] - \frac{1}{2} | .$

In the above game, the constraint is that

A_{1}

cannot ask the following queries:

O_{R K G e n} ({r c v}^{*})

O_{A u t h} (σ^{*}, {r c v}^{*})

O_{D e c} ({r c v}^{*}, σ^{*}, C^{*})

Definition 2

(OW-ID-CCA). Regarding

A_{2}

, the IBME-ET scheme meets OW-ID-CCA security when no PPT

A_{2}

is winning the game below with a non-negligible advantage:

1.: Setup: Same as Definition 1.
2.: Phase 1: $A_{2}$ can issue queries to the oracles: $O_{S K G e n}$ , $O_{R K G e n}$ , $O_{A u t h}$ , $O_{D e c}$ .
3.: Challenge: $A_{2}$ sends identities $σ^{*}, {r c v}^{*}$ to $C$ . Subsequently, $C$ randomly chooses a message $m^{*} \in {0, 1}^{λ}$ and answers to $A_{2}$ with the challenge ciphertext $C^{*} = E n c (p p, e k_{σ^{*}}, {r c v}^{*}, m^{*})$ .
4.: Phase 2: $A_{2}$ makes queries like in $P h a s e$ 1.
5.: Guess: $A_{2}$ answers a guess $m^{'}$ and is winning when $m^{*} = m^{'}$ . $A_{2}$ ’s advantage is defined as $A d v_{I B M E - E T, A_{2}}^{O W - I D - C C A} (λ) =$ Pr $[m^{*} = m^{'}] .$

In the above game, the constraints is that

A_{2}

cannot ask the following queries:

O_{R K G e n} ({r c v}^{*})

O_{D e c} ({r c v}^{*}, σ^{*}, C^{*})

Definition 3

(ANON-ID-CCA). Regarding

A_{3}

, the IBME-ET scheme meets ANON-ID-CCA security when no PPT

A_{3}

is winning the game below with a non-negligible advantage:

1.: Setup: Same as Definition 1.
2.: Phase 1: $A_{3}$ can issue queries to the oracles: $O_{S K G e n}$ , $O_{R K G e n}$ , $O_{A u t h}$ , $O_{E n c}$ , $O_{D e c}$ .
3.: Challenge: $A_{3}$ sends identities $({s n d}_{0}^{*}, ρ_{0}^{*})$ , $({s n d}_{1}^{*}, ρ_{1}^{*})$ and a message $m^{*}$ to $C$ . Subsequently, $C$ randomly chooses $x \in {0, 1}$ and answers to $A_{3}$ with the challenge ciphertext $C^{*} = E n c (p p, e k_{{s n d}_{x}^{*}}, ρ_{x}^{*}, m^{*})$ and the challenge trapdoor $t d_{({s n d}_{x}^{*}, ρ_{x}^{*})} = A u t h (p p, {s n d}_{x}^{*}, d k_{ρ_{x}^{*}})$ .
4.: Phase 2: $A_{3}$ makes queries like in $P h a s e$ 1.
5.: Guess: $A_{3}$ answers a guess $x^{'} \in {0, 1}$ and is winning when $x = x^{'}$ . $A_{3}$ ’s advantage is defined as $A d v_{I B M E - E T, A_{3}}^{A N O N - I D - C C A} (λ) = |$ Pr $[x = x^{'}] - \frac{1}{2} | .$

In the above game, the constraint is that

A_{3}

cannot ask the following queries:

$O_{S K G e n} ({s n d}_{0}^{*})$ , $O_{S K G e n} ({s n d}_{1}^{*})$ , $O_{E n c} ({s n d}_{0}^{*}, ρ_{0}^{*}, *)$ and $O_{E n c} ({s n d}_{1}^{*}, ρ_{1}^{*}, *)$ .
$O_{R K G e n} (ρ_{0}^{*})$ , $O_{R K G e n} (ρ_{1}^{*})$ , $O_{A u t h} ({s n d}_{0}^{*}, ρ_{0}^{*})$ and $O_{A u t h} ({s n d}_{1}^{*}, ρ_{1}^{*})$ .
$O_{D e c} (ρ_{0}^{*}, {s n d}_{0}^{*}, C^{*})$ , $O_{D e c} (ρ_{1}^{*}, {s n d}_{1}^{*}, C^{*})$ .

Definition 4

(sUF-ID-CMA). Regarding

A_{4}

, the IBME-ET scheme meets sUF-ID-CMA security when no PPT

A_{4}

is winning the game below with a non-negligible advantage:

1.: Setup: Same as Definition 1.
2.: Queries: $A_{4}$ can issue queries to the oracles: $O_{S K G e n}$ , $O_{R K G e n}$ , $O_{A u t h}$ , $O_{E n c}$ , $O_{D e c}$ .
3.: Forgery: $A_{4}$ answers a triple $({s n d}^{*}, ρ^{*}, C^{*})$ . $A_{4}$ is winning when $m^{*} = D e c (p p, d k_{ρ^{*}}$ , ${s n d}^{*}, C^{*}) \neq ⊥$ . $A_{4}$ ’s advantage is defined as $A d v_{I B M E - E T, A_{4}}^{s U F - I D - C M A} (λ) =$ Pr $[A_{4}$ wins].

In the above game, the constraint is that

A_{4}

cannot make the following queries:

O_{S K G e n} ({s n d}^{*})

and

O_{R K G e n} (ρ^{*})

. Furthermore,

C^{*}

cannot be an output of

O_{E n c} ({s n d}^{*}, ρ^{*}, *)

4. Our Construction

The IBME-ET scheme is concretely constructed as below:

Setup( $λ$ ): The following steps are taken:
- Randomly select the generators $g \in G$ along with $\hat{g} \in \hat{G}$ .
- Randomly select numbers $s, α, β_{0}, β_{1} \in Z_{q}^{*}$ , and set $g_{1} = g^{α}$ , $f = g^{β_{0}}$ , $\hat{f} = {\hat{g}}^{β_{0}}$ , $h = g^{β_{1}}$ , $\hat{h} = {\hat{g}}^{β_{1}}$ .
- Secure hash functions are defined: $H : G_{T} \to Z_{q}^{*}$ , $H_{1} : {0, 1}^{*} \to G$ , $H_{2} : {0, 1}^{*} \to \hat{G}$ , $H_{3} : {0, 1}^{*} \to \hat{G}$ , $H_{4} : G_{T} \to Z_{q}^{*}$ , $H_{5} : {0, 1}^{λ + l} \to Z_{q}^{*}$ , $H_{6} : G_{T}^{2} \times G^{3} \to {0, 1}^{λ + l}$ , $H_{7} : {0, 1}^{λ} \to \hat{G}$ , and $H_{8} : G_{T} \to \hat{G}$ .
- Return the master key $m k$ along with the system parameters $p p$ , where
  
  $m k = (s, α),$
  
  $p p = (G, g, \hat{g}, g_{1}, f, h, \hat{f}, \hat{h}, H, H_{1}, H_{2}, H_{3}, H_{4}, H_{5}, H_{6}, H_{7}, H_{8}) .$
SKGen( $p p, m k, σ$ ): Let $m k = (s, α)$ . This algorithm produces the encryption key $e k_{σ} = {H_{1} (σ)}^{s} .$
RKGen( $p p, m k, ρ$ ): Let $m k = (s, α)$ . This algorithm produces the decryption key $d k_{ρ} = (d_{1}, d_{2}, d_{3}) = ({H_{3} (ρ)}^{s}, {H_{2} (ρ)}^{α}, {H_{3} (ρ)}^{α})$ .
Enc( $p p, e k_{σ}, r c v, m$ ): Let $r c v = ρ$ and $m \in {0, 1}^{λ}$ . The ciphertext $C = (C_{0}, C_{1}, C_{2}, C_{3}, C_{4})$ is calculated as below:
- Randomly select $r \in Z_{q}^{*}$ and $k \in {0, 1}^{l}$ , and calculate $R = H_{5} (m, k)$ .
- Calculate $η = e (e k_{σ}, H_{3} (ρ))$ , $ω_{1} = {e (g_{1}, H_{2} (ρ))}^{r \cdot H_{4} (η)}$ and $ω_{2} = {e (g_{1}, H_{3} (ρ))}^{r \cdot H_{4} (η)}$ .
- Calculate the following numbers:
  
  $\begin{matrix} \{\begin{matrix} C_{0} = g^{R}, \\ C_{1} = g^{r}, \\ C_{2} = {(f h^{H (η)})}^{r}, \\ C_{3} = (m ‖ k) \oplus H_{6} (ω_{1}, η, C_{0}, C_{1}, C_{2}), \\ C_{4} = H_{7} {(m)}^{R} \cdot H_{8} (ω_{2}) . \end{matrix} \end{matrix}$
$D e c$ ( $p p, d k_{ρ}, s n d, C$ ): Let $d k_{ρ} = (d_{1}, d_{2}, d_{3})$ , $s n d = σ$ . The following steps are taken:
- Calculate $η = e (H_{1} (σ), d_{1}), ω_{1} = e (C_{1}, d_{2}^{H_{4} (η)})$ and $ω_{2} = e (C_{1}, d_{3}^{H_{4} (η)})$ .
- Obtain $m^{'} ‖ k^{'}$ by computing $C_{3} \oplus H_{6} (ω_{1}, η, C_{0}, C_{1}, C_{2})$ .
- Calculate $R^{'} = H_{5} (m^{'}, k^{'})$ .
- If $C_{0} = g^{R^{'}}$ and $C_{4} = H_{7} {(m^{'})}^{R^{'}} \cdot H_{8} (ω_{2})$ hold, answer $m^{'}$ ; otherwise, answer ⊥.
Auth( $p p, s n d, d k_{ρ}$ ): Let $d k_{ρ} = (d_{1}, d_{2}, d_{3})$ and $s n d = σ$ . The following steps are taken:
- Randomly select $y \in Z_{q}^{*}$ , and calculate $η = e (H_{1} (σ), d_{1})$ .
- Return the trapdoor $t d_{(s n d, ρ)} = (y_{1}, y_{2}) = (d_{3}^{H_{4} (η)} {(\hat{f} {\hat{h}}^{H (η)})}^{y}, {\hat{g}}^{y})$ .
Test( $p p, C_{(σ_{A}, {r c v}_{A})}, t d_{({s n d}_{A}, ρ_{A})}, C_{(σ_{B}, {r c v}_{B})}, t d_{({s n d}_{B}, ρ_{B})}$ ): Let $C_{(σ_{A}, {r c v}_{A})} = (C_{σ_{A}, {r c v}_{A}, 0},$ $C_{σ_{A}, {r c v}_{A}, 1}$ , $C_{σ_{A}, {r c v}_{A}, 2},$ $C_{σ_{A}, {r c v}_{A}, 3}, C_{σ_{A}, {r c v}_{A}, 4})$ , $t d_{({s n d}_{A}, ρ_{A})} = (y_{{s n d}_{A}, ρ_{A}, 1},$ $y_{{s n d}_{A}, ρ_{A}, 2})$ , $C_{(σ_{B}, {r c v}_{B})} = (C_{σ_{B}, {r c v}_{B}, 0}$ , $C_{σ_{B}, {r c v}_{B}, 1}, C_{σ_{B}, {r c v}_{B}, 2},$ $C_{σ_{B}, {r c v}_{B}, 3}, C_{σ_{B}, {r c v}_{B}, 4})$ and $t d_{({s n d}_{B}, ρ_{B})}) = (y_{{s n d}_{B}, ρ_{B}, 1}, y_{{s n d}_{B}, ρ_{B}, 2})$ . The following steps are taken:
- Calculate
  
  $ω_{A, 2} = e (C_{σ_{A}, {r c v}_{A}, 1}, y_{s n d_{A}, ρ_{A}, 1}) / e (C_{σ_{A}, {r c v}_{A}, 2}, y_{s n d_{A}, ρ_{A}, 2}),$
  
  $ω_{B, 2} = e (C_{σ_{B}, {r c v}_{B}, 1}, y_{s n d_{B}, ρ_{B}, 1}) / e (C_{σ_{B}, {r c v}_{B}, 2}, y_{s n d_{B}, ρ_{B}, 2}) .$
- Calculate
  
  $K_{A} = C_{σ_{A}, {r c v}_{A}, 4} / H_{8} (ω_{A, 2}),$
  
  $K_{B} = C_{σ_{B}, {r c v}_{B}, 4} / H_{8} (ω_{B, 2}) .$
- Check whether $e (C_{σ_{A}, {r c v}_{A}, 0}, K_{B}) = e (C_{σ_{B}, {r c v}_{B}, 0}, K_{A})$ holds. When it holds, answer 1 or 0 otherwise.

Correctness: The proposed scheme is correct in accordance with the correctness definition:

Regarding Condition 1, when $σ = s n d$ and $ρ = r c v$ , we have

$\begin{matrix} η = e (e k_{σ}, H_{3} (ρ)) = e (H_{1} (σ), H_{3} {(ρ))}^{s} = e (H_{1} (σ), d_{1}), \\ ω_{1} = {e (g_{1}, H_{2} (ρ))}^{r \cdot H_{4} (η)} = e {(g, H_{2} (ρ))}^{r α \cdot H_{4} (η)} = e (C_{1}, d_{2}^{H_{4} (η)}), \\ C_{3} \oplus H_{6} (ω_{1}, η, C_{0}, C_{1}, C_{2}) = (m ‖ k) \oplus H_{6} (ω_{1}, η, C_{0}, C_{1}, C_{2}) \oplus H_{6} (ω_{1}, η, C_{0}, C_{1}, C_{2}) = m ‖ k . \end{matrix}$

Thus, when $σ = s n d$ and $ρ = r c v$ , $D e c (p p, d k_{ρ}, s n d, E n c (p p, e k_{σ}, r c v, m)) = m$ always holds.
Regarding Condition 2, if $σ_{A} = {s n d}_{A} \land {r c v}_{A} = ρ_{A}$ $\land σ_{B} = {s n d}_{B} \land {r c v}_{B} = ρ_{B}$ $\land m_{A} = m_{B}$ , we have

$\begin{matrix} \frac{e (C_{σ_{A}, ρ_{A}, 1}, y_{σ_{A}, ρ_{A}, 1})}{e (C_{σ_{A}, ρ_{A}, 2}, y_{σ_{A}, ρ_{A}, 2})} & = \frac{e (g^{r_{A}}, d_{A, 3}^{H_{4} (η_{A})} {(\hat{f} {\hat{h}}^{H (η_{A})})}^{y_{A}})}{e ({(f h^{H (η_{A})})}^{r_{A}}, {\hat{g}}^{y_{A}})} = \frac{e (g^{r_{A}}, d_{A, 3}^{H_{4} (η_{A})}) \cdot e {(g, \hat{f} {\hat{h}}^{H (η_{A})})}^{r_{A} y_{A}}}{e {(f h^{H (η_{A})}, \hat{g})}^{r_{A} y_{A}}} \\ = \frac{e (g^{r_{A}}, d_{A, 3}^{H_{4} (η_{A})}) \cdot e {(g, {\hat{g}}^{β_{0} + β_{1} H (η_{A})})}^{r_{A} y_{A}}}{e {(g^{β_{0} + β_{1} H (η_{A})}, \hat{g})}^{r_{A} y_{A}}} = e (g^{r_{A}}, d_{A, 3}^{H_{4} (η_{A})}) \\ = e {(g, H_{3} (ρ_{A}))}^{r_{A} α \cdot H_{4} (η_{A})} = {e (g_{1}, H_{3} (ρ_{A}))}^{r_{A} \cdot H_{4} (η_{A})} = ω_{A, 2}, \\ \frac{e (C_{σ_{B}, ρ_{B}, 1}, y_{σ_{B}, ρ_{B}, 1})}{e (C_{σ_{B}, ρ_{B}, 2}, y_{σ_{B}, ρ_{B}, 2})} & = \frac{e (g^{r_{B}}, d_{B, 3}^{H_{4} (η_{B})} {(\hat{f} {\hat{h}}^{H (η_{B})})}^{y_{B}})}{e ({(f h^{H (η_{B})})}^{r_{B}}, {\hat{g}}^{y_{B}})} = \frac{e (g^{r_{B}}, d_{B, 3}^{H_{4} (η_{B})}) \cdot e {(g, \hat{f} {\hat{h}}^{H (η_{B})})}^{r_{B} y_{B}}}{e {(f h^{H (η_{B})}, \hat{g})}^{r_{B} y_{B}}} \\ = \frac{e (g^{r_{B}}, d_{B, 3}^{H_{4} (η_{B})}) \cdot e {(g, {\hat{g}}^{β_{0} + β_{1} H (η_{B})})}^{r_{B} y_{B}}}{e {(g^{β_{0} + β_{1} H (η_{B})}, \hat{g})}^{r_{B} y_{B}}} = e (g^{r_{B}}, d_{B, 3}^{H_{4} (η_{B})}) \\ = e {(g, H_{3} (ρ_{B}))}^{r_{B} α \cdot H_{4} (η_{B})} = {e (g_{1}, H_{3} (ρ_{B}))}^{r_{B} \cdot H_{4} (η_{B})} = ω_{B, 2} . \end{matrix}$

$\begin{matrix} K_{A} = \frac{C_{σ_{A}, ρ_{A}, 4}}{H_{8} (ω_{A, 2})} = \frac{H_{7} {(m_{A})}^{R_{A}} \cdot H_{8} (ω_{A, 2})}{H_{8} (ω_{A, 2})} = H_{7} {(m_{A})}^{R_{A}}, \\ K_{B} = \frac{C_{σ_{B}, ρ_{B}, 4}}{H_{8} (ω_{B, 2})} = \frac{H_{7} {(m_{B})}^{R_{B}} \cdot H_{8} (ω_{B, 2})}{H_{8} (ω_{B, 2})} = H_{7} {(m_{B})}^{R_{B}}, \\ e (C_{σ_{A}, ρ_{A}, 0}, K_{B}) = e (g^{R_{A}}, H_{7} {(M_{B})}^{R_{B}}) = e {(g, H_{7} (M_{B}))}^{R_{A} R_{B}}, \\ e (C_{σ_{B}, ρ_{B}, 0}, K_{A}) = e (g^{R_{B}}, H_{7} {(M_{A})}^{R_{A}}) = e {(g, H_{7} (M_{A}))}^{R_{A} R_{B}} . \end{matrix}$

If $σ_{A} = {s n d}_{A} \land {r c v}_{A} = ρ_{A}$ $\land σ_{B} = {s n d}_{B} \land {r c v}_{B} = ρ_{B}$ $\land m_{A} = m_{B}$ , then $e (C_{σ_{A}, ρ_{A}, 0}, K_{B}) = e (C_{σ_{B}, ρ_{B}, 0}, K_{A})$ , so $T e s t (p p, C_{(σ_{A}, {r c v}_{A})}, t d_{(s n d_{A}, ρ_{A})}, C_{(σ_{B}, {r c v}_{B})}, t d_{(s n d_{B}, ρ_{B})}) = 1;$ otherwise, $\Pr [T e s t (p p,$ $C_{(σ_{A}, {r c v}_{A})}, t d_{(s n d_{A}, ρ_{A})}, C_{(σ_{B}, {r c v}_{B})}, t d_{(s n d_{B}, ρ_{B})}) = 1]$ is negligible due to the hash functions $H_{7}$ and $H_{8}$ being collision-resistant.

5. Security Analysis

In the random oracle model, we used the method of proof by contradiction to show that if the BDH assumption and Gap-BDH assumption introduced in the preliminaries (see Section 2) hold, and our proposed IBME-ET scheme can meet confidentiality, authenticity, and anonymity in cryptography [30,31,32].

According to our IBME-ET scheme, given the ciphertext C, we have the following observations:

To reveal the message m, it is necessary to calculate $ω_{1} = {e (g_{1}, H_{2} (ρ))}^{r \cdot H_{4} (η)}$ .
To obtain $H_{7} {(m)}^{R}$ , which is used for the equality test, it is necessary to calculate $ω_{2} = {e (g_{1}, H_{3} (ρ))}^{r \cdot H_{4} (η)}$ .
To distinguish the identities of the sender and the receiver concealed in the ciphertext, it is necessary to calculate $η = e (e k_{σ}, H_{3} (ρ)) = e (H_{1} (σ), H_{3} {(ρ))}^{s}$ .
To fake any legitimate ciphertext pertaining to the sender $σ$ and the receiver $ρ$ , it is necessary to calculate $η = e (e k_{σ}, H_{3} (ρ)) = e (H_{1} (σ), H_{3} {(ρ))}^{s}$ .

Note that, regarding to the confidentiality, anonymity, and authenticity of the IBME-ET, four security models are defined by considering four distinct types of adversaries (see Section 3.3). The security proof of our scheme can be outlined as follows:

As for the confidentiality, we first used the BDH assumption to prove that our proposal meets IND-ID-CCA security regarding the Type-I adversary

A_{1}

. Given a BDH assumption instance

(g, g^{a}, g^{c}, \hat{g}, {\hat{g}}^{a}, {\hat{g}}^{b})

, we generated a simulated scheme

B

and interacted with

A_{1}

by following the IND-ID-CCA security model defined in Section 3.3.

B

simulates the oracles

O_{S K G e n}

O_{R K G e n}

O_{A u t h}

, and

O_{D e c}

to answer

A_{1}

’s queries and preserves the

L_{H}

and

L_{H_{i}} (i = 1, 2, 3, 5, 6, 7, 8)

lists to simulate the random oracles

O_{H}

and

O_{H_{i}} (i = 1, 2, 3, 5, 6, 7, 8)

. In the challenge phase,

A_{1}

sends identities

σ^{*}, {r c v}^{*}

and equal-length messages

m_{0}^{*}, m_{1}^{*}

B

. Let

{r c v}^{*} = ρ^{*}

B

randomly selects

x \in {0, 1}

and answers the challenge ciphertext

C^{*} = (C_{0}^{*}, C_{1}^{*}, C_{2}^{*}, C_{3}^{*}, C_{4}^{*}) = E n c (p p, e k_{σ^{*}}, ρ^{*}, m_{x}^{*})

A_{1}

. In the simulation, the challenge ciphertext implicitly sets

ω_{1}^{*} = e {(g, \hat{g})}^{a b c v^{*} \cdot H_{4} (η^{*})}

ω_{2}^{*} = e {(g, \hat{g})}^{a b c t^{*} \cdot H_{4} (η^{*})}

H_{6} (ω_{1}^{*}, η^{*}, C_{0}^{*},

C_{1}^{*}, C_{2}^{*}) = (m_{x} ‖ k) \oplus C_{3}^{*}

H_{8} (ω_{2}^{*})

= \frac{C_{4}^{*}}{H_{7} {(m_{x})}^{R}}

, where

g_{1} = g^{a}

H_{2} (ρ^{*}) = {\hat{g}}^{b v^{*}}

H_{3} (ρ^{*}) = {\hat{g}}^{b t^{*}}

H_{1} (σ^{*}) = g^{u^{*}}

e k_{σ^{*}} = g^{s u^{*}}

η^{*} = e {(g, \hat{g})}^{b s u^{*} t^{*}}

C_{0}^{*} = g^{R}

C_{1}^{*} = g^{c}

, and

C_{2}^{*} = g^{β_{0}^{'} c}

. Finally, in the guess phase,

A_{1}

outputs a guess

x^{'} \in {0, 1}

. The advantage of

A_{1}

for breaking our proposal is defined as

ϵ = |

[x = x^{'}] - \frac{1}{2} | .

ϵ

is non-negligible, then the tuple

[ω_{1}^{*}, η^{*}, C_{0}^{*}, C_{1}^{*}, C_{2}^{*}, δ^{*}]

is documented in

L_{H_{6}}

with non-negligible probability. If

B

selects the right tuple from

L_{H_{6}}

B

can return the BDH instance solution

{ω_{1}^{*}}^{{(v^{*} H_{4} (η^{*}))}^{- 1}}

(= e {(g, \hat{g})}^{a b c})

. As a result, the BDH assumption can be addressed by

B

with non-negligible advantage if

A_{1}

is able to break our proposal with non-negligible advantage.

Subsequently, as for the confidentiality, we used the BDH assumption to prove that our proposal meets OW-ID-CCA security regarding the Type-II adversary

A_{2}

. Given a BDH assumption instance

(g, g^{a}, g^{c},

\hat{g}, {\hat{g}}^{a}, {\hat{g}}^{b})

, we generated a simulated scheme

B

and interacted with

A_{2}

by following the OW-ID-CCA security model defined in Section 3.3.

B

simulates the oracles

O_{S K G e n}

O_{R K G e n}

O_{A u t h}

, and

O_{D e c}

to answer

A_{2}

’s queries and preserves the

L_{H}

and

L_{H_{i}} (i = 1, 2, 3, 5, 6, 7, 8)

lists to simulate the random oracles

O_{H}

and

O_{H_{i}} (i = 1, 2, 3, 5, 6, 7, 8)

. In the challenge phase,

A_{2}

sends identities

σ^{*}, {r c v}^{*}

B

. Let

{r c v}^{*} = ρ^{*}

B

randomly chooses a message

m^{*} \in {0, 1}^{λ}

and answers the challenge ciphertext

C^{*} = (C_{0}^{*}, C_{1}^{*}, C_{2}^{*}, C_{3}^{*}, C_{4}^{*}) = E n c (p p, e k_{σ^{*}}, ρ^{*}, m^{*})

A_{2}

. In the simulation, the challenge ciphertext implicitly sets

ω_{1}^{*} = e {(g, \hat{g})}^{a b c v^{*} \cdot H_{4} (η^{*})}

H_{6} (ω_{1}^{*}, η^{*}, C_{0}^{*}, C_{1}^{*}, C_{2}^{*})

= (m^{*} ‖ k) \oplus C_{3}^{*}

, where

g_{1} = g^{a}

H_{2} (ρ^{*}) = {\hat{g}}^{b v^{*}}

H_{3} (ρ^{*}) = {\hat{g}}^{t^{*}}

H_{1} (σ^{*}) = g^{u^{*}}

e k_{σ^{*}} = g^{s u^{*}}

η^{*} = e {(g, \hat{g})}^{b s u^{*} t^{*}}

C_{0}^{*} = g^{R}

C_{1}^{*} = g^{c}

C_{2}^{*} = g^{β_{0}^{'} c}

, and

C_{4}^{*} = {H_{7} (m^{*})}^{R} \cdot H_{8} (e (g^{c}, {\hat{g}}^{a t^{*} \cdot H_{4} (η^{*})}))

. Finally, in the guess phase,

A_{2}

outputs a guess

m^{'}

. The advantage of

A_{2}

for breaking our proposal is defined as

ϵ = |

[m^{*} = m^{'}] |

. If

ϵ

is non-negligible, then the tuple

[ω_{1}^{*}, η^{*}, C_{0}^{*}, C_{1}^{*}, C_{2}^{*}, δ^{*}]

is documented in

L_{H_{6}}

with non-negligible probability. If

B

selects the right tuple from

L_{H_{6}}

B

can return the BDH instance solution

{ω_{1}^{*}}^{{(v^{*} H_{4} (η^{*}))}^{- 1}} (= e {(g, \hat{g})}^{a b c})

. As a result, the BDH assumption can be addressed by

B

with non-negligible advantage if

A_{2}

is able to break our proposal with non-negligible advantage.

As for the anonymity, we used the Gap-BDH assumption to prove that our proposal meets ANON-ID-CCA security regarding the Type-III adversary

A_{3}

. Given a Gap-BDH assumption instance

(g, g^{a}, g^{c}, \hat{g}, {\hat{g}}^{a}, {\hat{g}}^{b},

O_{DBDH})

, we generated a simulated scheme

B

and interacted with

A_{3}

by following the ANON-ID-CCA security model defined in Section 3.3.

B

simulates the oracles

O_{H}

O_{H_{i}} (i = 1, 2, 3, 4, 5, 6, 7, 8)

O_{S K G e n}

O_{R K G e n}

O_{A u t h}

O_{E n c}

, and

O_{D e c}

to answer

A_{3}

’s queries. In the challenge phase,

A_{3}

sends identities

({s n d}_{0}^{*}, ρ_{0}^{*})

({s n d}_{1}^{*}, ρ_{1}^{*})

and a message

m^{*}

B

. Let

{s n d}_{0}^{*} = σ_{0}^{*}

{s n d}_{1}^{*} = σ_{1}^{*}

B

randomly chooses

x \in {0, 1}

and answers the challenge ciphertext

C^{*} = (C_{0}^{*}, C_{1}^{*}, C_{2}^{*}, C_{3}^{*}, C_{4}^{*}) = E n c (p p, e k_{σ_{x}^{*}}, ρ_{x}^{*}, m^{*})

and the challenge trapdoor

t d_{(σ_{x}^{*}, ρ_{x}^{*})} = (y_{1}, y_{2}) = A u t h (p p, σ_{x}^{*}, d k_{ρ_{x}^{*}})

A_{3}

. In the simulation, the challenge ciphertext implicitly sets

η^{*} = e {(g, \hat{g})}^{a b c u_{x}^{*} t_{x}^{*}}

ω_{1}^{*} = e {(g^{a α^{'}}, {\hat{g}}^{b})}^{r Ω v_{x}^{*}}

C_{3}^{*} = (m^{*} ‖ k) \oplus H_{6} (ω_{1}^{*}, η^{*}, C_{0}^{*}, C_{1}^{*}, C_{2}^{*})

, where

g_{1} = g^{a α^{'}}

H_{1} (σ_{0}^{*}) = g^{c u_{i_{x}^{*}}}

H_{2} (ρ_{x}^{*}) = {\hat{g}}^{b v_{j_{t}^{*}}}

H_{3} (ρ_{x}^{*}) = {\hat{g}}^{b v_{t_{x}^{*}}}

ω_{2}^{*} = e {(g^{a α^{'}}, {\hat{g}}^{b})}^{r {\tilde{Ω}}_{x x}}

H (η^{*}) = I = I_{x x}

H_{4} (η^{*}) = Ω = \frac{{\tilde{Ω}}_{x x}}{t_{x}^{*}}

C_{0}^{*} = g^{R}

C_{1}^{*} = g^{r}

C_{2}^{*} = {(f h^{I})}^{r}

, and

C_{4}^{*} = H_{7} {(m^{*})}^{R} \cdot H_{8} (ω_{2}^{*})

Furthermore, the challenge trapdoor implicitly sets

y = \tilde{y} - b z

, where

z = \frac{t_{x} α^{'} Ω}{β_{1} I} = \frac{α^{'} {\tilde{Ω}}_{x x}}{β_{1} I}

y_{1} = {\hat{g}}^{β_{0} (\tilde{y} - b z)} {\hat{g}}^{a β_{1} I \tilde{y}}

y_{2} = {\hat{g}}^{\tilde{y} - b z}

. Finally, in the guess phase,

A_{3}

outputs a guess

x^{'} \in {0, 1}

. The advantage of

A_{3}

for breaking our proposal is defined as

ϵ = |

[x = x^{'}] - \frac{1}{2} | .

ϵ

is non-negligible,

η^{*} = e {(g, \hat{g})}^{a b c u_{x}^{*} t_{x}^{*}}

has been queried to

O_{H}

with non-negligible probability. With

O_{DBDH} (g, g^{a}, g^{c}, \hat{g},

{\hat{g}}^{a}, {\hat{g}}^{b}, {η^{*}}^{{(u_{i_{x}^{*}} t_{j_{x}^{*}})}^{- 1}}) = 1

B

can return the Gap-BDH instance solution

{η^{*}}^{{(u_{i_{x}^{*}} t_{j_{x}^{*}})}^{- 1}} (= e {(g, \hat{g})}^{a b c})

. As a result, the Gap-BDH assumption can be addressed by

B

with non-negligible advantage if

A_{3}

is able to break our proposal with non-negligible advantage.

As for the authenticity, we used the Gap-BDH assumption to prove that our proposal meets sUF-ID-CMA security regarding the Type-IV adversary

A_{4}

. Given a Gap-BDH assumption instance

(g, g^{a}, g^{c}, \hat{g}, {\hat{g}}^{a}, {\hat{g}}^{b},

O_{DBDH})

, we generated a simulated scheme

B

and interacted with

A_{4}

by following the sUF-ID-CMA security model defined in Section 3.3.

B

simulates the oracles

O_{H}

O_{H_{i}} (i = 1, 2, 3, 4, 5, 6, 7, 8)

O_{S K G e n}

O_{R K G e n}

O_{A u t h}

O_{E n c}

, and

O_{D e c}

to answer

A_{4}

’s queries. In the simulation, the following numbers are implicitly set

η^{*} = e {(g, \hat{g})}^{a b c}

, where

H_{1} (σ^{*}) = g^{c}

H_{3} (ρ^{*}) = {\hat{g}}^{b}

H (η^{*}) = I^{*}

H_{4} (η^{*}) = Ω^{*}

. In the forgery phase,

A_{4}

outputs a triple

(s n d^{*}, ρ^{*}, C^{*})

, where

s n d^{*} = σ^{*}

and

C^{*} = (C_{0}^{*}, C_{1}^{*}, C_{2}^{*}, C_{3}^{*}, C_{4}^{*})

. If

m^{*} = D e c (p p, d k_{ρ^{*}}, σ^{*}, C^{*}) \neq ⊥

A_{4}

wins. The advantage of

A_{4}

for breaking our proposal is defined as

ϵ =

[A_{4} wins]

. With

ϵ

and the lemma on the relationship between the chosen-identity attack and given identity attack [33], if

ϵ

is non-negligible,

η^{*} = e {(g, \hat{g})}^{a b c}

has been queried to

O_{H}

with non-negligible probability. Then,

O_{DBDH} (g, g^{a}, g^{c}, \hat{g},

{\hat{g}}^{a}, {\hat{g}}^{b}, η^{*}) = 1

B

can return the Gap-BDH instance solution

η^{*} (= e {(g, \hat{g})}^{a b c})

. As a result, the Gap-BDH assumption can be addressed by

B

with non-negligible advantage if

A_{4}

is able to break our proposal with non-negligible advantage.

Theorem 1.

For any

A_{1}

, our IBME-ET scheme meets IND-ID-CCA security on the basis of the BDH assumption.

More precisely, if

A_{1}

is able to break our proposal with the advantage ϵ, we can conceive of a PPT algorithm

B

to address the BDH assumption with the advantage

ϵ^{'} \geq \frac{1}{q_{H_{6}}} (\frac{ϵ}{q_{H_{1}} q_{H_{2}}} - \frac{q_{D}}{2^{λ + l}} - \frac{q_{H_{8}}}{q}),

where

q_{H_{i}} (i = 1, 2, 6, 8)

and

q_{D}

denote the numbers of different queries to

O_{H_{i}} (i = 1, 2, 6, 8)

and

O_{D e c}

, respectively.

Proof.

Given a BDH assumption instance

(g, g^{a}, g^{c}, \hat{g}, {\hat{g}}^{a}, {\hat{g}}^{b})

, the task of

B

is to calculate

e {(g, \hat{g})}^{a b c}

by interacting with

A_{1}

as below:

(1)

Setup:

B

randomly selects

i^{*} \in {1, 2, \dots, q_{H_{1}}}

j^{*} \in {1, 2, \dots, q_{H_{2}}}

B

randomly chooses

I^{*}, s, β_{0}^{'}, β_{1}^{'} \in Z_{q}^{*}

, calculates

g_{1} = g^{a}

f = g^{β_{0}^{'} - a β_{1}^{'} I^{*}}

h = g^{a β_{1}^{'}}

\hat{f} = {\hat{g}}^{β_{0}^{'} - a β_{1}^{'} I^{*}}

, and

\hat{h} = {\hat{g}}^{a β_{1}^{'}}

, sets

p p = (G, g, \hat{g}, g_{1}, f, h, \hat{f}, \hat{h},

H, H_{i} (i = 1, 2, 3, 4, 5, 6, 7, 8))

, and delivers this to

A_{1}

with

p p

B

implicitly sets

m k = (s, a)

, because

B

has no knowledge about a.

B

preserves the

L_{H}

and

L_{H_{i}} (i = 1, 2, 3, 5, 6, 7, 8)

lists to simulate

O_{H}

and

O_{H_{i}} (i = 1, 2, 3, 5, 6, 7, 8)

. Afterwards,

B

randomly selects

u^{*}, v^{*}, t^{*} \in Z_{q}^{*}

(2)

Phase1:

B

answers

A_{1}

’s queries.

$O_{H} (η)$ : When $η \neq e {(g, \hat{g})}^{b s u^{*} t^{*}}$ , $B$ randomly selects $I \in Z_{q}^{*}$ , inserts a tuple $[η, I]$ into $L_{H}$ , and answers I. Otherwise, $B$ answers $I^{*}$ .
$O_{H_{1}} (σ_{i})$ : Suppose $σ_{i}$ as the i-th different query. When $i \neq i^{*}$ , $B$ randomly selects $u_{i} \in Z_{q}^{*}$ , inserts a tuple $[σ_{i}, u_{i}]$ into $L_{H_{1}}$ , and returns $g^{u_{i}}$ . Otherwise, $B$ has $u_{i^{*}} = u^{*}$ , inserts a tuple $[σ_{i^{*}}, u_{i^{*}}]$ into $L_{H_{1}}$ , and returns $g^{u_{i^{*}}}$ .
$O_{H_{2}} (ρ_{j})$ : Suppose $ρ_{j}$ as the j-th different query. When $j \neq j^{*}$ , $B$ randomly selects $v_{j} \in Z_{q}^{*}$ , inserts a tuple $[ρ_{j}, v_{j}]$ into $L_{H_{2}}$ , and returns ${\hat{g}}^{v_{j}}$ . Otherwise, $B$ has $v_{j^{*}} = v^{*}$ , inserts a tuple $[ρ_{j^{*}}, v_{j^{*}}]$ into $L_{H_{2}}$ , and returns ${\hat{g}}^{b v_{j^{*}}}$ .
$O_{H_{3}} (ρ_{j})$ : $B$ performs a simulation algorithm to query $O_{H_{2}} (ρ_{j})$ . Subsequently, $B$ searches the tuple $[ρ_{j}, v_{j}]$ in $L_{H_{2}}$ . When $j \neq j^{*}$ , $B$ selects $t_{j} \in Z_{q}^{*}$ randomly, inserts a tuple $[ρ_{j}, t_{j}]$ into $L_{H_{3}}$ , and returns ${\hat{g}}^{t_{j}}$ . Otherwise, $B$ has $t_{j^{*}} = t^{*}$ , inserts a tuple $[ρ_{j^{*}}, t_{j^{*}}]$ into $L_{H_{3}}$ , and returns ${\hat{g}}^{b t_{j^{*}}}$ .
$O_{H_{5}} (m, k)$ : $B$ randomly chooses $R \in Z_{q}^{*}$ , inserts a tuple $[m, k, R]$ into $L_{H_{5}}$ , and answers R.
$O_{H_{6}} (ω_{1}, η, C_{0}, C_{1}, C_{2})$ : $B$ randomly chooses $δ \in {0, 1}^{λ + l}$ , inserts a tuple $[ω_{1}, η, C_{0}, C_{1}, C_{2}, δ]$ into $L_{H_{6}}$ , and answers $δ$ .
$O_{H_{7}} (m)$ : $B$ randomly selects $h_{7} \in \hat{G}$ , inserts a tuple $[m, h_{7}]$ into $L_{H_{7}}$ , and returns $h_{7}$ .
$O_{H_{8}} (ω_{2})$ : $B$ randomly selects $π \in \hat{G}$ , inserts a tuple $[ω_{2}, π]$ into $L_{H_{8}}$ , and returns $π$ .
$O_{S K G e n} (σ_{i})$ : $B$ performs a simulation algorithm to query $O_{H_{1}} (σ_{i})$ . There is a tuple $[σ_{i}, u_{i}]$ in $L_{H_{1}}$ . Next, $B$ returns $e k_{σ_{i}} = g^{s u_{i}}$ .
$O_{R K G e n} (ρ_{j})$ : $B$ performs a simulation algorithm to query $O_{H_{3}} (ρ_{j})$ . There are a tuple $[ρ_{j}, v_{j}]$ in $L_{H_{2}}$ and a tuple $[ρ_{j}, t_{j}]$ in $L_{H_{3}}$ . When $j \neq j^{*}$ , $B$ returns $d k_{ρ_{j}} = (d_{1}, d_{2}, d_{3}) = ({\hat{g}}^{s t_{j}}, {\hat{g}}^{a v_{j}}, {\hat{g}}^{a t_{j}})$ . Otherwise, $B$ is aborted by failure.
$O_{D e c} (ρ_{j}, s n d, C)$ : Let $s n d = σ_{i}$ . $B$ performs a simulation algorithm to query $O_{H_{3}} (ρ_{j})$ and $O_{H_{1}} (σ_{i})$ .
-
When $j \neq j^{*}$ , $B$ can query $O_{R K G e n} (ρ_{j})$ to obtain $d k_{ρ_{j}}$ and returns the outcome of the algorithm $D e c (p p, d k_{ρ_{j}}, σ_{i}, C)$ .
-
Otherwise, $B$ can query $O_{S K G e n} (σ_{i})$ to obtain $e k_{σ_{i}}$ and calculates $η = e (e k_{σ_{i}},$ $H_{3} (ρ_{j}))$ . For each tuple $[ω_{1}, η, C_{0}, C_{1}, C_{2}, δ]$ in $L_{H_{6}}$ , $B$ calculates $m^{'} ‖ k^{'} = C_{3} \oplus δ$ and calculates $R^{'} = H_{5} (m^{'}, k^{'})$ . If $C_{0} = g^{R^{'}}$ and there exists a tuple $[ω_{2}, π]$ in $L_{H_{8}}$ such that $C_{4} = H_{7} {(m^{'})}^{R^{'}} \cdot π$ holds, it outputs $m^{'}$ . Once $L_{H_{8}}$ has no such tuple, $B$ outputs ⊥.
$O_{A u t h} (s n d, ρ_{j})$ : Let $s n d = σ_{i}$ . $B$ performs a simulation algorithm to query $O_{H_{3}} (ρ_{j})$ and $O_{H_{1}} (σ_{i})$ . When $j \neq j^{*}$ , $B$ can query $O_{R K G e n} (ρ_{j})$ to obtain $d k_{ρ_{j}}$ , returns $t d_{(σ_{i}, ρ_{j})} = A u t h (p p, σ_{i}, d k_{ρ_{j}})$ . Otherwise, $B$ executes the following operations:
-
When $(i, j) = (i^{*}, j^{*})$ , $B$ is aborted by failure.
-
Otherwise, $L_{H_{2}}$ has a tuple $[ρ_{j^{*}}, v_{j^{*}}]$ and $L_{H_{3}}$ has a tuple $[ρ_{j^{*}}, t_{j^{*}}]$ , and $B$ can query $O_{S K G e n} (σ_{i})$ to obtain $e k_{σ_{i}}$ , calculates $η = e (e k_{σ_{i}}, H_{3} (ρ_{j}))$ , $I = H (η)$ and $Ω = H_{4} (η)$ , randomly selects $\tilde{y} \in Z_{q}^{*}$ , calculates $z = \frac{t_{j^{*}} Ω}{β_{1}^{'} (I - I^{*})}$ , implicitly sets $y = \tilde{y} - b z$ , and returns $t d_{(σ_{i}, ρ_{j^{*}})} =$ $(y_{1}, y_{2}) = ({\hat{g}}^{β_{0}^{'} (\tilde{y} - b z)} {\hat{g}}^{a β_{1}^{'} (I - I^{*}) \tilde{y}},$ ${\hat{g}}^{\tilde{y} - b z})$ . $t d_{(σ_{i}, ρ_{j^{*}})} = (y_{1}, y_{2})$ is a valid random trapdoor according to $ρ_{j^{*}}$ and $σ_{i}$ , where

$\begin{matrix} y_{1} & = {\hat{g}}^{β_{0}^{'} (\tilde{y} - b z)} {\hat{g}}^{a β_{1}^{'} (I - I^{*}) \tilde{y}} = {\hat{g}}^{a b t_{j^{*}} \cdot Ω} {\hat{g}}^{β_{0}^{'} y} {\hat{g}}^{a β_{1}^{'} (I - I^{*}) y} = d_{3}^{Ω} {\hat{g}}^{(β_{0}^{'} - a β_{1} I^{*} + a β_{1}^{'} I) y} = d_{3}^{Ω} {(\hat{f} {\hat{h}}^{I})}^{y}, \\ y_{2} & = {\hat{g}}^{\tilde{y} - b z} = {\hat{g}}^{y} . \end{matrix}$

(3)

Challenge:

A_{1}

offers equal-length messages

m_{0}^{*}, m_{1}^{*} \in {0, 1}^{λ}

along with the pair of sender/receiver identities (

σ^{*}, {r c v}^{*}

) to

B

. Let

{r c v}^{*} = ρ^{*}

. Afterwards,

B

utilizes a simulation algorithm to query

O_{H_{1}} (σ^{*})

and

O_{H_{3}} (ρ^{*})

-: When the $i^{*}$ -th tuple in $L_{H_{1}}$ is $[σ^{*}, u^{*}]$ and the $j^{*}$ -th tuple in $L_{H_{2}}$ is $[ρ^{*}, v^{*}]$ , $B$ randomly selects $x \in {0, 1}$ , $C_{3}^{*} \in {0, 1}^{λ + l}$ , $C_{4}^{*} \in \hat{G}$ and $k \in {0, 1}^{l}$ , calculates $e k_{σ^{*}} = g^{s u^{*}}$ , $η^{*} = e {(g, \hat{g})}^{b s u^{*} t^{*}}$ , $R = H_{5} (m_{x}, k)$ , $C_{0}^{*} = g^{R}$ , $C_{1}^{*} = g^{c}$ , and $C_{2}^{*} = g^{β_{0}^{'} c}$ , and then, sends the challenge ciphertext $C^{*} = (C_{0}^{*}, C_{1}^{*}, C_{2}^{*}, C_{3}^{*}, C_{4}^{*})$ to $A_{1}$ .
The above construction implicitly sets $ω_{1}^{*} = e {(g, \hat{g})}^{a b c v^{*} \cdot H_{4} (η^{*})}$ , $ω_{2}^{*} =$ $e {(g, \hat{g})}^{a b c t^{*} \cdot H_{4} (η^{*})}$ , $H_{6} (ω_{1}^{*}, η^{*}, C_{0}^{*},$ $C_{1}^{*}, C_{2}^{*}) = (m_{x} ‖ k) \oplus C_{3}^{*}$ , $H_{8} (ω_{2}^{*})$ $= \frac{C_{4}^{*}}{H_{7} {(m_{x})}^{R}}$ , where $g^{u^{*}} = H_{1} (σ^{*})$ , ${\hat{g}}^{b v^{*}} = H_{2} (ρ^{*})$ , ${\hat{g}}^{b t^{*}} = H_{3} (ρ^{*})$ .
-: Otherwise, $B$ is aborted by failure.

(4)

Phase2:

A_{1}

makes queries like in

P h a s e

(5)

Guess:

A_{1}

answers a guess

x^{'} \in {0, 1}

B

randomly selects a tuple

[ω_{1}^{*}, η^{*}, C_{0}^{*}, C_{1}^{*}, C_{2}^{*}, δ^{*}]

from

L_{H_{6}}

and returns the BDH instance solution

{ω_{1}^{*}}^{{(v^{*} H_{4} (η^{*}))}^{- 1}} (= e {(g, \hat{g})}^{a b c})

□

Analysis: It is obvious that the simulations of

O_{H}

O_{H_{1}}

O_{H_{2}}

O_{H_{3}}

O_{H_{5}}

, and

O_{H_{7}}

are perfect. Denote the query

O_{H_{6}} (e {(g, \hat{g})}^{a b c v^{*} \cdot H_{4} (η^{*})}, η^{*}, C_{0}^{*}, C_{1}^{*}, C_{2}^{*})

as the event

A s k H_{6}^{*}

. Denote the query

O_{H_{8}} (e {(g, \hat{g})}^{a b c t^{*} \cdot H_{4} (η^{*})})

as the event

A s k H_{8}^{*}

. Denote the failure of

B

to decrypt the legitimate ciphertext in

O_{D e c}

as the event

D e r r

. Thus,

\Pr [D e r r] \leq \frac{q_{D}}{2^{λ + l}}

. Let

{r c v}^{*} = ρ^{*}

. Suppose

A b o r t R K

as the event in which

B

terminates upon the query

O_{R K G e n} (ρ^{*})

being issued,

A b o r t A u t h

as the event in which

B

terminates upon the query

O_{A u t h} (σ^{*}, ρ^{*})

being issued, and

A b o r t C h

as the event in which

B

terminates in the challenge phase. Clearly,

\neg A b o r t C h

implies

\neg A b o r t R K

and

\neg A b o r t A u t h

, because the queries

O_{R K G e n} (ρ^{*})

and

O_{A u t h} (σ^{*}, ρ^{*})

cannot be issued. We obtain

\Pr [\neg A b o r t C h] \geq \frac{1}{q_{H_{1}} q_{H_{2}}}

Define

E = (A s k H_{6}^{*} \lor A s k H_{8}^{*} \lor D e r r) | \neg A b o r t C h

. There is no greater over

\frac{1}{2}

advantage that

A_{1}

will gain in guessing x when E does not happen because

O_{H_{6}}

and

O_{H_{8}}

are random oracles.

\Pr [x = x^{'} | \neg E] = \frac{1}{2}

. Hence,

\begin{matrix} \Pr [x = x^{'}] & = \Pr [x = x^{'} | \neg E] \Pr [\neg E] + \Pr [x = x^{'} | E] \Pr [E] \leq \frac{1}{2} \Pr [\neg E] + \Pr [E] = \frac{1}{2} + \frac{1}{2} \Pr [E] . \end{matrix}

With

ϵ

, we obtain

\begin{matrix} ϵ & = | \Pr [x = x^{'}] - \frac{1}{2} | \leq \Pr [E] \leq \frac{\Pr [A s k H_{6}^{*}] + \Pr [A s k H_{8}^{*}] + \Pr [D e r r]}{\Pr [\neg A b o r t C h]} . \end{matrix}

Subsequently, we obtain

\begin{matrix} \Pr [A s k H_{6}^{*}] & \geq ϵ \Pr [\neg A b o r t C h] - \Pr [D e r r] - \Pr [A s k H_{8}^{*}] \geq \frac{ϵ}{q_{H_{1}} q_{H_{2}}} - \frac{q_{D}}{2^{λ + l}} - \frac{q_{H_{8}}}{q} . \end{matrix}

When

A s k H_{6}^{*}

happens,

A_{1}

can distinguish the simulation of the challenge ciphertext

C^{*}

. Because

O_{H_{6}} (e {(g, \hat{g})}^{a b c v^{*} \cdot H_{4} (η^{*})}, η^{*}, C_{0}^{*}, C_{1}^{*}, C_{2}^{*})

has been documented in

L_{H_{6}}

with non-negligible probability,

B

is winning when the right element is selected from

L_{H_{6}}

. Thus, the BDH assumption can be addressed by

B

with advantage

ϵ^{'} \geq \frac{1}{q_{H_{6}}} \Pr [A s k H_{6}^{*}] \geq \frac{1}{q_{H_{6}}} (\frac{ϵ}{q_{H_{1}} q_{H_{2}}} - \frac{q_{D}}{2^{λ + l}} - \frac{q_{H_{8}}}{q}) .

Theorem 2.

For any

A_{2}

, our IBME-ET scheme meets OW-ID-CCA security on the basis of the BDH assumption.

More precisely, if

A_{2}

is able to break our proposal with the advantage ϵ, we are able to conceive of a PPT algorithm

B

to address the BDH assumption with the advantage

ϵ^{'} \geq \frac{1}{q_{H_{6}}} (\frac{ϵ - \frac{1}{2^{λ}}}{q_{H_{1}} q_{H_{2}}} - \frac{q_{D}}{2^{λ + l}}),

where

q_{H_{i}} (i = 1, 2, 6)

and

q_{D}

denote the numbers of different queries to

O_{H_{i}} (i = 1, 2, 6)

and

O_{D e c}

, respectively.

Proof.

Given a BDH assumption instance

(g, g^{a}, g^{c}, \hat{g}, {\hat{g}}^{a}, {\hat{g}}^{b})

, the task of

B

is to calculate

e {(g, \hat{g})}^{a b c}

by interacting with

A_{2}

as below:

(1)

Setup:

B

executes like in the proof of Theorem 1.

(2)

Phase1:

B

answers

A_{2}

’s queries.

For $O_{H} (η)$ , $O_{H_{1}} (σ_{i})$ , $O_{H_{2}} (ρ_{j})$ , $O_{H_{5}} (m, k)$ , $O_{H_{6}} (ω_{1}, η, C_{0}, C_{1}, C_{2})$ , $O_{H_{7}} (m)$ , and $O_{H_{8}} (ω_{2})$ , $B$ executes like in the proof of Theorem 1.
$O_{H_{3}} (ρ_{j})$ : $B$ performs a simulation algorithm to query $O_{H_{2}} (ρ_{j})$ . Subsequently, $B$ searches the tuple $[ρ_{j}, v_{j}]$ in $L_{H_{2}}$ . When $j \neq j^{*}$ , $B$ randomly selects $t_{j} \in Z_{q}^{*}$ , inserts a tuple $[ρ_{j}, t_{j}]$ into $L_{H_{3}}$ , and returns ${\hat{g}}^{t_{j}}$ . Otherwise, $B$ sets $t_{j^{*}} = t^{*}$ , inserts a tuple $[ρ_{j^{*}}, t_{j^{*}}]$ into $L_{H_{3}}$ , and returns ${\hat{g}}^{t_{j^{*}}}$ .
$O_{S K G e n} (σ_{i})$ : $B$ performs a simulation algorithm to query $O_{H_{1}} (σ_{i})$ . There is a tuple $[σ_{i}, u_{i}]$ in $L_{H_{1}}$ . Next, $B$ returns $e k_{σ_{i}} = g^{s u_{i}}$ .
$O_{R K G e n} (ρ_{j})$ : $B$ performs a simulation algorithm to query $O_{H_{3}} (ρ_{j})$ . There are a tuple $[ρ_{j}, v_{j}]$ in $L_{H_{2}}$ and a tuple $[ρ_{j}, t_{j}]$ in $L_{H_{3}}$ . When $j \neq j^{*}$ , $B$ returns $d k_{ρ_{j}} = (d_{1}, d_{2}, d_{3}) = ({\hat{g}}^{s t_{j}}, {\hat{g}}^{a v_{j}}, {\hat{g}}^{a t_{j}})$ . Otherwise, $B$ is aborted by failure.
$O_{D e c} (ρ_{j}, s n d, C)$ : Let $s n d = σ_{i}$ . $B$ performs a simulation algorithm to query $O_{H_{3}} (ρ_{j})$ and $O_{H_{1}} (σ_{i})$ .
-
When $j \neq j^{*}$ , $B$ can query $O_{R K G e n} (ρ_{j})$ to obtain $d k_{ρ_{j}}$ and returns the outcome of the algorithm $D e c (p p, d k_{ρ_{j}}, σ_{i}, C)$ .
-
Otherwise, $B$ can query $O_{S K G e n} (σ_{i})$ to obtain $e k_{σ_{i}}$ and calculates $η = e (e k_{σ_{i}}, H_{3} (ρ_{j}))$ . For each tuple $[ω_{1}, η, C_{0}, C_{1}, C_{2}, δ]$ in $L_{H_{6}}$ , $B$ calculates $m^{'} ‖ k^{'} = C_{3} \oplus δ$ and calculates $R^{'} = H_{5} (m^{'}, k^{'})$ . If $C_{0} = g^{R^{'}}$ and there exists a tuple $[ω_{2}, π]$ in $L_{H_{8}}$ such that $C_{4} = H_{7} {(m^{'})}^{R^{'}} \cdot π$ holds, it outputs $m^{'}$ . When $L_{H_{8}}$ has no such tuple, $B$ outputs ⊥.
$O_{A u t h} (s n d, ρ_{j})$ : Let $s n d = σ_{i}$ . $B$ performs a simulation algorithm to query $O_{H_{3}} (ρ_{j})$ and $O_{H_{1}} (σ_{i})$ .
-
When $j \neq j^{*}$ , $B$ can query $O_{R K G e n} (ρ_{j})$ to obtain $d k_{ρ_{j}}$ and returns $t d_{(σ_{i}, ρ_{j})} = A u t h (p p, σ_{i}, d k_{ρ_{j}})$ .
-
Otherwise, there are a tuple $[ρ_{j^{*}}, v_{j^{*}}]$ in $L_{H_{2}}$ and a tuple $[ρ_{j^{*}}, t_{j^{*}}]$ in $L_{H_{3}}$ , and $B$ can query $O_{S K G e n} (σ_{i})$ to obtain $e k_{σ_{i}}$ , calculates $η = e (e k_{σ_{i}}, H_{3} (ρ_{j}))$ , $I = H (η)$ , $Ω = H_{4} (η)$ , and $d_{3} = H_{3} {(ρ_{j^{*}})}^{a} = {\hat{g}}^{a v_{j^{*}}}$ , randomly selects $y \in Z_{q}^{*}$ , and returns $t d_{(σ_{i}, ρ_{j^{*}})} =$ $(y_{1}, y_{2}) = (d_{3}^{Ω} {(\hat{f} {\hat{h}}^{I})}^{y}, {\hat{g}}^{y})$ .

(3)

Challenge:

A_{2}

submits a pair of sender/receiver identities (

σ^{*}, {r c v}^{*}

) to

B

. Let

{r c v}^{*} = ρ^{*}

. Afterwards,

B

chooses a message

m^{*} \in {0, 1}^{λ}

randomly and executes a simulation algorithm to query

O_{H_{1}} (σ^{*})

and

O_{H_{3}} (ρ^{*})

-: When the $i^{*}$ -th tuple in $L_{H_{1}}$ is $[σ^{*}, u^{*}]$ and the $j^{*}$ -th tuple in $L_{H_{2}}$ is $[ρ^{*}, v^{*}]$ , $B$ randomly selects $k \in {0, 1}^{l}$ , $C_{3}^{*} \in {0, 1}^{λ + l}$ , calculates $e k_{σ^{*}} = g^{s u^{*}}$ , $η^{*} = e {(g, \hat{g})}^{b s u^{*} t^{*}}$ , $R = H_{5} (m_{x}, k)$ , $C_{0}^{*} = g^{R}$ , $C_{1}^{*} = g^{c}$ , $C_{2}^{*} = g^{β_{0}^{'} c}$ , and $C_{4}^{*} = {H_{7} (m^{*})}^{R} \cdot H_{8} (e (g^{c}, {\hat{g}}^{a t^{*} \cdot H_{4} (η^{*})}))$ , and delivers this to $A_{2}$ with the challenge ciphertext $C^{*} = (C_{0}^{*}, C_{1}^{*}, C_{2}^{*}, C_{3}^{*}, C_{4}^{*})$ .
The above construction implicitly sets $ω_{1}^{*} = e {(g, \hat{g})}^{a b c v^{*} \cdot H_{4} (η^{*})}$ , $H_{6} (ω_{1}^{*}, η^{*}, C_{0}^{*}, C_{1}^{*}, C_{2}^{*})$ $= (m^{*} ‖ k) \oplus C_{3}^{*}$ , where $g^{u^{*}} = H_{1} (σ^{*})$ , ${\hat{g}}^{b v^{*}} = H_{2} (ρ^{*})$ , ${\hat{g}}^{t^{*}} = H_{3} (ρ^{*})$ .
-: Otherwise, $B$ is aborted by failure.

(4)

Phase2:

A_{2}

makes issues like in Phase1.

(5)

Guess:

A_{2}

answers a guess

m^{'}

B

randomly chooses a tuple

[ω_{1}^{*}, η^{*}, C_{0}^{*}, C_{1}^{*}, C_{2}^{*}, δ^{*}]

from

L_{H_{6}}

and answers the BDH instance solution

{ω_{1}^{*}}^{{(v^{*} H_{4} (η^{*}))}^{- 1}} (= e {(g, \hat{g})}^{a b c})

□

Analysis: It is obvious that the simulations of

O_{H}

O_{H_{1}}

O_{H_{2}}

O_{H_{3}}

O_{H_{5}}

O_{H_{7}}

, and

O_{H_{8}}

are perfect. Denote the query

O_{H_{6}} (e {(g, \hat{g})}^{a b c v^{*} \cdot H_{4} (η^{*})}, η^{*}, C_{0}^{*}, C_{1}^{*}, C_{2}^{*})

as the event

A s k H_{6}^{*}

. Denote the failure of

B

to decrypt the legitimate ciphertext in

O_{D e c}

as the event

D e r r

. Hence, we have,

\Pr [D e r r] \leq \frac{q_{D}}{2^{λ + l}}

. Let

{r c v}^{*} = ρ^{*}

. Suppose

A b o r t R K

as the event in which

B

terminates upon the query

O_{R K G e n} (ρ^{*})

being issued and

A b o r t C h

the event in which

B

terminates in the challenge phase. Clearly,

\neg A b o r t C h

implies

\neg A b o r t R K

, because the query

O_{R K G e n} (ρ^{*})

cannot be issued. We obtain

\Pr [\neg A b o r t C h] \geq \frac{1}{q_{H_{1}} q_{H_{2}}}

Define

E = (A s k H_{6}^{*} \lor D e r r) | \neg A b o r t C h

. There is no greater over

\frac{1}{2^{λ}}

advantage that

A_{2}

will gain in guessing m when E does not happen, because

O_{H_{6}}

is a random oracle.

\Pr [m = m^{'} | \neg E] \leq \frac{1}{2^{λ}}

. Hence,

\begin{matrix} \Pr [m = m^{'}] & = \Pr [m = m^{'} | \neg E] \Pr [\neg E] + \Pr [m = m^{'} | E] \Pr [E] \\ \leq \frac{1}{2^{λ}} \Pr [\neg E] + \Pr [E] = \frac{1}{2^{λ}} + \frac{1}{2} \Pr [E] \\ = (1 - \frac{1}{2^{λ}}) \Pr [E] + \frac{1}{2^{λ}} . \end{matrix}

With

ϵ

, we obtain

\begin{matrix} ϵ & = | \Pr [m = m^{'}] | \leq (1 - \frac{1}{2^{λ}}) \Pr [E] + \frac{1}{2^{λ}} \leq (1 - \frac{1}{2^{λ}}) \frac{\Pr [A s k H_{6}^{*}] + \Pr [D e r r]}{\Pr [\neg A b o r t C h]} + \frac{1}{2^{λ}} . \end{matrix}

Subsequently, we obtain

\begin{matrix} \Pr [A s k H_{6}^{*}] & \geq \frac{ϵ - \frac{1}{2^{λ}}}{1 - \frac{1}{2^{λ}}} \Pr [\neg A b o r t C h] - \Pr [D e r r] \geq \frac{ϵ - \frac{1}{2^{λ}}}{q_{H_{1}} q_{H_{2}}} - \frac{q_{D}}{2^{λ + l}} . \end{matrix}

When

A s k H_{6}^{*}

happens,

A_{2}

can distinguish the simulation of the challenge ciphertext

C^{*}

. Because

[e {(g, \hat{g})}^{a b c v^{*} \cdot H_{4} (η^{*})}, η^{*}, C_{0}^{*}, C_{1}^{*}, C_{2}^{*}, δ^{*}]

has been documented in

L_{H_{6}}

with non-negligible probability,

B

is winning when the right element is selected from

L_{H_{6}}

. Thus, the BDH assumption can be addressed by

B

with advantage

ϵ^{'} \geq \frac{1}{q_{H_{6}}} \Pr [A s k H_{6}^{*}] \geq \frac{1}{q_{H_{6}}} (\frac{ϵ - \frac{1}{2^{λ}}}{q_{H_{1}} q_{H_{2}}} - \frac{q_{D}}{2^{λ + l}}) .

Theorem 3.

For any

A_{3}

, our IBME-ET scheme meets ANON-ID-CCA security on the basis of the Gap-BDH assumption.

More precisely, if

A_{3}

is able to break our proposal with the advantage ϵ, we are able to conceive of a PPT algorithm

B

to address the Gap-BDH assumption with the advantage

ϵ^{'} \geq \frac{ϵ}{q_{H_{1}}^{2} q_{H_{2}}^{2}} - \frac{q_{D}}{2^{λ + l}},

where

q_{H_{i}} (i = 1, 2)

and

q_{D}

denote the numbers of different queries to

O_{H_{i}} (i = 1, 2)

and

O_{D e c}

, respectively.

Proof.

Given a Gap-BDH assumption instance

(g, g^{a}, g^{c}, \hat{g}, {\hat{g}}^{a}, {\hat{g}}^{b}, O_{DBDH})

, the task of

B

is to calculate

e {(g, \hat{g})}^{a b c}

by interacting with

A_{3}

as below:

(1)

Setup:

B

randomly selects

i_{0}^{*}, i_{1}^{*} \in {1, 2, \dots, q_{H_{1}}}

and

j_{0}^{*}, j_{1}^{*} \in {1, 2, \dots, q_{H_{2}}}

B

randomly selects

α^{'}, β_{0}, β_{1} \in Z_{q}^{*}

, calculates

g_{1} = g^{a α^{'}}

f = g^{β_{0}}

h = g^{a β_{1}}

\hat{f} = {\hat{g}}^{β_{0}}

and

\hat{h} = {\hat{g}}^{a β_{1}}

, sets

p p = (G, g, \hat{g}, g_{1}, f, h, \hat{f}, \hat{h}, H, H_{i} (i = 1, 2, 3, 4, 5, 6, 7, 8))

, and delivers this to

A_{3}

with

p p

B

implicitly sets

m k = (s, α) = (a, a α^{'})

, because

B

has no knowledge about a.

B

preserves the

L_{H}

L_{H_{i}} (i = 1, 2, 3, 4, 5, 6, 7, 8)

, and

L_{A}

lists to simulate

O_{H}

O_{H_{i}} (i = 1, 2, 3, 4, 5, 6, 7, 8)

, and

O_{A u t h}

. Afterwards,

B

randomly selects

u_{i_{0}^{*}}, u_{i_{1}^{*}}, v_{j_{0}^{*}}, v_{j_{1}^{*}}, t_{j_{0}^{*}}, t_{j_{1}^{*}} \in Z_{q}^{*}

and randomly chooses

{\tilde{Ω}}_{00}, {\tilde{Ω}}_{01}, {\tilde{Ω}}_{11}, {\tilde{Ω}}_{10}, I_{00}, I_{01}, I_{11}, I_{10} \in Z_{q}^{*}

(2)

Phase1:

B

answers

A_{3}

’s queries.

$O_{H} (η)$ : $B$ executes the following operations.
-
When $O_{DBDH} (g, g^{a}, g^{c}, \hat{g},$ ${\hat{g}}^{a}, {\hat{g}}^{b}, η^{{(u_{i_{0}^{*}} t_{j_{0}^{*}})}^{- 1}}) = 1$ , $B$ returns the Gap-BDH instance solution $η^{{(u_{i_{0}^{*}} t_{j_{0}^{*}})}^{- 1}} (= e {(g, \hat{g})}^{a b c})$ and defines $Ω = \frac{{\tilde{Ω}}_{00}}{t_{j_{0}^{*}}}$ and $I = I_{00}$ .
-
When $O_{DBDH} (g, g^{a}, g^{c}, \hat{g},$ ${\hat{g}}^{a}, {\hat{g}}^{b}, η^{{(u_{i_{1}^{*}} t_{j_{1}^{*}})}^{- 1}}) = 1$ , $B$ returns the Gap-BDH instance solution $η^{{(u_{i_{1}^{*}} t_{j_{1}^{*}})}^{- 1}} (= e {(g, \hat{g})}^{a b c})$ and defines $Ω = \frac{{\tilde{Ω}}_{11}}{t_{j_{1}^{*}}}$ and $I = I_{11}$ .
-
When $O_{DBDH} (g, g^{a}, g^{c}, \hat{g},$ ${\hat{g}}^{a}, {\hat{g}}^{b}, η^{{(u_{i_{0}^{*}} t_{j_{1}^{*}})}^{- 1}}) = 1$ , $B$ returns the Gap-BDH instance solution $η^{{(u_{i_{0}^{*}} t_{j_{1}^{*}})}^{- 1}} (= e {(g, \hat{g})}^{a b c})$ and defines $Ω = \frac{{\tilde{Ω}}_{01}}{t_{j_{1}^{*}}}$ and $I = I_{01}$ .
-
When $O_{DBDH} (g, g^{a}, g^{c}, \hat{g},$ ${\hat{g}}^{a}, {\hat{g}}^{b}, η^{{(u_{i_{1}^{*}} t_{j_{0}^{*}})}^{- 1}}) = 1$ , $B$ returns the Gap-BDH instance solution $η^{{(u_{i_{1}^{*}} t_{j_{0}^{*}})}^{- 1}} (= e {(g, \hat{g})}^{a b c})$ and defines $Ω = \frac{{\tilde{Ω}}_{10}}{t_{j_{0}^{*}}}$ and $I = I_{10}$ .
-
Otherwise, $B$ randomly selects $I, Ω \in Z_{q}^{*}$ .
Subsequently, $B$ inserts $[η, Ω]$ into $L_{H_{4}}$ and $[η, I]$ into $L_{H}$ and answers I.
$O_{H_{1}} (σ_{i})$ : Suppose $σ_{i}$ as the i-th different query. When $i = i_{0}^{*}$ , $B$ inserts a tuple $[σ_{i_{0}^{*}}, u_{i_{0}^{*}}]$ into $L_{H_{1}}$ and returns $g^{c u_{i_{0}^{*}}}$ . When $i = i_{1}^{*}$ , $B$ inserts a tuple $[σ_{i_{1}^{*}}, u_{i_{1}^{*}}]$ into $L_{H_{1}}$ and returns $g^{c u_{i_{1}^{*}}}$ . Otherwise, $B$ randomly selects $u_{i} \in Z_{q}^{*}$ , inserts a tuple $[σ_{i}, u_{i}]$ into $L_{H_{1}}$ , and returns $g^{u_{i}}$ .
$O_{H_{2}} (ρ_{j})$ : Suppose $ρ_{j}$ as the j-th different query. When $j = j_{0}^{*}$ , $B$ inserts a tuple $[ρ_{j_{0}^{*}}, v_{j_{0}^{*}}]$ into $L_{H_{2}}$ and returns ${\hat{g}}^{b v_{j_{0}^{*}}}$ . When $j = j_{1}^{*}$ , $B$ inserts a tuple $[ρ_{j_{1}^{*}}, v_{j_{1}^{*}}]$ into $L_{H_{2}}$ and returns ${\hat{g}}^{b v_{j_{1}^{*}}}$ . Otherwise, $B$ randomly selects $v_{j} \in Z_{q}^{*}$ , inserts a tuple $[ρ_{j}, v_{j}]$ into $L_{H_{2}}$ , and returns ${\hat{g}}^{v_{j}}$ .
$O_{H_{3}} (ρ_{j})$ : $B$ performs a simulation algorithm to query $O_{H_{2}} (ρ_{j})$ . Subsequently, $B$ searches the tuple $[ρ_{j}, v_{j}]$ in $L_{H_{2}}$ . When $j = j_{0}^{*}$ , $B$ inserts a tuple $[ρ_{j_{0}^{*}}, t_{j_{0}^{*}}]$ into $L_{H_{3}}$ and returns ${\hat{g}}^{b t_{j_{0}^{*}}}$ . When $j = j_{1}^{*}$ , $B$ inserts a tuple $[ρ_{j_{1}^{*}}, t_{j_{1}^{*}}]$ into $L_{H_{3}}$ and returns ${\hat{g}}^{b t_{j_{1}^{*}}}$ . Otherwise, $B$ randomly selects $t_{j} \in Z_{q}^{*}$ , inserts a tuple $[ρ_{j}, t_{j}]$ into $L_{H_{3}}$ , and returns ${\hat{g}}^{t_{j}}$ .
$O_{H_{4}} (η)$ : $B$ performs a simulation algorithm to query $O_{H} (η)$ . Subsequently, $B$ searches for the tuple $[η, Ω]$ in $L_{H_{4}}$ and returns $Ω$ .
$O_{H_{5}} (m, k)$ : $B$ randomly chooses $R \in Z_{q}^{*}$ , inserts a tuple $[m, k, R]$ into $L_{H_{5}}$ , and answers R.
$O_{H_{6}} (ω_{1}, η, C_{0}, C_{1}, C_{2})$ : $B$ performs a simulation algorithm to query $O_{H} (η)$ . Subsequently, $B$ randomly selects $δ \in {0, 1}^{λ + l}$ , inserts a tuple $[ω_{1}, -, η, C_{0}, C_{1}, C_{2}, δ]$ into $L_{H_{6}}$ , and returns $δ$ .
$O_{H_{7}} (m)$ : $B$ randomly selects $h_{7} \in \hat{G}$ , inserts a tuple $[m, h_{7}]$ into $L_{H_{7}}$ , and returns $h_{7}$ .
$O_{H_{8}} (ω_{2})$ : $B$ randomly selects $π \in \hat{G}$ , inserts a tuple $[ω_{2}, π]$ into $L_{H_{8}}$ , and returns $π$ .
$O_{S K G e n} (σ_{i})$ : $B$ performs a simulation algorithm to query $O_{H_{1}} (σ_{i})$ . There is a tuple $[σ_{i}, u_{i}]$ in $L_{H_{1}}$ . When $i \neq i_{0}^{*}$ and $i \neq i_{1}^{*}$ , $B$ answers $e k_{σ_{i}} = g^{a u_{i}}$ . Otherwise, $B$ is aborted by failure.
$O_{R K G e n} (ρ_{j})$ : $B$ performs a simulation algorithm to query $O_{H_{3}} (ρ_{j})$ . There are a tuple $[ρ_{j}, v_{j}]$ in $L_{H_{2}}$ and a tuple $[ρ_{j}, t_{j}]$ in $L_{H_{3}}$ . When $j \neq j_{0}^{*}$ and $j \neq j_{1}^{*}$ , $B$ answers $d k_{ρ_{j}} = (d_{1}, d_{2}, d_{3}) = ({\hat{g}}^{a t_{j}}, {\hat{g}}^{a α^{'} v_{j}}, {\hat{g}}^{a α^{'} t_{j}})$ . Otherwise, $B$ is aborted by failure.
$O_{E n c} (σ_{i}, r c v, m)$ : Let $r c v = ρ_{j}$ . $B$ performs a simulation algorithm to query $O_{H_{1}} (σ_{i})$ and $O_{H_{3}} (ρ_{j})$ . When $i \neq i_{0}^{*}$ and $i \neq i_{1}^{*}$ , $B$ can query $O_{S K G e n} (σ_{i})$ to obtain $e k_{σ_{i}}$ and returns $C = E n c (p p, e k_{σ_{i}}, ρ_{j},$ $m)$ . Otherwise, $B$ executes as below:
-
When $(i, j) = (i_{0}^{*}, j_{0}^{*})$ or $(i, j) = (i_{1}^{*}, j_{1}^{*})$ , $B$ is aborted by failure.
-
When $(i, j) = (i_{0}^{*}, j_{1}^{*})$ or $(i, j) = (i_{1}^{*}, j_{0}^{*})$ , $B$ executes a simulation algorithm to query $O_{A u t h} (σ_{i}, ρ_{j})$ . There is a tuple $[σ_{i}, ρ_{j}, I, Ω,$ ${t d}_{(σ_{i}, ρ_{j})}]$ in $L_{A}$ . Afterwards, $B$ randomly selects $r \in Z_{q}^{*}$ , $δ \in {0, 1}^{λ + l}$ , $k \in {0, 1}^{l}$ , calculates $ω_{1} = e (g_{1}, H_{2} {(ρ_{j}))}^{r \cdot Ω}$ , $ω_{2} = e (g_{1}, H_{3} {(ρ_{j}))}^{r \cdot Ω}$ and $R = H_{5} (m, k)$ , inserts a tuple $[ω_{1}, (i, j), -, C_{0}, C_{1}, C_{2}, δ]$ into $L_{H_{6}}$ , and returns $C = (C_{0}, C_{1}, C_{2}, C_{3}, C_{4})$ , where $C_{0} = g^{R}$ , $C_{1} = g^{r}$ , $C_{2} = {(f h^{I})}^{r}$ , $C_{3} = (m ‖ k) \oplus δ$ , $C_{4} = H_{7} {(m)}^{R} \cdot H_{8} (ω_{2})$ .
-
Otherwise, $B$ can query $O_{R K G e n} (ρ_{j})$ to get $d k_{ρ_{j}} = (d_{1}, d_{2}, d_{3})$ , selects $k \in {0, 1}^{l}$ , $r \in Z_{q}^{*}$ randomly, calculates $η = e (H_{1} (σ_{i}), d_{1})$ , $ω_{1} = e (g_{1}, H_{2} {(ρ_{j}))}^{r \cdot H_{4} (η)}$ , $ω_{2} = e (g_{1}, H_{3} {(ρ_{j}))}^{r \cdot H_{4} (η)}$ and $R = H_{5} (m, k)$ , and returns $C = (C_{0}, C_{1}, C_{2}, C_{3}, C_{4})$ , where $C_{0} = g^{R}$ , $C_{1} = g^{r}$ , $C_{2} = {(f h^{H (η)})}^{r}$ , $C_{3} = (m ‖ k) \oplus H_{6} (ω_{1}, η, C_{0}, C_{1}, C_{2})$ , $C_{4} = H_{7} {(m)}^{R} \cdot H_{8} (ω_{2})$ .
$O_{D e c} (ρ_{j}, s n d, C)$ : Let $s n d = σ_{i}$ . $B$ performs a simulation algorithm to query $O_{H_{2}} (ρ_{j})$ and $O_{H_{1}} (σ_{i})$ . When $j \neq j_{0}^{*}$ and $j \neq j_{1}^{*}$ , $B$ can query $O_{R K G e n} (ρ_{j})$ to obtain $d k_{ρ_{j}}$ and returns the outcome of $D e c (p p, d k_{(ρ_{j})}, σ_{i}, C)$ . Otherwise, $B$ executes the following operations:
-
When $(i, j) = (i_{0}^{*}, j_{0}^{*})$ , or $(i, j) = (i_{1}^{*}, j_{1}^{*})$ m or $(i, j) = (i_{0}^{*}, j_{1}^{*})$ , or $(i, j) = (i_{1}^{*}, j_{0}^{*})$ , $B$ searches for the tuple $[σ_{i}, ρ_{j}, I, Ω,$ ${t d}_{(σ_{i}, ρ_{j})}]$ in $L_{A}$ . When $L_{A}$ has no such tuple, $B$ executes as below.
When $(i, j) = (i_{0}^{*}, j_{0}^{*})$ , $Ω = \frac{{\tilde{Ω}}_{00}}{t_{j}}$ , $I = I_{00}$ . When $(i, j) = (i_{1}^{*}, j_{1}^{*})$ , $Ω = \frac{{\tilde{Ω}}_{11}}{t_{j}}$ , $I = I_{11}$ . When $(i, j) = (i_{0}^{*}, j_{1}^{*})$ , $Ω = \frac{{\tilde{Ω}}_{01}}{t_{j}}$ , $I = I_{01}$ . When $(i, j) = (i_{1}^{*}, j_{0}^{*})$ , $Ω = \frac{{\tilde{Ω}}_{10}}{t_{j}}$ , $I = I_{10}$ . Afterwards, $B$ randomly selects $\tilde{y} \in Z_{q}^{*}$ , calculates $z = \frac{t_{j} α^{'} Ω}{β_{1} I}$ , implicitly sets $y = \tilde{y} - b z$ , sets $t d_{(σ_{i}, ρ_{j})} = (y_{1}, y_{2}) = ({\hat{g}}^{β_{0} (\tilde{y} - b z)} {\hat{g}}^{a β_{1} I \tilde{y}}, {\hat{g}}^{\tilde{y} - b z})$ , and stores $[ρ_{j}, σ_{i}, I, Ω, {t d}_{(σ_{i}, ρ_{j})}]$ in $L_{A}$ . $t d_{(σ_{i}, ρ_{j})} = (y_{1}, y_{2})$ is a valid random trapdoor according to $ρ_{j}$ and $σ_{i}$ , where

$\begin{matrix} y_{1} & = {\hat{g}}^{β_{0} (\tilde{y} - b z)} {\hat{g}}^{a β_{1} I \tilde{y}} = {\hat{g}}^{a α^{'} b t_{j} \cdot Ω} {\hat{g}}^{β_{0} y} {\hat{g}}^{a β_{1} I y} = d_{3}^{Ω} {\hat{g}}^{(β_{0} + a β_{1} I) y} = d_{3}^{Ω} {(\hat{f} {\hat{h}}^{I})}^{y}, \\ y_{2} & = {\hat{g}}^{\tilde{y} - b z} = {\hat{g}}^{y} . \end{matrix}$

Next, $B$ calculates $ω_{2} = \frac{e (C_{1}, y_{1})}{e (C_{2}, y_{2})}$ . For each tuple $[ω_{1}, (i, j), -,$ $C_{0}, C_{1}, C_{2}, δ]$ in $L_{H_{6}}$ , $B$ calculates $m ‖ k = C_{3} \oplus δ$ and $R = H_{5} (m, k)$ . If both $C_{0} = g^{R}$ and $C_{4} = H_{7} {(m)}^{R} \cdot H_{8} (ω_{2})$ hold, $B$ returns m; otherwise, $B$ returns ⊥.
-
Otherwise, $B$ can query $O_{A u t h} (σ_{i}, ρ_{j})$ to obtain $t d_{(σ_{i}, ρ_{j})} = (y_{1}, y_{2})$ and calculates $ω_{2} = \frac{e (C_{1}, y_{1})}{e (C_{2}, y_{2})}$ . For each tuple $[ω_{1}, (i, j), -,$ $C_{0}, C_{1}, C_{2}, δ]$ in $L_{H_{6}}$ , $B$ calculates $m ‖ k = C_{3} \oplus δ$ and $R = H_{5} (m, k)$ . If both $C_{0} = g^{R}$ and $C_{4} = H_{7} {(m)}^{R} \cdot H_{8} (ω_{2})$ hold, $B$ returns m; otherwise, $B$ returns ⊥.
$O_{A u t h} (s n d, ρ_{j})$ : Let $s n d = σ_{i}$ . $B$ performs a simulation algorithm to query $O_{H_{3}} (ρ_{j})$ and $O_{H_{1}} (σ_{i})$ . There is a tuple $[ρ_{j}, v_{j}]$ in $L_{H_{2}}$ . When $j \neq j_{0}^{*}$ and $j \neq j_{1}^{*}$ , $B$ can query $O_{R K G e n} (ρ_{j})$ to obtain $d k_{ρ_{j}} = (d_{1}, d_{2}, d_{3})$ , calculates $η = e (H_{1} (σ_{i}), d_{1})$ , $I = H (η)$ , $Ω = H_{3} (η)$ , returns $t d_{(σ_{i}, ρ_{j})} = A u t h (p p, σ_{i}, d k_{ρ_{j}})$ , and stores $[σ_{i}, ρ_{j}, I, Ω, t d_{(σ_{i}, ρ_{j})}]$ into $L_{A}$ . Otherwise, $B$ executes as below:
-
When $(i, j) = (i_{0}^{*}, j_{0}^{*})$ or $(i, j) = (i_{1}^{*}, j_{1}^{*})$ , $B$ is aborted by failure.
-
When $(i, j) = (i_{0}^{*}, j_{1}^{*})$ , $Ω = \frac{{\tilde{Ω}}_{01}}{t_{j}}$ , $I = I_{01}$ .
-
When $(i, j) = (i_{1}^{*}, j_{0}^{*})$ , $Ω = \frac{{\tilde{Ω}}_{10}}{t_{j}}$ , $I = I_{10}$ .
-
Otherwise, $B$ can query $O_{S K G e n} (σ_{i})$ to obtain $e k_{σ_{i}}$ and calculates $η = e (e k_{σ_{i}},$ $H_{3} (ρ_{j}))$ , $Ω = H_{4} (η)$ . $I = H (η)$
Subsequently, $B$ randomly selects $\tilde{y} \in Z_{q}^{*}$ , calculates $z = \frac{t_{j} α^{'} Ω}{I β_{1}}$ , implicitly sets $y = \tilde{y} - b z$ , returns $t d_{(σ_{i}, ρ_{j})} = (y_{1}, y_{2}) = ({\hat{g}}^{β_{0} (\tilde{y} - b z)} {\hat{g}}^{a β_{1} I \tilde{y}}, {\hat{g}}^{\tilde{y} - b z})$ , and then, stores $[σ_{i}, ρ_{j}, I,$ $Ω, {t d}_{(σ_{i}, ρ_{j})}]$ in $L_{A}$ . ${t d}_{(σ_{i}, ρ_{j})} = (y_{1}, y_{2})$ is a valid random trapdoor according to $ρ_{j}$ and $σ_{i}$ , where

$\begin{matrix} y_{1} & = {\hat{g}}^{β_{0} (\tilde{y} - b z)} {\hat{g}}^{a β_{1} I \tilde{y}} = {\hat{g}}^{a α^{'} b t_{j} \cdot Ω} {\hat{g}}^{β_{0} y} {\hat{g}}^{a β_{1} I y} = d_{3}^{Ω} {\hat{g}}^{(β_{0} + a β_{1} I) y} = d_{3}^{Ω} {(\hat{f} {\hat{h}}^{I})}^{y}, \\ y_{2} & = {\hat{g}}^{\tilde{y} - b z} = {\hat{g}}^{y} . \end{matrix}$

(3)

Challenge:

A_{3}

offers a message

m^{*} \in {0, 1}^{λ}

and two pairs of sender/receiver identities (

{s n d}_{0}^{*}, ρ_{0}^{*}

), (

{s n d}_{1}^{*}, ρ_{1}^{*}

) to

B

. Set

{s n d}_{0}^{*} = σ_{0}^{*}

{s n d}_{1}^{*} = σ_{1}^{*}

. Afterwards,

B

utilizes a simulation algorithm to query

O_{H_{1}} (σ_{0}^{*})

O_{H_{1}} (σ_{1}^{*})

O_{H_{3}} (ρ_{0}^{*})

, and

O_{H_{3}} (ρ_{1}^{*})

-: When the $i_{0}^{*}$ -th tuple in $L_{H_{1}}$ is $[σ_{0}^{*}, u_{0}^{*}]$ , the $i_{1}^{*}$ -th tuple in $L_{H_{1}}$ is $[σ_{1}^{*}, u_{1}^{*}]$ , the $j_{0}^{*}$ -th tuple in $L_{H_{2}}$ is $[ρ_{0}^{*}, v_{0}^{*}]$ , and the $j_{1}^{*}$ -th tuple in $L_{H_{2}}$ is $[ρ_{1}^{*}, v_{1}^{*}]$ , $B$ executes the following operations:
Firstly, $B$ randomly selects $x \in {0, 1}$ and searches for the tuple $[σ_{x}^{*}, ρ_{x}^{*}, I, Ω, t d_{(σ_{x}^{*}, ρ_{x}^{*})}]$ in $L_{A}$ . When $L_{A}$ has no such tuple, $B$ sets $Ω = \frac{{\tilde{Ω}}_{x x}}{t_{x}^{*}}$ and $I = I_{x x}$ . Subsequently, $B$ randomly selects $\tilde{y} \in Z_{q}^{*}$ , calculates $z = \frac{t_{x} α^{'} Ω}{β_{1} I} = \frac{α^{'} {\tilde{Ω}}_{x x}}{β_{1} I}$ , implicitly sets $y = \tilde{y} - b z$ , obtains $t d_{(σ_{x}^{*}, ρ_{x}^{*})} = (y_{1}, y_{2}) = ({\hat{g}}^{β_{0} (\tilde{y} - b z)} {\hat{g}}^{a β_{1} I \tilde{y}}, {\hat{g}}^{\tilde{y} - b z})$ , and then, inserts a tuple $[σ_{x}^{*}, ρ_{x}^{*}, I, Ω, {t d}_{(σ_{x}^{*}, ρ_{x}^{*})}]$ in $L_{A}$ . $t d_{(σ_{x}^{*}, ρ_{x}^{*})} = (y_{1}, y_{2})$ is a valid random trapdoor according to $σ_{x}^{*}$ and $ρ_{x}^{*}$ , where

$\begin{matrix} y_{1} & = {\hat{g}}^{β_{0} (\tilde{y} - b z)} {\hat{g}}^{a β_{1} I \tilde{y}} = {\hat{g}}^{a b α^{'} \cdot {\tilde{Ω}}_{x x}} {\hat{g}}^{β_{0} y} {\hat{g}}^{a β_{1} I y} = {\hat{g}}^{a α^{'} b t_{x} \cdot Ω} {\hat{g}}^{β_{0} y} {\hat{g}}^{a β_{1} I y} = d_{3}^{Ω} {(\hat{f} {\hat{h}}^{I})}^{y}, \\ y_{2} & = {\hat{g}}^{\tilde{y} - b z} = {\hat{g}}^{y} . \end{matrix}$

Secondly, $B$ randomly selects $r \in Z_{q}^{*}$ , $C_{3}^{*} \in {0, 1}^{λ + l}$ , $k \in {0, 1}^{l}$ , calculates $ω_{2}^{*} = e {(g^{a α^{'}}, {\hat{g}}^{b})}^{r {\tilde{Ω}}_{x x}}$ , $R = H_{5} (m^{*}, k)$ , $C_{0}^{*} = g^{R}$ , $C_{1}^{*} = g^{r}$ , $C_{2}^{*} = {(f h^{I})}^{r}$ , and $C_{4}^{*} = H_{7} {(m^{*})}^{R} \cdot H_{8} (ω_{2}^{*})$ .
The above construction implicitly sets $C_{3}^{*} = (m^{*} ‖ k) \oplus H_{6} (ω_{1}^{*}, η^{*}, C_{0}^{*}, C_{1}^{*}, C_{2}^{*})$ , where $ω_{1}^{*} = e {(g^{a α^{'}}, {\hat{g}}^{b})}^{r Ω v_{x}^{*}}$ , $η^{*} = e {(g, \hat{g})}^{a b c u_{x}^{*} t_{x}^{*}}$ . $C_{x}^{*} = (C_{0}^{*}, C_{1}^{*}, C_{2}^{*}, C_{3}^{*}, C_{4}^{*})$ is the encryption of $m^{*}$ according to $σ_{x}^{*}$ and $ρ_{x}^{*}$ , where

$\begin{matrix} ω_{2}^{*} & = e {(g^{a α^{'}}, {\hat{g}}^{b})}^{r {\tilde{Ω}}_{x x}} = e {(g_{1}, {\hat{g}}^{b})}^{r t_{x}^{*} Ω} = e (g_{1}, {\hat{g}}^{b t_{x}^{*})^{r \cdot Ω}} = {e (g_{1}, H_{3} (ρ_{x}^{*}))}^{r \cdot Ω} . \end{matrix}$

Eventually, $B$ returns the corresponding challenge ciphertext $C_{x}^{*} = (C_{0}^{*}, C_{1}^{*}, C_{2}^{*}, C_{3}^{*}, C_{4}^{*})$ and challenge trapdoor $t d_{(σ_{x}^{*}, ρ_{x}^{*})} = (y_{1}, y_{2})$ to $A_{3}$ .
-: Otherwise, $B$ is aborted by failure.

(4)

Phase2:

A_{3}

makes issues like in Phase1.

(5)

Guess:

A_{3}

answers a guess

x^{'} \in {0, 1}

□

Analysis: It is obvious that the simulations of

O_{H_{1}}

O_{H_{2}}

O_{H_{3}}

O_{H_{5}}

O_{H_{7}}

, and

O_{H_{8}}

are perfect. Define

η_{(0, 0)} = e {(g, \hat{g})}^{a b c u_{i_{0}^{*}} t_{j_{0}^{*}}}

η_{(1, 1)} = e {(g, \hat{g})}^{a b c u_{i_{1}^{*}} t_{j_{0}^{*}}}

η_{(1, 0)} = e {(g, \hat{g})}^{a b c u_{i_{1}^{*}} t_{j_{0}^{*}}}

η_{(0, 1)} = e {(g, \hat{g})}^{a b c u_{i_{0}^{*}} t_{j_{1}^{*}}}

. Let

{s n d}_{0}^{*} = σ_{0}^{*}

and

{s n d}_{1}^{*} = σ_{1}^{*}

. Denote the queries

O_{H} (η_{(0, 0)})

O_{H} (η_{(0, 1)})

O_{H} (η_{(1, 0)})

, and

O_{H} (η_{(1, 1)})

as the event

A s k H

. Suppose

A b o r t S K

as the event in which

B

terminates upon the queries

O_{S K G e n} (σ_{0}^{*})

and

O_{S K G e n} (σ_{1}^{*})

being issued,

A b o r t R K

as the event in which

B

terminates upon the queries

O_{R K G e n} (ρ_{0}^{*})

and

O_{R K G e n} (ρ_{1}^{*})

being issued,

A b o r t A u t h

as the event in which

B

terminates upon the queries

O_{A u t h} (σ_{0}^{*}, ρ_{0}^{*})

and

O_{A u t h} (σ_{1}^{*}, ρ_{1}^{*})

being issued,

A b o r t E n c

as the event in which

B

terminates upon the queries

O_{E n c} (σ_{0}^{*}, ρ_{0}^{*}, *)

and

O_{E n c} (σ_{1}^{*}, ρ_{1}^{*}, *)

being issued, and

A b o r t C h

as the event in which

B

terminates in the challenge phase. Clearly,

\neg A b o r t C h

implies

\neg A b o r t S K

\neg A b o r t R K

\neg A b o r t A u t h

, and

\neg A b o r t E n c

, because the queries

O_{S K G e n} (σ_{0}^{*})

and

O_{S K G e n} (σ_{1}^{*})

cannot be issued, the queries

O_{R K G e n} (ρ_{0}^{*})

and

O_{R K G e n} (ρ_{1}^{*})

are unable to be issued,

(σ_{0}^{*}, ρ_{0}^{*})

and the queries

O_{A u t h} (σ_{0}^{*}, ρ_{0}^{*})

and

O_{A u t h} (σ_{1}^{*}, ρ_{1}^{*})

are unable to be issued, and the queries

O_{E n c} (σ_{0}^{*}, ρ_{0}^{*}, *)

and

O_{E n c} (σ_{1}^{*}, ρ_{1}^{*}, *)

are unable to be issued. Thus, we obtain

\Pr [\neg A b o r t C h] \geq \frac{1}{q_{H_{1}}^{2}} \cdot \frac{1}{q_{H_{2}}^{2}}

Denote the failure of

B

to decrypt the legitimate ciphertext in

O_{D e c}

as the event

D e r r

. Thus,

\Pr [D e r r] \leq \frac{q_{D}}{2^{λ + l}}

Define

E_{0} = (A s k H \lor D e r r) | \neg A b o r t C h

. There is no greater over

\frac{1}{2}

advantage that

A_{3}

will gain in guessing x when

E_{0}

does not happen because

O_{H}

O_{H_{4}}

, and

O_{H_{6}}

are random oracles. Hence,

\Pr [x = x^{'} | \neg E_{0}] = \frac{1}{2}

. We obtain

\begin{matrix} \Pr [x = x^{'}] & = \Pr [x = x^{'} | \neg E_{0}] \Pr [\neg E_{0}] + \Pr [x = x^{'} | E_{0}] \Pr [E_{0}] \leq \frac{1}{2} \Pr [\neg E_{0}] + \Pr [E_{0}] = \frac{1}{2} + \frac{1}{2} \Pr [E_{0}] . \end{matrix}

With

ϵ

, we obtain

\begin{matrix} ϵ & = | \Pr [x = x^{'}] - \frac{1}{2} | \leq \Pr [E_{0}] \leq \frac{\Pr [A s k H] + \Pr [D e r r]}{\Pr [\neg A b o r t C h]} . \end{matrix}

Subsequently, we obtain

\begin{matrix} \Pr [A s k H] & \geq ϵ \Pr [\neg A b o r t C h] - \Pr [D e r r] \geq \frac{ϵ}{q_{H_{1}}^{2} q_{H_{2}}^{2}} - \frac{q_{D}}{2^{λ + l}} . \end{matrix}

Obviously, when

A s k H

occurs, the Gap-BDH assumption can certainly be addressed by

B

B

addresses the Gap-BDH assumption with advantage

ϵ^{'} = \Pr [B s u c c e s s] = \Pr [A s k H] \geq \frac{ϵ}{q_{H_{1}}^{2} q_{H_{2}}^{2}} - \frac{q_{D}}{2^{λ + l}} .

Theorem 4.

For any

A_{4}

, our IBME-ET scheme meets sUF-ID-CMA security on the basis of the Gap-BDH assumption.

More precisely, if

A_{4}

is able to break our proposal with the advantage ϵ, we are able to conceive of a PPT algorithm

B

to address the Gap-BDH assumption with the advantage

ϵ^{'} \geq ϵ (1 - \frac{1}{q}) \frac{1}{q_{H_{1}} q_{H_{3}}} - \frac{1 + q_{D}}{2^{λ}},

where

q_{H_{i}} (i = 1, 3)

and

q_{D}

denote the numbers of different queries to

O_{H_{i}} (i = 1, 3)

and

O_{D e c}

, respectively.

Proof.

Given a Gap-BDH assumption instance

(g, g^{a}, g^{c}, \hat{g}, {\hat{g}}^{a}, {\hat{g}}^{b}, O_{DBDH})

, the task of

B

is to calculate

e {(g, \hat{g})}^{a b c}

by interacting with

A_{4}

as below:

(1)

Setup:

B

randomly chooses

i^{*} \in {1, 2, \dots, q_{H_{1}}}

j^{*} \in {1, 2, \dots, q_{H_{3}}}

B

randomly selects

α, β_{0}, β_{1} \in Z_{q}^{*}

, calculates

g_{1} = g^{α}

f = g^{β_{0}}

h = g^{β_{1}}

\hat{f} = {\hat{g}}^{β_{0}}

and

\hat{h} = {\hat{g}}^{β_{1}}

, sets

p p = (G, g, \hat{g}, g_{1}, f, h, \hat{f}, \hat{h}, H,

H_{i} (i = 1, 2, 3, 4, 5, 6, 7, 8))

, and delivers this to

A_{4}

with

p p

B

implicitly sets

m k = (a, α)

, because

B

has no knowledge about a.

B

preserves the

L_{H}

and

L_{H_{i}} (i = 1, 2, 3, 4, 5, 6, 7, 8)

lists to simulate

O_{H}

and

O_{H_{i}} (i = 1, 2, 3, 4, 5, 6, 7, 8)

. Afterwards,

B

randomly selects

I^{*}, Ω^{*} \in Z_{q}^{*}

(2)

Queries:

B

answers

A_{4}

’s queries as below:

$O_{H} (η)$ : When $O_{DBDH} (g, g^{a}, g^{c}, \hat{g}, {\hat{g}}^{a}, {\hat{g}}^{b}, η) \neq 1$ , $B$ randomly selects $Ω, I \in Z_{q}^{*}$ , inserts $[η, Ω]$ into $L_{H_{4}}$ and $[η, I]$ into $L_{H}$ , and answers I. Otherwise, $B$ answers the Gap-BDH solution $η (= e {(g, \hat{g})}^{a b c})$ , defines $Ω = Ω^{*}$ and $I = I^{*}$ , inserts $[η, Ω]$ into $L_{H_{4}}$ and $[η, I]$ into $L_{H}$ , and answers I.
$O_{H_{1}} (σ_{i})$ : Suppose $σ_{i}$ as the i-th different query. When $i \neq i^{*}$ , $B$ randomly selects $u_{i} \in Z_{q}^{*}$ , inserts a tuple $[σ_{i}, u_{i}]$ into $L_{H_{1}}$ , returns $g^{u_{i}}$ . Otherwise, $B$ inserts a tuple $[σ_{i}, -]$ into $L_{H_{1}}$ and returns $g^{c}$ .
$O_{H_{2}} (ρ_{j})$ : $B$ performs a simulation algorithm to query $O_{H_{3}} (ρ_{j})$ . Subsequently, $B$ randomly selects $v_{j} \in Z_{q}^{*}$ , inserts a tuple $[ρ_{j}, v_{j}]$ into $L_{H_{2}}$ , and returns ${\hat{g}}^{v_{j}}$ .
$O_{H_{3}} (ρ_{j})$ : Suppose $ρ_{j}$ as the j-th different query. When $j \neq j^{*}$ , $B$ randomly selects $t_{j} \in Z_{q}^{*}$ , inserts a tuple $[ρ_{j}, t_{j}]$ into $L_{H_{3}}$ , and returns ${\hat{g}}^{t_{j}}$ . Otherwise, $B$ inserts a tuple $[ρ_{j}, -]$ into $L_{H_{3}}$ and returns ${\hat{g}}^{b}$ .
$O_{H_{4}} (η)$ : $B$ performs a simulation algorithm to query $O_{H} (η)$ . Subsequently, $B$ searches for the tuple $[η, Ω]$ in $L_{H_{4}}$ and answers $Ω$ .
$O_{H_{5}} (m, k)$ : $B$ randomly chooses $R \in Z_{q}^{*}$ , inserts a tuple $[m, k, R]$ into $L_{H_{5}}$ , and answers R.
$O_{H_{6}} (ω_{1}, η, C_{0}, C_{1}, C_{2})$ : $B$ performs a simulation algorithm to query $O_{H} (η)$ . Subsequently, $B$ randomly selects $δ \in {0, 1}^{λ + l}$ , inserts a tuple $[ω_{1}, -, η, C_{0}, C_{1}, C_{2}, δ]$ into $L_{H_{6}}$ , and returns $δ$ .
$O_{H_{7}} (m)$ : $B$ randomly selects $h_{7} \in \hat{G}$ , inserts a tuple $[m, h_{7}]$ into $L_{H_{7}}$ , and returns $h_{7}$ .
$O_{H_{8}} (ω_{2})$ : $B$ randomly selects $π \in \hat{G}$ , inserts a tuple $[ω_{2}, π]$ into $L_{H_{8}}$ , and returns $π$ .
$O_{S K G e n} (σ_{i})$ : $B$ performs a simulation algorithm to query $O_{H_{1}} (σ_{i})$ . There is a tuple $[σ_{i}, u_{i}]$ in $L_{H_{1}}$ . If $i \neq i^{*}$ , $B$ returns $e k_{σ_{i}} = g^{a u_{i}}$ . Otherwise, $B$ is aborted by failure.
$O_{R K G e n} (ρ_{j})$ : $B$ performs a simulation algorithm to query $O_{H_{2}} (ρ_{j})$ . There is a tuple $[ρ_{j}, v_{j}]$ in $L_{H_{2}}$ . If $j \neq j^{*}$ , $B$ returns $d k_{ρ_{j}} = (d_{1}, d_{2}, d_{3})$ $= ({\hat{g}}^{a t_{j}}, {\hat{g}}^{α v_{j}}, {\hat{g}}^{α t_{j}})$ . Otherwise, $B$ is aborted by failure.
$O_{A u t h} (s n d, ρ_{j})$ : Let $s n d = σ_{i}$ . $B$ performs a simulation algorithm to query $O_{H_{2}} (ρ_{j})$ and $O_{H_{1}} (σ_{i})$ . There is a tuple $[ρ_{j}, t_{j}]$ in $L_{H_{3}}$ . When $j \neq j^{*}$ , $B$ can query $O_{R K G e n} (ρ_{j})$ to obtain $d k_{ρ_{j}} = (d_{1}, d_{2}, d_{3})$ , calculates $η = e (H_{1} (σ_{i}), d_{1})$ , $Ω = H_{4} (η)$ and $I = H (η)$ , and answers $t d_{(σ_{i}, ρ_{j})} = A u t h (p p, σ_{i}, d k_{ρ_{j}})$ . Otherwise, $B$ executes the following operations:
-
When $(i, j) \neq (i^{*}, j^{*})$ , $B$ can query $O_{S K G e n} (σ_{i})$ to obtain $e k_{σ_{i}}$ , calculates $η = e (e k_{σ_{i}}, H_{2} (ρ_{j}))$ , $I = H (η)$ , and $Ω = H_{4} (η)$ , calculates $d_{3} = {\hat{g}}^{α t_{j}}$ , randomly selects $y \in Z_{q}^{*}$ , and returns $t d_{(σ_{i}, ρ_{j})} =$ $(y_{1}, y_{2}) = (d_{3}^{H_{4} (η)} {(\hat{f} {\hat{h}}^{H (η)})}^{y}, {\hat{g}}^{y})$ .
-
Otherwise, $B$ defines $Ω = Ω^{*}$ , $I = I^{*}$ , calculates $d_{3} = {\hat{g}}^{b α}$ , randomly selects $y \in Z_{q}^{*}$ , and returns $t d_{(σ_{i}, ρ_{j})} = (y_{1}, y_{2}) = (d_{3}^{Ω} {(\hat{f} {\hat{h}}^{I})}^{y}, {\hat{g}}^{y})$ .
$O_{E n c} (σ_{i}, r c v, m)$ : Let $r c v = ρ_{j}$ . $B$ performs a simulation algorithm to query $O_{H_{1}} (σ_{i})$ and $O_{H_{2}} (ρ_{j})$ . When $i \neq i^{*}$ , $B$ can query $O_{S K G e n} (σ_{i})$ to obtain $e k_{σ_{i}}$ and returns $C = E n c (p p, e k_{σ_{i}}, ρ_{j}, m)$ . Otherwise, $B$ executes the following operations:
-
When $(i, j) \neq (i^{*}, j^{*})$ , $B$ can query $O_{R K G e n} (ρ_{j})$ to obtain $d k_{ρ_{j}} = (d_{1}, d_{2}, d_{3})$ , randomly selects $r \in Z_{q}^{*}$ , $k \in {0, 1}^{l}$ , calculates $R = H_{5} (m, k)$ , $η = e (H_{1} (σ_{i}), d_{1})$ , $Ω = H_{4} (η)$ , $ω_{1} = e (g_{1}, H_{2} {(ρ_{j}))}^{r \cdot Ω}$ and $ω_{2} = e (g_{1}, H_{3} {(ρ_{j}))}^{r \cdot Ω}$ , and then, returns $C = (C_{0}, C_{1}, C_{2}, C_{3}, C_{4})$ , where $C_{0} = g^{R}$ , $C_{1} = g^{r}$ , $C_{2} = {(f h^{I})}^{r}$ , $C_{3} = (m ‖ k) \oplus H_{6} (ω_{1})$ , $C_{4} = H_{7} {(m)}^{R} \cdot H_{8} (ω_{2})$ .
-
Otherwise, $B$ defines $Ω = Ω^{*}$ , $I = I^{*}$ , randomly picks $r \in Z_{q}^{*}$ , $δ \in {0, 1}^{λ + l}$ , $k \in {0, 1}^{l}$ , calculates $R = H_{5} (m, k)$ , $ω_{1} = e (g_{1}, H_{2} {(ρ_{j}))}^{r \cdot Ω}$ and $ω_{2} = e (g_{1}, H_{3} {(ρ_{j}))}^{r \cdot Ω}$ , inserts a tuple $[ω_{1}, (i, j), -, C_{0}, C_{1}, C_{2}, δ]$ into $L_{H_{6}}$ , and then, returns $C = (C_{0}, C_{1}, C_{2}, C_{3}, C_{4})$ , where $C_{0} = g^{R}$ , $C_{1} = g^{r}$ , $C_{2} = {(f h^{I})}^{r}$ , $C_{3} = (m ‖ k) \oplus δ$ , and $C_{4} = H_{7} {(m)}^{R} \cdot H_{8} (ω_{2})$ .
$O_{D e c} (ρ_{j}, s n d, C)$ : Let $s n d = σ_{i}$ . $B$ performs a simulation algorithm to query $O_{H_{2}} (ρ_{j})$ and $O_{H_{1}} (σ_{i})$ . When $j \neq j^{*}$ , $B$ can query $O_{R K G e n} (ρ_{j})$ to obtain $d k_{ρ_{j}}$ and returns the outcome of the algorithm $D e c (p p, d k_{ρ_{j}},$ $σ_{i}, C)$ . Otherwise, $B$ executes the following operations:
-
When $(i, j) \neq (i^{*}, j^{*})$ , $B$ can query $O_{A u t h} (σ_{i}, ρ_{j})$ to obtain ${t d}_{(σ_{i}, ρ_{j})} = (y_{1}, y_{2})$ , calculates $ω_{2} = \frac{e (C_{1}, y_{1})}{e (C_{2}, y_{2})}$ , obtains $e k_{σ_{i}}$ by querying $O_{S K G e n} (σ_{i})$ , calculates $η = e (e k_{σ_{i}}, H_{3} (ρ_{j}))$ , $Ω = H_{4} (η)$ , $d_{2} = H_{2} {(ρ_{j})}^{α}$ , $ω_{1} = e (C_{1}, d_{2}^{Ω})$ , recovers $m ‖ k$ by computing $C_{3} \oplus H_{6} (ω_{1}, η, C_{0}, C_{1}, C_{2})$ , calculates $R = H_{5} (m, k)$ . If $C_{0} = g^{R}$ and $C_{4} = H_{7} {(m)}^{R} \cdot H_{8} (ω_{2})$ hold, $B$ answers m; otherwise, $B$ answers ⊥.
-
Otherwise, $B$ defines $Ω = Ω^{*}$ , $I = I^{*}$ , calculates $ω_{1} = {e (C_{1}, {\hat{g}}^{v_{j}})}^{Ω}$ , obtains ${t d}_{(σ_{i}, ρ_{j})} = (y_{1}, y_{2})$ by querying $O_{A u t h} (σ_{i}, ρ_{j})$ , calculates $ω_{2} = \frac{e (C_{1}, y_{1})}{e (C_{2}, y_{2})}$ , and searches for the corresponding tuple $[ω_{1}, (i, j), -,$ $C_{0}, C_{1}, C_{2}, δ]$ in $L_{H_{6}}$ . If there exists no such tuple in $L_{H_{6}}$ , $B$ randomly selects $δ \in {0, 1}^{λ + l}$ and inserts $[ω_{1}, (i, j), -,$ $C_{0}, C_{1}, C_{2}, δ]$ into $L_{H_{6}}$ . Afterwards, $B$ recovers $m ‖ k$ by computing $C_{3} \oplus δ$ and calculates $R = H_{5} (m, k)$ . If $C_{0} = g^{R}$ and $C_{4} = H_{7} {(m)}^{R} \cdot H_{8} (ω_{2})$ hold, $B$ answers m; otherwise, $B$ answers ⊥.

(3)

Forgery:

A_{4}

outputs a triple

(s n d^{*}, ρ^{*}, C^{*})

, where

s n d^{*} = σ^{*}

and

C^{*} = (C_{0}^{*}, C_{1}^{*}, C_{2}^{*}, C_{3}^{*}, C_{4}^{*})

□

Analysis: It is obvious that the simulations of

O_{H_{1}}

O_{H_{2}}

O_{H_{3}}

O_{H_{5}}

O_{H_{7}}

, and

O_{H_{8}}

are perfect. Define

η^{*} = e {(g, \hat{g})}^{a b c}

. Denote the query

O_{H} (η^{*})

as the event

A s k H

. Denote the failure of

B

to decrypt the legitimate ciphertext in

O_{D e c}

as the event

D e r r

. Thus,

\Pr [D e r r] \leq \frac{q_{D}}{2^{λ + l}}

Suppose E as the event for which

σ^{*} = σ_{i^{*}}

ρ^{*} = ρ_{j^{*}}

, and

(σ^{*}, ρ^{*}, C^{*})

are legitimate. With

ϵ

and the lemma on the relationship between the chosen-identity attack and given identity attack [33], we obtain

\Pr [E] \geq ϵ (1 - \frac{1}{q}) \frac{1}{q_{H_{1}} q_{H_{3}}}

Define

E_{0} = A s k H \lor D e r r

. There is no greater over

\frac{1}{2^{λ}}

advantage that

A_{4}

will forge a valid

(σ_{i^{*}}, ρ_{j^{*}}, C^{*})

when

E_{0}

does not happen because

O_{H}

O_{H_{4}}

, and

O_{H_{6}}

are random oracles. Hence,

\Pr [E | \neg E_{0}] = \frac{1}{2^{λ}}

. We obtain

\begin{matrix} \Pr [E] & \leq \Pr [E | \neg E_{0}] \Pr [\neg E_{0}] + \Pr [E_{0}] \leq \frac{1}{2^{λ}} (1 - \Pr [E_{0}]) + \Pr [E_{0}] = \frac{1}{2^{λ}} + (1 - \frac{1}{2^{λ}}) \Pr [E_{0}] \leq \frac{1}{2^{λ}} + \Pr [E_{0}] . \end{matrix}

Therefore, we obtain

\begin{matrix} \Pr [E_{0}] & = \Pr [A s k H \lor D e r r] = \Pr [A s k H] + \Pr [D e r r] \geq \Pr [E] - \frac{1}{2^{λ}} . \end{matrix}

Subsequently, we obtain

\begin{matrix} \Pr [A s k H] & \geq ϵ (1 - \frac{1}{q}) \frac{1}{q_{H_{1}} q_{H_{3}}} - \frac{1}{2^{λ}} - \Pr [D e r r] \geq ϵ (1 - \frac{1}{q}) \frac{1}{q_{H_{1}} q_{H_{3}}} - \frac{1 + q_{D}}{2^{λ}} . \end{matrix}

Obviously, when

A s k H

occurs, the Gap-BDH assumption can certainly be addressed by

B

B

addresses the Gap-BDH assumption with advantage

ϵ^{'} = \Pr [B s u c c e s s] = \Pr [A s k H] \geq ϵ (1 - \frac{1}{q}) \frac{1}{q_{H_{1}} q_{H_{3}}} - \frac{1 + q_{D}}{2^{λ}} .

6. Performance Evaluation

We first give the functionality and security comparisons, then give the comparisons of the computational overhead and communication overhead.

In Table 1, we compare our proposed IBME-ET with the related schemes (i.e., IB-ME [22], IBEET [3,15], and IBSC-ET [7]) in terms of functionality and security. It can be seen that the IB-ME scheme in [22] ensures the confidentiality, authenticity, and anonymity of data stored in the cloud, but does not achieve CCA security nor provide equality test functionality without losing the confidentiality, authenticity, and anonymity of the data. The IBEET schemes in [3,15] ensure the confidentiality of the data, but neither offer the authenticity and anonymity of data, nor provide equality test functionality without losing the confidentiality, authenticity, and anonymity of the data. Moreover, although the scheme in [3] was the first proposed IBEET scheme, it fails to achieve CCA security. Hence, the IBEET scheme that achieves CCA security was proposed in [15]. The IBSC-ET scheme in [7] ensures the confidentiality and authenticity the data and achieves CCA security, but neither ensures the anonymity of data, nor provides the equality test functionality without losing the confidentiality, authenticity, and anonymity of the data. As a result, only our proposed IBME-ET can realize all the functionality and security, which not only ensures the confidentiality, authenticity, and anonymity of the data stored in the cloud and achieves CCA security, but also provides equality test functionality for ciphertexts generated under different identities without losing the confidentiality, authenticity, and anonymity of the data.

Note that the IB-ME scheme in [22] implements only CPA security. This means that the ciphertexts are malleable. When a valid plaintext/ciphertext pair of the sender and receiver is given, an attacker can utilize it to fake a valid ciphertext of any message, in this way to break the authenticity of the ciphertext stored in the cloud. Moreover, the IB-ME scheme in [22] cannot provide equality test functionality for ciphertexts. Obviously, the IB-ME scheme in [22] is not applicable to cloud storage application scenarios. In addition, it was proven in [15] that the computational overhead and communication overhead of the IBEET scheme in [15] are comparable to those of the IBEET scheme in [3]; however, the IBEET scheme in [15] achieves stricter CCA security while the IBEET scheme in [3] only achieves CPA security. Therefore, we only compared our proposed IBME-ET with the most-related schemes (i.e., IBEET [15] and IBSC-ET [7]) in terms of computational overhead and communication overhead.

Table 2 shows the computational overhead comparison, which theoretically analyzes the computational cost of our proposed scheme and the comparative schemes with regard to encryption key generation (indicated as SKGen ), decryption key generation (indicated as RKGen), encryption (indicated as Enc), decryption (indicated as Dec), authorization (indicated as Auth), and the equality test (indicated as Test). For the analysis, we concentrated on the operations that consumed the most time, including hash-to-point, bilinear pairing, and exponentiation. Notably, the authorization algorithms of the schemes in [7,15] have no computational cost. This is because both schemes directly use the partial decryption private key as the trapdoor regardless of anonymity. The communication overhead comparison is given in Table 3, which theoretically analyzes the communication cost of our proposed scheme and the comparative schemes with regard to the encryption private key, decryption private key, trapdoor, and ciphertext.

In order to compare the computational and communication overhead of our proposed scheme with the comparative schemes more intuitively, we used Charm 0.50 in Python 3.6.9 to implement these schemes. The experimental environment was configured as follows: Intel(R) Xeon(R) Platinum 8124M CPU @ 2.70 GHz (Intel Corporation, Santa Clara, CA, USA), 16 GB memory, and Ubuntu 18.03 LTS. The experiments were instantiated using the MNT224 curve in Charm and employed the Python module

t i m e i t

for the time measurements. Figure 3 shows the experimental computational overheads of these schemes, and Figure 4 shows the experimental communication overheads of these schemes.

From Table 1, Table 2 and Table 3 and Figure 3 and Figure 4, we can conclude that, with a small sacrifice in computational and communication efficiency, our IBME-ET scheme not only offers the confidentiality, authenticity, and anonymity of the data and achieves CCA security, but also provides equality test functionality for ciphertexts generated under different identities without losing the confidentiality, authenticity, and anonymity of the data. Other related schemes cannot support this feature.

7. Conclusions

In this paper, we presented the primitive of the IBME-ET, which not only offers the confidentiality, authenticity, and anonymity of data and achieves CCA security, but also provides equality test functionality for ciphertexts generated under different identities without losing the confidentiality, authenticity, and anonymity of the data. More precisely, we introduced the system model and definition of the IBME-ET. With respect to the confidentiality, authenticity, and anonymity, we formalized the security models for the IBME-ET. Finally, we proposed a concrete IBME-ET scheme, and our scheme was confirmed to be secure and practical by proving its security and evaluating its performance.

Author Contributions

Conceptualization, Z.Y. and X.L.; methodology, Z.Y.; validation, H.Q. and J.X.; writing—original draft, Z.Y. and X.L.; writing—review and editing, H.Q. and X.Z. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Data Availability Statement

Data are contained within the article.

Conflicts of Interest

The authors declare no conflicts of interest.

References

Boneh, D.; Di Crescenzo, G.; Ostrovsky, R.; Persiano, G. Public key encryption with keyword search. In Proceedings of the Advances in Cryptology—EUROCRYPT 2004, Interlaken, Switzerland, 2–6 May 2004; Springer: Berlin/Heidelberg, Germany, 2004; pp. 506–522. [Google Scholar]
Yang, G.; Tan, C.H.; Huang, Q.; Wong, D.S. Probabilistic public key encryption with equality test. In Proceedings of the Topics in Cryptology—CT-RSA 2010, San Francisco, CA, USA, 1–5 March 2010; Springer: Berlin/Heidelberg, Germany, 2010; pp. 119–131. [Google Scholar]
Ma, S. Identity-based encryption with outsourced equality test in cloud computing. Inf. Sci. 2015, 328, 389–402. [Google Scholar] [CrossRef]
Lu, J.; Li, H.; Huang, J.; Ma, S.; Au, M.H.A.; Huang, Q. An Identity-Based Encryption with Equality Test scheme for healthcare social apps. Comput. Stand. Interfaces 2023, 87, 103759. [Google Scholar] [CrossRef]
My HealtheVet. Available online: http://www.myhealth.va.gov (accessed on 22 December 2023).
Vaanchig, N.; Qin, Z.; Ragchaasuren, B. Constructing secure-channel free identity-based encryption with equality test for vehicle-data sharing in cloud computing. Trans. Emerg. Telecommun. Technol. 2022, 33, e3896. [Google Scholar] [CrossRef]
Xiong, H.; Hou, Y.; Huang, X.; Zhao, Y. Secure message classification services through identity-based signcryption with equality test towards the Internet of vehicles. Veh. Commun. 2020, 26, 100264. [Google Scholar] [CrossRef]
Ohtaki, Y. Constructing a Searchable Encrypted Log Using Encrypted Inverted Indexes. In Proceedings of the 2005 International Conference on Cyberworlds, CW 2005, Singapore, 23–25 November 2005; pp. 130–138. [Google Scholar]
Boneh, D.; Kushilevitz, E.; Ostrovsky, R.; Skeith, W.E. Public key encryption that allows PIR queries. In Proceedings of the Advances in Cryptology—CRYPTO 2007, Santa Barbara, CA, USA, 19–23 August 2007; Springer: Berlin/Heidelberg, Germany, 2007; pp. 50–67. [Google Scholar]
Camenisch, J.; Kohlweiss, M.; Rial, A.; Sheedy, C. Blind and anonymous identity-based encryption and authorised private searches on public key encrypted data. In Proceedings of the Public Key Cryptography—PKC 2009, Irvine, CA, USA, 18–20 March 2009; Springer: Berlin/Heidelberg, Germany, 2009; pp. 196–214. [Google Scholar]
Curtmola, R.; Garay, J.A.; Kamara, S.; Ostrovsky, R. Searchable symmetric encryption: Improved definitions and efficient constructions. In Proceedings of the ACM Conference on Computer and Communications Security, CCS 2006, Alexandria, VA, USA, 30 October–3 November 2006; pp. 79–88. [Google Scholar]
Cash, D.; Jarecki, S.; Jutla, C.S.; Krawczyk, H.; Rosu, M.; Steiner, M. Highly-scalable searchable symmetric encryption with support for Boolean queries. In Proceedings of the Advances in Cryptology—CRYPTO 2013, Santa Barbara, CA, USA, 18–22 August 2013; Springer: Berlin/Heidelberg, Germany, 2013; pp. 353–373. [Google Scholar]
Tang, Q. Public key encryption supporting plaintext equality test and user-specified authorization. Secur. Commun. Netw. 2012, 5, 1351–1362. [Google Scholar] [CrossRef]
Ma, S.; Huang, Q.; Zhang, M.; Yang, B. Efficient public key encryption with equality test supporting flexible authorization. IEEE Trans. Inf. Forensic Secur. 2014, 10, 458–470. [Google Scholar] [CrossRef]
Lee, H.T.; Ling, S.; Seo, J.H.; Wang, H. Semi-generic construction of public key encryption and identity-based encryption with equality test. Inf. Sci. 2016, 373, 419–440. [Google Scholar] [CrossRef]
Lin, X.J.; Sun, L.; Qu, H. Generic construction of public key encryption, identity-based encryption and signcryption with equality test. Inf. Sci. 2018, 453, 111–126. [Google Scholar] [CrossRef]
Li, N. Efficient equality test on identity-based ciphertexts supporting flexible authorization. Entropy 2023, 25, 362. [Google Scholar] [CrossRef] [PubMed]
Boyen, X. Multipurpose Identity-Based Signcryption. In Proceedings of the Advances in Cryptology—CRYPTO 2003, Santa Barbara, CA, USA, 17–21 August 2003; Springer: Berlin/Heidelberg, Germany, 2003; pp. 383–399. [Google Scholar]
Xiong, H.; Zhao, Y.; Hou, Y.; Huang, X.; Jin, C.; Wang, L.; Kumari, S. Heterogeneous Signcryption With Equality Test for IIoT Environment. IEEE Internet Things J. 2021, 8, 16142–16152. [Google Scholar] [CrossRef]
Xiong, H.; Hou, Y.; Huang, X.; Zhao, Y.; Chen, C.M. Heterogeneous Signcryption Scheme from IBC to PKI with Equality Test for WBANs. IEEE Syst. J. 2022, 16, 2391–2400. [Google Scholar] [CrossRef]
Hou, Y.; Huang, X.; Chen, Y.; Kumar, S.; Xiong, H. Heterogeneous signcryption scheme supporting equality test from PKI to CLC toward IoT. Trans. Emerg. Telecommun. Technol. 2021, 32, e4190. [Google Scholar] [CrossRef]
Ateniese, G.; Francati, D.; Nuñez, D.; Venturi, D. Match Me if You Can: Matchmaking Encryption and Its Applications. In Proceedings of the Advances in Cryptology—CRYPTO 2019, Santa Barbara, CA, USA, 18–22 August 2019; Springer: Cham, Switzerland, 2019; pp. 701–731. [Google Scholar]
Xu, S.; Ning, J.; Li, Y.; Zhang, Y.; Xu, G.; Huang, X.; Deng, R.H. Match in my way: Fine-grained bilateral access control for secure cloud-fog computing. IEEE Trans. Dependable Secur. Comput. 2020, 19, 1064–1077. [Google Scholar] [CrossRef]
Sun, J.; Yuan, Y.; Tang, M.; Cheng, X.; Nie, X.; Aftab, M.U. Privacy-preserving bilateral fine-grained access control for cloud-enabled industrial IOT healthcare. IEEE Trans. Ind. Inform. 2021, 18, 6483–6493. [Google Scholar] [CrossRef]
Chen, J.; Li, Y.; Wen, J.; Weng, J. Identity-Based Matchmaking Encryption from Standard Assumptions. In Proceedings of the Advances in Cryptology—ASIACRYPT 2022, Taipei, Taiwan, 5–9 December 2022; Springer: Cham, Switzerland, 2022; pp. 394–422. [Google Scholar]
Wu, A.; Luo, W.; Weng, J.; Yang, A.; Wen, J. Fuzzy Identity-Based Matchmaking Encryption and Its Application. IEEE Trans. Inf. Forensic Secur. 2023, 18, 5592–5607. [Google Scholar] [CrossRef]
Yan, Z.; Qu, H.; Zhang, X.; Xu, J.L.; Lin, X.J. Identity-based proxy matchmaking encryption for cloud-based anonymous messaging systems. J. Syst. Archit. 2023, 142, 102950. [Google Scholar] [CrossRef]
Sun, J.; Xu, G.; Zhang, T.; Yang, X.; Alazab, M.; Deng, R.H. Privacy-Aware and Security-Enhanced Efficient Matchmaking Encryption. IEEE Trans. Inf. Forensic Secur. 2023, 18, 4345–4360. [Google Scholar] [CrossRef]
Boyen, X. A tapestry of identity-based encryption: Practical frameworks compared. Int. J. Appl. Cryptogr. 2008, 1, 3–21. [Google Scholar] [CrossRef]
Bellare, M.; Rogaway, P. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the ACM Conference on Computer and Communications Security, CCS 1993, Fairfax, VA, USA, 3–5 November 1993; ACM: New York, NY, USA, 1993; pp. 62–73. [Google Scholar]
Tibouchi, M. Encyclopedia of Cryptography and Security; Springer: Boston, MA, USA, 2011. [Google Scholar]
Franklin, J. Proof in Mathematics: An Introduction; Quakers Hill Press: Sydney, Australia, 1996. [Google Scholar]
Choon, J.C.; Hee Cheon, J. An identity-based signature from gap Diffie-Hellman groups. In Proceedings of the 6th International Workshop on Practice and Theory in Public Key Cryptography, PKC 2002, Miami, FL, USA, 6–8 January 2002; Springer: Berlin/Heidelberg, Germany, 2002; pp. 18–30. [Google Scholar]

Figure 1. PHR system model.

Figure 2. IBME-ET system model.

Figure 3. Computational overhead comparison with LLS+16 [15] and XHH+20 [7].

Figure 4. Communication overhead comparison with LLS+16 [15] and XHH+20 [7].

Table 1. Comparison of functionality and security.

	Equality Test	Confidentiality	Authenticity	Anonymity
	Equality Test	Confidentiality	Authenticity	Sender	Receiver
[22]	✗	CPA	✓	✓	✓
[3]	✓	CPA	✗	✗	✗
[15]	✓	CCA	✗	✗	✗
[7]	✓	CCA	✓	✗	✗
Ours	✓	CCA	✓	✓	✓

Table 2. Comparison of computational overhead.

	SKGen	RKGen	Enc	Dec	Auth	Test
[15]	-	$3 \hat{h} + 3 \hat{e}$	$3 \hat{h} + 3 p + 6 e$	$3 p + 2 e$	0	$2 p + 2 e$
[7]	$2 h + 2 e$	$2 \hat{h} + 2 \hat{e}$	$2 \hat{h} + 2 p + 5 e + \hat{e}$	$2 h + 5 p + 2 e + \hat{e}$	0	$4 p$
Ours	$h + e$	$2 \hat{h} + 3 \hat{e}$	$2 \hat{h} + 3 p + 5 e + \hat{e}$	$h + 3 p + 2 e + \hat{e}$	$h + p + 4 \hat{e}$	$6 p$

e, \hat{e}

are exponentiation operations in

G

and

\hat{G}

, respectively.

h, \hat{h}

are hash-to-point operations in

G

and

\hat{G}

, respectively. p is the pairing operation.

Table 3. Comparison of communication overhead.

	Encryption Key	Decryption Key	Trapdoor	Ciphertext
[15]	-	$3 \| \hat{G} \|$	$\| \hat{G} \|$	$4 \| G \| + 5 λ$
[7]	$2 \| G \|$	$2 \| \hat{G} \|$	$\| \hat{G} \|$	$3 \| G \| + \| \hat{G} \| + \| Z_{q} \| + λ$
Ours	$\| G \|$	$3 \| \hat{G} \|$	$2 \| \hat{G} \|$	$3 \| G \| + \| \hat{G} \| + \| Z_{q} \| + λ$

| G |, | \hat{G} |

are the sizes of the elements in groups

G

and

\hat{G}

, respectively.

| Z_{q} |

is the size of the elements in

Z_{q}

, and

λ

is the security level.

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Yan, Z.; Lin, X.; Zhang, X.; Xu, J.; Qu, H. Identity-Based Matchmaking Encryption with Equality Test. Entropy 2024, 26, 74. https://doi.org/10.3390/e26010074

AMA Style

Yan Z, Lin X, Zhang X, Xu J, Qu H. Identity-Based Matchmaking Encryption with Equality Test. Entropy. 2024; 26(1):74. https://doi.org/10.3390/e26010074

Chicago/Turabian Style

Yan, Zhen, Xijun Lin, Xiaoshuai Zhang, Jianliang Xu, and Haipeng Qu. 2024. "Identity-Based Matchmaking Encryption with Equality Test" Entropy 26, no. 1: 74. https://doi.org/10.3390/e26010074

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

	Encryption Key	Decryption Key	Trapdoor	Ciphertext
[15]	-	$3 \| \hat{G} \|$	$\| \hat{G} \|$	$4 \| G \| + 5 λ$
[7]	$2 \| G \|$	$2 \| \hat{G} \|$	$\| \hat{G} \|$	$3 \| G \| + \| \hat{G} \| + \| Z_{q} \| + λ$
Ours	$\| G \|$	$3 \| \hat{G} \|$	$2 \| \hat{G} \|$	$3 \| G \| + \| \hat{G} \| + \| Z_{q} \| + λ$

Article Menu

Identity-Based Matchmaking Encryption with Equality Test

Abstract

1. Introduction

1.1. Motivation

1.2. Related Works

1.3. Contributions

1.4. Organization

2. Preliminaries

2.1. Asymmetric Bilinear Groups

2.2. Assumptions

3. Definitions of IBME-ET

3.1. System Model

3.2. IBME-ET Definition

3.3. Security Definitions

4. Our Construction

5. Security Analysis

6. Performance Evaluation

7. Conclusions

Author Contributions

Funding

Data Availability Statement

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI