Strongly Unforgeable and Efficient Proxy Signature Scheme with Fast Revocation Secure in the Standard Model

Abstract

The existing proxy signature schemes with the proxy revocation function are proven to be malleable and do not possess strong unforgeability. Motivated by these concerns, a new proxy signature scheme with fast revocation is proposed, and it can be proved that the proposed scheme can achieve strong unforgeability in the standard model. By using this scheme, the original signer can generate the delegation warrant for the proxy signer, and at the same time, he/she can perform the immediate revocation to completely terminate the delegation when needed. Analyses show that the proposed scheme satisfies all of the security requirements of proxy signature and has shorter public parameters than the existing ones.

1. Introduction

As a variation of digital signature [1], proxy signature [2] allows the original signer to delegate his/her signature rights to a proxy signer. In this case, the designated proxy signer can generate valid signatures like the original signer. Proxy signature has many important applications in our daily life. For example, in the sensor networks aiming at collecting temperature data, sensor nodes are responsible for collecting data and sending them to the sink node. With data from sensor nodes, the sink node processes them and issues the analysis result publicly through Internet. Generally, it is necessary for people to judge where this result comes from, and in this case the analysis result should be signed by the sink node before releasing it. Normally, the sink node is able to carry out the signature process by itself. However, it maybe has to choose a trustworthy and capable equipment to replace itself to implement signature for some reason, and the selected equipment is called a proxy signer. This is a typical case for sensor-based application systems. In fact, proxy signature has found even wider applications, including electronic commerce, e-cash, and mobile agents, where delegation of rights is quite common [3]. Thus, proxy signature becomes one of the hot topics in the field of information security, and many schemes [4–9] have been proposed recently.

In proxy signature, it is important to securely process the proxy revocation problem when a valid delegation expires or the original signer wants to revoke a valid delegation ahead of schedule for some reason. For instance, in the above example, the signature rights can be assigned to other equipment by the sink node. However, during the period of delegation, the sink node maybe wants to repeal the rights before the end of the delegation. In this case, the delegation revocation function is needed. Although fast revocation has already been taken into account in several proxy signature schemes [10–13], none of them have achieved the security notion of the secure existential unforgeablility, since an adversary can still generate a valid signature on the same message without the private key. That is to say, the adversary is still able to forge a signature after the proxy signer is revoked. The basic reason is that these proxy signature schemes are designed by using 2-level hierarchical Waters' schemes, but Waters et al.'s scheme is malleable [5, 14].

Motivated by the above concerns, we proposed a new proxy signature scheme with fast revocation in the standard model under the computational Diffie-Hellman assumption and proved that it can achieve strong unforgeability in the standard model. Compared with the existing proxy signature schemes, the proposed scheme has the following merits: shorter size of public parameters and tighter security reduction. At the same time, the proposed scheme has the property of fast revocation. In a word, our scheme achieves strong unforgeability of the proxy signature scheme with revocation.

The rest of this paper is organized as follows: in Section 2, we shall briefly review related works in the field of proxy signature. Hard problems and security notions are given in Section 3. In Section 4, we introduce the new proxy signature scheme. In Section 5, we analyze the correctness and security of our scheme and compare our scheme with existing schemes in terms of computational efficiency, the number of public parameters, and security. Finally, we conclude this paper in Section 6.

2. Related Works

The concept of proxy signature was first introduced by Mambo et al. [2], and it has been considered the most promising technique to solve the delegation problem of signature rights [15]. Since then, proxy signature has attracted a considerable amount of interest from researchers. According to the delegation types [2], proxy signature can be classified into three types: full delegation, partial delegation, and delegation by warrant. For the full delegation [15], the original signer directly sends his/her private key to the proxy signer. It is easy to implement the full delegation, but the signature produced by the proxy signer is completely indistinguishable from the one produced by the original signer. In fact, such schemes are obviously impractical and insecure, because the proxy signer has the same right as the original signer, and the original signer cannot achieve revocation of delegated rights. For the partial delegation [15], the original signer generates a proxy key from his/her private key and securely transfers it to the proxy signer, and the proxy signer uses this proxy key to sign messages on behalf of the original signer. Moreover, partial delegation is classified as proxy-unprotected and proxy-protected based on the protection of the proxy signer [15]. However, the signed messages by the proxy signer are not limited, so the proxy signer may sign some messages that the original signer is not willing to sign. To eliminate this drawback, Kim et al. [16] presented the partial delegation scheme with warrant, which combines the merits of the partial delegation and the delegation by warrant. In the delegation by warrant, the original signer specifies what kind of message is delegated in the warrant and produces a signature on the warrant. Then, the proxy signer uses this signature and his private key to create a valid proxy signature on behalf of the original signer. But this scheme was proven insecure later.

Recently, several proxy signature schemes have been put forward. In 2008, Liu et al. [6] presented a proxy multisignature scheme in the standard model, which allows a proxy signer to generate proxy signatures on behalf of two or more original signers. In 2012, Hwang et al. [17] proposed a variation of proxy signature scheme called threshold multiproxy multisignature scheme with shared verification based on the RSA problem. Sahu and Saraswat [18], in 2015, proposed an efficient and provably secure identity-based multi-proxy signature scheme, which allows a user to transfer its signature rights to a group of proxy signers.

However, most of the existing proxy signature schemes have the following essential shortcomings [19]. First, the declaration of a valid delegation in the warrant is useless. The proxy signer can still produce a signature even if the delegation period has expired. Second, when the original signer wants to revoke the delegation earlier than his/her schedule, he/she can do nothing. Thus, the revocation of delegated rights is an essential problem of proxy signature. To solve these problems, some schemes with revocation have been proposed. For example, Sun and Chen [20] proposed a time-stamped proxy signature scheme and claimed that the revocation problem can be solved by using a time-stamp. However, their scheme suffers from security weakness and cannot solve the second problem [21]. Seo et al. [19] proposed a mediated proxy signature scheme to solve the proxy revocation problem by using a special entity, called SEM, which is an online partially trusted server. But the shortcoming of the above schemes [19–21] is that they cannot be proven secure in the random oracle model or in the standard model. In order to eliminate this shortcoming, in 2009, Liu et al. [10] first proposed a provable secure proxy signature with revocation in the standard model.

For the lack of formal security definitions, many early schemes were proven insecure later. Therefore, security notion and security concept are important for designing the proxy signature schemes. In 2003, Boldyreva et al. [22] first defined the security model of proxy signature schemes. Although their model is efficient, it has received many criticisms, since the security of their model is unable to describe the security in the standard model. Consequently, their scheme is proved secure in the random oracle model, but it is vulnerable to the proxy key exposure attack. So, it is an interesting problem to design a proxy signature scheme, which can be proven secure in the standard model and avoid the proxy key exposure attack. In 2006, Huang et al. [4] divided the attackers into three types to make the security model much clearer and proposed a secure proxy signature in the standard model. Based on Huang et al.'s scheme and Waters' technique, Liu et al. [10] proposed a formal security model for proxy signature with fast revocation in the standard model. After that, many proxy signature schemes with revocation in the standard model have been proposed [10–13], and they are demonstrated by using a 2-level hierarchical Waters signature. However, there are two drawbacks in these schemes [10–12]. One is that they have a large number of public parameters, and the other is that they are not strongly unforgeable since an adversary is still able to forge a valid signature on the same message without the private key after the proxy signer is revoked.

Later, many new schemes were proposed. In 2013, Kim et al. [23] and Swapna et al. [24] constructed the provably secure ID-based proxy signature schemes based on the lattice problems, respectively and independently, but these schemes increased the length of the proxy private key significantly. In 2014, Hu et al. [25] presented a novel ID-based proxy signature scheme, and the proposed scheme is provably secure in the standard model. In the same year, Cao et al. [26] also presented a weak blind signature scheme by combing the requirements for proxy signature and weak blind signature. Unfortunately, Zhang and Jia [27] found that there exists a security problem in Cao et al.'s scheme. That is to say, the receiver of the signature can forge a valid signature on any message without being perceived, and at the same time, Zhang and Jia provided the detailed attack strategy and the possible improved schemes.

The existing proxy signature schemes are existentially unforgeable under adaptive chosen-message attacks and adaptive chosen-warrant attacks, which means that an adversary should not be able to produce a valid signature for a new message. However, most existing signature schemes are randomized and may produce some valid signatures for the same message, because they do not have the property of strong unforgeability, which is desirable in some applications [28]. A scheme is said to be strongly unforgeable if it is existentially unforgeable under adaptive chosen message attacks and an adversary cannot generate a different valid signature on the same message. Although strong unforgeability is an important property of proxy signature schemes, there are few proxy signatures that possess the property of strong unforgeability in the standard model because of the malleability of Waters' signature. In 2011, Sun et al. [7] proposed the first strongly unforgeable proxy signature in the standard model with the Waters' scheme and Boneh et al. [29]. This scheme shows the formal security of a strongly unforgeable proxy signature. However, Sun et al. could not solve the revocation problem of delegated rights described above.

Overall, although fast revocation has been taken into account in several proxy signature schemes, these schemes do not possess strong unforgeability. Therefore, a strongly unforgeable proxy signature with fast revocation in the standard model is an interesting topic. We need to construct a strongly unforgeable proxy signature with revocation under the computational Diffie-Hellman assumption. Our scheme is based on Sun et al.'s work [7] and the SEM revocation mechanism [19–21].

3. Preliminaries

Before introducing our scheme, we shall briefly introduce the difficult problems and security models related to our scheme. Notations used throughout the paper are summarized in Table 1.

Table 1

Notations.

Name	Meaning
P	Large prime integer
G	Additive group of order p
$$G_T$$	Multiplicative group of order p
$$Z_p$$	The set of positive integers which are less than p
g	Generator of G
e	Bilinear mapping, that is, e: $G\times G\to G_T$
$$h_i$$	Cryptographic hash function: ${\left\{\mathit{0,1}\right\}}^{\ast }\times G\times G_T\to Z_p$ ( $i=\mathit{1,2}$ )
$$H_0$$	Hash function: ${\left\{\mathit{0,1}\right\}}^{\ast }\to {\left\{\mathit{0,1}\right\}}^n$
$$\text{s}{\text{k}}_i$$	Private key of i, where $i\in \left\{A,B\right\}$
$$\text{p}{\text{k}}_i$$	Public key of i, where $i\in \left\{A,B\right\}$
w	Warrant including the period of delegation, and so forth
M	Message to sign
CDH	Computational Diffie-Hellman problem
ε	Probability of polynomial algorithm
pr	The probability of an event

3.1. Hard Problems

The security of the proposed scheme is based on the hardness of the well-known hard mathematical problem, the computational Diffie-Hellman problem.

Definition 1 (computational Diffie-Hellman (CDH) problem in G).

Given $g,g^a,g^b\in G$ for unknown values a and $b\in Z_p$ , to compute $g^{ab}\in G$ , the probability that a polynomial algorithm A can solve the CDH problem is defined as

$$\begin{array}{cc}& {\text{Succ}}_A^{\text{CDH}}=\mathrm{pr}\left[g^{ab}⟵A\left(G,g,g^a,g^b\right)\right].\end{array}$$

(1)

Definition 2 (computational Diffie-Hellman (CDH) assumption in G).

Given $g,g^a,g^b\in G$ for two unknown values a and $b\in Z_p$ , $\mathrm{S}\mathrm{u}\mathrm{c}{\mathrm{c}}_A^{\mathrm{C}\mathrm{D}\mathrm{H}}$ is negligible.

3.2. Algorithm Model

In this section, we will give the outline of a strongly unforgeable proxy signature with fast revocation. There exist three parties: an original signer Alice shorted by A, a proxy signer Bob shorted by B, and a security mediator SEM shorted by S, which is an online partial third server, introduced to check whether the proxy signer signs a message according to the warrant or he/she exists on the revocation list. B is picked by A. For other entities, S is supposed to be a partially trusted third party, who has to perform this protocol strictly. A proxy signature scheme with fast revocation consists of the following algorithms.

(1) Setup. Given the system security parameter, this algorithm outputs the system parameter π, which is publicly known.

(2) Key-Gen. Given π, this algorithm generates a private-public key pair ( $\mathrm{s}{\mathrm{k}}_i,\mathrm{p}{\mathrm{k}}_i$ ) for $i\in \left\{A,B\right\}$ . The private keys of signers must be kept secret.

(3) Delegation-Gen. Given π, the private key of A   $\mathrm{s}{\mathrm{k}}_A$ , and a warrant ω to be delegated, this algorithm outputs a revocation identifier $R_A$ , and two partial delegation keys ${\sigma }_B$ and ${\sigma }_S$ . A sends ( $\omega ,{\sigma }_B,R_A$ ) to B and ( $\omega ,{\sigma }_S,R_A$ ) to S.

(4) Delegation-Verify. After receiving ( $\omega ,{\sigma }_B,R_A$ ) and ( $\omega ,{\sigma }_S,R_A$ ), both S and B prove the validity of the delegation.

(5) Proxy-Valid. B wants to sign a message M. S must guarantee that the period of proxy delegation specified in the warrant ω is valid, and B is not on the public revocation list.

(6) ProxySign-Gen. Given π, a warrant ω, a message M, two delegation keys ${\sigma }_B$ and ${\sigma }_S$ , and the secret key $\mathrm{s}{\mathrm{k}}_B$ of B, this algorithm outputs a proxy signature σ.

(7) ProxySign-Verify. Given π, a warrant ω, a message M, the signature σ, and the public keys $\mathrm{p}{\mathrm{k}}_A$ and $\mathrm{p}{\mathrm{k}}_B$ , this algorithm outputs 1 if σ is valid and 0 otherwise.

(8) Proxy-Revocation. If A wants to revoke the delegation of B before the specific delegation period expires, he/she asks S to put ( $\omega ,R_A$ ) on the public revocation list. Therefore, if the delegation period has expired or ( $\omega ,R_A$ ) exists in the revocation list, S will not issue any token for the proxy signer.

3.3. Security Models

For proxy signature schemes, the first security model was proposed by Mambo et al. [15]. However, this model was vulnerable to proxy key exposure attacks. In order to avoid proxy key exposure attacks, Huang et al. [4] provided a new security model of proxy signatures, where adversaries are divided into three types to make the security model much clearer. We modified this model a little to make it adapt to our scheme and strengthen its strong unforgeability of proxy signature. Three types of adversaries are shown as follows.

Type I. Adversary $A_{\mathrm{I}}$ only has the public keys of A and B. It is an outside attacker in this case.

Type II. Adversary $A_{\mathrm{I}\mathrm{I}}$ has the public keys of A and B, and at the same time, he/she has corrupted the secret key of the proxy signer. It is an inside attacker in this case.

Type III. Adversary $A_{\mathrm{I}\mathrm{I}\mathrm{I}}$ has the public keys of A and B. In addition, he/she has corrupted the secret key of the original signer. It is also an inside attacker in this case.

Clearly, if a proxy signature scheme is strongly unforgeable against type II and type III adversaries, it is also strongly unforgeable against type I. Therefore, if we show that our scheme is strongly unforgeable against type II and type III adversaries, it means that our scheme is strongly unforgeable against all three types of adversaries. In the following security model, we only consider the type II adversary $A_{\mathrm{I}\mathrm{I}}$ and type III adversary $A_{\mathrm{I}\mathrm{I}\mathrm{I}}$ .

3.3.1. Strong Existential Unforgeability against the Adaptive $A_{\text{II}}$ Adversary

The strong unforgeability of the proxy signature scheme with fast revocation under $A_{\mathrm{I}\mathrm{I}}$ adversary requests that it is difficult for an attacker to forge a valid signature on M under a warrant if he/she does not obtain the delegation of the warrant ω. It is defined as the following game between a challenger C and an adversary $A_{\mathrm{I}\mathrm{I}}$ .

• (1)

$C\mathrm{\hspace{0.17em}\hspace{0.17em}}$ runs the Setup algorithm to obtain the system parameter π and runs the Key-Gen algorithm to obtain A's private/public key pair ( $\mathrm{s}{\mathrm{k}}_A,\mathrm{p}{\mathrm{k}}_A$ ) and B's private/public key pair ( $\mathrm{s}{\mathrm{k}}_B,\mathrm{p}{\mathrm{k}}_B$ ). Then, C sends $\mathrm{p}{\mathrm{k}}_A$ , $\mathrm{s}{\mathrm{k}}_B$ , and $\mathrm{p}{\mathrm{k}}_B$ to an adversary $A_{\mathrm{I}\mathrm{I}}$ .

(2)

$A_{\mathrm{I}\mathrm{I}}$ makes a series of queries.

• (a)

SEM-Delegation queries: $A_{\mathrm{I}\mathrm{I}}$ requests S's delegation key on a warrant ω. C runs the Delegation-Gen algorithm to obtain the partial delegation key ${\sigma }_S$ , and a revocation identifier $R_A$ , and then returns ( $\omega ,{\sigma }_S,R_A$ ) to an adversary $A_{\mathrm{I}\mathrm{I}}$ .

(b)

User-Delegation queries: $A_{\mathrm{I}\mathrm{I}}$ requests S's delegation key on a warrant ω. C runs the Delegation-Gen algorithm to obtain the partial delegation key ${\sigma }_B$ , and a revocation identifier $R_A$ , and then returns ( $\omega ,{\sigma }_B,R_A$ ) to an adversary $A_{\mathrm{I}\mathrm{I}}$ .

(c)

SEM-Sign queries: $A_{\mathrm{I}\mathrm{I}}$ requests S's partial proxy signature on a message M, which satisfies the warrant ω. C runs the ProxySign-Gen algorithm and obtains the partial proxy signature ${\sigma }_{\mathrm{p}\mathrm{s}}$ .

(d)

User-Sign queries: $A_{\mathrm{I}\mathrm{I}}$ requests B's complete signature on a message M. C runs the ProxySign-Gen algorithm and obtains a proxy signature σ.

(3)

Finally, $A_{\mathrm{I}\mathrm{I}}$ outputs a pair ( $M^{\ast },{\omega }^{\ast },{\sigma }^{\ast }$ ), such that

• (a)

${\omega }^{\ast }$ has not been queried in the SEM-Delegation or User-Delegation query,

(b)

${\sigma }^{\ast }$ is a valid signature of the message $M^{\ast }$ under the warrant ${\omega }^{\ast }$ ,

(c)

( $M^{\ast },{\omega }^{\ast },{\sigma }^{\ast }$ ) is not among the triplets ( $M_i,{\omega }_i,{\sigma }_i$ ) during the User-Sign query.

The advantage of an adversary $A_{\mathrm{I}\mathrm{I}}$ in the above game is defined to be

$$\begin{array}{cc}& {\text{Succ}}_{A_{\text{II}}}=\mathrm{pr}\left[A_{\text{II}}\text{succeeds}\right].\end{array}$$

(2)

Definition 3.

An adversary $A_{\mathrm{I}\mathrm{I}}$ is said to be an ( $\epsilon ,t,q_w,q_{\mathrm{p}\mathrm{s}}$ ) forger of a proxy signature scheme with revocation if $A_{\mathrm{I}\mathrm{I}}$ has the advantage of at least ε in the above game, runs in time at most t, and makes at most $q_w$ SEM-Delegation queries and User-Delegation queries, and $q_{\mathrm{p}\mathrm{s}}$ SEM-Sign queries and User-Sign queries. If no ( $\epsilon ,t,q_w,q_{\mathrm{p}\mathrm{s}}$ ) forger $A_{\mathrm{I}\mathrm{I}}$ exists, the scheme is said to be ( $\epsilon ,t,q_w,q_{\mathrm{p}\mathrm{s}}$ ) strongly unforgeable against adaptive chosen warrant/message attacks.

3.3.2. Strong Existential Unforgeability against Adaptive $A_{\text{III}}$ Adversary

The strong unforgeability of the proxy signature scheme with fast revocation under an $A_{\mathrm{I}\mathrm{I}\mathrm{I}}$ adversary requests that it is difficult for A to forge a valid signature on $M^{\ast }$ which has not been signed by B. It is defined as the following game between a challenger C and an adversary $A_{\mathrm{I}\mathrm{I}\mathrm{I}}$ .

• (1)

C runs the Setup algorithm to obtain system's parameters π and runs the Key-Gen algorithm to obtain A's private/public key pair ( $\mathrm{s}{\mathrm{k}}_A,\mathrm{p}{\mathrm{k}}_A$ ), and B's private/public key pair ( $\mathrm{s}{\mathrm{k}}_B,\mathrm{p}{\mathrm{k}}_B$ ). Then, C sends $\mathrm{p}{\mathrm{k}}_A$ , $\mathrm{s}{\mathrm{k}}_A$ , and $\mathrm{p}{\mathrm{k}}_B$ to the adversary $A_{\mathrm{I}\mathrm{I}\mathrm{I}}$ .

(2)

$A_{\mathrm{I}\mathrm{I}\mathrm{I}}$ makes a series of queries:

•   

User-Sign queries: $A_{\mathrm{I}\mathrm{I}\mathrm{I}}$ requests B's the complete proxy signature on a message M. C runs the ProxySign-Gen algorithm and obtains a proxy signature σ.

(3)

Finally, $A_{\mathrm{I}\mathrm{I}\mathrm{I}}$ outputs a pair ( $M^{\ast },{\omega }^{\ast },{\sigma }^{\ast }$ ), such that

• (a)

${\sigma }^{\ast }$ is a valid signature of the message $M^{\ast }$ under the warrant ${\omega }^{\ast }$ ,

(b)

( $M^{\ast },{\omega }^{\ast },{\sigma }^{\ast }$ ) is not among the triplets ( $M_i,{\omega }_i,{\sigma }_i$ ) during the User-Sign query.

The advantage of an adversary $A_{\mathrm{I}\mathrm{I}\mathrm{I}}$ in the above game is defined to be

$$\begin{array}{cc}& {\text{Succ}}_{A_{\text{III}}}=\mathrm{pr}\left[A_{\text{III}}\text{succeeds}\right].\end{array}$$

(3)

Definition 4.

An adversary $A_{\mathrm{I}\mathrm{I}\mathrm{I}}$ is said to be an ( $\epsilon ,t,0,q_{\mathrm{p}\mathrm{s}}$ ) forger of a proxy signature scheme with revocation if $A_{\mathrm{I}\mathrm{I}\mathrm{I}}$ has the advantage of at least ε in the above game, runs in time at most t, and makes at most $q_{\mathrm{p}\mathrm{s}}$ SEM-Sign queries and User-Sign queries. If no ( $\epsilon ,t,0,q_{\mathrm{p}\mathrm{s}}$ ) forger $A_{\mathrm{I}\mathrm{I}\mathrm{I}}$ exists, the scheme is said to be ( $\epsilon ,t,0,q_{\mathrm{p}\mathrm{s}}$ ) strongly unforgeable against adaptive chosen warrant/message attacks.

4. The Proposed Scheme

In this section, we shall introduce the strongly unforgeable proxy signature scheme with fast revocation in the standard model in detail, and this scheme is based on the existing works [5, 14]. Waters et al.'s scheme [14] is a basic algorithm prototype of Sun et al.'s scheme [5], and Sun et al. proposed the first proxy signature scheme based on Waters et al.'s model. Unfortunately, their schemes were proved to be insecure later [7]. So we analyzed their schemes and proposed a new proxy signature scheme with fast revocation, and this is our main contribution. Let A denote the original signer Alice, B denote the proxy signer Bob, and S denote the security mediator SEM who is an online partially trusted server. In the following, all the warrants to be signed will be regarded as a bit string of length n. Note: to construct a more flexible scheme which allows warrants of arbitrary length, a collision resistant hash function $H_0$ : ${\left\{\mathrm{0,1}\right\}}^{\ast }\to {\left\{\mathrm{0,1}\right\}}^n$ should be employed. The proposed scheme is illustrated in Figure 1 and elaborated on as follows.

Figure 1

The proposed proxy signature scheme with revocation.

(1) Setup. Let ( $G,G_T$ ) be bilinear groups where $\left|G\right|=\left|G_T\right|=p$ for a prime order p, and g is the generator of G. Let e denote a bilinear pairing e: $G\times G\to G_T$ . Additionally, choose random parameters $u^{\prime },u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_n$ , $v\in G$ , and a collision resistant hash function H: ${\left\{\mathrm{0,1}\right\}}^{\ast }\times G\times G_T\to Z_p$ , and then set $u=(u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_n)$ . The system's public parameters are denoted as $\pi =(G,G_T,e,p,g,u^{\prime },v,u,H)$ .

(2) Key-Gen. A randomly picks $x_A$ and $y_A\in Z_p$ and sets her private key $\mathrm{s}{\mathrm{k}}_A=(x_A,y_A)$ . Then, A computes her public key $\mathrm{p}{\mathrm{k}}_A=(\mathrm{p}{\mathrm{k}}_{Ax},\mathrm{p}{\mathrm{k}}_{Ay})=(g^{x_A},g^{y_A})$ . Similarly, B sets his secret key $\mathrm{s}{\mathrm{k}}_B=(x_B,y_B)$ , and the public key $\mathrm{p}{\mathrm{k}}_B=(\mathrm{p}{\mathrm{k}}_{Bx},\mathrm{p}{\mathrm{k}}_{By})=(g^{x_B},g^{y_B})$ . All public keys are certified by a Certification Authority (AS).

(3) Delegation-Gen. The warrant ω is signed by A and contains important information such as valid time of delegation of the signing rights, the identities of the original signer and the proxy signer, and other information of the delegation. Let ${\omega }_i$ denote the ith bit of ω, and set $W=\left\{i\mid {\omega }_i=1,i=\mathrm{1,2},\dots ,n\right\}$ . The original signer chooses randomly $x_{A1},x_{A2},r_B,r_S\mathrm{\hspace{0.17em}\hspace{0.17em}}\in Z_p$ , such that $x_{A\mathrm{1}}+x_{A\mathrm{2}}=x_A$ , and computes

$$\begin{array}{cc}& r_B+r_s=r_A,\\ R_A=g^{r_A},\\ {\sigma }_B=\left({\sigma }_{B\mathrm{1}},{\sigma }_{B\mathrm{2}}\right)=\left(g^{x_{A\mathrm{1}}{y}_A}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_B},g^{r_B}\right),\\ {\sigma }_S=\left({\sigma }_{S\mathrm{1}},{\sigma }_{S\mathrm{2}}\right)=\left(g^{x_{A\mathrm{2}}{y}_A}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_S},g^{r_S}\right).\end{array}$$

(4)

Then, A sends ( $\omega ,{\sigma }_B,R_A$ ) to B and ( $\omega ,{\sigma }_S,R_A$ ) to S, respectively.

(4) Delegation-Verify. To confirm the correctness of ( $\omega ,{\sigma }_B,R_A$ ), B computes $R_B=e({\sigma }_{B1},g)$ , and sends ( $\omega ,{\sigma }_B$ ) to S. After B receives $R_S=e({\sigma }_{S1},g)$ from S, he verifies whether the following equation holds:

$$\begin{array}{cc}& R_B{R}_s=e\left({\text{pk}}_{Ax},{\text{pk}}_{Ay}\right)e\left(u^{\prime }{\displaystyle \prod }_{i\in W}{u}_i,R_A\right).\end{array}$$

(5)

Similarly, S verifies the above equation by $R_B$ . If the verification is not valid, B and S would request valid delegations from A again or terminate this protocol.

(5) Proxy-Valid. To produce a proxy signature on a message M, B has to cooperate with S. B transmits his identity and ( $\omega ,M,R_A,R_B$ ) to S. S confirms that ( $\omega ,M,R_A,R_B$ ) was received in the Delegation-Gen and Delegation-Verify phases. Then, S must assure the following conditions, before he/she generates the partial proxy signature on the message M.

• (a)

The period of proxy delegation specified in the warrant ω should be valid.

(b)

( $\omega ,R_A$ ) should not be in the public revocation list. If ( $\omega ,R_A$ ) is in the list, it means that the delegation has been revoked.

If the two conditions hold, S can perform the ProxySign-Gen stage.

(6) ProxySign-Gen. Let M be an n-bit message. The proxy signer has to cooperate with S to generate a proxy signature on M.

• (a)

S randomly chooses $r_1,k_1\in Z_p$ and computes $h_{\mathrm{1}}=H(M\parallel \omega ,{\sigma }_{S\mathrm{2}},g^{k_{\mathrm{1}}})$ . Then, he sends the following partial proxy signature ${\sigma }_{\mathrm{p}\mathrm{s}}$ to B:

$$\begin{array}{cc}& {\sigma }_{\text{ps}}=\left(g^{x_{A\mathrm{2}}{y}_A}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_{\mathrm{1}}+r_S}{\left(Mv\right)}^{h_{\mathrm{1}}{k}_{\mathrm{1}}},g^{r_{\mathrm{1}}},g^{h_{\mathrm{1}}{k}_{\mathrm{1}}}\right).\end{array}$$

(6)

(b)

B checks whether the following equation holds:

$$\begin{array}{cc}& e\left({\sigma }_{\text{ps}\mathrm{1}},g\right)R_B=e\left({\text{pk}}_{Ax},{\text{pk}}_{Ay}\right)e\left(u^{\prime }{\displaystyle \prod }_{i\in W}{u}_i,R_A{\sigma }_{\text{ps}\mathrm{2}}\right)e\left(Mv,{\sigma }_{\text{ps}\mathrm{3}}\right).\end{array}$$

(7)

If yes, B chooses two random values $r_2,k_2\in Z_p$ and computes $h_{\mathrm{2}}=H(M\parallel \omega ,{\sigma }_{B\mathrm{2}},g^{k_{\mathrm{2}}})$ . The proxy signature is computed as in the following equation:

$$\begin{array}{cc}& \sigma =\left({\sigma }_{\text{ps}\mathrm{1}}{\sigma }_{B\mathrm{1}}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_{\mathrm{2}}}{\left(Mv\right)}^{h_{\mathrm{2}}{k}_{\mathrm{2}}}{g}^{x_B{y}_B},{\sigma }_{\text{ps}\mathrm{2}}{g}^{r_{\mathrm{2}}},{\sigma }_{\text{ps}\mathrm{3}}{g}^{h_{\mathrm{2}}{k}_{\mathrm{2}}}\right)=\left(g^{x_A{y}_A}{g}^{x_B{y}_B}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_{\mathrm{1}}+r_{\mathrm{2}}+r_B+r_S}{\left(Mv\right)}^{h_{\mathrm{1}}{k}_{\mathrm{1}}+h_{\mathrm{2}}{k}_{\mathrm{2}}},g^{r_{\mathrm{1}}+r_{\mathrm{2}}},g^{h_{\mathrm{1}}{k}_{\mathrm{1}}+h_{\mathrm{2}}{k}_{\mathrm{2}}}\right)=\left(g^{x_A{y}_A}{g}^{x_B{y}_B}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{\tilde{r}}{\left(Mv\right)}^{\tilde{h}},g^{r_{\mathrm{1}}+r_{\mathrm{2}}},g^{\tilde{h}}\right),\end{array}$$

(8)

where $\tilde{r}=r_{\mathrm{1}}+r_{\mathrm{2}}+r_B+r_S$ , and $\tilde{h}=h_{\mathrm{1}}{k}_{\mathrm{1}}+h_{\mathrm{2}}{k}_{\mathrm{2}}$ .

(7) ProxySign-Verify. The verifier verifies whether the proxy signature σ on the message M is valid by judging whether the following equation holds:

$$\begin{array}{cc}& e\left({\sigma }_{\mathrm{1}},g\right)=e\left({\text{pk}}_{Ax},{\text{pk}}_{Ay}\right)e\left({\text{pk}}_{Bx},{\text{pk}}_{By}\right)e\left(u^{\prime }{\displaystyle \prod }_{i\in W}{u}_i,R_A{\sigma }_{\mathrm{2}}\right)e\left(Mv,{\sigma }_{\mathrm{3}}\right).\end{array}$$

(9)

(8) Proxy-Revocation. When a valid delegation period expires or A wants to revoke a valid delegation ahead of schedule for some reason, she asks S to put ( $\omega ,R_A$ ) in a public revocation list. When B issues a proxy token for a message M, S will check the valid period of the delegation in the warrant and ( $\omega ,R_A$ ) in the public revocation list. If the delegation period has expired or ( $\omega ,R_A$ ) exists in the revocation list, S does not issue the proxy token for B. Once the period of delegation has expired, ( $\omega ,R_A$ ) of the public revocation list could be eliminated. So, the size of the public revocation list will not increase.

5. Correctness and Security

5.1. Correctness

Theorem 5.

The delegation verification algorithm in our algorithm is correct.

Proof.

In our algorithm, we have ${\sigma }_{B\mathrm{1}}=g^{x_{A\mathrm{1}}{y}_A}(u^{\prime }{\prod }_{i\in W}{u}_i{)}^{r_B}$ and ${\sigma }_{s\mathrm{1}}=g^{x_{A\mathrm{2}}{y}_A}(u^{\prime }{\prod }_{i\in W}{u}_i{)}^{r_S}$ . In addition, we have $e(g^{x_{A\mathrm{1}}{y}_A},g^{x_{A\mathrm{2}}{y}_A})=e(g^{x_{A\mathrm{1}}+x_{A\mathrm{2}}},g^{y_A})=e({\text{pk}}_{Ax},{\text{pk}}_{Ay})$ . Thus, we have

$$\begin{array}{cc}& R_B{R}_s=e\left({\sigma }_{B\mathrm{1}},g\right)e\left({\sigma }_{s\mathrm{1}},g\right)=e\left(g^{x_{A\mathrm{1}}{y}_A}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_B},g\right)e\left(g^{x_{A\mathrm{2}}{y}_A}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_S},g\right)=e\left(g^{x_{A\mathrm{1}}{y}_A}{g}^{x_{A\mathrm{2}}{y}_A},g\right)e\left({\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_B+r_S},g\right)=e\left({\text{pk}}_{Ax},{\text{pk}}_{Ay}\right)e\left(u^{\prime }{\displaystyle \prod }_{i\in W}{u}_i,R_A\right).\end{array}$$

(10)

Theorem 6.

The proxy signature verification algorithm in our algorithm is correct.

Proof.

In our algorithm, we have the equations ${\sigma }_{\text{ps}\mathrm{1}}=g^{x_{A\mathrm{2}}{y}_A}(u^{\prime }{\prod }_{i\in W}{u}_i{)}^{r_{\mathrm{1}}+r_S}(Mv{)}^{h_{\mathrm{1}}{k}_{\mathrm{1}}}$ and $R_B=e({\sigma }_{B\mathrm{1}},g)=e(g^{x_{A\mathrm{1}}{y}_A}(u^{\prime }{\prod }_{i\in W}{u}_i{)}^{r_B},g)$ . Thus, we have

$$\begin{array}{cc}& e\left({\sigma }_{\text{ps}\mathrm{1}},g\right)R_B=e\left(g^{x_{A\mathrm{2}}{y}_A}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_{\mathrm{1}}+r_S}{\left(Mv\right)}^{h_{\mathrm{1}}{k}_{\mathrm{1}}},g\right)e\left(g^{x_{A\mathrm{1}}{y}_A}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_B},g\right)=e\left({\text{pk}}_{Ax},{\text{pk}}_{Ay}\right)e\left(u^{\prime }{\displaystyle \prod }_{i\in W}{u}_i,R_A{\sigma }_{\text{ps}\mathrm{2}}\right)e\left(Mv,{\sigma }_{\text{ps}\mathrm{3}}\right).\end{array}$$

(11)

So, we prove the correctness of the proxy signature in the following way:

$$\begin{array}{cc}& e\left({\sigma }_{\mathrm{1}},g\right)=e\left({\sigma }_{\text{ps}\mathrm{1}}{\sigma }_{B\mathrm{1}}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_{\mathrm{2}}}{\left(Mv\right)}^{h_{\mathrm{2}}{k}_{\mathrm{2}}}{g}^{x_B{y}_B},g\right)=e\left(g^{x_A{y}_A}{g}^{x_B{y}_B}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_{\mathrm{1}}+r_{\mathrm{2}}+r_B+r_S}{\left(Mv\right)}^{h_{\mathrm{1}}{k}_{\mathrm{1}}+h_{\mathrm{2}}{k}_{\mathrm{2}}},g\right)=e\left({\text{pk}}_{Ax},{\text{pk}}_{Ay}\right)e\left({\text{pk}}_{Bx},{\text{pk}}_{By}\right)e\left(u^{\prime }{\displaystyle \prod }_{i\in W}{u}_i,R_A{\sigma }_{\mathrm{2}}\right)e\left(Mv,{\sigma }_{\mathrm{3}}\right).\end{array}$$

(12)

5.2. Security

The proposed scheme satisfies the security requirements of verifiability, strong identifiability, strong undeniability, and prevention of misuse, which can be briefly explained as follows: $(1)$ verifiability: any verifier can be assured of A's agreement on the signature; $(2)$ strong undeniability: no one can know the private key of B; when B generates a signature, he/she cannot repudiate it because the signature is produced by his/her private key; $(3)$ strong identifiability: the identity information is included in the valid signature and the warrant as a form of public key; $(4)$ prevention of misuse: once the delegated right is misused, A asks S to stop sending the proxy token to B. More importantly, our scheme can achieve strong unforgeability in the standard model, which makes our scheme different from the existing proxy signature schemes proven secure in the standard model. Therefore, in this section, we shall prove the proposed scheme is strongly unforgeable against three types of adversaries mentioned above. If a proxy signature scheme is strongly unforgeable against a Type II or Type III adversary, it is also strongly unforgeable against Type I. Therefore, in this section, we will only prove that our scheme is strongly unforgeable against type II and type III under adaptive chosen message/warrant attacks in the standard model under the computational Diffie-Hellman assumption.

Theorem 7.

If there exists a type $\text{II}$ adversary $A_{\text{II}}$ who can $\left(\epsilon ,t,q_w,q_{\text{ps}}\right)$ break our proxy signature scheme, there exists an algorithm C which can use $A_{\text{II}}$ to solve an instance of the $\text{CDH}$ problem in G with a probability

$$\begin{array}{cc}& {\text{Succ}}_C^{\text{CDH}}\ge \frac{\xi }{\mathrm{8}\left(n+\mathrm{1}\right)q_w}\end{array}$$

(13)

within running time $t+((n+\mathrm{5})q_w+(n+\mathrm{6})q_{\text{ps}}+n+\mathrm{4})T_m+(\mathrm{10}{q}_w+\mathrm{12}{q}_{\text{ps}}+\mathrm{2}n+\mathrm{8})T_e$ , where $T_m$ denotes the time for a multiplication in G, and $T_e$ denotes the time for an exponentiation in G, respectively.

Proof.

Assume that C receives a random CDH problem instance ( $g,g^a,g^b$ ) in G whose order is a prime number p, and his/her goal is to output $g^{ab}$ . C will run the adversary $A_{\mathrm{I}\mathrm{I}}$ as a subroutine, act as $A_{\mathrm{I}\mathrm{I}}$ 's challenger, and respond to $A_{\mathrm{I}\mathrm{I}}$ 's requests in the following ways.

(i) Setup. Let $l=4q_w$ . C randomly chooses

• (1)

an integer k  ( $\mathrm{0}\le k\le n$ ) (it is assumed that $l(n+1)<p$ for the given values $q_w,q_{\mathrm{p}\mathrm{s}},n$ ),

(2)

an integer $x^{\prime }\in Z_l$ and an n-dimensional vector $\mathbf{X}=(x_i)$ ( $x_i\in Z_l$ ),

(3)

an integer $y^{\prime }\in Z_p$ and an n-dimensional vector $\mathbf{Y}=(y_i)$ ( $y_i\in Z_p$ ).

For the ease of analysis, the following functions are defined:

$$\begin{array}{cc}& F\left(W\right)=\left(p-lk\right)+x^{\prime }+{\displaystyle \sum }_{i\in W}{x}_i,\\ J\left(W\right)=y^{\prime }+{\displaystyle \sum }_{i\in W}{y}_i,\\ K\left(W\right)=\left\{\begin{array}{cc}\mathrm{0},\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}{x}^{\prime }+{\displaystyle \sum }_{i\in W}{x}_i=\mathrm{0}\left(\mathrm{mod}\hspace{0.17em}l\right)\hfill \\ \mathrm{1},\hfill & \text{otherwise}.\hfill \end{array}\right.\end{array}$$

(14)

Then, C assigns a set of public parameters as follows:

• (1)

C sets the public key of the original signer $({\text{pk}}_{Ax},{\text{pk}}_{Ay})=(g^a,g^b)$ , where $(g^a,g^b)$ are from the input of the instance of the CDH problem.

(2)

C randomly picks two values ${\text{sk}}_{Bx},{\text{sk}}_{By}\in Z_p$ and sets the public key of the proxy signer $({\text{pk}}_{Bx},{\text{pk}}_{By})=(g^{\mathrm{s}{\mathrm{k}}_{Bx}},g^{\mathrm{s}{\mathrm{k}}_{By}})$ .

(3)

C sets $v=g^c$ , where $c\in Z_p$ .

(4)

C assigns $u^{\prime }={\text{pk}}_{Ax}^{p-lk+x^{\prime }}{g}^{y^{\prime }}$ and $u_i={\text{pk}}_{Ax}^{x_i}{g}^{y_i}$ , and sets $\overrightarrow{u}=(u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_n)$ .

Note that under the assignment

$$\begin{array}{cc}& u^{\prime }{\displaystyle \prod }_{i\in W}{u}_i={\text{pk}}_{Ax}^{F\left(W\right)}{g}^{J\left(W\right)}\end{array}$$

(15)

C returns $(G,G_T,e,p,g,u^{\prime },v,u,H)$ and $({\text{pk}}_{Ax},{\text{pk}}_{Ay},{\text{pk}}_{Bx},{\text{pk}}_{By},{\text{sk}}_{Bx},{\text{sk}}_{By})$ to the adversary.

(ii) C runs $A_{\mathrm{I}\mathrm{I}}$ and responds to queries of $A_{\mathrm{I}\mathrm{I}}$ .

(1) SEM-Delegation Query. C first selects two random integers $x_{\mathrm{1}},r_{\mathrm{1}}\in Z_p$ and computes

$$\begin{array}{cc}& {\sigma }_S=\left({\text{pk}}_{Ay}^{x_{\mathrm{1}}}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_{\mathrm{1}}},g^{r_{\mathrm{1}}}\right).\end{array}$$

(16)

(2) User-Delegation Query. If $K(W)=0$ , C terminates the simulation and reports failure and if   $K(W)\ne 0$ , which implies $F\left(W\right)\ne 0\mathrm{mod}p$ , C does not know the private key of A, but he/she can construct a delegation key related to A. Choose a random $r_2\in Z_p$ and compute a delegation key:

$$\begin{array}{cc}& {\sigma }_B=\left({\text{pk}}_{Ay}^{-J\left(W\right)/F\left(W\right)}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_{\mathrm{2}}}{\text{pk}}_{Ay}^{-x_{\mathrm{1}}},{\text{pk}}_{Ay}^{-\mathrm{1}/F\left(W\right)}{g}^{r_{\mathrm{2}}}\right).\end{array}$$

(17)

Let $x_{\mathrm{2}}=a-x_{\mathrm{1}}$ and ${\tilde{r}}_{\mathrm{2}}=r_{\mathrm{2}}-(b/F\left(W\right))$ (C does not know these values). Then, the correction of delegation key ${\sigma }_B$ can be proven as follows:

$$\begin{array}{cc}& {\sigma }_{B\mathrm{1}}={\text{pk}}_{Ay}^{-J\left(W\right)/F\left(W\right)}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_{\mathrm{2}}}{\text{pk}}_{Ay}^{-x_{\mathrm{1}}}={\text{pk}}_{Ay}^{-J\left(W\right)/F\left(W\right)}{\left({\text{pk}}_{Ax}^{F\left(W\right)}{g}^{J\left(W\right)}\right)}^{r_{\mathrm{2}}}{\text{pk}}_{Ay}^{-x_{\mathrm{1}}}={\left({\text{pk}}_{Ax}^{F\left(W\right)}{g}^{J\left(W\right)}\right)}^{r_{\mathrm{2}}-\left(b/F\left(W\right)\right)}{\text{pk}}_{Ax}^b{\text{pk}}_{Ay}^{-x_{\mathrm{1}}}={\text{pk}}_{Ay}^{a-x_{\mathrm{1}}}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_{\mathrm{2}}-\left(b/F\left(W\right)\right)}={\text{pk}}_{Ay}^{x_{\mathrm{2}}}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{{\tilde{r}}_{\mathrm{2}}}.\end{array}$$

(18)

Additionally, ${\sigma }_{B\mathrm{2}}={\text{pk}}_{Ay}^{-\mathrm{1}/F(W)}{g}^{r_{\mathrm{2}}}=g^{r_{\mathrm{2}}-\left(b/F(W)\right)}=g^{{\tilde{r}}_{\mathrm{2}}}$ .

C computes $R_A=g^{r_{\mathrm{1}}}{g}^{{\tilde{r}}_{\mathrm{2}}}$ and gives $A_{\mathrm{I}\mathrm{I}}$ the SEM-Delegation key ${\sigma }_S$ and User-Delegation key ${\sigma }_B$ .

If $F(W)\ne 0\mathrm{mod}p$ , C first produces delegation keys ${\sigma }_S$ and ${\sigma }_B$ by the Delegation-Gen query described above, and then he/she runs the SEM-Sign algorithm and User-Sign algorithm to answer $A_{\mathrm{I}\mathrm{I}}$ 's query since he/she knows the private key of B. Otherwise, C will construct a proxy signature in the same way as the construction of the delegation keys in the Delegation-Gen query. Then, C constructs the S's partial proxy signature and the user's complete proxy signature of ω on M in the following ways.

(3) SEM-Sign Query. C first chooses four random integers $x_1,r_1,r_s,k_1\in Z_p$ and computes

$$\begin{array}{cc}& h_{\mathrm{1}}=H\left(M\parallel \omega ,{\text{pk}}_{Ax}^{-\mathrm{1}/F\left(W\right)}·g^{r_{\mathrm{1}}+r_s},g^{k_{\mathrm{1}}}\right),\\ {\sigma }_{\text{ps}}=\left({\text{pk}}_{Ay}^{x_{\mathrm{1}}}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_{\mathrm{1}}+r_s}{\left(Mv\right)}^{h_{\mathrm{1}}{k}_{\mathrm{1}}},g^{r_s+r_{\mathrm{1}}},g^{h_{\mathrm{1}}{k}_{\mathrm{1}}}\right).\end{array}$$

(19)

(4) User-Sign Query. C chooses three integers $r_2,r_B,k_2\in Z_p$ and computes

$$\begin{array}{cc}& h_{\mathrm{2}}=H\left(M\parallel \omega ,{\text{pk}}_{Ax}^{-\mathrm{1}/F\left(W\right)}·g^{r_{\mathrm{2}}+r_B},g^{k_{\mathrm{2}}}\right),\\ \sigma =\left({\text{pk}}_{Ay}^{-J\left(W\right)/F\left(W\right)}{g}^{{\text{sk}}_{Bx}{\text{sk}}_{By}}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_{\mathrm{1}}+r_{\mathrm{2}}+r_s+r_B}{\left(Mv\right)}^{h_{\mathrm{1}}{k}_{\mathrm{1}}+h_{\mathrm{2}}{k}_{\mathrm{2}}},{\text{pk}}_{Ay}^{-\mathrm{1}/F\left(W\right)}{g}^{r_{\mathrm{1}}+r_{\mathrm{2}}+r_s+r_B},g^{h_{\mathrm{1}}{k}_{\mathrm{1}}+h_{\mathrm{2}}{k}_{\mathrm{2}}}\right).\end{array}$$

(20)

We will prove the correctness of the proxy signature as follows:

$$\begin{array}{cc}& {\sigma }_{\mathrm{1}}={\text{pk}}_{Ay}^{-J\left(W\right)/F\left(W\right)}{g}^{{\text{sk}}_{Bx}{\text{sk}}_{By}}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_{\mathrm{1}}+r_{\mathrm{2}}+r_s+r_B}{\left(Mv\right)}^{h_{\mathrm{1}}{k}_{\mathrm{1}}+h_{\mathrm{2}}{k}_{\mathrm{2}}}={\text{pk}}_{Ax}^b{g}^{{\text{sk}}_{Bx}{\text{sk}}_{By}}{\left(u^{\prime }\prod _{i\in W}{u}_i\right)}^{r_{\mathrm{1}}+r_{\mathrm{2}}+r_s+r_B-\left(b/F\left(W\right)\right)}{\left(Mv\right)}^{h_{\mathrm{1}}{k}_{\mathrm{1}}+h_{\mathrm{2}}{k}_{\mathrm{2}}},\\ {\sigma }_{\mathrm{2}}={\text{pk}}_{Ay}^{-\mathrm{1}/F\left(W\right)}{g}^{r_{\mathrm{1}}+r_{\mathrm{2}}+r_s+r_B}=g^{r_{\mathrm{1}}+r_{\mathrm{2}}+r_s+r_B-\left(b/F\left(W\right)\right)}.\end{array}$$

(21)

(iii) If C does not abort during the simulation, the adversary will return a proxy signature ${\sigma }^{\ast }=({\sigma }_{\mathrm{1}}^{\ast },{\sigma }_{\mathrm{2}}^{\ast },{\sigma }_{\mathrm{3}}^{\ast })$ on the message $M^{\ast }$ under the warrant ${\omega }^{\ast }$ with the probability of at least ε for B. If $F\left(W^{\ast }\right)=0\mathrm{mod}p$ , $u^{\prime }{\prod }_{i\in W^{\ast }}{u}_i=g^{J(W^{\ast })}$ . Since ${\sigma }^{\ast }$ is a valid proxy signature of the message $M^{\ast }$ under the warrant ${\omega }^{\ast }$ , we have

$$\begin{array}{cc}& e\left({\sigma }_{\mathrm{1}}^{\ast },g\right)=e\left({\text{pk}}_{Ax},{\text{pk}}_{Ay}\right)e\left({\text{pk}}_{Bx},{\text{pk}}_{By}\right)e\left(u^{\prime }{\displaystyle \prod }_{i\in W^{\ast }}{u}_i,{\sigma }_{\mathrm{2}}^{\ast }\right)e\left(Mv,{\sigma }_{\mathrm{3}}^{\ast }\right)=e\left(g^a,g^b\right)e\left(g^{{\text{sk}}_{Bx}},g^{{\text{sk}}_{By}}\right)e\left(g^{J\left(W^{\ast }\right)},{\sigma }_{\mathrm{2}}^{\ast }\right)e\left(Mv,{\sigma }_{\mathrm{3}}^{\ast }\right).\end{array}$$

(22)

Then, we can compute out

$$\begin{array}{cc}& g^{ab}=\frac{{\sigma }_{\mathrm{1}}^{\ast }}{{\left({\sigma }_{\mathrm{2}}^{\ast }\right)}^{J\left(W^{\ast }\right)}{\left(Mv\right)}^{h_{\mathrm{1}}{k}_{\mathrm{1}}+h_{\mathrm{2}}{k}_{\mathrm{2}}}{g}^{{\text{sk}}_{Bx}{\text{sk}}_{By}}}.\end{array}$$

(23)

This completes the description of the simulation. Now we have to assess C's probability of success. C will not abort if the following conditions hold.

• (1)

$K\left(W^{\ast }\right)\ne 0\mathrm{mod}l$ during the Delegation-Gen queries.

(2)

$F(W^{\ast })=0\mathrm{mod}p$ in the forgery phase.

The success probability is $\mathrm{S}\mathrm{u}\mathrm{c}{\mathrm{c}}_C^{\mathrm{C}\mathrm{D}\mathrm{H}}=\mathrm{pr}[A\wedge B]$ . Now we use Waters' technique [14] to compute a lower bound of C's success probability:

$$\begin{array}{cc}& \mathrm{pr}\left[A\wedge B\right]=\mathrm{pr}\left[{\displaystyle \bigcap }_{\mathrm{1}}^{q_w}K\left(W_i\right)\ne \mathrm{0}\wedge F\left(W^{\ast }\right)=\mathrm{0}\mathrm{mod}p\right]=\mathrm{pr}\left[{\displaystyle \bigcap }_{i=\mathrm{1}}^{q_w}K\left(W_i\right)\ne \mathrm{0}\right]\mathrm{pr}\left[F\left(W^{\ast }\right)=\mathrm{0}\mathrm{mod}p\mid {\displaystyle \bigcap }_{i=\mathrm{1}}^{q_w}K\left(W_i\right)\ne \mathrm{0}\right]\ge \left(\mathrm{1}-\frac{q_w}{l}\right)\mathrm{pr}\left[x^{\prime }+{\displaystyle \sum }_{i\in W}{x}_i=lk\mid {\displaystyle \bigcap }_{i=\mathrm{1}}^{q_w}K\left(W_i\right)\ne \mathrm{0}\right]=\left(\frac{\mathrm{1}}{n+\mathrm{1}}\right)\left(\mathrm{1}-\frac{q_w}{l}\right)\mathrm{pr}\left[K\left(W^{\ast }\right)=\mathrm{0}\mid {\displaystyle \bigcap }_{i=\mathrm{1}}^{q_w}K\left(W_i\right)\ne \mathrm{0}\right]\ge \left(\frac{\mathrm{1}}{n+\mathrm{1}}\right){\left(\mathrm{1}-\frac{q_w}{l}\right)}^{\mathrm{2}}\frac{\mathrm{1}}{l}\ge \left(\frac{\mathrm{1}}{n+\mathrm{1}}\right)\left(\mathrm{1}-\frac{\mathrm{2}{q}_w}{l}\right)\frac{\mathrm{1}}{l}.\end{array}$$

(24)

Therefore, $\mathrm{S}\mathrm{u}\mathrm{c}{\mathrm{c}}_C^{\mathrm{C}\mathrm{D}\mathrm{H}}\ge (\mathrm{1}/\left(n+\mathrm{1}\right)l)(\mathrm{1}-(\mathrm{2}{q}_w/l))\epsilon$ . We can optimize it by setting $l=\mathrm{4}{q}_w$ ; then

$$\begin{array}{cc}& {\text{Succ}}_C^{\text{CDH}}\ge \frac{\epsilon }{\mathrm{8}\left(n+\mathrm{1}\right)q_w}.\end{array}$$

(25)

Algorithm C's running time equals $A_{\mathrm{I}\mathrm{I}}$ 's running time which adds the time it takes to simulate the security proof. $2n+5$ exponentiation operations and $n+1$ multiplication operations in G are needed in the Setup phase. Ten exponentiation operations and $5+n$ multiplication operations are required in every Delegation-Gen query. ProxySign-Gen query needs 12 exponentiation operations and $6+n$ multiplication operations. In the forgery phase, 3 exponentiation operations and 3 multiplication operations are needed. If we assume each exponentiation operation takes time $T_e$ , and multiplication operation takes time $T_m$ , so the total running time of algorithm C is at most $t+((n+\mathrm{5})q_w+(n+\mathrm{6})q_{\mathrm{p}\mathrm{s}}+n+\mathrm{4})T_m+(\mathrm{10}{q}_w+\mathrm{12}{q}_{\mathrm{p}\mathrm{s}}+\mathrm{2}n+\mathrm{8})T_e$ .

Theorem 8.

The strongly unforgeable proxy signature with fast revocation is $({\epsilon }^{\prime },t^{\prime },\mathrm{0},q_{\text{ps}})$ secure against a type adversary $A_{\text{III}}$ assuming that the $({\epsilon }^{\prime },t^{\prime })\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{CDH}$ assumption holds in G, where

$$\begin{array}{cc}& {\text{Succ}}_C^{\text{CDH}}\ge \frac{{\epsilon }^{\prime }}{nl}\end{array}$$

(26)

within running time $t^{\prime }\le t+((n+\mathrm{6})q_{\text{ps}}+n+\mathrm{4})T_m+(\mathrm{12}{q}_{\text{ps}}+\mathrm{2}n+\mathrm{8})T_e$ .

Proof.

This proof is similar to that of Theorem 7 and thus we omit the detailed proof to save space. Here, we only illustrate the differences between them. First, we recall the capacity of adversary $A_{\mathrm{I}\mathrm{I}\mathrm{I}}$ . This type has the public keys of A and B, and the secret key of the original signer. Therefore, $A_{\text{III}}$ does not need Delegation-Gen queries and can generate delegations on arbitrary warrants. Secondly, in the Setup phase, the simulator should set the public key of the proxy signer as $({\text{pk}}_{Bx},{\text{pk}}_{By})=(g^a,g^b)$ , where $g^a$ and $g^b$ are the inputs of the given CDH problem instance. Other parts of this proof are similar to those of Theorem 7.

From Theorems 7 and 8, it can be seen that the proposed scheme can prevent Type II or Type III attacks; that is to say, our scheme has the strong unforgeability in the standard model. In fact, the reason why the existing proxy signature schemes with revocation cannot achieve the strong unforgeability results from their design method. From the aspect of the algorithm construction mechanism, the existing schemes can be regarded as 2-level hierarchical Waters' signature. However, Waters et al.'s scheme is malleable [5, 14], in which an adversary can generate a different valid signature on the same message even without the private key. In more details, in Waters' signature, we suppose that the signature of a message is denoted by $\sigma =({\sigma }_{\mathrm{1}},{\sigma }_{\mathrm{2}})$ . Anyone can create a valid signature in the following way: First, pick up an integer r and make the following equations hold: ${\stackrel{-}{\sigma }}_{\mathrm{1}}={\sigma }_{\mathrm{1}}(u^{\prime }{\prod }_{i\in M}{u}_i{)}^r$ and ${\stackrel{-}{\sigma }}_{\mathrm{2}}={\sigma }_{\mathrm{2}}{g}^r$ . Then, $\stackrel{-}{\sigma }=({\stackrel{-}{\sigma }}_{\mathrm{1}},{\stackrel{-}{\sigma }}_{\mathrm{2}})$ can be proven to be a valid signature. This weakness makes the existing proxy signature schemes with revocation not strongly unforgeable. However, in our scheme, we adopt different algorithm construction method, and our scheme is not 2-level hierarchical Waters' signature. Therefore, our scheme avoids the above attack and achieves the strong unforgeability.

5.3. Comparison with Existing Schemes

In this section, we will compare our scheme with other existing proxy signature schemes [3–12] in terms of the number of the public parameters, the size of the signature, the computational efficiency of the delegation stage, the proxy sign stage, and proxy sign verification stage. In order to facilitate the description, we define the symbols shown in Table 2.

Table 2

Symbol meaning.

Symbols	Meaning
n	The numbers of the warrant/message
t	The threshold in the threshold proxy signature
m	The number of the original or proxy signers in the multiproxy signature or proxy multisignature scheme
$$T_m$$	Time for multiplication operations in G
$$T_e$$	Time for exponentiation operations in G
E	Time for multiplication operations in $G_T$
P	Time for pairing operations

First, we will discuss the proxy signature process. In the proposed scheme, we consider the computational complexity. In order to delegate the proxy signer, the scheme needs 7 exponentiation operations in G, and $n+2$ multiplication operations in G. In the phase of ProxySign-Gen, our scheme needs 9 exponentiation operations in G, and $2n+8$ multiplication operations in G. In order to verify the signature, 5 pairing operations, 3 multiplication operations in $G_T$ , and $n+1$ multiplication operations in G are needed. For public parameters, only $n+2$ group elements are needed in our scheme. From this point, our scheme is more suitable for low storage requirement of applications such as in an Ad hoc network [30]. The specific comparison results are shown in Table 3, from which we can find that our scheme is much better than most of the existing schemes. Although strong unforgeability and fast revocation are achieved simultaneously, our scheme has almost no increase in computational efficiency as to other proxy signatures with revocation schemes.

Table 3

Proxy signature scheme efficiency comparison.

Schemes	Size	Parameter	Delegation	ProxySign	Verify
Scheme [3]	$3\left|G\right|$	2n + 2	3T e + (n + 1)T m	5T e + (2n + 4)T m + P	4P + 3E + 2nT m
Scheme [4]	$3\left|G\right|$	2n + 2	3T e + (n + 1)T m	5T e + (2n + 4)T m	5P + 3E + 2nT m
Scheme [5]	$3\left|G\right|$	n + 4	3T e + (n + 1)T m	4T e + 3T m	5P + 3E + (n + 1)T m + T e
Scheme [6]	$3\left|G\right|$	2n + 2	(3m + 3)T e + (n + 3m + 1)T m	2T e + (n + 1)T m	(m + 4)P + (m + 2)E + 2nT m
Scheme [7]	$3\left|G\right|$	n + 4	3mT e + (n + m)T m	4T e + (2m + 1)T m	(m + 4)P + (m + 2)E + (n + 1)T m + T e
Scheme [8]	$3\left|G\right|$	2n + 2	nP + (2n + 1)T e + 2nT m	4nT e + 6nT m + tP + (t − 1)E	4P + 3E + 2nT m
Scheme [9]	$3\left|G\right|$	2n + 2	3T e + (n + 1)T m	5T e + (2n + 4)T m + P	5P + 3E + 2nT m
Scheme [10]	$3\left|G\right|$	2n + 2	7T e + (n + 2)T m	9T e + (2n + 8)T m	5P + 3E + (2n + 1)T m
Scheme [11]	$3\left|G\right|$	2n + 2	7T e + (n + 2)T m	9T e + (2n + 8)T m + P	4P + 3E + 2nT m
Scheme [12]	$3\left|G\right|$	2n + 2	(m + n + 1)T e + (3m + 4)T m	8mT e + (2n + 10m − 1)T m	3P + E + (2n + m)T m
Our scheme	$3\left|G\right|$	n + 2	7T e + (n + 2)T m	9T e + (2n + 8)T m	5P + 3E + (n + 1)T m

Size: length of signature. Parameter: the number of system public parameters.Delegation: the computational efficiency in the Delegation-Gen phase. ProxySign: the computational efficiency in the ProxySign-Gen phase. Verify: the computational efficiency in the ProxySign-Verify phase.

Compared to existing schemes, our scheme has some advantages that other schemes do not have. Moreover, as we all know, if pairing operations are executed by sensor nodes, it would affect the efficiency of the sensor networks. But from Table 3, we can know that just ProxySign-Verify needs 5 pairing operations, and it should be executed by a sink node or one proxy equipment but not sensor nodes, so the pairing operations will not affect the efficiency of sensor-based network systems.

The merit/demerit comparison between the existing schemes and our scheme is summarized in Table 4.

Table 4

Comparison of merits and demerits.

Schemes	F.R	S.M	S.U
Scheme [3]	No	Yes	No
Scheme [4]	No	Yes	No
Scheme [5]	No	Yes	No
Scheme [6]	No	Yes	No
Scheme [7]	No	Yes	No
Scheme [8]	No	Yes	No
Scheme [9]	No	Yes	No
Scheme [10]	Yes	Yes	No
Scheme [11]	Yes	Yes	No
Scheme [12]	Yes	Yes	No
Our scheme	Yes	Yes	Yes

F.R: whether the proxy signature can achieve fast revocation. S.M: whether the scheme has security proof in the standard model. S.U: whether the scheme is strongly unforgeable.

From Table 4, we can see that $(1)$ all existing proxy signatures in the standard model are proved secure and $(2)$ our scheme is the only proxy signature scheme that has strong unforgeability and fast revocation in the standard model.

Overall, compared with other proxy signatures [3–12] in the standard model, our scheme has stronger security because it has strong unforgeability and has low storage requirement because it has a shorter system parameter. At the same time, the scheme can achieve fast revocation.

6. Conclusions

Until now, none of the existing proxy signature schemes with revocation possesses strong unforgeablility. This leads to the fact that the adversary can even produce a new signature for a signed message, which makes the existing schemes insecure. In order to solve this security problem, this paper improves the situation and proposes a strongly unforgeable proxy signature with revocation under the computational Diffie-Hellman assumption in the standard model. The proposed scheme satisfies all of the security requirements for proxy signature schemes. Through a security analysis, we show that the proposed scheme is secure in the standard model and it can resist those attacks mentioned above. Furthermore, compared with several proxy signature schemes in the standard model, it is easy to conclude that the proposed scheme has advantages over other schemes, namely, stronger security and shorter system parameters. As a special kind of digital signature, the proxy signature has been widely applied in electronic commerce. With improvement of the proxy signature with revocation, the proposed scheme can be widely used in more applications, such as mobile agent and electronic transactions.