近年來，為了方便與快速人們已習慣利用網際網路處理事情，如購買或拍賣商品，訂票等。對於這些商業活動，認證性與不可否認性為主要且不可或缺的特性。通常可用數位簽章來達到這些要求。數位簽章法允許簽章者產生文件的簽章，且可由任何人當成驗證者驗證簽章的合法性。數位簽章法的規則包括簽章者使用自己的私密金鑰簽署訊息，因而產生此訊息之有效簽章，之後驗證者利用簽章者之公開金鑰驗證這組簽章與訊息的正確性。因此，數位簽章法為認證特定簽章者訊息的一般方式。然而，應用數位簽章時有許多情況必須加以考量及定義。當簽章者無法線上簽名時，如簽章者正忙於某事或出差時，必須要有另一個適用於此環璄的數位簽章方法。代理簽章法則可用於此情形。
　　代理簽章在未來已變成愈來愈重要。許多人利用網路工作，也在網路的環境中簽署訊息（合約、文件等）。當他們很忙使得無法親自簽署重要文件時，他們就必須將簽署權力授與代理簽章者以代表他們行使簽章的權力。
　　在整個論文中，我們著重在代理簽章法且在各種環境下提出四種代理簽章法。這四種方法分別為傳統代理簽章法、門檻式代理簽章法、多重代理簽章法及完全分散式代理簽章法。在一般代理簽章法中，原始簽章者將他的簽署權力授與代理簽章者，而後代理簽章者可代表原始簽章者簽署訊息產生代理簽章。假使驗證者可確認代理簽章的正確性，則此簽署文件是合法的。此方法為一對一。在門檻式代理簽章法中，原始簽章者將他的簽署權力授與多個代理簽章者。(t,n)門檻式代理簽章法則允許原始簽章者授權給n個代理簽章者，唯有n個人中的t個代理簽章者可代表原始簽章者共同簽署訊息產生代理簽章。t-1以下的人都無法共同簽章合法的代理簽章。此方法為一對多。相反地，原始簽章者也可被分為多個原始簽章者。也就是說，許多原始簽章者可授與他們的簽署權力給一個代理簽章者。因此，此代理簽章者可代表二個以上的原始簽章者簽署訊息產生代理簽章。此方法為多對一。最後，完全分散式代理簽章法則結合門檻式代理簽章法與多重代理簽章法的特性。在此方法中，多個原始簽章者可授與他們的簽署權力給多個代理簽章者，這些代理簽章者則可代表多個原始簽章者簽署訊息。此方法為多對多。
　　在此論文，我們提出四種代理簽章法且在每一方法分別提出植基於因式分解與weil pairing的二種方式。所有的方法最後將附上正規證明。

　　In recent years, people have been used to deal with something on the Internet for convenience and speed, such as buying or bidding commodities, ordering the tickets, etc. For these commercial activities, authenticity and nonrepudiation are the major and indispensable properties. Usually digital signatures are applied to achieve these requirements. A digital signature scheme is a method which allows a signer to create digital signatures of documents, and the generated signatures can be verified by any person, called a verifier. The scenario for a digital signature scheme includes that the signer uses his private key to sign a message and hence generate a valid digital signature for the message, and then the verifier uses the corresponding public key of the signer to verify the correctness of the message-signature pair. Thus, a digital signature scheme is a general way to authenticate messages for a specific signer. However, more situations for digital signatures need to be considered and addressed. Considering the case when the signer cannot sign messages online, e.g., the signer is busy for something or on a business trip, we desire a variant of digital signature scheme to be suitable for such an environment. Proxy signature schemes are applied to this situation.
　　Proxy signatures are becoming more and more important in the future. Many people work on the Internet and sign messages (contracts, documents, etc.) in the environment, too. Once they cannot sign an important message personally because they are busy with something, they have to delegate their signing authority to proxy signers on behalf of them.
　　Throughout this thesis, we focus on the proxy signature schemes and propose four kinds of proxy signature schemes under diverse circumstances. The four kinds of schemes are traditional proxy signature scheme, threshold proxy signature scheme, proxy multi-signature scheme, and fully distributed proxy signature scheme, and they are defined as below. In ordinary proxy signature schemes, the original signer delegates his signing authority to the proxy signer, and then the proxy signer can sign messages and generate proxy signatures on behalf of the original signer. The signed message is valid if the verifier has checked the correctness of the proxy signature. It is a one-to-one scheme. In threshold proxy signature schemes, the original signer distributes his signing authority to multi-proxy signers. The (t,n) threshold proxy signature scheme allows the original signer to delegate his signing authority to n proxy signers. Only t out of n proxy signers can sign messages as the proxy signatures on behalf of the original signer collaboratively, t-1 or few proxy signers cannot generate a valid proxy signature. It is a one-to-many scheme. On the contrary, the entity of original signer also can be distributed into multi-original signers. That is, many original signers can delegate their own signing authority to one proxy signer. In proxy multi-signature schemes, a proxy signer can generate a proxy signature on behalf of two or more original signers. It is a many-to-one scheme. Finally, the fully distributed proxy signature schemes combine the properties of threshold proxy signature scheme and proxy multi-signature scheme. In fully distributed proxy signature schemes, a group of original signers delegate their signing authority to a group of proxy signers which can sign messages on behalf of these original signers. It is a many-to-many scheme
　　In this thesis, we propose four kinds of proxy signature schemes. In each method, we propose two schemes based on factoring and weil pairing individually. All of the schemes are provided the formal proof afterwards.

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Proxy Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
　2.1 Factoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
　2.2 Bilinear Pairing .. . . . . . . . . . . . . . . . . . . . . . . . . . . 7
　2.3 The GQ Signature Scheme ... . . . . . . . . . . . . . . . . . . . . . . 8
　2.4 Provable Security . . . . . . . . . . . . . . . . . . . . . . . . . . 10
　　　2.4.1 Security of a Proxy Signature Scheme . . . . . . . . . . . . . . 11
3 Traditional Proxy Signature Schemes . . . . . . . . . . . . . . . . . . . 13
　3.1 Review on Proxy Signature Scheme Based on Discrete Logarithm . . . . . 13
　3.2 Proxy Signature Scheme Based on Factoring . . . . . . . . . . . .. . . 15
　　　3.2.1 System Parameters . . . . . . . . . . . . . . . . . . . . .. . . 15
　　　3.2.2 Signing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
　　　3.2.3 Verifying . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
　　　3.2.4 Security Analysis . . . . . . . . . . . . . . . . . . . . . . . 19
　　　3.2.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . 21
　3.3 Proxy Signature Scheme Based on Weil Pairing . . . . . . . . . . . . . 22
　　　3.3.1 System Parameters . . . . . . . . . . . . . . . . . . . . . . . 22
　　　3.3.2 Signing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
　　　3.3.3 Verifying . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
　　　3.3.4 Security Analysis . . . . . . . . . . . . . . . . . . . . . . . 26
　　　3.3.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . 27
4 Threshold Proxy Signature Schemes. . . . . . . . . . . . . . . . . . . . 29
　4.1 Review on Threshold Proxy Signature Scheme Based on Discrete Logarithm 30
　4.2 Threshold Proxy Signature Scheme Based on Factoring . . . . . . . . . 32
　　　4.2.1 System Parameters . . . . . . . . . .. . . . . . . . . . . . . . 33
　　　4.2.2 Signing . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 34
　　　4.2.3 Verifying . . . . . . . . . . . . . . . . . . . . . .. . . . . . 34
　　　4.2.4 Security Analysis . . . . . . . . . . . . . . . . . .. . . . . . 37
　　　4.2.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . 40
　4.3 Threshold Proxy Signature Scheme Based on Weil Pairing . . . . . . . . 41
　　　4.3.1 System Parameters . . . . . . . . . . . . . . . . . . . .. . . . 41
　　　4.3.2 Signing . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 42
　　　4.3.3 Verifying . . . . . . . . . . . . . . . . . . . . . . . .. . . . 43
　　　4.3.4 Security Analysis . . . . . . . . . . . . . . . . . . . .. . . . 45
　　　4.3.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . 46
5 Proxy Multi-Signature Schemes . . . . . . . . . . . . . . . . . . . . . . 48
　5.1 Review on Proxy Multi-Signature Scheme Based on Discrete Logarithm. . .48
　5.2 Proxy Multi-Signature Scheme Based on Factoring . . . . . . . . . . . 50
　　　5.2.1 System Parameters . . . . . . . . . . . . . . . . . . . . . . . 50
　　　5.2.2 Signing . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 51
　　　5.2.3 Verifying . . . . . . . . . . . . . . . . . . . . . . . . . . .. 51
　　　5.2.4 Security Analysis . . . . . . . . . . . . . . . . . . . . . . .. 54
　　　5.2.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . 56
　5.3 Proxy Multi-Signature Scheme Based on Weil Pairing . . . . . . . . . . 56
　　　5.3.1 System Parameters . . . . . . . . . . . . . . . . . . . . . . .. 56
　　　5.3.2 Signing . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 57
　　　5.3.3 Verifying . . . . . . . . . . . . . . . . . . . . . . . . . . .. 59
　　　5.3.4 Security Analysis . . . . . . . . . . . . . . . . . . . . . . .. 61
　　　5.3.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . 62
6 Fully Distributed Proxy Signature Schemes. . . . . . . . . . . . . . . . 63
　6.1 Review on Fully Distributed Proxy Signature Scheme Based on Discrete
　　　Logarithm . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . 64
　6.2 Fully Distributed Proxy Signature Scheme Based on Factoring . . . . . 65
　　　6.2.1 System Parameters . . . . . . . . . . . . . . . . . . . . . . . 65
　　　6.2.2 Signing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
　　　6.2.3 Verifying . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
　　　6.2.4 Security Analysis . . . . . . . . . . . . . . . . . . . . . . . 71
　　　6.2.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . 74
　6.3 Fully Distributed Proxy Signature Scheme Based on Weil Pairing . . . . 75
　　　6.3.1 System Parameters . . . . . . . . . . . . . . . . . . . . . .. . 75
　　　6.3.2 Signing . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 76
　　　6.3.3 Verifying . . . . . . . . . . . . . . . . . . . . . . . . . .. . 76
　　　6.3.4 Security Analysis . . . . . . . . . . . . . . . . . . . . . .. . 80
　　　6.3.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . 81
7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 83
Bibliography 85

[1] M. Al-Ibrahim and A. Cerny, “Proxy and threshold one-time signatures,”ACNS
2003, LNCS 2846, pp. 123-136, 2003.
[2] M. Bellare, R. Canetti and H. Krawczyk, “Keying hash functions for message
authentication,” Advances in Cryptology – CRYPTO’96, pp. 1-15, 1996.
[3] M. Bellare, A. Desai, D. Pointcheval and P. Rogaway, “Relations among notions
of security for public-key encryption schemes,” Advances in Cryptology –
CRYPTO’98, pp. 26–45, 1998.
[4] M. Bellare and P. Rogaway, “Random oracles are practical: A paradigm for designing
e cient protocols,” Proc. of the First ACM Conference on Computer and
Communications Security, pp. 62–73, November 1993.
[5] M. Blaze, G. Bleumer, and M. Strauss, “Divertible protocols and atomic proxy
cryptography,”Advances in Cryptology EUROCRYPT’98, LNCS 1403, Springer-
Verlag, pp. 127-144, 1998.
[6] A. Boldyreva, A. Palacio and B. Warinschi, “Secure proxy signature
schemes for delegation of signing rights,”Preprint available at
http://eprint.iacr.org/2003/096/.
[7] D. Boneh, “The decision Di e-Hellman problem,” Proc. of Third Algorithmic
Number Theory Symposium, pp. 48–63, 1998.
[8] D. Boneh and M. Franklin, ”E cient generation of shared RSA keys,” In Crypto
’97, LNCS 1233, Springer-Verlag, pp. 425-439, 1997.
[9] Boneh, D. and Franklin, M., “Identity based Encryption from Weil Pairing,” in
Advances in Cryptography-CRYPTO 2001, Santa Barbara, CA, August 2001.
[10] R. Canetti, O. Goldreich and S. Halevi, “The random oracle methodology, revisited,”
Proc. of the 30th Annual ACM Symposium on Theory of Computing, pp.
209–218, 1998.
[11] J.C. Cha and J.H. Cheon, “An identity-based signature from gap Di e-Hellman
groups,”Public Key Cryptography - PKC 2003, LNCS 2139, pp. 18-30, Springer
Verlag, 2003.
[12] R. Cramer and V. Shoup, “Signature schemes based on the strong RSA assumption,”
ACM Transactions on Information and System Security, Vol. 3, No. 3, pp.
161-185, 2000.
[13] I. Damgard and M. Koprowski, ”Practical threshold RSA signatures without a
trusted dealer,” Advances in Cryptology EUROCRYPT’01, LNCS 2045, Springer-
Verlag, pp. 152-165, 2001.
[14] Y. Desmedt and Y. Frankel, “Threshold cryptosystems,” in Advances in
Cryptography-Crypto’89, LNCS 435, pp. 307-315, 1989.
[15] W. Di e and M. Hellman, “New directions in cryptography,” IEEE Transactions
on Information Theory, Vol. 22, No. 6, pp. 644–654, 1976.
[16] D. Dolev, C. Dwork and M. Naor, “Non-malleable cryptography (extended abstract),”
Proc. of the Twenty Third Annual ACM Symposium on Theory of Computing,
pp. 542–552, May 1991.
[17] T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete
logarithm,” IEEE Transactions on Information Theory, pp. 469–472, 1985.
[18] P.A. Fouque and J. Stern, ”Fully distributed threshold RSA under standard
assumptions,” Advances in Cryptology ASIACRYPT’01, LNCS 2248, Springer-
Verlag, pp. 310–330, 2001.
[19] E. Fujisaki and T. Okamoto, “Statistical zero knowledge protocols to prove
modular polynomial relations,”Advances in Cryptology CRYPTO’97, LNCS 1294,
Springer-Verlag, pp. 16–30, 1997.
[20] S. Goldwasser and S. Micali, “Probabilistic encryption,” Journal of Computer and
System Sciences, Vol. 28, No. 2, pp. 270–299, April 1984.
[21] S. Goldwasser, S. Micali and C. Racko , “The knowledge complexity of interactive
proof systems,” SIAM Journal on Computing, Vol. 18, No. 1, pp. 186–208, February
1989.
[22] L.C. Guillou and J.J. Quisquater, “A ”paradoxical” identity-based signature
scheme resulting from zero-knowledge,”Advances in Cryptology- Crypto 1988,
LNCS, Springer-Verlag, pp. 216-231, 1988.
[23] F. Hess, “E cient identity based signature schemes based on pairings,”SAC 2002,
LNCS 2595, pp. 310-324, Springer-Verlag, 2002.
[24] J. Herranz and G. Saez, “Verifiable secret sharing for general access structures,
with application to fully distributed proxy signatures,”In Financial Cryptography
(FC’03) , LNCS 2742, pp. 286-302, Springer-Verlag, 2003.
[25] J. Herranz and G. Saez, “Revisiting fully distributed proxy signature
schemes,”Preprint available at http://eprint.iacr.org/2003/197/.
[26] C.L. Hsu, T.S. Wu, and T.C. Wu, “Improvement of threshold proxy signature
scheme,”Applied Mathematics and Computation, Vol. 136, pp. 315-321, 2003.
[27] M.S. Hwang, J.L. Lu, I.C. Lin, “A Practical (t,n) Threshold Proxy SignatureScheme
Based on the RSA Cryptosystem,”IEEE Trans. Knowledge and Data
Engineering, Vol. 15, Np. 6, pp. 1552-1560, 2003.
[28] G. Itkis and L. Reyzin, “Foreward-secure signatures with optimal signing and
verifying,”Advances in Cryptology- Crypto 2001, LNCS, Springer-Verlag, pp. 332-
354, 2001.
[29] G. Itkis and L. Reyzin, “SiBIR: Signer-based intrusion-resilient signatures,”
Advances in Cryptology- Crypto 2002, LNCS, Springer-Verlag, p.p. 499-514,
2002.
[30] J. Katz and M. Yung, “Complete characterization of security notions for probabilistic
private-key encryption,” Proc. of the 32nd Annual ACM Symposium on
Theory of Computing, pp. 245–254, 2000.
[31] S. Kim, S. Park and D. Won, “Proxy signatures, revisited,”ICICS’97, LNCS 1334,
Springer-Verlag, pp. 223-232, 1997.
[32] J.Y. Lee, J. H. Cheon, and S. Kim, “An analysis of proxy signatures: Is a secure
channel necessary?,” In CT-RSA’03, LNCS 2612, pp. 68-79, Springer-Verlag, 2003.
[33] N.Y. Lee, T. Hwang, and C.H. Wang, “On Zhang’s nonrepudiable proxy signature
schemes,” In ACISP ’98, LNCS, pp. 415-422, 1999.
[34] B. Lee, H. Kim, and K. Kim, “Strong proxy signature and its applications,” In
Proceedings of SCIS, 2001.
[35] M. Mambo, K. Usuda, and E. Okamoto, “Proxy Signatures: Delegation of the
Power to Sign Message,” IEICE Trans. Fundamentals, Vol. E79-A, No. 9, pp.
1338-1353, Sep. 1996.
[36] M. Mambo, K. Usuda, and E. Okamoto, “Proxy Signatures for Delegation Signing
Operation,” Proc. Third ACM Conf. on Computer and Communications Security,
pp. 48-57, 1996.
[37] Menezes, Oorschot, and Vanstone, Handbook of Applied Cryptographt, CRC
Press, pp. 504, 1997.
[38] S. Micali, C. Racko and R. H. Sloan, “The notion of security for probabilistic
cryptosystems,” SIAM Journal on Computing, Vol. 17, No. 2, pp. 412–426, April
1988.
[39] M. Naor and O. Reingold, “Number-theoretic constructions of e cient pseudorandom
functions,” Proc. of 38th FOCS, pp. 458–467, 1997.
[40] R. M. Needham and M. D. Schroeder, “Using encryption for authentication in
large networks of computers,” Communications of the ACM, Vol. 21, No. 12, pp.
993–999, December 1978.
[41] B. C. Neuman, “Proxy-based authorization and accounting for distributed systems,”
Proc. 13th International Conference on Distributed Systems, pp. 283-291,
1993.
[42] T. Okamoto, M. Tada, and E. Okamoto, “Extended proxy signatures for smart
cards,”ISW ’99, LNCS 1729, pp. 247-258, 1999.
[43] D. Pointcheval and J. Stern, “Security proofs for signature schemes,” in Advances
in Cryptography-EUROCRYPT’96, LNCS 1070, pp. 387-398, 1996.
[44] R. L. Rivest, “RFC 1321: the MD5 message-digest algorithm”, Internet Activities
Board, 1992.
[45] R. L. Rivest, A. Shamir and L. Adleman, “A method of obtaining digital signatures
and public-key cryptosystems,” Communications of the ACM, Vol. 21, No. 2, pp.
120–126, February 1978.
[46] A. Shamir, ”How to share a secret,” Communications of the ACM, No. 22, pp.
612-613, 1979.
[47] A. Shamir, “Identity-Based Cryptosystems and Signature Schemes,” in Advances
in Cryptography-Crypto’84, pp. 47-53, 1984.
[48] Z. Shao, “Proxy signature schemes based on factoring,”Information Processing
Letters, No. 85, pp. 137-143, 2003.
[49] V. Shoup, ”Practical threshold signatures,” Advances in Cryptology EUROCRYPT’
00, LNCS 1807, Springer-Verlag, pp. 207-220, 2000.
[50] H.M. Sun, “On the design of time-stamped proxy signatures with traceable receivers,”
In IEE Proceedings - Computers and Digital Techniques, Vol. 147, No. 6,
pp. 462-466, Nov. 2000.
[51] H.M. Sun, “An e cient nonrepudiable threshold proxy signature scheme with
known signers,”Computer Comm., Vol. 22, No. 8, pp. 717-722, 1999.
[52] H.M. Sun and B.T. Hsieh, “Remarks on two nonrepudiable proxy signature
scheme,” Proc. of Ninth National Conference on Information Security, pp. 241-
246, 1999.
[53] H.M. Sun and B.T. Hsieh, “On the security of some proxy signature schemes,”
http://eprint.iacr.org/2003/068.
[54] H.M. Sun, N.Y. Lee, and T. Hwang, “Threshold proxy signatures,”IEE
Proceedings-Computers and Digital Techniques, Vol. 146, No. 5, pp. 259-263, 1999.
[55] H.M. Sun, C.T. Yang, and B.T. Hsieh, “On the Security of a Threshold Proxy
Signature Scheme Based on the RSA Cryptosystem,” manuscript, 2004.
[56] H. Tanaka, “A Realization Scheme for the ID-based Cryptosystem,” in Advances
in Cryptography-Crypto’87, pp. 341-349, 1987.
[57] S. Tsuji and T. Itoh, “An ID-Based Cryptosystem based on Discrete Logarithm
Problem,” IEEE Journal on Selected Areas in Communication, vol. 7, no. 4, pp.
467-473, 1989.
[58] V. Varadharajan, P. Allen, and S. Black, “An analysis of the proxy problem in
distributed systems,” Proc. 1991 IEEE Computer Society Symposium on Research
in Security and Privacy, pp. 255-275, 1991.
[59] H. Wang and J. Pieprzyk, “E cient one-time proxy signatures,” in Advances in
Cryptography-ASIACRYPT 2003, LNCS 2894, pp. 507-522, 2003.
[60] L. Yi, G. Bai, and G. Xiao, “Proxy multi-signature scheme: A new type of proxy
signature scheme,” Electroincs Letters, Vol. 36, No. 6, pp. 527-528, 2000.
[61] K. Zhang, “Threshold Proxy Signature Schemes,” Information Security Workshop,
Japan, pp. 191-199, Sep. 1997.
[62] Fangguo Zhang and Kwangjo Kim, “E cient ID-Based Blind Signature and
Proxy Signature from Bilinear Pairings,”In Information Security and Privacy
(ACISP’03), LNCS 2727, pp. 312-323, Springer-Verlag, 2003.