An Identity-Based Ring Signcryption Scheme

Abstract

Signcryption enables a user to perform digital signature for providing authenticity and public key encryption for providing message confidentiality simultaneously in a single logical step with a cost lesser than sign-then- encrypt approach. As the concept of ring signcryption emerged, various practical applications like electronic transaction protocol and key management protocols, felt the requirement of signer’s privacy, which was lacking in normal signcryption schemes. Without revealing the users’ identity of the ring signcryption can provide confidentiality and authenticity both. In this paper, we present a new ID-based ring signcryption scheme, motivated to the scheme provided by Zhu et al. [1]. Selvi et al. [2] and Wang et al. [3] found some security flaws in the Zhu’s scheme [1], which is being considered and repaired in this paper. The proposed scheme is proven to be secure against adaptive chosen ciphertext ring attacks (IND-IDRSC-CCA2) and secure against an existential forgery for adaptive chosen message attacks (EF-IDRSC-ACMA).

1 Introduction

The idea behind Identity-based Ring Signcryption is a collaboration of different security techniques, such as Identity Based Cryptography, Ring Signature and Signcryption. Identity based cryptography provides a variant to Certificate based public key cryptography; ring signature provides anonymity along with the authenticity in such a way that even verifier does not know who has signed the message but he can verify that one of the ring member has signed it, while signcryption provides the encryption and signature in a single logical step to obtain confidentiality, integrity, authentication and non-repudiation.The concept of identity-based cryptography was introduced by Shamir [4] in 1984, to remove the need of certification of the public keys, which is required in the conventional public key cryptography setting. But, Shamir only proposed ID-based signature and left the ID-based encryption as an open problem. Boneh and Franklin [5] presented the first Identity Based Encryption scheme that uses bilinear maps (the Weil or Tate pairing) over super singular elliptic curves. Rivest et al. [6] introduced ring signature which is a group oriented signature with privacy concerns: a user can anonymously sign a message on behalf of a group of spontaneously conscripted users, without managers including the actual signer. The first ID-based ring signature scheme with bilinear parings, was proposed by Zhang and Kim [7]. Yuliang Zheng [8] introduced the concept of public key signcryption which fulfils both the functions of digital signature and public key encryption in a logically single step, and with a cost lower than that required by the sign-then- encrypt approach. However, Zheng didn’t prove any security notions which was further proposed by Baek et al. [9], described a formal security model in a multi-user setting.

Xinyi Huang [10] combined the concepts of ID-based ring signature and signcryption together as identity-based ring signcryption. They provided a formal proof of their scheme with the chosen ciphertext security (IND-IDRSC-CCA) under the Decisional Bilinear Diffie-Hellman assumption. However, Huang et al.’s [10] scheme is computationally inefficient, since the number of pairing computations grows linearly with the group size. Huang et al.’s scheme needs n + 4 pairing computations, where n denotes the size of the group. The scheme lacks anonymity and had a key escrow problem as the scheme was based on ID-PKC. Wang et al. [11] eliminated the key escrow problem in [10] by proposing a verifiable certificate-less ring signcryption scheme and gave a formal security proof of the scheme in random oracle model. But this scheme also needs n + 4 pairing computations. The problem of ID-based ring signcryption schemes is that they are derived from bilinear pairings, and the number of pairing computations grows linearly with the group size. Zhu [1] solved the above problem; they proposed an efficient ID-based ring signcryption scheme, which only takes four pairing operations for any group size. Zhu [12] proposed an ID-based ring signcryption scheme, which offers savings in the ciphertext length and the computational cost.

The other schemes include Li et al. [13], Yong et al. [14] and Zhang [15]. Selvi et al. [2] proved that Li et al. [16] and Zhu et al. scheme [1] are not secure against adaptive chosen ciphertext attack while Zhu’s [12] scheme and Yong’s [14] scheme are not secure against chosen plaintext attack. Qi’s [17] proved that their scheme has the shortest ciphertext and is much more efficient than Huang’s [10] and Selvi’s [2] scheme. Selvi et al. [18] proved that Zhang et al. [19] scheme is insecure against confidentiality, existential unforgeability and anonymity attacks. Zhou [20] presented an efficient identity-based ring signcryption scheme in the standard model.

Roadmap: The remaining paper is organized as follows: Sect. 2 gives some preliminaries and basic definitions of Bilinear Pairing. The formal model has been discussed in Sect. 3. In Sect. 4, we propose our ID-based ring signcryption scheme; security analysis of the proposed scheme is discussed in Sect. 5. In Sect. 6, we concluded the remarks about the paper.

2 Preliminaries

2.1 Notations Used

The following notations have been made in common for all the existing schemes and Table 1 defines the description of the notations that have been used throughout the paper.

Table 1 Notations used

2.2 Basic Concepts on Bilinear Pairing

Let $G_{1}$ be a cyclic additive group generated by P of prime order q, and $G_{2}$ be a cyclic multiplicative group of the same order q. Let a and b be elements of $Z_{q}^{*}$. Assume that the discrete logarithm problem (DLP) in both $G_{1}$ and $G_{2}$ is hard. Let $\hat{e}:G_{1} \, \times \,G_{1} \, \to \,G_{2}$ be a bilinear pairing with the following properties shown in Table 2.

Table 2 Properties of bilinear mapping

3 Formal Model of Identity Based Ring Signcryption

A generic ID-based ring signcryption scheme consists of five algorithms Setup, Keygen, Signcrypt, Unsigncrypt and Consistency. The description of these algorithms has been provided in Table 3.

Table 3 Generic identity based ring signcryption scheme

4 Proposed Scheme

In this section, we propose our new Identity-Based Ring signcryption Scheme. Our scheme has four following algorithms:

• 1. Setup ($k$): Given a security parameter $k$, a trusted private key generator (PKG) generates the system’s public parameters $params$ and the corresponding master secret key $t$ that is kept secret by PKG.

  • a. The trusted authority randomly chooses $t \in_{R} Z_{q}^{*}$ keeps it as a master key and computes the corresponding public key $P_{pub} \, = \,tP$.

  • b. Let $(G_{1} , + )$ and $(G_{2} ,*)$ be two cyclic groups of prime order $q\, > \,2^{k}$ and a random generator $P \in G_{1}$.

  • c. $e:G_{1} \, \times \,G_{1} \, \to \,G_{2}$ is a bilinear pairing.

  • d. Choose Hash Functions

    $$ H_{1} :\{ 0,1\}^{*} \to G_{1} ,H_{2} :G_{2} \to \{ 0,1\}^{l} ,H_{3} :\{ 0,1\}^{*} \to Z_{q}^{*} ,H_{4} :\{ 0,1\}^{*} \to \{ 0,1\}^{l} $$

  • e. The public parameters are:$params = \{ G_{1} ,G_{2} ,e,q,P,P_{pub} ,H_{1} ,H_{2} ,H_{3} ,H_{4} \}$.

• 2. Keygen ($ID_{i}$): Given a user identity $ID_{i}$ of user $U_{i}$, the PKG, using the public key computes the parameters $params$ and the master secret key $t$, computes the corresponding private key $S_{i}$, and transmits it to $ID_{i}$ in a secure way as follows.

  • a. The public key is computed as $Q_{i} \, = \,H_{1} (ID_{i} )$.

  • b. The corresponding private key $S_{i} \, = \,tQ_{i}$.

  • c. PKG sends $S_{i}$ to user $U_{i}$ via a secure channel.

• 3. Signcrypt: Let $\mathcal{L}\, = \,\left\{ {ID_{1} , \ldots ,ID_{n} } \right\}$ be a set of n ring members, such that $ID_{S} \in \mathcal{L}$. $ID_{R}$ may or may not be in $\mathcal{L}$. The sender runs this algorithm to send a message $m \in M$, where $M$ is a message space, to a receiver with identity $ID_{R}$, the senders private key $S_{S}$, outputs a ring signcryption ${\mathbb{C}}$ as follows:

  • a. Choose a random number $r \in_{R} Z_{q}^{*}$ and $m^{*} \in_{R} M$.And compute $R_{0} \, = \,rP$, $R\, = \,e\left( {rP_{pub} ,Q_{R} } \right)$, $k\, = \,H_{2} \left( R \right)$, ${\mathbb{C}}_{1} \, = \,m^{*} \oplus k$

  • b. Choose $R_{i} \in G_{1} \, \forall \, i\, = \,\{ 1,2, \ldots ,n\} \backslash \{ S\}$ and compute $h_{i} \, = \,H_{3} (m||\mathcal{L}||R_{i} ||R_{0} )$.

  • c. Choose $r_{S} \in_{R} Z_{q}^{*} \, \forall \, i = S$ Compute $R_{S} \, = \,r_{S} Q_{S} \, - \,\sum\limits_{i \ne S} {\left( {R_{i} \, + \,h_{i} Q_{i} } \right)}$, $h_{S} \, = \,H_{3} (m||\mathcal{L}||R_{S} ||R_{0} )$, $V\, = \,\left( {h_{S} + r_{S} } \right)S_{S}$, ${\mathbb{C}}_{2} \, = \,\left( {m||r_{S} ||V} \right) \oplus H_{4} (m^{*} ||R_{0} )$.

  • d. Finally the sender outputs the ciphertext as $\sigma \, = \,(\mathcal{L},R_{0} ,R_{1} , \ldots ,R_{n} ,{\mathbb{C}}_{1} ,{\mathbb{C}}_{2} )$to the receiver.

• 4. Unsigncrypt: This algorithm is executed by a receiver $ID_{R}$. This algorithm takes the ring signcryption $\sigma$, the ring members $\mathcal{L}$ and the private key $S_{R}$, as input and produces the plaintext $m$, if $\sigma$ is a valid ring signcryption of $m$ from the ring $\mathcal{L}$ to $ID_{R}$ or ‘invalid’, if $\sigma$ is an invalid ring signcryption as follows:

  • a. Compute $R^{\prime}\, = \,e(R_{0} ,S_{R} ),k^{\prime}\, = \,H_{2} (R^{\prime}),m^{{\prime}^{*}} \, = \,{\mathbb{C}}_{1} \oplus k^{\prime}$

  • b. Recover $m^{\prime}$, $V^{\prime}$ as $\left( {m^{\prime}||r_{S} ||V^{\prime}} \right)\, = \,{\mathbb{C}}_{2} \oplus H_{4} (m^{\prime^{*}} ||R_{0} )$.

  • c. Compute $h_{i}^{\prime } \, = \,H_{3} (m^{\prime}||\mathcal{L}||R_{i} ||R^{\prime}) \, \forall \, i\, = \,\{ 1,2, \ldots ,n\}$

  • d. Checks if $e(P,V^{\prime})\,\mathop = \limits^{?} \,e\left( {P_{pub} ,\sum\limits_{i = 1}^{n} {(R_{i} + h_{i} Q_{i} )} } \right)$. If the check succeeds accept $m$, else return $\bot$.

5 Security Analyses of the Proposed Scheme

5.1 Correctness

In this section, a proof of correctness has been shown, that if the ciphertext ${\mathbb{C}}$ has been correctly generated, the verification equations will hold.

If $e(P,V^{\prime})\,\mathop = \limits^{?} \,e\left( {P_{pub} ,\sum\limits_{i = 1}^{n} {(R_{i} + h_{i} Q_{i} )} } \right)$ holds.

Proof: $\begin{aligned} e\left( {P,V} \right)\, = & \,e\left( {P,\left( {h_{S} \, + \,r_{S} } \right)S_{S} } \right)\, = \,e\left( {P,\left( {h_{S} \, + \,r_{S} } \right)tQ_{S} } \right)\, = \,e\left( {tP,h_{S} Q_{S} \, + \,R_{S} \, + \,\sum\limits_{i = 1,i \ne s}^{n} {\left( {R_{i} \, + \,h_{i} Q_{i} } \right)} } \right) \\ \, = e\left( {P_{pub} ,\sum\limits_{i = 1}^{n} {\left( {R_{i} \, + \,h_{i} Q_{i} } \right)} } \right) \\ \end{aligned}$

5.2 Security Analyses

5.2.1 Confidentiality

Theorem:

If an IND-IRSC-CCA2 adversary $\mathcal{A}$ has an advantage $\varepsilon$ against IRSC scheme, asking hash queries to random oracles $\mathcal{O}_{{H_{i} }} \left( {i\, = \,1,\;2,\;3,\;4} \right)$, $q_{e}$ extract queries ($q_{e} \, = \,q_{{e_{1} }} \, + \,q_{{e_{2} }}$, where $q_{{e_{1} }}$ and $q_{{e_{2} }}$ are the number of extract queries in the first phase and second phase respectively), $q_{sc}$ signcryption queries and $q_{us}$ unsigncryption queries, then there exist an algorithm $\mathcal{C}$ that solves the CBDH problem with advantage $\varepsilon \left( {\frac{1}{{q_{{H_{1} }} q_{{H_{2} }} }}} \right)$.

5.2.2 Unforgeability

Theorem:

An identity based ring signcryption scheme (IRSC) is said to be existentially unforgeable against adaptive chosen message attack (EUF-IRSC-CMA), against any polynomially bounded adversary $\mathcal{A}$ under the random oracle model if CDHP is hard.

6 Conclusion

Wang et al. [25] proved that the Zhu et al. scheme [1] to be insecure against anonymity and also does not satisfy the property of unforgeability. Selvi el al [2] also attacked and proved the scheme prone to confidentiality attack. Till now, a very few ID-based ring signcryption schemes have been proposed and most of them have been proved insecure. In this paper an efficient ID based ring signcryption scheme has been presented which has been proven secure against the primitive properties of signcryption: confidentiality, unforgeability and anonymity. The future work may include ring signcryption schemes in combination with ID-based threshold signcryption, ID-based proxy signcryption and id based hybrid signcryption schemes and certificate-less schemes in the standard model. Also, to reduce communication overhead, constant ciphertext size ring signcryption schemes can be improved.