An ID-based proxy signature schemes without bilinear pairings

Abstract

The proxy signature schemes allow proxy signers to sign messages on behalf of an original signer, a company, or an organization. Such schemes have been suggested for use in a number of applications, particularly in distributed computing, where delegation of rights is quite common. Many identity-based proxy signature schemes using bilinear pairings have been proposed. But the relative computation cost of the pairing is approximately twenty times higher than that of the scalar multiplication over elliptic curve group. In order to save the running time and the size of the signature, in this letter, we propose an identity-based signature scheme without bilinear pairings. With the running time being saved greatly, our scheme is more practical than the previous related schemes for practical application.

1 Introduction

In order to simplify the public-key authentication, Shamir [1] introduced the concept of identity-based (ID-based) cryptosystem problem. In this system, each user needs to register at a key generator center (KGC) with identity of himself before joining the network. Once a user is accepted, the KGC will generate a private key for the user and the user’s identity (e.g., user’s name or email address) becomes the corresponding public key. In this way, in order to verify a digital signature or send an encrypted message, a user only needs to know the “identity” of his communication partner and the public key of the KGC.

Mambo et al. [2] introduced the notion of proxy signature scheme. A proxy signature scheme allows an entity called original signer to delegate his signing capability to another entity, called proxy signer. Since it is proposed, the proxy signature schemes have been suggested for use in many applications, particularly in distributed computing where delegation of rights is quite common. In order to adapt different situations, many proxy signature variants are produced, such as one-time proxy signature, proxy blind signature, multi-proxy signature, and so on. Since the proxy signature appears, it attracts many researchers’ great attention. Using bilinear pairings, people proposed many new ID-based signature schemes [3–5] and ID-based proxy signature (IBPS) scheme [6–10]. All the above IBPS schemes are very practical, but they are based on bilinear pairings and the pairing is regarded as the most expensive cryptography primitive. The relative computation cost of a pairing is approximately twenty times higher than that of the scalar multiplication over elliptic curve group [11]. Therefore, IBPS schemes without bilinear pairings would be more appealing in terms of efficiency.

In this paper, we present an IBPS scheme without pairings. The scheme rests on the elliptic curve discrete logarithm problem (ECDLP).With the pairing-free realization, the scheme’s overhead is lower than that of previous schemes [6–10] in computation.

2 Preliminaries

2.1 Background of elliptic curve group

Let the symbol E/F _p denote an elliptic curve E over a prime finite field F _p , defined by an equation

$$ {y^2} = {x^3} + ax + b,\,a,b \in {F_p} $$

(1)

and with the discriminant

$$ \Delta = 4{a^3} + 27{b^2} \ne 0. $$

(2)

The points on E/F _p together with an extra point O called the point at infinity form a group

$$ \mathfrak{G} = \left\{ {\left( {x,y} \right):x,y \in {F_p},E\left( {x,y} \right) = 0} \right\} \cup \left\{ O \right\}. $$

(3)

Let the order of $\mathfrak{G}$ be n. $\mathfrak{G}$ is a cyclic additive group under the point addition “+” defined as follows: Let P, Q ∊ G, l be the line containing P and Q (tangent line to E/F _p if P = Q), and R, the third point of intersection of l with E/F _p . Let l′ be the line connecting R and O. Then P “+” Q is the point such that l′ intersects E/F _p at R and O and P “+” Q. Scalar multiplication over E/F _p can be computed as follows:

$$ tP = P + P + \ldots + P\left( {t{\hbox{ times}}} \right) $$

(4)

The following problems defined over $\mathfrak{G}$ are assumed to be intractable within polynomial time.

Eliptic curve discrete logarithm problem: For $x{ \in_R}Z_n^{*}$ and G the generator of G, given P = x ⋅ $\mathfrak{G}$ compute x.

2.2 ID-based proxy signatures

In this paper, unless stated otherwise, let O be the original signer with identity ID _O and private key D _O . He delegates his signing rights to a proxy signer A with identity ID _A and private key D _A . A warrant is used to delegate signing right. In [6], Gu and Zhu gave a formal security model for ID-based proxy signature schemes.

Definition 1

An ID-based proxy signature scheme is specified by the following polynomial-time algorithms with the following functionalities [6].

• Setup: The parameters generation algorithm, takes as input a security parameter k, and returns a master secret key x and system parameters Ω. This algorithm is performed by KGC.

• Extract: The private key generation algorithm, takes an identity ID _U  ∊ {0, 1}^*as input, and outputs the secret key D _U corresponding to ID _U . KGC uses this algorithm to extract the users’ secret keys.

• Delegate: The proxy-designation algorithm, takes O’s secret key D _O and a warrant m _ω as input, and outputs the delegation W _O→A .

• DVerify: The designation-verification algorithm, takes ID _O , W _O→A as input and verifies whether W _O→A is a valid delegation come from O.

• PKgen: The proxy key generation algorithm, takes W _O→A and some other secret information z (for example, the secret key of the executor) as input, and outputs a signing key D _p for proxy signature.

• PSign: The proxy signing algorithm, takes a proxy signing key D _p and a message m ∊ {0, 1}^* as input, and outputs a proxy signature (m, δ).

• PVerify: The proxy verification algorithm, takes ID _O , ID _A and a proxy signature (m, δ) as input, and outputs 0 or 1. In the later case, (m, δ) is a valid proxy signature of O.

We consider an adversary $\mathfrak{A}$ which is assumed to be a probabilistic Turing machine which takes as input the global scheme parameters and a random tape.

Definition 2

For an ID-based proxy signature scheme IBPS, we define an experiment ${\hbox{Exp}}_F^{\rm{IBPS}}(k)$ of adversary $\mathfrak{A}$ and security parameter k as follows [6]:

• 1. A challenger C runs Setup and gives the system parameters Ω to $\mathfrak{A}$.

• 2. C _list ← ϕ, D _list ← ϕ, G _list ← ϕ, S _list ← ϕ. (ϕ means null.)

• 3. Adversary $\mathfrak{A}$ can make the following requests or queries adaptively.

  • Extract(.): This oracle takes a user’s ID _i as input, and returns the corresponding private key D _i . If $\mathfrak{A}$ gets D _i  ← Extract(ID _i ), let C _list ← C _list ∪ {(ID _i , D _i )}.

  • Delegate(.): This oracle takes the designator’s identity ID and a warrant m _w as input, and outputs a delegation W. If $\mathfrak{A}$ gets W ← Delegate(ID, m _w ), let D _list ← D _list ∪ {(ID, m _w , W)}.

  • PKgen(.): This oracle takes the proxy signer’s ID and a delegation W as input, and outputs a proxy signing key D _p . If $\mathfrak{A}$ gets D _p  ← PKgen(ID, W), let G _list ← G _list ∪ {(ID, m _w , W)}.

  • PSign(.): This oracle takes the delegation W and message m ∊ {0, 1}^*as input, and outputs a proxy signature created by the proxy signer. If $\mathfrak{A}$ gets (m, τ) ← PSign(W, m), let S _list ← S _list ∪ {(m, τ)}.

• 4. $\mathfrak{A}$ outputs (ID, m _w , W) or (W, m, τ).

• 5. If $\mathfrak{A}$’s output satisfies one of the following terms, $\mathfrak{A}$’s attack is successful.

  • The output is (ID, m _w , W), and satisfies: DVerify(W, ID) = 1, (ID,⋅) ∉ C _list, (ID,⋅) ∉ G _list and (ID, m _w ,⋅) ∉ D _list. ${\hbox{Exp}}_F^{\rm{IBPS}}(k)$ returns 1.

  • The output is (W, m, τ), and satisfies PVerify((m, τ), ID _i , ID _j ) = 1, (W, m,⋅) ∉ S _list and (ID _j ,⋅) ∉ C _list (ID _j , W,⋅) ∉ G _list, where ID _i and ID _j are the identities of the designator and the proxy signer defined by W, respectively. ExpID ${\hbox{Exp}}_F^{\rm{IBPS}}(k)$ returns 2.

Otherwise, ${\hbox{Exp}}_F^{\rm{IBPS}}(k)$ returns 0.

Definition 3

[6]. An ID-based proxy digital signature scheme IBPS is said to be existential delegation and signature unforgeable under adaptive chosen message and ID attacks (DS-EUF-ACMIA), if for any polynomial-time adversary $\mathfrak{A}$, ${ \Pr }\left[ {{\hbox{Exp}}_F^{\rm{IBPS}}(k) = {1}} \right]$ and ${ \Pr }\left[ {{\hbox{Exp}}_F^{\rm{IBPS}}(k) = {2}} \right]$ are negligible.

3 Our scheme

3.1 Scheme description

In this section, we present an ID-based proxy signature scheme without pairing. Our scheme rests on the ECDLP.

Setup

Takes a security parameter k, returns system parameters and a master key. Given k, KGC does as follows.

• 1) Choose a k-bit prime p and determine the tuple {F _p , E/F _p , G, P} as defined in Section 2.

• 2) Choose the master private key $x \in Z_n^{*}$ and compute the master public key P _pub = x⋅P.

• 3) Choose two cryptographic secure hash functions ${H_{{1}}}:{\left\{ {0,{ 1}} \right\}^{*}} \to {Z_n}^{*}$ and ${H_{{2}}}:{\left\{ {0,{ 1}} \right\}^{*}} \times G \to {Z_p}^{*}$.

• 4) Publish {F _p , E/F _p , G, P, P _pub, H ₁, H ₂} as system parameters and keep the master key x secretly.

Extract

Takes system parameters, master key, and a user’s identifier as input, returns the user’s ID-based private key. With this algorithm, KGC works as follows for each user U with identifier ID _U .

• 1) Choose at random ${r_U} \in Z_n^{*}$, compute R _U  = r _U ⋅P and h _U  = H ₁(ID _U , R _U ).

• 2) Compute ${D_U} = {r_U} + {h_U}x$.

U’s private key is the tuple (D _U , R _U ) and is transmitted to U via a secure out-of-band channel. U can validate her private key by checking whether the equation

$$ {D_U} \cdot P = {R_U} + {h_U} \cdot {P_{\rm{pub}}} $$

(5)

holds. The private key is valid if the equation holds and vice versa.

Delegate

Takes O’s secret key D _O and a warrant m _ω as input, and outputs the delegation W _O→A . As shown in Fig. 1, the user O does as the follows.

Fig. 1

The process of Delegate, DVerify, and PKgen

• 1) Generate a random a and compute K = a⋅P.

• 2) Compute e ₁ = H ₂(m _w , K, ID _A ) and $\sigma = {e_1}{D_O} + a\bmod n$.

The delegation is W _O→A =(ID _O , R _O , ID _A , m _w , K, σ).

DVerify

As shown in Fig. 1, to verify the delegation W _O→A for message m _w , the user A first computes e ₁ = H ₂(m _w , K, ID _A ), h _O  = H ₁(ID _O , R _O ) and then checks whether

$$ \sigma \cdot P = {e_1}\left( {{R_O} + {h_O} \cdot {P_{\rm{pub}}}} \right) + K $$

(6)

Accept if it is equal. Otherwise reject.

PKgen

If A accepts the delegation W _O→A , as shown in Fig. 1, he computes the proxy signing key D _p as ${D_p} = \sigma + {D_A}{e_2}\bmod n$, where e ₂ = H ₂(m _w , K, ID _O ).

Sign

Takes system parameters, the proxy signing key D _p and a message m as inputs, returns a signature of the message m. The user A does as follows.

• 1) Choose at random b ∊ Z _n ^* to compute R = b⋅P.

• 2) Compute h = H ₂(m, R).

• 3) Verify whether the equation gcd (b + h, n) = 1 holds: Continue if it does and return to step 1 otherwise.

• 4) Compute $s = {\left( {l + h} \right)^{{ - 1}}}{D_p}\bmod n$.

• 5) The resulting signature is (ID _O , R _O , ID _A , R _A , m _w , K, σ, R, s).

Verify

To verify the signature (ID _O , R _O , ID _A , R _A , m _w , K, σ, R, s) for message m, a verifier first checks if the proxy signer and the message conform to m _w , then he computes, h _O = H ₁(ID _O , R _O ),h _A  = H ₁(ID _A , R _A ), e ₁ = H ₂(m _w , K, ID _A ), e ₂ = H ₂(m _w , K, ID _O ), h = H ₂(m, R), and then checks whether

$$ s\left( {R + h \cdot P} \right) = {e_1}\left( {{R_O} + {h_O} \cdot {P_{\rm{pub}}}} \right) + {e_2}\left( {{R_A} + {h_A} \cdot {P_{\rm{pub}}}} \right) + K $$

(7)

Accept if it is equal. Otherwise reject.

Since R = b⋅P and $s = {\left( {b + h} \right)^{{ - 1}}}{D_p}\bmod n$, we have

$$ \begin{gathered} s \cdot \left( {R + h \cdot P} \right) = {\left( {b + h} \right)^{{ - 1}}} \cdot {D_p} \cdot \left( {b \cdot P + h \cdot P} \right) = {\left( {b + h} \right)^{{ - 1}}} \cdot {D_p} \cdot \left( {b + h} \right) \cdot P \hfill \\= {D_p} \cdot P = \left( {\sigma + {D_A}{e_2}} \right)P = \sigma \cdot P + {e_2}{D_A} \cdot P \hfill \\= {e_1}\left( {{R_O} + {h_O} \cdot {P_{\rm{pub}}}} \right) + K + {e_2}\left( {{R_A} + {h_A} \cdot {P_{\rm{pub}}}} \right) \hfill \\\end{gathered} $$

(8)

Then the correctness of our scheme is proved.

3.2 Security analysis

Assume there is an adversary $\mathfrak{A}$ who can break our ID-based proxy signature scheme Σ. We will construct a polynomial-time algorithm $\mathfrak{F}$ that, by simulating the challenger and interacting with $\mathfrak{A}$, solves the ECDLP.

Theorem 1

Consider an adaptively chosen message attack in the random oracle model against Σ. If there is an attacker $\mathfrak{A}$ that can break Σ with at most ${q_{{{H_2}}}}$ H ₂-queries and q _S signature queries within time bound t and non- negligible probability ε. Then we can solve the ECDLP with non-negligible probability.

Proof Suppose that there is an attacker $\mathfrak{A}$ for an adaptively chosen message attack against Σ. Then, ${ \Pr }\left[ {{\hbox{Exp}}_F^{\rm{IBPS}}(k) = {1}} \right]$ or ${ \Pr }\left[ {{\hbox{Exp}}_F^{\rm{IBPS}}(k) = {2}} \right]$ are non-negligible. We show how to use the ability of $\mathfrak{A}$ to construct an algorithm $\mathfrak{F}$ solving the ECDLP.

Suppose $\mathfrak{F}$ is challenged with a ECDLP instance (P, Q) and is tasked to compute $x \in Z_n^{*}$ satisfying Q = x P. To do so, $\mathfrak{F}$ sets {F _p , E/F _p , G, P, P _pub = Q, H ₁, H ₂} as the system parameter and answers $\mathfrak{A}$’s queries (described in definition 2) as follows.

Extract-query: $\mathfrak{A}$ is allowed to query the extraction oracle for an identity ID _U . S simulates the oracle as follows. It chooses ${a_U},\,{b_U} \in Z_n^{*}$ at random and sets

$$ {R_U} = {a_U} \cdot {P_{\rm{pub}}} + {b_U} \cdot P,\,{D_U} = {b_U},\,{h_U} = {H_1}\left( {I{D_U},{R_U}} \right) \leftarrow - {a_U}\bmod n. $$

(9)

Note that (D _U , R _U ) generated in this way satisfies the equation ${D_U} \cdot P = {R_U} + {h_U} \cdot {P_{\rm{pub}}}$ in the extract algorithm. It is a valid secret key. F outputs (D _U , R _U , h _U ) as the secret key of ID _U and stores the value of (D _U , R _U , h _U ) in the C _list-table(we modify the content of C _list-table).

Delegate-query: $\mathfrak{A}$ queries the delegate oracle for a warrant m _w , ID _O and ID _A , $\mathfrak{F}$ first checks that whether ID _O and ID _A have been queried for the extraction oracle before. If yes, it just retrieves (D _O , R _O , h _O ) from the table and uses these values to delegate a warrant m _w , according to the delegate algorithm described in the scheme. It outputs the delegation W _O→A  = (ID _O , R _O , ID _A , m _w , K, σ) for m _w , ID _O and ID _A and stores the value W _O→A in the hash table D_list for consistency. If ID _O or ID _A has not been queried to the extraction oracle, $\mathfrak{F}$ executes the simulation of the extraction oracle and uses the corresponding secret key to sign the message.

Since $\mathfrak{F}$ knows every user’s private key(described in Extract-query), he can simulate Delegate-query, DVerify-query, PKgen-query, PSign-query, and PVerify-query as he simulates Delegate-query.

1. If $\mathfrak{A}$ can forge a valid delegation on warrant m _w with the probability $\varepsilon \geqslant 10\left( {{q_{{{H_2}}}} + 1} \right)\left( {{q_{{{H_2}}}} + {q_S}} \right)/{2^k}$, i.e. $\Pr \left[ {{\hbox{Exp}}_F^{\rm{IBPS}}(k) = 1} \right] \geqslant 10\left( {{q_{{{H_2}}}} + 1} \right)\left( {{q_{{{H_2}}}} + {q_S}} \right)/{2^k}$, where m _w has not been queried to the signature oracle, then a replay of $\mathfrak{F}$ with the same random tape but different choice of H ₂ will output two valid delegation (ID _O , R _O , ID _A , m _w , K, σ, e ₁) and $\left( {I{D_O},{R_O},I{D_A},{m_w},K,\sigma \prime,e_1^{\prime}} \right)$. Then we have

$$ \sigma \cdot P = {e_1}\left( {{R_O} + {h_O} \cdot {P_{\rm{pub}}}} \right) + K, $$

(10)

and

$$ \sigma \prime \cdot P = {e\prime_1}\left( {{R_O} + {h_O} \cdot {P_{\rm{pub}}}} \right) + K. $$

(11)

Let K = a P, ${R_O} = {a_O} \cdot {P_{\rm{pub}}} + {b_O} \cdot P$, ${P_{\rm{pub}}} = Q = x \cdot P$, then we have

$$ \sigma \cdot P = {e_1}\left( {{a_O} \cdot {P_{\rm{pub}}} + {b_O} \cdot P + {h_O} \cdot {P_{\rm{pub}}}} \right) + a \cdot P, $$

(12)

and

$$ \sigma \prime \cdot P = {e\prime_1}\left( {{a_O} \cdot {P_{\rm{pub}}} + {b_O} \cdot P + {h_O} \cdot {P_{\rm{pub}}}} \right) + a \cdot P. $$

(13)

then we have

$$ \sigma \cdot P = {e_1} \cdot {a_O} \cdot x \cdot P + {e_1} \cdot {b_O} \cdot P + {e_1} \cdot {h_O} \cdot x \cdot P + a \cdot P, $$

(14)

and

$$ \sigma \prime \cdot P = {e\prime_1} \cdot {a_O} \cdot x \cdot P + {e\prime_1} \cdot {b_O} \cdot P + {e\prime_1} \cdot {h_O} \cdot x \cdot P + a \cdot P. $$

(15)

Hence, we have

$$ \left( {{e_1} \cdot {a_O} + {e_1} \cdot {h_O} - {{e\prime}_1} \cdot {a_O} - {{e\prime}_1} \cdot {h_O}} \right) \cdot x \cdot P = \left( {\sigma - \sigma \prime - {e_1} \cdot {b_O} + {{e\prime}_1} \cdot {b_O}} \right) \cdot P $$

(16)

Let $u = {\left( {{e_1} \cdot {a_O} + {e_1} \cdot {h_O} - {{e\prime}_1} \cdot {a_O} - {{e\prime}_1} \cdot {h_O}} \right)^{{ - 1}}}\bmod n$ and $v = \left( {\sigma - \sigma \prime - {e_1} \cdot {b_O} + {{e\prime}_1} \cdot {b_O}} \right)\bmod n$, then, we get $x = uv\bmod n$. According to [12, Lemma 4], the ECDLP can be solved with probability ε′ ≥ 1/9 and time $t\prime \leqslant 23{q_{{{H_2}}}}t/\varepsilon$.

2. From case 1, we know the adversary $\mathfrak{A}$ cannot generate a valid delegation. In this case we will prove, if $\mathfrak{A}$ can forge a valid signature on message m under the delegation W _O→A =(ID _O , R _O , ID _A , m _w , K, σ) with the probability $\varepsilon \geqslant 10\left( {{q_{{{H_2}}}} + 1} \right)\left( {{q_{{{H_2}}}} + {q_S}} \right)/{2^k}$, i.e. $\Pr \left[ {{\hbox{Exp}}_F^{\rm{IBPS}}(k) = 2} \right] \geqslant 10\left( {{q_{{{H_2}}}} + 1} \right)\left( {{q_{{{H_2}}}} + {q_S}} \right)/{2^k}$, where m has not been queried to the signature oracle, then a replay of $\mathfrak{F}$ with the same random tape but different choice of H ₂ will output two valid signatures (ID _O , R _O , ID _A , R _A , m _w , K, σ, R, s, e ₁, e ₂, h), and (ID _O , R _O , ID _A , R _A , m _w , K, σ′, R, s, e′₁, e′₂, h′). Then we have

$$ s\left( {R + h \cdot P} \right) = {e_1}\left( {{R_O} + {h_O} \cdot {P_{\rm{pub}}}} \right) + {e_2}\left( {{R_A} + {h_A} \cdot {P_{\rm{pub}}}} \right) + K, $$

(17)

and

$$ s\prime\left( {R + h\prime \cdot P} \right) = {e\prime;_1}\left( {{R_O} + {h_O} \cdot {P_{\rm{pub}}}} \right) + {e\prime_2}\left( {{R_A} + {h_A} \cdot {P_{\rm{pub}}}} \right) + K. $$

(18)

Let K = a  P, R = b  P, ${R_O} = {a_O} \cdot {P_{\rm{pub}}} + {b_O} \cdot P$, ${P_{\rm{pub}}} = Q = x \cdot P$, then we have

$$ s\left( {b + h} \right) = {e_1}\left( {\left( {{a_O}x + {b_O}} \right) + {h_O}x} \right) + {e_2}\left( {\left( {{a_A}x + {b_A}} \right) + {h_A}x} \right) + a\bmod n, $$

(19)

and

$$ s\prime\left( {b + h\prime} \right) = {e\prime_1}\left( {\left( {{a_O}x + {b_O}} \right) + {h_O}x} \right) + {e\prime_2}\left( {\left( {{a_A}x + {b_A}} \right) + {h_A}x} \right) + a\bmod n. $$

(20)

In these equations, only b and x are unknown to $\mathfrak{F}$. $\mathfrak{F}$ solves for these values from the above like he does in case 1, and outputs x as the solution of the discrete logarithm problem.

According to [12, Lemma 4], the ECDLP can be solved with probability ε′ ≥ 1/9 and time $t\prime \leqslant 23{q_{{{H_2}}}}t/\varepsilon$.

4 Comparison with previous scheme

In this section, we will compare the efficiency of our new scheme with Gu et al.’s scheme [6], Zhang’s scheme [7], Wu et al.’s scheme [8], Gu et al.’s [9], and Ji et al.’s scheme [10]. In the computation efficiency comparison, we obtain the running time for cryptographic operations using MIRACAL [13], a standard cryptographic library.

The hardware platform is a PIV 3-GHZ processor with 512-MB memory and a Windows XP operation system. For the pairing-based scheme, to achieve the 1,024-bit RSA level security, we use the Tate pairing defined over the supersingular elliptic curve $E/{F_p}:{y^{{2}}} = {x^{{3}}} + x$ with embedding degree 2, where q is a 160-bit Solinas prime $q = {{2}^{{{159}}}} + {{2}^{{{17}}}} + {1}$ and p a 512-bit prime satisfying $p + {1} = {12}qr$. For the ECC-based schemes, to achieve the same security level, we employed the parameter secp160r1 [14], recommended by the Certicom Corporation, where $p = {{2}^{{{16}0}}} - {{2}^{{{31}}}} - {1}$. The running times are listed in Table 1, where sca.mul. stands for scalar multiplication.

Table 1 Cryptographic operation time (in milliseconds)

To evaluate the computation efficiency of different schemes, we use the simple method from [15, 16]. For example, the Extract algorithm of our scheme requires a KGC to carry out one ECC-based scale multiplication; thus, the computation time of the sign algorithm is 2.21 × 1 = 2.21 ms; the Delegate algorithm has to carry out one ECC-based scalar multiplications, and the resulting running time is 2.21 × 1 = 2.21 ms; the Dverify algorithm has to carry out two ECC-based scalar multiplications, and the resulting running time is 2.21 × 2 = 4.42 ms; the PKgen algorithm has to carry out one modular multiplications, we will ignore running time; the Psign algorithm has to carry out one ECC-based scalar multiplications, and the resulting running time is 2.21 × 1 = 2.21 ms; the PVerify algorithm has to carry out four ECC-based scalar multiplications, and the resulting running time is 2.21 × 4 = 8.84 ms. As another example, in Gu et al.’s scheme [6], the Extract algorithm of requires a KGC to carry out one pairing-based scale multiplication and a map-to-point hash function; thus, the computation time of the sign algorithm is 6.38 × 1 + 3.04 = 9.42 ms; the Delegate algorithm has to carry out one pairing -based scalar multiplications and a modular exponentiation, and the resulting running time is 6.38 × 1 + 5.31 = 11.69 ms; the Dverify algorithm has to carry out two pairing operations and a modular exponentiation, and the resulting running time is 20.04 × 2 + 5.31 = 45.39 ms; the PKgen algorithm has to carry out one pairing -based scalar multiplications, and the resulting running time is 6.38 × 1 = 6.38 ms; the Psign algorithm has to carry out one pairing -based scalar multiplications and a modular multiplication, then the resulting running time is 6.38 + 5.31 = 11.69 ms; the PVerify algorithm has to carry out two pairing, one pairing-based scalar multiplications and two modular exponentiations, then the resulting running time is 20.04 × 2 + 6.38 + 5.31 × 2 = 57.09 ms. Table 2 shows the results of the performance comparison.

Table 2 Performance comparison of different schemes

According to Table 2, the running time of the Psign algorithm of our scheme is 18.9% of Gu et al.’s schemes [6], 2.61% of Zhang et al.’s scheme [7], 6.99%of Wu et al.’s scheme [8], 18.9% of Gu et al.’s scheme [9], and 11.55% of Ji et al.’s scheme [10], the running time of the Pverify algorithm of our scheme is 15.27% of Gu et al.’s schemes [6], 16.74% of Zhang et al.’s scheme [7], 7.87% of Wu et al.’s scheme [8], 20.37% of Gu et al.’s scheme [9], and 19.04% of Ji et al.’s scheme [10]. Thus our scheme is more efficient than the previous schemes [6–10].

5 Conclusion

In this paper, we have proposed an efficient identity-based proxy signature scheme. We also prove the security of the scheme under random oracle. Compared with previous scheme, the new scheme reduces the running time heavily. Therefore, our scheme is more practical than the previous related schemes for practical application.