Efficient identity-based online/offline encryption and signcryption with short ciphertext

Abstract

The technique of online/offline is regarded as a promising approach to speed up the computation of encryption, because the most part of computation, such as pairing over points on elliptic curve and exponentiation in groups, can be pre-computed in the offline phase without knowing the message to be encrypted and/or recipient’s identity. The online phase only requires light computation, such as modular multiplication. In this paper, we propose two novel identity-based online/offline schemes: a full secure identity-based online/offline encryption scheme and an identity-based online/offline signcryption scheme. Compared to the other schemes in the literature, our schemes achieve the shortest ciphertext size in both offline and online phases and demonstrate the best performance in offline computation. Our schemes are applicable to devices with limited computation power. They are proven secure in the random oracle model.

1 Introduction

Identity-based encryption (IBE) was introduced by Shamir in 1984 [19] to eliminate the certificate in public key infrastructure. In an IBE system, each user’s public key can be an arbitrary string binding the user’s identity, such as an email address or a telephone number. If a new user wants to join the network in a network system based on IBE, there is no need for other users in the network to verify its certificate in order to communicate securely.

The merits of identity-based cryptography have drawn a lot of attraction (e.g., [1, 2, 4, 6, 10, 22, 23]). However, all of these works involve computations such as pairings over points on elliptic cure and exponentiations (point multiplications) in groups. These operations are regarded as the most costly computations in cryptography, which might not be applicable for lightweight devices. An elegant solution to reduce the computational overhead of digital signature schemes was proposed by Even et al. [9], where a signing process was split into two phases. The first phase is called offline phase, which is performed prior to obtaining the message to be signed. The second phase is called online phase, which is executed when the message becomes available. All the heavy computations in the signing phase are pre-computed in the offline phase. In the online phase, it only performs the light computations such as modular multiplication and hashing.

The first two identity-based online/offline encryption (IBOOE) schemes were proposed by Guo et al. [11] in 2008. In the offline phase, all the heavy computations are conducted without the requirements of the recipient’s identity and the message to be encrypted. When the recipient’s identity and the message become available, the online phase can be accomplished with great efficiency. However, the ciphertext size of both IBOOE schemes in [11] is large, so might not be desirable for lightweight devices.

The online/offline encryption schemes are usually formulated with the bilinear maps. Let ${\mathbb {G}}$ and ${\mathbb {G}}_T$ be two multiplicative groups with the same prime order p. A symmetric bilinear map is defined as $e:{\mathbb {G}} \times {\mathbb {G}} \rightarrow {\mathbb {G}}_T$. The first scheme in [11] needs one element in ${\mathbb {G}}_T$, four elements in ${\mathbb {G}}$, two elements in ${\mathbb {Z}}_p^*$ and two one-time signatures. The second scheme requires four elements in ${\mathbb {G}}_T$, two elements in ${\mathbb {G}}$ and two elements in ${\mathbb {Z}}_p^*$.

Subsequently, an IBOOE scheme, which is more efficient than Guo et al.’s [11], was proposed by Liu and Zhou [15]. They removed the elements in ${\mathbb {G}}_T$ from the final ciphertext and only needed three modular multiplications operations in the online phase. Later, Chow et al. [7] proposed the first identity-based online/offline key encapsulation (IBOOKEM). Based on their IBOOKEM, they proposed a secure IBOOE scheme in the random oracle model. Compared to [15], they saved two elements in ${\mathbb {G}}$ in the ciphertext. However, Selvi et al. [17, 18] showed that the schemes in [15] and [7] are not secure against the chosen ciphertext attack (CCA). A practical IBOOE scheme for wireless sensor network was proposed by Chu et al. [8], which removed the elements in ${\mathbb {G}}_T$ from the offline storage. However, the security, storage and computation of the proposed scheme are depended on a symmetric encryption scheme.

A provably CCA secure (in the random oracle model) and efficient IBOOE scheme was proposed by Selvi et al. [17, 18]. Their IBOOE scheme requires more than one element in group ${\mathbb {G}}$ in both online and offline phase. Recently, an efficient semi-generic transformation to achieve IBOOE from IBE was proposed by Lai et al. [12] in ACISP 2015. Due to the space limitation, they only proposed a key encapsulation scheme against the chosen plaintext attack.

In this paper, we propose an efficient identity-based online/offline encryption scheme. Our proposed IBOOE scheme achieves the shortest ciphertext, in comparison with other schemes in the literature. Compared to the best-known scheme in the literature, our scheme saves one element in ${\mathbb {G}}$ in both offline and online phases. We only require one element in ${\mathbb {G}}$ in both offline storage and ciphertext size in our scheme. In the offline phase, our scheme reduces one group operation in ${\mathbb {G}}$. Our proposed scheme is proven secure in the random oracle model.

The first identity-based online/offline signcryption (IBOOSC) scheme was proposed by Sun et al. [20] in 2008. They for the first time gave the definition of IBOOSC and its security model. Then, a generic construction of identity-based online/offline signcryption was given by Sun et al. [21]. However, Selvi et al. [18] pointed out that the schemes in [20] and [21] actually are not secure against the existential forgery attack.

To improve the security, Liu et al. [14] proposed a secure IBOOSC scheme. In [14], the final ciphertext still needs four elements in ${\mathbb {G}}$. To speed up the online computation, Selvi et al. [18] proposed a new secure IBOOSC scheme and reduced one multiplication operation in the online phase compared to [14]. But their scheme requires a larger offline storage and the ciphertext is bigger than [14]. Li et al. [13] proposed an efficient IBOOSC scheme based on [1] for low power devices. Their scheme requires three elements in ${\mathbb {G}}$ in both the offline storage and the final ciphertext.

Apart from our novel online/offline identity-based encryption scheme, in this paper, we also propose a novel and efficient identity-based online/offline signcryption scheme based on [1]. Our scheme achieves the shortest ciphertext, compared to the existing IBOOSC schemes. Compared to [13], our scheme saves one element in ${\mathbb {G}}$ in the final ciphertext and saves one element in ${\mathbb {G}}$ and one element in ${\mathbb {Z}}_p^*$ in the offline storage. In the offline phase, our signcryption scheme reduces one operation in ${\mathbb {G}}$. The online computation is comparable and only requires two modular operations.

Organization The remainder of the paper is organized as follows. In Sect. 2, we review some basic preliminaries including bilinear pairing, complexity assumptions, definitions and the corresponding security models. We describe our novel identity-based online/offline encryption scheme with the shortest ciphertext and show its security in Sect. 3. In Sect. 4, we propose an efficient identity-based online/offline signcryption scheme and give its security. In Sect. 5, we give the evaluation and comparison of our schemes and draw our conclusions in Sect. 6.

2 Preliminaries

2.1 Bilinear pairing

Let ${\mathbb {G}}$ and ${\mathbb {G}}_T$ be cyclic groups of the same prime order p. g is a generator of ${\mathbb {G}}$. A bilinear pairing is a map $e:{\mathbb {G}} \times {\mathbb {G}} \rightarrow {\mathbb {G}}_T$ with the following properties:

• 1. Bilinear: For all $u,v \in {\mathbb {G}}$ and $a,b \in {\mathbb {Z}}_p^*$, we have $e\left( {u^a,v^b} \right) = e\left( {u,v} \right) ^{ab}$.

• 2. Non-degeneracy: $e\left( {g,g} \right) \ne 1$.

• 3. Computability: It is efficient to compute $e\left( {u,v} \right)$ for all $u,v \in {\mathbb {G}}$.

2.2 Complexity assumptions

The computational assumptions for the security of our schemes are based on the following three assumptions. Let ${\mathbb {G}}$ and ${\mathbb {G}}_T$ be multiplicative cyclic groups of the same prime order p, g be a generator of ${\mathbb {G}}$ and e be a pairing map. We review the k-collision attack assumption 1 (k-CAA1) [5], the q-bilinear Diffie–Hellman inversion (q-BDHI) [2] assumption and the q-strong Diffie–Hellman (q-SDH) [3] assumption.

Definition 1

(k-CAA1) Given $\left( g,{g^a},{c_0},\left( {{c_1},{g^{\frac{1}{{{c_1} + a}}}}} \right) ,\right. \left. \ldots ,\left( {{c_k},{g^{\frac{1}{{{c_k} + a}}}}} \right) \right)$ where ${c_i}{ \in _R} {{\mathbb {Z}}}_p^*$ and distinct for $0 \le i \le k$, the k-CAA1 problem is to compute $e{\left( {g,g} \right) ^{\frac{1}{{{c_0} +a }}}}$.

Definition 2

(q-BDHI) Given $( q+1)$-tuple $\left( {h,{h^a},{h^{{a^2}}}, \ldots ,}\right. \left. {{h^{{a^q}}}} \right) \in {{\mathbb {G}}^{q + 1}}$ where $a{ \in _R}{{\mathbb {Z}}_p^*}$, the q -BDHI problem in (${\mathbb {G}},{\mathbb {G}}_T$) is to compute $e{\left( {h,h} \right) ^{\frac{1}{a}}}$.

Definition 3

(q-SDH) Given $( q+1)$-tuple $\left( h,{h^a},{h^{{a^2}}},\right. \left. \ldots ,{h^{{a^q}}} \right) \in {{\mathbb {G}}^{q + 1}}$ where $a{ \in _R}{{\mathbb {Z}}_p^*}$, the q -SDH problem in ${\mathbb {G}}$ is to find a pair $\left( {c,{h^{\frac{1}{a + c}}}} \right)$ with $c \in {\mathbb {Z}}_p^*$.

2.3 Definition of identity-based online/offline encryption

An identity-based online/offline encryption scheme consists of the following five algorithms:

Setup( k ): Taking as input a security parameter $k \in {\mathbb {Z}}^+$, it outputs the system parameters mpk and the master key msk, where the system parameters are publicly known, while the master key is kept secretly and known to generator (PKG) only.

KeyGen(mpk, msk, ${ ID}$): Taking as input the system parameters mpk, master key msk and an arbitrary ${ ID} \in {\left\{ {0,1} \right\} ^*}$, it outputs a private key $d_{{ ID}}$ for ${ ID}$.

Off-Encrypt(mpk): Taking as input the system parameters mpk, it outputs the offline ciphertext $C_{\mathrm{off}}$.

On-Encrypt(mpk, $C_{\mathrm{off}}$, ${ ID}$, m): Taking as input the system parameters mpk, offline ciphertext $C_{\mathrm{off}}$, an identity ${ ID} \in {\left\{ {0,1} \right\} ^*}$ and a message m, it outputs a ciphertext ${ CT}$.

Decrypt(mpk, ${ CT}$, ${d_{{ ID}}}$): Taking as input the system parameters mpk, ciphertext ${ CT}$ and the private key $d_{{ ID}}$, it outputs a plaintext message or a rejected symbol.

The security for IBOOE is the same as that for identity-based encryption. The strongest and commonly accepted notion of security for identity-based encryption system is that of indistinguishability against an adaptive chosen ciphertext attack. The game of IND-ID-CCA is defined under the following game between a challenger ${\mathcal {C}}$ and an adversary ${\mathcal {A}}$. Both take the security parameter $k \in {\mathbb {Z}}^+$ as input.

Setup: ${\mathcal {C}}$ takes as input a security parameter k and runs the Setup algorithm to obtain the system parameters mpk and the master key msk. It gives the adversary ${\mathcal {A}}$ the system parameters mpk.

Phase 1: ${\mathcal {A}}$ adaptively makes a polynomial number of following queries:

• Private key query $({ ID}_i)$. ${\mathcal {C}}$ responds by running key generation algorithm KeyGen to generate the private key ${d_{{ ID}_i}}$ and sending ${d_{{ ID}_i}}$ to ${\mathcal {A}}$.

• Decryption query $\left( {I{D_i},C{T_i}} \right)$. ${\mathcal {C}}$ responds by running key generation algorithm KeyGen to generate the private key $d_{ID_i}$, running the algorithm Decrypt to decrypt the ciphertext $\left( {{ ID}_i,{ CT}_i} \right)$ and sending the result back to ${\mathcal {A}}$.

Challenge: ${\mathcal {A}}$ outputs two messages $m_0, m_1$ and a challenged identity ${ ID}^*$ under one restriction that ${\mathcal {A}}$ did not request a private key for ${ ID}^*$ in Phase 1. ${\mathcal {C}}$ picks a random bit $b \in \left\{ {0,1} \right\}$, computes a challenge ciphertext ${{ CT}^*}$ on $m_b$ and then sends ${{ CT}^*}$ to ${\mathcal {A}}$.

Phase 2: ${\mathcal {A}}$ continues to issue private key queries on ${{{ ID}_i} \ne {{ ID}^*}}$ and decryption queries on $\left( {{ ID}_i,{ CT}_i} \right) \ne \left( {{ ID}^*,{ CT}^*} \right)$. ${\mathcal {C}}$ responds as in Phase 1.

Guess: Finally, ${\mathcal {A}}$ outputs its guess $b' \in \left\{ {0,1} \right\}$ for b and wins the game if $b'=b$.

We refer to such an adversary ${\mathcal {A}}$ as an IND-ID-CCA adversary. We define adversary ${\mathcal {A}}$’s advantage in attacking the game as

$$\begin{aligned} \mathsf {Adv}_{\mathcal {A}}\left( k \right) = \left| {\Pr [b = b'] - \frac{1}{2}} \right| . \end{aligned}$$

Definition 4

An identity-based online/offline encryption scheme is IND-ID-CCA secure if for any polynomial time IND-ID-CCA adversary the $\mathsf {Adv}_{{\mathcal {A}}}(k)$ is negligible.

2.4 Definition of identity-based online/offline signcryption

An signcryption scheme should provide confidentiality as well as authentication and non-repudiation. The formal structure of identity-based online/offline signcryption (IBOOS) scheme consists of five algorithms that are modeled as follows:

Setup( k ): The same as IBOOE.

KeyGen(mpk, msk, ID): The same as IBOOE.

Off-Signcrypt(mpk, ${ ID}_s$, $d_{{ ID}_s}$): Taking as input the system parameters mpk, sender’s identity ${ ID}_s$ and the sender’s private key $d_{{ ID}_s}$, it outputs offline ciphertext $\delta$.

On-Signcrypt(mpk, m, ${ ID}_s$, ${ ID}_r$, $\delta$): Taking as input a message m, a sender’s identity ${ ID}_s$, a receiver’s identity ${ ID}_r$ and the offline output $\delta$, it outputs the final signcryption $\sigma$.

Unsigncrypt(mpk, $\sigma$, ${ ID}_s$, ${ ID}_r$, $d_{ID_r}$): Taking as input a signcryption $\sigma$, a sender’s identity ${ ID}_s$, a receiver’s identity ${ ID}_r$ and the receiver’s private key $d_{{ ID}_r}$, it outputs the plaintext message or a rejected symbol.

Signcryption achieves both encryption and digital signature. We first give the security for message confidentiality. The notion of IND-ID-CCA for IBOOSC is similar to that for IBOOE and is defined under the following game between a challenger ${\mathcal {C}}$ and an adversary ${\mathcal {A}}$.

Setup: ${\mathcal {C}}$ takes as input a security parameter k and runs the Setup algorithm to obtain the system parameters mpk and the master key msk. It gives the adversary ${\mathcal {A}}$ the system parameters mpk.

Phase 1: ${\mathcal {A}}$ adaptively makes a polynomial number of following queries:

• Private key query $({ ID}_i)$. ${\mathcal {C}}$ responds by running key generation algorithm KeyGen to generate the private key ${d_{{ ID}_i}}$ and sending ${d_{{ ID}_i}}$ to ${\mathcal {A}}$.

• Signcryption query $\left( {{ ID}_s, { ID}_r, m} \right)$. ${\mathcal {C}}$ responds by running key generation algorithm KeyGen to generate the sender’s private key ${d_{{ ID}_s}}$, running the algorithm Off-Signcrypt to obtain $\delta$ and sending $\sigma$ by running On-Signcrypt to ${\mathcal {A}}$.

• Unsigncryption query $\left( {\sigma , { ID}_s, { ID}_r} \right)$. ${\mathcal {C}}$ runs KeyGen to generate the receiver’s private key $d_{{ ID}_r}$ and sends the result of Unsigncrypt to ${\mathcal {A}}$.

Challenge: ${\mathcal {A}}$ outputs two messages $m_0, m_1$ and challenged identities $\left( {{ ID}_s^*, { ID}_r^*} \right)$ under one restriction that ${\mathcal {A}}$ did not issue a private key query for ${ ID}_r^*$ in Phase 1. ${\mathcal {C}}$ picks a random bit $b \in \left\{ {0,1} \right\}$ and computes a challenge ciphertext ${\sigma ^*}$ on $m_b$, then sends ${\sigma ^*}$ to ${\mathcal {A}}$.

Phase 2: ${\mathcal {A}}$ issues more private key queries on ${ ID}_i\ne { ID}_r^*$ and unsigncryption queries on $\sigma _i\ne \sigma ^*$. ${\mathcal {C}}$ responds as in Phase 1.

Guess: Finally, ${\mathcal {A}}$ outputs its guess $b' \in \left\{ {0,1} \right\}$ for b and wins the game if $b'=b$.

We refer to such an adversary ${\mathcal {A}}$ as an IND-ID-CCA adversary. We define adversary ${\mathcal {A}}$’s advantage in attacking the game as

$$\begin{aligned} \mathsf {Adv}_{{\mathcal {A}}}\left( k \right) = \left| {\Pr [b = b'] - \frac{1}{2}} \right| . \end{aligned}$$

Definition 5

An identity-based online/offline signcryption scheme is IND-ID-CCA secure if for any polynomial time IND-ID-CCA adversary the $\mathsf {Adv}_{{\mathcal {A}}}\left( k \right)$ is negligible.

The next game defines the security for non-repudiation with regard to signatures embedded in ciphertexts. The commonly accepted notion of security for signature system is existentially unforgeable against adaptive chosen message attacks (EUF-CMA). This notion is defined by the following game between a challenger ${\mathcal {C}}$ and an adversary ${\mathcal {A}}$.

Setup: ${\mathcal {C}}$ takes as input a security parameter k and runs the Setup algorithm to obtain the system parameters mpk and the master key msk. It gives the adversary ${\mathcal {A}}$ the system parameters mpk.

Private key query $({ ID}_i)$. ${\mathcal {C}}$ responds as in the IND-ID-CCA game for IBOOSC.

Signcryption query $\left( {{ ID}_s, { ID}_r, m} \right)$. ${\mathcal {C}}$ responds as in the IND-ID-CCA game for IBOOSC.

Unsigncryption query $\left( {\sigma , { ID}_s, { ID}_r} \right)$. ${\mathcal {C}}$ responds as in the IND-ID-CCA game for IBOOSC.

Forge: Finally, ${\mathcal {A}}$ outputs a triple $\left( {{\sigma ^*}, { ID}_s^*, { ID}_r^*} \right)$ where the private key of ${ ID}_r^*$ has not been queried. ${\mathcal {A}}$ wins the game if $\sigma ^*$ is a valid ciphertext corresponding to the ${\left( {{ ID}_s^*, { ID}_r^*} \right) }$ and passes the verification. The adversary’s advantage is its probability to win the game.

Definition 6

An identity-based online/offline signcryption scheme is EUF-CMA secure if there is no probability polynomial time adversary ${\mathcal {A}}$ who can win this game with a non-negligible advantage.

3 Identity-based online/offline encryption

In this section, we give our efficient identity-based online/offline encryption scheme and the corresponding security analysis.

3.1 Construction

Let ${{\mathbb {G}}}$ and ${{\mathbb {G}}_T}$ be two cyclic groups of the same prime order p, and g is the generator of ${{\mathbb {G}}}$. Let $e:{{\mathbb {G}}} \times {{\mathbb {G}}} \rightarrow {{\mathbb {G}}_T}$ be the bilinear pairing and n be the length of the message. The scheme is described by the following five algorithms.

Setup: The system parameters are generated as follows. The PKG randomly chooses $\alpha \in {{\mathbb {Z}}_p^*}$, computes $v = e\left( {g,g} \right)$ and sets $g_1 =g^\alpha$. Let ${H_1}:\left\{ {0,1} \right\} ^* \rightarrow {{\mathbb {Z}}_p^*}$, ${H_2}:{{\mathbb {G}}_T} \rightarrow {\left\{ {0,1} \right\} ^n}$, ${H_3}:{{\mathbb {G}}_T} \times {\left\{ {0,1} \right\} ^n} \times {\mathbb {Z}}_p^* \times {{\mathbb {G}}} \rightarrow {{\mathbb {Z}}_p^*}$ be the cryptographic hash functions. The public parameters mpk and the master key msk are

$$\begin{aligned} {mpk = \left( {{{\mathbb {G}}},{{\mathbb {G}}_T}, p, g, g_1, v, n, e, {H_1}, {H_2}, {H_3}} \right) }, \quad \textit{msk} = \alpha . \end{aligned}$$

KeyGen: A user’s private key generation algorithm proceeds as follow. For an identity ${ ID} \in {\left\{ {0,1} \right\} ^*}$, the PKG computes

$$\begin{aligned} {d_{ID}} = {g^{\frac{1}{{\alpha + {H_1}\left( {ID} \right) }}}}. \end{aligned}$$

Off-Encrypt: The offline storage is computed as follows. The PKG randomly chooses $s,w \in {\mathbb {Z}}_p^*$ and computes

$$\begin{aligned} R = v^s,\quad {C_1} = {\left( {{g_1}{g^w}} \right) ^s},\quad h = {H_2}\left( R \right) . \end{aligned}$$

The offline storage is $C_{off} = \left( {{C_1}, R, s, w, h } \right)$.

On-Encrypt: To encrypt a message $m \in {\left\{ {0,1} \right\} ^n}$ for $ID \in {\left\{ {0,1} \right\} ^*}$, the sender computes

$$\begin{aligned} {C_2}= & {} s\left( {{H_1}\left( {ID} \right) - w} \right) \hbox { mod }p,\\ {C_3}= & {} h \oplus m,\\ {C_4}= & {} \left( {s + {H_3}\left( {R, m, {C_1}, {C_2}} \right) } \right) \,\hbox { mod }\,p. \end{aligned}$$

Then output the final ciphertext ${ CT} = \left( {{C_1}, {C_2}, {C_3}, {C_4}} \right)$.

Decrypt: Given a ciphertext ${ CT} = \left( {{C_1}, {C_2}, {C_3}, {C_4}} \right)$, the recipient decrypts the ciphertext by using its private key ${d_{ID}}$ to compute

$$\begin{aligned} R'= & {} e\left( {{d_{ID}},{C_1}{g^{{C_2}}}} \right) ,\\ m'= & {} {C_3} \oplus {H_2}\left( R' \right) ,\\ s'= & {} \left( {{C_4} - {H_3}\left( {R', m', {C_1}, {C_2}} \right) } \right) \,\hbox { mod }\,p,\\ w'= & {} \,\left( {{H_1}\left( {{ ID}} \right) - {C_2}s{'^{ - 1}}} \right) \hbox { mod }\,p. \end{aligned}$$

Then check whether

$$\begin{aligned} {C_1}\mathop {=}\limits ^{?} {\left( {{g_1}{g^{w'}}} \right) ^{s'}}. \end{aligned}$$

If it holds, the recipient outputs $m'$ as the result of decryption, and otherwise rejects it.

Correctness: For a valid ciphertext, we have

$$\begin{aligned} \begin{array}{ll} R'&{}=e\left( {d{}_{ID}, {C_1}{g^{{C_2}}}} \right) \\ &{}= e\left( {{g^{\frac{1}{{\alpha + {H_1}\left( {ID} \right) }}}}, {{\left( {{g_1}{g^w}} \right) }^s}{g^{s\left( {{H_1}\left( {ID} \right) - w} \right) }}} \right) \\ &{}=e\left( {{g^{\frac{1}{{\alpha + {H_1}\left( {ID} \right) }}}}, g_1^s{g^{s{H_1}\left( {ID} \right) }}} \right) \\ &{}=e{\left( {g, g} \right) ^s} \\ &{}=R. \end{array} \end{aligned}$$

The receiver gets the correct R by using its private key. Since it is a valid ciphertext, after getting correct R, receiver can compute the correct m, s and w, and then passes the checking equation. Thus, receiver can get the valid message.

3.2 Security

We now give the formal proof for the security of our scheme. We have the following result states that our scheme is IND-ID-CCA secure under the k-CAA1 assumption.

Theorem 1

Suppose the hash functions $H_1$, $H_2$ and $H_3$ are random oracles. Then our proposed scheme is indistinguishability against chosen ciphertext attacks (IND-ID-CCA) under k-CAA1 assumption. Specifically, suppose there is an IND-ID-CCA adversary ${\mathcal {A}}$ that has advantage $\epsilon$ against our proposed scheme. ${\mathcal {A}}$ makes at most ${q_E}$ private key queries and at most ${q_{H_1}}$, ${q_{H_2}}$, ${q_{H_3}}$ queries to the hash functions $H_1$, $H_2$, $H_3$, respectively. Then there is an algorithm ${\mathcal {S}}$ to solve the k-CAA1 problem with advantage $\epsilon '$, where

$$\begin{aligned} \epsilon ' \ge \frac{\epsilon }{{{q_{{H_1}}}\left( {{q_{{H_2}}} + {q_{{H_3}}}} \right) }}. \end{aligned}$$

Proof

Suppose ${\mathcal {A}}$ has advantage $\epsilon$ in attacking our scheme. We build a simulator ${\mathcal {S}}$ that solves k-CAA1 problem with advantage $\epsilon '$ by running ${\mathcal {A}}$. Let $\Bigg ( g, g^a, c_0, \left( {{c_1},{g^{\frac{1}{{{c_1} + a}}}}} \right) , \ldots ,\left( {{c_k}, {g^{\frac{1}{{{c_k} + a}}}}} \right) \Bigg )$ be a random instance of k-CAA1 problem taken as input by ${\mathcal {S}}$ and its goal is to compute $e{\left( {g,g} \right) ^{\frac{1}{{a + {c_0}}}}}$. In order to use ${\mathcal {A}}$ to solve the problem, ${\mathcal {S}}$ needs to simulate a challenger and responses all the queries for ${\mathcal {A}}$. Without loss of generality, we assume that $k = {q_{{H_1}}-1}$. Simulator ${\mathcal {S}}$ works by interacting with ${\mathcal {A}}$ in an IND-ID-CCA game as follows:

Setup: ${\mathcal {S}}$ sets $g_1 = g^a$ and randomly chooses an index $I \in \left\{ {1,2, \ldots ,{q_{{H_1}}}} \right\}$ and then sends the system parameters $\left( {{\mathbb {G}}, {\mathbb {G}}_T, p, g, g_1, {H_1}, {H_2}, {H_3}} \right)$ to ${\mathcal {A}}$.

$H_1$ queries: At any time adversary ${\mathcal {A}}$ may issue queries to the random oracle $H_1$ on ${ ID}_i$. ${\mathcal {S}}$ maintains a list $L_1$ of tuples $\left( {{ ID}_i, {c_i}} \right)$. This list is initially empty. If ${ ID}_i$ is already on the list $L_1$, ${\mathcal {S}}$ responds with ${H_1}\left( {{ ID}_i} \right) = {c_i}$. Otherwise, ${\mathcal {S}}$ checks the ${ ID}_i$. If ${ ID}_i={ ID}_I$, ${\mathcal {S}}$ sets ${H_1}\left( {{ ID}_I} \right) = {c_0}$, returns $c_0$ and then adds the new tuple $\left( {{ ID}_I, c_0} \right)$ into $L_1$. If ${ ID}_i \ne { ID}_I$, ${\mathcal {S}}$ randomly chooses $c_i$ from the instance of k-CAA1 which has not been chosen by ${\mathcal {S}}$ before and sets ${H_1}\left( {{ ID}_i} \right) = {c_i}$. Then ${\mathcal {S}}$ adds the new tuple $\left( {{ ID}_i, c_i} \right)$ into $L_1$ and returns $c_i$.

$H_2$ queries: At any time, adversary ${\mathcal {A}}$ may issue queries to the random oracle $H_2$ on $R_i$. ${\mathcal {S}}$ maintains a list $L_2$ of tuples $\left( {R_i,\beta _i} \right)$. This list is initially empty. If tuple $\left( {R_i, \beta _i} \right)$ is in the list $L_2$, ${\mathcal {S}}$ responds with ${H_2}\left( {{R_i}} \right) = {\beta _i}$. Otherwise, ${\mathcal {S}}$ picks a random string ${\beta _i} \in {\left\{ {0,1} \right\} ^n}$ where ${\beta _i}$ has not been used before and sets ${H_2}\left( {{R_i}} \right) = {\beta _i}$. Then ${\mathcal {S}}$ returns $\beta _i$ and adds the new tuple $\left( {R_i, \beta _i} \right)$ into $L_2$.

$H_3$ queries: At any time, adversary ${\mathcal {A}}$ may issue queries to the random oracle $H_3$ on $\left( {R_i, m_i, {C_1^i}, {C_2^i}} \right)$. ${\mathcal {S}}$ maintains a list $L_3$ of tuples $\left( {R_i, m_i, C_1^i, C_2^i, \gamma _i} \right)$. This list is initially empty. If $\left( {R_i, m_i, {C_1^i}, {C_2^i}} \right)$ is on the list, ${\mathcal {S}}$ responds with $\gamma _i$. Otherwise, ${\mathcal {S}}$ randomly chooses ${\gamma }_i \in {\mathbb {Z}}_p^*$ which does not exist in ${L_3}$. Then ${\mathcal {S}}$ sets ${H_3}\left( {R_i, m_i, {C_1^i}, {C_2^i}} \right) = \gamma _i$, responds to ${\mathcal {A}}$ with ${\gamma }_i$, and adds the new tuple $\left( {R_i, m_i, {C_1^i}, {C_2^i}, \gamma _i } \right)$ to the list $L_3$.

Phase 1: At any time, adversary ${\mathcal {A}}$ may issue the following queries:

• Private key queries. Let ${ ID}_i$ be a private key query issued by adversary ${\mathcal {A}}$. ${\mathcal {S}}$ responds to this query as follows. If ${ ID}_i={ ID}_I$, ${\mathcal {S}}$ aborts. Otherwise, ${\mathcal {S}}$ looks up the list $L_1$ to get the corresponding $\left( {{ ID}_i, c_i} \right)$. If $\left( {{ ID}_i, c_i} \right)$ is not in the list ${L_1}$, ${\mathcal {S}}$ runs the $H_1$ queries and gets the corresponding $c_i$ and adds the tuple $\left( {{ ID}_i, c_i} \right)$ into $L_1$. Then ${\mathcal {S}}$ sets ${d_{ID_i}} = {g^{\frac{1}{{\alpha + c_i}}}}$ and returns ${d_{ID_i}}$.

• Decryption queries. Consider a decryption query for a ciphertext $\left( {{ ID}_i, { CT}_i} \right)$ where ${ CT}_i = \left( {C_1^i, C_2^i, C_3^i, C_4^i} \right)$. Simulator ${\mathcal {S}}$ first examines the ${ ID}_i$. If ${ ID}_i \ne I{D_I}$; since ${\mathcal {S}}$ knows the private key of ${ ID}_i$, he can run the decryption algorithm to decrypt the ciphertext correctly by using ${d_{ID_i}}$. If $I{D_i} = { ID}_I$, ${\mathcal {S}}$ decrypts the ciphertext as follows:

  • 1. Search the tuple $\left( {R_i, m_i, C_1^i, C_2^i, \gamma _i} \right)$ from the list $L_3$ such that ${H_2}\left( {{R_i}} \right) \oplus {m_i} = C_3^i$. If no match, output “invalid.”

  • 2. Otherwise, compute ${s_i} = \left( {C_4^i - {\gamma _i}} \right) \hbox { mod }p$ and check whether

    $$\begin{aligned} C_1^i{g^{C_2^i}}\mathop = \limits ^? {\left( {{g_1}{g^{{H_1}\left( {{ ID}_i} \right) }}} \right) ^{{s_i}}}. \end{aligned}$$

    If it does not hold, go back to step 1 and test next tuple in $L_3$.

  • 3. Otherwise, compute ${w_i} = \left( {{H_1}\left( {{ ID}_i} \right) - C_2^i{s_i}^{ - 1}} \right) \hbox { mod }q$ and check whether

    $$\begin{aligned} C_1^i\mathop = \limits ^? {\left( {{g_1}{g^{{w_i}}}} \right) ^{{s_i}}}. \end{aligned}$$

    If it holds, output $m_i$ as the decryption result and return $m_i$ to ${\mathcal {A}}$, otherwise go back to step 1.

Challenge: Once adversary ${\mathcal {A}}$ decides Phase 1 is over, it outputs two messages ${m_0},{m_1} \in {\left\{ {0,1} \right\} ^n}$ and a challenged identity $ID^*$ under one restriction that ${ ID}^*$ has not been queried in the private key queries phase. If ${ ID}^* \ne { ID}_I$, ${\mathcal {S}}$ aborts. Otherwise, ${\mathcal {S}}$ picks a random bit $b \in \left\{ {0,1} \right\}$ and computes the challenge ciphertext as follows:

• 1. Randomly choose $\lambda \in {\mathbb {Z}}_p^*, ~C_2^*\in {\mathbb {Z}}_p^*, ~C_3^* \in {\left\{ {0,1} \right\} ^n}, ~C_4^* \in {\mathbb {Z}}_p^*$.

• 2. Compute $C_1^* = {g^{\lambda - C_2^*}}$ and set ${{ CT}^*} = \left( {C_1^*, C_2^*, C_3^*, C_4^*} \right)$.

Phase 2: ${\mathcal {A}}$ continues issuing more private key queries on ${{ ID}_i \ne { ID}^*}$ and decryption queries on $\left( {{ ID}_i, { CT}_i} \right) \ne \left( {{ ID}^*, { CT}^*} \right)$. ${\mathcal {S}}$ responds as in Phase 1.

Guess: Finally, ${\mathcal {A}}$ outputs its guess $b' \in \left\{ {0,1} \right\}$ for b.

From the ${\mathcal {A}}$’s point of view, if it knows that ${{ CT}^*}$ is a bad challenge ciphertext (invalid), it must have queried the $H_2$ or $H_3$ oracle with $R^*$ as input. This means that $R^*$ is one of input of $H_2$ or $H_3$ oracle and in the list $L_2$ or $L_3$. Otherwise, according to the assumption, ${\mathcal {A}}$ will with $\epsilon$ advantage output the correct $b'$. This also means that A has queried the value of $H_2$ or $H_3$ taken $R^*$ as input. From the decryption algorithm, we have

$$\begin{aligned} {R^*}= & {} e\left( {{d_{ID^*}}, C_1^*{g^{C_2^*}}} \right) = e\left( {{g^{\frac{1}{{\alpha + {H_1}\left( {ID^*} \right) }}}}, {g^{\lambda - C_2^*}}{g^{C_2^*}}} \right) \\= & {} e{\left( {g, g} \right) ^{\frac{\lambda }{{\alpha + {c_0}}}}}. \end{aligned}$$

${\mathcal {S}}$ ignores the guess of ${\mathcal {A}}$ and randomly picks a R from the list $L_2$ or $L_3$ and computes ${R^{{\lambda ^{ - 1}}}}$ as the solution to the given instance of k-CAA1 problem.

The above completes the description of simulation algorithm ${\mathcal {S}}$. To complete the security proof, it remains to show that ${\mathcal {S}}$ correctly outputs $e{\left( {g, g} \right) ^{\frac{1 }{{{c_0} + a}}}}$ with probability at least $\epsilon '$. We first analyze the probability that ${\mathcal {S}}$ does not abort during the simulation. We consider two events below:

• 1. $A_1:$ ${\mathcal {A}}$ did not query the private key on $ID^*$ in private key query phase.

• 2. $A_2:$ The challenged identity $ID^*$ is equal to ${ ID}_I$.

We have

$$\begin{aligned}&\Pr \left[ {A_1} \right] =1- \frac{{{q_E}}}{{{q_{{H_1}}}}},\\&\Pr \left[ {A_2} \right] = \frac{1}{{{q_{{H_1}}} - {q_E}}},\\&\begin{array}{ll} \Pr \left[ {{}^\lnot { abort}} \right] &{}=\Pr \left[ {{A_1} \wedge {A_2}} \right] \\ &{}= \Pr \left[ {{A_2}} \right] \Pr \left[ {{A_1}|{A_2}} \right] \\ &{}= \left( {\frac{1}{{{q_{{H_1}}} - {q_E}}}} \right) \left( {1 - \frac{{{q_E}}}{{{q_{{H_1}}}}}} \right) \\ &{}= \frac{1}{{{q_{{H_1}}}}}, \end{array} \end{aligned}$$

The probability of R randomly chosen from the list $L_2$ or $L_3$ to be the solution of k-CAA1 is at least $\frac{1}{{{q_{{H_2}}} + {q_{{H_3}}}}}$. It follows that ${\mathcal {S}}$ computes a correct answer for k-CAA1 problem by the above simulation with advantage

$$\begin{aligned} \epsilon ' \ge \frac{\epsilon }{{{q_{{H_1}}}\left( {{q_{{H_2}}} + {q_{{H_3}}}} \right) }}. \end{aligned}$$

This completes the proof.

4 Identity-based online/offline signcryption

In this section, we propose an efficient IBOOSC scheme based on Barreto et al.’s [1] identity-based signcryption scheme and give the security analysis.

4.1 Construction

Let ${\mathbb {G}}$ and ${\mathbb {G}}_T$ be two cyclic groups of the same prime order p, and g is the generator of ${\mathbb {G}}$. Let $e:{\mathbb {G}} \times {\mathbb {G}} \rightarrow {\mathbb {G}}_T$ be the bilinear pairing and n be the length of the message.

Setup: The system parameters are generated as follows. Given a system security parameter k, the PKG randomly chooses $\alpha \in {\mathbb {Z}}_p^*$, computes $v = e{\left( {g, g} \right) }$ and sets $g_1 =g^\alpha$. Let $H_1:\left\{ {0,1} \right\} ^* \rightarrow {\mathbb {Z}}_p^*$, $H_2:{\left\{ {0, 1} \right\} ^n} \times {\mathbb {G}}_T \times {\mathbb {G}} \times {\mathbb {G}} \rightarrow {\mathbb {Z}}_p^*$, $H_3:{\mathbb {G}}_T \rightarrow {\left\{ {0,1} \right\} ^n}$ be the cryptographic hash functions. The public parameters mpk and the master key msk are given by

$$\begin{aligned} {mpk = \left( {{\mathbb {G}}, {\mathbb {G}}_T, p, g, g_1, v, n, e, H_1, H_2, H_3} \right) }, \qquad \textit{msk} = \alpha . \end{aligned}$$

KeyGen: A user’s private key generation algorithm proceeds as follow. For identity ${ ID} \in \{0, 1\}^*$, the PKG computes

$$\begin{aligned} d_{ID} = {g^{\frac{1}{{\alpha + H_1\left( {{ ID}} \right) }}}}. \end{aligned}$$

Off-Signcrypt: The offline storage is computed as follows. The sender with identity ${ ID}_s$ randomly chooses $s, w, \beta \in {\mathbb {Z}}_p^*$ and computes

$$\begin{aligned} R = v^s, \quad C_1 = d_{ID_s}^\beta , \quad C_2 = {\left( {{g_1}{g^w }} \right) ^s}. \end{aligned}$$

The offline storage is $\delta = (s, \beta , w, R, C_1, C_2)$.

On-Signcrypt: To encrypt and sign a message $m \in \{0,1\}^n$ for a receiver with identity ${ ID}_r \in \{0,1\}^*$, the sender computes

$$\begin{aligned} C_3= & {} m \oplus H_3(R), \\ h= & {} H_2( m, R, C_1, C_2 ), \\ C_4= & {} {\beta ^{ - 1}}( s + h )\mod p, \\ C_5= & {} s\left( {{H_1}\left( { ID}_r \right) - w } \right) \mod p. \end{aligned}$$

Then output the final ciphertext $\sigma = ( C_1, C_2, C_3, C_4, C_5 )$.

Unsigncrypt: For a ciphertext $\sigma = (C_1, C_2, C_3, C_4, C_5)$, the recipient decrypts the ciphertext by using its private key $d_{ID_r}$ to compute

$$\begin{aligned} T= & {} C_2{g^{C_5}},\\ S= & {} C_1^{C_4},\\ R= & {} e(T, d_{ID_r}),\\ m= & {} C_3 \oplus H_3(R),\\ h= & {} H_2( m,R,C_1,C_2 ). \end{aligned}$$

Then check whether

$$\begin{aligned} R = e\left( {S, {g_1}{g^{{H_1}({ ID}_s)}}} \right) {v^{ - h}}. \end{aligned}$$

If it holds, output m as the result of decryption, and believe ${ ID}_s$ has signed on m. Otherwise, reject it.

Correctness: For a valid ciphertext, we have

$$\begin{aligned}&T = C_2g^{C_5} = {\left( {{g_1}{g^w}} \right) ^s}{g^{s\left( {{H_1}\left( {{ ID}_r} \right) - w} \right) }} = {\left( {{g_1}{g^{{H_1}\left( {{ ID}_r} \right) }}} \right) ^s},\\&S = C_1^{C_4} = {\left( {d_{ID_s}^\beta } \right) ^{{\beta ^{ - 1}}\left( {s + h} \right) }} = d_{ID_s}^{s + h},\\&\begin{array}{ll} e\left( {T,{d_{ID_r}}} \right) &{}= e\left( {{{\left( {{g_1}{g^{{H_1}\left( {{ ID}_r} \right) }}} \right) }^s},{g^{\frac{1}{{\alpha + {H_1}\left( {{ ID}_r} \right) }}}}} \right) \\ &{}= e\left( {{\left( {{g^{\alpha + {H_1}\left( {{ ID}_r} \right) }}} \right) ^s},{g^{\frac{1}{{\alpha + {H_1}\left( {{ ID}_r} \right) }}}}} \right) \\ &{}= e{\left( {g,g} \right) ^s}\\ &{}=R. \end{array} \end{aligned}$$

Receiver gets the correct R by using its private key. After obtaining the correct R, receiver can compute the correct m and h and pass the checking equation.

$$\begin{aligned} \begin{array}{ll} e\left( {S,{g_1}{g^{{H_1}\left( {{ ID}_s} \right) }}} \right) {v^{ - h}} &{}= e\left( {d_{ID_s}^{\left( {s + h} \right) },{g^{\alpha + {H_1}\left( {{ ID}_s} \right) }}} \right) e{\left( {g,g} \right) ^{ - h}} \\ &{}= e\left( {{g^{\frac{{s + h}}{{\alpha + {H_1}\left( {{ ID}_s} \right) }}}},{g^{\alpha + {H_1}\left( {{ ID}_s} \right) }}} \right) e{\left( {g,g} \right) ^{ - h}} \\ &{}= e{\left( {g,g} \right) ^{s + h}}e{\left( {g,g} \right) ^{ - h}}\\ &{}= e{\left( {g,g} \right) ^s}\\ &{}=R. \end{array} \end{aligned}$$

4.2 Security

We now give the formal proof for the security of our signcryption scheme. The security follows immediately from the following two theorems. The first theorem states that our scheme is IND-ID-CCA secure under the q-BDHI assumption for the message confidentiality. The second theorem ensures that our scheme is EUF-CMA secure under q-SDH assumption.

Theorem 2

Suppose that an IND-ID-CCA adversary ${\mathcal {A}}$ has an advantage $\epsilon$ against our scheme, when asking $q_{H_i}$ queries to random oracles ${H_i}\left( {i = 1,2,3} \right)$, $q_{sc}$ signcryption queries and $q_{us}$ queries to the unsigncryption queries. Then there is an algorithm ${\mathcal {S}}$ to solve the q-BDHI problem for $q=q_{H_1}$ with advantage

$$\begin{aligned} \epsilon ' \ge \frac{\epsilon }{{{q_{{H_1}}}\left( {2{q_{{H_2}}} + {q_{{H_3}}}} \right) }}\left( {1 - \frac{{{q_{sc}}\left( {{q_{sc}} + {q_{{H_2}}}} \right) }}{{{2^k}}}} \right) \left( {1 - \frac{{{q_{us}}}}{{{2^k}}}} \right) . \end{aligned}$$

Proof

Suppose the adversary ${\mathcal {A}}$ has advantage $\epsilon$ in attacking our scheme. We build a simulator ${\mathcal {S}}$ that solves q-BDHI problem with advantage $\epsilon '$ by running ${\mathcal {A}}$. Let $\left( {h, h^a, h^{a^2}, \ldots , h^{a ^q}} \right)$ be a random instance of q-BDHI problem taken as input by ${\mathcal {S}}$. Its goal is to compute $e(h, h)^{\frac{1}{a }}$. In order to use ${\mathcal {A}}$ to solve the problem, ${\mathcal {S}}$ needs to simulate a challenger and response all the queries for ${\mathcal {A}}$. Simulator ${\mathcal {S}}$ works by interacting with ${\mathcal {A}}$ in an IND-ID-CCA game as follows:

Setup: ${\mathcal {S}}$ randomly picks $l \in \{ 1,2, \ldots ,q_{H_1}\}$, $I_l \in {\mathbb {Z}}_p^*$ and $w_1, w_2, \ldots , w_{l - 1},$ $w_{l + 1}, \ldots , w_q \in {\mathbb {Z}}_p^*$. For $i = 1, 2, \ldots , l - 1, l + 1, \ldots , q$, it computes $I_i=I_l-w_i$. ${\mathcal {S}}$ expands the polynomial

$$\begin{aligned} f\left( z \right) = \prod \limits _{i = 1,i \ne l}^q {\left( {z + {w_i}} \right) } = \sum \limits _{j = 0}^{q - 1} {{c_j}{z^j}}, \end{aligned}$$

and sets $g = {h^{\sum \limits _{j = 0}^{q - 1} {{c_j}{a^j}} }} = {h^{f\left( a \right) }}$, $X = {h^{\sum \limits _{j = 1}^q {{c_{j - 1}}{a^j}} }} = {h^{af\left( a \right) }} = {g^a}$. For $i \in \left\{ {1, \ldots ,q} \right\} \backslash \left\{ l \right\}$, ${\mathcal {S}}$ expands

$$\begin{aligned} {f_i}\left( z \right) = \frac{{f\left( z \right) }}{{z + {w_i}}} = \sum \limits _{j = 0}^{q - 2} {{d_j}{z^j}}, \end{aligned}$$

and computes

$$\begin{aligned} {V_i} = {h^{\sum \limits _{j = 0}^{q - 2} {{d_j}{a^j}} }} = {h^{{f_i}\left( a \right) }} = {h^{\frac{{f\left( a \right) }}{{a + {w_i}}}}} = {g^{\frac{1}{{a + {w_i}}}}}. \end{aligned}$$

Thus, g is a generator of ${\mathbb {G}}$ and ${\mathcal {S}}$ knows $q-1$ pairs $\left( {w_i, V_i=g^{\frac{1}{a + {w_i}}}} \right)$. ${\mathcal {S}}$ sets ${g_1} = X^{-1}{g^{ - {I_l}}} = {g^{ - a - {I_l}}}$ and computes $v = e( g, g)$. The system public key is

$$\begin{aligned} {{ mpk} = ( G, G_T, p, g, g_1, v, n, e, H_1, H_2, H_3)}. \end{aligned}$$

${\mathcal {S}}$ implicitly sets the master key $msk=\alpha = -a-I_l$. For all $i \in \left\{ {1, \ldots ,q} \right\} \backslash \left\{ l \right\}$, we have $\left( {I_i, V_i^{-1}} \right) = \left( {I_i, {g^{\frac{1}{{\alpha + {I_i}}}}}} \right)$.

$H_1$ queries: At any time, ${\mathcal {A}}$ may issue queries to the random oracle $H_1$ on ${ ID}_i$. ${\mathcal {S}}$ maintains a list $L_1$ of tuples $({ ID}_i, I_i)$. This list is initially empty. If ${ ID}_i$ is already on the list ${L_1}$, ${\mathcal {S}}$ responds with ${H_1}\left( {{ ID}_i} \right) = {I_i}$. Otherwise, ${\mathcal {S}}$ sets ${H_1}\left( {{ ID}_i} \right) = {I_i}$, adds the new tuple $\left( { ID}_i,I_i \right)$ to the ${L_1}$ list and returns $I_i$.

$H_2$ queries: At any time, adversary ${\mathcal {A}}$ may issue queries to the random oracle $H_2$ on $\left( {m_i,R_i,C_{1,i},C_{2,i}} \right)$. ${\mathcal {S}}$ maintains a list ${L_2}$ of tuples$( m_i,R_i,C_{1,i},C_{2,i},h_{2,i},$ $C_{3,i},{\lambda _i})$. This list is initially empty. If the tuple $\left( {m_i,R_i,C_{1,i},C_{2,i}} \right)$ already appears on the list ${L_2}$, ${\mathcal {S}}$ responds with ${H_2}\left( {{m_i},{R_i},{C_{1,i}},{C_{2,i}}} \right) = {h_{2,i}}$.

Otherwise, ${\mathcal {S}}$ picks a random $h_{2,i} \in {\mathbb {Z}}_p^*$, sets ${H_2}\left( {{m_i},{R_i},{C_{1,i}},{C_{2,i}}} \right) = {h_{2,i}}$ and returns $h_{2,i}$ to ${\mathcal {A}}$. To anticipate possible subsequent Unsigncrypt requests, ${\mathcal {S}}$ additionally simulates random oracle $H_3$ on its own to obtain ${h_{3,i}} = {H_3}\left( {{R_i}} \right) \in {\left\{ {0,1} \right\} ^n}$, computes ${C_{3,i}} = {m_i} \oplus {h_{3,i}}$, ${\lambda _i} = {R_i} \cdot v^{{h_{2,i}}}$ and then adds the new tuple $\left( {m_i,R_i,C_{1,i},C_{2,i},h_{2,i},C_{3,i},{\lambda _i}} \right)$ to the list ${L_2}$.

$H_3$ queries: At any time, adversary ${\mathcal {A}}$ may issue queries to the random oracle $H_3$ on $R_i$. ${\mathcal {S}}$ maintains a list ${L_3}$ of tuples $\left( {{R_i},h_{3,i}} \right)$. This list is initially empty. If $R_i$ appears on the list, ${\mathcal {S}}$ responds with ${H_3}\left( {{R_i}} \right) = {h_{3,i}}$. Otherwise, ${\mathcal {S}}$ randomly chooses ${h_{3,i}} \in {\left\{ {0,1} \right\} ^n}$, sets ${H_3}\left( {{R_i}} \right) = {h_{3,i}}$, responds to ${\mathcal {A}}$ with ${h_{3,i}}$ and then adds the new tuple $\left( {{R_i},h_{3,i}} \right)$ to the list ${L_3}$.

Phase 1: At any time, adversary ${\mathcal {A}}$ may issue the following queries:

• Private key queries. Let ${ ID}_i$ be a private key query issued by adversary ${\mathcal {A}}$. If $i=l$, ${\mathcal {S}}$ outputs failure and stops. Otherwise, ${\mathcal {S}}$ knows $H_1({ ID}_i) = I_i$ and returns $V_i^{ - 1} = g^{\frac{1}{\alpha + I_i}}$ to ${\mathcal {A}}$.

• Signcryption queries. Once ${\mathcal {A}}$ issues a signcryption query for a message m and identities $({ ID}_s, { ID}_r) = ({ ID}_i, { ID}_j)$ for $i,j \in \left\{ {1, \ldots ,q_{H_1}} \right\}$. If $i \ne l$, ${\mathcal {S}}$ knows the sender’s private key $d_{ID_i} = V_i^{ - 1}$ and can answer the query according to the specification of Signcryption. If $i = l$, we have $j \ne l$ by the irreflexivity assumption. Thus, ${\mathcal {S}}$ knows the receiver’s private key $d_{ID_j} = V_j^{ - 1}$ and does the following steps:

  • 1. Randomly choose $x, y, h \in {\mathbb {Z}}_p^*$.

  • 2. Compute $C_1 = d_{ID_j}^{xy^{-1}}$, $C_2= {\left( {{g_1}{g^{{I_j}}}} \right) ^{ - h}}g_1^x$ and $r = e\left( {C_2g^{I_ix}, d_{ID_j}} \right)$, $C_5 = I_ix$, set $C_4=y$.

  • 3. Patch the hash value $H_2(m, R, C_1, C_2)$ to h. ${\mathcal {S}}$ fails if $H_2$ is already defined, but this only happens with probability $\frac{q_{sc} + q_{H_2}}{2^k}$.

  • 4. Compute $C_3 = m \oplus H_3(R)$ and return $\sigma = (C_1, C_2, C_3, y, I_jx)$ to ${\mathcal {A}}$.

  To see its correctness, we implicitly set $s = \left( {\frac{{\alpha + {I_i}}}{{\alpha + {I_j}}}} \right) x - h$, then we have

  $$\begin{aligned}&\begin{array}{ll} T&{}= {C_2}{g^{{C_5}}} \\ &{}= {\left( {{g_1}{g^{{I_j}}}} \right) ^{ - h}}g_1^x \cdot {g^{{I_i}x}}\\ &{}= {\left( {{g^{\alpha + {I_j}}}} \right) ^{ - h}} \cdot {\left( {{g^{\alpha + {I_i}}}} \right) ^x} \\ &{}= {\left( {{g^{\alpha + {I_j}}}} \right) ^{s - \left( {\frac{{\alpha + {I_i}}}{{\alpha + {I_j}}}} \right) x}} \cdot {\left( {{g^{\alpha + {I_i}}}} \right) ^x} \\ &{}= {\left( {{g^{\alpha + {I_j}}}} \right) ^s}{\left( {{g^{\alpha + {I_i}}}} \right) ^{ - x}} \cdot {\left( {{g^{\alpha + {I_i}}}} \right) ^x} \\ &{}= {\left( {{g^{\alpha + {I_j}}}} \right) ^s} \\ &{}= {\left( {{g_1}{g^{{H_1}\left( {{ ID}_j} \right) }}} \right) ^s}, \end{array}\\&S = C_1^{{C_4}} = {\left( {d_{ID_j}^{x{y^{ - 1}}}} \right) ^y} = d_{ID_j}^x = {\left( {{g^{\frac{1}{{\alpha + {I_j}}}}}} \right) ^{\left( {s + h} \right) \cdot \frac{{\alpha + {I_j}}}{{\alpha + {I_i}}}}} \\&\quad = {\left( {{g^{\frac{1}{{\alpha + {I_i}}}}}} \right) ^{\left( {s + h} \right) }} = d_{ID_i}^{s + h}. \end{aligned}$$

  Thus, $\sigma$ is a valid ciphertext.

• Unsigncryption queries. Once adversary issues the unsigncryption query on $\sigma = (C_1, C_2, C_3, C_4, C_5)$ for identities $({ ID}_s, { ID}_r) = ( { ID}_i, { ID}_j)$, simulator ${\mathcal {S}}$ first examines the ${ ID}_j$. If $j \ne l$, sine ${\mathcal {S}}$ knows receiver’s private key $d_{{ ID}_j}= V_j^{-1}$, and it can answer the query using $d_{ID_j}$. If $j = l$, we have $i \ne l$ by the irreflexivity assumption. Thus, ${\mathcal {S}}$ knows the sender’s private key $d_{ID_i} = V_i^{ - 1}$. For all valid ciphertexts, we have

  $$\begin{aligned} s={\log _{{d_{ID_i}}}}\left( {C_1^{{C_4}} \cdot d_{_{ID_i}}^{ - h}} \right) = {\log _{{g_1}{g^{_{{I_j}}}}}}\left( {{C_2}{g^{{C_5}}}} \right) . \end{aligned}$$

  That is

  $$\begin{aligned} d_{ID_i}^s = C_1^{{C_4}} \cdot d_{ID_i}^{ - h}, \quad {\left( {{g_1}{g^{{I_j}}}} \right) ^s} = {C_2}{g^{{C_5}}}, \end{aligned}$$

  where $h = H_2(m, R, C_1, C_2)$. Therefore, we have the relation

  $$\begin{aligned} e\left( {{C_2}{g^{C_5}},{d_{ID_i}}} \right) = e\left( {{g_1}{g^{_{{I_j}}}}, C_1^{C_4} \cdot d_{_{ID_i}}^{ - h}} \right) . \end{aligned}$$

  Then ${\mathcal {S}}$ computes $\lambda = e\left( {C_1^{{C_4}}, {g_1}{g^{_{I_i}}}} \right)$ and searches through list $L_2$ for entries of the form $\Big ( m_i, R_i, C_{1,i}, C_{2,i}, h_{2,i}, C_{3,i}, {\lambda _i}\Big )$ indexed by $i \in \left\{ {1, \ldots , q_{{H_2}}} \right\}$. If none is found, reject $\sigma$. Otherwise, ${\mathcal {S}}$ does the further following checking for the corresponding indexes

  $$\begin{aligned} \frac{{e\left( {{C_{2}}{g^{{C_{5}}}}, {d_{ID_i}}} \right) }}{{e\left( {{g_1}{g^{_{{I_j}}}}, C_1^{{C_4}}} \right) }} = e{\left( {{g_1}{g^{_{{I_j}}}}, d_{ID_i}} \right) ^{ - {h_{2,i}}}}. \end{aligned}$$

  If the unique $i \in \left\{ {1, \ldots , q_{H_2}} \right\}$ satisfies the above equation, the matching message $m_i$ is returned. Otherwise, ${\mathcal {S}}$ rejects it. It is clear that, for all queries, the probability to reject a valid ciphertext is smaller than $\frac{q_{us}}{2^k}$.

Challenge: ${\mathcal {A}}$ chooses two messages ${m_0},{m_1}$ and challenged identities $({ ID}_s, { ID}_r )$ under the restriction that ${ ID}_r$ has not been query its private key in Phase 1. If ${{ ID}_r \ne { ID}_l}$, ${\mathcal {B}}$ aborts.

Otherwise, ${\mathcal {S}}$ randomly chooses $C_3^* \in {\left\{ {0,1} \right\} ^n}$, $\beta , x, y \in {\mathbb {Z}}_p^*$, $C_1^* \in {\mathbb {G}}$, sets $C_4^*=x, C_5^*=y$ and computes $C_2^* = g^{ - \beta }g^{ - y}$. ${\mathcal {S}}$ returns the challenge ciphertext $\sigma ^* = \left( {C_1^*, C_2^*, C_3^*, C_4^*, C_5^*} \right)$ to ${\mathcal {A}}$. Let $\rho = \frac{\beta }{a}$, since $\alpha = -a-I_l$, we have

$$\begin{aligned} C_2^*{g^{C_5^*}} {=} {g^{ - \beta }}{g^{ - y}} \cdot {g^y} {=} {g^{ - \beta }} {=} {g^{ - \rho a}} {=} {g^{\rho \left( {\alpha {+} {I_l}} \right) }} {=} {\left( {{g_1}{g^{{I_l}}}} \right) ^\rho }. \end{aligned}$$

${\mathcal {A}}$ cannot learn that $\sigma ^*$ is an invalid ciphertext unless it has queried $H_2$ or $H_3$ on $e{\left( {g,g} \right) ^\rho }$.

Phase 2: ${\mathcal {A}}$ issues more queries as in Phase 1 under the restrictions that it cannot make a private key query on ${ ID}_r$ and unsigncryption query on $\sigma ^*$. ${\mathcal {S}}$ responds as in Phase 1.

Guess: Finally, ${\mathcal {A}}$ outputs its guess $b' \in \{0,1\}$.

${\mathcal {S}}$ ignores the guess of ${\mathcal {A}}$ and randomly picks an entry $\left( {R_i, h_{3,i}} \right)$ or $( m_i, R_i,$ $C_{1,i}, C_{2,i}, h_{2,i}, C_{3,i}, {\lambda _i})$ from the list $L_3$ or $L_2$. From the decryption, we have

$$\begin{aligned} {R^*} = e{\left( {g,g} \right) ^\rho } = e{\left( {g,g} \right) ^{\frac{\beta }{a}}} = e{\left( {h,h} \right) ^{\frac{{f{{\left( a \right) }^2}\beta }}{a}}}. \end{aligned}$$

As f(a) is the polynomial contained a, by polynomial division, we have

$$\begin{aligned}&\begin{array}{ll} \frac{{f{{\left( a \right) }^2}\beta }}{a} &{}= \left( {\sum \limits _{j= 0}^{q - 2} {{c_{j + 1}}{a^j} + \frac{{{c_0}}}{a}} } \right) f\left( a \right) \beta \\ &{}= f\left( a \right) \beta \cdot \sum \limits _{j = 0}^{q - 2} {{c_{j + 1}}{a^j}} + \left( {{c_0}\beta \sum \limits _{j = 0}^{q - 2} {{c_{j + 1}}{a^j} + \frac{{c_0^2\beta }}{a}} } \right) , \end{array}\\&\begin{array}{ll} {R^*} &{}= e{\left( {h,h} \right) ^{\frac{{f{{\left( a \right) }^2}\beta }}{a}}} \\ &{}= e{\left( {h,h} \right) ^{f\left( a \right) \beta \cdot \sum \limits _{j = 0}^{q - 2} {{c_{j + 1}}{a^j}} + \left( {{c_0}\beta \sum \limits _{j = 0}^{q - 2} {{c_{j + 1}}{a^j} + \frac{{c_0^2\beta }}{a}} } \right) }} \\ &{}= e\left( {{g^\beta },{h^{\sum \limits _{j = 0}^{q - 2} {{c_{j + 1}}{a^j}} }}} \right) e\left( {{h^{{c_0}\beta }},{h^{\sum \limits _{j = 0}^{q - 2} {{c_{j + 1}}{a^j}} }}} \right) e{\left( {h,h} \right) ^{\frac{{c_0^2\beta }}{a}}} \\ &{}= e\left( {{{\left( {g{h^{{c_0}}}} \right) }^\beta },{h^{\sum \limits _{j = 0}^{q - 2} {{c_{j + 1}}{a^j}} }}} \right) e{\left( {h,h} \right) ^{\frac{{c_0^2\beta }}{a}}}. \end{array} \end{aligned}$$

Thus, we can solve the q -BDHI problem by computing

$$\begin{aligned} e{\left( {h,h} \right) ^{\frac{1}{a}}} = {\left( {{R^*} \cdot e\left( {{{\left( {g{h^{{c_0}}}} \right) }^{ - \beta }},{h^{\sum \limits _{j = 0}^{q - 2} {{c_{j + 1}}{a^j}} }}} \right) } \right) ^{\frac{1}{{c_0^2\beta }}}}. \end{aligned}$$

This completes the description of the simulation. It remains to analyze ${\mathcal {S}}$’s advantage to solve the q-BDHI problem. We define the following events:

$E_1:$ ${\mathcal {A}}$ does not choose ${ ID}_l$ as the challenge receiver’s identity.

$E_2:$ ${\mathcal {A}}$ issues a private key query on ${ ID}_l$.

$E_3:$ ${\mathcal {S}}$ aborts in a signcryption query because of a collision on $H_2$.

$E_4:$ ${\mathcal {S}}$ rejects a valid ciphertext in one unsigncryption query.

From the above analysis, we know that these four events are independent events and the probability of ${\mathcal {S}}$ which will not abort is

$$\begin{aligned} \Pr \left[ {{}^\lnot { abort}} \right] = \Pr \left[ {{}^\lnot {E_1} \wedge {}^\lnot {E_2} \wedge {}^\lnot {E_3} \wedge {}^\lnot {E_4}} \right] . \end{aligned}$$

We have $\Pr \left[ {{}^\lnot {E_1}} \right] = \frac{1}{{{q_{{H_1}}}}}$ and know ${{}^\lnot {E_1}}$ implies ${{}^\lnot {E_2}}$. We also observe that $\Pr \left[ { {E_3}} \right] \le \frac{{{q_{sc}}\left( {{q_{sc}} + {q_{{H_2}}}} \right) }}{{{2^k}}}$ and $\Pr \left[ {{E_4}} \right] \le \frac{{{q_{us}}}}{{{2^k}}}$. Therefore,

$$\begin{aligned} \Pr \left[ {{}^\lnot { abort}} \right]= & {} \Pr \left[ {{}^\lnot {E_1} \wedge {}^\lnot {E_3} \wedge {}^\lnot {E_4}} \right] \\\ge & {} \frac{1}{{{q_{{H_1}}}}}\left( {1 - \frac{{{q_{sc}}\left( {{q_{sc}} + {q_{{H_2}}}} \right) }}{{{2^k}}}} \right) \left( {1 - \frac{{{q_{us}}}}{{{2^k}}}} \right) . \end{aligned}$$

The chosen entry contains the right element ${R^*} = e{\left( {g, g} \right) ^\rho }$ with probability larger than $\frac{1}{{2{q_{{H_2}}} + {q_{{H_3}}}}}$, since $L_3$ contains no more than $q_{H_2} + q_{H_3}$ records by construction. Thus, the advantage to solve q-BDHI problem is

$$\begin{aligned} \epsilon ' \ge \frac{\epsilon }{{{q_{{H_1}}}\left( {2{q_{{H_2}}} + {q_{{H_3}}}} \right) }}\left( {1 - \frac{{{q_{sc}}\left( {{q_{sc}} + {q_{{H_2}}}} \right) }}{{{2^k}}}} \right) \left( {1 - \frac{{{q_{us}}}}{{{2^k}}}} \right) . \end{aligned}$$

$\square$

Theorem 3

Suppose that an EUF-CMA adversary ${\mathcal {A}}$ has an advantage $\epsilon \ge \frac{{10\left( {{q_{sc}} + 1} \right) \left( {{q_{sc}} + {q_{{H_2}}}} \right) }}{{{2^k}}}$ to produce a forgery within a time t, when asking $q_{H_i}$ queries to random oracles ${H_i}\left( {i = 1,2,3} \right)$, $q_{sc}$ signcryption queries and $q_{us}$ queries to the unsigncryption queries. Then there is an algorithm ${\mathcal {S}}$ to solve the q-SDH problem for $q=q_{H_1}$ in expected time

$$\begin{aligned} t'\le & {} 120686{q_{{H_1}}}{q_{{H_2}}}\frac{{t + \mathrm{O}\left( {\left( {{q_{sc}} + {q_{us}}} \right) {t_p}} \right) + {q_{us}}{q_{{H_2}}}{t_e}}}{{\epsilon \left( {1 - {1 /{{2^k}}}} \right) \left( {1 - {q /{{2^k}}}} \right) }} \\&+\, \mathrm{O}\left( {{q^2}{t_m}} \right) \end{aligned}$$

where $t_p$ is the complexity of a pairing computation, $t_e$ is the cost of exponentiation in ${\mathbb {G}}_T$ and $t_m$ is the cost of scalar multiplication in ${\mathbb {G}}$.

Proof

Suppose adversary ${\mathcal {A}}$ can produce a forgery in our scheme with advantage $\epsilon$. We build a simulator ${\mathcal {S}}$ that solves q-SDH problem by running ${\mathcal {A}}$. Let $\left( {h, h^a, h^{a^2}, \ldots , h^{a ^q}} \right)$ be a random instance of q-SDH problem taken as input by ${\mathcal {S}}$ and its goal is to find a pair $\left( {c,h^{\frac{1}{{a + c}}}} \right)$, $c \in {\mathbb {Z}}_p^*$. In order to use ${\mathcal {A}}$ to solve the problem, ${\mathcal {S}}$ needs to simulate a challenger and responses all the queries for ${\mathcal {A}}$. Simulator ${\mathcal {S}}$ works by interacting with ${\mathcal {A}}$ in an EUF-CMA game as follows:

Setup: ${\mathcal {S}}$ randomly chooses $w^*, w_1, w_2, \ldots , w_{q-1} \in {\mathbb {Z}}_p^*$ and expands the polynomial

$$\begin{aligned} f\left( z \right) = \prod \limits _{i = 1}^{q-1} {\left( {z + {w_i}} \right) } = \sum \limits _{j = 0}^{q - 1} {{c_j}{z^j}}. \end{aligned}$$

Then set $g = h^{\sum \limits _{j = 0}^{q - 1} {{c_j}{a^j}} } = {h^{f\left( a \right) }}$, ${g_1} = {h^{\sum \limits _{j = 1}^q {{c_{j - 1}}{a^j}} }} = {h^{af\left( a \right) }} = {g^a}$ and

$$\begin{aligned} {f_i}\left( z \right) = \frac{{f\left( z \right) }}{{z + {w_i}}} = \sum \limits _{j = 0}^{q - 2} {{d_j}{z^j}}, \end{aligned}$$

and compute

$$\begin{aligned} {V_i} = {h^{\sum \limits _{j = 0}^{q - 2} {{d_j}{a^j}} }} = {h^{{f_i}\left( a \right) }} = {h^{\frac{{f\left( a \right) }}{{a + {w_i}}}}} = {g^{\frac{1}{{a + {w_i}}}}}. \end{aligned}$$

Thus, g is a generator of ${\mathbb {G}}$ and ${\mathcal {S}}$ knows pairs $\left( {w_i, V_i=g^{\frac{1}{a + w_i}}} \right)$. Then ${\mathcal {S}}$ computes $v = e(g, g)$. The system public key is

$$\begin{aligned} mpk = \left( {G, {G_T}, p, g, {g_1}, v, n, e, {H_1}, {H_2}, {H_3}} \right) . \end{aligned}$$

${\mathcal {S}}$ implicitly sets the master key ${ msk}=a$ and randomly chooses a challenge identity ${ ID}_s^* \in {\left\{ {0,1} \right\} ^*}$ to adversary ${\mathcal {A}}$.

$H_1$ queries: At any time, adversary ${\mathcal {A}}$ can query the random oracle $H_1$ on ${ ID}_i$. ${\mathcal {S}}$ maintains a list $L_1$ of tuples $\left( {{ ID}_i, w_i} \right)$. This list is initially empty. If ${ ID}_i$ is already on the list $L_1$, ${\mathcal {S}}$ responds with $H_1({ ID}_i) = w_i$. Otherwise, if ${ ID}_i = { ID}_s^*$, ${\mathcal {S}}$ sets $H_1({ ID}_i)=w^*$. If ${ ID}_i \ne { ID}_s^*$, ${\mathcal {S}}$ sets $H_1({ ID}_i) = w_i$. ${\mathcal {S}}$ adds the new tuple $({ ID}_i, w_i)$ to the list $L_1$ and returns $w_i$.

$H_2$ queries: At any time, adversary ${\mathcal {A}}$ can query the random oracle $H_2$ on $(m_i, R_i, C_{1,i}, C_{2,i} )$. ${\mathcal {S}}$ maintains a list ${L_2}$ of tuples $( m_i, R_i, C_{1,i}, C_{2,i}, h_{2,i}, C_{3,i}, \lambda _i)$. This list is initially empty. If tuple $(m_i, R_i, C_{1,i}, C_{2,i} )$ already appears on the list $L_2$, ${\mathcal {S}}$ responds with ${H_2}\left( {m_i, R_i, C_{1,i}, C_{2,i}} \right) = h_{2,i}$.

Otherwise, ${\mathcal {S}}$ picks a random $h_{2,i} \in {\mathbb {Z}}_p^*$, sets ${H_2}\left( {m_i, R_i, C_{1,i}, C_{2,i}} \right) = h_{2,i}$ and returns $h_{2,i}$ to ${\mathcal {A}}$. To anticipate possible subsequent Unsigncrypt requests, ${\mathcal {S}}$ additionally simulates random oracle $H_3$ on its own to obtain $h_{3,i} = H_3(R_i)$and computes $C_{3,i} = m_i \oplus h_{3,i}$, $\lambda _i = R_i \cdot v^{h_{2,i}}$ and adds the new tuple $\left( {m_i, R_i, C_{1,i}, C_{2,i}, h_{2,i}, C_{3,i}, {\lambda _i}} \right)$ to the list $L_2$.

$H_3$ queries: At any time, adversary ${\mathcal {A}}$ can query the random oracle $H_3$ on $R_i$. ${\mathcal {S}}$ maintains a list $L_3$ of tuples $\left( {R_i,h_{3,i}} \right)$. This list is initially empty. If $R_i$ is on the list, ${\mathcal {S}}$ responds with $H_3(R_i) = h_{3,i}$. Otherwise, ${\mathcal {S}}$ randomly chooses $h_{3,i} \in \left\{ {0,1} \right\} ^n$, sets $H_3(R_i) = h_{3,i}$ and responds to ${\mathcal {A}}$ with ${h_{3,i}}$ and then adds the new tuple $\left( {R_i,h_{3,i}} \right)$ to the list $L_3$.

Private key queries: Let ${ ID}_i$ be a private key query issued by ${\mathcal {A}}$. If $I{D_i} = { ID}_s^*$, ${\mathcal {S}}$ aborts. Otherwise, ${\mathcal {S}}$ returns $V_i = g^{\frac{1}{a + {w_i}}}$ to ${\mathcal {A}}$.

Signcryption queries Once ${\mathcal {A}}$ issues a signcryption query for a message m and identities $\left( {{ ID}_s, { ID}_r} \right) = \left( {{ ID}_i, { ID}_j} \right)$ for $i,j \in \left\{ {1, \ldots , q_{H_1}} \right\}$. If ${ ID}_i \ne { ID}_s^*$, ${\mathcal {S}}$ knows the sender’s private key $d_{ID_i} = V_i$ and can answer the query according to the specification of Signcryption. If ${ ID}_i = { ID}_s^*$, we have ${ ID}_j\ne { ID}_s^*$ by the irreflexivity assumption. Thus, ${\mathcal {S}}$ knows the receiver’s private key $d_{ID_j} = V_j$ and does the following steps:

• 1. Randomly choose $x, y, h \in {\mathbb {Z}}_p^*$.

• 2. Compute $C_1 = d_{ID_j}^{xy^{-1}}$, $C_2 = \left( {{g_1}{g^{I_j}}} \right) ^{ - h}g_1^x$, $R = e\left( {C_2g^{I_ix}, d_{ID_j}} \right)$ and $C_5 = {I_i}x$, set $C_4=y$.

• 3. Patch the hash value $H_2(m, R, C_1, C_2)$ to h. ${\mathcal {S}}$ fails if $H_2$ is already defined but this only happens with probability $\frac{q_{sc} + q_{H_2}}{2^k}$.

• 4. Compute $C_3 = m \oplus H_3(R)$ and return $\sigma = \left( {C_1, C_2, C_3, y, I_ix} \right)$ to ${\mathcal {A}}$.

To see it correctness, we implicitly set $s = \left( {\frac{\alpha + I_i}{\alpha + I_j}} \right) x - h$, then we have

$$\begin{aligned}&S = C_1^{{C_4}} = {\left( {d_{ID_j}^{x{y^{ - 1}}}} \right) ^y} = d_{ID_j}^x = {\left( {{g^{\frac{1}{{\alpha + {I_j}}}}}} \right) ^{\left( {s + h} \right) \cdot \frac{{\alpha + {I_j}}}{{\alpha + {I_i}}}}} \\&\quad = {\left( {{g^{\frac{1}{{\alpha + {I_i}}}}}} \right) ^{\left( {s + h} \right) }} = d_{ID_i}^{s + h},\\&\begin{array}{ll} T&{}= {C_2}{g^{{C_5}}} \\ &{}= {\left( {{g_1}{g^{{I_j}}}} \right) ^{ - h}}g_1^x \cdot {g^{{I_i}x}} \\ &{}= {\left( {{g^{\alpha + {I_j}}}} \right) ^{ - h}} \cdot {\left( {{g^{\alpha + {I_i}}}} \right) ^x} \\ &{}= {\left( {{g^{\alpha + {I_j}}}} \right) ^{s - \left( {\frac{{\alpha + {I_i}}}{{\alpha + {I_j}}}} \right) x}} \cdot {\left( {{g^{\alpha + {I_i}}}} \right) ^x} \\ &{}= {\left( {{g^{\alpha + {I_j}}}} \right) ^s}{\left( {{g^{\alpha + {I_i}}}} \right) ^{ - x}} \cdot {\left( {{g^{\alpha + {I_i}}}} \right) ^x} \\ &{}= {\left( {{g^{\alpha + {I_j}}}} \right) ^s} \\ &{}= {\left( {{g_1}{g^{{H_1}\left( {{ ID}_j} \right) }}} \right) ^s}. \end{array} \end{aligned}$$

Thus, $\sigma$ is a valid ciphertext.

Unsigncryption queries: Once adversary issues an unsigncryption query on $\sigma = \left( {C_1, C_2, C_3, C_4, C_5} \right)$ for identities $\left( {{ ID}_s, { ID}_r} \right) = \left( {{ ID}_i, { ID}_j} \right)$, simulator ${\mathcal {S}}$ first examines the ${ ID}_j$. If ${ ID}_j \ne { ID}_s^*$, since ${\mathcal {S}}$ knows receiver’s private key $d_{{ ID}_j} = V_j$, it can answer the query by using $d_{{ ID}_j}$ to decrypt the ciphertext. If ${ ID}_j = { ID}_s^*$, we have ${ ID}_i \ne { ID}_s^*$ by the irreflexivity assumption. Thus, ${\mathcal {S}}$ knows the sender’s private key $d_{ID_i} = V_i$. For all valid ciphertexts, we have

$$\begin{aligned} s={\log _{{d_{I{D_i}}}}}\left( {C_1^{{C_4}} \cdot d_{_{I{D_i}}}^{ - h}} \right) = {\log _{{g_1}{g^{_{{w_j}}}}}}\left( {{C_2}{g^{{C_5}}}} \right) . \end{aligned}$$

That is

$$\begin{aligned} d_{ID_i}^s= & {} C_1^{C_4} \cdot d_{ID_i}^{ - h},\\ {\left( {{g_1}{g^{{w_j}}}} \right) ^s}= & {} {C_2}{g^{{C_5}}}, \end{aligned}$$

where $h = {H_2}\left( {m, R, C_1, C_2} \right)$. Therefore, we have the relation

$$\begin{aligned} e\left( {{C_2}{g^{{C_5}}},{d_{ID_i}}} \right) = e\left( {{g_1}{g^{_{{w_j}}}},C_1^{{C_4}} \cdot d_{_{ID_i}}^{ - h}} \right) . \end{aligned}$$

Then ${\mathcal {S}}$ computes $\lambda = e\left( {C_1^{C_4}, g_1{g^{_{w_i}}}} \right)$ and searches through list $L_2$ for entries of the form $\Big ( m_i, R_i, C_{1,i}, C_{2,i}, h_{2,i}, C_{3,i}, \lambda _i \Big )$ indexed by $i \in \left\{ {1, \ldots ,{q_{{H_2}}}} \right\}$. If none is found, reject $\sigma$. Otherwise, ${\mathcal {S}}$ does the further following checking for the corresponding indexes

$$\begin{aligned} \frac{{e\left( {{C_2}{g^{{C_5}}},{d_{ID_i}}} \right) }}{{e\left( {{g_1}{g^{_{{w_j}}}},C_1^{{C_4}}} \right) }} = e{\left( {{g_1}{g^{_{{w_j}}}},{d_{ID_i}}} \right) ^{ - {h_{2,i}}}}. \end{aligned}$$

If the unique $i \in \left\{ {1, \ldots ,{q_{{H_2}}}} \right\}$ satisfies the above checking equation, the matching message $m_i$ is returned. Otherwise, ${\mathcal {S}}$ rejects it. It is clear that, for all queries, the probability to reject a valid ciphertext is smaller than $\frac{q_{us}}{2^k}$.

Forge: From the forking Lemma [16], after a polynomial replays of the adversary ${\mathcal {A}}$, ${\mathcal {S}}$ can obtain two valid forge signatures $\left( {C_1, C_2, C_3, C_4, C_5, s, h, m^*} \right)$ and $\left( {C_1, C_2,}\right. \left. {C_3, C_4', C_5, s, h', m^*} \right)$ for $ID^*$, where $h = H_2\left( {m^*, R, C_1,}\right. \left. {C_2} \right)$ and $h' = H_2\left( {m^*, R, C_1, C_2} \right)$, but $h \ne h'$. Since both signatures are valid and satisfy the verification equation, we have

$$\begin{aligned}&e\left( {C_1^{{C_4}},{g_1}{g^{{H_1}\left( {{ ID}_s^*} \right) }}} \right) e{\left( {g,g} \right) ^{ - h}} \\&\quad \qquad = e\left( {{C_1}{^{{C_4}'}},{g_1}{g^{{H_1}\left( {{ ID}_s^*} \right) }}} \right) e{\left( {g,g} \right) ^{ - h'}}. \end{aligned}$$

That is

$$\begin{aligned}&e\left( {C_1^{{C_4}- {C_4}'},{g_1}{g^{{H_1}\left( {{ ID}_s^*} \right) }}} \right) = e{\left( {g,g} \right) ^{h - h'}},\\&e\left( {{{\left( {C_1^{{C_4}- {C_4}'}} \right) }^{{{\left( {h - h'} \right) }^{ - 1}}}},{g_1}{g^{{H_1}\left( {{ ID}_s^*} \right) }}} \right) = e\left( {g,g} \right) . \end{aligned}$$

Since

$$\begin{aligned} {g_1}{g^{{H_1}\left( {{ ID}_s^*} \right) }} = {g^{\alpha + {w^*}}}, \end{aligned}$$

we have

$$\begin{aligned}&{V^*} = {\left( {C_1^{{C_4}- {C_4}'}} \right) ^{{{\left( {h - h'} \right) }^{ - 1}}}} = {g^{\frac{1}{{a + {w^*}}}}} = {h^{\frac{{f\left( a \right) }}{{a + {w^*}}}}},\\&\quad \qquad \frac{{f\left( a \right) }}{{a + {w^*}}} = \frac{\gamma }{{a + {w^*}}} + \sum \limits _{i = 0}^{q - 2} {{\gamma _i}{a^i}}. \end{aligned}$$

Therefore,

$$\begin{aligned} {h^{\frac{1}{{a + {w^*}}}}} = {\left( {{V^*} \cdot {h^{ - \sum \limits _{i = 0}^{q - 2} {{\gamma _i}{a^i}} }}} \right) ^{\frac{1}{\gamma }}}. \end{aligned}$$

We find a pair $\left( {{w^*},{h^{\frac{1}{{a + {w^*}}}}}} \right)$ to the solution of q-SDH problem.

Finally, by the forking Lemma, it comes that, if ${\mathcal {A}}$ forges a signature in a time t with probability $\epsilon \ge \frac{{10\left( {{q_{sc}} + 1} \right) \left( {{q_{sc}} + {q_{{H_2}}}} \right) }}{{{2^k}}}$, simulator ${\mathcal {S}}$ can solve the q-SDH problem in expected time

$$\begin{aligned} t'\le & {} 120686{q_{{H_1}}}{q_{{H_2}}}\frac{{t + \mathrm{O}\left( {\left( {{q_{sc}} + {q_{us}}} \right) {t_p}} \right) + {q_{us}}{q_{{H_2}}}{t_e}}}{{\epsilon \left( {1 - {1 /{{2^k}}}} \right) \left( {1 - {q /{{2^k}}}} \right) }} \\&+\, \mathrm{O}\left( {{q^2}{t_m}} \right) , \end{aligned}$$

where $t_p$ is the complexity of a pairing computation, $t_e$ is the cost of exponentiation in ${\mathbb {G}}_T$ and $t_m$ is the cost of scalar multiplication in ${\mathbb {G}}$. $\square$

5 Evaluation and comparison

In this section, we draw comparisons between our schemes and the other identity-based online/offline encryption schemes and signcryption schemes in the literature. We denote by $m_{c}$ the modular computation in ${\mathbb {Z}}_p^*$, ${\mathcal {S}}$ a one-time strong signature in [11]. We set k the block size of a symmetric key encryption ${\mathcal {E}}$ in [8], $\tilde{k}$ the security system parameter in [7], n the message size. We first compare our encryption scheme with the existing schemes. Then we provide an evaluation for our signcryption scheme. Without loss of generality, we assume one multi-exponentiation is equal to two exponentiations in group ${\mathbb {G}}$.

Table 1 Comparison of computation cost

Table 2 Comparison of storage

Table 3 Comparison of computation cost and size

Table 1 provides a comparison of computation cost and shows that our scheme has the lightest computation in the offline phase. It reduces at least one element in ${\mathbb {G}}$. In the online phase, it needs two modular computations in ${\mathbb {Z}}_p^*$ which still has a good computational efficiency. The proposed scheme can achieve IND-ID-CCA under the k-CAA1 assumption.

From Table 2, we achieve shorter ciphertext size than the best-known IBOOE instantiation. We only have one element in ${\mathbb {G}}$ in the final ciphertext, which greatly reduces the bandwidth when transmitting the encrypted massage. In the offline storage, our scheme also achieves a comparable result, although the protocol in [8] is slightly better in the offline storage compared to our scheme. However, [8] depends on one symmetric key encryption. It leads to the key management problem and the security also depends on the security of the symmetric key encryption algorithm. Thus, in some way, our scheme has the smallest size and saves one element in ${\mathbb {G}}$ in both the offline and online phases.

Table 3 shows that compared to the existing schemes, our identity-based online/offline signcryption scheme achieves the least computation and the smallest storage in both offline and online stages. In the offline computation, we reduce at least one operation in ${\mathbb {G}}$. Compared to [13], our proposed scheme saves one element in ${\mathbb {G}}$ and one element in ${\mathbb {Z}}_p^*$ in the offline storage, which leads to reduce one element in ${\mathbb {G}}$ in the final ciphertext. The online computation is still comparable and requires two modular multiplications. These improvements in our two schemes are very important when the communication bandwidth is limited.

We remark that the security proofs of our schemes are under the random oracle model. Random oracle model has usually been regarded as a heuristic method since no hash functions can be used as the random oracle. However, the proof analysis in the random oracle model is more efficient than that without random oracle and achieves an acceptable security level, which has been commonly accepted. In some situations, the weight of efficiency is over security level. Therefore, in this case, the random oracle model provides a better choice.

6 Conclusion

We proposed two novel and efficient identity-based online/offline schemes for encryption and signcryption, respectively. Both our schemes are proven secure in the random oracle model and achieve the shortest ciphertext. The proposed schemes can reduce one operation in ${\mathbb {G}}$ in offline computation and save at least one element in ${\mathbb {G}}$ in both offline storage and online ciphertext. These improvements are significant for the devices with limited storage and computation power. Therefore, our schemes are desirable candidates for lightweight devices.