臺灣博碩士論文加值系統

傳統電子投票系統都針對大型投票設計，由於投票人數眾多，直接公布候選者的得票數，並無法追溯投票者的選票流向。本論文研究適用於投票人數限制於數百人以下的中小型電子投票系統，例如：小型董事會議。這樣的投票系統必須符合“隱藏候選者得票數”的隱私需求，更進一步保障投票者的隱私，免除對於公正第三者的依賴。
本論文提出兩種電子投票機制，都基於ElGamal密碼系統的同形性質、利用電子佈告欄作為通訊管道，以及投票者對於每一位候選者產生“選與不選”的密文組成選票，並產生零知識證明保證選票的格式正確。在決定當選者時並不直接解密候選者之得票數密文，第一種方法應用混序網路並以基於混序比對的演算法隱藏候選者得票數及得票數之間的差距；第二種方法應用不同的向量化混序網路，透過混序比對來轉換候選者得票數之格式並進行隱藏票數之開票，最後僅公佈超過某門檻值得票數的當選者。

Traditional electronic voting systems are all designed for large-scale election schemes. Because the number of voters in a large-scale voting scheme is numerous such tat announcing the received vote-count of each candidate directly leaks little information about a voter’s vote. This thesis studies and develops algorithms for medium- and small-scale electronic voting systems in which the number of voters is limited to several hundreds, e.g. the meeting of the board of a company. The proposed electronic voting system conforms to the privacy requirement of “hiding the received vote-count of each candidate”, one step further in the attempt to hide the voter’s privacy, without relying to any third party.
This thesis proposes two electronic voting mechanisms, both based on top of the ElGamal Homomorphic cryptosystem, and using the electronic bulletin board as the communication channel. The ballots consist of separate encrypted ‘yes/no’ vote for each candidate in order to implement the ‘Approval voting’. The correctness of each ballot is guaranteed through ZKPs. In the winner determination stage, the first method uses the “mix-net” and the “mix-and-match” subprotocol in order to hide the differences of the received vote-counts across different candidates. The second method uses the “vectorized mix-net” and the “mix-and-match” subprotocol for transforming the received vote-counts to their equivalent vector presentations and determining the set of winners. The results are those winners for this election scheme. The received vote-count for each candidate is hided as much as possible for both methods.

中文摘要..................................................Ⅱ
英文摘要..................................................Ⅲ
誌謝......................................................Ⅴ
目錄......................................................Ⅵ
第一章、 緒論.............................................1
1.1、 研究動機.........................................1
1.2、 研究成果.........................................1
1.3、 章節介紹.........................................2
第二章、 電子投票的基本模型...............................3
2.1、 參與單位.........................................3
2.2、 選舉形式.........................................3
2.3、 運作過程.........................................5
2.4、 通訊方式.........................................5
2.5、 特性要求.........................................6
第三章、 密碼學相關理論與技術.............................8
3.1、 秘密分享.........................................8
3.2、 同形加密性質....................................11
3.3、 盲簽章..........................................12
3.4、 零知識證明......................................12
3.5、 混序網路........................................16
3.6、 向量化混序網路..................................18
3.7、 混序比對........................................23
第四章、 現有電子投票機制...............................27
4.1、 電子投票機制發展歷程............................27
4.2、 基於匿名管道以及盲簽章的電子投票機制............28
4.3、 基於機率式密碼系統同形加密性質的電子投票機制....30
4.4、 結合匿名管道與同形加密性的電子投票機制..........32
4.5、 應用於陪審團的表決機制..........................34
第五章、 可隱藏得票數且可公開驗證的小型電子投票機制(一)..36
5.1、 介紹............................................36
5.2、 模型............................................37
5.3、 安全的投票協定..................................38
5.4、 效率與安全性分析................................44
第六章、 可隱藏得票數且可公開驗證的小型電子投票機制(二)..47
6.1、 介紹............................................47
6.2、 模型............................................48
6.3、 安全的投票協定..................................48
6.4、 效率與安全性分析................................52
第七章、 結論與未來工作.................................56

[Abe98] M. Abe, “Universally verifiable MIX with verification work independent of the number of MIX servers”, Advanced in Cryptology – Eurocrypt 1998, LNCS 1403, 1998.
[Acq04] A. Acquisti, “Receipt-Free Homomorphic Elections and Write-in Ballots”, 2003, www.heinz.cmu.edu/acquisti/research.htm.
[AS02] M. Abe and K. Suzuki, “M+1-st Price Auction Using Homomorphic Encryption”, PKC 2002, LNCS 2274, pp. 115-124, 2002.
[Arr63] K. J. Arrow. “Individual Values and Social Choice”. John Wiley & Sons, New York, 2nd Ed. 1963.
[BFPSP01] 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, 2001.
[BF88] Manuel Blum, Paul Feldman, “Non-Interactive Zero Knowledge and It’s applications”, In Proceedings of the twentieth ACM Syrup. Theory of Computing, STOC, pp. 103-112, 1988.
[Ben87] J. C. Benaloh, “Verifiable Secret Ballot Elections”, Ph.D. thesis, Yale University, 1987.
[BG93] M. Bellare and P. Rogaway, “Random oracles are practical: A paradigm for designing efficient protocols”, In Proc. 1st ACM Conference on Computer and Communications Security, 1993.
[Cha81] D. Chaum, “Untraceable electronic mail, return address, and digital pseudonym”, Communication of ACM 24, Feb 1981.
[Cha83] D. Chaum, “Blind signatures for untraceable payments”, Advanced in Cryptology – Crypto 1982, pp. 199-203, 1982.
[Cha02] D. Chaum, “Secret-ballot receipts and transparent integrity”, Draft, 2002. www.vreceipt.com/article.pdf.
[CP92] D. Chaum and T. Pedersen, “Wallet Databases with Observers”, Advanced in Cryptology – Crypto 1992, pp. 89-105, 1992.
[CDNO97] R. Canetti, C. Dwork, M. Naor and R. Ostrovsky, Denyable Encryption, Advances in Cryptology – CRYPTO’97, LNCS 1294, Springer, 1997, pp. 90-104.
[CGS97] R. Cramer, R. Gennaro, and B. Schoenmakers, “A Secure and Optimally Efficient Multi-Authority Election Scheme”, Advanced in Cryptology – Eurocrypt 1997, LNCS 1233, pp. 119-136, 1997.
[CP92] D. Chaum and T. P. Pedersen, “Wallet Databases with Observers”. CRYPTO 1992: 89-105
[EG85] T. ElGamal, “A Public-key Cryptosystem and Signature Scheme Based on Discrete Logarithms”, IEEE Trans. on Information Theory, Vol. IT-31, pp. 469-472, 1985.
[FS86] A. Fiat and A. Shamir, “How To Prove Yourself: Practical Solutions to Identification and Signature Problems”, Advances in Cryptology: Proc. Crypto’86, pp.186-194, 1986.
[Fel87] P. Feldman, “A practical scheme for non-interactive verifiable secret sharing”, In Proc. 28th IEEE Symposium on Foundations of Computer Science (FOCS’87), pages 427-437, IEEE Computer Society, 1987.
[FOO92] A. Fujioka, T. Okamoto, and K. Ohta, “A practical secret voting scheme for large scale elections”, Advanced in Cryptology – AUSCRYPT’92, 1992.
[GK03] S. Goldwasser and Y. T. Kalai, “On the (In)security of the Fiat-Shamir Paradigm”, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science(FOCS’03).
[GMW87] O. Goldreich, S. Micali, and A. Wigderson, “How to Play Any Mental Game”, ACM STOC’87, 1987
[GMR85] Goldwasser. S, S. Micali and C. Rackoff, “Knowledge Complexity of Interactive Proof Systems”, Proceedings of STOC’85, pp. 291-304.
[Gro04] J. Groth, “Evaluating Security of Voting Schemes in the Universal Composability Frmework”, Proc. ACNS’04, 2004.
[Gen99] R. Gennaro et al. “Secure Distributed Key Generation for Discrete-Log Based Cryptosystems”, Advances in Cryptology: Proc. Eurocrypt’99, pp. 293-310, 1999.
[HS00] M. Hirt and K. Sako, “Efficient receipt-free voting based on homomorphic encryption”, Advanced in Cryptology – Eurocrypt’00, 2000.
[HK02] Hevia and Kiwi, “Electronic Jury Voting Protocols”. Proc. of the 5th Latin American Symposium on Theoretical Informatics (LATIN'02), ancun, exico, pp. 415-429
[JJ00] M. Jakobsson and A. Juels, “Mix and Match: Secure Function Evaluation via Ciphertexts”, Advanced in Cryptology – Asiacrypt’00, pp. 162-177, 2000.
[JJ99] M. Jakobsson and A. Juels, “Millimix: Mixing in Small Batches”, Tech. Rep. 99-33, DIMACS, 1999.
[JJ02] A. Juels and M. Jakobsson, “Coercion-resistant electronic elections”, 2002. citeseer.nj.nec.com/555869.html.
[KY04] A. Kiayias and M. Yung, “The vector-ballot e-voting approach”, 2004. Mimeo, University of Connecticut and Columbia University.
[Nef03] A. Neff, “Detecting malicious poll site voting clients”, 2003. http://www.votehere.net/.
[Ped91] T. P. Pedersen, “A Threshold Cryptosystem without a Trusted Party”, Advanced in Cryptology – Eurocrypt 1991, pp. 522-526, 1991.
[Pai99] P. Paillier, “Public-Key Cryptosystems Based on Discrete Logarithms Residues”. In Eurocrypt’99, LNCS 1592. Springer-Verlag, 1999.
[Rad95] M. J. Radwin, “An untraceable, universally verifiable voting scheme”, 1995, available at http://www.radwin.org/michael/projects/voting.html.
[Riv91] R. Rivest, “Electronic Voting”, Financial Cryptography’91, 1991.
[Rja02] Z. Rjaskova, “Electronic Voting Schemes”, Ms Thesis, Comenius University, Bratislava, 2002.
[Sha79] Adi Shamir, “How to share a secret”, Communication of the ACM, 22:612-613, 1979.
[Sch91] C. P. Schnorr, “Effficient Signature Generation by Smart Cards”, Journal of Cryptology 1991.
[Sch99] Berry Schoenmakers. “A simple publicly verifiable secret sharing scheme and its application to electronic voting”, Advances in Cryptology-CRYPTO, 1666 of Lecture Notes in Computer Science: 148-164, 1999.
[TL03] P.-Y. Ting, Y.-T. Lee, C.-Y. Chen “On The Public Verifiability of an M+1-st Price Auction Using Homomorphic Encryption”, Taiwan ISC, 2004.