# Attacks on One Designated Verifier Proxy Signature Scheme

Authors: Baoyuan Kang
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

In a designated verifier proxy signature scheme, there are three participants, namely, the original signer, the proxy signer, and the designated verifier. The original signer delegates his or her signing right to the proxy signer, then the proxy signer can generate valid signature on behalf of the original signer. But only the designated verifier can verify the proxy signature. Several designated verifier proxy signature schemes have been proposed. However, most of them were proven secure in the random oracle model, which has received a lot of criticism since the security proofs in the random oracle model are not sound with respect to the standard model. Recently, by employing Water's hashing technique, Yu et al. proposed a new construction of designated verifier proxy signature. They claimed that the new construction is the first designated verifier proxy signature, whose security does not rely on the random oracles. But, in this paper, we will show some attacks on  Yu et al.'s scheme. So, their scheme is not secure.


---

## Body

## 1. Introduction

The concept of proxy signature was first introduced by Mambo et al. [1] in 1996. Proxy signature is very useful when a user, called an original signer, wants to delegate his or her signing rights to the other user, called a proxy signer. In a proxy signature scheme, the proxy signer can generate a valid signature on behalf of the original signer. Anyone can verify the authenticity of the purported signature by using the public keys of the original signer and proxy signer. But, when a verifier receives a proxy signature, he should not only verify the correctness by a given verification procedure, but also be convinced of the original signer’ agreement on the signed message. Proxy signature schemes have been suggested for use in a number of applications, including electronic commerce, e-cash, and distributed shared object systems.Unlike standard signature, In order to protect signature privacy, Jakobsson et al. [2] introduced a new primitive named designated verifier proofs in 1996. Such a proof enables a prover convince a designated verifier  that a statement is true, while the designated verifier cannot use the proof to convince others of this fact, since the designated verifier himself can simulate such a proof. Furthermore, Jakobsson et al. proposed a designated verifier signature scheme in the sense that only the designated verifier can be convinced that a signature is produced by the claimed signer.  Jakobsson et al. also discussed a stronger concept called strong designated verifier signature in the same paper.In 2003, based on the concepts of proxy signatures and designated verifier signatures, Dai et al. [3] consider a scenario where the proxy signer wishes to protect his signing privilege from knowing by other parties. In other words, the proxy signer only wants to convince the designated receiver that he has signed the specific message. They proposed such a scheme called designated verifier proxy signature, which provides authentication of a message without providing a nonrepudiation property of traditional digital signature. A designated verifier proxy signature scheme can be used to convince the designated verifier and only the designated verifier whether a signature is valid or not. This is due to the fact that the designated verifier can always generate a valid signature intended for himself that is indistinguishable from an original signature. This kind of signature is useful in electronic commerce applications. Unfortunately, Wang [4] pointed out there exists a forgery attack in Dai et al.’s scheme. Huang et al. [5] proposed a short designated verifier proxy signature from pairings to improve the communication efficiency. Lu and cao [6] proposed a designated verifier proxy signature with message recovery in 2005. Zhang and Mao [7] proposed a novel ID-based designated verifier proxy signature scheme. Although several designated verifier proxy signature schemes have been proposed. However, most of them were proven secure in the random oracle model, which has received a lot of criticism since the security proofs in the random oracle model are not sound with respect to the standard model. Recently, by employing Water’s hashing technique [8], Yu et al. [9] proposed a new construction of designated verifier proxy signature scheme. They claimed that the new construction is the first designated verifier proxy signature scheme, whose security does not rely on the random oracles. But in this paper, we will show some attacks on their scheme. So, their scheme is not secure.The paper is organized as follows. In the next section, we will review Yu et al.’s designated verifier proxy signature scheme. The attacks on Yu et al.'s scheme are presented in Section3. Finally, Section 4 concludes the paper.


## 2. Review  of  Yu et al.’s Designated Verifier Proxy Signature Scheme

In this section, we review the designated verifier proxy signature scheme proposed by Yu et al.. There are three participants in Yu et al.’s scheme, namely, Alice, Bob, and Cindy, who act as the original signer, the proxy signer, and the designated verifier, respectively. Yu et al.’s scheme consists of the following algorithms.


### 2.1. Setup

The system parameters are as follows. Let(G,GT) be bilinear groups, where |G|=|GT|=p for some prime, g is a generator of G. e denotes an admissible pairing G×G→GT. Pick u′,m′∈G and vectors u→=(ui),m→=(mi) of length n, whose entries are random elements from G. The public parameters are  (G,GT,e,u′,m′,u→,m→).


### 2.2. Keygen

Alice picks randomlyxa,ya∈Zp* and sets her secret key ka=(xa,ya). Then she computes her public key:
(2.1)pka=(pkax,pkay)=(gxa,gya).
Similarly, Bob’s secret key is  skb=(xb,yb), and the public key is
(2.2)pkb=(pkbx,pkby)=(gxb,gyb).
Cindy’s secret key is  skc=(xc,yc), and the public key is
(2.3)pkc=(pkcx,pkcy)=(gxc,gyc).


### 2.3. DelegationGen

LetW be an n-bit message called warrant to be signed by the original signer and Wi denotes the i-bit of, and let w⊆{1,2,…,n} be the set of all i for which Wi=1. The original signer picks a random  ra∈Zp and computes the delegation σω=(σω1,σω2) and sends it to the proxy signer Bob, where
(2.4)σω1=gxaya(u′∏i∈wui)ra,σω2=gra.


### 2.4. ProxySign

LetM be an n-bit message to be signed by the proxy signer Bob and Mi denotes the i-bit of, and let m⊆{1,2,…,n} be the set of all i for which Mi=1. The proxy signature is generated as follows. First, the proxy signer Bob picks two random values  ra′,rb∈Zp. Then the proxy signature σ=(σ1,σ2,σ3) on M is constructed as
(2.5)σ1=e(σω1(u′∑i∈wui)ra′gxbya(m′∏i∈mmi)rb,pkcx),σ2=σω2gra′,σ3=grb.


### 2.5. Verification

To check whetherσ=(σ1,σ2,σ3) is a valid proxy signature on the message M under the warrant, Cindy uses her secret key to verify whether the following equation holds:(2.6)σ1=e(pkax,pkay)xce(pkbx,pkby)xc⋅e(u′∑i∈wui,σ2)xce(m′∏i∈mmi,σ3)xc.


### 2.6. Transcript Simulation

Cindy can use her private key to compute a signature on an arbitrary messageM* with the warrant W*. She picks two random values r1,r2∈Zp* and computes  σ*=(σ1*,σ2*,σ3*), where
(2.7)σ2*=gr1,σ3*=gr2,σ1*=e(pkax,pkay)xce(pkbx,pkby)xc⋅e(u′∑i∈w*ui,σ2*)xce(m′∏i∈m*mi,σ3*)xc.


## 2.1. Setup

The system parameters are as follows. Let(G,GT) be bilinear groups, where |G|=|GT|=p for some prime, g is a generator of G. e denotes an admissible pairing G×G→GT. Pick u′,m′∈G and vectors u→=(ui),m→=(mi) of length n, whose entries are random elements from G. The public parameters are  (G,GT,e,u′,m′,u→,m→).


## 2.2. Keygen

Alice picks randomlyxa,ya∈Zp* and sets her secret key ka=(xa,ya). Then she computes her public key:
(2.1)pka=(pkax,pkay)=(gxa,gya).
Similarly, Bob’s secret key is  skb=(xb,yb), and the public key is
(2.2)pkb=(pkbx,pkby)=(gxb,gyb).
Cindy’s secret key is  skc=(xc,yc), and the public key is
(2.3)pkc=(pkcx,pkcy)=(gxc,gyc).


## 2.3. DelegationGen

LetW be an n-bit message called warrant to be signed by the original signer and Wi denotes the i-bit of, and let w⊆{1,2,…,n} be the set of all i for which Wi=1. The original signer picks a random  ra∈Zp and computes the delegation σω=(σω1,σω2) and sends it to the proxy signer Bob, where
(2.4)σω1=gxaya(u′∏i∈wui)ra,σω2=gra.


## 2.4. ProxySign

LetM be an n-bit message to be signed by the proxy signer Bob and Mi denotes the i-bit of, and let m⊆{1,2,…,n} be the set of all i for which Mi=1. The proxy signature is generated as follows. First, the proxy signer Bob picks two random values  ra′,rb∈Zp. Then the proxy signature σ=(σ1,σ2,σ3) on M is constructed as
(2.5)σ1=e(σω1(u′∑i∈wui)ra′gxbya(m′∏i∈mmi)rb,pkcx),σ2=σω2gra′,σ3=grb.


## 2.5. Verification

To check whetherσ=(σ1,σ2,σ3) is a valid proxy signature on the message M under the warrant, Cindy uses her secret key to verify whether the following equation holds:(2.6)σ1=e(pkax,pkay)xce(pkbx,pkby)xc⋅e(u′∑i∈wui,σ2)xce(m′∏i∈mmi,σ3)xc.


## 2.6. Transcript Simulation

Cindy can use her private key to compute a signature on an arbitrary messageM* with the warrant W*. She picks two random values r1,r2∈Zp* and computes  σ*=(σ1*,σ2*,σ3*), where
(2.7)σ2*=gr1,σ3*=gr2,σ1*=e(pkax,pkay)xce(pkbx,pkby)xc⋅e(u′∑i∈w*ui,σ2*)xce(m′∏i∈m*mi,σ3*)xc.


## 3. Attacks on Yu et al.’s Designated Verifier Proxy Signature Scheme

In this section, we will give some attacks on Yu et al.’s designated verifier proxy signature scheme.


### 3.1.  Attack 1

On receiving the delegationσω=(σω1,σω2) and the warrant, the attacker randomly selects ra*∈Zp and alters the delegation as σω*=(σω1*,σω2*), where
(3.1)σω1*=σω1(u′∏i∈wui)ra*,(3.2)σω2*=σω2gra*.


### 3.2. Attack 2

On receiving the proxy signatureσ=(σ1,σ2,σ3) on one message M, everybody can forge another valid proxy signature σ*=(σ1*,σ2*,σ3*) on M as follows:
(3.3)σ1*=σ1⋅e((m′∏i∈mmi)rb*,pkcx),σ2*=σ2,σ3*=σ3grb*rb*∈Zp is  a  random  number.In fact, becauseσ=(σ1,σ2,σ3) is valid proxy signature, the following verification equation holds:
(3.4)σ1=e(pkax,pkay)xce(pkbx,pkby)xc⋅e(u′∑i∈wui,σ2)xce(m′∏i∈mmi,σ3)xc.
Then,
(3.5)σ1*=σ1⋅e((m′∏i∈mmi)rb*,pkcx)=e(pkax,pkay)xce(pkbx,pkby)xc⋅e(u′∑i∈wui,σ2)xce(m′∏i∈mmi,σ3)xc⋅e((m′∏i∈mmi)rb*,pkcx)=e(pkax,pkay)xce(pkbx,pkby)xc⋅e(u′∑i∈wui,σ2)xce(m′∏i∈mmi,σ3)xc⋅e(m′∏i∈mmi,grb*)xc=e(pkax,pkay)xce(pkbx,pkby)xc⋅e(u′∑i∈wui,σ2)xce(m′∏i∈mmi,σ3grb*)xc=e(pkax,pkay)xce(pkbx,pkby)xc⋅e(u′∑i∈wui,σ2)xce(m′∏i∈mmi,σ3*)xc.
So,σ*=(σ1*,σ2*,σ3*)is  a  valid  proxy  signature  onM.


### 3.3. Attack 3

Anyone who getsgxaya can personate the original signer to delegate signing rights of the original signer. On the other hand, in some scenarios the original signer may reveal gxaya without revealing his private key (xa,ya) to make confusion about the delegation of signing rights on purpose.


### 3.4. Attack 4

Similarly, anyone who getsgxbyb can personate the proxy signer to generate proxy signatures. On the other hand, in some scenarios the proxy signer may reveal gxbyb without revealing his private key (xb,yb) to make confusion about the production of proxy signatures on purpose.


## 3.1.  Attack 1

On receiving the delegationσω=(σω1,σω2) and the warrant, the attacker randomly selects ra*∈Zp and alters the delegation as σω*=(σω1*,σω2*), where
(3.1)σω1*=σω1(u′∏i∈wui)ra*,(3.2)σω2*=σω2gra*.


## 3.2. Attack 2

On receiving the proxy signatureσ=(σ1,σ2,σ3) on one message M, everybody can forge another valid proxy signature σ*=(σ1*,σ2*,σ3*) on M as follows:
(3.3)σ1*=σ1⋅e((m′∏i∈mmi)rb*,pkcx),σ2*=σ2,σ3*=σ3grb*rb*∈Zp is  a  random  number.In fact, becauseσ=(σ1,σ2,σ3) is valid proxy signature, the following verification equation holds:
(3.4)σ1=e(pkax,pkay)xce(pkbx,pkby)xc⋅e(u′∑i∈wui,σ2)xce(m′∏i∈mmi,σ3)xc.
Then,
(3.5)σ1*=σ1⋅e((m′∏i∈mmi)rb*,pkcx)=e(pkax,pkay)xce(pkbx,pkby)xc⋅e(u′∑i∈wui,σ2)xce(m′∏i∈mmi,σ3)xc⋅e((m′∏i∈mmi)rb*,pkcx)=e(pkax,pkay)xce(pkbx,pkby)xc⋅e(u′∑i∈wui,σ2)xce(m′∏i∈mmi,σ3)xc⋅e(m′∏i∈mmi,grb*)xc=e(pkax,pkay)xce(pkbx,pkby)xc⋅e(u′∑i∈wui,σ2)xce(m′∏i∈mmi,σ3grb*)xc=e(pkax,pkay)xce(pkbx,pkby)xc⋅e(u′∑i∈wui,σ2)xce(m′∏i∈mmi,σ3*)xc.
So,σ*=(σ1*,σ2*,σ3*)is  a  valid  proxy  signature  onM.


## 3.3. Attack 3

Anyone who getsgxaya can personate the original signer to delegate signing rights of the original signer. On the other hand, in some scenarios the original signer may reveal gxaya without revealing his private key (xa,ya) to make confusion about the delegation of signing rights on purpose.


## 3.4. Attack 4

Similarly, anyone who getsgxbyb can personate the proxy signer to generate proxy signatures. On the other hand, in some scenarios the proxy signer may reveal gxbyb without revealing his private key (xb,yb) to make confusion about the production of proxy signatures on purpose.


## 4. Conclusion

A designated verifier proxy signature scheme can be used to convince the designated verifier and only the designated verifier whether a signature is valid or not. This is due to the fact that the designated verifier can always generate a valid signature intended for him that is indistinguishable from an original signature. This kind of signature is useful in electronic commerce applications. Recently, Yu et al. proposed a new construction of designated verifier proxy signature scheme. As for the security, they classified the potential adversaries into three kinds according to their attack power and proved that their scheme is unforgeable against all kinds of adversaries in the standard model. But, in this paper, we show some attacks on their scheme. So, their scheme is not secure.



---

*Source: 508981-2012-07-05.xml*