A New Provably Secure Identity-Based Multi-proxy Signature Scheme

Abstract

In a multi-proxy signature scheme, an original signer could delegate his signing power to a designated proxy group. Only the cooperation of all proxy signers in the proxy group could generate a legitimate proxy signature on behalf of the original signer. In this paper, we formalize the definition and security model of the identity-based multi-proxy signature, and we construct a new identity-based multi-proxy signature scheme using bilinear pairings. We show the security of our scheme in the random oracle model, and the security of our scheme is based on the hardness of the computational Diffie-Hellman problem.

1 Introduction

The concept of an identity-based (ID-based) cryptosystem was first introduced by Shamir [20] in 1984. In an ID-based cryptosystem, the user does not generate his key pairs by himself. The system needs a trusted third authority named the private key generator (PKG) to compute the user’s private key, and the user’s public key can be derived as an arbitrary string that indicates the user’s identity information, such as the user’s e-mail address, IP address, and social security number. An ID-based cryptosystem simplifies the problem of key management in traditional public-key cryptography. Due to this advantage, many ID-based cryptosystems have been proposed [1, 3, 5, 12, 21].

In 1996, Mambo et al. [14, 15] introduced the concept of the proxy signature, which solved the problem of the authorization of the signing capability. In a proxy signature scheme, an original signer is allowed to delegate his signing power to a designated person named a proxy signer. Provided with the proxy delegation, the proxy signer could sign a message on behalf of the original signer. Any verifier could be convinced of both the original signer’s authorization and the proxy signer’s signature. Proxy signatures could be used in many situations, especially in applications where the delegation of rights is highly common, such as distributed computing and mobile communications. To date, many proxy signature schemes have been proposed [2, 7, 9, 18, 19, 23].

The primitive of the multi-proxy signature was first introduced by Hwang and Shi in 2000 [8]. In a multi-proxy signature scheme, an original signer can delegate his signing power to a designated proxy group. Only the cooperation of all proxy signers in the proxy group could generate a legitimate proxy signature on behalf of the original signer. The multi-proxy signature scheme can be regarded as a special threshold proxy signature scheme [24]. Since that work, some multi-proxy signature schemes have been successively proposed [10, 11, 16, 17], but they lacked provable security, and their securities were only heuristically analyzed. In 2009, Cao and Cao [4] gave the first formal definition and security model of an ID-based multi-proxy signature and then proposed an ID-based multi-proxy signature scheme using bilinear pairings. However, Xiong et al. [22] showed that Cao-Cao’s scheme was not secure under their security model. These researchers proposed an improved scheme, but they did not give the formal security proof of the improved scheme. Moreover, some provably secure multi-proxy signature schemes in the standard model have been proposed [6, 13].

In this paper, based on the work of Bellare et al. [1] and Cao and Cao [4], we give a formal definition and security model of an ID-based multi-proxy signature scheme. Then, we present a concrete ID-based multi-proxy signature scheme that meets our definition. Our scheme is provably secure in the random oracle model, and the security of our scheme is based on the hardness of computational Diffie-Hellman problem. To the best of our knowledge, to date, our scheme is the only ID-based multi-proxy signature scheme using bilinear pairings that is proved to be secure in the random oracle model.

The rest of this paper is organized as follows. In Sect. 2, we introduce some preliminaries. In Sect. 3, we give a formal definition and security model of the ID-based multi-proxy signature scheme. In Sect. 4, we propose a new ID-based multi-proxy signature scheme. In Sect. 5, we prove our scheme’s security and compare the efficiency of our scheme with some similar schemes. The final section is the conclusion.

2 Preliminaries

In this section, we introduce some concepts for bilinear pairings and the computational Diffie-Hellman problem.

2.1 Bilinear Pairings

Let $(G_{1} , + )$ and $(G_{2} , \cdot )$ be two groups of prime order $q$. We call a map $e:G_{1} \times G_{1} \to G_{2}$ a bilinear pairing if it satisfies the following properties:

• Bilinear: For any P, $Q \in G_{1}$, and any $\alpha$, $\beta \in Z_{q}$, we have $e(\alpha P,\beta Q) = e(P,Q)^{\alpha \beta }$;

• Nondegenerate: Their exists P, $Q \in G_{1}$, such that $e(P,Q) \ne 1$;

• Computable: For any P, $Q \in G_{1}$, there is an efficient algorithm to compute $e(P,Q)$.

2.2 Computational Assumption

The security of our scheme is based on the hardness of the computational Diffie-Hellman problem.

Definition 1.

Computational Diffie-Hellman (CDH) problem. Let $G_{1}$ be a group of prime order $q$ with generator P. Given aP, $bP \in G_{1}$, where a, $b \in Z_{q}^{ * }$, compute abP.

Definition 2.

CDH Assumption. We say that the $(t,\varepsilon )$-CDH assumption holds in group $G_{1}$ if no probabilistic algorithm can solve the CDH problem in $G_{1}$ with a non-negligible probability of at least $\varepsilon$ within polynomial time t.

3 Definition and Security Model of Identity-Based Multi-proxy Signature

In this section, we give a formal definition and security model for our ID-based multi-proxy signature scheme.

3.1 Definition of Identity-Based Multi-proxy Signature

We give the definition of the ID-based multi-proxy signature scheme as follows. More details can be found in [4].

Definition 3.

An identity-based multi-proxy signature scheme consists of the following algorithms: Setup, User-Key-Gen, Delegation-Gen, Multi-Proxy-Sign, and Multi-Proxy-Verify. It is composed of the following entities: the key generation center KGC, the original signer $U_{0}$, the proxy signers $U_{i}$$(i = 1,2, \cdots ,n)$, and the verifier.

• Setup: This algorithm is run by the KGC on the input security parameter $1^{k}$, and it generates the system’s master key $s$ and public parameters $params$.

• User-Key-Gen: This algorithm is run by the KGC. It takes as inputs the $params$, the identity $ID_{0}$ of the original signer $U_{0}$, or the identity $ID_{i}$ of the proxy signer $U_{i}$$(i = 1,2, \cdots ,n)$, and then returns the corresponding private key $S_{{ID_{i} }}$$(i = 0,1,2, \cdots ,n)$.

• Delegation-Gen: This algorithm is run by the original signer $U_{0}$. It takes as inputs the $params$, his private key $S_{{ID_{0} }}$, the identity $ID_{i}$ of the proxy signer $U_{i}$$(i = 1,2, \cdots ,n)$, and a warrant message $w$, and it outputs a proxy delegation $\sigma_{0}$.

• Multi-Proxy-Sign: This algorithm is run by every proxy signer $U_{i}$. It takes as inputs the $params$, the private key $S_{{ID_{i} }}$, the delegation $\sigma_{0}$ and the message m, and it outputs a partial proxy signature S_i $(i = 1,2, \cdots ,n)$. Then, $U_{i}$ sends S_i to a clerk who is a designated proxy signer in the proxy group. The clerk verifies the validity of S_i, and it returns the multi-proxy signature S if all of S_i are accepted; otherwise, the algorithm stops.

• Multi-Proxy-Verify: It takes as inputs the $params$, the identities $ID_{0}$ and $ID_{i}$$(i = 1,2, \cdots ,n)$, the message m and the multi-proxy signature S. The algorithm outputs 1 if S is a valid multi-proxy signature, and it outputs 0 otherwise.

3.2 Security Model of Identity-Based Multi-proxy Signature

According to the security model of the proxy signature that is proposed in [14, 15], the security of the proxy signature is mainly considered based on the unforgeability of the delegation and the proxy signature. The unforgeability of the delegation means that an adversary could not forge an efficient delegation on behalf of the original signer, and the proxy signer could not generate a valid proxy signature without the delegation. The unforgeability of the proxy signature means that nobody (including the original signer) could generate a legitimate proxy signature without the proxy signer’s private key.

In our model, we consider the adversary who can adaptively choose an identity $ID_{0}$ for an original signer or an identity $ID_{i}$ for a proxy signer, and then acts as a user with the identity of $ID_{0}$ or $ID_{i}$ when executing the multi-proxy signature scheme with other users. Therefore, we can divide the potential adversaries into the following two kinds:

Type I:

Adversary $A_{\text{I}}$ attempts to forge a multi-proxy signature without the delegation. For the adversary $A_{\text{I}}$, we mainly model the malicious proxy signer. Moreover, adversary $A_{\text{I}}$ can be considered as a collusion attack from multiple proxy signers.

Type II:

Adversary $A_{\text{II}}$ attempts to forge a multi-proxy signature without the proxy signer’s private key. For the adversary $A_{\text{II}}$, we mainly model the malicious original signer.

According to the work of [4], we define the security model of an ID-based multi-proxy signature as follows.

Definition 4.

Let $A_{\text{I}}$ and $A_{\text{II}}$ be adversaries that act as the malicious proxy signer and the original signer, respectively. The security of an ID-based multi-proxy signature scheme is modeled by the following games between a challenger C and $A_{\text{I}}$ and $A_{\text{II}}$, respectively.

$Game\text{ }1$

The challenger C inputs a security parameter $1^{k}$, performs the Setup algorithm, generates the system parameters $params$, and then C sends $params$ to $A_{\text{I}}$. $A_{\text{I}}$ can carry out the following queries in polynomial bounded times.

• Hash query: $A_{\text{I}}$ can query the value of all Hash functions in the scheme.

• User-Key query: $A_{\text{I}}$ can input an arbitrary user’s identity $ID_{i}$ to query the private key $S_{{ID_{i} }}$. C performs the User-Key-Gen algorithm to generate $S_{{ID_{i} }}$ and returns the result to $A_{\text{I}}$.

• Delegation query: $A_{\text{I}}$ can query the proxy delegation certificate $\sigma_{0}$ of a chosen warrant message $w$. C performs the Delegation-Gen algorithm and then returns the result to $A_{\text{I}}$.

• Multi-Proxy-Sign query: $A_{\text{I}}$ can input the original signer’s identity $ID_{0}$, the proxy signer’s identity $ID_{i}$$(i = 1,2, \cdots ,n)$, the warrant message $w$ and the message m, and queries the multi-proxy signature on m. C performs the Multi-Proxy-Sign algorithm to generate a multi-proxy signature S and then returns the result to $A_{\text{I}}$.

Finally, $A_{\text{I}}$ outputs a multi-proxy signature S^* on message m using the proxy signers $U_{i}$$(i = 1,2, \cdots ,n)$ with the warrant message $w$. We say that $A_{\text{I}}$ wins the game if and only if the multi-proxy signature S^* is accepted by the verifier, the warrant message $w$ has not been queried in the Delegation query, and $(w,m)$ has not been queried in the Multi-Proxy-Sign query.

$Game\text{ }2$

The challenger C inputs a security parameter $1^{k}$, performs the Setup algorithm, generates the system parameters $params$, and then C sends $params$ to $A_{\text{II}}$. $A_{\text{II}}$ can perform the same queries as $Game\text{ }1$ in polynomial bounded times.

Finally, $A_{\text{II}}$ outputs a multi-proxy signature S^* on message m using the proxy signers $U_{i}$$(i = 1,2, \cdots ,n)$ with the warrant message $w$. We say that $A_{\text{II}}$ wins the game if and only if the multi-proxy signature S^* is accepted by the verifier, there is at least one $ID_{I} \in \{ ID_{1} ,ID_{2} , \cdots ,ID_{n} \}$ that has not been queried in the User-Key query, and $(w,m)$ has not been queried in the Multi-Proxy-Sign query.

Definition 5.

An identity-based multi-proxy signature scheme is existentially unforgeable against the chosen massage attack and chosen warrant attack if and only if there is no probabilistic polynomial-time (PPT) adversary that could win the above games with a non-negligible probability.

4 Identity-Based Multi-proxy Signature Scheme

In this section, we propose a new ID-based multi-proxy signature scheme based on the ID-based signature scheme that was constructed by Sakai-Ogishi-Kasahara [1, 12].

Setup:

Given a security parameter $1^{k}$, let $G_{1}$ be an additive group of prime order $q$ with a generator P, $G_{2}$ is a multiplicative group with the same prime order, and $e:G_{1} \times G_{1} \to G_{2}$ is a bilinear map. The KGC chooses the hash functions $H_{1} :\{ 0,1\}^{ * } \to G_{1}$, $H_{2} :\{ 0,1\}^{ * } \times G_{1} \to G_{1}$ and $H_{3} :\{ 0,1\}^{ * } \times G_{1} \times G_{1} \to Z_{q}^{ * }$. The KGC randomly chooses $s \in Z_{q}^{ * }$ as the master key, computes the system public key $P_{pub} = sP$, and then publishes the system parameters $params = (G_{1} ,G_{2} ,q,e,P,P_{pub} ,H_{1} ,H_{2} ,H_{3} )$.

User-Key-Gen:

Given the identity $ID_{0}$ of the original signer $U_{0}$ or the identity $ID_{i}$ of the proxy signer $U_{i}$, where $1 \le i \le n$, the KGC computes $Q_{{ID_{i} }} = H_{1} (ID_{i} )$ and $S_{{ID_{i} }} = sQ_{{ID_{i} }}$, and then it sends $S_{{ID_{i} }}$ to $U_{i}$$(i = 0,1,2, \cdots ,n)$ via a secure channel.

Delegation-Gen:

The original signer $U_{0}$ generates the proxy warrant message $w$, which includes the identity information of the original signer and proxy signers, the scope of the proxy authority, and the delegation period.

• 1. $U_{0}$ randomly chooses $r_{0} \in Z_{q}^{ * }$, and computes $R_{0} = r_{0} P$.

• 2. $U_{0}$ computes $h_{0} = H_{2} (w,R_{0} )$, $V_{0} = r_{0} h_{0} + S_{{ID_{0} }}$.

• 3. $U_{0}$ sends a proxy warrant message $w$ and its signature $\sigma_{0} = (R_{0} ,V_{0} )$ to the proxy signers $U_{i}$$(i = 1,2, \cdots ,n)$ via a secure channel.

The proxy signer $U_{i}$ computes $h_{0} = H_{2} (w,R_{0} )$, and then checks the following equation:

$$ e(P,V_{0} ) = e(P_{pub} ,Q_{{ID_{0} }} )e(R_{0} ,h_{0} ). $$

If the equality holds, $U_{i}$ accepts $\sigma_{0}$ as a valid delegation.

Multi-Proxy-Sign:

Given a message m to be signed, for $1 \le i \le n$, the proxy signer $U_{i}$ can sign the message m as follows:

• 1. $U_{i}$ randomly chooses $r_{i} \in Z_{q}^{ * }$, computes $R_{i} = r_{i} P$, and broadcasts $R_{i}$ to the other proxy signers.

• 2. $U_{i}$ computes $R = \sum\limits_{i = 1}^{n} {R_{i} }$, $h_{0} = H_{2} (w,R_{0} )$, $h = H_{3} (m,R_{0} ,R)$, and $V_{i} = r_{i} h_{0} + hS_{{ID_{i} }} + V_{0}$.

• 3. $U_{i}$ sends the partial proxy signature $\sigma_{i} = (w,R_{0} ,R_{i} ,V_{i} )$ to the clerk who is a designated proxy signer in the proxy group.

• 4. The clerk computes $R = \sum\limits_{i = 1}^{n} {R_{i} }$, $h_{0} = H_{2} (w,R_{0} )$, $h = H_{3} (m,R_{0} ,R)$, then verifies the validity of $\sigma_{i}$ using the following equation:

$$ e(P,V_{i} ) = e(P_{pub} ,hQ_{{ID_{i} }} + Q_{{ID_{0} }} )e(R_{i} + R_{0} ,h_{0} ),\;i = 1,2, \cdots ,n $$

If all of the equalities hold, the clerk computes $V = \sum\limits_{i = 1}^{n} {V_{i} }$, and then the multi-proxy signature on message m is $\sigma = (w,R_{0} ,R,V)$.

Multi-Proxy-Verify:

To verify a multi-proxy signature $\sigma = (w,R_{0} ,R,V)$, the verifier computes $h_{0} = H_{2} (w,R_{0} )$, $h = H_{3} (m,R_{0} ,R)$, and accepts the signature if and only if the following equation holds:

$$ e(P,V) = e(P_{pub} ,nQ_{{ID_{0} }} + h\sum\limits_{i = 1}^{n} {Q_{{ID_{i} }} } )e(nR_{0} + R,h_{0} ). $$

5 Analysis of Our Scheme

5.1 Correctness

The correctness of a partial proxy signature can be proved by the following:

$$ \begin{aligned} e(P,V_{i} ) & = e(P,r_{i} h_{0} + hS_{{ID_{i} }} + V_{0} ) \\ & = e(P,r_{i} h_{0} )e(P,hS_{{ID_{i} }} )e(P,r_{0} h_{0} )e(P,S_{{ID_{0} }} ) \\ & = e(r_{i} P,h_{0} )e(P_{Pub} ,hQ_{{ID_{i} }} )e(r_{0} P,h_{0} )e(P_{Pub} ,Q_{{ID_{0} }} ) \\ & = e(P_{pub} ,hQ_{{ID_{i} }} + Q_{{ID_{0} }} )e(R_{i} + R_{0} ,h_{0} ). \\ \end{aligned} $$

The proposed ID-based multi-proxy signature scheme is correct according to the following:

$$ \begin{aligned} e(P,V) & = e(P,\sum\limits_{i = 1}^{n} {(r_{i} h_{0} + hS_{{ID_{i} }} + V_{0} )} ) \\ & = e(P,\sum\limits_{i = 1}^{n} {r_{i} h_{0} } )e(P,h\sum\limits_{i = 1}^{n} {S_{{ID_{i} }} } )e(P,nr_{0} h_{0} )e(P,nS_{{ID_{0} }} ) \\ & = e(\sum\limits_{i = 1}^{n} {r_{i} P} ,h_{0} )e(P_{Pub} ,h\sum\limits_{i = 1}^{n} {Q_{{ID_{i} }} } )e(nr_{0} P,h_{0} )e(P_{Pub} ,nQ_{{ID_{0} }} ) \\ & = e(P_{pub} ,nQ_{{ID_{0} }} + h\sum\limits_{i = 1}^{n} {Q_{{ID_{i} }} } )e(nR_{0} + R,h_{0} ). \\ \end{aligned} $$

5.2 Security Proof of Our Scheme

In this section, we will prove that our scheme is secure in the random oracle model. The Delegation-Gen algorithm in our scheme is the ID-based signature scheme that was constructed by Sakai-Ogishi-Kasahara [1, 12], which was proved to be secure, such that an adversary could not forge a valid delegation certificate without the original signer’s private key.

Theorem 1.

In the random oracle model, let $A_{\text{I}}$ be a PPT adversary with the non-negligible probability $\varepsilon$ to win $Game\text{ }1$ in time t. Assume that $A_{\text{I}}$ makes at most $q_{{H_{i} }}$ queries to the hash functions $H_{i}$$(i = 1,2,3)$, at most $q_{K}$ queries to the User-Key-Gen oracle, at most $q_{D}$ queries to the Delegation-Gen oracle, and at most $q_{P}$ queries to the Multi-Proxy-Sign oracle. Then, there exists an algorithm C with the probability $\varepsilon^{\prime} \ge \varepsilon \frac{1}{{(q_{K} + q_{D} + n + 1)e}}$ to solve the CDH problem in time $t^{\prime} < t + (q_{{H_{1} }} + q_{K} + q_{{H_{2} }} + 3q_{D} + 3nq_{P} + n + 4)t_{s} + t_{i}$, where $t_{i}$ is the time of an inversion computation in $Z_{q}^{ * }$, and $t_{s}$ is the time of a scalar multiplication in $G_{1}$.

Proof:

Let $(P,aP,bP)$ be a random instance of the CDH problem in $G_{1}$ acting as a challenger of $A_{\text{I}}$. C could compute $abP$ via $Game\text{ }1$ as follows.

C runs the setup algorithm, sets the system public key $P_{Pub} = aP$, and generates the system parameters $params$. Then, it gives $params$ to $A_{\text{I}}$. C maintains an H₁-list $(ID_{i} ,Q_{{ID_{i} }} ,t_{i} ,c_{i} )$ to hold the value of hash function $H_{1}$, a UK-list $(ID_{i} ,S_{{ID_{i} }} )$ to hold the user’s private key, an H₂-list $(w,R_{0} ,h_{0} ,d_{0} )$ to hold the value of hash function $H_{2}$, a Del-list $(ID_{0} ,w,r_{0} ,R_{0} ,V_{0} )$ to hold the delegation certificate, and a H₃-list $(m,R_{0} ,R,h)$ to hold the value of hash function $H_{3}$.

$A_{\text{I}}$ can conduct queries as follows.

H₁ Query:

When $A_{\text{I}}$ makes H₁ query $ID_{i}$$(i = 0,1,2, \cdots ,n)$, $ID_{0}$ is the identity of the original signer, and $ID_{i}$$(i = 1,2, \cdots ,n)$ are the identities of the proxy signers. C responds as follows.

• (1) For $0 \le i \le n$, if $ID_{i}$ has been queried, C returns $Q_{{ID_{i} }}$ from the H₁-list.

• (2) Otherwise, C randomly chooses $t_{i} \in Z_{q}^{ * }$, and generates a random coin $c_{i} \in \{ 0,1\}$ such that $\Pr [c_{i} = 0] = \delta$ and $\Pr [c_{i} = 1] = 1 - \delta$, where $0 < \delta < 1$.

Then, C sets $Q_{{ID_{i} }} = H_{1} (ID_{i} ) = t_{i} P$ if $c_{i} = 0$, and sets $Q_{{ID_{i} }} = t_{i} (bP)$ if $c_{i} = 1$.

Finally, C adds $(ID_{i} ,Q_{{ID_{i} }} ,t_{i} ,c_{i} )$ into the H₁-list, and returns $Q_{{ID_{i} }}$ to $A_{\text{I}}$.

User-Key Query:

When $A_{\text{I}}$ queries the private key of $ID_{i}$, C responds as follows.

• (1) C searches the UK-list. If $ID_{i}$ has been queried, then C returns the corresponding private key $S_{{ID_{i} }}$ to $A_{\text{I}}$.

• (2) Otherwise, C searches the H₁-list to get $(ID_{i} ,Q_{{ID_{i} }} ,t_{i} ,c_{i} )$. When there is no record of $ID_{i}$ in the H₁-list, C will create $(ID_{i} ,Q_{{ID_{i} }} ,t_{i} ,c_{i} )$ according to the H₁ query.

If $c_{i} = 0$, C computes $S_{{ID_{i} }} = t_{i} (aP)$, returns $S_{{ID_{i} }}$ to $A_{\text{I}}$ and adds $(ID_{i} ,S_{{ID_{i} }} )$ into the UK-list. If $c_{i} = 1$, C outputs “failure” and terminates the simulation.

H₂ Query:

When $A_{\text{I}}$ makes an H₂ query on $(w,R_{0} )$, C responds as follows.

• (1) If $(w,R_{0} )$ has been queried, C returns $h_{0}$ from the H₂-list;

• (2) Otherwise, C randomly chooses $d_{0} \in Z_{q}^{ * }$, and $d_{0}$ has not been in the H₂-list. C computes $h_{0} = d_{0} P$ and returns $h_{0}$ to $A_{\text{I}}$. Then, C adds $(w,R_{0} ,h_{0} ,d_{0} )$ into the H₂-list.

H₃ Query:

When $A_{\text{I}}$ makes an H₃ query on $(m,R_{0} ,R)$, C responds as follows.

• (1) If $(m,R_{0} ,R)$ has been queried, C returns $h$ from the H₃-list;

• (2) Otherwise, C randomly chooses $h \in Z_{q}^{ * }$, and $h$ has not been in H₃-list. Then, C returns $h$ to $A_{\text{I}}$ and adds $(m,R_{0} ,R,h)$ into the H₃-list.

Delegation Query:

$A_{\text{I}}$ can query the proxy delegation certificate $\sigma_{0}$ of a chosen warrant message $w$ from $ID_{0}$, and C responds as follows.

• (1) If $(ID_{0} ,w)$ has been queried, C returns $\sigma_{0} = (R_{0} ,V_{0} )$ from the Del-list.

• (2) Otherwise, C searches the UK-list to get $(ID_{0} ,Q_{{ID_{0} }} ,t_{0} ,c_{0} )$.

If $c_{0} = 0$, C randomly chooses $r_{0} \in Z_{q}^{ * }$ and computes $R_{0} = r_{0} P$. Then, C searches the H₂-list to get $(w,R_{0} ,h_{0} ,d_{0} )$, computes $V_{0} = r_{0} h_{0} + t_{0} (aP)$, returns $\sigma_{0} = (R_{0} ,V_{0} )$ to $A_{\text{I}}$, and adds $(ID_{0} ,w,r_{0} ,R_{0} ,V_{0} )$ to the Del-list.

If $c_{i} = 1$, C outputs “failure” and terminates the simulation.

When there are no records of $ID_{i}$ or $(w,R_{0} )$ in the UK-list and the H₂-list, C will create the corresponding values according to the User-Key query and H₂ query.

Multi-Proxy-Sign Query:

$A_{\text{I}}$ can input a proxy signer’s identity $ID_{i}$$(i = 1,2, \cdots ,n)$, an original signer’s identity $ID_{0}$, a warrant message $w$ and a message m, and it then queries the multi-proxy signature. C responds as follows.

• (1) C searches the H₁-list to get $(ID_{i} ,Q_{{ID_{i} }} ,t_{i} ,c_{i} )$, where $i = 0,1,2, \cdots ,n$. If $c_{0} = 1$ or $c_{i} = 1$, C outputs “failure” and terminates the simulation.

• (2) Otherwise, for $1 \le i \le n$, C randomly chooses $r_{i} \in Z_{q}^{ * }$, and computes $R_{i} = r_{i} P$, $R = \sum\limits_{i = 1}^{n} {R_{i} }$.

C searches the UK-list to get $(ID_{i} ,S_{{ID_{i} }} )$$(i = 0,1,2, \cdots ,n)$, and then searches the Del-list, H₂-list and H₃-list to get the records $(ID_{0} ,w,r_{0} ,R_{0} ,V_{0} )$, $(w,R_{0} ,h_{0} ,d_{0} )$ and $(m,R_{0} ,R,h)$, respectively. If there are no corresponding records in the lists, C generates the corresponding values according to the above queries.

For $1 \le i \le n$, C computes $V_{i} = r_{i} h_{0} + hS_{{ID_{i} }} + V_{0} = r_{i} h_{0} + ht_{i} (aP) + r_{0} h_{0} + t_{0} (aP)$, $V = \sum\limits_{i = 1}^{n} {V_{i} }$, and then returns $\sigma = (w,R_{0} ,R,V)$ to $A_{\text{I}}$.

Finally, $A_{\text{I}}$ stops the simulation, and outputs a multi-proxy signature tuple $\left\{ {ID_{0} ,ID_{i} ,m,\sigma^{ * } = (w,R_{0} ,R,V)} \right\}$. C searches the H₁-list to get $(ID_{i} ,Q_{{ID_{i} }} ,t_{i} ,c_{i} )$$(0 \le i \le n)$. If $c_{0} = 0$ or $c_{i} = 1$ $(1 \le i \le n)$, C outputs “failure” and terminates the simulation. Otherwise, $c_{0} = 1$ and $c_{i} = 0$ $(1 \le i \le n)$, C gets $(w,R_{0} ,h_{0} ,d_{0} )$ and $(m,R_{0} ,R,h)$ in the H₂-list and H₃-list, respectively. The forged multi-proxy signature satisfies the following equation.

$$ \begin{aligned} e(P,V) = e(P_{pub} ,h\sum\limits_{i = 1}^{n} {Q_{{ID_{i} }} } + nQ_{{ID_{0} }} )e(R + nR_{0} ,h_{0} ) \hfill \\ \text{ } = e(aP,h\sum\limits_{i = 1}^{n} {t_{i} } P + nt_{0} bP)e(R + nR_{0} ,d_{0} P) \hfill \\ \text{ } = e(P,h\sum\limits_{i = 1}^{n} {t_{i} } aP + nt_{0} abP + d_{0} (R + nR_{0} )) \hfill \\ \end{aligned} $$

Then, C computes $abP = (nt_{0} )^{ - 1} (V - h\sum\limits_{i = 1}^{n} {t_{i} } P_{Pub} - d_{0} (R + nR_{0} ))$. Therefore, C can solve the CDH problem.

To analyze the probability of C succeeding in the above game, we define the following five events, which are needed for C to succeed.

$E_{1}$: C does not abort in the User-Key query.

$E_{2}$: C does not abort in the Delegation-Gen query.

$E_{3}$: C does not abort in the Multi-Proxy-Sign query.

$E_{4}$: $A_{\text{I}}$ succeeds to forge a valid multi-proxy signature.

$E_{5}$: Event $E_{4}$ occurs, $c_{0} = 1$, and $c_{i} = 0$$(1 \le i \le n)$. Here, $c_{0}$ and $c_{i}$ are the c-components of the tuple on the H₁-list.

Therefore, the probability that C can solve the instance of CDH problem is

$$ \begin{aligned} & \Pr [E_{1} \wedge E_{2} \wedge E_{3} \wedge E_{4} \wedge E_{5} ] \\ & = \Pr [E_{1} ]\Pr [\left. {E_{2} } \right|E_{1} ]\Pr [\left. {E_{3} } \right|E_{1} \wedge E_{2} ]\Pr [\left. {E_{4} } \right|E_{1} \wedge E_{2} \wedge E_{3} ]\text{ }\Pr [\left. {E_{5} } \right|E_{1} \wedge E_{2} \wedge E_{3} \wedge E_{4} ]\text{ }\text{.} \\ \end{aligned} $$

From the simulation, we have the following results.

$\Pr [E_{1} ] \ge \delta^{{q_{K} }}$,

$\Pr [\left. {E_{2} } \right|E_{1} ] \ge \delta^{{q_{D} }}$,

$\Pr [\left. {E_{3} } \right|E_{1} \wedge E_{2} ] = 1$,

$\Pr [\left. {E_{4} } \right|E_{1} \wedge E_{2} \wedge E_{3} ] \ge \varepsilon$, and

$\Pr [\left. {E_{5} } \right|E_{1} \wedge E_{2} \wedge E_{3} \wedge E_{4} ] \ge (1 - \delta )\delta^{n}$.

Thus, we have $\Pr [E_{1} \wedge E_{2} \wedge E_{3} \wedge E_{4} \wedge E_{5} ] \ge \varepsilon \left( {1 - \delta } \right)\delta^{{q_{K} + q_{D} + n}}$.

When $\delta = \frac{{q_{K} + q_{D} + n}}{{q_{K} + q_{D} + n + 1}}$, $\left( {1 - \delta } \right)\delta^{{q_{K} + q_{D} + n}}$ obtains the minimum value $\frac{1}{{(q_{K} + q_{D} + n + 1)e}}$. Then, the probability that C succeeds is $\varepsilon^{\prime} \ge \varepsilon \frac{1}{{(q_{K} + q_{D} + n + 1)e}}$.

The total running time of C is $t^{\prime} < t + (q_{{H_{1} }} + q_{K} + q_{{H_{2} }} + 3q_{D} + 3nq_{P} + n + 4)t_{s} + t_{i}$.

Theorem 2.

In the random oracle model, let $A_{\text{II}}$ be a PPT adversary with a non-negligible probability $\varepsilon$ to win $Game\,2$ in time t. Assume that $A_{\text{II}}$ makes at most $q_{{H_{i} }}$ queries to hash functions $H_{i}$$(i = 1,2,3)$, at most $q_{K}$ queries to the User-Key-Gen oracle, at most $q_{D}$ queries to the Delegation-Gen oracle, and at most $q_{P}$ queries to the Multi-Proxy-Sign oracle. Then, there exists an algorithm C with the probability $\varepsilon^{\prime} \ge \varepsilon \frac{n}{{(q_{K} + q_{D} + n + 1)e}}$ to solve the CDH problem in time $t^{\prime} < t + (q_{{H_{1} }} + q_{K} + q_{{H_{2} }} + 3q_{D} + 3nq_{P} + n + 4)t_{s} + t_{i}$, where $t_{i}$ is the time of an inversion computation in $Z_{q}^{ * }$, and $t_{s}$ is the time of a scalar multiplication in $G_{1}$.

Proof:

Let $(P,aP,bP)$ be a random instance of the CDH problem in $G_{1}$. C could conduct the same computation as in Theorem 1, and $A_{\text{II}}$ could also conduct the same queries as in Theorem 1.

Finally, $A_{\text{II}}$ stops the simulation, and outputs a multi-proxy signature tuple $\left\{ {ID_{0} ,ID_{i} ,m,\sigma^{ * } = (w,R_{0} ,R,V)} \right\}$. C searches the H₁-list to get $(ID_{i} ,Q_{{ID_{i} }} ,t_{i} ,c_{i} )$$(0 \le i \le n)$. If $c_{0} = 1$ or $c_{i} = 0$$(1 \le i \le n)$, C outputs “failure” and terminates the simulation. Otherwise, $c_{0} = 0$ and at least one $c_{i} = 1$. Without the loss of generality, we assume that $c_{1} = 1$, and C gets $(w,R_{0} ,h_{0} ,d_{0} )$ and $(m,R_{0} ,R,h)$ in the H₂-list and H₃-list, respectively. The forged multi-proxy signature satisfies the following equation.

$$ \begin{aligned} e(P,V) & = e(P_{pub} ,h\sum\limits_{i = 1}^{n} {Q_{{ID_{i} }} } + nQ_{{ID_{0} }} )e(R + nR_{0} ,h_{0} ) \\ & = e(aP,h\sum\limits_{i = 2}^{n} {t_{i} } P + ht_{1} bP + nt_{0} P)e(R + nR_{0} ,d_{0} P) \\ & = e(P,h\sum\limits_{i = 2}^{n} {t_{i} } aP + ht_{1} abP + nt_{0} aP + d_{0} (R + nR_{0} )). \\ \end{aligned} $$

Then, C computes $abP = (ht_{1} )^{ - 1} (V - h\sum\limits_{i = 2}^{n} {t_{i} } P_{Pub} - nt_{0} P_{Pub} - d_{0} (R + nR_{0} ))$. Therefore, C can solve the CDH problem. As with the proof in Theorem 1, the probability that C succeeds in the game is $\varepsilon^{\prime} \ge \varepsilon \frac{n}{{(q_{K} + q_{D} + n + 1)e}}$.

The total running time of C is $t^{\prime} < t + (q_{{H_{1} }} + q_{K} + q_{{H_{2} }} + 3q_{D} + 3nq_{P} + n + 4)t_{s} + t_{i}$.

5.3 Efficiency Comparison

We compare the efficiency of our scheme with some ID-based multi-proxy signature schemes based on bilinear pairings in Table 1. We only consider the computational costs for a single user and compare the algorithmic efficiency of delegation-gen, multi-proxy-sign and multi-proxy-verify, respectively. In Table 1, M denotes the point scalar multiplication operation in G₁, E denotes the exponentiation operation in G₂, and P denotes the pairing operation. We ignore other operations, such as hashing, in all the schemes.

Table 1. Comparison of efficiency for similar schemes

As shown in Table 1, we can see that our scheme is more efficient than the scheme in [4] which is provable secure. Moreover, we proved that our scheme was secure under the computational Diffie-Hellman problem. Although the scheme in [16] is more efficient than ours, there was no formal security proof in the scheme, and the schemes in [11, 17, 22] lacked provable security, as well. Meanwhile, it was proved that scheme [4] was not secure in [22]. Therefore, to the best of our knowledge, our scheme is the only ID-based multi-proxy signature scheme using bilinear pairings that is proved to be secure in the random oracle model.

6 Conclusion

In this paper, we describe the definition and security model of an identity-based multi-proxy signature scheme and propose a new identity-based multi-proxy signature scheme. Based on the hardness of the computational Diffie-Hellman problem, our scheme was proven to be secure in the random oracle model. Moreover, compared with previous ID-based multi-proxy signature schemes based on bilinear pairings, our scheme is provably secure and more efficient.