臺灣博碩士論文加值系統

本論文提出並分析一種基於RSA 之新式代理簽章機制及其對應之
門檻式代理簽章機制。此機制和許多先前學者之研究不同的地方在於
本研究所提出之門檻式代理簽章不需信賴者。本文所提出之代理簽章
機制及門檻式代理簽章機制之安全性皆基於標準RSA 假設，並提出此
機制於Random Oracle 模型下之安全性分析。

In this thesis we propose and analyze a new RSA-based proxy signature
scheme and its corresponding (t, ) threshold scheme. Unlike numerous previous
research works, the threshold proxy scheme does not require any trusted
combiner and is thus a truly practical approach. The security of both schemes
is based on the RSA assumption. Both schemes are existentially unforgeable
against no message attack in the random oracle model and especially the
threshold proxy scheme inherits the merit of its predecessor - Shoup’s RSA
threshold scheme - and thus is secure under a multi-party computation setup
with active adversaries.

Contents
1 Introduction 1
2 The Related Works 5
2.1 The HLL-scheme . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 The CC-scheme . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 The Security Model 11
3.1 Intractability Assumption . . . . . . . . . . . . . . . . . . . . 11
3.2 Security Definitions of the Proxy Signature . . . . . . . . . . . 11
3.3 Security Definitions of the Threshold Proxy Signature . . . . . 15
4 An RSA-based Proxy Signature Scheme 20
4.1 Setup. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2 The Proxy Delegation Protocol . . . . . . . . . . . . . . . . . 20
4.3 The Proxy Delegation Verification Protocol . . . . . . . . . . . 21
4.4 The Proxy Signature Signing Protocol . . . . . . . . . . . . . 21
4.5 The Proxy Signature Verification Protocol . . . . . . . . . . . 21
5 An RSA threshold (t, l) Proxy Signature Scheme 23
5.1 Setup. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.2 The Proxy Delegation Protocol . . . . . . . . . . . . . . . . . 23
5.3 The Proxy Delegation Verification Protocol . . . . . . . . . . . 24
5.4 The Proxy Signature Share Generation Protocol . . . . . . . . 25
5.5 The Proxy Signature Share Verification Protocol . . . . . . . . 25
5.6 The Proxy Signature Combining Protocol . . . . . . . . . . . 25
5.7 The Proxy Signature Verification Protocol . . . . . . . . . . . 26
6 Security Analysis 27
6.1 Security Analysis on the Proxy Signature Scheme . . . . . . . 27
6.2 Security Analysis on the Threshold Proxy Signature Scheme . 34
7 Conclusions 37
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

[1] M. Bellare and P. Rogaway, “Random Oracles are Practical: A Paradigm
for Designing Efficient Protocols,” in Proceedings of the First ACM
Conference on Computer and Communications Security, 1993.
[2] A. Boldyreva, A. Palacio, and B.Warinschi, “Secure Proxy Signature
Schemes for Delegation of Signing Rights,” 2003, available at
http://eprint.iacr.org/2003/096.
[3] Y.F. Chang and C.C. Chang, “An RSA-based (t, n) Threshold Proxy
Signature Scheme with Free-will Identities,” in International Journal of
Information and Computer Security, Vol. 1, No. 1/2, pp. 201-209, 2007.
[4] D. Chaum and T. Pedersen, “Wallet Databases with Observers,” in
Advances in Cryptology - Crypto’92, LNCS 740, pp. 89-105, 1992.
[5] I. Damg˚ard and M. Jurik, “A Generalisation, a Simplification and Some
Applications of Paillier’s Probabilistic Public-Key System,” in Proceedings
of Public Key Cryptography - PKC’ 01, LNCS 1992, pp. 119-136,
2001.
[6] I. Damg˚ard and M. Koprowski,“Practical Threshold RSA Signatures
Without a Trusted Dealer,” in Advances in Cryptology - EuroCrypt’
01, LNCS 2045, pp. 152–165, 2001.
[7] W. Diffie and M. Hellman, “New Directions in Cryptography,” in IEEE
Transactions on Information Theory, Vol. IT-22, No. 6, pp. 644-654,
1976.
[8] T. ElGamal, ”A Public-Key Cryptosystem and a Signature Scheme
Based on Discrete Logarithms”, in IEEE Transactions on Information
Theory, Vol. IT-31, No. 4, pp469-472, 1985.
[9] S. Goldwasser, S. Micali, and R. Rivest, “A ”Paradoxical” Solution to
the Signature Problem,” in Proceedings of the 25th Annual Foundations
of Computer Science, ACM, 1984.
[10] L.C. Guillou and J.J. Quisquater, “A “Paradoxical” Identity-Based Signature
Scheme Resulting from Zero-Knowledge,” in Advances in Cryptology
- Crypto’88, LNCS 330, pp. 123-128, 1988.
[11] C.L. Hsu, T.S.Wu, and T.C.Wu, “New Nonrepudiable Threshold Proxy
Signature Scheme with Known Signers,” in The Journal of Systems and
Software, Vol. 58, pp. 119-124, 2001.
[12] M.S. Hwang, I.C. Lin and J. L. Lu, “A Secure Nonrepudiable Threshold
Proxy Signature Scheme with Known Signers,” in Informatica, Vol. 11,
No. 2, pp. 1-8, 2000.
[13] M.S. Hwang, J.L. Lu, and I.C. Lin, “A Practical (t, n) Threshold Proxy
Signature Scheme based on the RSA Cryptosystem,” in IEEE Transactions
on Knowledge and Data Engineering, Vol. 15, No. 6, 2003.
[14] S. Kim, S. Part, and D. Won, “Proxy Signature, Revisited,” in Proceedings
of International Conference on Information and Communication
Security ICICS’97, Beijing, China, pp. 223-232, 1997.
[15] W.C. Kuo and M.Y. Chen, “A Modified (t, n) Threshold Proxy Signature
Scheme based on the RSA cryptosystem,” in Proceedings of the 3rd
International Conference on Information Technology and Applications
(ICITA), 2005.
[16] R. Lu and Z. Cao, “A Proxy-Protected Signature Scheme based on
Conic” in ACM International Conference Proceeding Series, Vol. 85, in
Proceedings of the 3rd International Conference on Information security,
pp. 22-26, 2004.
[17] R.X. Lu, Z.F. Cao, and H.J. Zhu, “A Robust (k,n)+1 Threshold Proxy
Signature Scheme based on Factoring,” in Applied Mathematics and
Computation, vol. 166, pp. 35-45, 2005.
[18] M. Mambo, K. Usuda, and E. Okmamoto, “Proxy Signatures: Delegation
of the Power to Sign Messages,” in IEICE Transactions on Fundamentals,
Vol. E79-A No. 9, pp. 1338-1353, 1996.
[19] M. Mambo, K. Usuda, and E. Okmamoto, “Proxy Signatures for Delegating
Signing Operation,” in Proceedings of 3rd ACM Conference Computer
and Communication Security, pp. 48-57, 1996.
[20] B.C. Neuman, “Proxy-based authorization and accounting for distributed
systems,” in Proceedings of 13th International Conference on
Distributed Systems, pp. 283-291, 1993.
[21] P. Paillier, “Public-key cryptosystems based on composite degree residuosity
classes,” in Advances in Cryptology - Eurocrypt’99, LNCS 1592,
pp. 223-238, 1999.
[22] D. Pointcheval and J. Stern, “Security Arguments for Digital Signatures
and Blind Signatures,” in Journal of Cryptology, Vol. 13, pp. 361-396,
2000.
[23] R. L. Rivest and B. Kaliski, “RSA Problem,” 2003, available at
http://people.csail.mit.edu/rivest/RivestKaliski-RSAProblem.pdf.
[24] R.L. Rivest, A. Shamir, and L.M. Adleman, “A Method for Obtaining
Digital Signatures and Public-Key Cryptosystems,” in Communications
of the ACM, Vol. 21, pp. 120-126, Feb. 1978.
[25] A Shamir, “How to share a secret,” in Communications of the ACM,
Vol. 22, pp. 612-613, 1979.
[26] Z. Shao, “Proxy Signature Schemes based on Factoring,” in Information
Processing Letters, Vol. 85, No. 3, pp. 137-143, 2003.
[27] V. Shoup, “Practical Threshold Signatures,” in Advances in Cryptology
- EuroCrypt’ 00, LNCS 1807, pp. 207-220, 2000.
[28] V. Shoup and R. Gennaro, “Securing Threshold Cryptosystems against
Chosen Ciphertext Attack,” in Journal of Cryptology, Vol. 15, pp. 75-96,
2002.
[29] H.M. Sun, “An Efficient Nonrepudiable Threshold Proxy Signature
Scheme with Known Signers,” in Computer Communications, Vol. 22,
No. 8, pp. 717-722, 1999.
[30] H.M. Sun, “Threshold Proxy Signatures,” in IEE Proceedings of Computers
Digital Techniques, Vol. 146, No. 5, pp. 259-263, Sep. 1999.
[31] H.M. Sun, C.T. Yang, and B.T. Hsieh, “Cryptanalysis of a Threshold
Proxy Signature Scheme,” in Proceedings of 14th Information Security
Conference, 2004.
[32] G. Wang, F. Bao, J. Zhou and R.H. Deng, “Security Analysis of Some
Proxy Signatures,” in Proceedings of International Conference on Information
Security and Cryptology ICICS’03, Mongolia, China, pp. 305-
319, 2004.
[33] G. Wang, F. Bao, J. Zhou, R.H. Deng, and I.C. Lin, “Comments on
”A Practical (t, n) Threshold Proxy Signature Scheme based on the
RSA cryptosystem”,” in IEEE Transactions on Knowledge and Data
Engineering, Vol. 16, No. 10, 2004.
[34] K. Zhang, “Threshold Proxy Signature Schemes,” in Proceedings of Information
Security Workshop - ISW’97, California U.S.A., pp. 282-290,
1997.