臺灣博碩士論文加值系統

本論文提出一種門檻式 Paillier 代理簽章機制。Paillier 密碼系統的加法同形性質，加上代理簽章機制以及門檻信任模型，使得在設計電子投票系統或電子投標系統時，它比其他密碼系統還要方便。 在隨機智者模型下，證明本文中所提出的方法能抵抗選擇明文攻擊者的攻擊，並具有：不可偽造性、保護代理簽章者、不可否認性、祕密性以及可分辨代理簽章者等安全性質。本機制所用的假設和 Paillier 密碼系統相同，都是基於計算合成數模數 n 次方根問題的困難性。

In this thesis, a threshold Paillier proxy signature scheme is proposed. The additive homomorphism of the Paillier cryptosystem, together with the proxy mechanism and the threshold trust make it more convenient than other probabilistic cryptosystems in designing electronic voting systems or electronic auction systems. In this thesis, this scheme is proven to be unforgeabile, proxy-protected, undeniabile, secret and signer-identi?able against chosen message attackers in the random oracle model. These security properties of this scheme are based on the computational composite residuosity assumption.

1 Introduction 1
2 Basic tools 6
2.1 Public Key Cryptosystem . . . . . . . . . . . . . . . . . . . . 6
2.2 Paillier Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.2 Encryption and Decryption . . . . . . . . . . . . . . . 8
2.2.3 Digital Signature and Veri?cation . . . . . . . . . . . . 8
2.2.4 Some Important Properties . . . . . . . . . . . . . . . 9
2.3 Modi?ed Setting in QRn2 . . . . . . . . . . . . . . . . . . . . . 10
2.3.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.2 Encryption and Decryption . . . . . . . . . . . . . . . 11
2.3.3 Some Properties of the Modi?ed Setting . . . . . . . . 12
2.4 Paillier Proxy Signature . . . . . . . . . . . . . . . . . . . . . 18
2.4.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.2 Proxy Delegation Protocol . . . . . . . . . . . . . . . . 18
2.4.3 Proxy Signature Signing Protocol . . . . . . . . . . . . 19
2.4.4 Proxy Signature Veri?cation Protocol . . . . . . . . . . 19
3 The Security Model 20
3.1 Intractability Assumption . . . . . . . . . . . . . . . . . . . . 20
3.2 Security De?nitions of a Threshold Proxy Signature . . . . . . 21
4 A Paillier (d, `)-threshold Proxy Signature Scheme 27
4.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 Proxy Delegation Protocol . . . . . . . . . . . . . . . . . . . . 28
4.3 Proxy Key Veri?cation Protocol . . . . . . . . . . . . . . . . . 29
4.4 Proxy Signature Signing Protocol . . . . . . . . . . . . . . . . 30
4.5 Proxy Signature Share Veri?cation Protocol . . . . . . . . . . 31
4.6 Proxy Signature Combination Protocol . . . . . . . . . . . . . 31
4.7 Proxy Signature Veri?cation Protocol . . . . . . . . . . . . . . 33
4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5 Security Analysis 34
6 Conclusions 48
Appendices 49
A The Schnorr Signature 50
B GQ Signature 52
C Decryption with the modi?ed setting 54
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

[1] M. Abe and K. Suzuki, “M+1-st Price Auction Using Homomorphic
Encryption,” PKC’02, LNCS 2274, pp.115-124, 2002.
[2] O. Baudron, P. Fouque, D. Pointcheval, J. Stern, and G. Poupard,
“Practical Multi-Candidate Election System,” ACM 20-th Symposium
on Principle of Distributed Computing, PODC’01, pp.274-283, 2001.
[3] M. Bellare and P. Rogaway, “The Exact Security of Digital Signatures-
How to Sign with RSA and Rabin,” Advances in Cryptology-
Eurocrypt’96, LNCS 1070, pp.399-416, 1996.
[4] A. Boldyreva, A. Palacio, and B. Warinschi, “Secure Proxy Sig-
nature Schemes for Delegation of Signing Rights,” available at
http://venona.antio?ine.com/2003/096.pdf.
[5] Y. F. Chang and C. C. Chang, “An RSA-based (t, n) Threshold Proxy
Signature Scheme with Free-will Identities,” International Journal of
Information and Computer Security, Vol. 1, No. 1/2, pp.201-209, 2007.
[6] I. Damg?ard and M. Jurik, “A Generalisation, a Simpli?cation and Some
Applications of Paillier’s Probabilistic Public-Key System,” PKC’01,
LNCS 1992, pp.119-136, 2001.
[7] Y. Desmedt, “Society and Group Oriented Cryptography,” Advances in
Cryptology-Crypto’87, LNCS 293, pp.120-127, 1987.
[8] Y. Desmedt and Y. Frankel, “Shared Generation of Authenticators and
Signatures,” Advances in Cryptology-Crypto’91, LNCS 576, pp.457-469,
1991.
[9] W. Di?e and M. E. Hellman, “New Directions in Cryptography,” IEEE
Transactions on Information Theory, Vol. IT-22, No. 6, pp.644-654,
1976.
[10] T. ElGamal, “A Public-Key Cryptosystem and a Signature Scheme
based on Discrete Logarithms,” IEEE Transactions on Information The-
ory, Vol. IT-31, No. 4, pp.469-472, 1985.
[11] A. Fiat and A. Shamir, “How to Prove Yourself: Practical Solutions
to Identi?cation and Signature Problems,” Advances in Cryptology-
Crypto’86, LNCS 263, pp.186-194, 1986.
[12] S. Goldwasser, S. Micali, and R. Rivest, “A ‘Paradoxical’ Solution to
the Signature Problem,” Advances in Cryptology-Crypto’84, LNCS 196,
pp.441-448, 1984.
[13] L. C. Guillou and J.-J. Quisquater, “A ‘Paradoxical’ Identity-based
Signature Scheme Resulting from Zero-Knowledge,” Advances in
Cryptology-Crypto’88, LNCS 403, pp.216-231, 1988.
[14] C.-H. Hseu, A Secure Paillier Proxy Signature Scheme, Master thesis,
Dept. of Computer Science and Engineering, National Taiwan Ocean
University, 2006.
[15] C. L. Hsu, T. S. Wu, and T. C. Wu, “New Nonrepudiable Threshold
Proxy Signature Scheme with Known Signers,” Journal of Systems and
Software, Vol. 58, pp. 119-124, 2001.
[16] X.-W. Huang, An RSA-based (t,n) Threshold Proxy Signature Scheme
without a Trusted Combiner, Master thesis, Dept. of Computer Science
and Engineering, National Taiwan Ocean University, 2007.
[17] M. S. Hwang, J. L. Lu, and I. C. Lin, “A Practical (t, n) Threshold Proxy
Signature Scheme based on the RSA Cryptosystem,” IEEE Transactions
on Knowledge and Data Engineering, Vol. 15, No. 6, pp.1552-1560, 2003.
[18] S.-J. Hwang and C.-H. Shi, “A Simple Multi-proxy Signature Scheme,”
Proceedings of the Tenth National Conference on Information Security,
pp.134-138, 2000.
[19] H. Javier and S. German, “Revisiting Fully Distributed Proxy Signature
Schemes,” Progress in Cryptology-Indocrypto’04, LNCS 3348, pp.356-
370, 2004.
[20] H. Kim, J Baek, B. Lee, and K. Kim, “Secret Computation with Secrets
for Mobile Agent Using One-time Proxy Signature,” SCIS’01, pp.845-
850, 2001.
[21] S. Kim, S. Park, and D. Won, “Proxy Signatures, Revised,” ICICS’97,
LNCS 1334, pp.223-232, 1997.
[22] W. C. Kuo and M. Y. Chen, “A Modi?ed (t, n) Threshold Proxy Signa-
ture Scheme based on the RSA cryptosystem,” ICITA’05, Vol. 2, pp.576-
579, 2005.
[23] R. Lu and Z. Cao, “A Proxy-Protected Signature Scheme based on
Conic,” ACM the 3rd International Conference on Information Secu-
rity, pp.22-26, 2004.
[24] R. X. Lu, Z. F. Cao, and H. J. Zhu, “A Robust (k,n)+1 Threshold
Proxy Signature Scheme based on Factoring,” Applied Mathematics and
Computation, Vol. 166, pp.35-45, 2005.
[25] M. Mambo, K. Usuda, and E. Okmamoto, “Proxy Signatures: Delega-
tion of the Power to Sign Messages,” IEICE Transactions on Fundamen-
tals E79-A, No. 9, pp.1338-1353, 1996.
[26] M. Mambo, K. Usuda, and E. Okmamoto, “Proxy Signatures for Dele-
gating Signing Operation,” Proceedings of 3rd ACM Conference Com-
puter and Communication Security, pp.48-57, 1996.
[27] P. Paillier, “Public-key Cryptosystems based on Composite Degree
Residuosity Classes,” Advances in Cryptology-Eurocrypt’99, LNCS
1592, pp.223-238, 1999.
[28] D. Pointcheval and J. Stern, “Security Arguments for Digital Signatures
and Blind Signatures,” Journal of Cryptology, Vol. 13, pp.361-396, 2000.
[29] R. L. Rivest, A. Shamir, and L. M. Adleman, “A Method for Obtaining
Digital Signatures and Public-Key Cryptosystems,” Communications of
the ACM, Vol. 21, pp.120-126, 1978.
[30] C. P. Schnorr, “E?cient Signature Generation by Smart Card,” Journal
of Cryptology, Vol. 4, pp.161-174, 1991.
[31] A. Shamir, “How to Share a Secret,” Communication of ACM, Vol.22,
No. 11, pp.612-613, 1979.
[32] D. Shanks, Solved and Unsolved Problems in Number Theory, American
Mathematical Society, 2001.
[33] Z. Shao, “Proxy Signature Schemes based on Factoring,” Information
Processing Letters, Vol. 85, No. 3, pp.137-143, 2003.
[34] V. Shoup, “Practical Threshold Signatures,” Advances in Cryptology-
Eurocrypt’00, LNCS 1807, pp.207-220, 2000.
[35] V. Shoup and R. Gennaro, “Securing Threshold Cryptosystems Against
Chosen Ciphertext Attack,” Advances in Cryptology-Eurocrypt’98,
LNCS 1403, pp.1-16, 1998.
[36] K. Shum and V. K. Wei, “A Strong Proxy Signature Scheme with Proxy
Signer Privacy Protection,” 11th IEEE International Workshops on En-
abling Technologies: Infrastructure for Collaborative Enterprises, pp.55-
56, 2002.
[37] D. Stinson, Cryptography Theory and Practice, CRC Press, 2nd Ed.,
2002.
[38] H.-M. Sun, N. Y. Lee, and T. Hwang, “Threshold Proxy Signatures,”
Computers and Digital Techniques, Vol. 146, No. 5, pp.259-263, 1999.
[39] H.-M. Sun, “An E?cient Nonrepudiable Threshold Proxy Signature
Scheme with Known Signers,” Computer Communication, Vol. 22, No.
8, pp.717-722, 1999.
[40] W. Trappe and L. C. Washington, Introduction to Cryptography with
Coding Theory, Prentice Hall, 1st Ed, 2002.
[41] 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’,” IEEE Transactions on Knowledge and Data Engineer-
ing, Vol. 16, No. 10, pp.1309-1311, 2004.
[42] H.X. Wang and J. Pieprzyk, “E?cient One-time Proxy Signatures,”
Advanced in Cryptology-Asiacrypt’03, LNCS 2894, pp.507-522, 2003.
[43] Weisstein and W. Eric, “Carmichael’s Theorem,”
MathWorld-A Wolfram Web Resource, available at
http://mathworld.wolfram.com/CarmichaelsTheorem.html.
[44] L. Yi, G. Bai, and G. Xiao, “Proxy Multi-signature Scheme: A New
Type of Proxy Signature Scheme,” Electronics Letters, Vol. 36, No. 6,
pp.527-528, 2000.
[45] K. Zhang, “Threshold Proxy Signature Schemes,” 1997 Information Se-
curity Workshop, pp.191-197, 1997.