### Paper Menu >>

### Journal Menu >>

J. Software Engineering & Applications, 2009, 2: 267-275 doi:10.4236/jsea.2009.24034 Published Online November 2009 (http://www.SciRP.org/journal/jsea) Copyright © 2009 SciRes 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. Email: {ljiang, smyiu, ydong, hui, shywong}@cs.hku.hk. 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 ﬁrst efﬁcient 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 beneﬁt 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 ﬁcate. 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 sacriﬁced both the original signer and the supervising agent’s undeniabilities due to the advantage the authors presented that there is no need for the veriﬁer 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] deﬁned 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 efﬁciency, 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 veriﬁcation 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 deﬁne 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 deﬁned as U2. Similarly, any subgroup of t3 ≤ n3 employees signing the replied email is deﬁned 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 veriﬁcation 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 Deﬁnition 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 Copyright © 2009 SciRes JSEA 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. Deﬁnition 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 Veriﬁcation 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 IDentiﬁcation 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 deﬁnition clearly describes what kinds of individ- ual algorithms and interactive protocols are required to be run by original signer and proxy signers. After deﬁne the structure of CTPS scheme, we design a concrete scheme based on the deﬁnition. 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 certiﬁcate 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 veriﬁes 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). Copyright © 2009 SciRes JSEA Secure Chained Threshold Proxy Signature without and with Supervision 270 Let us discuss a little more about the difference and difﬁculty 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 reshufﬂe {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 Fsktg 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) 31t31t 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) Copyright © 2009 SciRes JSEA 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,kU3. 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. Deﬁnition 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 pkgpkg . 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 pkgpkg . 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 deﬁned, 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 deﬁne 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 Copyright © 2009 SciRes JSEA 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 ﬁts 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 deﬁne the former as (TDu, TPu). The signing and veriﬁcation 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 Deﬁni {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 eﬁned in Deﬁnition 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 Veriﬁcation 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 IDentiﬁcation 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 Deﬁnition 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 Copyright © 2009 SciRes JSEA 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 deﬁned in Deﬁnition 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. Deﬁnition 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 speciﬁes 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 pkgpkg . 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 agspeciﬁe 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 pkgpkg . R3: u1 designates 2 2, {} j n u and 3 3, {} kn uas his proxy signer groups in level 2 & 3, respectively, and speciﬁes 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 kpskp . 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 speciﬁ 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 kpskp 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 deﬁned, 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 deﬁned, 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 pkgpk g , or - CTPIDwS (pσ3) \ 1 23SA pkg pkgpk 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 deﬁne 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 ﬂexible delegation Copyright © 2009 SciRes JSEA Secure Chained Threshold Proxy Signature without and with Supervision Copyright © 2009 SciRes JSEA 274 and with Supeational Conference on Computerare Engineering na, pp. 223−232, 1997. to identiﬁcation 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 identiﬁcation 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, “Efﬁcient 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, “Efﬁcient 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 pkgpkg . 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 veriﬁes f all the veriﬁc 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 deﬁned, 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 Copyright © 2009 SciRes JSEA |