Open AccessArticle

Identity Based Generalized Signcryption Scheme in the Standard Model

Xiaoqin Shen

Yang Ming

^2,*

and

Jie Feng

School of Sciences, Xi’an University of Technology, Xi’an 710054, China

School of Information Engineering, Chang’an University, Xi’an 710064, China

Author to whom correspondence should be addressed.

Entropy 2017, 19(3), 121; https://doi.org/10.3390/e19030121

Submission received: 10 January 2017 / Revised: 7 March 2017 / Accepted: 13 March 2017 / Published: 17 March 2017

(This article belongs to the Section Information Theory, Probability and Statistics)

Download Versions Notes

Abstract

Generalized signcryption (GSC) can adaptively work as an encryption scheme, a signature scheme or a signcryption scheme with only one algorithm. It is more suitable for the storage constrained setting. In this paper, motivated by Paterson–Schuldt’s scheme, based on bilinear pairing, we first proposed an identity based generalized signcryption (IDGSC) scheme in the standard model. To the best of our knowledge, it is the first scheme that is proven secure in the standard model.

Keywords:

generalized signcryption; identity based cryptography; bilinear pairings; standard model

1. Introduction

Confidentiality, integrity, non-repudiation and authentication are the important requirements for many cryptographic applications. A traditional approach to achieve these requirements simultaneously is to sign-then-encrypt or encrypt-then-sign. To enhance efficiency, Zheng [1] proposed the concept of signcryption in 1997. The main idea of this primitive is to perform signature and encryption simultaneously in a logical step. Compared with traditional methods [2], signcryption reduces the computational costs and communication overheads. Since then, many public key signcryption schemes have been proposed [3,4,5].

In 1984, Shamir [6] first proposed the idea of identity-based (ID-based) public key cryptography (ID-PKC) to simplify key management procedures of traditional certificate-based public key cryptography. The main idea of ID-PKC is that the user’s public key can be calculated directly from his/her identity such as email addresses rather than being extracted from a certificate issued by a certificate authority (CA). Private keys are generated for the users by a trusted third party, called a Private Key Generator (PKG) using some master key related to the global parameters for the system. The direct derivation of public keys in ID-PKC eliminates the need for certificates and some of the problems associated with them. The first identity based signature scheme was given by Shamir [6], but the first identity based encryption scheme was presented by Boneh and Fanklin [7] in 2001. The first identity based signcryption scheme was proposed by Malone Lee [8] in 2002, and they also gave the security model for signcryption in identity based settings. Since then, many identity based signcryption schemes have been proposed [9,10,11,12,13,14,15,16,17].

The signcryption scheme was used in these application environments, which need simultaneous confidentiality and authenticity. However, it is not all application environments requiring both confidentiality and authenticity. If only one of the two functionalities is required, then the signcryption scheme is not efficient. To achieve this, we can use an encryption/signature scheme. However, in the low bandwidth environment, we have to afford to use three different cryptographic algorithms—encryption, signature and signcryption—to achieve confidentiality and authenticity separately or simultaneously. In 2006, to decrease implementation complexity, Han et al. [18] proposed the concept of generalized signcryption, which can work as an encryption scheme or a signature scheme or a signcryption scheme as required. They also proposed a concert construction based on the Elliptic Curve Digital Signature Algorithm (ECDSA) . Wang et al. [19] gave the security model of a generalized signcryption scheme and modified the scheme proposed in [18]. In 2008, Lal et al. [20] presented the first identity based generalized signcryption (IDGSC) scheme. However, Yu et al. [21] showed that the security model in [20] is not complete. They modified the security model and gave a new scheme that is secure in this model. In 2011, Kushwah et al. [22] simplified the security model for IDGSC and proposed an efficient scheme.

Provable security is the basic requirement for ID-based generalized signcryption schemes. The security of all of the schemes [20,21,22] described above was only proven secure in the random oracle model. The random oracle model was introduced by Bellare and Rogaway in [23]. The model is a formal model in analyzing cryptographic schemes, where a hash function is considered as a black box that contains a random function. Although the model is efficient and useful, it has received a lot of criticism that the proofs in the random oracle model are not proven. Canetti et al. [24] have shown that security in the random oracle model does not imply security in the real world, in that a scheme can be secure in the random oracle model and yet be broken without violating any particular intractability assumption, and without breaking the underlying hash functions.

Therefore, to design a provable secure ID-based generalized signcryption scheme in the standard model (without random oracles) remains an open and interesting research problem.

In this paper, we first proposed an ID-based generalized signcryption scheme in the standard model. Using the Paterson–Schuldt scheme [25], we give a concrete scheme. We also prove its semantic security under the hardness of the Decisional Bilinear Diffie–Hellman problem and its unforgeability under the computational Diffie–Hellman assumption.

2. Preliminaries

In this section, we briefly review the basic concepts on bilinear pairings and some related complexity assumptions.

2.1. Bilinear Pairings

Let

G_{1}

and

G_{2}

be two multiplicative cyclic groups of prime order q and let g be a generator of

G_{1}

. The map

e : G_{1} \times G_{1} \to G_{2}

is said to be an admissible bilinear pairing with the following properties:

Bilinearity: For all $u, v \in G_{1}$ , and $a, b \in Z_{q}$ , $e (u^{a}, v^{b}) = e {(u, v)}^{a b}$ .
Non-degeneracy: $e (g, g) \neq 1$ .
Computability: There exists an efficient algorithm to compute $e (u, v)$ for all $u, v \in G_{1}$ .

We note that the modified Weil and Tate pairings associated with supersingular elliptic curves are examples of such admissible pairings.

2.2. Complexity Assumptions

2.2.1. Decisional Bilinear Diffie–Hellman (DBDH) Problem

Given

g, g^{a}, g^{b}, g^{c} \in G_{1}

, for unknown

a, b, c \in Z_{q}^{*}

and

Z \in G_{2}

, decide whether

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

Defining the advantage ε of a polynomial algorithm

A

against the DBDH problem is

| Pr [A (g, g^{a}, g^{b}, g^{c}, e {(g, g)}^{a b c}) = 1] - Pr [A (g, g^{a}, g^{b}, g^{c}, Z) = 1] | \geq ε,

where the probability is over the randomly chosen

a, b, c

and the random bits consumed by

A

Definition 1.

The

(t, ε)

DBDH assumption holds if no t-time adversary has at least ε advantage in solving the DBDH problem.

2.2.2. Computational Diffie–Hellman (CDH) Problem

Given

g, g^{a}, g^{b} \in G_{1}

, for unknown

a, b \in Z_{q}^{*}

, compute

g^{a b}

The success probability δ of a polynomial algorithm

A

in solving the CDH problem is denoted as

S u c c_{A}^{C D H} = Pr [A (g, g^{a}, g^{b}) = g^{a b},] \geq δ

where the probability is over the randomly chosen

a, b

and the random bits consumed by

A

Definition 2.

The

(t, δ)

CDH assumption holds if no t-time adversary has at least δ in solving the CDH problem.

3. Formal Model of Identity-Based Generalized Signcryption Schemes

3.1. Generic Scheme

An identity based generalized signcryption scheme consists of the following four algorithms:

Setup: Given a security parameter k, the private key generator (PKG) generates system parameters $p a r a m s$ and a master key s. $p a r a m s$ is made public while s is kept secret.
Extract: Given an identity $I D$ , the PKG computes the corresponding private key $d_{I D}$ and transmits it to the $I D$ via a secure channel.
Generalized Signcrypt: Given the sender’s identity $I D_{A}$ and private key $d_{A}$ , the receiver’s identity $I D_{B}$ and a message m, the sender outputs the ciphertext σ.
Generalized Unsigncrypt: Given the sender’s identity $I D_{A}$ , the receiver’s identity $I D_{B}$ and private key $d_{B}$ and the ciphertext σ, the receiver with identity $I D_{B}$ outputs m or the symbol ⊥ if σ is an invalid ciphertext under $I D_{A}$ and $I D_{B}$ .

There is no special sender (or receiver) when we encrypt (or sign) a message using IDGSC. We denote the absence of sender (or receiver) by

I D_{Φ}

. If

I D_{B} = I D_{Φ}

, the IDGSC scheme becomes a signature scheme and output of the IDGSC is a signature of sender

I D_{A}

on the message m. If

I D_{A} = I D_{Φ}

, the IDGSC scheme becomes an encryption scheme and output of the IDGSC is merely an encryption of message m for receiver

I D_{B}

. If

I D_{A} \neq I D_{Φ}

and

I D_{B} \neq I D_{Φ}

, then IDGSC works as the signcryption scheme and output of IDGSC is the signcryption of message m for sender

I D_{A}

and receiver

I D_{B}

. Thus, the IDGSC scheme works in three models via signcryption mode, encryption mode and signature mode.

3.2. Security Model

According to Yu et al.’s scheme [21], the abilities of an adversary are formally modeled by queries issued by adversities. Each adversary may issue the following queries:

Private-Key-Extract: The adversary submits an identity, and the challenger responds with the private key of that identity.
Sign: The adversary submits a sender’s identity and a message, and the challenger responds with the signature of the signer on the message.
Verify: The adversary submits a signer’s identity and a message/signature pair, and the challenger responds with 1 if the signature is accepted and 0 otherwise.
Encrypt: The adversary submits a receiver’s identity and a message, and the challenger responds with the ciphertext on this message for the receiver.
Decrypt: The adversary submits a receiver’s identity and a ciphertext, and the challenger decrypts the ciphertext under the private key of the receiver and returns the corresponding plaintext.
Signcrypt: The adversary submits a sender’s and receiver’s identities and a message, and the challenger responds with the ciphertext under the sender’s private key and the receiver’s public key.
Unsigncrypt: The adversary submits a ciphertext and a receiver’s identity, and the challenger decrypts the ciphertext under the private key of the receiver and verifies that the resulting decryption is a valid message/signature pair under the public key of the decrypted identity. Then, the challenger returns the message.

The identity based generalized signcryption can work in three modes: encryption mode, signature mode and signcryption mode, denoted IDGSC-EN, IDGSC-SG and IDGSC-SC, respectively.

For the confidentiality, we define the following two games (Game 1 and Game 2) under IDGSC-EN and IDGSC-SC, respectively.

Game 1. Indistinguishability (IND)-(IDGSC-EN)-CCA2 Secure

Consider the following game played between a challenger

C

and an adversary

A

Initial: The challenger $C$ takes security parameters k and runs the Setup algorithm to generate system parameters $p a r a m s$ and the master key s. $C$ sends $p a r a m s$ to $A$ and keeps s secret.
Phase 1: The adversary $A$ can perform a polynomially bounded number of seven above types of queries. These queries may be made adaptively, i.e., each query may depend on the answers to the previous queries.
Challenge: The adversary $A$ decides when Phase 1 ends, and chooses two equal length plaintexts $m_{0}$ , $m_{1}$ and two identities $I D_{A} = I D_{Φ}, I D_{B} \neq I D_{Φ}$ on which to be challenged. The identity $I D_{B}$ should not appear in any private key extract queries in Phase 1. $C$ chooses randomly a bit b, encrypts $m_{b}$ and then sends the ciphertext σ to $A$ .
Phase 2: The adversary $A$ makes a polynomial number of queries adaptively again as in Phase 1 with the restriction that it cannot make private key extract queries on $I D_{B}$ and cannot make an unsigncrypt query on σ.
Guess: The adversary $A$ produces a bit $b^{'}$ and wins the game if $b^{'} = b$ .

The advantage of

A

is defined as

A d v_{I D G S C - E N}^{I N D - C C A 2} (A) = | 2 Pr [b^{'} = b] - 1 |

, where

Pr [b^{'} = b]

denotes the probability that

b^{'} = b

Definition 3 (Confidentiality-IDGSC-EN).

An IDGSC scheme is said to have the indistinguishability against chosen adaptive ciphertext attacks (IND-(IDGSC-EN)-CCA2) or semantic security if no polynomially bounded adversary has a non-negligible advantage in Game 1.

Game 2. IND-(IDGSC-SC)-CCA2 Secure

Consider the following game played between a challenger

C

and an adversary

A

Initial: The challenger $C$ takes security parameters k and runs the Setup algorithm to generate system parameters $p a r a m s$ and the master key s. $C$ sends $p a r a m s$ to $A$ and keeps s secret.
Phase 1: The adversary $A$ can perform a polynomially bounded number of the seven types of queries above. These queries may be made adaptively, i.e., each query may depend on the answers to the previous queries.
Challenge: The adversary $A$ decides when phase 1 ends, chooses two equal length plaintexts $m_{0}$ , $m_{1}$ and two identities $I D_{A} \neq I D_{Φ}, I D_{B} \neq I D_{Φ}$ on which to be challenged. The identity $I D_{B}$ should not appear in any private key extract queries in Phase 1. $C$ chooses randomly a bit b, encrypts $m_{b}$ and then sends the ciphertext σ to $A$ .
Phase 2: The adversary $A$ makes a polynomial number of queries adaptively again as in Phase 1 with the restriction that it cannot make private key extract queries on $I D_{B}$ and cannot make an unsigncrypt query on σ.
Guess: The adversary $A$ produces a bit $b^{'}$ and wins the game if $b^{'} = b$ .

The advantage of

A

is defined as

A d v_{I D G S C - S C}^{I N D - C C A 2} (A) = | 2 Pr [b^{'} = b] - 1 |

, where

Pr [b^{'} = b]

denotes the probability that

b^{'} = b

Definition 4 (Confidentiality-IDGSC-SC).

An IDGSC scheme is said to have the indistinguishability against adaptive chosen ciphertext attacks (IND-(IDGSC-SC)-CCA2) or semantic security if no polynomially bounded adversary has a non-negligible advantage in Game 2.

For the unforgeability, we define the following two games (Game 3 and Game 4) under IDGSC-SG and IDGSC-SC, respectively.

Game 3. EF-(IBGSC-SG)-Adaptive Chosen Message Attack (ACMA) Secure

Consider the following game played between a challenger

C

and an adversary

A

Initial: The challenger $C$ runs the Setup algorithm with a security parameter k and obtains system parameters $p a r a m s$ and the master secret key s. $C$ sends $p a r a m s$ to $A$ .
Queries: The adversary $A$ performs a polynomially bounded number of queries adaptively just like in Game 1.
Forgery: Finally, the adversary $A$ produces two identities $I D_{A} \neq I D_{Φ}, I D_{B} = I D_{Φ}$ and a ciphertext (signature) σ. The adversary wins the game if $I D_{A} \neq I D_{Φ}$ ; σ was a valid ciphertext (signature) on $m, I D_{A}$ ; no private key extract query was made on $I D_{A}$ ; σ did not result from signature query on $m, I D_{A}$ .

The advantage of

A

is defined as

A d v_{I D G S C - S G}^{E F - A C M A} (A) = Pr [A w i n s]

Definition 5 (Unforgeability-IDGSC-SG).

An IDGSC scheme is said to have the existential unforgeability against chosen adaptive message attacks (EF-(IDGSC-SG)-ACMA) if no polynomially bounded adversary has a non-negligible advantage in Game 3.

Game 4. EF-(IDGSC-SC)-ACMA Secure

Consider the following game played between a challenger

C

and an adversary

A

Initial: The challenger $C$ runs the Setup algorithm with a security parameter k and obtains system parameters $p a r a m s$ and the master secret key s. $C$ sends $p a r a m s$ to $A$ .
Queries: The adversary $A$ performs a polynomially bounded number of queries adaptively just like in Game 1.
Forgery: Finally, the adversary $A$ produces a new tuple $(σ, I D_{A}, I D_{B})$ . Let m be the result of unsigncryption σ under the private key of $I D_{B}$ . The adversary wins the game if $I D_{A} \neq I D_{Φ}, I D_{B} \neq I D_{Φ}$ ; no private key extract query was made on $I D_{A}$ ; σ is a valid signature under $m, I D_{A}$ ; $(σ, I D_{A}, I D_{B})$ was not output by a signcrypt query.

The advantage of

A

is defined as

A d v_{I D G S C - S C}^{E F - A C M A} (A) = Pr [A w i n s]

Definition 6 (Unforgeability-IDGSC-SC).

An IDGSC scheme is said to have the existential unforgeability against chosen adaptive message attacks (EF-(IDGSC-SC)-ACMA) if no polynomially bounded adversary has a non-negligible advantage in Game 4.

4. The Proposed Scheme

Our IDGSC scheme is described as the following algorithms.

Setup: Given a security parameter k, the PKG chooses groups $G_{1}$ and $G_{2}$ of prime order q, a generator g of $G_{1}$ , a admissible bilinear pairing $e : G_{1} \times G_{1} \to G_{2}$ , and hash functions $H : {0, 1}^{*} \to {0, 1}^{l}$ and $H_{m} : {0, 1}^{*} \to {0, 1}^{n_{m}}$ . The PKG chooses a random value $α \in Z_{q}^{*}$ , computes $g_{1} = g^{α}$ and selects $g_{2} \in G_{1}$ . Furthermore, the PKG computes $z = e (g_{1}, g_{2})$ and picks $u^{'}, m^{'} \in G_{1}$ and vectors $u = {u_{i}}$ , $m = {m_{i}}$ of length $n_{u}$ and $n_{m}$ , respectively, whose entries are random elements from $G_{1}$ . The system parameters are $p a r a m s = {G_{1}, G_{2}, e, p, g, g_{1}, g_{2}, H, H_{m}, z, u^{'}, m^{'}, u, m}$ and the master secret key $g_{2}^{α}$ .
Let $f (I D)$ be a special function, where $I D \in {0, 1}^{n_{u}}$ . If identity is vacant, that is $I D = I D_{Φ}$ , $f (I D) = 0$ , otherwise $f (I D) = 1$ .
Extract: Let $I D$ be a bit string of length $n_{u}$ , representing an identity and let $I D [i]$ be the i-th bit of $I D$ . Define $U_{I D} \subset {1, 2, \cdot \cdot \cdot, n_{u}}$ to be the set of indices i such that $I D [i] = 1$ . A private key $d_{I D}$ for identity $I D$ is generated as follows. The PKG picks $r_{I D} \in Z_{q}^{*}$ and computes

$d_{I D} = (d_{I D 1}, d_{I D 2}) = (g_{2}^{α} {(u^{'} \prod_{i \in U_{I D}} u_{i})}^{r_{I D}}, g^{r_{I D}}) .$

Therefore, the sender with identity $I D_{A}$ and the receiver with identity $I D_{B}$ private keys are

$d_{A} = (d_{A 1}, d_{A 2}) = (g_{2}^{α} {(u^{'} \prod_{i \in U_{A}} u_{i})}^{r_{A}}, g^{r_{A}}),$

$d_{B} = (d_{B 1}, d_{B 2}) = (g_{2}^{α} {(u^{'} \prod_{i \in U_{B}} u_{i})}^{r_{B}}, g^{r_{B}}) .$
Generalized Signcrypt: Suppose the sender A with identity I D A wants to send a message m ∈ { 0 , 1 } l to the receiver B with identity I D B , A picks randomly r ∈ Z q * and does the following:
- Compute $σ_{1} = g^{r}$ .
- Compute $w = z^{r f (I D_{B})}$ .
- Compute $c = m \oplus H (w)$ .
- Compute $σ_{2} = {(d_{A 2})}^{f (I D_{A})}$ .
- Compute $σ_{3} = {(u^{'} \prod_{i \in U_{B}} u_{i})}^{r f (I D_{B})}$ .
- Compute $π = H_{m} (m, σ_{1}, σ_{2}, σ_{3}, w)$ . Here π is an $n_{m}$ bit string and $π [j]$ denotes the j-th bit of π, and $M \subset {1, 2, \cdot \cdot \cdot, n_{m}}$ denotes the set of j for which $π [j] = 1$ .
- Compute $σ_{4} = {(d_{A 1})}^{f (I D_{A})} \cdot σ_{3} \cdot {(m^{'} \prod_{j \in M} m_{j})}^{r}$ .
The ciphertext is $σ = (σ_{1}, σ_{2}, σ_{3}, σ_{4}, c)$ .
Generalized Unsigncrypt: When receiving σ, the receiver with identity I D B follows the steps below:
- Compute $f (I D_{B})$ .
- Compute $w = e (d_{B 1}, σ_{1}^{f (I D_{B})}) \cdot e {(d_{B 2}, σ_{3})}^{- 1}$ .
- Compute $m = c \oplus H (w)$ .
- Compute $π = H_{m} (m, σ_{1}, σ_{2}, σ_{3}, w)$ and generate the corresponding set M, the set of all j for which $π [j] = 1$ .
- Accepted the message if and only if the following equality holds:
  
  $e (σ_{4}, g) = e {(g_{2}, g_{1})}^{f (I D_{A})} e (u^{'} \prod_{i \in U_{A}} u_{i}, σ_{2}) e {(u^{'} \prod_{i \in U_{B}} u_{i}, σ_{1})}^{f (I D_{B})} e (m^{'} \prod_{j \in M} m_{j}, σ_{1}) .$

Remark 1.

Our Setup, Extract algorithm in our scheme is from the existing work, i.e., Paterson–Schuldt’s scheme [25]. However, our Setup algorithm has some differences from [25], and we added some parameters: H and

H_{m}

. Other algorithms such as Generalized Signcrypt and Generalized Unsigncrypt are new designs.

5. Analysis

5.1. Correctness

\begin{matrix} \frac{e (d_{B 1}, σ_{1}^{f (I D_{B})})}{e (d_{B 2}, σ_{3})} = \frac{e (g_{2}^{α} {(u^{'} \prod_{i \in U_{B}} u_{i})}^{r_{B}}, g^{r f (I D_{B})})}{e (g^{r_{B}}, {(u^{'} \prod_{i \in U_{B}} u_{i})}^{r f (I D_{B})})} = \frac{e (g_{2}^{α}, g^{r f (I D_{B})}) e ({(u^{'} \prod_{i \in U_{B}} u_{i})}^{r_{B}}, g^{r f (I D_{B})})}{e (g^{r_{B}}, {(u^{'} \prod_{i \in U_{B}} u_{i})}^{r f (I D_{B})})} = e {(g_{1}, g_{2})}^{r f (I D_{B})} \end{matrix}

\begin{matrix} e (σ_{4}, g) & = e ((g_{2}^{α f (I D_{A})} \cdot {(u^{'} \prod_{i \in U_{A}} u_{i})}^{r_{A} f (I D_{A})} \cdot {(u^{'} \prod_{i \in U_{B}} u_{i})}^{r f (I D_{B})} \cdot {(m^{'} \prod_{j \in M} m_{j})}^{r}, g)) \\ = e (g_{2}^{α f (I D_{A})}, g) e ((u^{'} \prod_{i \in U_{A}} u_{i})^{r_{A} f (I D_{A})}, g)) e (({(u^{'} \prod_{i \in U_{B}} u_{i})}^{r f (I D_{B})}, g)) e (({(m^{'} \prod_{j \in M} m_{j})}^{r}, g)) \\ = e {(g_{2}, g_{1})}^{f (I D_{A})} e (u^{'} \prod_{i \in U_{A}} u_{i}, g^{r_{A} f (I D_{A})}) e (u^{'} \prod_{i \in U_{B}} u_{i}, g^{r f (I D_{B})}) e (m^{'} \prod_{j \in M} m_{j}, g^{r}) \\ = e {(g_{2}, g_{1})}^{f (I D_{A})} e (u^{'} \prod_{i \in U_{A}} u_{i}, σ_{2}) e {(u^{'} \prod_{i \in U_{B}} u_{i}, σ_{1})}^{f (I D_{B})} e (m^{'} \prod_{j \in M} m_{j}, σ_{1}) . \end{matrix}

There are three cases to be considered.

Case 1. In the IDGSC-SC Model

In this case, there is

I D_{A} \neq I D_{Φ}, I D_{B} \neq I D_{Φ}

, so

f (I D_{A}) = f (I D_{B}) = 1

. The generalized signcryption scheme in signcryption model is as follows:

Signcrypt:
- Compute $σ_{1} = g^{r}$ .
- Compute $w = z^{r}$ .
- Compute $c = m \oplus H (w)$ .
- Compute $σ_{2} = d_{A 2}$ .
- Compute $σ_{3} = {(u^{'} \prod_{i \in U_{B}} u_{i})}^{r}$ .
- Compute $π = H_{m} (m, σ_{1}, σ_{2}, σ_{3}, w)$ . Here π is an $n_{m}$ bit string and $π [j]$ denotes the j-th bit of π, and $M \subset {1, 2, \cdot \cdot \cdot, n_{m}}$ denotes the set of j for which $π [j] = 1$ .
- Compute $σ_{4} = d_{A 1} \cdot σ_{3} \cdot {(m^{'} \prod_{j \in M} m_{j})}^{r}$ .
The ciphertext is $σ = (σ_{1}, σ_{2}, σ_{3}, σ_{4}, c)$ .
Unsigncrypt:
- Compute $w = e (d_{B 1}, σ_{1}) \cdot e {(d_{B 2}, σ_{3})}^{- 1}$ .
- Compute $m = c \oplus H (w)$ .
- Compute $π = H_{m} (m, σ_{1}, σ_{2}, σ_{3}, w)$ and generate the corresponding set M, the set of all j for which $π [j] = 1$ .
- Accepted the message if and only if the following equality holds:
  
  $e (σ_{4}, g) = e (g_{2}, g_{1}) e (u^{'} \prod_{i \in U_{A}} u_{i}, σ_{2}) e (u^{'} \prod_{i \in U_{B}} u_{i}, σ_{1}) e (m^{'} \prod_{j \in M} m_{j}, σ_{1}) .$

Case 2. In the IDGSC-SG Model

In this case, there is

I D_{A} \neq I D_{Φ}, I D_{B} = I D_{Φ}

, so

f (I D_{A}) = 1, f (I D_{B}) = 0

. The generalized signcryption scheme in the signature model is as follows:

Sign:
- Compute $σ_{1} = g^{r}$ .
- Compute $w = z^{r f (I D_{B})} = 1$ .
- Compute $c = m \oplus H (w)$ .
- Compute $σ_{2} = {(d_{A 2})}^{f (I D_{A})} = d_{A 2}$ .
- Compute $σ_{3} = {(u^{'} \prod_{i \in U_{B}} u_{i})}^{r f (I D_{B})} = 1$ .
- Compute $π = H_{m} (m, σ_{1}, σ_{2}, σ_{3}, w)$ . Here π is an $n_{m}$ bit string and $π [j]$ denotes the j-th bit of π , and $M \subset {1, 2, \cdot \cdot \cdot, n_{m}}$ denotes the set of j for which $π [j] = 1$ .
- Compute $σ_{4} = d_{A 1} \cdot σ_{3} \cdot {(m^{'} \prod_{j \in M} m_{j})}^{r}$ .
The signature is $σ = (σ_{1}, σ_{2}, σ_{3}, σ_{4}, c \oplus H (w)) = (σ_{1}, σ_{2}, σ_{3}, σ_{4}, m)$ .
Verify:
- Compute $π = H_{m} (m, σ_{1}, σ_{2}, σ_{3}, w)$ and generate the corresponding set M, the set of all j for which $π [j] = 1$ .
- Accepted the signature if and only if the following equality holds:
  
  $e (σ_{4}, g) = e (g_{2}, g_{1}) e (u^{'} \prod_{i \in U_{A}} u_{i}, σ_{2}) e (u^{'} \prod_{i \in U_{B}} u_{i}, σ_{1}) e (m^{'} \prod_{j \in M} m_{j}, σ_{1}) .$

Case 3. In the IDGSC-EN Model

In this case, there is

I D_{A} = I D_{Φ}, I D_{B} \neq I D_{Φ}

, so

f (I D_{A}) = 0, f (I D_{B}) = 1

. The generalized signcryption scheme in the encryption model as follows:

Encrypt:
- Compute $σ_{1} = g^{r}$ .
- Compute $w = z^{r f (I D_{B})} = z^{r}$ .
- Compute $c = m \oplus H (w)$ .
- Compute $σ_{2} = {(d_{A 2})}^{f (I D_{A})} = 1$ .
- Compute $σ_{3} = {(u^{'} \prod_{i \in U_{B}} u_{i})}^{r f (I D_{B})} = {(u^{'} \prod_{i \in U_{B}} u_{i})}^{r}$ .
- Compute $π = H_{m} (m, σ_{1}, σ_{2}, σ_{3}, w)$ . Here π is an $n_{m}$ bit string and $π [j]$ denotes the j-th bit of $π [j]$ , and $M \subset {1, 2, \cdot \cdot \cdot, n_{m}}$ denotes the set of j for which $π [j] = 1$ .
- Compute $σ_{4} = {(d_{A 1})}^{f (I D_{A})} \cdot σ_{3} \cdot {(m^{'} \prod_{j \in M} m_{j})}^{r} = {(u^{'} \prod_{i \in U_{B}} u_{i})}^{r} \cdot {(m^{'} \prod_{j \in M} m_{j})}^{r}$ .
The ciphertext is $σ = (σ_{1}, σ_{2}, σ_{3}, σ_{4}, c)$ .
Decrypt:
- Compute $w = e (d_{B 1}, σ_{1}) \cdot e {(d_{B 2}, σ_{3})}^{- 1}$ .
- Compute $m = c \oplus H (w)$ .
- Compute $π = H_{m} (M, σ_{1}, σ_{2}, σ_{3}, w)$ and generate the corresponding set M, the set of all j for which $π [j] = 1$ .
- Accepted the message if and only if the following equality holds:
  
  $e (σ_{4}, g) = e (u^{'} \prod_{i \in U_{B}} u_{i}, σ_{1}) e (m^{'} \prod_{j \in M} m_{j}, σ_{1}) .$

5.2. Security Proof

Theorem 1.

(Confidentiality in the IDGSC-EN model) Assume there is an adversary IND (IBGSC-EN) CCA2

A

that is able to distinguish two valid ciphertexts during the defined in Game 1 with an advantage ε when running in a time t, then there exists an algorithm

D

that can break Waters’ identity based encryption scheme in a time

t^{'} = t

with an advantage

ε^{'} = ε

Proof.

When the IDGSC scheme works as an encryption scheme, it is a actually the identity based encryption proposed by Waters [26] and one-time signature. Owing to the theorem proposed by Canetti et al. [27], this scheme is secure against the normal adaptive chosen-ciphertext attack. Considering the signcrypt/unsigncrypt query, the adversary cannot transform the target encryption ciphertext into a valid signcryption ciphertext. This conclusion is based on the EF-ACMA security of PS. So IDGSC scheme in encryption model is IND-CCA2 secure. Thus, the theorem follows. ☐

Theorem 2.

(Confidentiality in the IDGSC-SC model). Assume there is an adversary IND (IDGSC-SC) CCA2

A

that is able to distinguish two valid ciphertexts during the defined in Game 2 with an advantage ε when running in a time t and making at most

q_{k}

private key extract queries,

q_{s}

sign queries,

q_{v}

verify queries,

q_{e}

encrypt queries,

q_{d}

decrypt queries,

q_{s c}

signcrypt queries and

q_{u s}

unsigncrypt queries. Then, there exists a distinguisher that can solve an instance of the DBDH problem in a time

t^{'} = t + (5 q_{k} + 2 q_{s} + 4 q_{e} + 4 q_{s c}) t_{e} + (4 q_{d} + 7 q_{u s} + 4 q_{v}) t_{p}

with an advantage

ε^{'} = \frac{ε}{8 (q_{k} + q_{d} + q_{s} + q_{s c} + q_{u s}) (n_{u} + 1) q_{s c} (n_{m} + 1)}

, where

t_{e}

denotes the time of an exponentiation in

G_{1}

and

t_{p}

denotes the time of a pairing in

(G_{1}, G_{2})

Proof.

Assume that there is a polynomially bounded adversary

A

that is able to break the semantic security of our scheme. Then, there exists a distinguisher

D

that can decide whether

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

or not with a non-negligible advantage when receiving a random instance

g, g^{a}, g^{b}, g^{c}, Z

D

runs

A

as the subroutine and acts as the challenger in Game 2 and interacts with

A

as described below. ☐

Initial. D chooses randomly as follows:
- Two integers $0 ⩽ l_{u} ⩽ q$ and $0 ⩽ l_{m} ⩽ q$ .
- Two integers $0 ⩽ k_{u} ⩽ n_{u}$ and $0 ⩽ k_{m} ⩽ n_{m}$ ( $l_{u} (n_{u} + 1) < q$ , $l_{m} (n_{m} + 1) < q$ ).
- An integer $x^{'} \in Z_{l_{u}}$ and $n_{u}$ -dimensional vector $(x_{1}, \cdot \cdot \cdot, x_{n_{u}}) \in Z_{l_{u}}$ .
- An integer $y^{'} \in Z_{l_{m}}$ and $n_{m}$ -dimensional vector $(y_{1}, \cdot \cdot \cdot, y_{n_{m}}) \in Z_{l_{m}}$ .
- An integer $z^{'} \in Z_{q}$ and $n_{u}$ -dimensional vector $(z_{1}, \cdot \cdot \cdot, z_{n_{u}}) \in Z_{q}$ .
- An integer $ω^{'} \in Z_{q}$ and $n_{m}$ -dimensional vector $(ω_{1}, \cdot \cdot \cdot, ω_{n_{m}}) \in Z_{q}$ .
To make the notation easy to follow, we define four functions:

$F (I D) = x^{'} + \sum_{i \in U} x_{i} - l_{u} k_{u}, J (I D) = z^{'} + \sum_{i \in U} z_{i},$

$K (M) = y^{'} + \sum_{i \in M} y_{i} - l_{m} k_{m}, L (M) = ω^{'} + \sum_{i \in M} ω_{i} .$
D sets system parameters as follows:
- $g_{1} = g^{a}$ and $g_{2} = g^{b}$ .
- $u^{'} = g_{2}^{- l_{u} k_{u} + x^{'}} g^{z^{'}}$ and $u_{i} = g_{2}^{x_{i}} g^{z_{i}}$ ( $1 ⩽ i ⩽ n_{u}$ ), which means that, for any identity $I D$ , we have $u^{'} \prod_{i \in U_{I D}} u_{i} = g_{2}^{F (I D)} g^{J (I D)}$ .
- $m^{'} = g_{2}^{- l_{m} k_{m} + y^{'}} g^{ω^{'}}$ and $m_{i} = g_{2}^{y_{i}} g^{ω_{i}}$ ( $1 ⩽ i ⩽ n_{m}$ ), which means that, for any π, we have $m^{'} \prod_{i \in M} m_{i} = g_{2}^{K (π)} g^{L (π)}$ .
Finally, D returns all parameters to A . We can see that all distributions are identical to that in the real world.
Phase 1. D answers the queries as follows:
–
Private key extract queries: When the adversary $A$ issues a private key extract query on an identity $I D$ , $D$ acts as follows:
If $F (I D) = 0 mod l_{u}$ , $D$ aborts and reports failure.
If $F (I D) \neq 0 mod l_{u}$ , $D$ can construct a private key by picking a random $r_{I D} \in Z_{q}^{*}$ and computing:

$d_{I D} = (d_{I D 1}, d_{I D 2}) = (g_{1}^{- \frac{J (I D)}{F (I D)}} {(g_{2}^{F (I D)} g^{J (I D)})}^{r_{I D}}, g_{1}^{- \frac{1}{F (I D)}} g^{r_{I D}}) .$
–
Encrypt queries: At any time, the adversary $A$ can perform an encrypt query on a plaintext m for the receiver $I D_{B}$ , and $D$ runs the encrypt algorithm in the encryption model to answer $A$ ’s query.
–
Decrypt queries: At any time, the adversary $A$ can perform a decrypt query on a ciphertext σ for the receiver $I D_{B}$ , and $D$ acts as follows:
If $F (I D_{B}) = 0 mod l_{u}$ , $D$ aborts and reports failure.
If $F (I D_{B}) \neq 0 mod l_{u}$ , $D$ first obtains the private key for $I D_{B}$ as he does in response to the private key extract query, and then runs a decrypt algorithm in the encryption model to answer $A$ ’s query.
–
Sign queries: At any time, the adversary $A$ can perform a sign query on a message m for the sender $I D_{A}$ , $D$ acts as follows:
If $F (I D_{A}) = 0 mod l_{u}$ , $D$ aborts and reports failure.
If $F (I D_{A}) \neq 0 mod l_{u}$ , $D$ first obtains the private key for $I D_{A}$ as he does in response to the private key extract query, and then runs a sign algorithm in the signature model to answer $A$ ’s query.
–
Verify queries: At any time, the adversary $A$ can perform a verify query on a message/signature pair $(m, σ)$ for the sender $I D_{A}$ , and $D$ runs a verify algorithm in the signature model to answer $A$ ’s query.
–
Signcrypt queries: At any time, the adversary $A$ can perform a signcrypt query on a plaintext m for the sender identity $I D_{A}$ and the receiver identity $I D_{B}$ , and $D$ acts as follows:
If $F (I D_{A}) = 0 mod l_{u}$ , $D$ aborts and reports failure.
If $F (I D_{A}) \neq 0 mod l_{u}$ , $D$ first obtains the private key for $I D_{A}$ as he does in response to the private key extract query, and then runs the signcrypt algorithm in the signcryption model to answer $A$ ’s query.
–
Unsigncrypt queries: At any time, the adversary $A$ can perform an unsigncrypt query on a ciphertext σ for the sender identity $I D_{A}$ and the receiver identity $I D_{B}$ , and $D$ acts as follows:
If $F (I D_{B}) = 0 mod l_{u}$ , $D$ aborts and reports failure.
If $F (I D_{B}) \neq 0 mod l_{u}$ , $D$ first obtains the private key for $I D_{B}$ as he does in response to the private key extract query, and then runs the unsigncrypt algorithm in the signcryption model to answer $A$ ’s query.
Challenge. After a polynomially bounded number of queries, the adversary $A I D_{A}^{*}, I D_{B}^{*}$ on which he wishes to be challenged. Note that $D$ fails if $A$ has made a private key extract query on $I D_{B}^{*}$ during Phase 1. Then, $A$ submits two messages $m_{0}, m_{1} \in {0, 1}^{l}$ and $I D_{A}^{*}, I D_{B}^{*}$ to $D$ . $D$ will abort if $F (I D_{B}^{*}) \neq 0 mod l_{u}$ . Otherwise, $D$ flips a fair binary coin $γ \in {0, 1}$ and constructs ciphertext $m_{γ}$ as follows.
$D$ randomly chooses a number $r^{*} \in Z_{q}^{*}$ and computes

$π_{γ}^{*} = H (m_{γ}, g^{c}, g_{1}^{- \frac{1}{F (I D_{A}^{*})}} g^{I D_{A}^{*}}, {(g^{c})}^{J (I D_{B}^{*})}, m_{γ} \oplus H (Z)) .$

$M_{γ}^{*}$ denoted the set of 1 for which $π_{γ}^{*} [j] = 1$ . If $K (M_{γ}^{*}) \neq 0 mod q$ , $D$ aborts. Otherwise, $D$ sets the ciphertext as:

$σ^{*} = (g^{c}, g_{1}^{- \frac{1}{F (I D_{A}^{*})}} g^{I D_{A}^{*}}, {(g^{c})}^{J (I D_{B}^{*})}, g_{1}^{- \frac{J (I D_{A}^{*})}{F (I D_{A}^{*})}} {(g_{2}^{F (I D_{A}^{*})} g^{J (I D_{A}^{*})})}^{r^{*}} {(g^{c})}^{J (I D_{B}^{*})} {(g^{c})}^{L (π_{γ}^{*})}) .$
Phase 2. The adversary $A$ then performs a second series of queries which are treated in the same as Phase 1. It is not allowed to make the private key extract query on $I D_{B}^{*}$ and an unsigncrypt query on $σ^{*}$ under $I D_{B}^{*}$ .
Guess. At the end of the simulations, the adversary $A$ outputs a guess $γ^{'}$ . If $γ^{'} = γ$ , $D$ answers 1, indicating that $Z = e {(g, g)}^{a b c}$ ; otherwise, $D$ answers 0 to the DBDH problem.

This completes the description of simulation. Analyzing the probability of

D

not aborting still needs to be analyzed.

D

will not abort if all the following conditions are fulfilled:

$F (I D) \neq 0 mod l_{u}$ during the private key extract queries.
$F (I D_{B}) \neq 0 mod l_{u}$ during the decrypt queries.
$F (I D_{A}) \neq 0 mod l_{u}$ during the sign queries.
$F (I D_{A}) \neq 0 mod l_{u}$ during the signcrypt queries.
$F (I D_{B}) \neq 0 mod l_{u}$ during the unsigncrypt queries.
$F (I D_{B}^{*}) = 0 mod q$ and $K (M_{γ}^{*}) = 0 mod q$ during the challenge phase.

Let

I D_{1}, \cdot \cdot \cdot, I D_{q_{I D}}

be the identity appearing in all queries not involving the challenge identity. Clearly, we will have

q_{I D} ⩽ q_{k} + q_{d} + q_{s} + q_{s c} + q_{u s}

. Define the following events:

$A_{i}$ : $F (I D_{i}) \neq 0 mod l_{u}$ where $i = 1, \cdot \cdot \cdot, q_{I D}$ .
$B$ : $F (I D_{B}^{*}) = 0 mod q$ .
$C$ : $K (M_{γ}^{*}) = 0 mod q$ .

The success probability of

D

Pr [\neg a b o r t] = Pr [Λ_{i = 1}^{q_{I D}} A_{i} \land B \land C]

The functions F and K are selected independently; therefore, the events

(\land_{i = 1}^{q_{I D}} A_{i} \land B)

and

C

are independent. According to

l_{u} (n_{u} + 1) < q

, it is easy to see that

F (u) = 0 mod q \Rightarrow F (u) = 0 mod l_{u}

. Furthermore, this implies that, if

F (u) = 0 mod l_{u}

, there will be a unique

k_{u}

with

0 ⩽ k_{u} ⩽ n_{u},

such that

F (u) = 0 mod q

. For the randomness of

k_{u}, x^{'}, x_{1}, \cdot \cdot \cdot, x_{n_{u}}

, we have

\begin{matrix} Pr [B] & = Pr [F (I D_{B}^{*}) = 0 mod q] \\ = Pr [F (I D_{B}^{*}) = 0 mod l_{u}] Pr [F (I D_{B}^{*}) = 0 mod q | F (I D_{B}^{*}) = 0 mod l_{u}] \\ = (\frac{1}{l_{u}} \frac{1}{n_{u} + 1}) . \end{matrix}

On the other hand, for any i, the event

A_{i}

and

B

are independent, so we have

\begin{matrix} Pr [\land_{i = 1}^{q_{I D}} A_{i} \land B] & = Pr [B] Pr [\land_{i = 1}^{q_{I D}} A_{i} | B] = Pr [B] (1 - Pr [\lor_{i = 1}^{q_{I D}} \neg A_{i} | B]) \\ ⩾ Pr [B] (1 - \sum_{i = 1}^{q_{I D}} Pr [\neg A_{i} | B]) = (\frac{1}{l_{u} (n_{u} + 1)}) (1 - \frac{q_{I D}}{l_{u}}) . \end{matrix}

Similarly, we have

Pr [C] = Pr [K (M_{γ}^{*}) = 0 mod q] = \frac{1}{l_{m}} \frac{1}{n_{m} + 1}

Let

l_{u} = 2 (q_{k} + q_{d} + q_{s} + q_{s c} + q_{u s})

and

l_{m} = 2 q_{s c}

. Then, we have

\begin{matrix} Pr [\neg a b o r t] & = Pr [\land_{i = 1}^{q_{I D}} A_{i} \land B \land C] = (\frac{1}{l_{u} (n_{u} + 1)}) (1 - \frac{q_{I D}}{l_{u}}) (\frac{1}{l_{m}} \frac{1}{n_{m} + 1}) \\ = \frac{1}{8 (q_{k} + q_{d} + q_{s} + q_{s c} + q_{u s}) (n_{u} + 1) q_{s c} (n_{m} + 1) .} \end{matrix}

If the simulation does not abort, the adversary

A

will win Game 2 with the advantage at least ε. Thus,

D

can solve for the DBDH problem instance with the advantage

ε^{'} = \frac{ε}{8 (q_{k} + q_{d} + q_{s} + q_{s c} + q_{u s}) (n_{u} + 1) q_{s c} (n_{m} + 1)}

Algorithm

D

’s running time is the same as

A

’s running time plus the time it takes to respond to

q_{k}

private key extract queries,

q_{s}

sign queries,

q_{v}

verify queries,

q_{e}

encrypt queries,

q_{d}

decrypt queries,

q_{s c}

signcrypt queries and

q_{u s}

unsigncrypt queries. Each private key extract query requires five exponentiation operations in

G_{1}

. Each sign query needs two exponentiation operations in

G_{1}

. Each verify query needs four pairing operations in

(G_{1}, G_{2})

. Each encrypt query needs four exponentiation operations in

G_{1}

. Each decrypt query needs four pairing operations in

(G_{1}, G_{2})

. Each signcrypt query requires four exponentiation operations in

G_{1}

. Each unsigncrypt query requires seven pairing operations in

(G_{1}, G_{2})

. If we assume each that exponentiation takes time

t_{e}

and each pairing takes time

t_{p}

, the total running time is at most

t + (5 q_{k} + 2 q_{s} + 4 q_{e} + 4 q_{s c}) t_{e} + (4 q_{d} + 7 q_{u s} + 4 q_{v}) t_{p}

. Thus, the theorem follows.

Theorem 3.

(Unforgeability in the IDGSC-SG Model) Assuming that there is an adversary EF (IDGSC-SG) ACMA

A

that breaks our scheme with the probability δ when running in a time t, then there exists an algorithm

B

that can forge a valid signature of Paterson–Schuldt in a time

t^{'} = t

with the probability

δ^{'} = δ

Proof.

When the IDGSC scheme works as a signature scheme, it is actually the identity based signature proposed by Paterson and Schuldt [25]. This signature scheme itself is EF-ACMA secure. Considering the signcrypt/unsigncrypt query that is absent in the normal signature scheme, these queries are useless to the adversary of EF-(IDGSC-SG)-ACMA. The identities of sender and receiver are included in the signature. Hence, an adversary can break the Paterson and Schuldt scheme if he can break our scheme in the signature model. Then, the theorem follows. ☐

Theorem 4.

(Unforgeability in the IDGSC-SC Model) Assume that there is an adversary EF (IDGSC-SC) ACMA

A

that breaks our scheme with the probability δ when running in a time t and making at most

q_{k}

private key extract queries,

q_{s}

sign queries,

q_{v}

verify queries,

q_{e}

encrypt queries,

q_{d}

decrypt queries,

q_{s c}

signcrypt queries and

q_{u c}

unsigncrypt queries. Then, there exists a algorithm

B

that can solve an instance of the CDH problem in a time

t^{'} = t + (5 q_{k} + 2 q_{s} + 4 q_{e} + 4 q_{s c}) t_{e} + (4 q_{d} + 7 q_{u s} + 4 q_{v}) t_{p}

with the probability

δ^{'} = \frac{δ}{16 {(q_{k} + q_{d} + q_{s} + q_{s c} + q_{u s})}^{2} {(n_{u} + 1)}^{2} q_{s c} (n_{m} + 1)}

, where

t_{e}

denotes the time of an exponentiation in

G_{1}

and

t_{p}

denotes the time of a pairing in

(G_{1}, G_{2})

Proof.

Assume that there is a polynomially bounded adversary

A

that is able to break the unforgeability of our scheme. Then, there exists an algorithm

B

that can compute

g^{a b}

with a non-negligible advantage when receiving a random CDH problem instance

(g, g^{a}, g^{b})

B

runs

A

as the subroutine and acts as the challenger in Game 4 and interacts with

A

as described below. ☐

Initial: $B$ sets the system parameter using the initial phase described in Theorem 1. Note that $B$ assigns $g_{1} = g^{a}$ and $g_{2} = g^{b}$ .
Queries: $A$ can perform a polynomially bounded number of queries including private key extract queries, sign queries, verify queries, encrypt queries, decrypt queries, signcrypt queries and unsigncrypt queries. $B$ answers the adversary $A$ in the same way as that of Theorem 2.
Forgery: Finally, A outputs a forgery ciphertext σ * = ( σ 1 * , σ 2 * , σ 3 * , σ 4 * , c * ) on the message m * under the receivers I D B * and the sender I D A * such that
- $σ^{*}$ is a valid ciphertext.
- $I D_{A}^{*}$ has not been submitted as one of the private key extract queries.
- $m^{*}$ has not been submitted as one of the signcrypt queries under the $I D_{A}^{*}, I D_{B}^{*}$ .

Now,

B

can unsigncrypt

σ^{*}

and obtain

m^{*}

under the

I D_{A}^{*}, I D_{B}^{*}

B

computes

π^{*} = H_{m} (m^{*}, σ_{1}^{*}, σ_{2}^{*}, σ_{3}^{*}, w^{*})

and generates

M^{*}

, the set of all i for which

π^{*} [j] = 1

. If

F (I D_{A}^{*}) \neq 0 mod q

F (I D_{B}^{*}) \neq 0 mod q

and

K (π^{*}) \neq 0 mod q

B

will abort. Otherwise,

F (I D_{A}^{*}) = 0 mod q

F (I D_{B}^{*}) = 0 mod q

and

K (π^{*}) = 0 mod q

B

can obtain the following case:

\begin{matrix} e (σ_{4}^{*}, g) = e (g_{2}, g_{1}) e (u^{'} \prod_{i \in U_{A}^{*}} u_{i}, σ_{2}^{*}) e (u^{'} \prod_{i \in U_{B}^{*}} u_{i}, σ_{1}^{*}) e (m^{'} \prod_{j \in M^{*}} m_{j}, σ_{1}^{*}) \\ = e (g^{a}, g^{b}) e (g^{J (I D_{A}^{*})}, σ_{2}^{*}) e (g^{J (I D_{B}^{*})}, σ_{1}^{*}) e (g^{L (π^{*})}, σ_{1}^{*}) . \end{matrix}

Thus, we have

g^{a b} = \frac{σ_{4}^{*}}{{(σ_{1}^{*})}^{J (I D_{B}^{*})} {(σ_{2}^{*})}^{J (I D_{A}^{*})} {(σ_{1}^{*})}^{L (π^{*})}}

, which is the solution to the given CDH problem.

Analogous to Theorem 1, we can obtain that

B

solves for the CDH problem instance with the probability

δ^{'} = \frac{δ}{16 {(q_{k} + q_{d} + q_{s} + q_{s c} + q_{u s})}^{2} {(n_{u} + 1)}^{2} q_{s c} (n_{m} + 1)}

, with time being

t^{'} = t + (5 q_{k} + 2 q_{s} + 4 q_{e} + 4 q_{s c}) t_{e} + (4 q_{d} + 7 q_{u s} + 4 q_{v}) t_{p}

. Thus, the theorem follows.

5.3. Efficiency

We compare the efficiency and security of our scheme with those of three identity based generalized signcryption schemes, including Lal et al.’s scheme [20], Yu et al.’s scheme [21] and Kushwah et al.’s scheme [22]. We denote the modular exponentiation and the pairing computation by E, P, respectively. Other operations are omitted in the following analysis since their computation cost is trivial. We consider the pre-computation here and do not take hash function evaluations into account.

To compare the computation cost of related schemes, we compute the execution time of the cryptographic operations above using MIRACL [28], which is a famous cryptographic library and has been widely used to implement cryptographic operations in many environments. Our hardware platform consists of an Intel I7-4770 processor with 3.40 GHz clock frequency, 4 gigabytes memory and runs the Windows 7 operating system. A bilinear pairing P operation needs 4.211 milliseconds and a modular exponentiation E operation needs 1.709 milliseconds.

We summarize the comparisons of the four schemes in Table 1. The Generalized Signcrypt column and the Generalized Unsigncrypt column demonstrate the computational costs of each identity based generalized signcryption scheme. The Security Model column specifies the security model that the schemes rely on, where RO and SM represent Random Oracle and Standard Model, respectively.

From Table 1, in Generalized Signcrypt, the computation cost of our scheme is less than Lal et al.’s scheme [20] and Yu et al.’s scheme [21] and more than Kushwash et al.’s scheme [22]. Our scheme has slightly higher computation costs than other schemes [20,21,22] in Generalized Unsigncrypt, whereas our scheme is proven secure in the standard model. To the best of our knowledge, it is the first scheme that is proven secure in the standard model. All previous schemes mentioned above have proven their security on the random oracle model. For some special applications that require very high security, it is believed that only those schemes that can be proven in the standard model must be employed. Thus, our scheme is suitable for secure e-mail and electronic commerce, where the confidentiality and authenticity are simultaneously or separately required to enable a secure and trustable communication environment.

6. Conclusions

The main purpose of identity based generalized signcryption is to reduce implementation complexity. According to different application environments, identity based generalized signcryption can fulfill the function of identity based signature, encryption or signcryption, respectively. In this paper, we proposed a concrete, ID-based generalized signcryption scheme based on the Paterson–Schuldt scheme. To the best of our knowledge, this is the first ID-based generalized signcryption scheme that can be proven secure in the standard model.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No. 61202438), the Key Project of Industry Science and Technology of Shaanxi Province (Nos. 2015GY021, 2015GY014) and the Project of Technology Transfer Promoting Engineering of Xi’an City (No. CXY1437(10)).

Author Contributions

Y. Ming conceived and designed the generalized signcryption scheme; X. Shen provided the secure proof and completed the paper writing; J. Feng performed the experiments and numerical analysis. All authors have read and approved the final manuscript.

Conflicts of Interest

The authors declare no conflict of interest.

References

Zheng, Y. Digital signcryption or how to achieve cost(signature & encryption) ≪ cost(signature) + cost(encryption). In Proceedings of the Advances in Cryptology-Crypto’97, LNCS 1294, Santa Barbara, CA, USA, 17–21 August 1997.
Linn, J. Privacy Enhancement for Internet Electronic Mail: Part I: Message Encryption and Authentication Procedures. Available online: https://www.rfc-editor.org/rfc/pdfrfc/rfc1421.txt.pdf (accessed on 14 March 2017).
Zheng, Y.; Imai, H. How to construct efficient signcryption schemes on elliptic curves. Inf. Process. Lett. 1998, 68, 227–233. [Google Scholar] [CrossRef]
Bao, F.; Deng, R.H. A signcryption scheme with signature directly verifiable by public key. In Proceedings of the Public Key Cryptography-PKC’98, LNCS 1431, Yokohama, Japan, 5–6 February1998; pp. 55–59.
Malone-Lee, J.; Mao, W. Two birds one stone: Signcryption using RSA. In Proceedings of the Topics in Cryptology-CT-RSA’03, LNCS 2612, San Francisco, CA, USA, 13–17 April 2003; pp. 210–224.
Shamir, A. Identity-based cryptosystems and signature schemes. In Proceedings of the Advances in Cryptology-CRYPTO’84, LNCS 196, Santa Barbara, CA, USA, 19–22 August 1984; pp. 47–53.
Boneh, D.; Franklin, M. Identity-based encryption from the weil pairing. In Proceedings of the Advances in Cryptology-CRYPTO’01, LNCS 2139, Santa Barbara, CA, USA, 19–23 August 2001; pp. 213–229.
Malone-Lee, J. Identity Based Signcryption. Cryptology ePrint Archive, Report 2002/098. 2002. Available online: http://eprint.iacr.org/2002/098 (accessed on 14 March 2017).
Libert, B.; Quisquator, J.J. A new identity based signcryption scheme from pairings. In Proceedings of the IEEE Information Theory Workshop-ITW’03, Paris, France, 31 March–4 April 2003; pp. 155–158.
Chow, S.S.M.; Yiu, S.M.; Hui, L.C.K.; Chow, K.P. Efficient forward and provably secure ID-based signcryption scheme with public verifiability and public ciphertext authenticity. In Proceedings of the Information Security and Cryptology-ICISC’03, LNCS 2971, Seoul, Korea, 27–28 November 2004; pp. 352–369.
Boyen, X. Multipurpose identity based signcryption: A Swiss army knife for identity based cryptography. In Proceedings of the Advance in Cryptology-CRYPTO’03, LNCS 2729, Santa Barbara, CA, USA, 17–21 August 2003; pp. 383–399.
Chen, L.; Malone-Lee, J. Improved identity-based signcryption. In Proceedings of the Public Key Cryptography-PKC’05, LNCS 3386, Les Diablerets, Switzerland, 23–26 January 2005; pp. 362–379.
Barreto, P.S.L.M.; Libert, B.; McCullagh, N.; Quisquater, J.J. Efficient and provably-secure identity based signatures and signcryption from bilinear maps. In Proceedings of the Advance in Cryptology-ASIACRYPT’05, LNCS 3788, Chennai, India, 4–8 December 2005; pp. 515–532.
Selvi, S.S.D.; Vivek, S.S.; Rangan, C.P. Identity based public verifiable signcryption scheme. In Proceedings of the ProvSec’10, LNCS 6402, Malacca, Malaysia, 13–15 October 2010; pp. 244–260.
Yu, Y.; Yang, B.; Sun, Y.; Zhu, S. Identity based signcryption scheme without random oracles. Comput. Stand. Interfaces 2009, 31, 56–62. [Google Scholar] [CrossRef]
Jin, Z.; Wen, Q.; Du, H. An improved semantically-secure identity-based signcryption scheme in the standard model. Comput. Electr. Eng. 2010, 36, 545–552. [Google Scholar] [CrossRef]
Li, F.; Muhaya, F.B.; Zhang, M.; Takagi, T. Efficient identity-based signcryption in the standard model. In Proceedings of the ProvSec’11, LNCS 6980, Xi’an, China, 16–18 October 2011; pp. 120–137.
Han, Y.; Yang, X. ECGSC: Elliptic Curve Based Generalized Signcryption Scheme. Cryptology ePrint Archive, Report 2006/126. 2006. Available online: http://eprint.iacr.org/2006/126 (accessed on 14 March 2017).
Wang, X.; Yang, Y.; Han, Y. Provable Secure Generalized Signcryption. Cryptology ePrint Archive, Report 2007/173. 2007. Available online: http://eprint.iacr.org/2007/173 (accessed on 14 March 2017).
Lal, S.; Kushwah, P. ID Based Generalized Signcryption. Cryptology ePrint Archive, Report 2008/084. 2008. Available online: http://eprint.iacr.org/2008/084 (accessed on 14 March 2017).
Yu, G.; Ma, X.; Shen, Y.; Han, W. Provable secure identity based genrealized signcryption schem. Theor. Comput. Sci. 2010, 411, 3614–3624. [Google Scholar] [CrossRef]
Kushwah, P.; Lal, S. An efficient identity based generalized signcryption scheme. Theor. Comput. Sci. 2011, 412, 6382–6389. [Google Scholar] [CrossRef]
Bellare, M.; Rogaway, P. The exact security of digital signatures-how to sign with RSA and Rabin. In Proceedings of the Advances in Cryptology-EUROCRYPT’96, LNCS 0950, Kenmare, Ireland, 9–12 May 1996; pp. 399–416.
Canetti, R.; Goldreich, O.; Halevi, S. The random oracle methodology, revisited. In Proceedings of the Annual Symposium on the Theory of Computing-STOC’98, Dallas, TX, USA, 23–26 May 1998; pp. 209–218.
Paterson, K.G.; Schuldt, J.C.N. Efficient identity based signatures secure in the standard mode. In Proceedings of the Information Security and Privacy-ACISP’06, LNCS 4058, Melbourne, Australia, 3–5 July 2006; pp. 207–222.
Waters, R. Efficient identity based encryption without random oracles. In Proceedings of the Advance in Cryptology-Eurocrypt’05, LNCS 3494, Aarhus, Denmark, 22–26 May 2005; pp. 114–127.
Canetti, R.; Halevi, S.; Kate, J. Chosen-ciphertext security from identity-based encryption. In Proceedings of the Advance in Cryptology-Eurocrypt’04, LNCS 3027, Interlaken, Switzerland, 2–6 May 2004; pp. 207–222.
Shamus Software Ltd. MIRACL Library. Available online: http://www.shamus.ie/index.php?page=home (accessed on 1 May 2015).

Table 1. Comparison of identity based generalized signcryption schemes.

**Table 1.** Comparison of identity based generalized signcryption schemes.
Schemes	Generalized Signcrypt	Generalized Unsigncrypt	Security Model
Lal et al. [20]	$6 E + 1 P = 14.456$ ms	$3 P + 1 E = 14.342$ ms	RO
Yu et al. [21]	$4 E + 1 P = 11.047$ ms	$3 P + 3 E = 17.76$ ms	RO
Kushwah et al. [22]	$4 E = 6.836$ ms	$2 P + 3 E = 13.549$ ms	RO
Ours	$6 E = 10.254$ ms	$5 P + 2 E = 24.473$ ms	SM

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

Share and Cite

MDPI and ACS Style

Shen, X.; Ming, Y.; Feng, J. Identity Based Generalized Signcryption Scheme in the Standard Model. Entropy 2017, 19, 121. https://doi.org/10.3390/e19030121

AMA Style

Shen X, Ming Y, Feng J. Identity Based Generalized Signcryption Scheme in the Standard Model. Entropy. 2017; 19(3):121. https://doi.org/10.3390/e19030121

Chicago/Turabian Style

Shen, Xiaoqin, Yang Ming, and Jie Feng. 2017. "Identity Based Generalized Signcryption Scheme in the Standard Model" Entropy 19, no. 3: 121. https://doi.org/10.3390/e19030121

APA Style

Shen, X., Ming, Y., & Feng, J. (2017). Identity Based Generalized Signcryption Scheme in the Standard Model. Entropy, 19(3), 121. https://doi.org/10.3390/e19030121

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

Article Menu

Identity Based Generalized Signcryption Scheme in the Standard Model

Abstract

1. Introduction

2. Preliminaries

2.1. Bilinear Pairings

2.2. Complexity Assumptions

2.2.1. Decisional Bilinear Diffie–Hellman (DBDH) Problem

2.2.2. Computational Diffie–Hellman (CDH) Problem

3. Formal Model of Identity-Based Generalized Signcryption Schemes

3.1. Generic Scheme

3.2. Security Model

Game 1. Indistinguishability (IND)-(IDGSC-EN)-CCA2 Secure

Game 2. IND-(IDGSC-SC)-CCA2 Secure

Game 3. EF-(IBGSC-SG)-Adaptive Chosen Message Attack (ACMA) Secure

Game 4. EF-(IDGSC-SC)-ACMA Secure

4. The Proposed Scheme

5. Analysis

5.1. Correctness

Case 1. In the IDGSC-SC Model

Case 2. In the IDGSC-SG Model

Case 3. In the IDGSC-EN Model

5.2. Security Proof

5.3. Efficiency

6. Conclusions

Acknowledgments

Author Contributions

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI