臺灣博碩士論文加值系統

目前資訊技術迅速地發展、網路無遠弗屆地普及，一方面為我們帶來許多便利，一方面隨之而來的網路安全問題也日趨複雜，再一方面我們看到這個網路科技世界也成為民主運作的新平台，網際網路儼然成為將來候選人主要的戰場之一。
本篇基於Paillier同形密碼系統建構一個安全的電子化單一可轉讓投票系統(Single Transferable Voting；STV)，此系統符合了一般選舉應該有的性質：完整性、合格性、不可重複性、公平性、可驗證性、強固性、以及私密性，是一個具有實用價值的方法。

The fast advances of information technologies and the ubiquitous Internet bring us so much convenience on the one hand. However, the complex security issues accompanying these handy accesses become dominating factors. On the other hand, the integration of network and information technologies also provides a new platform for the democratic operations. The Internet is becoming one of the main battlefields for all kinds of elections.
This thesis proposed a secure electronic “single transferable voting” based on the Paillier homomorphic encryption system. It meets the basic requirements for secure e-voting, such as completeness, eligibility, un-reusability, fairness, public verifiability, soundness, and privacy. It is practical to be used in a small-scale election.

中文摘要 I
英文摘要 II
致謝 III
目錄 IV

第一章、緒論 1
1.1、 研究動機 1
1.2、 文獻回顧 2
1.3、 研究成果 3
1.4、 章節介紹 3
第二章、電子投票機制基本模型 4
2.1、 參與單位 4
2.2、 選舉過程 5
2.3、 通訊方式 5
2.4、 安全要求 6
第三章、密碼學相關之技術 8
3.1、 Paillier加密系統 8
3.2、 同形加密(Homomorphic Encryption)性質 8
3.3、 秘密分享(Secret sharing) 9
3.4、 零知識證明(Zero-Knowledge proof) 11
3.5、 可公開驗證的Paillier 秘密重排(Shuffle) 14
3.6、 分散式明文相等測試(PET) 18
第四章、單一可轉讓投票系統(STV) 19
4.1、 簡介 19
4.2、 運作模式 19
4.3、 第一版演算法 21
4.4、 範例說明 23
4.5、 第二版演算法 25
第五章、基於Paillier同形加密之單一可轉讓電 28
5.1、 簡介 28
5.2、 選票格式 28
5.3、 選票及位移之合法性証明 31
5.4、 完整選票之格式 35
5.5、 安全的投票協定 35
第六章、效率與安全性分析 41
6.1、 安全性分析 41
6.2、 安全性證明 42
6.3、 效率分析 47
6.4、 攻擊分析 53
第七章、結論與未來工作 55
參考文獻 57

[1] Wikipedia, the free encyclopedia, “Single Transferable Vote,” available at http://en.wikipedia.org/wiki/Single_Transferable_Vote.
[2] P. Paillier, “Public-key Cryptosystems Based on Composite Degree Residuosity Classes,” Advances in Cryptology-Eurocrypt’99, LNCS 1592, pp. 223-238, 1999.
[3] Adi Shamir, “How to share a secret,” Communication of the ACM, Vol.22, pp.612-613, November 1979.
[4] T. P. Pedersen, “A Threshold Cryptosystem Without a Trusted Party,” Advances in Cryptology-Eurocrypt’91, LNCS 547, pp.522-526, 1991.
[5] A. Fiat and A. Shamir, “How To Prove Yourself: Practical Solutions to Identification and Signature Problems,” Advances in Cryptology-Crypto’86, LNCS 263, pp.186-194, 1986.
[6] C. P. Schnorr, “Effficient Signature Generation by Smart Cards,” Journal of Cryptology, Vol.4, No.3, pp.161-174, 1991.
[7] O. Baudron, P.-A. Fouque, D, Pointcheval, G. Poupard and J. Stern, “Practical Multi-Candidate Election System,” In ACM 20-th Symposium on Principe of Distributed Computing, PODC’01, pp.15-19, 2001.
[8] I. Damgård, M. Jurik, and J.B. Nielsen, “A Generalization of Paillier’s Public-Key System with Applications to Electronic Voting,” available at http://citeseer.ist.psu.edu/damgard03generalization.html, 2003.
[9] I. Damgård and M. Koprowski. “Practical Threshold RSA Signatures Without a Trusted Dealer,” Advances in Cryptology-Eurocrypt’01, LNCS 2045, pp.152-165, 2001.
[10] M. Jakobsson and A. Juels, “Mix and Match: Secure Function Evaluation via Ciphertexts,” Advances in Cryptology-Asiacrypt’00, LNCS 1976, pp. 162-177, 2000.
[11] R. Adity, “Secure Electronic Voting with Flexible Ballot Structure,” available at http://www.isi.qut.edu.au/people/riza/publications/0511_phd_thesis-print. pdf, pp.43-46, November, 2005.
[12] J. Furukwa and K. Sako, “An Efficient Scheme for Proving a Shuffle,” Advances in Cryptology-Crypto’01, LNCS 2139, pp.368-387, 2001.
[13] Lan Nguyen, Rei Safavi-Naini, and Kaoru Kurosawa, “Verifiable Shuffles：A Formal Model and a Paillier-Based Efficient Construction with Provable Security,” ACNS 2004, LNCS 3089, pp.61-75, 2004.
[14] John J. Bartholdi and James B. Orlin, “Single Transferable Vote Resists Strategic Voting,” November 13,1990; revised April 4, 2003, available at http://www2.isye.gatech.edu/~jjb/papers/stv.pdf.
[15] K. J. Arrow, “Individual Values and Social Choice,” John Wiley & Sons, New York, 2nd Ed. 1963.
[16] M. Pivato, “Introduction to Voting Theory,” available at http://xaravve.trentu.ca/pivato, February 2, 2004.
[17] C. A. Neff, “A Veriable Secret Shuffle and its Application to E-Voting,” ACM CCS’01, pp. 116-125, 2001.
[18] A. Fujioka, T. Okamoto, and K. Ohta, “A Practical Digital Multisignature Scheme Based on Discrete Logarithms,” Advances in Cryptology – AusCrypt’92, LNCS 718, pp. 244-251, 1992.
[19] K. Sako and J. Killian, “Secure Voting using Partial Compatible Homomorphism,” Advances in Cryptology-Crypto’94, LNCS 839, pp.411-424, 1994.
[20] R. Cramer, R. Gennaro, and B. Schoenmakers, “A Secure and Optimally Efficient Multi-Authority Election Scheme,” Advances in Cryptology –European’97, LNCS 1233, Vol.??, pp.103-118, 1997.
[21] B. Schoenmakers, “Fully Auditable Electronic Secret-Ballot Elections,” available at http://www.win.tue.nl/~berry.
[22] B. Wichmann, “A Technical Description of the Single Transferable Vote,” available at http://www.math.duke.edu/~robbins/mgso/ stvtechnical.pdf, March 17, 2003.
[23] C. A. Neff, “Verifiable Mixing (shuffling) of ElGamal Pairs,” available at http://theory.lcs.mit.edu/~rivest/voting/papers/Neff-2004-04-21-ElGamalShuffles.pdf, December 1, 2003.
[24] R. Li and C. K. Wu, “Co-operative Private Equality Test,” International Journal of Network Security, Vol.1, No.3, pp.149-153, Nov, 2005.
[25] C. Geller, “Single Transferable Vote with Borda Elimination：A New Vote Counting System,” available at http://www.deakin.edu.au/buslaw/aef/ publications/wp/wp2201.pdf, May, 2002.
[26] O. Goldreich, Foundations of Cryptography-Volume Ⅱ, Basic Applications, Cambridge Press, 2004.