J. Software Engineering & Applications, 2009, 2: 267-275
doi:10.4236/jsea.2009.24034 Published Online November 2009 (http://www.SciRP.org/journal/jsea)
267
Secure Chained Threshold Proxy Signature
without and with Supervision*
Zoe L. JIANG, S. M. YIU, Y. DONG, L. C. K. HUI, S. H. Y. WONG
Department of Computer Science, The University of Hong Kong, Hong Kong, China.
Received June 4th, 2009; revised July 15th, 2009; accepted July 24th, 2009.
ABSTRACT
Threshold Proxy Signature (TPS) scheme facilitates a manager to delegate his signing capability to a group of n2 sub-
ordinates without revealing his own private key, such that a subgroup of at least t2
≤ n
2 subordinates is required to
generate a proxy signature. In reality, the situation can be more complicated. First of all, the subgroup may further
delegate their proxy signing capabilities to another group of n3 subordinates such that at least another subgroup of at
least t3 ≤ n3 subordinates are of the proxy signing capabilities (in the form of a chain). t2 can be unequal to t3 depending
on the concrete requirement. This is a group-to-group delegation problem. In addition, a supervising agent (SA) may be
introduced in the above chain to supervise the subordinates, such that proxy signing can only be successfully executed
with SA’s agreement. This is a delegation with supervision problem in the threshold delegation chain described above.
These two extensions of delegation problems are not solved yet. This paper designs two provably secure cryptographic
schemes Chained Threshold Proxy Signature (CTPS) scheme and Chained Threshold Proxy Signature with Supervision
(CTPSwS) scheme to solve these two delegation problems.
Keywords: Delegation, Threshold Proxy Signature, Chained Threshold Proxy Signature with Supervision
1. Introduction
1.1 Motivation
It is a common practice for a manager to delegate his
signing right to a group of n subordinates when he is on
leave so that a subgroup of at least t ≤ n of them can co-
operate to sign a document on behalf of the manager.
This is a threshold delegation problem, and can be solved
by Threshold Proxy Signature (TPS) [2] scheme. In real-
ity, the delegation may involve more than one level (in
the form of a chain). Consider the following scenario.
There is an email sent by the manager of software de-
velopment department in corporation A, Simon, to the
manager of the same department in corporation B, Sam.
Since Sam is too busy to check every single detail of the
data part before he replies with his signature, and the data
are so important that he cannot rely on any single one of
his three vice managers (his subordinates), he forwards
this email to all of them. Further any two of them, as a
subgroup, may forward this email to their employees
checking the data part. As a result, to answer this email
to Simon, it is desirable for a subgroup of the employees
to cooperate on behalf of Sam. How the any two of the
vice managers pass their proxy signing capabilities to
their employees is referred to group-to-group delegation
problem. In a more cautious situation, the contract part
needs to be authorized by the manager of the software
maintenance department in corporation B, Steven. In this
case, besides delegation, Sam is also required to appoint
Steven as his supervising agent (SA) such that only when
Steven agrees to the contract part, the employees can
compute a proxy signature on behalf of Sam. How Sam
appoints Steven as an SA is referred to delegation with
supervision problem in threshold delegation chain. In this
paper, we propose two schemes, Chained Threshold
Proxy Signature (CTPS) scheme and Chained Threshold
Proxy Signature with Supervision (CTPSwS) scheme, to
solve these two delegation problems.
1.2 Related work
Mambo et al. [3] introduced the first efficient proxy sig-
nature in 1996, where it allows a user to delegate his
signing power to a designated signer, a proxy signer. It is
widely applicable in all kinds of known standard signa-
ture schemes such as El Gamal scheme [4], Okamoto
scheme [5] and Fiat-Shamir scheme [6]. In 1997, Kim et
al. [2] proposed proxy signature for partial delegation
with warrant combining the benefit of Mambo’s partial
delegation and Neuman’s [7] delegation by warrant/certi-
*The preliminary work has been published in 2008 International Con-
ference on Computer Science and Software Engineering [1].

Secure Chained Threshold Proxy Signature without and with Supervision 268
ficate. They also extended it to a (t, n) Threshold Proxy
Signature (TPS) such that any t ≤ n proxy signers using
their proxy secret key shares can cooperate to generate a
proxy signature on behalf of an original signer, but less
than t can not, by deploying Ceredo’s Schnorr type
threshold digital signature scheme [8].
Lui et al. [9] proposed a chained delegation scheme
with supervision scheme, in which the original signer
sends, in ahead of time, his permission information about
the proxy signer to a supervising agent (SA) who he
trusts. Then the proxy signer can only generate a valid
proxy signature under SA’s supervision even when the
original signer is not available. This delegation can be
executed in multiple levels. However, on one hand, the
scheme does not consider the threshold problem. On the
other hand, the scheme sacrificed both the original signer
and the supervising agent’s undeniabilities due to the
advantage the authors presented that there is no need for
the verifier to be aware of whether supervision is per-
formed or not. In many cases, this is unacceptable from
the security point of view.
Boldyreva [10] defined a formal proof model for the
security of proxy signature schemes, which enables the
cryptographic analysis of such schemes, instead of just
presenting attacks that fail. Then they proved the security
of Triple Schnorr Proxy Signature scheme, a variant of
Kim at al.’s proxy signature scheme, preserving its
efficiency, in the random oracle model assuming the
hardness of computation of discrete logarithm.
1.3 Our Contribution
Firstly, in this paper we propose Chained Threshold
Proxy Signature (CTPS) scheme to solve the
group-to-group delegation problem. Although, Threshold
Proxy Signature (TPS) scheme [2] and Triple Schnorr
Signature scheme [10] are two important components to
design our scheme, we need to consider how to distribute
the proxy shares from a subgroup of vice managers to
another subgroup of employees in a group-to-group
manner. Therefore, we deploy Herzberg et al.’s [11]
proactive secret sharing idea into our scheme. Proactive
secret sharing is proposed to periodically renew the
shares without changing the secret, in such a way that
any information learnt by the adversary about individual
shares becomes obsolete after the shares are renewed.
But in our scheme, the renewed shares should be se-
curely passed to employees by each vice manager while
old ones are kept secret by the vice managers themselves.
To solve the delegation with supervision problem in
threshold delegation chain, we adapt Lui et al’s supervi-
sion idea in delegation chain (no threshold) into CTPS
scheme to implement Chained Threshold Proxy Signa-
ture with Supervision (CTPSwS) scheme. Different with
Lui et al’s idea, however, supervising agent is also ac-
tively involved in the delegation using his/her own pri-
vate key, such that verification for the proxy signature
requires supervising agent’s public key as well, besides
original signer and proxy signers’ public keys.
We also provide formal security models and proofs to
show that the schemes we designed are secure in the
random oracle model assuming the hard problem of dis-
crete logarithm.
1.4 Organization
A 3-level CTPS scheme and its security proof will be
described in section 2 & 3, respectively. Then a 3-level
CTPSwS scheme and security proof draft will be intro-
duced in section 4 & 5, respectively. Section 6 concludes
the paper and discusses some future work.
2. Chained Threshold Proxy S ignature (CTPS)
Recall that Sam, the manager of software development
department in corporation B, delegates his signing right
to a group of n2 vice managers, any subgroup of whom
with t2 members further delegate their proxy signing ca-
pabilities to a group of n3 employees, such that any sub-
group of t3 employees can reply to Simon with their
proxy signature on behalf of Sam.
We can formally define the above roles by letting Sam
the original signer u1 in level 1, vice managers a group of
n2 proxy signers in level 2, (for short), and em-
ployees a group of n3 proxy signers in level 3,
(for short). Any subgroup of t2 ≤ n2 vice manag-
ers performing the delegation is defined as U2. Similarly,
any subgroup of t3 ≤ n3 employees signing the replied
email is defined as U3. Note the difference between
2
2,
{}
jn
u
3
3,
{}
kn
u
2
2,
{}
j
n
u
22
{,Uu
3
3,
{}
kt
u
and U2, and U3. WLOG, we assume
and
. Let (sk1,pk1), (sk2,j, pk2,j), (skg2, pkg2), (sk3,k,
pk3,k) and (skg3, pkg3) denote u1, u2,j,
3
3,
{}
kn
u
2,
, }{u
22
,
}
t,12,2 2
,tj u u
3
33,13,2 3,
{, ,,
t
Uuu u
2
2,
{}
}
j
n
u, u3,k, and
’s secret/public key pairs respectively. By ex-
tending Boldyreva’s proxy signature scheme model,
CTPS scheme to achieve the delegation procedure should
involve a one-to-group protocol run between the original
signer and the group of proxy signers in level 2, a
group-to-group protocol run between any subgroup of
proxy signers in level 2 and the group of proxy signers in
level 3, a chained threshold proxy signing algorithm and
the corresponding verification algorithm. Additionally,
there should be an algorithm that extracts the identities of
the groups of proxy signers in both level 2 & 3.
3
3,
{}
kn
u
Definition 1 describes the detailed components of a
3-level Chained Threshold Proxy Signature scheme. A
list of important parameters and symbols is shown here
for your reference.
ω1: warrant including u1 and 2
2,
{}
j
n
u’s IDs, and other

Secure Chained Threshold Proxy Signature without and with Supervision 269
information on the delegation
ω2: warrant including 2
2,
{}
j
n
uand ’s IDs, and
other information on the delegation
3
3,
{}
kn
u
skt: secret key transformation generated by u1
skt1, j: share of secret key transformation sent to u2, j
skp2, j: proxy secret key share generated by u2, j
skt2, j: share of proxy secret key transformation gener-
ated by u2,j
skt2, j, k: sub-share of proxy secret key transformation
sent to u3, k
'
2,k
s
kt : share of proxy secret key transformation re-
trieved by u3,k
skp3, k: proxy secret key share generated by u3, k
pσ3: chained threshold proxy signature.
Definition 1 (CTPS Scheme) Let CTPS = (G, K, (TD,
TP), (CTD, CTP), CTPS, CTPV, CTPID) be a chained
threshold proxy signature scheme, where the constituent
algorithms run in polynomial time.
G is a random parameter-generation algorithm, and it
will output some global parameters params.
K is a random key-generation algorithm, and it will
output secret/public key pairs for original signer u1 and
proxy signers in both level 2 & 3, 2
2,
{}
j
n
uand ,
in the scheme.
3
3,
{}
kn
u
(TD, TP) is a Threshold Designation-Proxy protocol
between the original signer u1 and the proxy signers in
level 2, 2
2,
{}
j
n
u. Both TD and TP take as input the pub-
lic keys pk1 and pkg2, respectively. TD also takes as input
the secret key sk1 of u
1, and TP also takes as input the
secret key sk2,j of u2,j. As the result of the interaction, the
expected local output of TP is skp2, j, the proxy secret
share which is kept secret by each u2, j.
[TD (pk1, pkg2, sk1),TP (pk1, pkg2, sk2,j)] → skp2,j
(CTD, CTP) is a Chained Threshold Designation-
Proxy protocol between U2 and . Both CTD and
CTP take as input the public keys pk1, pkg2 and pkg3,
respectively. CTD also takes as input the proxy secret
shares
3
3,
{}
kn
u
2
2,
{}
jt
s
kp of 2
2,
{}
j
t
u. CTP takes as input the se-
cret key sk3,k of u3,k. The expected local output of CTP is
skp3,k, the proxy secret key share which is kept secret by
each u3,k. Note that for each u3,k to generate skp3,k, the
subgroup U2 is involved in CTD, but not just a certain
proxy signer in U2.
[CTD (pk1, pkg2, pkg3,2
2,
{}
j
t
skp ),
CTP (pk1, pkg2, pkg3, sk3,k)] → skp3,k
CTPS is the (possibly) randomized Chained Threshold
Proxy Signing algorithm. It takes as input3
3,
{}
kt
s
kp and a
message M{0,1}*, and outputs a chained thresh-
old-proxy signature pσ3.
CTPS (M,) → pσ3
3
3,
{}
kt
skp
CTPV is the deterministic Chained Threshold Proxy
Verification algorithm. It takes as input a message M, a
proxy signature pσ3, and (pk1, pkg2, pkg3), and outputs 0
or 1.
CTPV (M, pσ3, pk1, pkg2, pkg3) = 0/1
CTPID is the Chained Threshold Proxy IDentification
algorithm. It takes as input a valid proxy signature pσ3
and outputs identities of two proxy signer groups, i.e.,
public keys.
CTPID (pσ3) = (pkg2, pkg3)/⊥
SIGNATURE VERIFICATION CONDITION: If
CTPV =1 and CTPID = (pkg2, pkg3), we say pσ3 is a valid
chained threshold proxy signature by proxy signers in U2
and U3 on behalf of u1.
The definition clearly describes what kinds of individ-
ual algorithms and interactive protocols are required to
be run by original signer and proxy signers. After define
the structure of CTPS scheme, we design a concrete
scheme based on the definition.
We give a high-level description of our scheme here,
followed by the concrete calculation. First of all, by us-
ing public parameters and secret/public key pairs gener-
ated through G and K, u1 generates the certificate of war-
rant ω1 in (1), which is actually a signature of ω1 using
sk1. We call it secret key transformation skt1 in our
scheme since it masks u1’s secret key sk1 and will be
used for 2
2,
{}
j
n
u to generate proxy signing keys. In or-
der to designate 2
2,
{}
j
n
u as u1’s threshold proxy signers,
each share skt1,j generated by (2) will be distributed to u2,j
securely. After verifying skt1,j as a signature generated by
u1 using (3), each u2,j computes proxy secret key share
skp2,j in (4).
As the applications we described above, if any t2 ≤ n2
vice managers, such as U2, want to further delegate their
proxy signing capabilities to their employees ,
which we call a group-to-group delegation, each
3
3,
{}
kn
u
2, 2j
uU

computes secret key transformation skt2,j in (5)
as u1 does in (1), then divides it to n3 shares,
skt2,j,k(k=1,2, ··· ,n3), as calculated in (6), which are sent
to u3,k securely. As a result, each u3,k verifies
skt2,j,k(k=1,2, ··· ,t2) he receives using (8) and computes
'
2,k
s
kt by accumulating them in (9). By comparing (5)
and (9), skt2,j and'
2,k
s
kt are generated by two different
random polynomials F2(j) and '
2()
F
k with same con-
stant sktg2. For how (9) is deduced, please refer to La-
grange Formula, which was also used in [2]. Then each
u3,k can successfully generate the proxy secret key share
skp3,k in (11).

Secure Chained Threshold Proxy Signature without and with Supervision 270
Let us discuss a little more about the difference and
difficulty of (CTD, CTP) protocol compared with (TD,
TP) here. During (TD, TP) protocol, skt1,j carrying secret
information sk1 inside is generated and delivered to u2,j as
the mark for u1 to designate u2,j as one of his proxy sign-
ers. Similarly in (CTD, CTP) protocol, skt2,j carrying se-
cret information sk2,j should also be delivered to ,
but in an indirect way for the reason that there are a
group of delegators and a group of delegatees. Sending
skt2,j to u3,k where j = k one by one does not work because
U2 and may have different numbers t2 and n2.
However, from the group point of view, we need a
scheme to reshuffle {skt2,j = F2(j)(j = 1,2, ··· ,t2)} to
3
3,
{}
kn
u
3
3,
{}
kn
u
''
2
{(
2, 3
)(1,2,,
k)}
s
ktk n
2
(0)
F k
'
22
(0)
, satisfying that
F
Fsktg
2
2,
{}
. It seems that we keep the group
secret key transformation sktg2 unchanged and make se-
cret key transformation shares updated. With this pur-
pose, we found a good candidate of proactive secret
sharing approach [11], which was proposed to periodi-
cally renew the shares, like
j
t
s
kt
skt
3,
{u2
2,
{}
, to the new ones,
like , without changing the secret, like sktg2.
However, in our scheme, the renewed ones belong
to , but not
3
'
2,
{}
kn
3
}
kn
j
n
u.
Schnorr signature scheme [12] is used in CTPS and
CTPV where partial proxy signatures are pub-
lished among U3 such that each can calculate
proxy signature pσ3 in (13). The following details how
the algorithms and protocols are performed.
3
3,
{}
kt
ps
3
U
3,k
u
The system runs G. On input 1k , params = G(1k) =
(p,q,g,G,H), such that 2k−1 ≤ p< 2k, q|p − 1,
p
g
Z

of
order q, two hash functions G: {0,1}∗→ Zq, and H : {0,1}
∗→ Zq.
The system runs K. On input (p,q,g,G,H), K generates
1
R
q
s
kZ, pk1 = 1
s
k
g
mod p, sk2,j = SK2(j) and pk2,j =
2, j
s
k
g
mod p, where SK2(x) is a random polynomial with
random constant skg2 and degree t2 − 1. pkg2 = 2
s
kg
g
mod p. Note that although the intuitive idea for the above
procedure is to generate SK2(x) and distribute sk2,j to u2,j
securely by a trusted dealer, we deploy the protocol for
generating random number in [2] to implement it without
a dealer for security consideration. As a result, each u2,j
can only calculate his own secret key sk2,j without know-
ing skg2. skg3, pkg3, and are gener-
ated in the same way.
3
3,
{}
kn
sk 3
3,
{}
kn
pk
u1 runs TD.
1111
s
kte skk mod where (1)
,q
1
1
k
r
g
 mod 1
,
R
q
p
kZ

,
e1 = G (0║pk1║pkg2║ω1, r1).
skt1,j = F1(j) = skt1 +a1,1j + a1,2j2 +···+ mod q. (2)
2
2
1
1, 1
t
t
aj


F1(j) is a random polynomial privately owned by u1. r1
and {1,m
a
g
mod p}21t

are broadcast.
u2,j runs TP.
s
1, j
kt
g= (r1) · A mod p, where (3)
1
1
e
pk
21,
1
1()mod
m
m
j
ta
m
A
gp


.
skp2,j = e1 · sk2,j + skt1,j mod q. (4)
u2,j runs CTD.
skt2,j = e2 · skp2,j + k2,j mod q
=
e2 (e1 · SK2(j) + F1(j)) + K2(j)
= F2(j), where (5)
e2 = G (0║pkg2║pkg3║ω2, r2),
F2(0) = e2 (e1 · skg2 + skt1) + k2 = sktg2.
skt2,j,k = F2,j(k) mod q, where (6)
F
2,j(k) = skt2,j + b2,j,1k + b2,j,2k2 +···+ b2,j,mod q. (7)
31t31t
k
2
2,
{}
j
n
kare generated by running the protocol for gen-
erating random number in [2] such that each u2,j can cal-
culate k2,j without knowing any other’s secret shares
{k2,x}x≠j and satisfying that k2,j = K2(j), where K2(j) is a
random polynomial with constant kg2 and degree t2 − 1.
F2,j(k) is a random polynomial privately owned by each
u2,j with constant skt2,j and degree t3 − 1. {r2,j = 2, j
k
g
mod p} and r2 =
2
t2
kg
g
mod p are broadcast.
u3,k runs CTP.
2, ,jk
skt
g =


2
1
12, 1
e
e
j
pkpkr Ar2,j B, where (8)

32,,
1
1()mod
m
jm
k
tb
m
B
gp



22
'
2,2, ,2,
11
'
2
()
(),where
tt
kjjkj
jj
j
s
ktsktF k
Fk





(9)
22
'
22, 2,
11
(0) (0)
tt
jjj j
jj
2
F
Fskt 



sktg
(10)
2
1,
t
jllj
ljl





'
3,23,2, mod . kkk
s
kpe sksktq  (11)
U3 runs CTPS.
ps3,k = c3 · skp3,k + k3,k, where (12)
c3 = H (1║M║pkg2║pkg3║ω2║r1, r2), and
r3 = 3
k
g
mod p.
3, 3
33
,
kkk
uU
pp 


,
s

(13)

Secure Chained Threshold Proxy Signature without and with Supervision 271
3
1,
t
kllk
lkl





Verifier runs CTPV .
3
p
g

= 3
c
PKP · r3 mod p, where (14)
PK
PROOF OF (14) Let θ3 represents u3,kU3.
p
The proof proves the correctness of our CTPS scheme
from the computation point of view. In the following
se
del and prove
adaptive cho-
3
f of u1;
an CTPS,A
P =

122
2123
pkgrr pkg.

1
eee
pk
33
33,33, 3,kkkk k

33
3
33
33 , 3,
'
323,2,3
'
3233,2, 3
32 32,3
2
32 32 2,
()
()
()
()
((
kk kk
kkk
kkk
jj
jj
ppscskpk
cskp k
ce sksktk
c esksktk
ceskgskt k
ceskge skp




 









 
 





3
3232121123
2, 3
2
32 3 22,23
2
3232121123
((()))
))
()
((()))mod,
...
mod
...
j
jj
p
ceskgeeskgsk k kk
kk
ceskgeskpkk
ceskgeeskgskkk kq
LHS g
g
RHS






 
 





ction, we will prove its security.
3. Security of the CTPS Scheme
In the section, we set up CTPS security mo
that our CTPS scheme is secure against
sen-message attack in random oracle model.
As discussed in [10], the formal model includes a
rather powerful adversary who is able to corrupt all other
users’ secret keys except the Single Honest User (SHU).
Furthermore, A is of the capability to launch adaptive
chosen-message attacks according to three kinds of roles
that the SHU can play, namely Role 1: the original signer
u1, Role 2: one of the required proxy signers in U2, say
u2,2, and Role 3: one of the required proxy signers in U3,
say u3,2. All kinds of attacks will be described in the
model later. Besides, A can access to a chained threshold
proxy signing oracle. So the goal of the adversary A in-
cludes:
- A forgery CTPS on behalf of u1 (SHU);
- A forgery CTPS by proxy signers in U, who are
delegated by U2 including u2,2 (SHU), on behal
- A forgery CTPS by proxy signers including u3,2
(SHU) in U3 on behalf of u1.
Definition 2 (Security of CTPS Scheme) Let CTPS =
(G, K, (TD, TP), (CTD , CTP), CTPS, CTPV, CTPID) be
a chained threshold proxy signature scheme. Consider
experiment Exp (k) related to CTPS, adversary A
and parameter k. In the extreme case, adversary A
should represent all proxy signers if the SHU is the
original signer; or the original signer and all other proxy
signers except the SHU if the SHU is one of the proxy
signers in level 2 or 3. First, system parameters params
and secret/public key pairs are generated by running G
and K. Empty array skp3,2 and empty sets pkg2 and pkg3
are created. The adversary A is of all the secret keys ex-
cept SHU’s, and it can make the following requests and
queries.
R1: u1(SHU) designates 2
2,
{}
j
n
uand 3
3,
{}
kn
uas his
proxy signers. A requests to interact with u1(SHU) run-
ning TD, and plays the role o2
}f 2, {
j
nru P, and
the roles of U2 and 3
3,
{}
kn
urunning (CTD, CTP). And
pkg2 is set to 22
pkgpkg .
R2: u1 designates
unning T
2
2,
{}
j
n
u
y sig
interact with
and 3
3,
{}
kn
u, where u2,2 is
the SHU, as his pners
tiv
rox in and 3 respec- level 2
2,
{} ely. A requests to 2
j
n
u
2,j
CTD,, a
running P,
and plays the role of u1 running TD and the roles of all
other proxy signers in level 2 except u. Then A requests
again to interact with u2,2 running nd plays the
role of U2 except u2,2, and 3
3,
{}
kn
urunning (CTD, CTP).
pkg3 is set to 33
pkgpkg .
R3: u1 designates2, {}
T
2
j
n
u3
3, } kn
u, where u3,2 is
the SHU, as his pners in lev
tiv A
and
r and 3 respec-
{
el 2
3, {}
kn
u
oxy sig
teract ely. requests to inwith3running CTP,
and plays the role of U2 running CT D , and the roles of u1
and 2
2,
{}
j
n
u running (TD, TP). The private output skp3,2
by u3,2 (SHU) is stored in skp3,2. A does not have access
to skp3,2.
Q1 ned threshold proxy signature query by U3,
where u3,2 is the SHU, on behalf of u1. A can make a
query (M, 3
: Chai
2, x) to oracle OCTPS (skp3,k(k = 1,3, ··· ,t3),
skp3,2[x],·,·,·,). If skp3,2[x] has been defined, we say that
this query is valid and the oracle returns pσ3 = OCTPS
(skp3,k(k = 1,3, ··· ,t3), skp3,2[x],M,32,x,). Eventually A
outputs a forgery (M, pσ3, pk 1). The output of the ex-
periment is 1, if
- CTPID (pσ3) \ 32 pkg

pkg , or
- CTPID (pσ3) \ 23 pkg

pkg , or
- alid quNo v x)to
3, ··· ,t3), skp3,2[x]
ery (M, 32,OCTPS (skp3,k(k =
1, ,·,·,·,).
Ot is 0.
,A(k) = 1].
ure chained threshold proxy
negligible
fo a-
herwise, the output
We define the advantage of adversary A as
AdvCTPS,A(k) = Pr [ExpCTPS
We say that CTPS is a sec
signature scheme if the function AdvCTPS,A(k) is
the security pr A of time complexity polynomial in
rameter k.
SECURITY OF CTPS. The following theorem states

Secure Chained Threshold Proxy Signature without and with Supervision 272
our result about the security of Chained Threshold Proxy
Signature scheme. The proof of Theorem 1 is in Appen-
dix A.
Theorem 1 Let CTPS = (G, K, (TD, TP), (CTD, CTP),
CTPS, CTPV, CTPID) be our proposed chained thresh-
old proxy signature scheme in random oracle model. If
the Schnorr signature scheme is secure, then CTPS
sc
e by A suc-
ce
ent department,
as igners such
that oners can
ides th
heme is secure in random oracle model.
PROOF IDEA. The conclusion that a Chained Thresh-
old Proxy Signature scheme is provably secure can be
deduced with respect to the contradiction that if a forgery
of a chained threshold proxy signature schem
sses in polynomial time, i.e. AdvCTPS,A(k) is not negli-
gible, then a well-known standard signature scheme, i.e.
the Schnorr signature scheme, is broken.
4. Chained Threshold Proxy Signature with
Supervision (CTPSwS) Scheme
Recall when Sam, the software developm
appoints Steven, the software maintenance department,
the supervising agent to supervise proxy s
ly with permission of Steven, proxy sign
perform the signing capabilities. CTPSwS scheme in this
section extended from CTPS fits into this kind of sce-
nario by deploying Lui et al.’s [9] idea into our CTPS
scheme.
Different from the CTPS model, there is a new proto-
col (TDSA, TPSA ) run between original signer u
1 and his
supervising agent SA1. To differentiate the protocol run
between u1 and 2
2,
{}
jn
uin CTPSwS scheme with that in
CTPS, we define the former as (TDu, TPu). The signing
and verification algorithm should also include SA1’s pub-
lic key. The CTPSwS scheme model is as follows in
Definition 3. Bese notations described in Section 2,
we have several new ones shown here.
11
(,)
SA SA
sk pk: SA1’s secret and public key pair
1
SA
s
kp : partial proxy secret key generated by SA1
ps : partial chained threshold pro
1
SA xy signature gen-
erated by SA
Defini {G,
K, (TD
CTPVw
pervision scheme, where the constituent
al
1
tion 3 (CTPSwS Scheme) Let CTPSwS =
SA,TPSA), (TDu,TPu), (CTD,CTP), CTPS wS,
S, CTPIDwS} be a chained threshold proxy sig-
nature with su
gorithms run in polynomial time. G and K are similar
to those in CTPS except that K is also responsible to
generate SA1’s secret/public key pair11 (,)
SA SA
sk pk.
(TDSA, TPSA) is a Threshold Designation-Proxy proto-
col between the original signer u1 and the supervising
agent SA1. Both TDSA and TPSA take input the public
keys pk , pkg andpk , respectivelyake
as
2. TD also ts as 11
SA SA
input the secret key sk1 of u1, and TPSA takes as input the
secret key1
SA
s
kof SA1. As the result of the interaction,
the expected localut of TPSA is1
SA
outp
s
kp , the partial
proxy secret key of SA1. The undeniability of both u1 and
SA1 is achie by adding 1
SA
ved
s
kin the protocol.
[TDSA (pk1, pkg2, 1
SA
pk ,
TPSA (1
12
,,,
SA
pk pkgpksk)] → 1
SA
sk1),
1
SA
s
kp .
(TDu, TPu) is a Threshgnoxy protocol
between u1 an
old De
d{}
si ation-Pr
2
2,
j
n
u. u1 runs to send TDu warrant ω1
to 2
2,
{}
j
n. TP ta
u
al outpu
. Not
u run
the resu
by each proxy signeu2,jkes as
in
r
put the public keys pk1, pkg2 and the secret key sk2,j
respectively. Aslt of the interaction, the expected
loct of TPu is skp2,j, the partial proxy secret share
of u2,je the difference of this skp 2,j with that in CTPS
scheme. We call it partial here because all {skp2,j}t2 can
not perform anything without another part 1
SA
s
kp .
[TDu, TPu (pk1, pkg2, sk2,j)] → skp2,j
(CTD, CTP) is a Chained Threshold Designa-
tion-Proxy protocol between U2 and3, {}
kn
u3
sk3,k)] →
. It is similar
to that is d
CTPSw
efined in Definition 1.
[CTD (1
123
,,,,
SA
pk pkgpkpkg{skp2,j}t2),
CTP (1
123
,,,,
SA
pk pkgpkpkg skp3,k
S is omized Ch
Proxy sion algorit
the (p raained
Threshold Signinpervihm. It
is run greem SA put
the t ou correspares
{s
ossibly)
g with Su
ent of
onding pa
nd
rtial proxy
by U3 with a1, and takes as in
t of nsecret sh
3 3
kp3,k}t3 and SA1’s partial proxy secret 1
SA
s
kp and a
message M∈{0,1}*, and outputs a chained threshold
proxy signature with supervision pσ3.
CTPSwS [{skp3,k}t3, 1
SA
s
kp , M] → pσ
3
CTPVwS is the deterministic Chained Threshold Proxy
Verification with Supervision algorithm as follows.
CTPVwS [M, pσ3, 1 pk , , 1
SA
pk , pkg3] = 0/1
2
pkg
CTPIDwS is the Chained Threshold Proxy
IDentification with Supervision algorithm. It takes as
inpunat , an,
i.e., p
. Di fromu1 needs to
run Tnd
agent 1.’s i1SA
to
t a valid proxy sigreputs identities
ublic keys.
u pσ3
fferent
and
Lui et al
d out
CTPS,
s t
dea, SA
CTPIDwS (pσ3) = [2
pkg , 1
SA
pk , pkg3] /⊥
Based on Definition 3, we give a draft of a concrete
CTPSwS scheme here
DSA to calculate skt1seo his supervising
SA . Different from runs TP
generate 11
11SA SA
s
kpsk eskt mod q using his secret
key 1
SA
s
k. Without knowing skt1,j, each u2,j runs TPu to
generate skp2,j = sk2,j e1 mod q. (CTD, CTP) run between

Secure Chained Threshold Proxy Signature without and with Supervision 273
U2 and 3, {u that in CTPS . At last
whenh 3, 3k uU agrees to the data part, they must
forward this email to SA1, Steven, for him to check the
contract p can not generate a valid proxy signature
on behalf oftil Steven agrees to the contract part
and contrihis partial proxy signature
111
3SASA SA
psskp ck
mod q where 1
SAR q
kZ and
1
1mod
SA
k
SA
rg q. Since SA1’s secret key 1
SA
3
}
kn
c
art. U2
Sam
bute
is the same as
ea
un
s
s
k is in-
volved, security level of our scheme is enhanced by add-
erty.
CTPSwS
The security model of CTPSwS is similar to that of CTPS
defined in Definition 2, exce
ing SA1
5. Sec
re
-protected
urity of
prop
pt that Aurth
t of u1, s of
(k)
can be the fo
SA1. In term
p
role, Role 4: the supervising agen
this role, the goal of A also includes a forgery CTPSwS
by U2, U3 and SA1 (SHU) on behalf of u1.
Definition 4 (Security of CTPSwS) Let CTPSwS =
{G, K, (TDSA, TPSA), (TDu, TPu), (CTD, CTP), CTPS wS,
CTPVwS, CTPIDwS} be a chained threshold proxy sig-
nature scheme. Consider an experiment Ex CTPSwS,A
lated to CTPSwS, adversary A and parameter k. In the
extreme case, adversary A should represent all proxy
signers and SA1 if the SHU is the original signer, or the
original signer, SA1, and all other proxy signers except
the SHU if the SHU is one of the proxy signers in level 2
or 3, or the original signers and all proxy signers if the
supervising agent SA1 is the SHU. Empty arrays skp3,2,
1
SA
skp and empty sets pkg2, pkg3 are created. The ad-
versary A can make the following requests and queries:
R1: u1(SHU) designates2
2,
{}
j
n
u and 3
3,
{}
kn
uas his
gner groups in level 2 & 3, respectively, and
specifies SA1 as u1’s supervising agent. A requests to in
ter th TD P
proxy si
ro
-
act wi u1(SHU) runningnd T plays
les of all others running(TDSA A) andCTP).
1
SA
pkg is set to 11
SA SA
pkgpkg .
R2: u1 designates 2
2,
{}
SA a
, TPS
SA, and
(CTD,
j
n
u and 3
3,
{}
kn
uas his proxy
signer groups in level 2 & 3, where u2,2 is the SHU and
s SA1 asg agspecifie
ter
ro
u1’s supervisin
running
ing (TD
ent.
d
PSA),
A reque
CT
T
sts to in-
act with u2,2 (SHU) TPu anD, and plays
les of all others runnSA, TDu and CTP.
pkg2 is set to 22
pkgpkg .
R3: u1 designates 2
2,
{}
j
n
u and 3
3,
{}
kn
uas his proxy
signer groups in level 2 & 3, respectively, and specifies
SA1 (SHU) as ing agen
ac
u1’s supervis
nning TP
anent
t. A
thms
requests to
plays roles of all
a
inter-
t with SA1 (SHU) ruSA, and
rs running the remalgorind protocols.
1
SA
skp is set to 11
SA SA
othe
s
kpskp .
R4: u1 designates 2
2,
{}
j
n
u and 3
3,
{}
kn
uas his proxy
signer groups in level 2 & 3, where u3,2 is the SHU, and
es SA1 asing specifi u1’s supervisagent. A requests to in-
te nning Cd pla
otanent thms a
ract with u3,2 (SHU) ruTP, anys roles of all
hers running the remalgorind protocols.
skp3,2 is set to 3,23,2 .
s
kpskp
Q1: Chained threshold proxy signature with supervi-
sion query, where u3,2 is the SHU, on behalf of u1. A can
make a query (M,32,x) to oracle OCTPVwS(skp3,k(k
=1,3,··· ,t3),skp ,·). If skp [x] has been
3,2 1
SA
[x],
s
kp ,·,· 3,2
defined, we say this query is valid and the oracle returns
pσ3 = CTPSwS(skp3,k(k =1,3,··· ,t3),skp3,2[x], 1
SA
s
kp ,M,·,·).
Q2: Chained threshoroxy signature with supervi-
sion query, where SA1 is the SHU, on behalf of u1. A can
make a query (M,SA1,x) to oracle OC(skp3,k(k
=1,2,··· ,t), skp [x],·,·,·). If skp [s been
ld p
A outp
TPVwS
x] ha
, M,pσ
31
SA 1 SA
defined, we say this query is valid and the oracle returns
pσ3 = CTPSwS (skp3,k(k =1,2,··· ,t3), 1
SA
skp [x],M,·,·).
Eventually uts a forgery (3,pk1). The out-
put of the experiment is determined as follows:
- CTPIDwS (pσ3) \


1
32SA
pkg pkgpk
g
, or
- CTPIDwS (pσ3) \


1
23SA
pkg pkgpk
g
, or
- No valid queVwS(skp
,3,··· ,t3),skp3,2[x],·,·,
ry (M
·),
y (M,
).
TPSwS [
is ne
odel, Chained
,32,x) to OCTP 3,k(k
=1
SA1,x) to OCTP 3,k(k
=1
s
CExpCTPSwS,A(k) = 1]
hained threshold proxy
si function
Ad CTPSw of plexity
polynom
acle m Threshold Proxy Signature
oxy Signature
, to solve the
- No valid querVwS(skp
,2,··· ,t), skp ,·,·,·
31
SA
Otherwise, the output is 0.
We define the advantage of adversary A a
Adv ,A(k) = Pr
We say that CTPSwS is a secure c
gnature with supervision scheme if the
vA
S,A(k)gligible for time com
ial in the security parameter k.
Security proof details follow the similar logic as the
CTPS scheme, but are more tedious and skipped in this
paper.
6. Conclusion and Discussion
This paper designs two provably secure schemes in ran-
dom or
(CTPS) scheme and Chained Threshold Pr
with Supervision (CTPS wS) scheme
group-to-group delegation problem and delegation with
supervision in delegation chain problem. They are very
useful in email with signature system where a manager
wants to delegate his signing right to his vice managers,
who can further perform the delegation to their employ-
ees. In some cases, the delegatee’s proxy signing rights
can be supervised by manager’s supervising agent. For
future work, we hope to develop more flexible delegation

Secure Chained Threshold Proxy Signature without and with Supervision 274
and with Supeational Conference
on Computerare Engineering
na, pp. 223−232, 1997.
to identification and signature problems,” In
roceedings of 13th In-
based
77, No.
delegation of signing rights,”
to cope with perpetual
l. 4, No. 3, pp. 161−
scheme that enables delegatees in different levels, say
any one of vice managers and any two employees can
cooperate to generate proxy signature. Also, more effi-
cient schemes for these problems are always desirable.
REFERENCES
[1] Zoe L. Jiang, S. M. Yiu, L. C. K. Hui, Y. Dong, and S. H.
Y. Wong, “Chained threshold proxy signature without
t
rvision,” In 2008 Intern
Science and Softw
(CSSE’08), HongKong, China, pp. 837−840, December
2008.
[2] S. Kim, S. Park, and D. Won, “Proxy signatures, revis-
ited,” In 1st International Conference on Information and
Communications Security (ICICS’97), LNCS 1334, Bei-
jing, Chi
[3] M. Mambo, K. Usuda, and E. Okamoto, “Proxy signa-
tures for delegating signing operations,” In 3rd ACM
Conference on Computer and Communication Security,
New Delhi, India, pp. 48−57, 1996.
[4] T. El Gamal, “A public key cryptosystem and a signature
scheme based on discrete logarithms,” In IEEE Transac-
tions on Information Theory, Vol. 31, No. 4, pp. 469−472,
1985.
[5] T. Okamoto, “Provably secure and practical identification
schemes and corresponding signature schemes,” In Ad-
vances in Cryptology (Crypto’92), LNCS 740, pp. 31−53,
1992.
[6] A. Fiat and A. Shamir, “How to prove yourself: Practical
solutions
Advances in Cryptology-Eurocrypt 1986 (EuroCrypt’86),
LNCS 263, pp. 186−194, 1987.
[7] B. C. Neuman, “Proxy-based authorization and account-
ing for distributed systems,” In P
ernational Conference on Distributed Computing Sys-
tems, Pittsburgh, USA, pp. 283−291, May 1993.
[8] M. Cerecedo, T. Matsumoto, and H. Imal, “Efficient and
secure multiparty generation of digital signatures
on discrete logarithms,” In IEICE Transactions on Fun-
damentals of Electronics, Communications & Computer
Science, Vol. E76-A, No. 4, pp. 532−545, 1993.
[9] R. W. C. Lui, L. C. K. Hui, and S. M. Yiu, “Delegation
with supervision,” In Information Sciences, Vol. 1
19, pp. 4014−4030, 2007.
[10] A. Boldyreva, A. Palacio, and B. Warinschi, “Secure
proxy signature schemes for
http://eprint.iacr.org/2003/096.
[11] A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung.
“Proactive secret sharing or: How
leakage,” In Advances in Cryptology (Crypto’95), LNCS
963, Vol. 963, pp. 339−352, 1995.
[12] C. P. Schnorr, “Efficient signature generation by smart-
cards,” In Journal of Cryptology, Vo
174, 1991.

Secure Chained Threshold Proxy Signature without and with Supervision 275
APPENDIX
Proof of Theorem 1
uppose adversary A is a successful forger against CTPS
heme in polynomial time. Let adversaries B, C, and D
cation channels from and to A, and
gning oracle O
S, a chained
cle OCTPS, and two random
A
S
sc
wrap all communi
have access to a standard si
threshold proxy signing ora
oracles functioning as hash functions G and H to answer
A’s requests and queries. First, system parameters
params and secret/public key pairs are generated by run-
ning G and K. Empty array wskp3,2 and empty sets pkg2
and pkg3 are created. The adversary A is of all the secret
keys except SHU’s, and it can make the following re-
quests and queries.
R1: A requests to interact with u1(SHU) running TD,
and plays the role of 2
2,
{}
j
n
urunning TP. The request is
interrupted by B. B creates an appropriate warrant ω1 and
makes query (0║pk1║pkg2║ω1) to its signing oracle
O(sk ,·). Upon receivi
S1ng an answer (skt1,r1), it forwards
1,skt1,r1) to 2
2,
{}
(ω
j
n
u. After a successful run, pkg2 is set
to pkg2∪pkg2.
R2: A requests to interact with 2
2,
{}
j
n
urunning TP,
where u2,2 is the SHU, and plays the role of u1 running
TD. C createspropriate warrant ω2 and makes
query (0║pkg2║
OS(skp,·). Upon
an ap
pkg3║ω2) to ing oracle
receiving an ans, r), it di-
vi
t2,j,2, them. I
ations pass, Dore
ts signi
wer (skt2,2
random
2,2 2
des the answer into n3 shares using polynomial
F2,2(x) and forwards (ω2,

3
2,2, kn
skt , r2) to 3
3,
{}
kn
u.
pkg3 is set to 33 pkgpkg .
R3: A requests to interact with 3
3,
{}
kn
urunning CTP,
where u3,2 is the SHU, and plays the role of U2 running
CTD. When A outputs ω2, sk verifies f
all the verific st
r2, D
s (ω2,'
2,2
s
kt , r2) in the
la
A
st unoccupied position of ws kp3,2.
Q1: can make a query (M,32,x) to oracle
OCTPS(skp3,k(k = 1,3,···,t3),skp3,2[x],·,·,·). If wskp3,2[x] is
not defined, it returns ⊥. Otherwise, D performs the
following operations:
- Pick a random number .cZ
3q

- Pick a random number 3,2 .
q
ps Z
- Make a query (0║pkg ║pkg3║ω2,r2) to oracle G and
2
3║ω2║r2, r3) ← c3
Suppose after the experiment ExpCTPS,A(k), A outputs a
forgery in pol of
th
2
let e2 be the response.
- Compute commitment
2, 3,2 3
1
3,2 3,2
()mod
j
skt ps c
e
rg pk gp


- Set H(1║M║pkg2║pkg
- Return (r3,2, ps3,2) to A
ynomial time of k such that at least one
e following events occurs:
E1. CTPID(pσ3) \ 3 pkg

pk
g
.
E2. CTPID(pσ3) \ 23 pkg

pk
g
.
E3. no valid query (M,32,x) to OCTPS(skp3,k(k =
1,
s. Since all the coming in and out
ch ed by the arsaries, the query
H
c3. By using forking lemma, B
ca
3,···,t3),skp3,2[x],·,·,·).
Assume E1 occur
annels are wrappdve
(1║M║pkg2║pkg3║ω2║r2, r3) made by A must be
grabbed and responded by
n rewind A to this point and gives A another random
'
3
c

c3. With non-negligible probability, A produces a
forgery with respect to the same query, such that
33
''
33
3
3
mod ,
mod .
pc
pc
g
PKPrp
g
PKPrp




Hence,
''
33 33
()mod ()mod
3212112
mod ,
mod ,
(())mod.
ppqccq
SKP
gPKP
PKP gp
skgeeskgsk k kq
 


 
2
SKP e
p
B subtracts e2 · skg3 + e2(e · skg2)+ k2 for B knows
skg2 and skg3. Then it obtains
1
'
1

= sk1 · e1 + k1 mod
successful Schnorr signature of u1.
q, a
Assume E2 occurs. The deduction is similar to the
above. However since the SHU is u2,2, the adversary C
should subtract the corresponding parts, and obtain '
2,2

= sk · e + k mod q, a successful S
2,2 11
2,2.
Assume E3 occurs. The deduction is similar to the
above. However since the SHU is u3,2, the adversa
should subtract the corresponding parts, and obtain '
3, 2
chnorr signature of
u
ry D

= sk ·
3,2 2k2
3,2.
e + mod q, a successful Schnorr signature of
u