# On the Security of a Novel Probabilistic Signature Based on Bilinear Square Diffie-Hellman Problem and Its Extension

Authors: Zhenguo Zhao; Wenbo Shi
Journal: The Scientific World Journal
 (2014)

---

## Abstract

Probabilistic signature scheme has been widely used in modern electronic commerce since it could provide integrity, authenticity, and nonrepudiation. Recently, Wu and Lin proposed a novel probabilistic signature (PS) scheme using the bilinear square Diffie-Hellman (BSDH) problem. They also extended it to a universal designated verifier signature (UDVS) scheme. In this paper, we analyze the security of Wu et al.’s PS scheme and UDVS scheme. Through concrete attacks, we demonstrate both of their schemes are not unforgeable. The security analysis shows that their schemes are not suitable for practical applications.


---

## Body

## 1. Introduction

Signature scheme is an important modern cryptographic mechanism of the public key cryptosystem. In the signature scheme, the signer uses his private key to sign a message and generate a signature, which could be verified by other users using the signer’s public key. The signature could provide integrity, authenticity, and nonrepudiation; then it could be used in modern electronic commerce [1–5].The undeniable signature (US) scheme is a variation of the signature scheme, which was first introduced by Chaum and van Antwerpen [6]. In the US scheme, the verifier should get the signer’s cooperation to finish the verification. In order to remove the complicated cooperation between the signer and the verifier, Jakobsson et al. [7] introduced the concept of the designated verifier signature (DVS) scheme and proposed a concrete DVS scheme. However, Wang [8] found that there is serious security vulnerability in Jakobsson et al.’s scheme. Later, Steinfeld et al. [9, 10] introduced the concept of the universal designated verifier signature (UDVS) scheme to generate the concept of the DVS scheme. In the UDVS scheme, the signer could generate a signature and only the designated verifier could verify the signature using his private key.Later, Zhang et al. [11] used Diffie-Hellman problem to construct a UDVS scheme and demonstrated that their scheme is provably secure in the standard model. Unfortunately, Cheon [12] found that Zhang et al.’s scheme had a security flaw. To enhance security, Huang et al. [13] presented a new UDVS scheme using the gap bilinear Diffie-Hellman problem. In order to satisfy applications in identity-based systems, Chen et al. [14] proposed the first identity-based UDVS scheme. In order to improve efficiency, Wu and Lin [15] proposed a probabilistic signature (PS) scheme using the bilinear square Diffie-Hellman (BSDH) problem. Then, they extended this PS scheme to a UDVS scheme. They also demonstrated that both of their schemes are provably secure in the random oracle. In this paper, we analyze the security of both Wu and Lin’s PS scheme and UDVS scheme. Through concrete attacks, we show that neither of their schemes is unforgeable. We will also propose efficient countermeasures to withstand those attacks.The organization of the paper is sketched as follows. Section2 gives a brief review of Wu et al.’s PS scheme and UDVS scheme. Section 3 presents our attacks against Wu et al.’s PS scheme and UDVS scheme. Section 4 presents our countermeasures to withstand the proposed attacks. At last, Section 5 presents some conclusion of the paper.


## 2. Review of Wu and Lin’s Schemes

In this section, we will give the details of Wu et al.’s PS scheme and UDVS scheme.


### 2.1. Review of Wu and Lin’s PS Scheme

There are two participants in Wu and Lin’s PS scheme, that is, a signer and a verifier, where the signer generates a publicly verifiable signature (PV-signature) using his private key and the verifier could verify the validity of the PV-signature using the signer’s public key. There are three algorithms in Wu and Lin’s PS scheme, that is,Setup,PV-Signature-Generation, andPV-Signature-Verification.Setup. Taking a security parameter k as input, the system authority (SA) runs the following steps to generate system parameters. Besides, the user Ui registers his public key.(1)
SA chooses a random numberq and selects two multiplicative groups (G1,×) and (G2,×) with the same order q, where the bit length of q is k.(2)
SA chooses a generatorP of the group (G1,×) and a bilinear pairing e:G1×G1→G2.(3)
SA chooses two secure hash functionsh1 and h2, where h1:G1→G1 and h2:{0,1}*×G1→Zq.(4)
SA publishes the system parametersparams={G1,G2,q,P,e,h1,h2}.(5)
Ui chooses a random number xi∈Zq as his private key and registers his public key Yi=Pxi.PV-Signature-Generation. Upon receiving the message m, the signer Us runs the following steps to generate a PV-signature Ω.(1)
Us chooses a random number r∈Zq and computes R=Pr, T=h1(R)xs, and ρ=h2(m,R)xs2-rmod⁡q.(2)
Us outputs Ω=(R,T,ρ) as the PV-signature of the message m.PV-Signature-Verification. Upon receiving the message m, the PV-signature Ω, and the signer’s public key Ys, the verifier Uv runs the following steps to verify the validity of the PV-signature.(1)
Uv checks whether the equation e(PρR,h1(R))=e(Ys,T)h2(m,R) holds.(2)
If the equation holds,Uv confirms the PV-signature is valid; otherwise, Uv confirms that the PV-signature is not valid.


### 2.2. Review of Wu and Lin’s UDVS Scheme

There are two participants in Wu and Lin’s UDVS scheme, that is, a signer and a verifier, where the signer generates a designated verifiable signature (DV-signature) using his private key and only the designated verifier could verify the validity of the DV-signature using the signer’s public key. There are five algorithms in Wu and Lin’s UDVS scheme, that is,Setup,PV-Signature-Generation,PV-Signature-Verification,DV-Signature-Generation, andDV-Signature-Verification. Because the first three algorithms are the same as those in PS scheme, only the last two algorithms will be described in detail.DV-Signature-Generation. Upon receiving a message m and the designated verifier Uv’s public key Yv, the signer Us runs the following steps to generate a DV-signature Ω.(1)
Us chooses a random number r∈Zq and computes R=Pr, T=h1(R)xs, ρ=h2(m,R)xs2-rmod⁡q, and W=Yvρ.(2)
Us outputs Ω=(R,T,W) as the DV-signature of the message m.DV-Signature-Verification. Upon receiving a message m, the DV-signature Ω, and the signer’s public key Ys, the designated verifier Uv runs the following steps to verify the validity of the DV-signature.(1)
Uv checks whether the equation e(Wxv-1R,h1(R))=e(Ys,T)h2(m,R) holds.(2)
If the equation holds,Uv confirms the DV-signature is valid; otherwise, Uv confirms that the PV-signature is not valid.


## 2.1. Review of Wu and Lin’s PS Scheme

There are two participants in Wu and Lin’s PS scheme, that is, a signer and a verifier, where the signer generates a publicly verifiable signature (PV-signature) using his private key and the verifier could verify the validity of the PV-signature using the signer’s public key. There are three algorithms in Wu and Lin’s PS scheme, that is,Setup,PV-Signature-Generation, andPV-Signature-Verification.Setup. Taking a security parameter k as input, the system authority (SA) runs the following steps to generate system parameters. Besides, the user Ui registers his public key.(1)
SA chooses a random numberq and selects two multiplicative groups (G1,×) and (G2,×) with the same order q, where the bit length of q is k.(2)
SA chooses a generatorP of the group (G1,×) and a bilinear pairing e:G1×G1→G2.(3)
SA chooses two secure hash functionsh1 and h2, where h1:G1→G1 and h2:{0,1}*×G1→Zq.(4)
SA publishes the system parametersparams={G1,G2,q,P,e,h1,h2}.(5)
Ui chooses a random number xi∈Zq as his private key and registers his public key Yi=Pxi.PV-Signature-Generation. Upon receiving the message m, the signer Us runs the following steps to generate a PV-signature Ω.(1)
Us chooses a random number r∈Zq and computes R=Pr, T=h1(R)xs, and ρ=h2(m,R)xs2-rmod⁡q.(2)
Us outputs Ω=(R,T,ρ) as the PV-signature of the message m.PV-Signature-Verification. Upon receiving the message m, the PV-signature Ω, and the signer’s public key Ys, the verifier Uv runs the following steps to verify the validity of the PV-signature.(1)
Uv checks whether the equation e(PρR,h1(R))=e(Ys,T)h2(m,R) holds.(2)
If the equation holds,Uv confirms the PV-signature is valid; otherwise, Uv confirms that the PV-signature is not valid.


## 2.2. Review of Wu and Lin’s UDVS Scheme

There are two participants in Wu and Lin’s UDVS scheme, that is, a signer and a verifier, where the signer generates a designated verifiable signature (DV-signature) using his private key and only the designated verifier could verify the validity of the DV-signature using the signer’s public key. There are five algorithms in Wu and Lin’s UDVS scheme, that is,Setup,PV-Signature-Generation,PV-Signature-Verification,DV-Signature-Generation, andDV-Signature-Verification. Because the first three algorithms are the same as those in PS scheme, only the last two algorithms will be described in detail.DV-Signature-Generation. Upon receiving a message m and the designated verifier Uv’s public key Yv, the signer Us runs the following steps to generate a DV-signature Ω.(1)
Us chooses a random number r∈Zq and computes R=Pr, T=h1(R)xs, ρ=h2(m,R)xs2-rmod⁡q, and W=Yvρ.(2)
Us outputs Ω=(R,T,W) as the DV-signature of the message m.DV-Signature-Verification. Upon receiving a message m, the DV-signature Ω, and the signer’s public key Ys, the designated verifier Uv runs the following steps to verify the validity of the DV-signature.(1)
Uv checks whether the equation e(Wxv-1R,h1(R))=e(Ys,T)h2(m,R) holds.(2)
If the equation holds,Uv confirms the DV-signature is valid; otherwise, Uv confirms that the PV-signature is not valid.


## 3. Security Analysis of Wu and Lin’s Schemes

In this section, we will give the security analysis of Wu et al.’s PS scheme and UDVS scheme.


### 3.1. Security Analysis of Wu and Lin’s PS Scheme

Wu and Lin claimed that their PS scheme was unforgeable against various attacks. Through concrete attack, we will show that an adversary without the signerUs’s private key could forge a legal PV-signature of any message. Given a message m, the adversary A could forge a legal PV-signature through the following steps.(1)
A generates a random number ρ∈Zq and computes R=YsP-ρ and T=h1(R)h2(m,R)-1mod⁡q.(2)
A outputs Ω=(R,T,ρ) as the PV-signature of the message m.SinceR=YsP-ρ and T=h1(R)h2(m,R)-1mod⁡q, we could get
(1)e(PρR,h1(R))=e(PρYsP-ρ,h1(R))=e(Ys,h1(R)),e(Ys,T)h2(m,R)=e(Ys,h1(R)h2(m,R)-1mod⁡q)h2(m,R)=e(Ys,h1(R))h2(m,R)·h2(m,R)-1mod⁡q=e(Ys,h1(R)).From (1), we know that the equation e(PρR,h1(R))=e(Ys,T)h2(m,R) holds. Then, the PV-signature generated by the adversary could pass the verifier’s check. Therefore, the adversary could forge a legal PV-signature.


### 3.2. Security Analysis of Wu and Lin’s UDVS Scheme

Wu and Lin claimed that their UDVS scheme was unforgeable against various attacks. Through concrete attack, we will show that an adversary without the signerUs’s private key could forge a legal DV-signature of any message. Given a message m and the designated verifier Uv’s public key Yv, the adversary A could forge a legal DV-signature through the following steps.(1)
A generates a random number ρ∈Zq and computes R=YsP-ρ, T=h1(R)h2(m,R)-1mod⁡q and W=Yvρ.(2)
A outputs Ω=(R,T,ρ) as the DV-signature of the message m.SinceR=YsP-ρ, T=h1(R)h2(m,R)-1mod⁡q, W=Yvρ, and Yv=Pxv, we could get
(2)e(Wxv-1R,h1(R))=e((Yvρ)xv-1YsP-ρ,h1(R))=e(((Pxv)ρ)xv-1YsP-ρ,h1(R))=e(Pxvρxv-1YsP-ρ,h1(R))=e(PρYsP-ρ,h1(R))=e(Ys,h1(R)),e(Ys,T)h2(m,R)=e(Ys,h1(R)h2(m,R)-1mod⁡q)h2(m,R)=e(Ys,h1(R))h2(m,R)·h2(m,R)-1mod⁡q=e(Ys,h1(R)).From (2), we know that the equation e(Wxv-1R,h1(R))=e(Ys,T)h2(m,R) holds. Then, the DV-signature generated by the adversary could pass the verifier’s verification. Therefore, the adversary could forge a legal DV-signature.


## 3.1. Security Analysis of Wu and Lin’s PS Scheme

Wu and Lin claimed that their PS scheme was unforgeable against various attacks. Through concrete attack, we will show that an adversary without the signerUs’s private key could forge a legal PV-signature of any message. Given a message m, the adversary A could forge a legal PV-signature through the following steps.(1)
A generates a random number ρ∈Zq and computes R=YsP-ρ and T=h1(R)h2(m,R)-1mod⁡q.(2)
A outputs Ω=(R,T,ρ) as the PV-signature of the message m.SinceR=YsP-ρ and T=h1(R)h2(m,R)-1mod⁡q, we could get
(1)e(PρR,h1(R))=e(PρYsP-ρ,h1(R))=e(Ys,h1(R)),e(Ys,T)h2(m,R)=e(Ys,h1(R)h2(m,R)-1mod⁡q)h2(m,R)=e(Ys,h1(R))h2(m,R)·h2(m,R)-1mod⁡q=e(Ys,h1(R)).From (1), we know that the equation e(PρR,h1(R))=e(Ys,T)h2(m,R) holds. Then, the PV-signature generated by the adversary could pass the verifier’s check. Therefore, the adversary could forge a legal PV-signature.


## 3.2. Security Analysis of Wu and Lin’s UDVS Scheme

Wu and Lin claimed that their UDVS scheme was unforgeable against various attacks. Through concrete attack, we will show that an adversary without the signerUs’s private key could forge a legal DV-signature of any message. Given a message m and the designated verifier Uv’s public key Yv, the adversary A could forge a legal DV-signature through the following steps.(1)
A generates a random number ρ∈Zq and computes R=YsP-ρ, T=h1(R)h2(m,R)-1mod⁡q and W=Yvρ.(2)
A outputs Ω=(R,T,ρ) as the DV-signature of the message m.SinceR=YsP-ρ, T=h1(R)h2(m,R)-1mod⁡q, W=Yvρ, and Yv=Pxv, we could get
(2)e(Wxv-1R,h1(R))=e((Yvρ)xv-1YsP-ρ,h1(R))=e(((Pxv)ρ)xv-1YsP-ρ,h1(R))=e(Pxvρxv-1YsP-ρ,h1(R))=e(PρYsP-ρ,h1(R))=e(Ys,h1(R)),e(Ys,T)h2(m,R)=e(Ys,h1(R)h2(m,R)-1mod⁡q)h2(m,R)=e(Ys,h1(R))h2(m,R)·h2(m,R)-1mod⁡q=e(Ys,h1(R)).From (2), we know that the equation e(Wxv-1R,h1(R))=e(Ys,T)h2(m,R) holds. Then, the DV-signature generated by the adversary could pass the verifier’s verification. Therefore, the adversary could forge a legal DV-signature.


## 4. Countermeasures

### 4.1. Countermeasure for Wu and Lin’s PS Scheme

From the details of Wu and Lin’s PS scheme, we know that the valueT has no relation with the value of ρ. Then the adversary could choose the value T freely to remove the relation between R and ρ. To withstand the attack described in Section 3.1, we just need to modify Wu and Lin’s PS scheme slightly.DV-Signature-Generation. Upon receiving a message m, the signer Us runs the following steps to generate a PV-signature Ω.(1)
Us chooses a random number r∈Zq and computes R=Pr, T=h1(R)xs, and ρ=h2(m,R,T)xs2-rmod⁡q.(2)
Us outputs Ω=(R,T,ρ) as the PV-signature of the message m.DV-Signature-Verification. Upon receiving a message m, the PV-signature Ω, and the signer’s public key Ys, the verifier Uv runs the following steps to verify the validity of the PV-signature.(1)
Uv checks whether the equation e(PρR,h1(R))=e(Ys,T)h2(m,R,T) holds.(2)
If the equation holds,Uv confirms the PV-signature is valid; otherwise, Uv confirms that the PV-signature is not valid.After the modification, the adversaryA could generate a random number ρ∈Zq and compute R=YsP-ρ, T=h1(R)h2(m,R)-1mod⁡q. However, the equation e(PρR,h1(R))=e(Ys,T)h2(m,R,T) never holds since the adversary cannot use h2(m,R)-1mod⁡q to remove the function h2(m,R,T)-1mod⁡q. Then, the modified scheme is secure against the attack described in Section 3.1.


### 4.2. Countermeasure for Wu and Lin’s UDVS Scheme

From the details of Wu and Lin’s UDVS scheme, we know that the valueT has no relation to the value of W. Then the adversary could choose the value T freely to remove the relation between R and W. To withstand the attack described in Section 3.2, we just need to modify Wu and Lin’s UDVS scheme slightly.DV-Signature-Generation. Upon receiving a message m and the designated verifier Uv’s public key Yv, the signer Us runs the following steps to generate a DV-signature Ω.(1)
Us chooses a random number r∈Zq and computes R=Pr, T=h1(R)xs, ρ=h2(m,R,T)xs2-rmod⁡q, and W=Yvρ.(2)
Us outputs Ω=(R,T,W) as the DV-signature of the message m.DV-Signature-Verification. Upon receiving a message m, the DV-signature Ω, and the signer’s public key Ys, the designated verifier Uv runs the following steps to verify the validity of the DV-signature.(1)
Uv checks whether the equation e(Wxv-1R,h1(R))=e(Ys,T)h2(m,R,T) holds.(2)
If the equation holds,Uv confirms the DV-signature is valid; otherwise, Uv confirms that the PV-signature is not valid.After the modification, the adversaryA could generate a random number ρ∈Zq and compute R=YsP-ρ, T=h1(R)h2(m,R)-1mod⁡q and W=Yvρ. However, the equation e(Wxv-1R,h1(R))=e(Ys,T)h2(m,R,T) never holds since the adversary cannot use h2(m,R)-1mod⁡q to remove the function h2(m,R,T)-1mod⁡q. Then, the modified scheme is secure against the attack described in Section 3.2.


## 4.1. Countermeasure for Wu and Lin’s PS Scheme

From the details of Wu and Lin’s PS scheme, we know that the valueT has no relation with the value of ρ. Then the adversary could choose the value T freely to remove the relation between R and ρ. To withstand the attack described in Section 3.1, we just need to modify Wu and Lin’s PS scheme slightly.DV-Signature-Generation. Upon receiving a message m, the signer Us runs the following steps to generate a PV-signature Ω.(1)
Us chooses a random number r∈Zq and computes R=Pr, T=h1(R)xs, and ρ=h2(m,R,T)xs2-rmod⁡q.(2)
Us outputs Ω=(R,T,ρ) as the PV-signature of the message m.DV-Signature-Verification. Upon receiving a message m, the PV-signature Ω, and the signer’s public key Ys, the verifier Uv runs the following steps to verify the validity of the PV-signature.(1)
Uv checks whether the equation e(PρR,h1(R))=e(Ys,T)h2(m,R,T) holds.(2)
If the equation holds,Uv confirms the PV-signature is valid; otherwise, Uv confirms that the PV-signature is not valid.After the modification, the adversaryA could generate a random number ρ∈Zq and compute R=YsP-ρ, T=h1(R)h2(m,R)-1mod⁡q. However, the equation e(PρR,h1(R))=e(Ys,T)h2(m,R,T) never holds since the adversary cannot use h2(m,R)-1mod⁡q to remove the function h2(m,R,T)-1mod⁡q. Then, the modified scheme is secure against the attack described in Section 3.1.


## 4.2. Countermeasure for Wu and Lin’s UDVS Scheme

From the details of Wu and Lin’s UDVS scheme, we know that the valueT has no relation to the value of W. Then the adversary could choose the value T freely to remove the relation between R and W. To withstand the attack described in Section 3.2, we just need to modify Wu and Lin’s UDVS scheme slightly.DV-Signature-Generation. Upon receiving a message m and the designated verifier Uv’s public key Yv, the signer Us runs the following steps to generate a DV-signature Ω.(1)
Us chooses a random number r∈Zq and computes R=Pr, T=h1(R)xs, ρ=h2(m,R,T)xs2-rmod⁡q, and W=Yvρ.(2)
Us outputs Ω=(R,T,W) as the DV-signature of the message m.DV-Signature-Verification. Upon receiving a message m, the DV-signature Ω, and the signer’s public key Ys, the designated verifier Uv runs the following steps to verify the validity of the DV-signature.(1)
Uv checks whether the equation e(Wxv-1R,h1(R))=e(Ys,T)h2(m,R,T) holds.(2)
If the equation holds,Uv confirms the DV-signature is valid; otherwise, Uv confirms that the PV-signature is not valid.After the modification, the adversaryA could generate a random number ρ∈Zq and compute R=YsP-ρ, T=h1(R)h2(m,R)-1mod⁡q and W=Yvρ. However, the equation e(Wxv-1R,h1(R))=e(Ys,T)h2(m,R,T) never holds since the adversary cannot use h2(m,R)-1mod⁡q to remove the function h2(m,R,T)-1mod⁡q. Then, the modified scheme is secure against the attack described in Section 3.2.


## 5. Conclusion

Recently, Wu and Lin proposed a PS scheme using the bilinear square Diffie-Hellman problem and extended it to a UDVS scheme. They also demonstrated that their scheme is provably secure in the random oracle. Through concrete attacks, we demonstrate that neither of their schemes is unforgeable against common adversary. To improve security, we also propose efficient countermeasures to withstand the proposed attacks.



---

*Source: 345686-2014-06-12.xml*