# Strong Identity-Based Proxy Signature Schemes, Revisited

Authors: Weiwei Liu; Yi Mu; Guomin Yang; Yangguang Tian
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Proxy signature is a useful cryptographic primitive that has been widely used in many applications. It has attracted a lot of attention since it was introduced. There have been lots of works in constructing efficient and secure proxy signature schemes. In this paper, we identify a new attack that has been neglected by many existing proven secure proxy signature schemes. We demonstrate this attack by launching it against an identity-based proxy signature scheme which is proven secure. We then propose one method that can effectively prevent this attack. The weakness in some other proxy signature schemes can also be fixed by applying the same method.


---

## Body

## 1. Introduction

Proxy signature is a special type of digital signature which allows one user (original signer) to delegate his/her signing right to another signer (proxy signer). The latter can then issue signatures on behalf of the former. The corresponding proxy signature can be verified by the public that it is indeed generated by the proxy signer with proper delegation from the original signer [1, 2]. Proxy signature has been found useful in many applications, such as distributed computing [3], electronic commerce [4], mobile agents [5], and grid computing [6]. It is worth noticing that proxy signature can also serve as a useful tool in Internet of things (IoT), since most of the RFID tags in IoT only have limited storage and computing ability. For those operations involving a large amount of computation, those tags can authorize the tag readers with strong computing ability to perform those operations with the help of a proxy signature scheme [7, 8].The concept of proxy signature was introduced by Mambo, Usuda, and Okamoto in 1996 [9]. They presented three different types of proxy signature, namely, full delegation, partial delegation, and delegation by warrant in their seminal work. Shortly after Mambo et al.’s work, Kim et al. [10] proposed a new type of proxy signature combing partial delegation and warrant. They demonstrated that schemes combining partial delegation and warrant can provide a higher level of security than schemes based on partial delegation or warrant separately. Since then, proxy signature has been extensively researched in different settings, such as blind proxy signature [11], anonymous proxy signature [12], and identity-based proxy signature [13].These delegation-by-warrant proxy signature schemes can be further classified into two categories according to whether the proxy signature is generated by the proxy signer using his own private key or not. In the first type, the proxy signer generates a new proxy signing key using the delegation information and his own private key. The proxy signatures are generated under the new proxy signing key. The proxy signature schemes in [5, 14–17] fall into the first type. In the second type, the proxy signer issues a proxy signature using his own private key. The proxy signatures are essentially combinations of the original signer’s signature on the warrant and the proxy signer’s signature on the message. Such proxy signature schemes could be found in [13, 18–21].On the security modelling of proxy signature, Boldyreva et al. [22] proposed a comprehensive security model for the delegation-by-warrant proxy signature, where an original signer can also perform self-delegation. Malkin et al. [23] extended the security model to allow fully hierarchical proxy signatures. They also proved that proxy signatures are essentially equivalent to key-insulated signatures. The security model proposed in [22, 23] is in the registered key model, which means the adversary has to submit every public and private key pair in the security game except the challenge one. Later, Schuldt et al. [24] proposed an enhanced security model for proxy signature by allowing the adversary to query arbitrary proxy signing keys. Roughly speaking, a secure proxy signature scheme should satisfy the following requirements.(i)
Verifiability: given a proxy signature, a verifier can be convinced that the proxy signature is indeed a valid signature generated by the proxy signer with proper delegation from an original signer on the signed message.(ii)
Identifiability: given a proxy signature, a verifier is able to determine the identities of the corresponding original signer and proxy signer.(iii)
Unforgeability: no one, except the designated proxy signer, can create a valid proxy signature.(iv)
Untenability: a proxy signer cannot deny at a later time on a proxy signature that he has created before.(v)
Prevention of misuse: it is required in the first type of proxy signature schemes that the proxy signing key cannot be used for purposes other than creating proxy signatures. Once misused, the identity of the misbehaving proxy signer can be determined explicitly.


### 1.1. Our Contribution

We revisit proxy signature and show an attack that has been neglected by the second type of proxy signature schemes [13, 18–21] that have been proven secure. In these schemes, a proxy signature is essentially the combination of the original signer’s standard signature on a warrant and the proxy signer’s standard signature on a message. In the security analysis, it is assumed that an adversary has access to the original signer and proxy signer’s standard signature oracles. We show that, under such a circumstance, some proxy signature schemes [13, 18–21] that have been previously proved secure are in fact not secure.We demonstrate a new attack by launching it against an identity-based proxy signature scheme [13] that has been proven secure. We show that a malicious adversary can create a proxy signature on a message, if he has access to the standard signature of the original signer and proxy signer, which is as defined in the security models in [13, 18]. Thus, these proxy signature schemes [13, 18–21], which we believe is not a complete list, are in fact not secure. We propose an efficient solution by revising the identity-based proxy signature scheme [13] to thwart this attack. It is worth noticing that the same method can also be applied to [18–21] to resist this attack.We have noticed there have been several works [5, 22] aiming to transform normal proxy signature schemes into strong ones. The authors in [22] suggested to add two different prepositive tags “00” and “11” to distinguish the signatures generated by the original signer and proxy signer. However, this simple solution cannot prevent the attack proposed in this paper according to the original security model in [13]. The adversaries are able to query any message of their choices. To stop the proxy signer from misusing the proxy signing key, the authors in [5] classified existing proxy signature schemes into strong and weak ones and proposed one method to transform weak proxy signature schemes into strong ones. However, as have been mentioned above, their method is only applicable when a proxy signature is generated from a proxy signing key which is created by the proxy signer using the delegation information and his own private key. Therefore, the method proposed in [5] is not suitable for the scenarios discussed in this paper.Paper Organization. The rest of the paper is organized as follows. We introduce some preliminaries in Section 2. Then we present a new attack in some proxy signature schemes in Section 3 by attacking an identity-based proxy signature scheme. The security model for proxy signature that captures the attack is presented in Section 4. We then revise the identity-based proxy signature scheme in Section 5. The security proof and efficiency analysis are presented in Section 6 and the paper is concluded in Section 7.


## 1.1. Our Contribution

We revisit proxy signature and show an attack that has been neglected by the second type of proxy signature schemes [13, 18–21] that have been proven secure. In these schemes, a proxy signature is essentially the combination of the original signer’s standard signature on a warrant and the proxy signer’s standard signature on a message. In the security analysis, it is assumed that an adversary has access to the original signer and proxy signer’s standard signature oracles. We show that, under such a circumstance, some proxy signature schemes [13, 18–21] that have been previously proved secure are in fact not secure.We demonstrate a new attack by launching it against an identity-based proxy signature scheme [13] that has been proven secure. We show that a malicious adversary can create a proxy signature on a message, if he has access to the standard signature of the original signer and proxy signer, which is as defined in the security models in [13, 18]. Thus, these proxy signature schemes [13, 18–21], which we believe is not a complete list, are in fact not secure. We propose an efficient solution by revising the identity-based proxy signature scheme [13] to thwart this attack. It is worth noticing that the same method can also be applied to [18–21] to resist this attack.We have noticed there have been several works [5, 22] aiming to transform normal proxy signature schemes into strong ones. The authors in [22] suggested to add two different prepositive tags “00” and “11” to distinguish the signatures generated by the original signer and proxy signer. However, this simple solution cannot prevent the attack proposed in this paper according to the original security model in [13]. The adversaries are able to query any message of their choices. To stop the proxy signer from misusing the proxy signing key, the authors in [5] classified existing proxy signature schemes into strong and weak ones and proposed one method to transform weak proxy signature schemes into strong ones. However, as have been mentioned above, their method is only applicable when a proxy signature is generated from a proxy signing key which is created by the proxy signer using the delegation information and his own private key. Therefore, the method proposed in [5] is not suitable for the scenarios discussed in this paper.Paper Organization. The rest of the paper is organized as follows. We introduce some preliminaries in Section 2. Then we present a new attack in some proxy signature schemes in Section 3 by attacking an identity-based proxy signature scheme. The security model for proxy signature that captures the attack is presented in Section 4. We then revise the identity-based proxy signature scheme in Section 5. The security proof and efficiency analysis are presented in Section 6 and the paper is concluded in Section 7.


## 2. Preliminaries

In this section, we introduce some preliminaries used throughout this paper.


### 2.1. Bilinear Map

LetG1, G2 be two cyclic groups of prime order q and P a generator of G1. The e:G1×G1→G2 is said to be an admissible bilinear map if the following conditions hold:(i)
Bilinearity:e(aP1,bP2)=e(abP1,P2)=e(P1,abP2) for all P1,P2∈G1 and a,b∈RZq.(ii)
Nondegeneracy: there existsP1,P2∈G1 such that e(P1,P2)≠1G2.(iii)
Computability: there is an efficient algorithm to computee(P1,P2) for all P1,P2∈G1.


### 2.2. Complexity Assumption

Definition 1 (computational Diffie-Hellman (CDH) problem).
GivenP,aP,bP∈G1 for some random a,b∈Zq, compute abP∈G1. Define the success probability of a polynomial algorithm A in solving the CDH problem as (1)SuccA,G1CDHκ=PrAP,aP,bP=abP:a,b∈RZqwhere κ=log⁡(q) is the security parameter. The CDH assumption states that, for any polynomial algorithm adversary A, SuccA,G1CDH(κ) is negligible in κ.


## 2.1. Bilinear Map

LetG1, G2 be two cyclic groups of prime order q and P a generator of G1. The e:G1×G1→G2 is said to be an admissible bilinear map if the following conditions hold:(i)
Bilinearity:e(aP1,bP2)=e(abP1,P2)=e(P1,abP2) for all P1,P2∈G1 and a,b∈RZq.(ii)
Nondegeneracy: there existsP1,P2∈G1 such that e(P1,P2)≠1G2.(iii)
Computability: there is an efficient algorithm to computee(P1,P2) for all P1,P2∈G1.


## 2.2. Complexity Assumption

Definition 1 (computational Diffie-Hellman (CDH) problem).
GivenP,aP,bP∈G1 for some random a,b∈Zq, compute abP∈G1. Define the success probability of a polynomial algorithm A in solving the CDH problem as (1)SuccA,G1CDHκ=PrAP,aP,bP=abP:a,b∈RZqwhere κ=log⁡(q) is the security parameter. The CDH assumption states that, for any polynomial algorithm adversary A, SuccA,G1CDH(κ) is negligible in κ.


## 3. A New Attack in Some Proxy Signature Schemes

In this section, we present an attack that has been neglected by many existing proxy signature schemes [13, 18–21]. To better explain how an attacker works, we demonstrate this attack via a concrete example. Before we start to introduce the attack, we first review an identity-based proxy signature scheme proposed in [13].


### 3.1. An Identity-Based Proxy Signature Scheme

(1)
Setup: let e:G1×G1→G2 be a bilinear pairing map, where G1 and G2 are of prime order q. Let P be a generator of G1. Choose a random number s∈Zq∗ and set Ppub=sP. Select three collision-resistant hash functions H0,H1,H2 such that H0,H1,H2:{0,1}∗→G1. The system parameters params={e,G1,G2,q,Ppub,H0,H1,H2}, the master secret key Msk=s. (2)
KeyExtract: on input a user’s identity ID, output the secret key for this identity skID=sH0(ID). (3)
StandardSign: on input a message m, the standard signature on m under identity ID is σ=(σ1,σ2) such that σ1=skID+rH1(M) and σ2=rP, where r∈Zq. (4)
StandardVer: on input a standard signature σ=(σ1,σ2) of message m under identity ID, output “1” if e(σ1,P)=e(H0(ID),Ppub)e(H1(m),σ2); otherwise, output “0”. (5)
DelegationGen: let w be a warrant that includes the delegation information such as the identities of the original signer and the designated proxy signer, the delegation period, the types of messages that a proxy signer can sign, and so on. Then the original signer with identity IDA generates the delegation information σw=(σW1,σW2) such that σW1=skIDA+rAH1(mw) and σW2=rAP, where rA∈Zq. The original signer sends the delegation signing key σw to the proxy signer. (6)
ProSign: upon receiving the delegation information σw=(σW1,σW2) and w from the original signer, the proxy signer with identity IDB generates a proxy signature σ=(σM1,σM2,σM3) on a message m such that σM1=σW1+skIDB+rBH2(m), σM2=σW2, σM3=rBP. (7)
ProVer: on input the identities IDA,IDB of the original signer and proxy signer, a warrant w∈{0,1}∗ and a message m∈{0,1}∗ and the proxy signature σ=(σM1,σM2,σM3), output “1” if (2)eσM1,P=eH0IDA,PpubeH1w,σM2eH0IDB,PpubeH2m,σM3. Otherwise, output “0”.


### 3.2. An Attack against the ID-Based Proxy Signature Scheme

Wu et al.’s identity-based proxy signature scheme [13] is proven secure. However, we show below that if the original signer and proxy signer also use their private keys to generate standard signatures, which is just as defined in their security models, then their scheme could be broken by a malicious outsider attacker. Assume the identities of the original signer and proxy signer are IDA,IDB, respectively, in the security model in [13], three types of adversaries are defined, namely,(i)
AI, which is an outsider adversary that has knowledge of IDA,IDB,(ii)
AII, which is a malicious proxy signer that has knowledge of IDA,IDB,skIDB,(iii)
AIII, which is a malicious original signer that has knowledge of IDA,skIDA,IDB.The original signer and proxy signer could use the same key pairs to generate normal signatures using the standard signature scheme introduced in [13]. Suppose AI aims to generate a proxy signature σ=(σM1,σM2,σM3) on a message m with a warrant w; it is worth noticing that AI might obtain such a genius warrant w when verifying a valid proxy signature. Then AI acts as follows:(i)
AI requires a standard signature (σA1,σA2) on warrant w of the original signer with identity IDA, where w is a warrant containing the delegation information. The original signer chooses a random rA∈Zq and generates the standard signature (σA1,σA2) such that σA1=skIDA+rAH1(w) and σA2=rAP.(ii)
Upon receiving the standard signature(σA1,σA2) on w from the original signer. AI aborts if e(σA1,P)≠e(H0(IDA),Ppub)e(H1(w),σA2).(iii)
AI requires a standard signature (σB1,σB2) on message w∥m of the proxy signer with identity IDB, where m is a message. The proxy signer chooses a random rB∈Zq and generates the standard signature (σB1,σB2) such that σB1=skIDB+rBH2(w,m) and σB2=rBP.(iv)
Upon receiving the standard signature(σB1,σB2) on m from the proxy signer. AI aborts if e(σB1,P)≠e(H0(IDB),Ppub)e(H2(w,m),σB2).(v)
If both(σA1,σA2) and (σB1,σB2) are valid. AI outputs a proxy signature σ=(σM1,σM2,σM3) on message m with warrant w such that σM1=σA1+σB1=skIDA+rAH1(w)+skIDB+rBH2(w,m), σM2=σA2=rAP and σM3=σB2=rBP.It can be verified thatσ=(σM1,σM2,σM3) is a valid proxy signature. Thus, the proposed identity-based proxy signature is insecure, since given a proxy signature σ=(σM1,σM2,σM3), it might come from a malicious adversary. The proposed attack is a practical attack since a malicious adversary could launch such an attack without notice of both the original signer and the proxy signer. Besides the scheme mentioned in this paper, we have found that the proxy signature schemes in [18–21] are also subjected to this attack.


## 3.1. An Identity-Based Proxy Signature Scheme

(1)
Setup: let e:G1×G1→G2 be a bilinear pairing map, where G1 and G2 are of prime order q. Let P be a generator of G1. Choose a random number s∈Zq∗ and set Ppub=sP. Select three collision-resistant hash functions H0,H1,H2 such that H0,H1,H2:{0,1}∗→G1. The system parameters params={e,G1,G2,q,Ppub,H0,H1,H2}, the master secret key Msk=s. (2)
KeyExtract: on input a user’s identity ID, output the secret key for this identity skID=sH0(ID). (3)
StandardSign: on input a message m, the standard signature on m under identity ID is σ=(σ1,σ2) such that σ1=skID+rH1(M) and σ2=rP, where r∈Zq. (4)
StandardVer: on input a standard signature σ=(σ1,σ2) of message m under identity ID, output “1” if e(σ1,P)=e(H0(ID),Ppub)e(H1(m),σ2); otherwise, output “0”. (5)
DelegationGen: let w be a warrant that includes the delegation information such as the identities of the original signer and the designated proxy signer, the delegation period, the types of messages that a proxy signer can sign, and so on. Then the original signer with identity IDA generates the delegation information σw=(σW1,σW2) such that σW1=skIDA+rAH1(mw) and σW2=rAP, where rA∈Zq. The original signer sends the delegation signing key σw to the proxy signer. (6)
ProSign: upon receiving the delegation information σw=(σW1,σW2) and w from the original signer, the proxy signer with identity IDB generates a proxy signature σ=(σM1,σM2,σM3) on a message m such that σM1=σW1+skIDB+rBH2(m), σM2=σW2, σM3=rBP. (7)
ProVer: on input the identities IDA,IDB of the original signer and proxy signer, a warrant w∈{0,1}∗ and a message m∈{0,1}∗ and the proxy signature σ=(σM1,σM2,σM3), output “1” if (2)eσM1,P=eH0IDA,PpubeH1w,σM2eH0IDB,PpubeH2m,σM3. Otherwise, output “0”.


## 3.2. An Attack against the ID-Based Proxy Signature Scheme

Wu et al.’s identity-based proxy signature scheme [13] is proven secure. However, we show below that if the original signer and proxy signer also use their private keys to generate standard signatures, which is just as defined in their security models, then their scheme could be broken by a malicious outsider attacker. Assume the identities of the original signer and proxy signer are IDA,IDB, respectively, in the security model in [13], three types of adversaries are defined, namely,(i)
AI, which is an outsider adversary that has knowledge of IDA,IDB,(ii)
AII, which is a malicious proxy signer that has knowledge of IDA,IDB,skIDB,(iii)
AIII, which is a malicious original signer that has knowledge of IDA,skIDA,IDB.The original signer and proxy signer could use the same key pairs to generate normal signatures using the standard signature scheme introduced in [13]. Suppose AI aims to generate a proxy signature σ=(σM1,σM2,σM3) on a message m with a warrant w; it is worth noticing that AI might obtain such a genius warrant w when verifying a valid proxy signature. Then AI acts as follows:(i)
AI requires a standard signature (σA1,σA2) on warrant w of the original signer with identity IDA, where w is a warrant containing the delegation information. The original signer chooses a random rA∈Zq and generates the standard signature (σA1,σA2) such that σA1=skIDA+rAH1(w) and σA2=rAP.(ii)
Upon receiving the standard signature(σA1,σA2) on w from the original signer. AI aborts if e(σA1,P)≠e(H0(IDA),Ppub)e(H1(w),σA2).(iii)
AI requires a standard signature (σB1,σB2) on message w∥m of the proxy signer with identity IDB, where m is a message. The proxy signer chooses a random rB∈Zq and generates the standard signature (σB1,σB2) such that σB1=skIDB+rBH2(w,m) and σB2=rBP.(iv)
Upon receiving the standard signature(σB1,σB2) on m from the proxy signer. AI aborts if e(σB1,P)≠e(H0(IDB),Ppub)e(H2(w,m),σB2).(v)
If both(σA1,σA2) and (σB1,σB2) are valid. AI outputs a proxy signature σ=(σM1,σM2,σM3) on message m with warrant w such that σM1=σA1+σB1=skIDA+rAH1(w)+skIDB+rBH2(w,m), σM2=σA2=rAP and σM3=σB2=rBP.It can be verified thatσ=(σM1,σM2,σM3) is a valid proxy signature. Thus, the proposed identity-based proxy signature is insecure, since given a proxy signature σ=(σM1,σM2,σM3), it might come from a malicious adversary. The proposed attack is a practical attack since a malicious adversary could launch such an attack without notice of both the original signer and the proxy signer. Besides the scheme mentioned in this paper, we have found that the proxy signature schemes in [18–21] are also subjected to this attack.


## 4. Security Model for Proxy Signature

### 4.1. Malicious Attackers

We revise the security model for identity-based proxy signature defined in [13] to capture the new attack in this section. In the security model for proxy signature, the capability of an adversary is modelled by its ability to query different oracles. Before we formally define each adversarial game, we first introduce four types of oracle queries that will appear in the models:(i)
Key extract query: A can query an identity ID∈ID, where ID represents the identity space, to the key extract oracle OKE(·). The corresponding key skID is then generated and returned to A.(ii)
Original signer’s standard signing query: A can query the original signer’s signing oracle OOS′S(·) with any warrant w∈W under the original signer’s identity ID∈ID, where W represents the warrant space. The private key skID on identity ID is generated using the key extraction algorithm. The corresponding original signer’s signature σo on warrant w is generated and returned to A.(iii)
Proxy signing query: A can query the proxy signing oracle OPS(·) with any message m∈M with warrant w∈W of his choice under the original signer’s identity IDA and the proxy signer’s identity IDB such that IDA,IDB∈ID, where M represents the message space. The private keys skIDA and skIDB on identities IDA, IDB are generated using the key extraction algorithm. A valid proxy signature on m is then generated and returned to A.(iv)
Proxy signer’s signing query: A can query the standard signature with any message m∈M of his choice to the proxy signer’s standard signing oracle OPS′S(·). A valid standard signature of the proxy signer σp on m under the proxy signer’s identity is then generated and returned to A.According to the information held by an attacker, three different types of adversaries are defined:(1)
AI: an outsider attacker who only has the identities of the original signer and the proxy signer that aims to forge a valid proxy signature.(2)
AII: a malicious proxy signer who possesses the private key skIDB of the proxy signer and the identity of the original signer, and tries to forge a valid proxy signature σ without knowledge of the private key skIDA of the original signer.(3)
AIII: a malicious original signer that possesses the private key skIDA of the original signer and the identity IDB of the proxy signer, and tries to forge a valid proxy signature σ without knowing the private key skIDB of the proxy signer.


### 4.2. Adversarial Game with a Malicious Outsider AdversaryAI

We first define the adversarial game between a malicious outsider adversaryAI and a simulator S as follows:(i)
Setup: the simulator S runs Setup algorithm to generate the params and MSK and sends params to AI as well as keeping MSK secret.(ii)
Original signer’s standard signing queries: AI can choose any warrant w∈W with the original signer’s identity IDA and queries the original signer’s standard signing oracle OOS′S. S generates the private key skIDA using the key extract algorithm skIDA←KeyExtract(MSK,IDA,params); then S generates the delegation information σo←StandardSign(skIDA,w,params) and sends σo to AI.(iii)
Proxy Signer’s Standard Signature Queries: AI queries the proxy signer’s standard signing oracle OPS′S with a message m∈M of his choice under the proxy signer’s identity IDB∈ID. S generates the private key skIDB using the key extract algorithm skIDB←KeyExtract(MSK,IDB,params); then S generates the standard signature sσ←StandardSign(skIDB,m,params) and sends sσ to AI.(iv)
Forgery Phase: finally, AI outputs a proxy signature σ∗ on message M∗ for a warrant W∗ with the original signer’s identity IDA and the proxy signer’s identity IDB.We sayAII wins the game if(i)
ProVer(σ∗,IDA,IDB,W∗,M∗)=1;(ii)
(W∗,IDA) has been queried to the original signer’s standard signing oracle OOS′S;(iii)
(W∗,M∗,IDB) has been queried to the proxy signer’s standard signing oracle OPS′S.Define the advantage of a malicious adversaryAI in winning the game as (3)AdvAIκ=Pr⁡AIWins  the  game.Definition 2.
We say an identity-based proxy signature scheme is secure against an outsider adversaryAI if for any probabilistic polynomial time AI, AdvAI(κ) is negligible in κ.


### 4.3. Adversarial Game with a Malicious Proxy SignerAII

We first define the adversarial game between a malicious proxy signerAII and a simulator S as follows:(i)
Setup: the simulator S runs Setup algorithm to generate the params and MSK and sends params to AII as well as keeping MSK secret.(ii)
Key extract queries: AII selects an identity ID such that ID∈ID, the simulator S runs skID←KeyExtract(MSK,ID,params) and returns skID to AII.(iii)
Original signer’s standard signing queries: AII can choose any warrant w∈W with an identity ID∈ID and queries original signer’s standard signing oracle OOS′S. S generates the private key skID using the key extract algorithm skID←KeyExtract(MSK,ID,params); then S generates the original signer’s standard signature σo←StandardSign(skID,w,params) and sends σo to AII.(iv)
Proxy signing queries: AII chooses a warrant w∈W and a message m∈M and queries the proxy signing oracle OPS with the original signer’s identity ID1 and the proxy signer’s identity ID2. S generates(4)skID1,skID2←KeyExtractMSK,ID1,ID2,paramsσw←DelegationGenskID1,w,params,σ←ProSignσw,skID2,m,paramsand returnsσ to AII.(v)
Forgery Phase: finally, A outputs a proxy signature σ∗ on message M∗ for a warrant W∗ with the original signer’s identity IDA and the proxy signer’s identity IDB.We sayAII wins the game if(i)
ProVer(σ∗,IDA,IDB,W∗,M∗)=1;(ii)
IDA has not been queried to the key extraction oracle OKE(·);(iii)
(W∗,IDA) has not been queried to the delegation oracle ODG;(iv)
(W∗,M∗,IDA,IDB) has not been queried to the proxy signing oracle OPS.Define the advantage of a malicious adversaryAII in winning the game as (5)AdvAIIκ=Pr⁡AIIWins  the  game.Definition 3.
We say an identity-based proxy signature scheme is secure against theAII under chosen identity and warrant attacks if for any probabilistic polynomial time AII, AdvAII(κ) is negligible in κ.


### 4.4. Adversarial Game with Malicious Original Signer

The adversarial game between a malicious original signerAIII and a simulator S is defined as follows:(i)
Setup,Key Extract Queries andProxy Signing Queries are the same as those in the adversarial game against a malicious proxy signer.(ii)
Proxy Signer’s Standard Signature Queries: AIII queries the proxy signer’s standard signing oracle Ops′s with a message m∈M of his choice under an identity ID∈ID. S generates the private key skID using the key extract algorithm skID←KeyExtract(MSK,ID,params); then S generates the standard signature σp←StandardSign(skID,m,params) and sends σp to AIII.(iii)
Forgery Phase: finally, AIII outputs a proxy signature σ∗ on message M∗ for a warrant W∗ with the original signer’s identity IDA and the proxy signer’s identity IDB.We sayAIII wins the game if(i)
ProVer(σ∗,IDA,IDB,W∗,M∗)=1;(ii)
IDB has not been queried to the key extraction oracle OKE;(iii)
(W∗,M∗,IDB) has not been queried to the proxy signer’s standard signing oracle OPS′S;(iv)
(W∗,M∗,IDA,IDB) has not been queried to the proxy signing oracle OPS.Define the advantage of a malicious adversaryAIII in winning the game as (6)AdvAIIIκ=PrAIIIWins  the  game.Definition 4.
We say an identity-based proxy signature scheme is secure against theAIII under chosen identity and message attacks if for any probabilistic polynomial time AIII, AdvAIII(κ) is negligible in κ.


## 4.1. Malicious Attackers

We revise the security model for identity-based proxy signature defined in [13] to capture the new attack in this section. In the security model for proxy signature, the capability of an adversary is modelled by its ability to query different oracles. Before we formally define each adversarial game, we first introduce four types of oracle queries that will appear in the models:(i)
Key extract query: A can query an identity ID∈ID, where ID represents the identity space, to the key extract oracle OKE(·). The corresponding key skID is then generated and returned to A.(ii)
Original signer’s standard signing query: A can query the original signer’s signing oracle OOS′S(·) with any warrant w∈W under the original signer’s identity ID∈ID, where W represents the warrant space. The private key skID on identity ID is generated using the key extraction algorithm. The corresponding original signer’s signature σo on warrant w is generated and returned to A.(iii)
Proxy signing query: A can query the proxy signing oracle OPS(·) with any message m∈M with warrant w∈W of his choice under the original signer’s identity IDA and the proxy signer’s identity IDB such that IDA,IDB∈ID, where M represents the message space. The private keys skIDA and skIDB on identities IDA, IDB are generated using the key extraction algorithm. A valid proxy signature on m is then generated and returned to A.(iv)
Proxy signer’s signing query: A can query the standard signature with any message m∈M of his choice to the proxy signer’s standard signing oracle OPS′S(·). A valid standard signature of the proxy signer σp on m under the proxy signer’s identity is then generated and returned to A.According to the information held by an attacker, three different types of adversaries are defined:(1)
AI: an outsider attacker who only has the identities of the original signer and the proxy signer that aims to forge a valid proxy signature.(2)
AII: a malicious proxy signer who possesses the private key skIDB of the proxy signer and the identity of the original signer, and tries to forge a valid proxy signature σ without knowledge of the private key skIDA of the original signer.(3)
AIII: a malicious original signer that possesses the private key skIDA of the original signer and the identity IDB of the proxy signer, and tries to forge a valid proxy signature σ without knowing the private key skIDB of the proxy signer.


## 4.2. Adversarial Game with a Malicious Outsider AdversaryAI

We first define the adversarial game between a malicious outsider adversaryAI and a simulator S as follows:(i)
Setup: the simulator S runs Setup algorithm to generate the params and MSK and sends params to AI as well as keeping MSK secret.(ii)
Original signer’s standard signing queries: AI can choose any warrant w∈W with the original signer’s identity IDA and queries the original signer’s standard signing oracle OOS′S. S generates the private key skIDA using the key extract algorithm skIDA←KeyExtract(MSK,IDA,params); then S generates the delegation information σo←StandardSign(skIDA,w,params) and sends σo to AI.(iii)
Proxy Signer’s Standard Signature Queries: AI queries the proxy signer’s standard signing oracle OPS′S with a message m∈M of his choice under the proxy signer’s identity IDB∈ID. S generates the private key skIDB using the key extract algorithm skIDB←KeyExtract(MSK,IDB,params); then S generates the standard signature sσ←StandardSign(skIDB,m,params) and sends sσ to AI.(iv)
Forgery Phase: finally, AI outputs a proxy signature σ∗ on message M∗ for a warrant W∗ with the original signer’s identity IDA and the proxy signer’s identity IDB.We sayAII wins the game if(i)
ProVer(σ∗,IDA,IDB,W∗,M∗)=1;(ii)
(W∗,IDA) has been queried to the original signer’s standard signing oracle OOS′S;(iii)
(W∗,M∗,IDB) has been queried to the proxy signer’s standard signing oracle OPS′S.Define the advantage of a malicious adversaryAI in winning the game as (3)AdvAIκ=Pr⁡AIWins  the  game.Definition 2.
We say an identity-based proxy signature scheme is secure against an outsider adversaryAI if for any probabilistic polynomial time AI, AdvAI(κ) is negligible in κ.


## 4.3. Adversarial Game with a Malicious Proxy SignerAII

We first define the adversarial game between a malicious proxy signerAII and a simulator S as follows:(i)
Setup: the simulator S runs Setup algorithm to generate the params and MSK and sends params to AII as well as keeping MSK secret.(ii)
Key extract queries: AII selects an identity ID such that ID∈ID, the simulator S runs skID←KeyExtract(MSK,ID,params) and returns skID to AII.(iii)
Original signer’s standard signing queries: AII can choose any warrant w∈W with an identity ID∈ID and queries original signer’s standard signing oracle OOS′S. S generates the private key skID using the key extract algorithm skID←KeyExtract(MSK,ID,params); then S generates the original signer’s standard signature σo←StandardSign(skID,w,params) and sends σo to AII.(iv)
Proxy signing queries: AII chooses a warrant w∈W and a message m∈M and queries the proxy signing oracle OPS with the original signer’s identity ID1 and the proxy signer’s identity ID2. S generates(4)skID1,skID2←KeyExtractMSK,ID1,ID2,paramsσw←DelegationGenskID1,w,params,σ←ProSignσw,skID2,m,paramsand returnsσ to AII.(v)
Forgery Phase: finally, A outputs a proxy signature σ∗ on message M∗ for a warrant W∗ with the original signer’s identity IDA and the proxy signer’s identity IDB.We sayAII wins the game if(i)
ProVer(σ∗,IDA,IDB,W∗,M∗)=1;(ii)
IDA has not been queried to the key extraction oracle OKE(·);(iii)
(W∗,IDA) has not been queried to the delegation oracle ODG;(iv)
(W∗,M∗,IDA,IDB) has not been queried to the proxy signing oracle OPS.Define the advantage of a malicious adversaryAII in winning the game as (5)AdvAIIκ=Pr⁡AIIWins  the  game.Definition 3.
We say an identity-based proxy signature scheme is secure against theAII under chosen identity and warrant attacks if for any probabilistic polynomial time AII, AdvAII(κ) is negligible in κ.


## 4.4. Adversarial Game with Malicious Original Signer

The adversarial game between a malicious original signerAIII and a simulator S is defined as follows:(i)
Setup,Key Extract Queries andProxy Signing Queries are the same as those in the adversarial game against a malicious proxy signer.(ii)
Proxy Signer’s Standard Signature Queries: AIII queries the proxy signer’s standard signing oracle Ops′s with a message m∈M of his choice under an identity ID∈ID. S generates the private key skID using the key extract algorithm skID←KeyExtract(MSK,ID,params); then S generates the standard signature σp←StandardSign(skID,m,params) and sends σp to AIII.(iii)
Forgery Phase: finally, AIII outputs a proxy signature σ∗ on message M∗ for a warrant W∗ with the original signer’s identity IDA and the proxy signer’s identity IDB.We sayAIII wins the game if(i)
ProVer(σ∗,IDA,IDB,W∗,M∗)=1;(ii)
IDB has not been queried to the key extraction oracle OKE;(iii)
(W∗,M∗,IDB) has not been queried to the proxy signer’s standard signing oracle OPS′S;(iv)
(W∗,M∗,IDA,IDB) has not been queried to the proxy signing oracle OPS.Define the advantage of a malicious adversaryAIII in winning the game as (6)AdvAIIIκ=PrAIIIWins  the  game.Definition 4.
We say an identity-based proxy signature scheme is secure against theAIII under chosen identity and message attacks if for any probabilistic polynomial time AIII, AdvAIII(κ) is negligible in κ.


## 5. The Revised Identity-Based Proxy Signature Scheme

We present the revised ID-based proxy signature scheme that efficiently thwarts the proposed attack in this section.(1)
Setup: let e:G1×G1→G2 be a bilinear pairing map, where G1 and G2 are of prime order q. Let P be a generator of G1. Choose a random number s∈Zq∗ and set Ppub=sP. Select three collision-resistant hash functions H0,H1,H2 such that H0,H1,H2:{0,1}∗→G1. The system parameters params={e,G1,G2,q,Ppub,H0,H1,H2}, the master secret key Msk=s.(2)
KeyExtract: on input a user’s identity ID, output the secret key for this identity skID=sH0(ID).(3)
StandardSign: on input a message m, the standard signature on m under identity ID is σ=(σ1,σ2) such that σ1=skID+rH1(m) and σ2=rP, where r∈Zq∗.(4)
StandardVer: on input a standard signature σ=(σ1,σ2) of message m under identity ID, output “1” if e(σ1,P)=e(H0(ID),Ppub)e(H1(m),σ2); otherwise, output “0”.(5)
DelegationGen: let w be a warrant that includes the delegation information such as the identities of the original signer and the designated proxy signer, the delegation period, the types of messages that a proxy signer can sign, and so on. Then the original signer with identity IDA generates the delegation information σw=(σW1,σW2) such that σW1=skIDA+rAH1(w) and σW2=rAP, where rA∈Zq. The original signer sends the delegation information σw to the proxy signer.(6)
ProSign: upon receiving the delegation information σw=(σW1,σW2) and w from the original signer, the proxy signer with identity IDB generates a proxy signature σ=(σM1,σM2,σM3 on a message m such that σM1=σW1+skIDB+rBH2(w,m)+rBH1(w), σM2=σW2+rBP, σM3=rBP.(7)
ProVer: on input the identities IDA,IDB of the original signer and proxy signer, a warrant w and a message m and the proxy signature σ=(σM1,σM2,σM3), outputs “1” if e(σM1,P)=e(H0(IDA),Ppub)e(H1(w)),σM2)·e(H0(IDB),Ppub)e(H2(w,m),σM3). Otherwise, output “0”.


## 6. Security Analysis

In this section, we analyse the security of the revised ID-based proxy signature scheme againstAI, AII, and AIII adversaries.Theorem 5.
The revised ID-based proxy signature scheme is secure against an outsider adversaryAI if the CDH assumption holds.Proof.
The proof is by contradiction under the random oracle model. Suppose there exists an outsider adversaryAI that has a nonnegligible advantage ϵ in attacking the proposed scheme; then we can build another algorithm B that uses AI to solve the CDH problem. Let G1 be a bilinear pairing group of prime order q; B is given P,aP,bP∈G1 which is a random instance of the CDH problem. Its goal is to compute abP. Algorithm B will simulate the challenger and interact with the forger AI as described below. (1)
Setup: B selects a bilinear map e:G1×G1→G2 where G1 and G2 are of prime order q. B chooses a generator P of G1. Let (P,aP,bP) be the inputs of the CDH problem. B sets the master public key Ppub=sP, where s∈Zq∗. B selects three collision-resistant hash functions H0,H1,H2:{0,1}∗→G1. B sends (e,G1,G2,q,P,Ppub,H0,H1,H2) to AII.(2)
Hash queries: in the security proof, the hash functions H0,H1,H2 are modelled as random oracles. We regard the identity, warrant, and message queries as H0, H1, and H2 queries, respectively. Assume B keeps hash tables T0, T1, and T2 for these queries.
(a)
H0Query: for each query on identity IDi, if IDi has existed in T0, the same value H0(IDi) is returned to AII. Otherwise, B chooses a random ci∈Zq and sets H0(IDi)=ciP. B sends ciP to AI as well as stores (IDi,ci,H0(IDi)) to T0.(b)
H1Query: assume AI makes qH1 warrant queries; B selects a random number β∈(1,qH1), for each query on warrant wi such that 1≤i≠β≤qH1; if wi has existed in T1, the same value H1(wi) is returned to AI. Otherwise,
(i)
ifwi≠wβ, B chooses a random ki∈Zq and sets H1(wβ)=kiP. B sends H1(wβ) to AI as well as storing (wβ,ki,H1(wβ)) to T1.(ii)
Ifwi=wβ, B sets H1(wβ)=aP. B sends H1(wβ) to AI.(c)
H2Query: for each query on message mi accompanying with a warrant wi, if H2(wi,mi) has existed in T2, the same value H2(wi,mi) is returned to AI. Otherwise, B chooses a random ui∈Zq and sets H2(wi,mi)=uiP. B sends H2(wi,mi) to AI as well as storing ((wi,mi),ui,H2(wi,mi)) to T2.(3)
Original signer’s standard signing queries: AI can query the original signer’s standard signature on a warrant wi. Assume AI makes qos′s queries with the original signer’s identity IDA, for each query on wi, assume H0(IDA) and H1(wi) have existed in T0 and T1; if they are not the cases, B performs the above algorithms to assign values for H0(IDA) and H1(wi). Assume H0(IDA)=cAP, B simulates as follows:
(i)
Ifwi≠wβ, assume H1(wi)=kiP; then B chooses randomly rAi∈Zq and sets σwi=(σwi1,σwi2) such that σwi1=cAsP+rAikiP=sH0(IDA)+rAiH1(wi) and σwi2=rAiP.(ii)
Ifwi=wβ, then B chooses randomly rAβ∈Zq and sets σβ=(σwβ1,σ2β2) such that σwβ1=cAsP+rAβbP=sH0(IDA)+rAβH1(wβ) and σwβ2=rAβP.(4)
Proxy signer’s standard signing queries: assume AI makes qps′s standard signature queries under the proxy signer’s identity IDB. For each query on Mi=wi∥mi, assume H0(IDB) and H2(Mi) have existed in T0 and T2; if they are not the cases, B performs the above algorithms to assign values for H0(IDA) and H2(Mi). Assume H0(IDB)=cBP; B chooses a number δ∈(1,qps′s) and simulates as follows:
(i)
IfMi≠Mδ, assume H2(M2)=uiP; then B chooses randomly rBi∈Zq and sets σpi=(σpi1,σpi2) such that σpi1=cBsP+rBikiP=sH0(IDB)+rBiH2(Mi) and σpi1=rBiP.(ii)
IfMi=Mδ, assume H2(Mδ)=uδP; then B sets dskδ=(σB1δ,σB2δ) such that σB1δ=cBsP+buδP=sH0(IDB)+bH2(Mδ) and σB2i=bP.(5)
Forgery: assume AI outputs a valid proxy signature σ∗=(σM1∗,σM2∗,σM3∗) on message M∗ under a warrant W∗ with the proxy signer’s identity IDA and the proxy signer’s identity IDB. Besides,
(i)
(IDA,W∗) has been queried in the original signer’s standard signing queries;(ii)
(IDB,W∗,M∗) has been queried in the proxy signer’s standard signing queries.IfW∗≠wβ or M∗≠Mδ, B will abort. Otherwise, given the forged proxy signature σ∗=(σM1∗,σM2∗,σM3∗). B can solve the CDH problem(7)abP=σM1∗-σA1β-σB1δ
B will not abort when W∗=wβ and M∗=Mδ. Thus, if there exists an outsider adversary AI that has a nonnegligible probability ϵ in breading the proposed identity-based proxy signature scheme, then there exists another probabilistic polynomial time algorithm B that has a probability(8)SuccB,G1CDH=ϵqos′s·qps′swhich is nonnegligible. Thus, we reach a contradiction.Theorem 6.
The revised ID-based proxy signature scheme is secure against theAII chosen identity and chosen warrant attacks if the CDH assumption holds.Proof.
Let us recall the definition ofAII; AII is a malicious proxy signer possessing the private key of the proxy signer. With this in mind, the simulation is as follows: (1)
Setup: B selects a bilinear map e:G1×G1→G2, where G1 and G2 are of prime order q. B chooses a generator P of G1. Let (P,aP,bP) be the inputs of the CDH problem. B sets the master public key Ppub=aP. B selects three collision-resistant hash functions H0,H1,H2:{0,1}∗→G1. B sends (e,G1,G2,q,P,Ppub,H0,H1,H2) to AII.(2)
Hash queries: regard the identity, warrant, and message queries as H0, H1, and H2 queries, respectively. B keeps hash tables T0, T1, and T2 for these queries.
(a)
H0Query: assume AII makes qH0 identity queries, choose α∈(1,qH0), for each query on identity IDi such that 1≤i≠α≤qH0, if IDi has existed in T0, the same value H0(IDi) is returned to AII. Otherwise,
(i)
Ifi≠α, B chooses a random ci∈Zq and sets H0(IDi)=ciP. B sends ciP to AII as well as storing (IDi,ci,H0(IDi)) to T0.(ii)
Ifi=α, B sets H0(IDα)=bP+cαP, where cα∈Zq and returns H0(IDI) to AII. B adds (IDα,cα,H0(IDα)) to T0.(b)
H1Query: assume AII makes qH1 warrant queries; B selects a random number β∈(1,qH1), for each query on warrant wi such that 1≤i≠β≤qH1, if wi has existed in T1, the same value H1(wi) is returned to AII. Otherwise,
(i)
ifwi≠wβ|IDα→o, which means IDα is included in wi and the user with identity IDα plays the role of original signer in the system. B chooses a random ki∈Zq and sets H1(wi)=kiP-bP. B sends H1(wi) to AII as well as storing (wi,bi,H1(wi)) to T1;(ii)
ifwi≠wβ|IDα→p, which means IDα is included in wi and the user with identity IDα plays the role of proxy signer in the system. B chooses a random ki∈Zq and sets H1(wi)=kiP. B sends H1(wi) to AII as well as stores (wi,ki,H1(wi)) to T1;(iii)
ifwi=wβ, B chooses a random ki∈Zq and sets H1(wβ)=kiP. B sends H1(wβ) to AII as well as storing (wβ,ki,H1(wβ)) to T1.(c)
H2Query: assume AII makes qH2 message queries, B selects a random number δ∈(1,qH1), for each query on message mi accompanying with a warrant wi such that 1≤i≠δ≤qH2, if H2(wi,mi) has existed in T2, the same value H2(wi,mi) is returned to AII. Otherwise,
(i)
ifwi≠wβ,mi≠mδ, B chooses a random ui∈Zq and sets H2(wi,mi)=uiP+aP. B sends H2(wi,mi) to AII as well as storing ((wi,mi),ci,H2(wi,mi)) to T2;(ii)
ifwi=wβ,mi≠mδ, the same as the case when wi≠wβ,mi≠mδ;(iii)
ifwi≠wβ,mi=mδ, the same as the case when wi≠wβ,mi≠mδ;(iv)
ifwi=wβ,mi=mδ, B chooses a random ui∈Zq and sets H2(wβ,mδ)=uiP. B sends H2(wβ,mβ) to AII as well as storing ((wβ,mδ),ui,H2(wβ,mδ)) to T2.(3)
Key extraction queries: AII can make key extraction queries on any identity ID∈ID such that ID≠IDα. If AII makes key extraction query on identity IDα, B just terminates the simulation and reports a failure. Assume AII makes qk key extractions queries, for each query on identity IDi for 1≤i≤qk.
(i)
IfIDi has existed in table T0, assume H0(IDi)=ciP; then B returns skIDi=ciaP=aH0(IDi) to AII.(ii)
Otherwise,B chooses a random ci∈Zq and sets H0(IDi)=ciP. B returns skIDi=ciaP to AII and adds (IDi,ci,H0(IDi)) to T0.(4)
Original signer’s standard signing queries: AII can query original signer’s standard signature on a warrant wi∈W under an identity IDi∈ID. Assume AII makes qos′s original signer’s standard signing queries. For each query, assume IDi and wi have been submitted to the H0 and H1 queries, respectively. If they are not the cases, B performs the above algorithms to set values for H0(IDi) and H1(wi); then B simulates σwi as follows:
(i)
IfIDi≠IDα and wi≠wβ|IDα→o, assume H0(IDi)=ciP and H1(wi)=kiP-bP, respectively; then B chooses a random ri∈Zq and returns the original signer’s standard signature σwi=(σwi1,σwi2) such that σwi1=ciPpub+ri(kiP-bP)=skIDi+riH1(wi) and σwi2=riP and to AII.(ii)
IfIDi≠IDα and wi≠wβ|IDα→p, assume H0(IDi)=ciP and H1(wi)=kiP, respectively; then B chooses a random ri∈Zq and returns original signer’s standard signature σwi=(σwi1,σwi2) such that σwi1=ciPpub+rikiP=skIDi+riH1(wi) and σwi2=riP to AII.(iii)
IfIDi=IDα and wi≠wβ|IDα→o, assume H0(IDi)=bP+ciP and H1(wi)=kiP-bP, respectively; then B simulates the original signer’s standard signature σwi=(σwi1,σwi2) by setting σwi2=riP=liP+aP, where li∈RZq∗ and σwi1=(ci+ki)Ppub+kiliP-libP. It can be verified that (σwi1,σwi2) is a correct simulation since (9)σwi1=ci+kiPpub+kiliP-libP=abP+ciaP+kiaP+kiliP-libP-abP=aciP+bP+a+likiP-bP=aH0IDα+riH1wi(iv)
IfIDi=IDα and wi≠wβ|IDα→p, since we do not consider self-delegation in our scheme, then B just terminates the simulation and reports failure.(v)
IfIDi=IDα and wi=wβ, B terminates the simulation and reports failure.(5)
Proxy signing queries: AII can query a proxy signature on a message mi∈M under a warrant wi∈W with the proxy signer’s identity ID1i and the original signer’s identity ID2i such that ID1i,ID2i∈ID. Assume ID1i,ID2i have been submitted to the H0 query and wi and wi∥mi have been submitted to the H1 and H2 queries, respectively. If they are not the cases, the above algorithms will be performed to assign new values H0(ID1i), H0(ID2i), H1(wi), and H2(wi,mi). Assume AII makes qps proxy signing queries. For each queries on a message mi with warrant wi such that 1≤i≤qps, B simulates the corresponding proxy signature as follows:
(a)
IfID1i≠IDα, ID2i≠IDα assume H0(ID1i)=c1iP, H0(ID2i)=c2iP; then B chooses two random numbers r1i,r2i∈Zq∗ and returns the proxy signature σi=(σMi1,σMi2,σMi3) such that σMi1=c1iaP+r1iH1(wi)+c2iaP+r2iH2(wi,mi)+r2iH2(mi), σMi2=(r1i+r2i)P and σMi3=r2iP to AII. It is a correct simulation since (10)eσMi1,P=ec1iaP+r1iH1wi+c2iaP+r2iH2wi,mi+r2iH1wi,P=ec1iP,aPeH1wi,r1i+r2iPec2iP,aPeH2mi,wi,r2iP=eH0ID1i,PpubeH1wi,σMi2eH0ID2i,PpubeH2mi,wi,σMi3(b)
IfID1i≠IDα, ID2i=IDα, assume H0(ID1i)=c1iP, H0(ID2i)=cαP+bP; then
(i)
Ifwi≠wβ|IDα→o,mi≠mδ or wi≠wβ|IDα→o,mi=mδ, B terminates the simulation and reports failure.(ii)
Ifwi≠wβ|IDα→p and mi≠mδ, assume H1(wi)=kiP and H2(wi,mi)=uiP+aP; B simulates the proxy signature σi=(σMi1,σMi2,σMi3) by setting σMi3=r2iP=viP-bP, σMi2=r1iP+viP-bP and σMi1=(c1i+cα+vi)Ppub+r1iH2(wi)+ki(viP-bP)+ui(viP-bP), where vi,r1i∈Zq. It can be verified that it is a correct simulation since (11)eσMi1,P=ec1i+cα+viPpub+r1iH2wi+kiviP-bP+uiviP-bP,P=ec1iP,aPeH1wi,r1i+r2iPeabP+cαaP+viaP+uiviP-uibP-abP,P=ec1iP,aPeH1wi,r1i+r2iPeabP+cαP,Pevi-buiP+aP,P=eH0ID1i,PpubeH1wi,σMi2eH0ID2i,PpubeH2wi,mi,σMi3(iii)
Ifwi≠wβ|IDα→p,mi=mδ or wi=wβ,mi≠mδ, B performs the same as that in case (ii).(iv)
Ifwi=wβ and mi=mδ, B terminates the simulation and reports failure.(c)
IfID1i=IDα, ID2i≠IDα, assume H0(ID1i)=cαP+bP, H0(ID2i)=c2iP, then
(i)
ifwi≠wβ|IDα→o and mi≠mδ, assume H1(wi)=kiP-bP and H2(wi,mi)=uiP+aP. B chooses li,r2i∈Zq∗ and simulates the proxy signature σi=(σMi1,σMi2,σMi3) by setting σMi3=r2iP, σMi2=viP-bP+r2iP and σMi1=(cα+ki+c2i)Ppub+li(kiP-bP)+r2i(kiP-bP)+r2i(uiP+aP). It is a correct simulation since (12)eσMi1,P=ecα+ki+c2iPpub+likiP-bP+r2ikiP-bP+r2iuiP+aP,P=eabP+acαP+likiP-libP+akiP-abp+r2ikiP-bP,Pec2iPpub,Per2iuiP+aP,P=eacαP+bP,Peli+a+r2ikiP-bP,Pec2iP,aPeuiP+aP,r2iP=eH0ID1i,PpubeH1wi,σMi2eH0ID2i,PpubeH2wi,mi,σMi3(ii)
Ifwi≠wβ|IDα→p,mi≠mδ or wi≠wβ|IDα→p,mi=mδ, B terminates the simulation and reports failure.(iii)
Ifwi≠wβ|IDα→0 and mi=mδ, assume H1(wi)=kiP-bP and H2(wi,mβ)=uiP+aP; B performs the same as that in case (i).(iv)
Ifwi=wβ and mi≠mδ, assume H1(wβ)=kiP and H2(wβ,mi)=uiP+aP; B chooses vi,r1i∈Zq∗ and simulates the proxy signature σi=(σMi1,σMi2,σMi3) by setting σMi3=viP-bP, σMi2=viP-bP+r1iP, and σMi1=(cα+c2i+vi)Ppub+r1ikiP+ki(viP-bP)+ui(viP-bP). It is a correct simulation since (13)eσMi1,P=ecα+c2i+viPpub+r1ikiP+kiviP-bP+uiviP-bP,P=ecα+baP+c2iaP+r1ikiP+kiviP-bP+vi-baP+uiviP-bP,P=ecαP+bP,aPekiP,r1iP+viP-bPec2iP,aPeuiP,viP-bP=eH0ID1i,PpubeH1wi,σMi2eH0ID2i,PpubeH2wi,mi,σMi3(v)
Ifwi=wβ and mi=mδ, B terminates the simulation and reports failure.(d)
IfID1i=IDα, ID2i=IDα, B terminates the simulation and reports failure.(6)
Forgery: assume AII outputs a valid proxy signature σ∗=(σM1∗,σM2∗,σM3∗) on message M∗ under a warrant W∗ with the proxy signer’s identity IDA and the proxy signer’s identity IDB. Besides,
(i)
IDA has not been queried in the key extraction queries,(ii)
(IDA,W∗) has not been queried in the delegation queries,(iii)
(IDA,IDB,W∗,M∗) has not been queried in the proxy signing queries,IfH0(IDA)≠bP+cαP or H1(W∗)≠kβP or H2(W∗,M∗)≠uδP, B will abort. Otherwise, given the forged proxy signature σ∗=(σM1∗,σM2∗,σM3∗). B can solve the CDH problem(14)abP=σM1∗-cαaP-kβσM2∗-c2iaP-uδσM3∗whenH0(IDA)=bP+cαP, H1(IDB)=kβP, and H2(W∗,M∗)=uδP.
Next, we analyze the success probability ofB; B will not abort if the following conditions hold:(i)
IDA=IDα.(ii)
W∗=wβ.(iii)
M∗=mδ.
Therefore, ifAII has a nonnegligible probability ϵ in breaking the proposed ID-based proxy signature scheme, then the success probability of B in solving CDH problem is(15)SuccB,G1CDH≥ϵqH0+qk+qos′s+2qpsqH1+qos′s+qpsqH2+qps.which is nonnegligible. Thus, we reach a contradiction.Theorem 7.
The revised ID-based proxy signature scheme is secure against theAIII chosen message and identity attack if the CDH assumption holds.Proof.
The security is similar to that in Theorem6. Thus, we just describe it briefly. (1)
Setup,Hash queries, andKey extract queries are the same as those in the security proof against a malicious proxy signer.(2)
Proxy signer’s standard signing queries andProxy signing queries are similar to theOriginal signer’s stand signing queries andProxy signing queries in the security for Theorem 6.
Through simulation, it can be reduced that if there exists a malicious original signer that can break the proposed scheme with a nonnegligible probabilityϵ, then we can build another probabilistic polynomial time algorithm B that can solve the CDH problem with a nonnegligible probability SuccB,G1CDH such that(16)SuccB,G1CDH≥ϵqH0+qk+qps′s+2qpsqH1+qps′s+qpsqH2+qps where qps′s refers to the number of proxy signer’s standard signing queries. Thus, we reach a contradiction.


### 6.1. Efficiency Analysis

We analyze the efficiency of the revised proxy signature scheme and compare it with the original scheme. The detail computation costs are presented in Table1. As have been noticed, some algorithms in the revised scheme remains unchanged; thus, we only concern those algorithms that are different in our and the original schemes. Let MG1, AG1 denote the multiplication add addition calculations in G1, TH denote the calculation of hash function (either H0, H1, or H2), and let P denote the calculation of paring. We can see that our revised proxy signature scheme involves only one addition, two multiplication, and one hash operation in the proxy signing algorithm. As for the expensive paring operations needed in the proxy verification parts, the numbers are exactly the same.Table 1
Comparison regarding the computational costs.
Schemes ProSign ProVer Wu et al.’s scheme [13] 2 ⋅ A G 1 + 2 ⋅ M G 1 + 1 ⋅ T H 5 ⋅ P + 4 ⋅ T H  Our scheme 3 ⋅ A G 1 + 4 ⋅ M G 1 + 2 ⋅ T H 5 ⋅ P + 4 ⋅ T H


## 6.1. Efficiency Analysis

We analyze the efficiency of the revised proxy signature scheme and compare it with the original scheme. The detail computation costs are presented in Table1. As have been noticed, some algorithms in the revised scheme remains unchanged; thus, we only concern those algorithms that are different in our and the original schemes. Let MG1, AG1 denote the multiplication add addition calculations in G1, TH denote the calculation of hash function (either H0, H1, or H2), and let P denote the calculation of paring. We can see that our revised proxy signature scheme involves only one addition, two multiplication, and one hash operation in the proxy signing algorithm. As for the expensive paring operations needed in the proxy verification parts, the numbers are exactly the same.Table 1
Comparison regarding the computational costs.
Schemes ProSign ProVer Wu et al.’s scheme [13] 2 ⋅ A G 1 + 2 ⋅ M G 1 + 1 ⋅ T H 5 ⋅ P + 4 ⋅ T H  Our scheme 3 ⋅ A G 1 + 4 ⋅ M G 1 + 2 ⋅ T H 5 ⋅ P + 4 ⋅ T H


## 7. Conclusion

In this paper, we introduced a practical attack which has not been considered by some existing proxy signature schemes. In particular, we took an identity-based proxy signature scheme to describe how this attack works. We also presented an enhanced security model that can capture this attack. Our model has considered different types of potential adversaries against an identity-based proxy signature scheme and allowed the adversary to query the individual signatures of both the original signer and the proxy signer. The proposed new scheme inherits the good features of the original scheme and at the same time can effectively prevent the attack. The proposed method can also be applied in other proxy signature schemes [18–21] to ensure an improved security.



---

*Source: 6925019-2018-08-06.xml*