An efficient IBE scheme with tight security reduction in the random oracle model

Abstract

We present a new practical identity-based encryption (IBE) system that can be another candidate for standard IBE techniques. Our construction is based on a new framework for realizing an IBE trapdoor from pairing-based groups, which is motivated from the ‘two equation’ revocation technique suggested by Lewko et al. (IEEE Symposium on Security and Privacy, 2010). The new framework enables our IBE system to achieve a tight security reduction to the Decisional Bilinear Diffie–Hellman assumption in the random oracle model. Due to its the tightness, our system can take as input the shorter size of security parameters than the previous practical BF, SK, and $\hbox {BB}_{1}$ systems, which provides better efficiency to our system in terms of computational cost.

1 Introduction

Identity-based encryption (IBE) [45] is a special type of public key encryption where a public key can be any string that carries its own meaning to a user’s identity, such as an e-mail address. As such a meaningful string can be naturally associated with a user, an IBE system does not need a certifying mechanism to ensure that a public key (as the meaningful string) is bound to a user (as the owner of the public key). As opposed to an IBE system, a traditional public key encryption system needs the certifying mechanism to securely distribute public keys, and indeed it must run on a complex architecture called ‘public key infrastructure’.

By virtue of the advantage over the public key encryption, IBE had received considerable interest to cryptographic researchers since Shamir [45] posed the initial question about the existence of such an IBE system. In 2001, Boneh and Franklin [13] proposed the first practical IBE system based on groups with efficiently computable bilinear maps (i.e., paring), along with a formal security definition of IBE. Since then, a large body of work [10, 20–22, 29, 38, 39, 43, 46, 47] has been devoted to constructing pairing-based IBE systems to improve in terms of security and efficiency. Among the previous IBE systems, three of them have been perceived as practical constructions, which are works by Boneh and Franklin [13], Sakai and Kasahara [20, 22, 43], and Boneh and Boyen [10] (denoted as ‘$\hbox {BB}_{1}$’), and thereafter they have been submitted to the IEEE P1363.3 standard for “Identity-Based Cryptographic Techniques using Pairings”.

1.1 Our contribution

In this work we present a new practical IBE system that can be another candidate for standard IBE techniques. Our IBE system results from a new framework for realizing the IBE trapdoor, which is motivated by the ‘two equation’ technique recently suggested by Lewko et al. [40]. One notable advantage of the new framework is that our construction is also pairing-based like BF, SK, and $\hbox {BB}_{1}$ systems, yet it has a tight security reduction to the standard decision bilinear Diffie–Hellman (DBDH) assumption. In order to encrypt arbitrary-length messages, we also suggest a new identity-based key encapsulation mechanism (IBKEM) combined with one-time symmetric-key encryption. Our IBE systems are all proven to be fully secure against chosen ciphertext attacks in the random oracle model. In particular, one-time symmetric-key encryption secure against passive attacks is sufficient for the latter IBE system without the need of the ‘encrypt-then-MAC’ or ‘authenticated symmetric encryption’ paradigm.

None of the three practical BF, SK, and $\hbox {BB}_{1}$ systems provided tightness in their respective security analysis, and in fact there existed significant security gaps between security assumptions and their IBE systems. Later, Attrapadung et al. [5] presented a variant of the BF system that is tightly secure under the DBDH assumption, using the Katz and Wang [33, 36] key generation technique. One might wonder what the benefit from such tightness in security reduction is. The benefit is that we can achieve security of our system straightforwardly from that of the underlying DBDH assumption at the same security level. This means that if we want to instantiate our IBE system at current 80-bit security level, we can use a DBDH-hard group at the same security level. However, this is not the case in BF, SK, and $\hbox {BB}_{1}$ systems where security is loosely reduced to each security assumption by a factor of (at least) $2^{50}$ if we consider a reasonable number of adversarial hash queries as $2^{50}$. The loose security reduction forces us to choose a larger security parameter (regarding DBDH-hard groups) than the 80-bit one even if we want to instantiate them at the 80-bit security level. Importantly, the larger security parameter tends to have an unfavorable effect on computational cost of resulting IBE systems [16]. For instance, when comparing BF, SK, and $\hbox {BB}_{1}$ systems at 128-bit security level with our system at 80-bit security level, ours has about at least 10 times faster decryption than the three systems, and about 22 times faster encryption than the BF system. Also, when compared to Attrapadung et al.’s IBE system (denoted by ‘$\hbox {AFG}^{+}$’) at 80-bit same security level, ours requires 1.2 times longer size of ciphertext, but instead ours achieves about 8.6 times faster encryption and 1.6 times faster decryption under groups with symmetric bilinear maps. To add credence to these results, we give more concrete performance comparison in terms of security and efficiency in Sect. 5.

1.2 Overview of our new technique

BF, SK, and $\hbox {BB}_{1}$ systems have their unique frameworks to realize IBE trapdoors from paring-based groups, respectively. Following Boyen’s naming in [16], each framework is called ‘full-domain-hash’ (for BF), ‘exponent-inversion’ (for SK), and ‘commutative-blinding’ (for $\hbox {BB}_{1}$). Each framework determines both the distinct structure of a private key and different kinds of security assumptions. Also, most of the subsequent paring-based IBE systems fall into one of the three paradigms.

To build our new IBE system, we also come up with a new framework for realizing the IBE trapdoor. As we mentioned before, our framework is motivated by the two equation technique of Lewko et al. [40]. Roughly speaking, the original LSW technique is to use private key elements $(g^{r}, (g_{1}u^{\mathsf {ID}})^{r})$ and ciphertext elements $(g^{s}, (g_{1}u^{\mathsf {ID}'})^{s})$ to compute a pairing value $e(g, u)^{sr}$. Here, $g, g_{1}$, and $u$ are from public parameters. The value $e(g,u)^{sr}$ is then used to recover a message blinding factor $e(g,g)^{\alpha s}$ by pairing $g^{s}$ with an additional key element $g^{\alpha } u^{r}$. The point is that such a pairing value can be obtained only if $\mathsf {ID} \ne \mathsf {ID}'$, and this gives the revocation system [40] where only users whose identities are different from $\mathsf {ID}'$ are able to compute the pairing value. On the other hand, our two equation technique is slightly changed in a way that computing the value $e(g, u)^{sr}$ is possible only if $\mathsf {ID}=\mathsf {ID}'$. This can be done by setting private key elements as $(g^{r}, (\mathcal {H}(\mathsf {ID})u^{\mathrm {tag}_{k}})^{r})$ and ciphertext elements as $(g^{s}, (\mathcal {H}(\mathsf {ID}')u^{\mathrm {tag}_{c}})^{s})$, where $\mathcal {H}$ is a cryptographic hash function and (as we explain below) the probability that $\mathrm {tag}_{k} = \mathrm {tag}_{c}$ is negligible.

As in the BF system, our framework requires a cryptographic hash function $\mathcal {H}$ that maps an identity string $\mathsf {ID} \in \{0,1\}^*$ to a group element $\mathcal {H}(\mathsf {ID})$, but unlike the BF system a private key for an identity $\mathsf {ID}$ is not uniquely determined. A private key $\mathsf {sk}_{\mathsf {ID}}$ consists of three groups $(g^{\alpha }u^{r}, g^{r}, (\mathcal {H}(\mathsf {ID})u^{\mathrm {tag}_{k}})^{r})$, which differs by a randomly-chosen exponent $r$ in $\mathbb {Z}_{p}$. Here, $\alpha$ is the master secret key known only to a key generation center. At this moment, one may wonder how the value $\mathrm {tag}_{k}$ is decided. Indeed, we have that $\mathrm {tag}_{k}=h(g^{\alpha }u^{r}, g^{r}) \in \mathbb {Z}_{p}$ by introducing another cryptographic hash function $h$. Similarly, when encrypting a message $M$, a ciphertext under $\mathsf {ID}$ is constructed as $\big ( M e(g,g)^{\alpha s}, g^{s}, (\mathcal {H}(\mathsf {ID})u^{\mathrm {tag}_{c}})^{s} \big )$ using the hash value $\mathrm {tag}_{c}=h(M e(g,g)^{\alpha s}, g^{s})$. In case of our IBKEM, an arbitrary length message $M$ is encrypted as $\big ( \mathcal {E}_{K}(M), g^{s}, (\mathcal {H}(\mathsf {ID})u^{\mathrm {tag}_{c}})^{s} \big )$ using a one-time symmetric-key encryption algorithm $\mathcal {E}$, where $K=e(g,g)^{\alpha s}$ and $\mathrm {tag}_{c}=h(\mathcal {E}_{K}(M), g^{s})$. If we use a collision-resistant hash function $h$, the correctness error caused by the equality $\mathrm {tag}_{k} = \mathrm {tag}_{c}$ becomes acceptable in practice. Another characteristic of our framework is to use the hash function $h$ to protect the ciphertext element $M e(g,g)^{\alpha s}$ or $\mathcal {E}_{K}(M)$ related to $M$. Indeed, the distinct usage of $h$ enables our system to directly obtain chosen ciphertext security without resorting to other methods such as ‘encrypt-then-MAC’ or ‘authenticated symmetric encryption’ or Fujisaki-Okamoto transform [27].

We now explain how our IBE system can achieve a tight security reduction under the DBDH assumption. In our security proofs, the two hash functions $\mathcal {H}$ and $h$ are modeled as random oracles. Somewhat surprisingly, being able to use two hash functions in generating one group element enables our reduction algorithm to generate private keys for all identities and use any identity as a challenge identity $\mathsf {ID}^*$. Nevertheless, a private key for $\mathsf {ID}^*$ is not helpful to decrypt the challenge ciphertext (that can be constructed under $\mathsf {ID}^*$), which is necessary for solving the so-called ‘self-decryption’ paradox. Notice that similar reductions can be found in [29, 47] that provided full security without random oracles. Let $(g, g^{a}, g^{b}, g^{c}, T)$ be a DBDH instance. Given an identity $\mathsf {ID}_{i}$, the random oracle $\mathcal {H}$ outputs $\mathcal {H}(\mathsf {ID}_{i})=(g^{a})^{\gamma _{i}} g^{\pi _{i}}$ for two randomly-chosen exponents $\gamma _{i}$ and $\pi _{i}$ in $\mathbb {Z}_{p}$. The important point is that the value $\gamma _{i}$ per each identity can be information-theoretically hidden from an adversary’s view and later used for an output value of another random oracle $h$. When creating a private key for $\mathsf {ID}_{i}$, our reduction algorithm is able to generate the key as $\big (g^{\alpha } u^{\widetilde{r}}, g^{\widetilde{r}}, ( \mathcal {H}(\mathsf {ID}_{i}) u^{\mathrm {tag}_{k}} )^{\widetilde{r}} \big )$ by setting $\mathrm {tag}_{k}=h(g^{\alpha } u^{\widetilde{r}}, g^{\widetilde{r}})=\gamma _{i}$ and $\widetilde{r}=b+r$ for a random $r$ in $\mathbb {Z}_{p}$. The validity of the private key is checked under the condition that $\alpha =ab$ and $u=g^{-a}g^{\delta }$ for a random $\delta \in \mathbb {Z}_{p}$. A similar manipulation is taken when generating the challenge ciphertext under $\mathsf {ID}^*$. As $\mathsf {sk}_{\mathsf {ID}^*}$ must not be asked, the value $\gamma ^*$ embedded into $\mathcal {H}(\mathsf {ID}^*)$ will be hidden until the challenge phase (with overwhelming probability) and thus can be reserved for setting $\mathrm {tag}_{c}=\gamma ^*$ (as well as $s=c$ for the DBDH problem). In case when trying to decrypt the challenge ciphertext using $\mathsf {sk}_{\mathsf {ID}^*}$, it should be the case that $\mathrm {tag}_{k}=\gamma ^*$ that was already embedded into $\mathcal {H}(\mathsf {ID}^*)$. Therefore, the decryption is not possible because $\mathrm {tag}_{k}=\mathrm {tag}_{c}$, and this explains how the self-decryption paradox can be solved.

To achieve the chosen ciphertext security, our reduction algorithm needs to deal with adversarial decryption queries. In our security analysis, this is not a big problem as private keys for all identities can be generated and ill-formed ciphertexts are detected via consistency check using pairing. The only problem is that in the event that $\mathrm {tag}_{k}=\mathrm {tag}_{c}$ happens, normal decryption cannot be performed. However, as an output of $h$ as a random oracle is determined by choosing a random value in $\mathbb {Z}_{p}$ and $p$ is exponentially large (e.g., $p$ is a 160-bit prime), our reduction can avoid such a troublesome case in all decryption queries with overwhelming probability.

1.2.1 Comparison to the Katz–Wang technique

As in the BF system and ours, the Katz–Wang technique is based on a cryptographic hash function $\mathcal {H}$ that maps an identity string $\mathsf {ID} \in \{0,1\}^*$ to a group element $\mathcal {H}(\mathsf {ID})$ is required. The key idea is that two public keys $\mathcal {H}(\mathsf {ID}_{i},0)$ and $\mathcal {H}(\mathsf {ID}_{i},1)$ both are used in encrypting a message for one identity $\mathsf {ID}_{i}$, but a private key corresponding to one of two public keys is given to a user with $\mathsf {ID}_{i}$. In security analysis, $\mathcal {H}(\mathsf {ID}_{i},b)$ is programmed to extract a private key for a randomly chosen $b \in \{0,1\}$, whereas the other $\mathcal {H}(\mathsf {ID}_{i},\overline{b})$ is programmed to calculate a CDH value. Therefore, a reduction algorithm can only create a private key for $\mathcal {H}(\mathsf {ID}_{i},b)$, which is enough to answer a private key query. If $\mathsf {ID}_{i}$ is chosen as the challenge identity, the other $\mathcal {H}(\mathsf {ID}_{i},\overline{b})$ will be used to deal with the DBDH problem. This shows that the reduction algorithm can answer private key queries for all identities and use any identity as the challenge $\mathsf {ID}^*$. The self-decryption paradox is then resolved from the fact that the reduction algorithm cannot generate a private key for $\mathcal {H}(\mathsf {ID}_{i}, \overline{b})$ itself.

Compared to our new framework, the Katz–Wang technique causes inefficiency in terms of encryption and decryption costs. In case of the $\hbox {AFG}^+$ system, for instance, two paring computations corresponding to both $\mathcal {H}(\mathsf {ID}_{i},0)$ and $\mathcal {H}(\mathsf {ID}_{i},1)$ should be performed in every encryption, which makes encryption cost a lot more expensive than ours. Moreover, decryption algorithm requires more computation to determine whether ciphertext elements corresponding to $\mathcal {H}(\mathsf {ID}_{i},\overline{b})$ is well formed. This is because each user is given a private key for one $\mathcal {H}(\mathsf {ID}_{i},b)$ for a random $b \in \{0,1\}$ and thus ciphertext elements for $\mathcal {H}(\mathsf {ID}_{i},\overline{b})$ cannot be decrypted directly. In case of the $\hbox {AFG}^+$ system, a variant of Fujisaki–Okamoto transform is used, so that decrypting ciphertext elements for $\mathcal {H}(\mathsf {ID}_{i},b)$ can yield a random value and message that are then used to re-generate ciphertext elements corresponding to $\mathcal {H}(\mathsf {ID}_{i},\overline{b})$.

1.2.2 Comparison to the Coron technique

A similar technique to our key generation framework was previously used by Coron [24], where a private key for $\mathsf {ID}$ is generated as $((\mathcal {H}(\mathsf {ID})u^{-y})^{a}, y)$ using the (fixed) master secret key $a$ and a newly chosen random $y$. The idea behind their security proof was also similar to ours by manipulating the hash output $\mathcal {H}(\mathsf {ID})$ as $(g^{a})^{y}g^{r}$ for two randomly-chosen $y$ and $r$, which leads to a tight security reduction. However, there are several differences between them: in terms of security, Coron-IBE system relies on the square-DBDH assumption¹ [37] whereas our system relies on the DBDH assumption. Obviously, the square-DBDH assumption [37] is stronger than the standard DBDH assumption. In terms of efficiency, Coron-IBE system provides faster decryption than ours, but instead slower encryption and longer size of ciphertexts than ours when comparing both schemes at the same security level. We notice that a variant of Coron-IBE system was also suggested in [24], which achieves a tight security reduction under the DBDH assumption. As the variant provides almost the same efficiency as the original Coron’s system, it has slower encryption and faster decryption, compared to ours. In Sect. 5, we will give an efficiency comparison between the variant and ours in more detail.

1.3 Related work

Boneh and Franklin [13] presented the first practical IBE system based on groups with efficiently computable pairings and defined the formal security notion for IBE known as full security against chosen ciphertext attacks. Most of the subsequent IBE systems followed the notion depending on different kinds of security assumptions. Until now, BF [13], SK [20, 22, 43], and $\hbox {BB}_{1}$ [10] systems have been considered as practical constructions and their security was all demonstrated in the random oracle model.

In an attempt to prove security without random oracles, Canetti et al. [18] suggested a weaker security notion for IBE, known as selective-ID security. Following the weaker notion, Boneh and Boyen [10] proposed two efficient IBE systems, one of which was the basis for $\hbox {BB}_{1}$. Many IBE systems [21, 29, 38, 39, 46, 47] were later suggested to achieve full security without random oracles, but they all become less efficient than the random oracle constructions in practical aspects such as public parameter size or achieving chosen ciphertext security.

Regarding tight security reduction, Attrapadung et al. [5] proposed a Katz–Wang variant of the BF system whose security is tightly reduced to the DBDH assumption. Their construction is fully secure against chosen ciphertext attacks in the random oracle model, but less efficient than our IBE system in terms of both encryption and decryption costs (see Sect. 5 for concrete performance comparison). On the other hand, Gentry IBE [29] achieved the full security without random oracles. Tightness in its security reduction was achieved by relying on a (non-standard) $q$-type assumption where $q$ depends on the number of private key queries that an adversary makes.

The notion of IBE has been extended in two flavors. In a vertical (and hierarchical) extension, IBE can provide a ‘delegation’ mechanism [31, 35] by which private keys for lower-level identities are created from an upper-level identity but the reverse is not possible. Many works [10, 11, 17, 30, 31, 44, 46, 47] have been suggested to realize such a delegation mechanism, also known as hierarchical IBE (HIBE). In a horizontal extension, IBE becomes the special case of the attribute-based encryption (ABE) [9, 34, 42], where attributes (instead of a single identity) are associated with private keys and ciphertexts, respectively, and decryption works only if attributes satisfy a function depending on each ABE system. Furthermore, when attributes (an identity) embedded into ciphertexts are encrypted, ABE (IBE) can also be extended for providing searchable techniques [1, 12] on encrypted data. Recently, the horizontal extensions are conceptually united under the notion of functional encryption (FE) [15].

Finally, we notice that there exist other approaches to build IBE trapdoors without pairings. Cocks [23] and Boneh et al. [14] constructed IBE systems based on the quadratic-residuosity problem and Gentry et al. [32] demonstrated how to build an IBE system based on lattice. Recently, lattice-based IBE can also be extended toward HIBE [2, 3, 19] and FE [4] constructions.

2 Preliminaries

2.1 Identity-based encryption

An IBE system consists of four algorithms:

• Setup($k$) takes a security parameter $k$ as input and outputs a public parameter $\mathsf {PP}$ and a master secret key $\mathsf {msk}$.

• KeyGen($\mathsf {msk}, \mathsf {PP}, \mathsf {ID}$) takes a master secret key $\mathsf {msk}$, a public parameter $\mathsf {PP}$ and an identity $\mathsf {ID} \in \mathcal {ID}$ as inputs, where $\mathcal {ID}$ is an identity space. It outputs $\mathsf {sk}_{\mathsf {ID}}$, a private key for $\mathsf {ID}$.

• Encrypt($\mathsf {PP}, M, \mathsf {ID}$) takes a public parameter $\mathsf {PP}$, a message $M \in \mathcal {M}$, and an identity $\mathsf {ID} \in \mathcal {ID}$ as inputs, where $\mathcal {M}$ is a message space. It outputs $\mathsf {CT}$ under $\mathsf {ID}$, a ciphertext under $\mathsf {ID}$.

• Decrypt($\mathsf {CT}, \mathsf {PP}, \mathsf {sk}_{\mathsf {ID}}$) takes a ciphertext $\mathsf {CT}$ under $\mathsf {ID}$, a public parameter $\mathsf {PP}$, and a private key $\mathsf {sk}_{\mathsf {ID}}$ as inputs. It outputs a message $M$ or a random message.

Correctness For all $\mathsf {ID} \in \mathcal {ID}$ and all $M \in \mathcal {M}$, let $(\mathsf {PP}, \mathsf {msk}) \leftarrow \mathbf{Setup}(k), \mathsf {sk}_{\mathsf {ID}} \leftarrow \mathbf{KeyGen}(\mathsf {msk}, \mathsf {PP}, \mathsf {ID}), \mathsf {CT} \leftarrow \mathbf{Encrypt}(\mathsf {PP}, M, \mathsf {ID})$. We have $M \leftarrow \mathbf{Decrypt}(\mathsf {sk}_{\mathsf {ID}}, \mathsf {PP}, \mathsf {CT})$.

We next define chosen ciphertext security [13] of an IBE system. The security is defined via the following game interacted by a challenger $\mathcal {C}$ and an adversary $\mathcal {A}$:

• Setup: $\mathcal {C}$ runs the setup algorithm to obtain a public parameter $\mathsf {PP}$ and a master secret key $\mathsf {msk}$. $\mathcal {C}$ gives $\mathsf {PP}$ to $\mathcal {A}$.

• Query Phase 1: $\mathcal {A}$ adaptively issues a number of queries where each query is one of:

  • Private key query on $\mathsf {ID}$: $\mathcal {C}$ runs the key generation algorithm to obtain a private key for $\mathsf {ID}$ and gives the key $\mathsf {sk}_{\mathsf {ID}}$ to $\mathcal {A}$.

  • Decryption query on $(\mathsf {CT}, \mathsf {ID})$: $\mathcal {C}$ runs the key generation algorithm to obtain $\mathsf {sk}_{\mathsf {ID}}$ to $\mathcal {A}$ and then runs the decryption algorithm using $\mathsf {CT}_{\mathsf {ID}}$ and $\mathsf {sk}_{\mathsf {ID}}$. It gives the resulting message to $\mathcal {A}$.

• Challenge: $\mathcal {A}$ outputs two equal-length messages $M_{0}, M_{1}$ and an identity $\mathsf {ID}^*$ on which it wishes to be challenged. The only restriction is that $\mathsf {ID}^*$ is not queried in Query Phase 1. $\mathcal {C}$ flips a coin $\sigma \in \{0,1\}$. $\mathcal {C}$ gives $\mathsf {CT}^* \leftarrow \mathbf {Encrypt}(\mathsf {PP}, M_{\sigma }, \mathsf {ID}^*)$ as a challenge ciphertext to $\mathcal {A}$.

• Query Phase 2: $\mathcal {A}$ adaptively issues a number of additional queries where each query is one of:

  • Private key query on $\mathsf {ID}$, where $\mathsf {ID} \ne \mathsf {ID}^*$: $\mathcal {C}$ responds as in Query Phase 1.

  • Decryption query on $(\mathsf {CT}, \mathsf {ID})$, where $(\mathsf {CT}, \mathsf {ID}) \ne (\mathsf {CT}^*, \mathsf {ID}^*)$: $\mathcal {C}$ responds as in Query Phase 1.

• Guess: $\mathcal {A}$ outputs a guess $\sigma ' \in \{0,1\}$. $\mathcal {A}$ wins if $\sigma '=\sigma$.

The advantage of the adversary $\mathcal {A}$ in breaking the chosen ciphertext security of an IBE system $\mathcal {IBE}$ is defined as $\mathbf {Adv}^{\mathrm {CCA}}_{\mathcal {IBE}, \mathcal {A}}=\big |\mathrm {Pr}[b'=b ]- 1/2 \big |$.

Definition 1

We say that an IBE system is $(t, \epsilon , q_{K}, q_{D})$-IND-ID-CCA secure if $\mathbf {Adv}^{\mathrm {CCA}}_{\mathcal {IBE}, \mathcal {A}} < \epsilon$ for any adversary $\mathcal {A}$ that runs in time at most $t$, issues at most $q_{K}$ private key queries, and issues at most $q_{D}$ decryption queries in chosen ciphertext security games.

2.2 One-time symmetric-key encryption

A one-time symmetric-key encryption scheme consists of two algorithms: a deterministic encryption algorithm $\mathcal {E}$ takes a message $M \in \{0,1\}^*$ and a key $K \in \mathcal {K}$ as inputs and outputs a ciphertext $C=\mathcal {E}_{K}(M)$. Here, $\mathcal {K}$ is a key space that is determined by a security parameter $k \in \mathbb {Z}^+$. Another deterministic algorithm $\mathcal {D}$ is a decryption algorithm that takes a ciphertext $C$ and a key $K$ as inputs and outputs a message $M =\mathcal {D}_{K}(C)$.

We define security for a one-time symmetric-key encryption scheme $\mathcal {SKE}=(\mathcal {E}, \mathcal {D})$, which is security against passive attacks [25]. The security is defined via the following game interacted by a challenger $\mathcal {C}$ and an adversary $\mathcal {A}$:

• Setup: $\mathcal {C}$ chooses a random key $K$ in key space $\mathcal {K}(k)$.

• Challenge: $\mathcal {A}$ outputs two equal-length messages $M_{0}$ and $M_{1}$. $\mathcal {C}$ flips a coin $\sigma \in \{0,1\}$ and gives $C^* \leftarrow \mathcal {E}_{K}(M_{\sigma })$ as a challenge ciphertext to $\mathcal {A}$.

• Guess: $\mathcal {A}$ outputs a guess $\sigma ' \in \{0,1\}$. $\mathcal {A}$ wins if $\sigma '=\sigma$.

The advantage of the adversary $\mathcal {A}$ in breaking the passive security of a one-time symmetric-key encryption scheme $\mathcal {SKE}$ is defined as $\mathbf {Adv}^\mathrm{OT-IND }_{\mathcal {SKE}, \mathcal {A}}=\big |\mathrm {Pr}[b'=b ]- 1/2 \big |$.

Definition 2

We say that a one-time symmetric-key encryption scheme is $(t, \epsilon )$-secure against passive attacks if $\mathbf {Adv}^\mathrm{OT-IND }_{\mathcal {SKE}, \mathcal {A}} < \epsilon$ for any adversary $\mathcal {A}$ that runs in time at most $t$ in passive attack games.

2.3 Bilinear maps and complexity assumptions

2.3.1 Bilinear maps

Our schemes will be parameterized by a pairing parameter generator. This is an algorithm $\mathcal {G}$ that on input $k \in \mathbb {N}$ returns the description of multiplicative cyclic groups $\mathbb {G}_{1}$ and $\mathbb {G}_{2}$ of prime order $p$, the description of a multiplicative cyclic group $\mathbb {G}_{T}$ of the same order, and a non-degenerate bilinear pairing $e:\mathbb {G}_{1} \times \mathbb {G}_{2} \rightarrow \mathbb {G}_{T}$. We assume that $g_{1}$ is a generator of $\mathbb {G}_{1}$ and $g_{2}$ is a generator of $\mathbb {G}_{2}$. Following the standard notation in [10, 13], we assume that the function $e$ has the following three properties.

• 1. Bilinear: for all $u \in \mathbb {G}_{1}, v \in \mathbb {G}_{2}$ and $a,b \in \mathbb {Z}$, we have $e(u^{a},v^{b})=e(u,v)^{ab}$.

• 2. Non-degenerate: $e(g_{1}, g_{2})\ne 1$.

• 3. Computable: there is an efficient algorithm to compute the map $e$.

2.3.2 The asymmetric decisional bilinear Diffie–Hellman (DBDH) problem

The asymmetric DBDH problem [41] is defined as follows: given $(g_{1}, g_{1}^{a}, g_{1}^{b}, g_{1}^{c}, g_{2}, g_{2}^{a}, g_{2}^{b}, g_{2}^{c}, T) \in \mathbb {G}_{1}^{4} \times \mathbb {G}_{2}^{4} \times \mathbb {G}_{T}$ as input, output 1 if $T=e(g_{1},g_{2})^{abc}$ and 0 otherwise. For our security analysis, it suffices to consider a slightly weaker problem that does not need to take $g_{1}^{a}$ as input. Hereafter, we refer to the asymmetric DBDH problem as the weaker one. We say that an algorithm $\mathcal {A}$ that outputs $\sigma \in \{0,1\}$ has an advantage $\mathbf {Adv}^\mathrm{ADBDH }_{\mathbb {G}, \mathcal {A}}=\epsilon$ in solving the asymmetric DBDH problem in $\mathbb {G}$ if

$$\begin{aligned}&\Big | \text {Pr} \big [\mathcal {A}(g_{1}, g_{1}^{b}, g_{1}^{c}, g_{2}, g_{2}^{a}, g_{2}^{b}, g_{2}^{c}, e(g_{1},g_{2})^{abc})=0 \big ]\\&\quad -\text {Pr} \big [\mathcal {A}(g_{1}, g_{1}^{b}, g_{1}^{c}, g_{2}, g_{2}^{a}, g_{2}^{b}, g_{2}^{c}, R)=0 \big ] \Big | \ge \epsilon , \end{aligned}$$

where the probability is taken over the random choice of $a, b, c \in \mathbb {Z}_{p}$, the random choice of $R \in \mathbb {G}_{T}$, and the random bits used by $\mathcal {A}$.

Definition 3

We say that the $(t,\epsilon )$-asymmetric DBDH assumption holds in $\mathbb {G}_{1}$ and $\mathbb {G}_{2}$ if no polynomial time adversary $\mathcal {A}$ that runs in time at most $t$ has at least advantage $\epsilon$ in solving the asymmetric DBDH problem in $\mathbb {G}_{1}$ and $\mathbb {G}_{2}$.

3 Our IBE system

3.1 Construction

Setup($k$): Given a security parameter $k \in \mathbb {Z}^+$, the setup algorithm runs $\mathcal {G}(k)$ to obtain a tuple $(p,\mathbb {G}_{1}, \mathbb {G}_{2}, \mathbb {G}_{T},e)$. The algorithm selects a random generator $g_{1} \in \mathbb {G}_{1}$, a random generator $g_{2} \in \mathbb {G}_{2}$, a random group element $u \in \mathbb {G}_{2}$, and a random exponent $\alpha \in \mathbb {Z}_{p}$. The algorithm sets $A=e(g_{1}, g_{2})^{\alpha }$ and chooses two cryptographic hash functions $H_{1}:\{0,1\}^* \rightarrow \mathbb {G}_{2}$ and $H_{2}:\{0,1\}^* \rightarrow \mathbb {Z}_{p}$. The public parameters $\mathsf {PP}$ (with the description of $(p,\mathbb {G}_{1}, \mathbb {G}_{2}, \mathbb {G}_{T},e)$) and the master secret key $\mathsf {msk}$ are generated as

$$\begin{aligned}&\mathsf {PP}=\big (g_{1}, u, A, H_{1}, H_{2} \big ),~~~\mathsf {msk}=g_{2}^{\alpha }. \end{aligned}$$

KeyGen($\mathsf {msk}, \mathsf {PP}, \mathsf {ID}$): To create a private key $\mathsf {sk}_{\mathsf {ID}}$ for an identity $\mathsf {ID} \in \mathcal {ID}$, the key generation algorithm does the following:

• 1. Pick a random exponent $r \in \mathbb {Z}_{p}$.

• 2. Compute $d_{0}=g_{2}^{\alpha }u^{r} \in \mathbb {G}_{2}, d_{1}=g_{1}^{r} \in \mathbb {G}_{1}$, and $\mathrm {tag}_{k}=H_{2}(d_{0},d_{1}) \in \mathbb {Z}_{p}$.

• 3. Compute $d_{2}=\big ( H_{1}(\mathsf {ID})u^{\mathrm {tag}_{k}} \big )^{r} \in \mathbb {G}_{2}$.

• 4. Output a private key $\mathsf {sk}_{\mathsf {ID}}=( d_{0}, d_{1}, d_{2}, \mathrm {tag}_{k} ) \in \mathbb {G}_{2} \times \mathbb {G}_{1} \times \mathbb {G}_{2} \times \mathbb {Z}_{p}$.

Encrypt($\mathsf {PP}, \mathsf {ID}, M$): To encrypt a message $M \in \mathbb {G}_{T}$ under an identity $\mathsf {ID} \in \mathcal {ID}$, the encryption algorithm does as follows:

• 1. Pick a random exponent $s \in \mathbb {Z}_{p}$.

• 2. Compute $C_{0}=A^{s} M \in \mathbb {G}_{T}, C_{1}=g_{1}^{s} \in \mathbb {G}_{1}$, and $\mathrm {tag}_{c}=H_{2}(C_{0},C_{1}) \in \mathbb {Z}_{p}$.

• 3. Compute $C_{2}=\big ( H_{1}(\mathsf {ID})u^{\mathrm {tag}_{c}} \big )^{s} \in \mathbb {G}_{2}$.

• 4. Output a ciphertext $\mathsf {CT}=(C_{0}, C_{1}, C_{2}) \in \mathbb {G}_{T} \times \mathbb {G}_{1} \times \mathbb {G}_{2}$.

Decrypt($\mathsf {PP}, \mathsf {CT}, \mathsf {sk}_{\mathsf {ID}}$): To decrypt a ciphertext $(C_{0}, C_{1}, C_{2})$ using a private key $\mathsf {sk}_{\mathsf {ID}}=(d_{0}, d_{1}, d_{2}, \mathrm {tag}_{k})$ for $\mathsf {ID}$, the decryption algorithm does as follows:

• 1. Compute $\mathrm {tag}_{c}=H_{2}(C_{0}, C_{1}) \in \mathbb {Z}_{p}$ and check if $e\big (C_{1}, H_{1}(\mathsf {ID})u^{\mathrm {tag}_{c}}\big ) \mathop {=}\limits ^{?} e(g_{1}, C_{2})$.

• 2. If the equality above fails, output a random $\widehat{M} \in \mathbb {G}_{T}$.

• 3. Otherwise, check if $\mathrm {tag}_{c} \mathop {=}\limits ^{?} \mathrm {tag}_{k}$ in $\mathbb {Z}_{p}$.

• 4. If the equality above holds, output $\perp$.

• 5. Otherwise, compute

  $$\begin{aligned} M = C_{0} ~\Big / ~ e(C_{1}, d_{0}) \cdot \Bigg ( \frac{e(d_{1}, C_{2})}{e(C_{1}, d_{2})} \Bigg )^{\frac{-1}{\mathrm {tag}_{c}-\mathrm {tag}_{k}}}. \end{aligned}$$

  (1)

3.1.1 Correctness

If $\mathrm {tag}_{c} = \mathrm {tag}_{k}$ in $\mathbb {Z}_{p}$, the decryption algorithm does not work, so that it has the correctness error $1/p$ on each decryption. Otherwise, we can verify that the decryption algorithm works correctly for well-formed ciphertexts as follows:

$$\begin{aligned} e(C_{1}, d_{0}) \cdot \Bigg ( \frac{e(d_{1}, C_{2})}{e(C_{1}, d_{2})} \Bigg )^{\frac{-1}{\mathrm {tag}_{c}-\mathrm {tag}_{k}}}&=e\big (g_{1}^{s}, g_{2}^{\alpha }u^{r} \big ) \cdot \Bigg ( \frac{ e\big ( g_{1}^{r}, (H_{1}(\mathsf {ID})u^{\mathrm {tag}_{c}})^{s} \big ) }{ e\big ( g_{1}^{s}, (H_{1}(\mathsf {ID})u^{\mathrm {tag}_{k}})^{r} \big ) } \Bigg )^{\frac{-1}{\mathrm {tag}_{c}-\mathrm {tag}_{k}}}\\&=e(g_{1}, g_{2}^{\alpha })^{s} e(g_{1}, u)^{sr} \cdot e\big ( g_{1}^{sr}, u^{\mathrm {tag}_{c}-\mathrm {tag}_{k}} \big )^{\frac{-1}{\mathrm {tag}_{c}-\mathrm {tag}_{k}} }\\&=A^{s}. \end{aligned}$$

3.1.2 Encryption and decryption costs

In encryption, the three exponentiations $A^{s}, g_{1}^{s}$, and $u^{\mathrm {tag}_{c} \cdot s}$ can be calculated in fixed bases $A \in \mathbb {G}_{T}, g_{1} \in \mathbb {G}_{1}$, and $u \in \mathbb {G}_{2}$, respectively. Instead, the hashing $H_{1}(\mathsf {ID})$ and its exponentiation $H_{1}(\mathsf {ID})^{s}$ in $\mathbb {G}_{2}$ will be done separately without precomputation in usual situations. Thus, the encryption cost becomes one fixed-base exponentiation in each group $\mathbb {G}_{1}, \mathbb {G}_{2}, \mathbb {G}_{T}$, respectively, one hashing into $\mathbb {G}_{2}$, and one general exponentiation in $\mathbb {G}_{2}$.

Upon decryption, it seems that the decryption algorithm requires computing five pairings, but these can be saved into two parings. We first can change the above formula (1) into:

$$\begin{aligned}&e(C_{1}, d_{0}) \cdot \Bigg ( \frac{e(d_{1}, C_{2})}{e(C_{1}, d_{2})} \Bigg )^{\frac{-1}{\mathrm {tag}_{c}-\mathrm {tag}_{k}}}= \frac{e\Big ( d_{1}^{\frac{-1}{\mathrm {tag}_{c}-\mathrm {tag}_{k}}}, C_{2} \Big )}{e\Big ( C_{1}, d_{0}^{-1}d_{2}^{\frac{-1}{\mathrm {tag}_{c}-\mathrm {tag}_{k}}} \Big )}. \end{aligned}$$

Next, by using the implicit consistency check [38], we do not need to perform the pairing consistency test explicitly. Instead, the decryption algorithm randomizes two elements $H_{1}(\mathsf {ID})u^{\mathrm {tag}_{c}}$ and $g_{1}$ by raising a randomly chosen exponent $\widetilde{r} \in \mathbb {Z}_{p}$ and performs the following computation:

$$\begin{aligned} \frac{e\Big ( d_{1}^{\frac{-1}{\mathrm {tag}_{c}-\mathrm {tag}_{k}}} g_{1}^{\widetilde{r}}, C_{2} \Big )}{e\Big ( C_{1}, d_{0}^{-1}d_{2}^{\frac{-1}{\mathrm {tag}_{c}-\mathrm {tag}_{k}}} (H_{1}(\mathsf {ID})u^{\mathrm {tag}_{c}})^{\widetilde{r}} \Big )}. \end{aligned}$$

(2)

If the pairing test passes, the output of the above equation becomes the same as that of the original decryption algorithm. Otherwise, the fresh random value $\widetilde{r}$ chosen by the decryption algorithm survives and thus prevents an adversary from gaining any information on an ill-formed ciphertext. As a consequence, the decryption cost is determined by the computation in the Eq. 2 that shows five exponentiations and two pairing computations. All the exponentiations can be done in fixed bases such as $g_{1}, d_{1} \in \mathbb {G}_{1}$ and $d_{2}, u, H_{1}(\mathsf {ID}) \in \mathbb {G}_{2}$. Notice that a user with identity $\mathsf {ID}$ can compute $H_{1}(\mathsf {ID}) \in \mathbb {G}$ in advance and prepare for fixed bases related to it, regardless of any received ciphertext. Thus, the decryption cost is concluded with two fixed-base exponentiations in $\mathbb {G}_{1}$, three fixed-base exponentiations in $\mathbb {G}_{2}$, and two parings.

3.1.3 Achieving perfect correctness

Upon decryption, our decryption algorithm cannot proceed in the event that $\mathrm {tag}_{c} = \mathrm {tag}_{k}$ occurs. Obviously, the probability that the event happens is negligible when the value $\mathrm {tag}$ is in $\mathbb {Z}_{p}$ and $p$ is represented by approximately $160$ bits. However, in order to avoid even the negligible correctness error, we can employ an approach suggested in a recent tag-based dual system encryption [47]. A possible solution is to simply run an efficient selectively (chosen-ciphertext) secure IBE system [10] in parallel. When a message is encrypted under $\mathsf {ID}$ with $\mathrm {tag}_{c}$, an encryptor also encrypts the message under the $\mathrm {tag}_{c}$ (as an identity) in the second selective system. When $\mathrm {tag}_{c} \ne \mathrm {tag}_{k}$, we can use our original IBE system. In the unlikely event that $\mathrm {tag}_{c}=\mathrm {tag}_{k}$, we can use the second ciphertext. An alternative approach in [47] such as giving two private keys for an identity $\mathsf {ID}$ seems to not be applicable to our system, because our security analysis shows that a hash value $H_{1}(\mathsf {ID})$ should be assigned to only one $\mathrm {tag}_{k}$.

3.1.4 Stateful key generation algorithm

According to our security analysis, the KeyGen algorithm should be stateful, in that the algorithm stores a random exponent $r \in \mathbb {Z}_{p}$ used to generate a private key for an identity and later the exponent should be used again when the same identity is requested for a private key generation.

3.2 Security

Theorem 1

Let $H_{1}$ and $H_{2}$ be modeled as random oracles. Suppose the $(t',\epsilon ')$-asymmetric DBDH assumption holds in $\mathbb {G}_{1}$ and $\mathbb {G}_{2}$. Then our IBE system is $(t, \epsilon , q_{K}, q_{D})$-IND-ID-CCA secure, where

$$\begin{aligned}&\epsilon \le \Big ( 1 - \frac{q_{H_{2}}}{p} - \frac{2q_{D}}{p} \Big ) \cdot \epsilon ',\\&t \ge t' - \mathcal {O}((q_{K}+q_{D}+q_{H_{1}}) \cdot t_{e} ) - \mathcal {O}(q_{D} \cdot t_{p} ). \end{aligned}$$

Here, $\{q_{H_{1}}, q_{H_{2}}\}$ is the number of $\{H_{1}, H_{2}\}$ oracle queries issued by an adversary, $t_{e}$ is the cost of an exponentiation in $\mathbb {G}_{1}$ or $\mathbb {G}_{2}$, and $t_{p}$ is the cost of a pairing computation.

Proof

Suppose that there exists an adversary $\mathcal {A}$ which can break the CCA security of our IBE system. We can then build an algorithm $\mathcal {B}$ which uses $\mathcal {A}$ to solve an asymmetric DBDH problem in $\mathbb {G}$. On input $(g_{1}, g_{1}^{b}, g_{1}^{c}, g_{2}, g_{2}^{a}, g_{2}^{b}, g_{2}^{c}, T) \in \mathbb {G}_{1}^{3} \times \mathbb {G}_{2}^{4} \times \mathbb {G}_{T}$ , $\mathcal {B}$ attempts to output 1 if $T=e(g_{1}, g_{2})^{abc}$ and 0 otherwise. $\mathcal {B}$ interacts with $\mathcal {A}$ as follows.

Setup $\mathcal {B}$ selects a random element $\delta \in \mathbb {Z}_{p}$ and sets $u=g_{2}^{-a}g_{2}^{\delta }$ and $A=e(g_{1}^{b}, g_{2}^{a})$. Note that $\alpha = ab \in \mathbb {Z}_{p}$, which is unknown to $\mathcal {B}$. Then, $\mathcal {A}$ is given the public key $\mathsf {PK}=( g_{1}, u, A, H_{1}, H_{2})$, where $H_{1}$ and $H_{2}$ are modeled as random oracles.

Query Phase 1 $\mathcal {A}$ issues $H_{1}, H_{2}$, private key, and decryption queries. $\mathcal {B}$ responds as follows:

$H_{1}$ queries To respond to $H_{1}$ queries, $\mathcal {B}$ maintains a list of tuples $<\mathsf {ID}_{i}, \gamma _{i}, \pi _{i}, H_{1}(\mathsf {ID}_{i})>$ as explained below. We refer to this list as the $H_{1}^{list}$. When $\mathcal {B}$ is given an identity $\mathsf {ID}_{i}$ as an input to $H_{1}, \mathcal {B}$ first scans through the $H_{1}^{list}$ to see if the input $\mathsf {ID}_{i}$ appears in a tuple $<\mathsf {ID}_{i}, \gamma _{i}, \pi _{i}, H_{1}(\mathsf {ID}_{i})>$. If it does, $\mathcal {B}$ responds with $H_{1}(\mathsf {ID}_{i})$. Otherwise, $\mathcal {B}$ picks two random exponents $\gamma _{i}, \pi _{i} \in \mathbb {Z}_{p}$ and sets $H_{1}(\mathsf {ID}_{i}) = (g_{2}^{a})^{\gamma _{i}}g_{2}^{\pi _{i}} \in \mathbb {G}_{2}$. $\mathcal {B}$ adds the new tuple $<\mathsf {ID}_{i}, \gamma _{i}, \pi _{i}, H_{1}(\mathsf {ID}_{i})>$ to the $H_{1}^{list}$ and responds with $H_{1}(\mathsf {ID}_{i})$. Recall that the values $\{\gamma _{i}\}$ are information-theoretically hidden to $\mathcal {A}$’s view.

$H_{2}$ queries To respond to $H_{2}$ queries, $\mathcal {B}$ maintains a list of tuples $<W_{i}, Q_{i}, \mu _{i}>$ as explained below. We refer to this list as the $H_{2}^{list}$. When $\mathcal {B}$ is given values $(W_{i}, Q_{i})$, which is in either $\mathbb {G}_{2} \times \mathbb {G}_{1}$ or $\mathbb {G}_{T} \times \mathbb {G}_{1}$, as an input to $H_{2}, \mathcal {B}$ first scans through the $H_{2}^{list}$ to see if the input $(W_{i}, Q_{i})$ appears in a tuple $<W_{i}, Q_{i}, \mu _{i}>$. If it does, $\mathcal {B}$ responds with $H_{2}(W_{i}, Q_{i})=\mu _{i}$. Otherwise, $\mathcal {B}$ picks a random exponent $\mu _{i} \in \mathbb {Z}_{p}$ and sets $H_{2}(W_{i}, Q_{i}) = \mu _{i}$. $\mathcal {B}$ adds the new tuple $<W_{i}, Q_{i}, \mu _{i}>$ to the $H_{2}^{list}$ and responds with $H_{2}(W_{i}, Q_{i})$.

Key queries When $\mathcal {B}$ is given an identity $\mathsf {ID}_{i} \in \mathcal {ID}$ as an input to a private key query, $\mathcal {B}$ selects a random exponent $r \in \mathbb {Z}_{p}$ and (implicitly) sets $\widetilde{r} = b + r \in \mathbb {Z}_{p}$. $\mathcal {B}$ generates key elements $(d_{0,i}, d_{1,i})$ as $d_{0,i}=(g_{2}^{a})^{-r}(g_{2}^{b})^{\delta } g_{2}^{\delta r}$ and $d_{1,i}=g_{1}^{b}g_{1}^{r}$. The validity of those elements can be verified as follows:

$$\begin{aligned}&d_{0,i}=(g_{2}^{a})^{-r}(g_{2}^{b})^{\delta } g_{2}^{\delta r}=g_{2}^{ab} (g_{2}^{-a}g_{2}^{\delta })^{b+r} = g_{2}^{\alpha } u^{\widetilde{r}},\\&d_{1,i}=g_{1}^{b}g_{1}^{r}=g_{1}^{\widetilde{r}}. \end{aligned}$$

Next, $\mathcal {B}$ refers to the $H_{1}^{list}$ to find out the tuple $<\mathsf {ID}_{i}, \gamma _{i}, \pi _{i}, H_{1}(\mathsf {ID}_{i})>$. At this moment, $\mathcal {B}$’s goal is to set $H_{2}(d_{0,i}, d_{1,i})=\gamma _{i}$. Thus, if there is a tuple $<d_{0,i}, d_{1,i}, \gamma _{i}>$ in the $H_{2}^{list}, \mathcal {B}$ can continue the key query process.

In fact, $\mathcal {B}$ can make such a (favorable) tuple always exist in the $H_{2}^{list}$ as follows: whenever $\mathcal {B}$ adds a new tuple $<\mathsf {ID}_{i}, \gamma _{i}, \pi _{i}, H_{1}(\mathsf {ID}_{i})>$ to the $H_{1}^{list}, \mathcal {B}$ generates $\mathsf {sk}_{\mathsf {ID}_{i}}$ by choosing a random $r$, constructing key elements $(d_{0,i}, d_{1,i})$ as above, setting $H_{2}(d_{0,i}, d_{1,i})=\gamma _{i}$, and adding the tuple $<d_{0,i}, d_{1,i}, \gamma _{i}>$ to the $H_{2}^{list}$. On the other hand, if $H_{2}(d_{0,i}, d_{1,i})$ has already be set to $\mu _{i}$, then $\mathcal {B}$ simply adds a new tuple $<\mathsf {ID}_{i}, \mu _{i}, \pi _{i}, H_{1}(\mathsf {ID}_{i})>$ to the $H_{1}^{list}$.

Without loss of generality, let the tuple $H_{2}(d_{0,i}, d_{1,i})=\gamma _{i}$ (where $\gamma _{i}$ is from the tuple in the $H_{1}^{list}$ above) be in the $H_{2}^{list}$. $\mathcal {B}$ generates the element $d_{2,i}$ as $d_{2,i}=(g_{2}^{b})^{\pi _{i} + \gamma _{i} \delta }g_{2}^{(\pi _{i} + \gamma _{i} \delta )r}$. The validity of $d_{2,i}$ can be verified as follows:

$$\begin{aligned} d_{2,i}&=(g_{2}^{b})^{\pi _{i} + \gamma _{i} \delta }g_{2}^{(\pi _{i} + \gamma _{i} \delta )r}=\big ( (g_{2}^{a})^{\gamma _{i}}g_{2}^{\pi _{i}} \cdot (g_{2}^{-a + \delta })^{\gamma _{i}} \big )^{b+r}\\&=\big ( H_{1}(\mathsf {ID}_{i}) u^{H_{2}(d_{0,i}, d_{1,i})} \big )^{\widetilde{r}}. \end{aligned}$$

Then, $\mathcal {B}$ responds with a private key $\mathsf {sk}_{\mathsf {ID}_{i}}=(d_{0,i}, d_{1,i}, d_{2,i}, \mathrm {tag}_{k}=\gamma _{i})$ for the requested identity $\mathsf {ID}_{i}$. Since the key generation algorithm is stateful, $\mathcal {B}$ keeps the random exponent $r$ used for generating $\mathsf {sk}_{\mathsf {ID}_{i}}$.

Decryption queries When $\mathcal {B}$ is given a ciphertext $\mathsf {CT}_{i}=(C_{0,i}, C_{1,i}, C_{2,i})$ (as well as an identity $\mathsf {ID}_{i}$) as an input to a decryption query, $\mathcal {B}$ first refers to the $H_{1}^{list}$ to find out the tuple $<\mathsf {ID}_{i}, \gamma _{i}, \pi _{i}, H_{1}(\mathsf {ID}_{i})>$. (If no tuple exists, $\mathcal {B}$ can run the $H_{1}$-query process in advance as explained above.) Next, $\mathcal {B}$ generates a private key $\mathsf {sk}_{\mathsf {ID}_{i}}=(d_{0,i}, d_{1,i}, d_{2,i}, \mathrm {tag}_{k})$ for the identity $\mathsf {ID}_{i}$ or uses the private key $\mathsf {sk}_{\mathsf {ID}_{i}}$ that was generated before. Recall that $H_{2}(d_{0,i}, d_{1,i})=\gamma _{i}=\mathrm {tag}_{k}$.

To check whether $H_{2}(C_{0,i}, C_{1,i})=\mathrm {tag}_{c} \mathop {=}\limits ^{?} \mathrm {tag}_{k}=H_{2}(d_{0,i}, d_{1,i}), \mathcal {B}$ refers to the $H_{2}^{list}$ to search for a tuple $< C_{0,i}, C_{1,i}, \widetilde{\mu }_{i} >$. If such a tuple regarding $(C_{0,i}, C_{1,i})$ does not exist, $\mathcal {B}$ sets $H_{2}(C_{0,i}, C_{1,i})=\widetilde{\mu }_{i}$ by choosing a random $\widetilde{\mu }_{i} \in \mathbb {Z}_{p}$ and adds the new tuple $<C_{0,i}, C_{1,i}, \widetilde{\mu }_{i}>$ to the $H_{2}^{list}$.

[Case 1] If $\widetilde{\mu }_{i} = \gamma _{i}, \mathcal {B}$ aborts. (We refer to this event as $\mathsf {abort1}$.) Notice that $\gamma _{i}$ is from the tuple $<\mathsf {ID}_{i}, \gamma _{i}, \pi _{i}, H_{1}(\mathsf {ID}_{i})>$ in the $H^{list}_{1}$. In the real decryption, the equality means that $\mathrm {tag}_{c}=\mathrm {tag}_{k}$ and thus the normal decryption is expected to output $\perp$, but $\mathcal {B}$ simply aborts in our simulation. We will give the reason below. Fortunately, the probability that the event $\mathsf {abort1}$ happens is negligible while $H_{2}$ acts like a random oracle.

[Case 2] If $\widetilde{\mu }_{i} \ne \gamma _{i}, \mathcal {B}$ performs the normal decryption using $\mathsf {sk}_{\mathsf {ID}_{i}}$ and replies with the resulting message.

Challenge $\mathcal {A}$ outputs two messages $M_{0}, M_{1} \in \mathbb {G}_{T}$ and an identity $\mathsf {ID}^*$ on which it wishes to be challenged. If necessary, $\mathcal {B}$ runs the algorithm for responding to $H_{1}$ query on $\mathsf {ID}^*$. Let $<\mathsf {ID}^*, \gamma ^*, \pi ^*, H_{1}(\mathsf {ID}^*)>$ be the tuple in the $H_{1}^{list}$ regarding the challenged identity $\mathsf {ID}^*$. Notice that $\mathcal {A}$ cannot query a private key for $\mathsf {ID}^*$. This means that the exponent $\gamma ^*$ in the tuple is not revealed to $\mathcal {A}$ (with overwhelming probability) until the Challenge phase.

$\mathcal {B}$ picks a random bit $\sigma \in \{0,1\}$ and sets $C^*_{0}=M_{\sigma }T$ and $C^*_{1}=g_{1}^{c}$. It sets $H_{2}(C^*_{0}, C^*_{1})=\gamma ^*$. If the tuple $<C^*_{0}, C^*_{1}, \gamma _{j} >$ are already in the $H_{2}^{list}$ and $\gamma _{j} \ne \gamma ^*$, then $\mathcal {B}$ aborts. (We refer to this event as $\mathsf {abort2}$.) Otherwise, $\mathcal {B}$ generates the ciphertext $\mathsf {CT}^*=(C^*_{0}, C^*_{1}, C^*_{2})=\big ( M_{\sigma }T, g_{1}^{c}, (g_{2}^{c})^{\pi ^* + \delta \gamma ^*} \big )$. $\mathcal {B}$ (implicitly) sets $s=c$. The validity of $C_{2}^{*}$ can then be verified as follows:

$$\begin{aligned} (g_{2}^{c})^{\pi ^* + \delta \gamma ^*}&= \big ( (g_{2}^{a})^{\gamma ^*}g_{2}^{\pi ^*} \cdot (g_{2}^{-a + \delta })^{\gamma ^*} \big )^{c} \\&= \big ( H_{1}(\mathsf {ID}^*) u^{H_{2}(C^*_{0}, C^*_{1})} \big )^{s}. \end{aligned}$$

Query Phase 2 $\mathcal {A}$ issues more $\{H_{i}\}_{i=1,2}$, private key, and decryption queries. $\mathcal {B}$ responds as in Query Phase 1. At this phase, however, there are challenging decryption queries $\mathcal {B}$ has to deals with. That happens when $\mathcal {A}$ issues valid ciphertexts such as $\mathsf {CT}_{i}=(C_{0,i}, C^*_{1}, C_{2,i})$ on either $\mathsf {ID}$ or $\mathsf {ID}^*$, where $C^*_{1}$ is the same as in $\mathsf {CT}^*$. We call a ciphertext $\mathsf {CT}=(C_{0}, C_{1}, C_{2})$ under an identity $\mathsf {ID}$ valid if the pairing test upon decryption holds, i.e., $e\big (C_{1}, H_{1}(\mathsf {ID})u^{H_{2}(C_{0},C_{1})}\big ) = e(g_{1}, C_{2})$. Notice that when a queried ciphertext is $\mathsf {CT}_{i}=(C_{0,i}, C_{1,i}, C_{2,i})$ on either $\mathsf {ID}$ or $\mathsf {ID}^*$ where $C_{1,i}\ne C^*_{1}, \mathcal {B}$ can simply respond as in Query Phase 1. Regarding the challenging decryption queries, there are four possible cases:

[Case 1] $\mathsf {CT}_{i}=(C^*_{0}, C^*_{1}, C_{2,i})$ on $\mathsf {ID}^*$, where $C_{2,i} \ne C^*_{2}$. As the ciphertext is valid, it passes the pairing test upon decryption. Thus, $\mathcal {B}$ has that $e\big (C^*_{1}, H_{1}(\mathsf {ID}^{*})u^{H_{2}(C^*_{0},C^*_{1})}\big ) = e(g_{1}, C_{2,i})$. Since $C^*_{1}=g_{1}^{c}$, the equation shows $C_{2,i} = ( H_{1}(\mathsf {ID}^{*})u^{H_{2}(C^*_{0},C^*_{1})} )^{c}$, in which case $C_{2,i}=C^*_{2}$. This means that such a valid ciphertext in the form of $(C^*_{0}, C^*_{1}, C_{2,i})$ such that $C_{2,i} \ne C^*_{2}$ is not possible.

[Case 2] $\mathsf {CT}_{i}=(C_{0,i}, C^*_{1}, C^*_{2})$ on $\mathsf {ID}^*$, where $C_{0,i} \ne C^*_{0}$. This case can happen only if $\mathcal {B}$ sets $H_{2}(C_{0,i}, C^*_{1})=\gamma ^* \in \mathbb {Z}_{p}$. In this case, $\mathcal {B}$ aborts. (We refer to this event as $\mathsf {abort3}$.) This is because otherwise, i.e., $\mathcal {B}$ returns $\perp$ as the normal decryption result and this gives the information of $\gamma ^*$ (as $\mathrm {tag}_{k}$) in the $\mathsf {sk}_{\mathsf {ID}^*}$. $\gamma ^*$ (as $\mathrm {tag}^*_{c}$) is already used for the challenge ciphertext, which gives the knowledge that $\gamma ^*$ is used two times in both $\mathsf {sk}_{\mathsf {ID}^*}$ and $\mathsf {CT}^*$. Naturally, such an unusual leakage can cause $\mathcal {A}$ to distinguish between the simulation and the real attack.

[Case 3] $\mathsf {CT}_{i}=(C_{0,i}, C^*_{1}, C_{2,i})$ on $\mathsf {ID}^*$, where $C_{0,i} \ne C^*_{0}$ and $C_{2,i} \ne C^*_{2}$. As the ciphertext is valid, $\mathcal {B}$ has that $e\big (C^*_{1}, H_{1}(\mathsf {ID}^{*})u^{H_{2}(C_{0,i},C^*_{1})} \big ) = e(g_{1}, C_{2,i})$. Since $C^*_{1}=g_{1}^{c}$, the equation shows that $C_{2,i} = ( H_{1}(\mathsf {ID}^{*})u^{H_{2}(C_{0,i},C^*_{1})} )^{c}$. Also, since $C_{2,i} \ne C^*_{2}$, we know that $H_{2}(C_{0,i},C^*_{1}) \ne \gamma ^*$. Then, $\mathcal {B}$ has that

$$\begin{aligned} C_{2,i}&=\big ( H_{1}(\mathsf {ID}^*) u^{H_{2}(C_{0,i}, C^*_{1})} \big )^{s}\\&=\big ( (g_{2}^{a})^{\gamma ^*}g_{2}^{\pi ^*} \cdot (g_{2}^{-a + \delta })^{H_{2}(C_{0,i},C^*_{1})} \big )^{c}\\&=(g_{2}^{ac})^{\gamma ^* - H_{2}(C_{0,i},C^*_{1})}(g_{2}^{c})^{\pi ^* + \delta H_{2}(C_{0,i},C^*_{1})}, \end{aligned}$$

in which case $\mathcal {B}$ can obtain $g_{2}^{ac}$ by computing $\big [ C_{2,i} / (C^*_{1})^{\pi ^* + \delta H_{2}(C_{0,i},C^*_{1})} \big ]^{1/(\gamma ^* - H_{2}(C_{0,i},C^*_{1}))}$. It follows that $\mathcal {B}$ can solve the asymmetric DBDH problem immediately.

[Case 4] $\mathsf {CT}_{i}=(C_{0,i}, C^*_{1}, C_{2,i})$ on $\mathsf {ID} (\ne \mathsf {ID}^*)$. Let $<\mathsf {ID}, \gamma , \pi , H_{1}(\mathsf {ID})>$ be the tuple in the $H_{1}^{list}$ regarding $\mathsf {ID}$. From the pairing test equation, $\mathcal {B}$ has that $e\big (C^*_{1}, H_{1}(\mathsf {ID})u^{H_{2}(C_{0,i},C^*_{1})}\big ) = e(g_{1}, C_{2,i})$. Since $C^*_{1}=g_{1}^{c}$, the equation shows that $C_{2,i} = ( H_{1}(\mathsf {ID})u^{H_{2}(C_{0,i},C^*_{1})} )^{c}$. If $H_{2}(C_{0,i},C^*_{1}) = \gamma , \mathcal {B}$ outputs $\perp$ as the result of normal decryption.² Otherwise, $\mathcal {B}$ has that

$$\begin{aligned} C_{2,i}&=\big ( H_{1}(\mathsf {ID}) u^{H_{2}(C_{0,i}, C^*_{1})} \big )^{s}\\&=\big ( (g_{2}^{a})^{\gamma }g_{2}^{\pi } \cdot (g_{2}^{-a + \delta })^{H_{2}(C_{0,i},C^*_{1})} \big )^{c}\\&=(g_{2}^{ac})^{\gamma - H_{2}(C_{0,i},C^*_{1})}(g_{2}^{c})^{\pi + \delta H_{2}(C_{0,i},C^*_{1})}, \end{aligned}$$

in which case $\mathcal {B}$ can obtain $g_{2}^{ac}$ by computing $\big [ C_{2,i} / (C^*_{1})^{\pi + \delta H_{2}(C_{0,i},C^*_{1})} \big ]^{1/(\gamma - H_{2}(C_{0,i},C^*_{1}))}$. It follows that $\mathcal {B}$ can solve the asymmetric DBDH problem immediately.

Guess $\mathcal {A}$ outputs a guess $\sigma ' \in \{0,1\}$. $\mathcal {B}$ then outputs its guess $\sigma ' \in \{0,1\}$ as the solution to the asymmetric DBDH problem.

Comment The reason why $\mathcal {B}$ aborts in the event $\mathsf {abort1}$ is that the equality can leak the information on the $\mathrm {tag}_{k}$ such that $H_{2}(d_{0,i}, d_{1,i})=\gamma _{i}=\mathrm {tag}_{k}$, where $\gamma _{i}$ is from the tuple $<\mathsf {ID}_{i}, \gamma _{i}, \pi _{i}, H_{1}(\mathsf {ID}_{i})>$ and $(d_{0,i}, d_{1,i})$ are from the private key $\mathsf {sk}_{\mathsf {ID}_{i}}=(d_{0,i}, d_{1,i}, d_{2,i}, \mathrm {tag}_{k}=\gamma _{i})$. That is, $\mathcal {A}$ is able to know that the value $\mathrm {tag}_{k}(=\gamma _{i})$ is used in $\mathsf {sk}_{\mathsf {ID}_{i}}$, even though all key elements in $\mathsf {sk}_{\mathsf {ID}_{i}}$ are not revealed to $\mathcal {A}$. The problem can then happen in the Challenge phase where $\mathcal {A}$ can select such $\mathsf {ID}_{i}$ as the challenge identity. Then, $\mathcal {B}$ has no choice but to use the same $\gamma _{i}$ as the $\mathrm {tag}^*_{c}$ in constructing the challenge ciphertext such that $H_{2}(C^*_{0}, C^*_{1})=\gamma _{i}$. This gives the information that $\gamma _{i}$ is used two times in both $\mathsf {sk}_{\mathsf {ID}_{i}}$ and $\mathsf {CT}^*$. As mentioned above, such an unusual leakage can cause $\mathcal {A}$ to distinguish between the simulation and the real attack.

Analysis The dominated additional computation that $\mathcal {B}$ requires is both the exponentiations for handling $q_{K}$ private key queries and the pairings for handling $q_{D}$ decryption queries. Thus, the inequality about computational time can easily be obtained.

Next, we assume Cases 3 and 4 described in the Query Phase 2 do not happen (which would rather increase $\mathcal {B}$’s success probability to solve the asymmetric DBDH problem). To analyze $\mathcal {B}$’s advantage, we first prove the following claim that argues that the probability that $\mathcal {B}$ aborts in the simulation is at most $\frac{q_{H_{2}}}{p} + \frac{2q_{D}}{p}$, which is negligible.$\square$

Claim 1

$\mathrm {Pr}[\mathsf {abort}]=\mathrm {Pr}[\mathsf {abort1} \vee \mathsf {abort2} \vee \mathsf {abort3}]$ in the simulation is at most $\frac{q_{H_{2}}}{p} + \frac{2q_{D}}{p}$.

Proof

The event $\mathsf {abort1}$ happens if $\mathcal {B}$ sets $H_{2}(C_{0,i}, C_{1,i})=\gamma _{i}$ for any queried ciphertext $\mathsf {CT}_{i}=(C_{0,i}, C_{1,i}, C_{2,i})$, where $\gamma _{i}$ is from the tuple $<\mathsf {ID}_{i}, \gamma _{i}, \pi _{i}, H_{1}(\mathsf {ID}_{i})>$ in the $H^{list}_{1}$. $\gamma _{i}$ is a pre-determined value and the output of $H_{2}$ query is just set by choosing a random value in $\mathbb {Z}_{p}$. Thus, the probability that the event $\mathsf {abort1}$ happens is at most $1/p$ on each decryption query. Since $\mathcal {B}$ has to handle $q_{D}$ decryption queries, the probability that the event $\mathsf {abort1}$ occurs throughout the simulation becomes at most $q_{D} /p$.

The event $\mathsf {abort2}$ can occur if the value $(M_{\sigma }T, g^{c})$ already exists in the $H_{2}^{list}$ as the input value queried by $\mathcal {A}$. There are $p$ possibilities in picking a value as an input to the $H_{2}$ query, because it is determined by a randomly chosen exponent $c \in \mathbb {Z}_{p}$. This gives the probability at most $q_{H_{2}}/p$ that the event $\mathsf {abort2}$ happens. (If we consider the possible cases from the selection of a value in $\mathbb {G}_{T}$, then the probability will be much smaller.)

Regarding the event $\mathsf {abort3}$, the event happens if $\mathcal {B}$ sets $H_{2}(C_{0,i}, C^*_{1})=\gamma ^*$ for any queried ciphertext $\mathsf {CT}_{i}=(C_{0,i}, C^*_{1}, C^*_{2})$ on $\mathsf {ID}^*$, where $C_{0,i} \ne C^*_{0}$. Here, the value $\gamma ^*$ is the pre-determined value and the output of $H_{2}$ query is just set by choosing a random value in $\mathbb {Z}_{p}$. Thus, the probability that the event $\mathsf {abort3}$ happens is at most $1/p$ on each decryption query. Since $\mathcal {B}$ has to handle $q_{D}$ decryption queries, the probability that the event $\mathsf {abort3}$ occurs throughout the simulation becomes at most $q_{D} /p$.

We know that all the events that $\mathcal {B}$ aborts are relatively independent. As a result, the probability $\mathrm {Pr}[\mathsf {abort1} \vee \mathsf {abort2} \vee \mathsf {abort3}]$ in the simulation is at most $\frac{q_{H_{2}}}{p} + \frac{2q_{D}}{p}$.

From Claim 1, we can see that the probability that $\mathcal {B}$ aborts in the simulation is negligible (under the appropriate selection of security parameters). We argue that as long as $\mathcal {B}$ does not abort, $\mathcal {B}$ provides $\mathcal {A}$ with a perfect simulation whose distribution is identical to the distribution in a real attack. This is because (1) the simulation of $H_{1}$ and $H_{2}$ oracles are obviously perfect as the output values are determined by randomly chosen values in $\mathbb {G}_{2}$ and $\mathbb {Z}_{p}$, respectively, and (2) the simulation of private key oracles is also perfect as each key on an identity $\mathsf {ID}_{i}$ is generated with a randomly chosen exponent $r \in \mathbb {Z}_{p}$ such that $\widetilde{r} = b +r$, and (3) the simulation of decryption oracles is also perfect as it is done via normal decryption using private keys, and (4) the values $\{\gamma _{i}\}$ in the $H_{1}^{list}$ are uniformly distributed and information-theoretically hidden from $\mathcal {A}$’s view until private keys and $\mathsf {CT}^*$ are given to $\mathcal {A}$.

As long as $\mathcal {B}$ does not abort in the simulation, $\mathcal {B}$ can use the $\mathcal {A}$’s advantage to break the chosen ciphertext security straightforwardly. This can be checked as follows: if $T=e(g_{1}, g_{2})^{abc}$, then the challenge ciphertext $\mathsf {CT}^*$ is a valid encryption of $M_{\sigma }$ under $\mathsf {ID}^*$. Otherwise, i.e., if $T$ is random in $\mathbb {G}_{T}$, then $M_{\sigma }T$ is independent of the bit $\sigma$. Thus, if $\mathcal {A}$ distinguishes between the two ciphertexts, then $\mathcal {B}$ can distinguish between the two possible values of $T$ with the same advantage. Therefore, unless $\mathcal {B}$ does not abort, we have the following result:

$$\begin{aligned} \mathbf {Adv}_{\mathcal {IBE}, \mathcal {A}}^{\mathrm {CCA}}(k) \le \left( 1 -\frac{q_{H_{2}}}{p} - \frac{2q_{D}}{p} \right) \cdot \mathbf {Adv}_{\mathbb {G}, \mathcal {B}}^{\mathrm {ADBDH}}(k), \end{aligned}$$

as required. This concludes the proof of Theorem 1.$\square$

3.3 Hash-BDH and BDH construction

Our IBE system can be slightly modified to encrypt arbitrary $n$-bit message strings such as $M \in \{0,1\}^{n}$. To do this, we consider a family of hash functions of the form $H_{3}: \mathbb {G}_{T} \rightarrow \{0,1\}^{n}$ (where $n \in \mathbb {Z}^+$ is determined by the security parameter). A resultant ciphertext is then computed as $C_{0}=H_{3}(A^{s}) \oplus M \in \{0,1\}^{n}, C_{1}=g_{1}^{s} \in \mathbb {G}_{1}$, and $C_{3}=\big ( H_{1}(\mathsf {ID})u^{\mathrm {tag}_{c}} \big )^{s} \in \mathbb {G}_{2}$ where $\mathrm {tag}_{c}=H_{2}(C_{0},C_{1}) \in \mathbb {Z}_{p}$. Decryption can be performed by hashing the pairing value in the equation (2) and XOR-ing the result with $C_{0}$.

The security of the modified system can be proven in two flavors: if $H_{3}$ is a random selection of the (appropriate) hash family, then the modified system is IND-ID-CCA secure under the asymmetric Hash-BDH assumption³ and the security reduction becomes tight. The proof is almost identical to that of Theorem 1. On the other hand, if $H_{3}$ is modeled as a random oracle, then the modified system is IND-ID-CCA secure under the asymmetric BDH assumption⁴ and the security loss becomes $O(q_{H_{3}})$. In this case, $\mathcal {B}$ maintains additional $H_{3}^{list}$ with respect to $H_{3}$, and the challenge ciphertext is constructed as $\mathsf {CT}^*=(C^*_{0}=R, C^*_{1}=g_{1}^{c}, C^*_{2}=\big ( H_{1}(\mathsf {ID}^*)u^{\mathrm {tag}^*_{c}} \big )^{c})$ where $R$ is a randomly chosen string in $\{0,1\}^{n}$ and $\mathrm {tag}^*_{c}=H_{2}(C^*_{0}, C^*_{1})$. $C^*_{0}$ is not relevant to any of two challenged messages, and $\mathcal {B}$ just wants to employ the adversary’s advantage to issue the correct answer of an asymmetric BDH problem as the input of $H_{3}$ query. At the end of the simulation, $\mathcal {B}$ selects a random input value among tuples in the $H_{3}^{list}$ as its answer to the BDH problem, which causes the security loss of $O(q_{H_{3}})$. We notice that CCA security using a similar proof strategy was already used to prove IND-ID-CPA security of ‘BasicIdent’ in [13]. The rest of the proof can be completed based on the proof of the BasicIdent as well as Theorem 1.

4 Extension for arbitrary length messages

We extend our IBE system to deal with arbitrary length messages. Our extended system is based on the well-known framework using the key encapsulation mechanism (KEM) and data encapsulation mechanism (DEM). Identity-based KEM (IBKEM) encrypts a symmetric key under which an arbitrarily long message is encrypted under a symmetric-key cipher DEM. Usually, to achieve CCA security of an entire IBE system, both IBKEM and DEM should be CCA-secure respectively [8] or DEM should be an authenticated symmetric-key encryption [39]. However, a slight difference resides in our extended IBE system where it is sufficient for DEM to be a one-time symmetric-key encryption secure against passive attacks [25]. In practice, such a weak DEM can easily be instantiated with a block cipher using a so-called ‘counter mode’. The difference is because our IBE system is able to provide a consistency check (using pairing) to see if ciphertext elements including the DEM part are the same as what an encryptor constructed. Such a weak DEM when achieving CCA security can also be seen in the CCA-secure BF-IBE system [13].

4.1 Construction

Setup($k$): As in the previous IBE system. Additionally, the setup algorithm chooses a one-time symmetric-key encryption scheme $\mathcal {SKE}=(\mathcal {E}, \mathcal {D})$. The public parameters $\mathsf {PP}$ and the master secret key $\mathsf {msk}$ are generated as

$$\begin{aligned}&\mathsf {PP}=\big (g_{1}, u, A, H_{1}, H_{2}, \mathcal {SKE} \big ),~~~\mathsf {msk}=g_{2}^{\alpha }. \end{aligned}$$

KeyGen($\mathsf {msk}, \mathsf {PP}, \mathsf {ID}$): As in the previous IBE system.

Encrypt($\mathsf {PP}, \mathsf {ID}, M$): To encrypt an arbitrary length message $M \in \{0,1\}^*$ under an identity $\mathsf {ID} \in \mathcal {ID}$, the encryption algorithm does as follows:

• 1. Pick a random exponent $s \in \mathbb {Z}_{p}$.

• 2. Compute a key $K = A^{s} \in \mathbb {G}_{T}$.

• 3. Compute $C_{0}=\mathcal {E}_{K}(M), C_{1}=g_{1}^{s} \in \mathbb {G}_{1}$, and $\mathrm {tag}_{c}=H_{2}(C_{0},C_{1}) \in \mathbb {Z}_{p}$.

• 4. Compute $C_{2}=\big ( H_{1}(\mathsf {ID})u^{\mathrm {tag}_{c}} \big )^{s} \in \mathbb {G}_{2}$.

• 5. Output a ciphertext $\mathsf {CT}=(C_{0}, C_{1}, C_{2}) \in \{0,1\}^{|M|} \times \mathbb {G}_{1} \times \mathbb {G}_{2}$.

Decrypt($\mathsf {PP}, \mathsf {CT}, \mathsf {sk}_{\mathsf {ID}}$): To decrypt a ciphertext $(C_{0}, C_{1}, C_{2})$ using a private key $\mathsf {sk}_{\mathsf {ID}}=(d_{0}, d_{1}, d_{2}, \mathrm {tag}_{k})$ for $\mathsf {ID}$, the decryption algorithm does as follows:

• 1. Compute $\mathrm {tag}_{c}=H_{2}(C_{0}, C_{1})$ and check whether or not $e\big (C_{1}, H_{1}(\mathsf {ID})u^{\mathrm {tag}_{c}} \big ) \mathop {=}\limits ^{?} e(g_{1}, C_{2})$.

• 2. If the equality above fails, choose a random key $\widetilde{K}$ from $\mathbb {G}_{T}$ and output $\mathcal {D}_{\widetilde{K}}(C_{0})$.

• 3. Otherwise, check if $\mathrm {tag}_{c} \mathop {=}\limits ^{?} \mathrm {tag}_{k}$.

• 4. If the equality above holds, output $\perp$.

• 5. Otherwise, compute a key

  $$\begin{aligned}&K = e(C_{1}, d_{0}) \cdot \Bigg ( \frac{e(d_{1}, C_{2})}{e(C_{1}, d_{2})} \Bigg )^{\frac{-1}{\mathrm {tag}_{c}-\mathrm {tag}_{k}}}. \end{aligned}$$

• 6. Output a message $M=\mathcal {D}_{K}(C_{0})$.

Remark

The efficiency of the IBE system above is almost the same as that in the previous section. Notice that the KEM part in a ciphertext is not expanded and the DEM part $C_{0}=\mathcal {E}_{K}(M)$ is also hashed and embedded into the ciphertext element $C_{3}$. We can check the consistency of ciphertext elements including the DEM part and therefore avoid to use an authenticated encryption scheme with the help of a secure message authentication code (MAC). In practice, a one-time symmetric-key encryption scheme $\mathcal {SKE}$ with key-space $\mathcal {K} \in \{0,1\}^{k}$ can be implemented by AES with a counter mode, and a real symmetric key for $\mathcal {E}$ can be obtained via a key-derivation function [25] that maps an element from $\mathbb {G}_{T}$ into $2k$-bit strings.

4.2 Security

Theorem 2

Let $H_{1}$ and $H_{2}$ be modeled as random oracles. Suppose the $(t',\epsilon ')$-asymmetric DBDH assumption holds in $\mathbb {G}_{1}$ and $\mathbb {G}_{2}$ and the one-time symmetric-key encryption scheme $\mathcal {SKE}$ is $(t'', \epsilon '')$-secure against passive attacks. Then our IBE system is $(t, \epsilon , q_{K}, q_{D})$-IND-ID-CCA secure, where

$$\begin{aligned}&\epsilon \le \Big (1- \frac{q_{H_{2}}}{p} - \frac{2q_{D}}{p} \Big ) \cdot (\epsilon ' + \epsilon ''),\\&t \ge t' + t''- \mathcal {O}((q_{K}+q_{D} + q_{H_{1}}) t_{e} ) - \mathcal {O}(q_{D} (t_{p} + t_{symD} ) ). \end{aligned}$$

Here, $\{q_{H_{1}}, q_{H_{2}}\}$ is the number of $\{H_{1}, H_{2}\}$ oracle queries issued by an adversary, $t_{e}$ is the cost of an exponentiation in $\mathbb {G}_{1}$ or $\mathbb {G}_{2}, t_{p}$ is the cost of a pairing computation, and $t_{symD}$ is the cost of symmetric-key decryption in the $\mathcal {SKE}$.

Proof

The proof of Theorem 2 is almost similar to that of Theorem 1. For clarity, we reconstruct the entire proof by creating a sequence of hybrid games. If necessary, we will adapt several notations that appeared in the proof of Theorem 1 without explicit explanation.

Let $\mathcal {A}$ be an adversary on the chosen ciphertext security of our IBE system above. We will consider two games, $\mathbf {Game~ 0}$ and $\mathbf {Game~ 1}$, each game interacting with $\mathcal {A}$. Let $X_{i}$ (for $i=0,1$) be the event that in $\mathbf {Game~ i}, \mathcal {A}$ wins the game.

$\mathbf {Game~ 0}$ The game is a real attack game of chosen ciphertext security, so that (for a security parameter $k$) we have

$$\begin{aligned}&| \mathrm {Pr}[X_{0}] - 1/2 | = \mathbf {Adv}^\mathrm{CCA }_{\mathcal {IBE}, \mathcal {A}}(k). \end{aligned}$$

(3)

$\mathbf {Game~1}$ The game is the same as Game 0, except that the value $K^*$ used for a symmetric key in $\mathsf {CT}^*$ is replaced by a random value $K \in \mathbb {G}_{T}$. Unless the events $\mathsf {abort1}$ and $\mathsf {abort2}$ and $\mathsf {abort3}$ (defined in the proof of Theorem 1) occur in $\mathbf {Game~ 1}$, we have

$$\begin{aligned}&| \mathrm {Pr}[X_{1}] - \mathrm {Pr}[X_{0}] | = \mathbf {Adv}^\mathrm{ADBDH }_{\mathbb {G}, \mathcal {B}_{1}}(k), \end{aligned}$$

(4)

where $\mathcal {B}_{1}$ is an algorithm whose goal is to solve the asymmetric DBDH problem.

The proof of (4) is almost the same as that of Theorem 1. On an input $(g_{1}, g_{1}^{b}, g_{1}^{c}, g_{2}, g_{2}^{a}, g_{2}^{b}, g_{2}^{c}, T)$, we describe how $\mathcal {B}_{1}$ constructs $\mathsf {CT}^*$: when $\mathcal {A}$ outputs two messages $M_{0}, M_{1} \in \{0,1\}^*$ of the same length and an identity $\mathsf {ID}^*, \mathcal {B}_{1}$ picks a random bit $\sigma \in \{0,1\}$. Let $<\mathsf {ID}^*, \gamma ^*, \pi ^*, H_{1}(\mathsf {ID}^*)>$ be the tuple in the $H_{1}^{list}$ regarding $\mathsf {ID}^*$. $\mathcal {B}_{1}$ sets $C^*_{0}=\mathcal {E}_{T}(M_{\sigma }), C^*_{1}=g_{1}^{c}$, and $H_{2}(C^*_{0}, C^*_{1})=\gamma ^*$. If the tuple $<C^*_{0}, C^*_{1}, \gamma _{j} >$ are already in the $H_{2}^{list}$ and $\gamma _{j} \ne \gamma ^*$, then $\mathcal {B}_{1}$ aborts. (In the proof of Theorem 1 (and thus Game 1 above), the event has already been taken into consideration under the event $\mathsf {abort2}$.) Otherwise, the challenge ciphertext is generated as $\mathsf {CT}^*=(C^*_{0}, C^*_{1}, C^*_{2})=\big ( \mathcal {E}_{T}(M_{\sigma }), g_{1}^{c}, (g_{2}^{c})^{\pi ^* + \delta \gamma ^*} \big )$. Other slight differences exist in handling decryption and $H_{2}$ queries. Answering decryption queries needs to run $\mathcal {D}$ of $\mathcal {SKE}$, and inputs $(W_{i}, Q_{i})$ to $H_{2}$ queries are in either $\mathbb {G}_{2} \times \mathbb {G}_{1}$ or $\{0,1\}^{*} \times \mathbb {G}_{1}$ (instead of $\mathbb {G}_{2} \times \mathbb {G}_{1}$ or $\mathbb {G}_{T} \times \mathbb {G}_{1}$). However, the way of answering $H_{2}$ queries is the same as in the proof of Theorem 1. Thus, the probability that the events $\mathsf {abort1}$ and $\mathsf {abort2}$ and $\mathsf {abort3}$ happen in proving the Eq. 4 is the same as that in Theorem 1.

Finally, in $\mathbf {Game~ 1}$ we have the following relation that directly comes from the definition of ciphertext indistinguishability for $\mathcal {SKE}$ unless the event $\mathsf {abort3}$ occurs in $\mathbf {Game~ 1}$:

$$\begin{aligned}&|\mathrm {Pr}[X_{1}] - 1/2| = \mathbf {Adv}^\mathrm{OT-IND }_{\mathcal {SKE}, \mathcal {B}_{2}}(k), \end{aligned}$$

(5)

where $\mathcal {B}_{2}$ is an algorithm whose goal is to break $\mathcal {SKE}$.

One thing we want to clarify is that $\mathcal {B}_{2}$ does not need to deal with any decryption query regarding the one-time symmetric-key encryption scheme $\mathcal {SKE}$. To prove the Eq. 5, $\mathcal {B}_{2}$ relays the two messages $M_{0}, M_{1} \in \{0,1\}^*$ to its challenger and is given a challenge ciphertext $\mathcal {E}_{K^*}(M_{\sigma })$ for a random (unknown) key $K^* \in \mathbb {G}_{T}$. $\mathcal {B}_{2}$ then reconstructs its challenge ciphertext $\mathsf {CT}^*$ as explained above and gives it to $\mathcal {A}$. Whenever $\mathcal {A}$ requests any decryption query on $\mathsf {CT}_{i}, \mathcal {B}_{2}$ can use private keys (generated by $\mathcal {B}_{2}$) to perform normal decryption. The only troublesome queries are possible when $\mathcal {A}$ issues decryption queries on valid $\mathsf {CT}_{i}=(C_{0,i}, C^*_{1}, C_{2,i})$, in which case $\mathcal {B}_{2}$ would have to decrypt $\mathsf {CT}_{i}$ with the unknown symmetric-key $K^*$. Fortunately, those troublesome queries can be handled as in Query Phase 2 of Theorem 1. More precisely, there are four possible cases:

[Case 1] $\mathsf {CT}_{i}=(C^*_{0}, C^*_{1}, C_{2,i})$ on $\mathsf {ID}^*$, where $C_{2,i} \ne C^*_{2}$. As before, it is impossible to generate a valid ciphertext $(C^*_{0}, C^*_{1}, C_{2,i})$ such that $C_{2,i} \ne C^*_{2}$.

[Case 2] $\mathsf {CT}_{i}=(C_{0,i}, C^*_{1}, C^*_{2})$ on $\mathsf {ID}^*$, where $C_{0,i} \ne C^*_{0}$. This happens only if $\mathcal {B}$ sets $H_{2}(C_{0,i}, C^*_{1})=\mathrm {tag}^*_{c} \in \mathbb {Z}_{p}$. In this case, $\mathcal {B}$ aborts. (This event has already been referred to as $\mathsf {abort3}$.)⁵

[Case 3] $\mathsf {CT}_{i}=(C_{0,i}, C^*_{1}, C_{2,i})$ on $\mathsf {ID}^*$, where $C_{0,i} \ne C^*_{0}$ and $C_{2,i} \ne C^*_{2}$. We have shown that the $\mathcal {A}$’s ability to issue such a valid ciphertext can be used to compute $g_{2}^{ac}$ in the previous Query Phase 2.

[Case 4] $\mathsf {CT}_{i}=(C_{0,i}, C^*_{1}, C_{2,i})$ on $\mathsf {ID} (\ne \mathsf {ID}^*)$. $\mathcal {B}$ generates $\mathsf {sk}_{\mathsf {ID}}$ and performs normal decryption. If $H_{2}(C_{0,i},C^*_{1}) = \mathrm {tag}_{k}$ where $\mathrm {tag}_{k}$ is from $\mathsf {sk}_{\mathsf {ID}}$, then $\mathcal {B}$ outputs $\perp$ as the result of normal decryption. Otherwise, we also have shown that the $\mathcal {A}$’s ability to issue such a valid ciphertext can be used to compute $g_{2}^{ac}$ in the previous Query Phase 2.

Analysis It is easy to see that time complexity is obviously achieved as argued in Theorem 2. As long as the events $\mathsf {abort1}$ and $\mathsf {abort2}$ and $\mathsf {abort3}$ do not happen throughout the simulation, the Eqs. 4 and 5 hold. As a result, by putting the results of all relations 3, 4, and 5 above together, we gain a bound on the $\mathcal {A}$’s advantage as follows:

$$\begin{aligned} \mathbf {Adv}^\mathrm{CCA }_{\mathcal {IBE}, \mathcal {A}}(k) \le \Big ( 1- \frac{q_{H_{2}}}{p} - \frac{2q_{D}}{p} \Big ) \cdot \left( \mathbf {Adv}^\mathrm{ADBDH }_{\mathbb {G},\mathcal {B}_{1}}(k) + \mathbf {Adv}^\mathrm{OT-IND }_{\mathcal {SKE}, \mathcal {B}_{2}}(k) \right) \!, \end{aligned}$$

which concludes the proof of Theorem 2.$\square$

5 Comparison to previous IBE systems

In this section we compare our IBE system with the previous practical IBE systems such as BF [13], SK [20, 22, 43], the CCA-secure variant [16]⁶ of $\hbox {BB}_{1}$, Attrapadung et al.’s IBE system [5] (denoted as ‘$\hbox {AFG}^{+}$’), and the CCA-secure variant⁷ of [24] (denoted as ‘$\hbox {Cor}^{\mathsf {FO}}$’) in terms of security and efficiency. Following Bellare and Rogaway [6, 39], we estimate the number of (random oracle) hash queries as $q_{H}=2^{50}$ and the number of private key queries as $q_{K}=2^{25}$. For a fair comparison we consider the asymmetric decisional type of security assumptions in each system, so that BF, $\hbox {BB}_{1}, \hbox {AFG}^{+}$, and $\hbox {Cor}^{\mathsf {FO}}$ systems are based on the asymmetric DBDH assumption and the SK system relies on the asymmetric version of $q$-decisional bilinear Diffie–Hellman inversion (DBDHI) assumption [10]. We also refer to [28] for correcting a flawed security analysis of BF system. Table 1 presents the comparison result with respect to security assumptions and reductions, which was also addressed by [16, 24, 39]. The ‘asymptotic bound’ in the security reduction means that the advantage of breaking the CCA security of an IBE system is larger than that of solving a security assumption in comparable time, by a factor of each bound. In other words, the larger the bound is, the bigger the security loss (i.e., gap) is between an IBE system and a security assumption. In Table 1, a concrete bound at each IBE system is estimated when considering the reasonable number of adversarial queries $q_{H}$ and $q_{K}$ as $2^{50}$ and $2^{25}$, respectively. The respective bound tells us that, roughly speaking,

$$\begin{aligned} \mathbf {Adv}^{\mathrm {CCA}}_{\mathcal {IBE},\mathcal {A}} \le (\mathrm {bound}) \cdot \mathbf {Adv}^{\mathrm {Assumption}}_{\mathcal {B}} \end{aligned}$$

(6)

for algorithms $\mathcal {A}$ and $\mathcal {B}$. When the bound is quite large, we have to choose a larger security parameter $k$ for a security assumption so that we can make $(\mathrm {bound}) \cdot \mathbf {Adv}^{\mathrm {Assumption}}_{\mathcal {B}}$ small and consequently $\mathbf {Adv}^{\mathrm {CCA}}_{\mathcal {IBE},\mathcal {A}}$ small enough at a desired security level. This is the reason why one has to choose a larger system security parameter than an idealized security level when a large security loss arises at reduction. In contrast to the BF, SK, and $\hbox {BB}_{1}$ systems, $\hbox {AFG}^{+}, \hbox {Cor}^{\mathsf {FO}}$ and our systems have tight security reductions to the asymmetric DBDH assumption and thus we can say that the latter IBE systems are as secure as the hardness of the asymmetric DBDH assumption. We notice that security of all the compared IBE systems above is proven in the random oracle model.

Table 1 Security comparison between the previous IBE systems and ours

Table 2 presents an efficiency comparison between the previous IBE systems and ours, considering the space overheads of the various data types and the number of group operations. To give more detailed comparison based on the security loss, we employ Boyen’s work [16] that investigates relatively estimated calculation times for various operations and representation sizes for group elements. Table 3 shows the values when considering SS curves at the 80-bit security level and MNT curves at security levels 80 and 128. Especially, following [16], we consider that a ratio of two pairings can be optimized into about 1.2 pairing in all the three cases. We focus on the $80$-bit security as a desired security level of IBE system. As mentioned above, BF, SK, and $\hbox {BB}_{1}$ systems all have concrete security loss of at least $2^{50}$, so that they must have a larger system security parameter than 80 bits. Obviously, it will be unfair to straightforwardly compare ours with the three systems at the same security level. As a warm-up case, however, we give an efficiency comparison when considering supersingular (SS) curves at the 80-bit security level. Table 4 shows the comparison result, which demonstrates that our system is comparable to the other IBE systems in terms of all efficiency respects even when not considering security losses caused by the security reductions. In particular, compared to $\hbox {AFG}^+$ and $\hbox {Cor}^{\mathsf {FO}}$ systems, ours has a remarkable advantage in terms of encryption, which is about 8.6 times faster than $\hbox {AFG}^+$ and about 4.5 times faster than $\hbox {Cor}^{\mathsf {FO}}$.

Table 2 Efficiency comparison between the previous IBE systems and ours

Table 3 Representation sizes and estimated calculation times for various algebraic operations

Table 4 Estimated calculation times for CCA-secure IBE systems at 80-bit security level (not considering security loss)

For a fairer comparison, we try to compensate for such security losses by boosting the security parameter of the underlying assumptions. There is no general rule of such compensation, but we might be able to use conjectures that were made by Bellare and Rogaway [7] for advantage functions of various block ciphers. For instance, the advantage of DES with 128-bit keys was conjectured as (roughly speaking) $\mathbf {Adv}^{\mathrm {CPA}}_{\mathrm {AES}} \le c / 2^{128}$ for some constant $c$. A similar approach can be made for advantages of IBE systems, so that we want to make $\mathbf {Adv}^{\mathrm {CCA}}_{\mathcal {IBE}, \mathcal {A}} \le c / 2^{80}$ at the 80-bit security level. In that case, Eq. 6 tells us that we have to make $\mathbf {Adv}^{\mathrm {Assumption}}_{\mathcal {B}} \le c / 2^{130}$ when considering that the security loss is bounded under $2^{50}$. For simplicity, we assume that the reduction bounds in both BF and SK systems are $2^{50}$ (although they are much larger than it). Under these assumptions, the actual security parameter must be of 130 bits in size (approximately) to gain the real system security of an IBE system at the desired 80-bit security level. To accomplish this, we consider that the BF, $\hbox {BB}_{1}$, and SK systems are instantiated in MNT curves at the 128-bit security level, whereas $\hbox {AFG}^{+}, \hbox {Cor}^{\mathsf {FO}}$, and ours are based on MNT curves at the 80-bit security level. Also, we assume that the output length of all hash functions (except the MapToPoint hash) is 160 bits and the MapToPoint hash function necessary for BF, $\hbox {AFG}^{+}, \hbox {Cor}^{\mathsf {FO}}$, and ours maps an identity to a group element in $\mathbb {G}_{2}$. Table 5 shows the comparison result between those CCA-secure IBE systems. Compared to BF, SK, and $\hbox {BB}_{1}$ at the 128-bit security level, ours gives an advantage in terms of decryption, because decryption in ours is at least 6 times faster than those systems. Compared to $\hbox {AFG}^{+}$ and $\hbox {Cor}^{\mathsf {FO}}$ systems at the 80-bit security level, our IBE system provides at least about 1.6 times faster encryption than the others. However, $\hbox {AFG}^{+}$ system gives at least about 2.4 times shorter size of ciphertext (considering only KEM part) than $\hbox {Cor}^{\mathsf {FO}}$ and ours, and $\hbox {Cor}^{\mathsf {FO}}$ system provides at least about 1.8 times faster decryption than $\hbox {AFG}^{+}$ and ours (when a ratio of two pairings is considered as 2 pairings). It is therefore unclear which of the (asymmetric) DBDH-based IBE systems with tight security reduction must be chosen in general. It depends on the context of which efficiency factor out of encryption, decryption, and ciphertext size is taken into account significantly.

Table 5 Estimated calculation times for CCA-secure IBE systems at corrected 80-bit security level

6 Discussion

6.1 On extension for hierarchical IBE system

In a hierarchical IBE (HIBE) system [31, 35], a user’s identity $\mathsf {ID}$ can be hierarchically scalable by delegating a private key $\mathsf {sk}_{\mathsf {ID}}$ to lower-level identities. For instance, a user with identity $\mathsf {ID}_{1}$ can generate a private key $\mathsf {sk}_{\mathsf {ID}'}$ for a lower-level identity $\mathsf {ID}'=(\mathsf {ID}_{1}, \mathsf {ID}_{2})$ using its own private key $\mathsf {sk}_{\mathsf {ID}_{1}}$. The reverse of key generation (i.e., from lower level to upper level) is not possible. This is called the ‘delegation mechanism’. Using it, an HIBE system can be used for several applications including forward-secure encryption [18] and conversion for public key broadcast encryption [26]. In a security analysis for HIBE, an adversary is given the capability to request either private keys generated by a key generation center or ones delegated from upper-level identities of its choice.

One may wonder if our IBE system can be extended for supporting hierarchical identities. As far as we know, the answer is no. Since the private key structure of our system has similarity to that of Waters’ tag-based dual system encryption [47], it may seem possible that a similar extension method can be applied to ours. However, the problem occurs because of the ‘locked’ tag values associated with upper-level identities. In the security analysis of the resulting HIBE system, an adversary requests a private key for an identity $\mathsf {ID}=(\mathsf {ID}_{1}, \ldots , \mathsf {ID}_{\ell })$. In order to generate a private key $\mathsf {sk}_{\mathsf {ID}}$, we have to use one of the hidden values⁸ that are embedded into $\{H_{i}(\mathsf {ID}_{i})\}$ for $i=1,\ldots ,\ell$. Assume we use a hidden value in $H_{k}(\mathsf {ID}_{k})$ for $k\le \ell$. In that case, the tag values corresponding to $j$ for $j <k$ are chosen at random and mapped to $H_{2}$-query outputs in an appropriate sense. However, those random tag values are locked and cannot be changed into other different values. The adversary can still query private keys for upper-level identities, e.g., $\mathsf {ID}'=(\mathsf {ID}_{1}, \ldots , \mathsf {ID}_{k-1})$, in which $\mathsf {sk}_{\mathsf {ID}'}$ should be generated using those locked tags. Unfortunately, such a private key cannot be generated. One solution would be to use hidden values for each level of hierarchy, but instead it can reveal all hidden tag values that must be secretly reserved for challenge ciphertext. We leave it as an open problem to build a hierarchical version from our IBE system.