On security of a Certificateless Hybrid Signcryption Scheme

Abstract

Certificateless hybrid signcryption is a newly cryptosystem that plays a great role in some storage-constrained networks when confidentiality and authenticity are needed simultaneously. Now considering almost all certificateless signcryption schemes that have been proposed in the literature cannot effectively against the public-key-replacement attacks. In this paper, we proposed a hybrid signcryption scheme in the certificateless setting to fill this security gaps, and its security has been verified to achieve the confidentiality and unforgeability in random oracle model. Moreover, performance analysis shows the proposed scheme is efficient and practical.

1 Introduction

Confidentiality, integrity, non-repudiation and authentication are the important requirements for many cryptographic applications. In the traditional Public Key Cryptography (PKC), when a sender wishes to transmit a message to the receiver, firstly the sender needs a trusted Certificate Authorities (CA) to issue digital certificate and authenticated public key [1]. And certificate is notoriously considered to be costly to use and manage. Observing the heavy overheads of storing, transferring and verifying the certificate in the traditional PKC [2]. To simplify certificate management procedures of traditional PKI, identity-based cryptography (IBC) was proposed by Shamir [3] and makes deployment practical. The idea of IBC is to get rid of certificates by allowing the user’s public key to some unique message that identifies a user in the system. Examples of such message include IP addresses and email addresses. This eliminates the requirement to link the public key with a user, and several practical IBC schemes have been devised [4–6]. However, the private key corresponding to a user’s public key is derived by a trusted authority called the private key generator (PKG), which leads to the private key escrow problem.

To solve this problem, Al-Riyami and Paterson [7] proposed a new cryptographic paradigm called Certificateless Public Key Cryptography (CL-PKC). In this cryptosystem, a user private key is a combination of some user-chosen secret and some contribution of a trusted PKG, in such a way that the key escrow problem can be solved. In order to perform encryption and signature simultaneously more efficiently in some network environments e.g. smartcards or wireless sensor networks (WSN) etc. Barbosa and Farshim [8] proposed a novel notion of certificateless signcryption (CLSC) in 2008, which is combined with the signcryption technology that simultaneously fulfills both the functions of public key encryption and digital signature in a logically single step. Subsequently, as one of the research hotspots, the CLSC has attracted extensive attention from the academia.

Recently, many efficient CLSC schemes have been proposed [9–12]. Wu et al. [10] proposed an efficient CLSC scheme in 2008, which requires four pairing operations in the signcryption and unsigncryption phase, but unfortunately it was found insecure by Selvi et al. [11]. And in 2011, Selvi et al. [12] also introduced a new security CLSC scheme, which requires five pairing operations in same phase. While above schemes are required to send message from a particular collection.

A practical way to perform secrecy communication for large messages is to use hybrid encryption that separates the encryption into two parts: one part uses public key techniques to encrypt a one-time symmetric key; the other part uses the symmetric key to encrypt the actual message. In such a construction, the public key part of the algorithm is known as the key encryption mechanism (KEM) while the symmetric key part is known as the data encapsulation mechanism (DEM). The formal treatment of this paradigm originates in the work of Shoup and Cramer [13]. And the resulting hybrid encryption paradigm has received much attention in recent years [14–16]. It is very attractive as it gives a clear separation between the various parts of the cipher allowing for modular design.

In 2013, Li et al. [17] extended the concept of hybrid signcryption to CLSC cryptosystem, which can handle message of arbitrary length, but it still requires six pairing operations. In 2014, Zhou et al. [18] introduce a certificateless generalized signcryption scheme in formal security model to against the malicious-but passive key generation center attacks, but its compute overhead is still high in the signcryption and unsigncryption phase.

In this paper, aimed at designing an efficient protocol for storage-constrained network. We proposed a practical and provably secure certifiacteless hybrid signcryption scheme, which used the technique of the public key binding in the extract-partial-private-key and only required four bilinear pairing operations. Therefore, this scheme not only can resist efficiently the current known security attacks, especially against public-key-replacement attacks, but also has lower communication overhead and shorter ciphertext length.

The paper is organized as follows. In Sect. 2, the preliminaries are reviewed and the formal model of certificicateless hybrid signcryption algorithm. In Sect. 3, we propose a concrete scheme under the new security model. Security and performance analysis of our scheme is included in Sect. 4. Finally, we draw some concluding remarks in Sect. 5.

2 Preliminaries

In this section, we briefly review some fundamental backgrounds such as bilinear maps, complexity assumptions and definition of the algorithm model. The following four definitions are quoted from [13, 17–19].

Definition 1

Let $G_{1}$ and $G_{2}$ be two cyclic multiplicative groups of prime order p, and a bilinear map $\hat{e}:G_{1} \times G_{1} \to G_{2}$ satisfying the following properties:

• 1. Bilinearity: $\hat{e}(aP,bP) = \hat{e}(P,P)^{ab}$ for any $a,b \in Z_{q}^{ * }.$

• 2. Non-degeneracy: $\hat{e}(P,P) \ne 1_{G2}.$

• 3. Computability: $\hat{e}(P,Q)$ is efficiently computable for all $P,Q \in G_{1}.$

Definition 2

The challenger randomly chooses $a \in Z_{q}^{ * }$ at random and given $(P,aP) \in G_{1}.$ The computational elliptic curve discrete logarithm problem (ECDLP) is to compute a.

An adversary, ${\mathcal{A}},$ has a probability of at least $\varepsilon$ in solving the ECDLP problem if

$$ \Pr [{\mathcal{A}}(P,aP) = a] \ge \varepsilon $$

The ECDLP assumption holds if the advantage of any PPT adversary ${\mathcal{A}}$ is negligible in solving the ECDLP problem.

Definition 3

The challenger chooses $a,b \in Z_{q}^{ * }$ at random and output $(P,aP,bP).$ The computational Diffie–Hellman (CDH) problem is to compute $abP.$

An adversary, ${\mathcal{A}},$ has a probability of at least $\varepsilon$ in solving the CDH problem if

$$ \Pr [{\mathcal{A}}(P,aP,bP) = abP] \ge \varepsilon $$

The CDH assumption holds if the advantage of any PPT adversary ${\mathcal{A}}$ is negligible in solving the CDH problem.

Definition 4

The challenger randomly chooses $a,b,c,{\text{T}} \in Z_{q}^{ * }$ and sets $\delta \in \{ 0,1\},$ if $\delta = 1,$ and a 5-tuple $(P,aP,bP,cP,e(P,P)^{abc} )$ is output, otherwise $(P,aP,bP,cP,e(P,P)^{T} ).$ The decisional Bilinear Diffie–Hellman (BDH) problem is to determine the value of T. An adversary ${\mathcal{A}}$ has at least an $\varepsilon$ advantage in solving the BDH problem if

$$ \left| {\Pr \left[ {{\mathcal{A}}(P,aP,bP,cP,e(P,P)^{abc} ) = 1} \right]} \right| - \left| {\Pr \left[ {{\mathcal{A}}(P,aP,bP,cP,e(P,P)^{T} ) = 1} \right]} \right| \ge 2\varepsilon $$

where the probability is defined over the randomly chosen $a,b,c,{\text{T}}$ and the random bits consumed by ${\mathcal{A}}.$ The BDH assumption holds if the advantage of any PPT adversary ${\mathcal{A}}$ is negligible in solving the BDH problem.

2.1 Formal model of certificateless hybrid signcryption

The notion of a certificateless hybrid signcryption scheme was defined by Cramer and Shoup [13]. A generic certificateless hybrid signcryption scheme works as following.

2.1.1 Key-Encapsulation-Mechanism

• Setup This algorithm takes as input a security k and returns system parameters params and a randomly chooses master secret key msk. After the algorithm is performed the KGC publishes the system parameters params and keeps the master key msk secret.

• Extract-Partial-Private-Key This algorithm takes as input params, msk and an identity $ID \in \{ 0,1\}^{n}$ of an entity, and returns a partial private key D _ID . The KGC carries out the algorithm after verifying the user’s identity.

• Generate-User-Key This algorithm takes as input params and an identity ID and returns a randomly outputted secret value x _ID and a public key PK. This algorithm is run by a user to obtain a public key and a secret value which can be used to construct a full private key. Note that, the public key is published without certification.

• Extract-Private-Key This algorithm takes params, a user’s partial private key D _ID and secret value x _ID as input, and returns the user’s full private key SK. Obviously, the algorithm is executed by the entity itself.

• Signcrypt The algorithm takes params, a message m, a sender’s identity ID, private key SK and public key PK, and a receiver’s identity ID and public key PK as input, and returns a ciphertext or error symbol $\bot.$

• Unsigncrypt The algorithm takes a ciphertext, the receiver’s identity ID, private key SK and public key PK, and a sender’s identity ID and public key PK as input, and outputs a plaintext or an error symbol $\bot.$

2.1.2 Data-Encapsulation-Mechanism

• Enc this algorithm takes as input message $m \in \{ 0,1\}^{n}$ and encapsulation key K, then output a ciphertext $C \in {\text{ 0,1}}^{\rm n},$ where m is a bit string arbitrary length. We denote this as $C \leftarrow Enc_{K} (m).$

• Dec this algorithm takes as input a key K and a ciphertext C, an outputs the message $m \in \{ 0,1\}^{n}$ or error symbol $\bot.$

Note that it is only required that the Data-Encapsulation-Mechanism is secure with respect to confidentiality and unforgeable.

2.2 Security Notions for Certificateless Hybrid Signcryption

Barbosa and Farshim [8] defined the formal security notions for CLSC scheme firstly, and scheme should satisfy confidentiality and unforgeability. As shown in [18–23], these security models are discussed in detail by considering two different type adversaries, Type I and II. A Type I adversary model an attacker which is a common user of the system and is not in possession of the KGC’s master secret key, but it can replace the public key of an arbitrary entity, obtain the partial private key and private key. A Type II adversary model is an honest-but-curious KGC who knows the KGC’s master secret key, but it cannot replace user’s public key. While in the security game, the security model simulates the $game_{A}^{IND - CCA2}$ and $game_{A}^{EUF - CMA}$ between the adversary and challenger. And this paper gives the game simulation instance in Sect. 4.

3 Proposed Scheme

In this section, we illustrate a kind of practical certificateless hybrid signcryption scheme which consists of the following algorithm.

• Setup Given a security parameter $k,$ the KGC performs the following to set up the system parameter.

  • Run the parameter generator on input k to generate a prime p, two cyclic groups ${\mathbb{G}}_{1} {\text{ and }}{\mathbb{G}}_{2}$ of same order $q \, (q > 2^{k} ),$ a generator $P \in {}_{R}{\mathbf{\mathbb{G}}}_{1}$ and an admissible pairing $\hat{e}:{\mathbb{G}}_{1} \times {\mathbb{G}}_{1} \to {\mathbb{G}}_{2}.$

  • Selects the master secret key $s \in {}_{R}{\mathbb{G}}_{q}^{ * }$ and the system public key is set to be $P_{pub} = sP.$

  • Selects three hash functions $H_{1} :\{ 0,1\}^{ * } \to {\mathbb{G}}_{1},$ $H_{2} :(\{ 0,1\}^{ * } )^{2} \times ({\mathbb{G}}_{1} )^{2} \times {\mathbb{G}}_{2} \to \{ 0,1\}^{n}$ and $H_{3} :\{ 0,1\}^{l} \times (\{ 0,1\}^{ * } )^{2} \times ({\mathbb{G}}_{1} )^{4} \times {\mathbb{G}}_{2} \to Z_{q}^{ * }.$

  • Chooses a family of data encapsulation algorithm (Enc, Dec), and this algorithm is the confidentiality and unforgeable.

  • The public parameters of the scheme are set to be $params \leftarrow (q,{\mathbb{G}}_{1},{\mathbb{G}}_{2},\hat{e},P,P_{pub},H_{1},H_{2},H_{3},Enc,Dec)$ and the master secret key is $msk \leftarrow s.$

• Generate-User-Key This algorithm takes as input params and a user’s identity $ID,$ it picks a random value $x_{ID} \in {}_{R}Z_{q}^{ * }$ as user’s secret value, and computes $PK_{ID} = x_{ID} \cdot P$ as the public key.

• Extract-Partial-Private-Key Given a group of user’s identity $ID \in \{ 0,1\}^{ * }$ and the corresponding public key $PK_{ID},$ the KGC generates a partial private key $D_{ID} = sH_{1} (ID\left\| {PK_{ID} } \right.)$ uniformly, and sends to user by using secure channel. Note that, the process of generate-partial-private-key is show in Fig. 1. Comparing to the traditional partial-private-key, getting partial-private-key of our scheme combined with the identity ID and public key $PK_{ID}.$ Therefore, the partial-private-key can do some valid verification in the face of a threats to public key replacement attack.

  Fig. 1

  

  The process of extract-partial-private-key

• Signcrypt In order to signcrypt the message m to the receiver with identity $ID_{R}$ and public key $PK_{R},$ and sender with public–private key pair $\{ ID_{S},PK_{S},SK_{S} - (D_{S},x_{S} )\}$ works as follow:

  • Choose $r_{1},r_{2} \in {}_{R}Z_{q}^{ * },$ compute $R_{1} = r_{1} P,R_{2} = r_{2} P,$ $Q_{R} = H_{1} (ID_{R} \left\| {PK_{R} } \right.).$

  • Compute $U = r_{1} PK_{R},$ $V = \hat{e}(r_{2} Q_{R},P_{pub} ),$ $K = H_{2} (ID_{S},ID_{R},R_{1},R_{2},U,V),$ $\tau = Enc_{K} (m).$

  • Compute $h = H_{3} (\tau,ID_{S},ID_{R},PK_{S},PK_{R},R_{1},R_{2},U,V),$ $W = h(D_{S} + r_{2} Q_{S} ),$ $T = hx_{S} + r_{1}.$

  • Output $\sigma = (\tau,h,W,T)$ as the signcryption on m.

• Unsigncrypt To unsigncrypt a ciptertext $\sigma = (\tau,h,W,T)$ form the sender with identity $ID_{S}$ and public key $PK_{S},$ the receiver with full public–private key ${\text{\{ }}ID_{R},PK_{R},SK_{R} { - }(D_{R},x_{R} ){\text{\} }}$ works as follow:

  • Compute $Q_{S} = H_{1} (ID_{S} \left\| {PK_{S} } \right.),$ $R_{1} = TP - hPK_{S},$ $U^{\prime} = x_{R} R^{\prime}_{1},$ $V^{\prime} = \hat{e}(D_{R},R_{2} ).$

  • Check $h = H_{3} (\tau,ID_{S},ID_{R},PK_{S},PK_{R},R^{\prime}_{1},R_{2},U^{\prime},V^{\prime}),$ $\hat{e}(W,P) = \hat{e}(hQ_{S} R_{2} + P_{pub} )$ hold or not.

  • If they hold, compute and output the decapsulation key $K^{\prime} = H_{2} (ID_{S},ID_{R},R^{\prime}_{1},R_{2},U^{\prime},V^{\prime}),$ else output symbol $'' \bot ''.$

3.1 Correctness

The correctness of our scheme is described as follow:

$$ R^{\prime}_{1} = TP - hPK_{S} = hx_{S} P + r_{1} P - hPK_{S} = r_{1} P = R_{1} $$

$$ U^{\prime} = x_{R} R^{\prime}_{1} = rx_{R} P = rP_{R} = U $$

$$ V^{\prime} = \hat{e}(D_{R},R_{2} ) = \hat{e}(sQ_{R},r_{2} P) = \hat{e}(r_{2} Q_{R},sP) = \hat{e}(r_{2} Q_{R},P_{pub} ) = V $$

Therefore, it is obvious that

$$ h = H_{3} (\tau,ID_{S},ID_{R},PK_{S},PK_{R},R_{1},R_{2},U,V) $$

$$ \begin{aligned} \hat{e}(W,P) &= \hat{e}(hD_{S},P) \cdot \hat{e}(hr_{2} Q_{S},P) = \hat{e}(hQ_{S},sP) \cdot \hat{e}(hQ_{S},r_{2} P) \hfill \\ \, &= \hat{e}(hQ_{S},sP + r_{2} P) = \hat{e}(hQ_{S},R_{2} + P_{pub} ) \hfill \\ \end{aligned} $$

Finally, we verify whether $K^{\prime} = K$ holds or not, and recover the message m.

4 Proof of Security

Theorem 1

Under the CDH assumption and BDH assumption, and the data encapsulation algorithm $(Enc,Dec)$ is confidentiality, we proposed scheme is Indistinguishability Against Adaptive Chosen Ciphertext Attacks (IND-CCA2) secure in the random oracle model. This theorem follows from Lemmas 1 and 2.

Lemma 1

Our scheme is IND-CCA2-I secure during the $game_{{A_{I} }}^{IND - CCA2 - I},$ assuming that a probabilistic polynomial-time (PPT) adversary $A_{I}$ (assume a dishonest user, but does not know system msk) has non-negligible advantage $\varepsilon$ in winning this game against our scheme. More precisely, there exist an algorithm ${\mathcal{C}}$ which uses $A_{I}$ to solve the BDH problem:

$$ Adv_{scheme}^{IND - CCA2 - I} (A_{I} ) \ge \varepsilon \cdot \frac{1}{{q_{1} }}\left( {1 - \frac{1}{{q_{2} }}} \right) \cdot \left( {1 - \frac{1}{{q_{pa} }}} \right) \cdot \left( {1 - \frac{{q_{S} (2q_{1} + q_{2} + q_{3} )}}{{2^{k} }}} \right)\left( {1 - \frac{{q_{un} }}{{2^{k} }}} \right) $$

here $q_{i}$ is denoted to query of hash oracle, $q_{sk}$ extract private key query, $q_{qk}$ extract public key query, $q_{pa}$ request partial private key query, $q_{r}$ public key replacement query, $q_{s}$ signcryption query and $q_{un}$ unsigncryption query.

Proof

We suppose that the algorithm ${\mathcal{C}}$ is an example of BDH problem. ${\mathcal{C}}$ will run $A_{I}$ as a subroutine and act as $A_{I}$’s challenger in the $game_{{A_{I} }}^{IND - CCA2 - I}$ for our scheme. By using this game, $A_{I}$ will get various answers from each oracle and store these responses in the list which is empty at beginning. And the proof structure of random oracle model as shown in the Fig. 2.

Fig. 2

The proof structure of random oracle model

Setup

${\mathcal{C}}$ runs setup algorithm and gives $A_{I}$ the system $params(q,{\mathbb{G}}_{1},{\mathbb{G}}_{2},\hat{e},P,P_{pub},H_{1},H_{2},H_{3},Enc,Dec)$ with $P_{pub} \leftarrow aP,$ where a as the system msk is unknown to ${\mathcal{C}}.$ Then, ${\mathcal{C}}$ picks a challenged identity $J \in {}_{R}\{ 1,2, \ldots,q_{1} \}$ randomly and answers oracle query as follows.

$H_{1} {\hbox{-}}Query$

${\mathcal{C}}$ maintains a hash list $L_{1}^{list}$ of tuple $\langle ID_{i},PK_{i},Q_{i},d_{i} \rangle.$ When $A_{I}$ ask the oracle $H_{1}$ at a point $\langle ID_{j},PK_{j},Q_{j},d_{j} \rangle,$ if the tuple already appears in the $L_{1}^{list},$ it returns the value. Otherwise, ${\mathcal{C}}$ picks a random $d_{j} \in {}_{R}Z_{q}^{ * },$ computes $Q_{j} = d_{j} P,$ and adds new tuple $\langle ID_{j},PK_{j},Q_{j},d_{j} \rangle$ in the $L_{1}^{list}.$ Note that, at the J-th query, ${\mathcal{C}}$ answers $Q_{j} = bP$ and puts the special tuple $\langle ID_{J},PK_{J},bP, \bot \rangle$ into the $L_{1}^{list}.$

$H_{2} {\hbox{-}}Query$

${\mathcal{C}}$ maintains a hash list $L_{2}^{list}$ of tuple $\langle ID_{i},ID_{j},R_{1i},R_{2i},U_{i},V_{i},K_{i} \rangle,$ when $A_{I}$ query the oracle $H_{2},$ ${\mathcal{C}}$ checks the $L_{2}^{list}$ and returns a unique value $K_{i}$ if this tuple exists. Otherwise, ${\mathcal{C}}$ responses as follows:

• 1. If $\{ j \ne J,U_{i} = x_{j} R_{1i} /x_{j}^{ * } R_{1i},V_{i} = e(d_{j} P,R_{2i} )\}$ hold, ${\mathcal{C}}$ picks $K_{i} \in {}_{R}Z_{q}^{ * }$ and returns this value, then adds into the $L_{2}^{list}$.

• 2. If $\{ j = J,U_{i} = x_{j} R_{1i} /x_{j}^{ * } R_{1i},V_{i} = e(abP,R_{2i} )\}$ hold, ${\mathcal{C}}$ picks $K_{i} \in {}_{R}Z_{q}^{ * }$ and returns this value, then adds into the $L_{2}^{list}$

• 3. Otherwise, ${\mathcal{C}}$ aborts and denotes the event by E1.

$H_{3} {\hbox{-}}Query$

For each query $\langle \tau,ID_{i},ID_{j},PK_{i},PK_{j},R_{1i},R_{2i},U_{i},V_{i},h_{i} \rangle,$ ${\mathcal{C}}$ checks the list $L_{3}^{list}$ and returns $h_{i}$ if these entities already exist in the $L_{3}^{list} /L_{S}^{list}$. Otherwise, ${\mathcal{C}}$ searches the $L_{1}^{list}$ and $L_{2}^{list},$ picks a different $h_{i} \in {}_{R}Z_{q}^{ * }$ to answer $A_{I},$ updates the $L_{3}^{list}$ and the $L_{S}^{list}$ at last.

Public-Key-Extract

${\mathcal{C}}$ maintains a public key list $L_{PK}^{list}$ of tuple $\langle ID_{i},PK_{i},x_{i} \rangle$. For each query on $PK_{j},$ ${\mathcal{C}}$ will answer its value if the $L_{1}^{list}$ or the $L_{PK}^{list}$ contain this entity. Otherwise, ${\mathcal{C}}$ chooses $x_{j} \in {}_{R}Z_{q}^{ * }$ randomly, generates a new key $PK_{j} = x_{j} P$ and returns this value, then updates the corresponding list.

Private-Key-Extract

For each query on $x_{i},$ if the $L_{PK}^{list}$ contain the corresponding entity, ${\mathcal{C}}$ adds it into the list $L_{SK}^{list}$ of tuple $\langle ID_{i},x_{i}, \bot \rangle$. If not, ${\mathcal{C}}$ makes a public key extraction query and updates this list.

Request-Partial-Private-Key

When $A_{I}$ ask a partial private key query, ${\mathcal{C}}$ will go through the list $L_{1}^{list}$ and look for the corresponding index $\{ ID_{j},PK_{j} \}$. If $j \ne J,$ ${\mathcal{C}}$ computes $D_{j} = d_{j} P_{pub},$ adds this tuple $\langle ID_{i},x_{i},D_{j} \rangle$ in the $L_{SK}^{list},$ and returns the value. If not, this game aborts and denotes the event by E2.

Public-Key-Replacement

When $A_{I}$ submits a identity $ID_{i}$ and a certificateless public key $PK_{i}^{ * }$ to the $L_{PK}^{list},$ ${\mathcal{C}}$ inserts or updates the corresponding list with tuple $\langle ID_{i},PK_{i} \leftarrow PK_{i}^{ * }, \bot,\rangle$. Note that, $A_{I}$ cannot query this private key pair from oracle.

Signcrypt-Query

${\mathcal{C}}$ maintains the $L_{S}^{list}$ of tuple $\langle m,ID_{i},ID_{j},PK_{i},PK_{j},R_{1i},R_{2i},U_{i},V_{i},\tau_{i},h_{i},W_{i},T_{i} \rangle,$ where $\{ ID_{i},ID_{j} \}$ are the identity of sender and that of the receiver respectively. For each signcryption query, if $\{ i \ne J,d_{i} \ne \bot,x_{i} /x_{i}^{ * } \ne \bot \},$ where $x_{i}^{ * }$ input by $A_{I},$ ${\mathcal{C}}$ answers this query and follow with the signcrypt algorithm as Sect. 3, then generates the signcrytion ciphertext $\sigma \leftarrow (h_{i},R_{2i},W_{i},T_{i} )$ as query result.

Note that, this game aborts and denotes the event by E3, if in this case $h_{{L_{3} }} \ne h_{{L_{S} }},$ where $\{ h_{{L_{3} }},h_{{L_{S} }} \}$ are the entity from the list $L_{3}^{list}$ and $L_{S}^{list}$ respectively.

Note also that, if $PK_{i} \leftarrow PK_{i}^{ * },$ $A_{I}$ inputs the value $x_{i}^{ * }$ and ${\mathcal{C}}$ computes $T_{i} = h_{i} x_{i}^{ * } + r_{1},$ $W_{i} = h_{i} r_{i} Q_{i}^{ * }$. If not, ${\mathcal{C}}$ computes $T_{i} = h_{i} x_{i}^{{}} + r_{1},$ $W_{i} = h_{i} r_{i} Q_{i}^{{}}$ and processes as usual.

Unsigncrypt-Query

For each unsigncryption query $\langle m,ID_{i},ID_{j},PK_{i},PK_{j},R_{1i},R_{2i},U_{i},V_{i},\sigma \rangle,$ where $\{ ID_{i},ID_{j} \}$ are the identity of sender and that of the receiver respectively, ${\mathcal{C}}$ proceeds as follows. Firstly, it obtains the receiver’s partial private key $D_{j} = d_{j} P_{pub}$ and the sender’s identity hash value $Q_{i}$ corresponding to $\{ ID_{i},PK_{i} \}$ from the list $L_{1}^{list}$. Then, it executes the verification part of the unsigncryption algorithm as Sect. 3, returns $\bot$ if the verification does not succeed. After that, if $ID_{j} = ID_{J},$ ${\mathcal{C}}$ fails and stop (denote event by E4). Otherwise, it go through list and looks for a different entity $K^{ * } \leftarrow (ID_{i},ID_{j},R_{1i},R_{2i},U_{i},V_{i} )$. If such an entity exists, ${\mathcal{C}}$ returns this result $m^{\prime}/ \bot \leftarrow Dec_{{K^{ * } }} (\sigma )$.

Challenge phase

${\mathcal{C}}$ generates two equal length plaintext $(m_{0},m_{1} )$ newly. And $A_{I}$ picks two identities $ID_{S}^{ * }$ and $ID_{R}^{ * }$ on which it wishes to be challenged. If $ID_{R}^{ * } \ne ID_{J},$ ${\mathcal{C}}$ fails and stops (denote event by E5). Otherwise, it proceeds to construct a challenge as follows. It randomly chooses $m_{b} (b \in {}_{R}\{ 0,1\} )$ and $r_{1}^{ * } \in {}_{R}Z_{q}^{ * },$ computes $R_{1}^{ * } = r_{1}^{ * } P,$ $U_{{}}^{ * } = r_{1}^{ * } PK_{R}$. Then it sets $R_{2}^{ * } = cP,$ computes $V^{ * } = \hat{e}(cQ_{j},P_{pub} ) = \hat{e}(P,P)^{adc}$. After that, it computes $\tau^{ * } = Enc_{{K^{ * } }} (m_{b} ),$ $T^{ * } = h^{ * } x_{S}^{ * } + r_{1}^{ * },$ $W^{ * } = h_{{}}^{ * } (D_{S} + cQ_{S} ),$ where $K^{ * }$ is obtained from the $L_{2}^{list},$ $h^{ * }$ is obtained from the $L_{3}^{list}$. At last, ${\mathcal{C}}$ sends the challenge ciphertext $\sigma^{ * } \leftarrow (h^{ * },R_{2}^{ * },W^{ * },T^{ * } )$.

Guess phase

$A_{I}$ then performs a second series of queries which is treated in the same way as the first one (beyond the Partial-Private-Key query). At the end of the simulation, it produces the guess of challenge ciphertext $m^{\prime}_{b}$ for which it believes the $h^{ * } \leftarrow (\tau^{ * },ID_{S}^{ * },ID_{R}^{ * },PK_{S}^{ * },PK_{R}^{ * },R_{1}^{ * },R_{2}^{ * },U^{ * },V^{ * } ),$ $e(W^{ * },P) = e(h^{ * } Q_{S},R_{2}^{ * } + P_{pub} ),$ $\sigma^{ * } \leftarrow Enc_{{K^{ * } }} (m^{\prime}_{b} )$ hold. Therefore, it wins this game if $b^{\prime} = b$ and game does not abortion. $A_{I}$ has non-negligible advantage in winning the $game_{{A_{I} }}^{IND - CCA2 - I}$ against our scheme, there exist an algorithm ${\mathcal{C}}$ which use $A_{I}$ to solve the BDH problem such that:

$$ \begin{aligned} Adv_{scheme}^{IND - CCA2 - I} (A_{I} ) & = \varepsilon \cdot \Pr [\neg E1 \wedge \neg E2 \wedge \neg E3 \wedge \neg E4 \wedge \neg E5] \\ & \ge \varepsilon \cdot \frac{1}{{q_{1} }}\left( {1 - \frac{1}{{q_{2} }}} \right) \cdot \left( {1 - \frac{1}{{q_{pa} }}} \right) \cdot \left( {1 - \frac{{q_{S} (2q_{1} + q_{2} + q_{3} )}}{{2^{k} }}} \right)\left( {1 - \frac{{q_{un} }}{{2^{k} }}} \right) \\ \end{aligned} $$

Lemma 2

Our scheme is IND-CCA2-II secure during the $game_{{A_{II} }}^{IND - CCA2 - II},$ assuming that a PPT adversary ${\mathbb{A}}_{II}$ (assume an honest but curious KGC, and it cannot replace user’s key) has non-negligible advantage $\varepsilon$ in winning this game against our scheme. More precisely, there exist an algorithm ${\mathcal{C}}$ which uses ${\mathbb{A}}_{II}$ to solve the CDH problem:

$$ Adv_{scheme}^{IND - CCA2 - II} (A_{II} ) \ge \varepsilon \cdot \frac{1}{{q_{1} }} \cdot \left( {1 - \frac{1}{{q_{2} }}} \right) \cdot \left( {1 - \frac{1}{{q_{sk} }}} \right) \cdot \left( {1 - \frac{{q_{S} (2q_{1} + q_{2} + q_{3} )}}{{2^{k} }}} \right)\left( {1 - \frac{{q_{un} }}{{2^{k} }}} \right) $$

here $q_{1},q_{2},q_{3},q_{pk},q_{sk},q_{pa},q_{S}\, {\text{and}} \,q_{un}$ denote the same as in Lemma 1.

Proof

The algorithm ${\mathcal{C}},$ solving example of CDH problem, simulation process is similar to Lemma 1. But the difference is that ${\mathbb{A}}_{II}$ will have different way of answer.

Setup

${\mathcal{C}}$ runs setup algorithm and gets the system $params(q,{\mathbb{G}}_{1},{\mathbb{G}}_{2},\hat{e},P,P_{pub},H_{1},H_{2},H_{3},Enc,Dec),$ then ${\mathcal{C}}$ sends both (params, msk) to ${\mathbb{A}}_{II}$.

$H_{1} {\hbox{-}}Query$

For each $H_{1}$ query, ${\mathcal{C}}$ goes through the list $L_{1}^{list}$ if containing a tuple $\langle ID_{i},PK_{i},Q_{i},d_{i} \rangle,$ it returns the value. Otherwise, ${\mathcal{C}}$ chooses a random value $d_{i} \in Z_{q}^{ * }$ and puts the new entries $\langle ID_{i},PK_{i},Q_{i},d_{i} \rangle$ into the list $L_{1}^{list},$ answers $Q_{i} = d_{i} P$ in the end.

$H_{2} {\hbox{-}}Query$

same as the Lemma 1.

$H_{3} {\hbox{-}}Query$

$H_{3}$same as the Lemma 1.

Public-Key-Extract

For each query on $PK_{i},$ if $j \ne J,$ ${\mathcal{C}}$ generates a usually key pair $\{ PK_{i},x_{i} \}$ and updates these corresponding list. Otherwise, ${\mathcal{C}}$ returns $PK_{j} \leftarrow aP,$ adds into the $L_{1}^{list}$ of tuple $\langle ID_{j},aP,Q_{j},d_{j} \rangle$ and the $L_{PK}^{list}$ of tuple $\langle ID_{i}, \bot,aP\rangle$.

Private-Key-Extract

For each query on $x_{i},$ if the $L_{PK}^{list}$ contain the corresponding entity, ${\mathcal{C}}$ adds it into the list $L_{SK}^{list}$ of tuple $\langle ID_{i},x_{i}, \bot \rangle$. If not, ${\mathcal{C}}$ makes a public key extraction query or fails this game at J-th query (denote event by E2).

Request-Partial-Private-Key

When ${\mathbb{A}}_{II}$ ask a partial private key query on identity $ID_{j},$ ${\mathcal{C}}$ goes through the $L_{1}^{list}$ and looks for these corresponding entities $\{ ID_{j},PK_{j} \},$ computes $Dj = d_{j} P_{pub},$ then adds tuple $\langle ID_{j},x_{j},D_{j} \rangle$ into the $L_{SK}^{list}$.

Signcrypt-Query

${\mathcal{C}}$ maintains the $L_{S}^{list}$ of tuple $\langle m,ID_{i},ID_{j},PK_{i},PK_{j},R_{1i},R_{2i},U_{i},V_{i},\tau_{i},h_{i},W_{i},T_{i} \rangle,$ where $\{ ID_{i},ID_{j} \}$ are the identity of sender and that of the receiver respectively. For each signcryption query, if $\{ i \ne J,x_{i} \ne \bot \},$ ${\mathcal{C}}$ answers this query and follow with the signcrypt algorithm as Sect. 3, then generates the signcrytion ciphertext $\sigma \leftarrow (h_{i},R_{2i},W_{i},T_{i} )$ as query result. If $\{ i = J,x_{i} = \bot \},$ ${\mathcal{C}}$ chooses $\{ r_{2}^{{}},h,T\} \in {}_{R}Z_{q}^{ * }$ randomly, and computes $R_{1} = TP - h_{i} PK_{i},$ $R_{2i} = r_{2} P,$ $U = x_{j} R,$ $V = \hat{e}(r_{2} Q_{j},P_{pub} ),$ then returns the result $\sigma \leftarrow (h_{i},R_{2i},W_{i},T_{i} )$.

Note that, this game fails and stops (denotes the event by E3), if $h_{{L_{3} }} \ne h_{{L_{S} }},$ where $\{ h_{{L_{3} }},h_{{L_{S} }} \}$ are the entity from the list $L_{3}^{list}$ and $L_{S}^{list}$ respectively.

Unsigncrypt-Query

For each unsigncryption query $\langle m,ID_{i},ID_{j},PK_{i},PK_{j},R_{1i},R_{2i},U_{i},V_{i},\sigma \rangle,$ where $\{ ID_{i},ID_{j} \}$ are the identity of sender and that of the receiver respectively, ${\mathcal{C}}$ works as follows. Firstly, it obtains the receiver’s partial private key $D_{j} = d_{j} P_{pub}$ and the sender’s identity hash value $Q_{i}$ corresponding to $\{ ID_{i},PK_{i} \}$ from the list $L_{1}^{list}$. Then, it executes the verification part of the unsigncryption algorithm as subsection 3.2, returns $\bot$ if the verification does not succeed. After that, if $ID_{j} = ID_{J},$ ${\mathcal{C}}$ fails and stop (denote event by E4). Otherwise, it go through list and looks for a different entity $K^{ * } \leftarrow (ID_{i},ID_{j},R_{1i},R_{2i},U_{i},V_{i} )$. If such an entity exists, ${\mathcal{C}}$ returns this result $m^{\prime}/ \bot \leftarrow Dec_{{K^{ * } }} (\sigma )$.

Challenge phase

${\mathcal{C}}$ generates two equal length plaintext $(m_{0},m_{1} )$ newly. And ${\mathbb{A}}_{II}$ picks two identities $ID_{S}^{ * }$ and $ID_{R}^{ * }$ on which it wishes to be challenged. If $ID_{R}^{ * } \ne ID_{J},$ ${\mathcal{C}}$ fails and stops (denote event by E5). Otherwise, it proceeds to construct a challenge as follows. It randomly chooses $m_{b} (b \in {}_{R}\{ 0,1\} )$ and $r_{2}^{ * } \in {}_{R}Z_{q}^{ * },$ computes $R_{1}^{ * } = bP,$ $U^{ * } = abP,$ $V^{ * } = \hat{e}(r_{2} Q_{J},P_{pub} )$. After that, it computes $\tau^{ * } = Enc_{{K^{ * } }} (m_{b} ),$ $T^{ * } = h^{ * } x_{S}^{ * } + r_{1}^{ * },$ $W^{ * } = h_{{}}^{ * } (D_{S} + cQ_{S} ),$ At last, ${\mathcal{C}}$ returns $\sigma^{ * } \leftarrow (h^{ * },R_{2}^{ * },W^{ * },T^{ * } )$ to ${\mathbb{A}}_{II}$ as the challenge ciphertext.

Guess phase

${\mathbb{A}}_{II}$ then performs a second series of queries which is treated in the same way as the first one (prohibit the Private - Key query). At the end of the simulation, it produces the guess of challenge ciphertext $m^{\prime}_{b}$ for which it believes the $h^{ * } \leftarrow (\tau^{ * },ID_{S}^{ * },ID_{R}^{ * },PK_{S}^{ * },PK_{R}^{ * },R_{1}^{ * },R_{2}^{ * },U^{ * },V^{ * } ),$ $e(W^{ * },P) = e(h^{ * } Q_{S},R_{2}^{ * } + P_{pub} ),$ $\sigma^{ * } \leftarrow Enc_{{K^{ * } }} (m^{\prime}_{b} )$ hold. Therefore, it wins this game if $b^{\prime} = b$ and game does not abortion. More precisely, ${\mathbb{A}}_{II}$ have non-negligible advantage in winning the $game_{{A_{II} }}^{IND - CCA2 - II}$ against our scheme, there exist an algorithm ${\mathcal{C}}$ which use ${\mathbb{A}}_{II}$ to solve the CDH problem such that:

$$ \begin{aligned} Adv_{scheme}^{IND - CCA2 - II} (A_{II} ) &= \varepsilon \cdot \Pr [\neg E1 \wedge \neg E2 \wedge \neg E3 \wedge \neg E4 \wedge \neg E5] \hfill \\ & \ge \varepsilon \cdot \frac{1}{{q_{1} }} \cdot \left( {1 - \frac{1}{{q_{2} }}} \right) \cdot \left( {1 - \frac{1}{{q_{sk} }}} \right) \cdot \left( {1 - \frac{{q_{S} (2q_{1} + q_{2} + q_{3} )}}{{2^{k} }}} \right)\left( {1 - \frac{{q_{un} }}{{2^{k} }}} \right) \hfill \\ \end{aligned} $$

Theorem 2

Under the CDH assumption and ECDL assumption, and the data encapsulation algorithm $(Enc,Dec)$ is confidentiality, we proposed scheme is Existentially Unforgeable Against Chosen Message Attacks (EUF-CMA) secure in the random oracle model. This theorem follows from Lemmas 3 and 4.

Lemma 3

We proposed scheme is EUF-CMA -I secure during the $game_{{A_{I} }}^{EUF - CMA - I},$ assuming that a PPT adversary $A_{I}$ has non-negligible advantage $\varepsilon$ in winning this game against our scheme. More precisely, there exist an algorithm ${\mathcal{C}}$ which uses $A_{I}$ to solve the CDH problem with probability:

$$ Adv_{scheme}^{EUF - CMA - I} (A_{I} ) \ge \varepsilon \cdot \frac{1}{{q_{1} }}\left( {1 - \frac{1}{{q_{2} }}} \right) \cdot \left( {1 - \frac{1}{{q_{pa} }}} \right) \cdot \left( {1 - \frac{{q_{S} (2q_{1} + q_{2} + q_{3} )}}{{2^{k} }}} \right) $$

here $q_{1},q_{2},q_{3},q_{pk},q_{sk},q_{pa},q_{S}\; {\text{and}} \; q_{un}$ denote the same as in Lemma 1.

Proof

In query phase, $A_{I}$ can ask a polynomially bounded number of queries adaptively again as Lemma 1 (prohibit the signcrypt-query). At the end of the simulation, $A_{I}$ outputs a group of challenge ciphertex $\sigma^{ * } \leftarrow (h^{ * },R_{2}^{ * },W^{ * },T^{ * } ),$ and ${\mathcal{C}}$ checks $ID_{S}^{ * } \ne ID_{J}$. If not, it aborts this game. Otherwise, it obtains $r_{2}^{ * }$ and $h^{ * }$ by calling the hash oracle and retrieves $Q_{S}$ from the list $L_{1}^{list}$ to computing the answer of CDH problem:

$$ \begin{aligned} \hat{e}(W^{ * },P) &= \hat{e}(h^{ * } Q_{S},R_{2}^{ * } + P_{pub} ) = \hat{e}(h^{ * } Q_{S},P_{pub} )\hat{e}(h^{ * } Q_{S},R_{2}^{ * } )\\ \hfill \hat{e}(W^{ * },P) &= \hat{e}(bP,aP)^{{h^{ * } }} \hat{e}(h^{ * } bP,r_{2}^{ * } P) \hfill \\ \hat{e}(abP,P) &= \hat{e}\left(\frac{{W^{ * } }}{{h^{ * } }} - r_{2}^{ * } Q_{S},P\right) \hfill \\ \end{aligned} $$

Thus ${\mathcal{C}}$ can recover $abP = \frac{{W^{ * } }}{{h^{ * } }} - r_{2}^{ * } Q_{S}$ as the return of the CDH problem. And $A_{I}$ has non-negligible advantage $\varepsilon$ in winning the $game_{{A_{I} }}^{EUF - CMA - I}$ against our scheme, an algorithm ${\mathcal{C}}$ to solve the CDH problem with probability:

$$ Adv_{scheme}^{EUF - CMA - I} (A_{I} ) \ge \varepsilon \cdot \frac{1}{{q_{1} }}\left( {1 - \frac{1}{{q_{2} }}} \right) \cdot \left( {1 - \frac{1}{{q_{pa} }}} \right) \cdot \left( {1 - \frac{{q_{S} (2q_{1} + q_{2} + q_{3} )}}{{2^{k} }}} \right) $$

Lemma 4

We proposed scheme is EUF-CMA -II secure during the $game_{{A_{II} }}^{EUF - CMA - II},$ assuming that a PPT adversary ${\mathbb{A}}_{II}$ has non-negligible advantage $\varepsilon$ in winning this game against our scheme. More precisely, there exist an algorithm an algorithm ${\mathcal{C}}$ which uses ${\mathbb{A}}_{II}$ to solve the ECDL problem with probability:

$$ Adv_{scheme}^{IND - CCA2 - II} (A_{II} ) \ge \varepsilon \cdot \frac{1}{{q_{1} }} \cdot \left( {1 - \frac{1}{{q_{2} }}} \right) \cdot \left( {1 - \frac{1}{{q_{sk} }}} \right) \cdot \left( {1 - \frac{{q_{S} (2q_{1} + q_{2} + q_{3} )}}{{2^{k} }}} \right) $$

here $q_{1},q_{2},q_{3},q_{pk},q_{sk},q_{pa},q_{S} \; {\text{and}}\; q_{un}$ denote the same as in Lemma 1.

Proof

The proof program is same as the Lemmas 2 and 3.

5 Efficiency of Our Scheme

Since computational overhead and ciphertext size are two important factors affecting the efficiency, we present the compassion with the existing CLSC schemes in this section [10, 12, 17, 18]. In view of the computation cost, we focus on the costly operations and omit the computation efforts which can be pre-computed. Note that, the pairing operations is several times more expensive than other operation [24, 25]. And we use Mult, Exp and Pair as abbreviations for point multiplications, exponentiations and pairing computations respectively. We also use $\left| G \right|,\left| r \right|$ and $\left| m \right|$ to denote the size of an element in G ₁ , and the size of an element in finite field $Z_{q}^{ * }$ and the length if message m. From Table 1, we can observe that communication overhead and computational cost of our scheme are more efficient than the relating schemes.

Table 1 efficiency comparison with other schemes

6 Conclusion

In this paper, we have discussed a practical certificateless hybrid signcryption scheme, which not only can signcrypt arbitrary length data, but also can guarantee scheme efficiently against the public-key-replacement attacks by using the technique of the public key binding in the extract-partial-private-key. Furthermore, this scheme has been proved its confidentiality and unforgeable in the random oracle model. According to the comparison with other related schemes, the new scheme is efficient and practical.