# On Delegatability of Some Strong Designated Verifier Signature Schemes

Authors: Baoyuan Kang; Hao Xu; Yongzheng Niu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

A strong designated verifier signature scheme makes it possible for a signer to convince a designated verifier that she has signed a message in such a way that the designated verifier cannot transfer the signature to a third party, and no third party can even verify the validity of a designated verifier signature. In 2005, Lipmaa, Wang, and Bao identified a new essential security property, non delegatability, of designated verifier signature schemes. Briefly, in a non delegatability designated verifier signature scheme, neither a signer nor a designated verifier can delegate the signing rights to any third party without revealing their secret keys. However, this paper shows that four recently proposed strong designated verifier signature schemes are delegatable. These schemes do not satisfy non delegatability secure requirement of strong designated verifier signature schemes.


---

## Body

## 1. Introduction

Ensuring the integrity and the authenticity of the origin of a message is one of the goals of cryptography, and standard authentication tools are digital signatures. Digital signature schemes allow a receiver of a signature, Bob, to verify that the signature received is indeed sent by the sender, Alice. And Bob can convince any third party that Alice has indeed sent him the message. This is also referred to as nonrepudiation in the sense that Alice cannot deny the fact that she has sent a signature to Bob. Nonrepudiation is a very useful property for the authenticity of the origin of a message when dispute could occur at some later time. On the other hand, in numerous applications such as tender, electronic voting, or electronic auctions, the public verification and nonrepudiation properties of a signature are not desired. Let us consider the following example [1].Suppose that a public institution initiates a call for tenders, asking some companies to propose their prices for a set of instruments and tasks to be accomplished. The institution may require the companies to sign their offers in order to make sure that they are actually authentic and originated from whom they claim to be. This is a valid requirement, but no company involved in this process desires its offer to affect other tenders’ decisions. That is, a company may capture a competitor’s signed offer on the transmission line (to the institution) and prepares its offer consequently in order to increase its chance to be selected by the institution. The here raised question is about the conflict between authenticity and privacy.To satisfy the above requirements in signature schemes, Jakobsson et al. [2] firstly proposed the concept of strong designated verifier signatures (SDVS). A SDVS scheme is special type of digital signature which provides message authentication without nonrepudiation. In a SDVS scheme, suppose Alice, the signer, has sent a signature to Bob, the designated verifier. Bob can use his private key to verify the validity of the signature. But Bob cannot prove to a third party that Alice has created the signature. Since Bob can efficiently simulate signatures that are indistinguishable from Alice’s signature. The SDVS fit into various cryptographic applications such as privacy preserving cloud computing [3] and social networks [4]. They also are useful in some new fields, such as cognitive computing [5], where a brainy robot needs to authenticate its owner and keeps no evidences of its owner’s authentication.After Saeednia et al. [1] formalized the notion of SDVS in 2003, many SDVS schemes have been proposed [6–18]. Based on nondelegatability proposed by Lipmaa, Wang, and Bao in 2005, an essential security property of designated verifier signature schemes, Huang et al. [14] proposed a security model for SDVS scheme. The model is stricter than the previous one [11]. All schemes [6–13] are insecure in Huang et al.’s model. In a nondelegatability designated verifier signature scheme, neither a signer nor a designated verifier can delegate the signing rights to any third party without revealing their secret keys. Recently, four strong designated verifier signature schemes are proposed [15–18]. However, in this work, we show that the four schemes are delegatable. So, they are insecure.The remainder of this paper is organized as follows. Some basic concepts are introduced in Section2. In Section 3, we review four designated verifier signature schemes and present delegation attacks on them. Finally, Section 4 concludes the paper.


## 2. Preliminaries

In this section, we briefly review the basic concepts of bilinear pairings and model of strong designated verifier signatures.


### 2.1. Basic Concepts on Bilinear Pairings

LetG
1 be a cyclic additive group and G
2 a cyclic multiplicative group of the same order q. An admissible bilinear pairing is a map e
:
G
1
×
G
1
→
G
2, which satisfies the following properties.(i)
Bilinearity. One has   e
(
a
P
,
b
Q
)
=
e
(
P
,
Q
)
a
b for all P
,
Q
∈
G
1, a
,
b
∈
Z
q
*. This can also be stated as e
(
P
+
Q
,
R
)
=
e
(
P
,
R
)
e
(
Q
,
R
) and e
(
P
,
Q
+
R
)
=
e
(
P
,
Q
)
e
(
P
,
R
) for all P
,
Q
,
R
∈
G
1.
(ii)
Nondegeneracy. There exists P
,
Q
∈
G
1, such that e
(
P
,
Q
)
≠
1.
(iii)
Computability. There is an efficient algorithm to compute e
(
P
,
Q
) for all P
,
Q
∈
G
1.


### 2.2. Complexity Assumptions

Definition 1 (bilinear Diffie-Hellman (BDH) problem).
Given randomly chosenP
∈
G
1, as well as a
P
,
b
P
,
c
P (for unknown randomly chosen a
,
b
,
c
∈
Z
q
*), compute e
(
P
,
P
)
a
b
c.Definition 2 (BDH assumption).
The BDH assumption(
t
,
ε
) holds in the bilinear setting (
G
,
G
2
,
e
,
q
,
P
), if there is no probabilistic polynomial-time adversary A that runs in time at most t and Pr
[
a
,
b
,
c
∈
Z
q
*
:
e
(
P
,
P
)
a
b
c
←
A
(
a
P
,
b
P
,
c
P
)
]
>
ε.


### 2.3. Model of Strong Designated Verifier Signature Scheme

Here, we introduce the concept of strong designated verifier signature in identity-based setting. An identity-based strong designated verifier signature scheme (IDSDVS) consists of five algorithms (that may be randomized) as follows.(i)
Parameter Generation (Setup) is an algorithm that accepts a security parameter k and outputs a string consisting of system parameters and master key.
(ii)
Key Extraction (Extract) is an algorithm that accepts system parameters and master key and an arbitrary string ID
∈
{
0,1
}
* outputs a private key U
ID. Here ID is the user's identity and will be used as the user's public key.
(iii)
Signature Generation (Sign) is an algorithm that accepts system parameters, the signer's private key U
ID, a message m, and the designated verifier's public key ID
V and outputs the signature δ on the message m.
(iv)
Designated Verification (Ver) is an algorithm that accepts system parameters, the signer's identity ID
S, a message m, the designated verifier's public key ID
V, and private key u
V and the signature δ on the message m outputs either accept or reject as the verification decision.
(v)
Transcript Simulation is the algorithm that the designated verifier runs to produce identically distributed transcripts which are indistinguishable from the signature produced by the signer.The IDSDVS scheme should satisfy the following security properties.(i)
Correctness. A properly formed IDSDVS must be accepted by the verifying algorithm.
(ii)
Nontransferability. We require an IDSDVS scheme to be nontransferable. The nontransferability property is ensured by a transcript simulation algorithm that can be performed by all designated verifiers to produce an indistinguishable signature from the one that should be produced by the signature holder.
(iii)
Unforgeability.It is computationally infeasible to construct a valid IDSDVS signature without the knowledge of the private key of either the signer or the designated verifier.
(iv)
Nondelegatability. It requires an adversary to “know” a secret key of a signer or a designated verifier if the adversary can produce a valid signature on a message.


## 2.1. Basic Concepts on Bilinear Pairings

LetG
1 be a cyclic additive group and G
2 a cyclic multiplicative group of the same order q. An admissible bilinear pairing is a map e
:
G
1
×
G
1
→
G
2, which satisfies the following properties.(i)
Bilinearity. One has   e
(
a
P
,
b
Q
)
=
e
(
P
,
Q
)
a
b for all P
,
Q
∈
G
1, a
,
b
∈
Z
q
*. This can also be stated as e
(
P
+
Q
,
R
)
=
e
(
P
,
R
)
e
(
Q
,
R
) and e
(
P
,
Q
+
R
)
=
e
(
P
,
Q
)
e
(
P
,
R
) for all P
,
Q
,
R
∈
G
1.
(ii)
Nondegeneracy. There exists P
,
Q
∈
G
1, such that e
(
P
,
Q
)
≠
1.
(iii)
Computability. There is an efficient algorithm to compute e
(
P
,
Q
) for all P
,
Q
∈
G
1.


## 2.2. Complexity Assumptions

Definition 1 (bilinear Diffie-Hellman (BDH) problem).
Given randomly chosenP
∈
G
1, as well as a
P
,
b
P
,
c
P (for unknown randomly chosen a
,
b
,
c
∈
Z
q
*), compute e
(
P
,
P
)
a
b
c.Definition 2 (BDH assumption).
The BDH assumption(
t
,
ε
) holds in the bilinear setting (
G
,
G
2
,
e
,
q
,
P
), if there is no probabilistic polynomial-time adversary A that runs in time at most t and Pr
[
a
,
b
,
c
∈
Z
q
*
:
e
(
P
,
P
)
a
b
c
←
A
(
a
P
,
b
P
,
c
P
)
]
>
ε.


## 2.3. Model of Strong Designated Verifier Signature Scheme

Here, we introduce the concept of strong designated verifier signature in identity-based setting. An identity-based strong designated verifier signature scheme (IDSDVS) consists of five algorithms (that may be randomized) as follows.(i)
Parameter Generation (Setup) is an algorithm that accepts a security parameter k and outputs a string consisting of system parameters and master key.
(ii)
Key Extraction (Extract) is an algorithm that accepts system parameters and master key and an arbitrary string ID
∈
{
0,1
}
* outputs a private key U
ID. Here ID is the user's identity and will be used as the user's public key.
(iii)
Signature Generation (Sign) is an algorithm that accepts system parameters, the signer's private key U
ID, a message m, and the designated verifier's public key ID
V and outputs the signature δ on the message m.
(iv)
Designated Verification (Ver) is an algorithm that accepts system parameters, the signer's identity ID
S, a message m, the designated verifier's public key ID
V, and private key u
V and the signature δ on the message m outputs either accept or reject as the verification decision.
(v)
Transcript Simulation is the algorithm that the designated verifier runs to produce identically distributed transcripts which are indistinguishable from the signature produced by the signer.The IDSDVS scheme should satisfy the following security properties.(i)
Correctness. A properly formed IDSDVS must be accepted by the verifying algorithm.
(ii)
Nontransferability. We require an IDSDVS scheme to be nontransferable. The nontransferability property is ensured by a transcript simulation algorithm that can be performed by all designated verifiers to produce an indistinguishable signature from the one that should be produced by the signature holder.
(iii)
Unforgeability.It is computationally infeasible to construct a valid IDSDVS signature without the knowledge of the private key of either the signer or the designated verifier.
(iv)
Nondelegatability. It requires an adversary to “know” a secret key of a signer or a designated verifier if the adversary can produce a valid signature on a message.


## 3. Four Designated Verifier Signature Schemes and Attacks on Them

### 3.1. Lee et al.’s Scheme

Lee et al.’s scheme [16] can be described as follows.Letp and q be two large primes such that q
∣
p
-
1 and g an element of Z
p
* of order q. The message to be signed is m
∈
Z
p. Let signer Alice’s public key be y
A
=
g
x
A
mod
⁡
⁡
p, where x
A
∈
Z
q
* is her secret key, and designated verifier Bob’s public key be y
B
=
g
x
B
mod
⁡
⁡
p, where x
B
∈
Z
q
* is his secret key. One-way hash function H outputs values in Z
q. Suppose that Alice wants to send a strong designated verifier signature (
t
,
c
,
r
,
s
) with a message m to Bob.(i)
Signature generation. Alice chooses two random numbers k
1 from Z
q
* and k
2 from Z
q and generates a signature (
t
,
c
,
r
,
s
) as follows:
(1)
t
=
g
k
1
mod
⁡
⁡
p
,
c
=
m
y
B
k
2
mod
⁡
⁡
p
,
r
=
H
(
m
,
g
k
2
)
,
s
=
k
1
-
1
(
x
A
r
-
k
2
)
mod
⁡
⁡
q
.
(ii)
Message Recovery and Verification. Upon receiving (
t
,
c
,
r
,
s
) from Alice, Bob recovers the message and verifies the signature by computing
(2)
m
=
c
(
t
s
y
A
-
r
)
x
B
mod
⁡
⁡
p
,
r
=
?
H
(
m
,
y
A
r
t
-
s
)
.
(iii)
Transcript Simulation. Bob can simulate the designated verifier signature (
t
,
c
,
r
,
s
) of m. Bob selects two random values w
1
∈
Z
q
* and w
2
∈
Z
q. Then he computes (
t
,
c
,
r
,
s
) as follows:
(3)
t
=
y
A
w
1
-
1
mod
⁡
⁡
p
,
c
=
m
y
A
x
B
w
1
-
1
w
2
mod
⁡
⁡
p
,
r
=
H
(
m
,
y
A
w
1
-
1
w
2
)
s
=
w
1
r
-
w
2
mod
⁡
⁡
q
.Attack on Lee et al.’s Scheme. Assume that the signer discloses D
=
y
B
x
A or the designated verifier discloses y
A
x
B
(
=
y
B
x
A
) to any third party T. Given any message m
*, T selects two random values d
1
∈
Z
q
* and d
2
∈
Z
q. Then he computes (
t
*
,
c
*
,
r
*
,
s
*
) as follows:
(4)
t
*
=
y
A
d
1
-
1
mod
⁡
⁡
p
,
c
*
=
m
*
D
d
1
-
1
d
2
mod
⁡
⁡
p
,
r
*
=
H
(
m
,
y
A
d
1
-
1
d
2
)
,
s
*
=
d
1
r
*
-
d
2
mod
⁡
⁡
q
.
Tgenerates a simulated signature (
t
*
,
c
*
,
r
*
,
s
*
). Bob verifies whether r
*
=
H
(
m
,
y
A
r
*
t
*
-
s
*
) and recovers message m
*
=
c
*
(
t
*
s
*
y
A
-
r
*
)
x
B
mod
⁡
⁡
p. The verification accepts since
(5)
c
*
(
t
*
s
*
y
A
-
r
*
)
x
B
=
m
*
D
d
1
-
1
d
2
(
y
A
d
1
-
1
(
d
1
r
*
-
d
2
)
y
A
-
r
*
)
x
B
=
m
*
D
d
1
-
1
d
2
(
y
A
-
d
1
-
1
d
2
)
x
B
=
m
*
,
H
(
m
*
,
y
A
r
*
t
*
-
s
*
)
=
H
(
m
*
,
y
A
r
*
(
y
A
d
1
-
1
)
-
(
d
1
r
*
-
d
2
)
)
=
H
(
m
*
,
y
A
d
1
-
1
d
2
)
=
r
*
.
Therefore, Lee et al.’s scheme is delegatable.


### 3.2. Yang et al.’s Scheme

Yang et al.’s certificateless strong designated verifier signature scheme [18] consists of the following six algorithms.(i)
Setup. Given a security parameter l, a KGC chooses two groups G
1 and G
2 of the same prime order q
>
2
l and a modified Tate pairing map e: G
1
×
G
1
→
G
2. P is a generator of group G
1; then the KGC selects two distinct cryptographic hash functions  H
1:{
0,1
}
*
→
G
1, H
2:{
0,1
}
*
×
G
1
3
→
Z
q
*, picks a random s
∈
Z
q
* as the master key, computes the system public key P
0
=
s
P, and publishes params
≔
{
l
,
G
1
,
G
2
,
e
,
q
,
P
,
P
0
,
H
1
,
H
2
} but keeps s secret.
(ii)
Partial-Private-Key-Extract. Given an identity ID
i
∈
(
0,1
)
*, i
∈
{
A
,
B
}, this paper assumes that user A is the signer and B is the designated verifier, the KGC computes Q
i
=
H
1
(
ID
i
), d
i
=
s
Q
i, and sends d
i to a user with identity ID
i as his partial private key by a secure channel.
(iii)
User-Key-Extract. On inputs p
a
r
a
m
s and the user’s identity ID
i
(
i
∈
{
A
,
B
}
), the algorithm picks a random x
i
∈
Z
q
* as the user’s secret value and computes p
k
i
=
x
i
P as his public key.
(iv)
CLSDVS-Sign. On inputs p
a
r
a
m
s, signer A’s identity ID
A, his private key pair (
d
A
,
x
A
), and a message m
∈
(
0,1
)
*, the algorithm works as follows.
(1)
Pick a random valuer
∈
Z
q
* and compute U
=
r
P.
(2)
Computeh
=
H
2
(
m
,
U
,
p
k
A
,
x
A
p
k
B
)
∈
Z
q
*.
(3)
ComputeV
=
r
P
0
+
h
d
A and T
=
e
(
V
,
Q
B
).The signature on messagem is σ
=
(
U
,
T
).(v)
CLSDVS-Verify. To verify a signature σ on a message m for an identity ID
A with public key p
k
A, the designated verifier B acts as follows.
(1)
Parseσ
=
(
U
,
T
).
(2)
Computeh
=
H
2
(
m
,
U
,
p
k
A
,
x
B
p
k
A
)
∈
Z
q
*.
(3)
Accept the signature and return 1 if and only if the following equation holds:(6)
T
=
?
e
(
U
+
h
Q
A
,
d
B
)
.
(vi)
CLSDVS-Simulation. The designated verifier B cannot prove to a third party that a signature σ
=
(
U
,
T
) on a message m has been produced by signer A since he can also create an indistinguishable signature σ on m by the following means.
(1)
Pick randomlyr
′
∈
Z
q
*, and compute U
′
=
r
′
P.
(2)
Seth
′
=
H
2
(
m
,
U
′
,
p
k
A
,
x
B
p
k
A
).
(3)
ComputeT
′
=
e
(
U
′
+
h
′
Q
A
,
d
B
).The signature on the messagem is σ
′
=
(
U
′
,
T
′
).Attack on Yang et al.’s Scheme. Since in CLSDVS-Verify algorithm,
(7)
T
=
e
(
U
+
h
Q
A
,
d
B
)
=
e
(
U
,
d
B
)
e
(
Q
A
,
d
B
)
h
.When one third partyW gets (
V
1
,
V
2
)
=
(
x
A
p
k
B
,
e
(
Q
A
,
d
B
)
), W picks a random value r
*
∈
Z
q
*, and computes
(8)
U
*
=
r
*
P
,
h
*
=
H
2
(
m
*
,
U
*
,
p
k
A
,
V
1
)
,
T
*
=
V
2
h
*
e
(
P
0
,
r
*
Q
B
)
.W can obtain a simulated signature σ
*
=
(
U
*
,
T
*
). Because
(9)
h
*
=
H
2
(
m
*
,
U
*
,
p
k
A
,
V
1
)
=
H
2
(
m
*
,
U
*
,
p
k
A
,
x
B
p
k
A
)
,
T
*
=
V
2
h
*
e
(
P
0
,
r
*
Q
B
)
=
e
(
h
*
Q
A
,
d
B
)
e
(
r
*
P
,
d
B
)
=
e
(
h
*
Q
A
+
U
*
,
d
B
)
.
So, σ
*
=
(
U
*
,
T
*
) is a valid signature. Therefore, Lee et al.’s scheme is delegatable.


### 3.3. Lee et al.’s Scheme

Lee et al.’s strong designated verifier signature scheme [15] is as follows.Letp and q be two large primes such that q
∣
p
-
1 and g an element of Z
p
* of order q. Let the signer Alice’s public key be y
A
=
g
x
A
mod
⁡
⁡
p, where x
A
∈
Z
q
* is her secret key, and designated verifier Bob’s public key y
B
=
g
x
B
mod
⁡
⁡
p, where x
B
∈
Z
q
* is his secret key. One-way hash function H outputs values in Z
q. Suppose that Alice wants to send a strong designated verifier signature with a message m to Bob.(i)
Signature Generation. Alice selects a random value k
∈
Z
q
*. She computes r, s, and t as follows:
(10)
r
=
g
k
mod
⁡
p
,
s
=
k
+
x
A
r
mod
⁡
q
,
t
=
H
(
m
,
y
B
s
mod
⁡
p
)
.Then, the signature isσ
=
(
r
,
t
).(ii)
Signature Verification. Upon receiving m and σ, Bob can verify the validity of the signature by checking whether t
=
H
(
m
,
(
r
y
A
r
*
)
x
B
mod
⁡
p
).
(iii)
Signature Simulation. Bob can simulate the transcript σ
′
=
(
r
′
,
t
′
) for the message m by selecting a random number k
′
∈
Z
q
* and compute r
′ and t
′ as follows:
(11)
r
′
=
g
k
′
mod
⁡
p
,
t
′
=
H
(
m
,
(
r
′
y
A
r
′
)
x
B
mod
⁡
p
)
.Attack on Lee et al.’s Scheme. Assume that the signer discloses y
B
x
A or the designated verifier y
A
x
B
(
=
y
B
x
A
) to any third party T. Given any message m
*, T selects a random number k
*
∈
Z
q
* and computes
(12)
r
*
=
g
k
*
t
*
=
H
(
m
*
,
y
B
k
*
(
y
A
x
B
)
r
*
mod
⁡
p
)
.
T generates a simulated signature (
t
*
,
r
*
). Bob verifies whether t
*
=
H
(
m
*
,
(
r
*
y
A
r
*
)
x
B
mod
⁡
p
). The verification accepts since
(13)
H
(
m
*
,
(
r
*
y
A
r
*
)
x
B
mod
⁡
⁡
p
)
=
H
(
m
*
,
(
g
k
*
y
A
r
*
)
x
B
mod
⁡
⁡
p
)
=
H
(
m
*
,
y
B
k
*
(
y
A
x
B
)
r
*
mod
⁡
⁡
p
)
.
Therefore, Lee et al.’s scheme is delegatable.


### 3.4. Ki et al.’s Scheme

Ki et al.’s strong designated verifier signature scheme [17] is as follows.(i)
Setup. Let G be an additive group and G
T a multiplicative group. Let e
:
G
×
G
→
G
T be a symmetric bilinear map, where G and G
T have prime order q. P is a random generator of G. The algorithm selects s
∈
Z
q
* at random and computes P
pub
←
s
P
∈
G. It also selects two collision-resistant cryptographic hash functions,   H
0
:
{
0,1
}
→
G and H
:
{
0,1
}
*
→
{
0,1
}
λ. The algorithm outputs the master secret key, msk
=
s, and its corresponding public parameters, params
=
(
G
,
G
T
,
q
,
e
,
P
,
P
pub
,
H
0
,
H
).
(ii)
Key-Extract. For given identity ID, it computes Q
ID
=
H
0
(
ID
)
∈
G and s
k
ID
←
s
Q
ID.
(iii)
IDSig. For given message m
∈
{
0,1
}
*, verifier’s identity ID
V, and signer’s secret key s
k
I
D
S
=
s
H
0
(
ID
S
), it computes Q
I
D
V
←
H
0
(
ID
V
)
∈
G and T
K
←
e
(
s
k
I
D
S
,
Q
I
D
V
)
∈
G
T. It selects r
∈
Z
q
* and computes θ
←
r
P
∈
G and k
d
←
e
(
r
P
pub
,
Q
I
D
V
). It computes η
←
H
(
k
d
∥
T
K
) and τ
←
H
(
η
∥
θ
∥
m
). The signature on a message is σ
=
(
θ
,
τ
).
(iv)
IDVerify. For a given signature σ
=
(
θ
,
τ
), message m, and verifier’s secret key s
k
I
D
V, it computes Q
I
D
S
←
H
0
(
I
D
S
), T
K
′
←
e
(
Q
I
D
S
,
s
k
I
D
V
), k
D
′
←
e
(
θ
,
s
k
I
D
V
), and η
′
←
H
(
k
D
′
∥
T
K
′
). It tests if H
(
η
′
∥
θ
∥
m
)
?
=
τ holds. If the equality holds, then it outputs valid; otherwise, it outputs invalid.Attack on Ki et al.’s Scheme. Obviously any third party T can generate valid signature when they get T
K
=
e
(
s
k
ID
S
,
Q
ID
V
). So, Ki et al.’s scheme is delegatable.


## 3.1. Lee et al.’s Scheme

Lee et al.’s scheme [16] can be described as follows.Letp and q be two large primes such that q
∣
p
-
1 and g an element of Z
p
* of order q. The message to be signed is m
∈
Z
p. Let signer Alice’s public key be y
A
=
g
x
A
mod
⁡
⁡
p, where x
A
∈
Z
q
* is her secret key, and designated verifier Bob’s public key be y
B
=
g
x
B
mod
⁡
⁡
p, where x
B
∈
Z
q
* is his secret key. One-way hash function H outputs values in Z
q. Suppose that Alice wants to send a strong designated verifier signature (
t
,
c
,
r
,
s
) with a message m to Bob.(i)
Signature generation. Alice chooses two random numbers k
1 from Z
q
* and k
2 from Z
q and generates a signature (
t
,
c
,
r
,
s
) as follows:
(1)
t
=
g
k
1
mod
⁡
⁡
p
,
c
=
m
y
B
k
2
mod
⁡
⁡
p
,
r
=
H
(
m
,
g
k
2
)
,
s
=
k
1
-
1
(
x
A
r
-
k
2
)
mod
⁡
⁡
q
.
(ii)
Message Recovery and Verification. Upon receiving (
t
,
c
,
r
,
s
) from Alice, Bob recovers the message and verifies the signature by computing
(2)
m
=
c
(
t
s
y
A
-
r
)
x
B
mod
⁡
⁡
p
,
r
=
?
H
(
m
,
y
A
r
t
-
s
)
.
(iii)
Transcript Simulation. Bob can simulate the designated verifier signature (
t
,
c
,
r
,
s
) of m. Bob selects two random values w
1
∈
Z
q
* and w
2
∈
Z
q. Then he computes (
t
,
c
,
r
,
s
) as follows:
(3)
t
=
y
A
w
1
-
1
mod
⁡
⁡
p
,
c
=
m
y
A
x
B
w
1
-
1
w
2
mod
⁡
⁡
p
,
r
=
H
(
m
,
y
A
w
1
-
1
w
2
)
s
=
w
1
r
-
w
2
mod
⁡
⁡
q
.Attack on Lee et al.’s Scheme. Assume that the signer discloses D
=
y
B
x
A or the designated verifier discloses y
A
x
B
(
=
y
B
x
A
) to any third party T. Given any message m
*, T selects two random values d
1
∈
Z
q
* and d
2
∈
Z
q. Then he computes (
t
*
,
c
*
,
r
*
,
s
*
) as follows:
(4)
t
*
=
y
A
d
1
-
1
mod
⁡
⁡
p
,
c
*
=
m
*
D
d
1
-
1
d
2
mod
⁡
⁡
p
,
r
*
=
H
(
m
,
y
A
d
1
-
1
d
2
)
,
s
*
=
d
1
r
*
-
d
2
mod
⁡
⁡
q
.
Tgenerates a simulated signature (
t
*
,
c
*
,
r
*
,
s
*
). Bob verifies whether r
*
=
H
(
m
,
y
A
r
*
t
*
-
s
*
) and recovers message m
*
=
c
*
(
t
*
s
*
y
A
-
r
*
)
x
B
mod
⁡
⁡
p. The verification accepts since
(5)
c
*
(
t
*
s
*
y
A
-
r
*
)
x
B
=
m
*
D
d
1
-
1
d
2
(
y
A
d
1
-
1
(
d
1
r
*
-
d
2
)
y
A
-
r
*
)
x
B
=
m
*
D
d
1
-
1
d
2
(
y
A
-
d
1
-
1
d
2
)
x
B
=
m
*
,
H
(
m
*
,
y
A
r
*
t
*
-
s
*
)
=
H
(
m
*
,
y
A
r
*
(
y
A
d
1
-
1
)
-
(
d
1
r
*
-
d
2
)
)
=
H
(
m
*
,
y
A
d
1
-
1
d
2
)
=
r
*
.
Therefore, Lee et al.’s scheme is delegatable.


## 3.2. Yang et al.’s Scheme

Yang et al.’s certificateless strong designated verifier signature scheme [18] consists of the following six algorithms.(i)
Setup. Given a security parameter l, a KGC chooses two groups G
1 and G
2 of the same prime order q
>
2
l and a modified Tate pairing map e: G
1
×
G
1
→
G
2. P is a generator of group G
1; then the KGC selects two distinct cryptographic hash functions  H
1:{
0,1
}
*
→
G
1, H
2:{
0,1
}
*
×
G
1
3
→
Z
q
*, picks a random s
∈
Z
q
* as the master key, computes the system public key P
0
=
s
P, and publishes params
≔
{
l
,
G
1
,
G
2
,
e
,
q
,
P
,
P
0
,
H
1
,
H
2
} but keeps s secret.
(ii)
Partial-Private-Key-Extract. Given an identity ID
i
∈
(
0,1
)
*, i
∈
{
A
,
B
}, this paper assumes that user A is the signer and B is the designated verifier, the KGC computes Q
i
=
H
1
(
ID
i
), d
i
=
s
Q
i, and sends d
i to a user with identity ID
i as his partial private key by a secure channel.
(iii)
User-Key-Extract. On inputs p
a
r
a
m
s and the user’s identity ID
i
(
i
∈
{
A
,
B
}
), the algorithm picks a random x
i
∈
Z
q
* as the user’s secret value and computes p
k
i
=
x
i
P as his public key.
(iv)
CLSDVS-Sign. On inputs p
a
r
a
m
s, signer A’s identity ID
A, his private key pair (
d
A
,
x
A
), and a message m
∈
(
0,1
)
*, the algorithm works as follows.
(1)
Pick a random valuer
∈
Z
q
* and compute U
=
r
P.
(2)
Computeh
=
H
2
(
m
,
U
,
p
k
A
,
x
A
p
k
B
)
∈
Z
q
*.
(3)
ComputeV
=
r
P
0
+
h
d
A and T
=
e
(
V
,
Q
B
).The signature on messagem is σ
=
(
U
,
T
).(v)
CLSDVS-Verify. To verify a signature σ on a message m for an identity ID
A with public key p
k
A, the designated verifier B acts as follows.
(1)
Parseσ
=
(
U
,
T
).
(2)
Computeh
=
H
2
(
m
,
U
,
p
k
A
,
x
B
p
k
A
)
∈
Z
q
*.
(3)
Accept the signature and return 1 if and only if the following equation holds:(6)
T
=
?
e
(
U
+
h
Q
A
,
d
B
)
.
(vi)
CLSDVS-Simulation. The designated verifier B cannot prove to a third party that a signature σ
=
(
U
,
T
) on a message m has been produced by signer A since he can also create an indistinguishable signature σ on m by the following means.
(1)
Pick randomlyr
′
∈
Z
q
*, and compute U
′
=
r
′
P.
(2)
Seth
′
=
H
2
(
m
,
U
′
,
p
k
A
,
x
B
p
k
A
).
(3)
ComputeT
′
=
e
(
U
′
+
h
′
Q
A
,
d
B
).The signature on the messagem is σ
′
=
(
U
′
,
T
′
).Attack on Yang et al.’s Scheme. Since in CLSDVS-Verify algorithm,
(7)
T
=
e
(
U
+
h
Q
A
,
d
B
)
=
e
(
U
,
d
B
)
e
(
Q
A
,
d
B
)
h
.When one third partyW gets (
V
1
,
V
2
)
=
(
x
A
p
k
B
,
e
(
Q
A
,
d
B
)
), W picks a random value r
*
∈
Z
q
*, and computes
(8)
U
*
=
r
*
P
,
h
*
=
H
2
(
m
*
,
U
*
,
p
k
A
,
V
1
)
,
T
*
=
V
2
h
*
e
(
P
0
,
r
*
Q
B
)
.W can obtain a simulated signature σ
*
=
(
U
*
,
T
*
). Because
(9)
h
*
=
H
2
(
m
*
,
U
*
,
p
k
A
,
V
1
)
=
H
2
(
m
*
,
U
*
,
p
k
A
,
x
B
p
k
A
)
,
T
*
=
V
2
h
*
e
(
P
0
,
r
*
Q
B
)
=
e
(
h
*
Q
A
,
d
B
)
e
(
r
*
P
,
d
B
)
=
e
(
h
*
Q
A
+
U
*
,
d
B
)
.
So, σ
*
=
(
U
*
,
T
*
) is a valid signature. Therefore, Lee et al.’s scheme is delegatable.


## 3.3. Lee et al.’s Scheme

Lee et al.’s strong designated verifier signature scheme [15] is as follows.Letp and q be two large primes such that q
∣
p
-
1 and g an element of Z
p
* of order q. Let the signer Alice’s public key be y
A
=
g
x
A
mod
⁡
⁡
p, where x
A
∈
Z
q
* is her secret key, and designated verifier Bob’s public key y
B
=
g
x
B
mod
⁡
⁡
p, where x
B
∈
Z
q
* is his secret key. One-way hash function H outputs values in Z
q. Suppose that Alice wants to send a strong designated verifier signature with a message m to Bob.(i)
Signature Generation. Alice selects a random value k
∈
Z
q
*. She computes r, s, and t as follows:
(10)
r
=
g
k
mod
⁡
p
,
s
=
k
+
x
A
r
mod
⁡
q
,
t
=
H
(
m
,
y
B
s
mod
⁡
p
)
.Then, the signature isσ
=
(
r
,
t
).(ii)
Signature Verification. Upon receiving m and σ, Bob can verify the validity of the signature by checking whether t
=
H
(
m
,
(
r
y
A
r
*
)
x
B
mod
⁡
p
).
(iii)
Signature Simulation. Bob can simulate the transcript σ
′
=
(
r
′
,
t
′
) for the message m by selecting a random number k
′
∈
Z
q
* and compute r
′ and t
′ as follows:
(11)
r
′
=
g
k
′
mod
⁡
p
,
t
′
=
H
(
m
,
(
r
′
y
A
r
′
)
x
B
mod
⁡
p
)
.Attack on Lee et al.’s Scheme. Assume that the signer discloses y
B
x
A or the designated verifier y
A
x
B
(
=
y
B
x
A
) to any third party T. Given any message m
*, T selects a random number k
*
∈
Z
q
* and computes
(12)
r
*
=
g
k
*
t
*
=
H
(
m
*
,
y
B
k
*
(
y
A
x
B
)
r
*
mod
⁡
p
)
.
T generates a simulated signature (
t
*
,
r
*
). Bob verifies whether t
*
=
H
(
m
*
,
(
r
*
y
A
r
*
)
x
B
mod
⁡
p
). The verification accepts since
(13)
H
(
m
*
,
(
r
*
y
A
r
*
)
x
B
mod
⁡
⁡
p
)
=
H
(
m
*
,
(
g
k
*
y
A
r
*
)
x
B
mod
⁡
⁡
p
)
=
H
(
m
*
,
y
B
k
*
(
y
A
x
B
)
r
*
mod
⁡
⁡
p
)
.
Therefore, Lee et al.’s scheme is delegatable.


## 3.4. Ki et al.’s Scheme

Ki et al.’s strong designated verifier signature scheme [17] is as follows.(i)
Setup. Let G be an additive group and G
T a multiplicative group. Let e
:
G
×
G
→
G
T be a symmetric bilinear map, where G and G
T have prime order q. P is a random generator of G. The algorithm selects s
∈
Z
q
* at random and computes P
pub
←
s
P
∈
G. It also selects two collision-resistant cryptographic hash functions,   H
0
:
{
0,1
}
→
G and H
:
{
0,1
}
*
→
{
0,1
}
λ. The algorithm outputs the master secret key, msk
=
s, and its corresponding public parameters, params
=
(
G
,
G
T
,
q
,
e
,
P
,
P
pub
,
H
0
,
H
).
(ii)
Key-Extract. For given identity ID, it computes Q
ID
=
H
0
(
ID
)
∈
G and s
k
ID
←
s
Q
ID.
(iii)
IDSig. For given message m
∈
{
0,1
}
*, verifier’s identity ID
V, and signer’s secret key s
k
I
D
S
=
s
H
0
(
ID
S
), it computes Q
I
D
V
←
H
0
(
ID
V
)
∈
G and T
K
←
e
(
s
k
I
D
S
,
Q
I
D
V
)
∈
G
T. It selects r
∈
Z
q
* and computes θ
←
r
P
∈
G and k
d
←
e
(
r
P
pub
,
Q
I
D
V
). It computes η
←
H
(
k
d
∥
T
K
) and τ
←
H
(
η
∥
θ
∥
m
). The signature on a message is σ
=
(
θ
,
τ
).
(iv)
IDVerify. For a given signature σ
=
(
θ
,
τ
), message m, and verifier’s secret key s
k
I
D
V, it computes Q
I
D
S
←
H
0
(
I
D
S
), T
K
′
←
e
(
Q
I
D
S
,
s
k
I
D
V
), k
D
′
←
e
(
θ
,
s
k
I
D
V
), and η
′
←
H
(
k
D
′
∥
T
K
′
). It tests if H
(
η
′
∥
θ
∥
m
)
?
=
τ holds. If the equality holds, then it outputs valid; otherwise, it outputs invalid.Attack on Ki et al.’s Scheme. Obviously any third party T can generate valid signature when they get T
K
=
e
(
s
k
ID
S
,
Q
ID
V
). So, Ki et al.’s scheme is delegatable.


## 4. Conclusion

Strong designated verifier signatures provide authentication of a message, without, however, having the nonrepudiation property of traditional signatures. They convince one and only one specified recipient that they are valid, but unlike standard digital signature, nobody else can be convinced about their validity or invalidity. The reason is that the designated verifier in these schemes is able to create a signature intended to himself, that is, indistinguishable from a “real” signature. Strong designated verifier signatures fit into various cryptographic applications where privacy preservation is needed. Recently, four strong designated verifier signature schemes are proposed. However, in this work, we show that the four schemes are delegatable. That is to say, in their scheme the signer or the designated verifier can delegate the signing right to any third party by releasing a piece of information related to but different from their secret keys. This enables a third party to simulate the signer's signatures. So, these schemes do not satisfy nondelegatability secure requirement of strong designated verifier signature scheme.



---

*Source: 761487-2014-04-01.xml*