Auditable and verifiable electronic voting with homomorphic RSA tallying


Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Enformatik Enstitüsü, Bilişim Sistemleri Anabilim Dalı, Türkiye

Tezin Onay Tarihi: 2010

Öğrenci: OKAN YÜCEL

Danışman: NAZİFE BAYKAL

Özet:

In this work, we investigate the general structure and the concepts behind the contemporary electronic voting schemes, with special emphasis on voter verifiable preferential voting, homomorphic tallying and voter privacy. We firstly propose a modification in the Single Transferable Voting (STV) method to be applied to large scale elections with electoral barriers. Our proposal prevents the loss of votes and distributes them securely to the second or higher choices of their voters. This method is most suitably used in e-voting with the voter verifiable “Prêt à Voter: All-In-One” scheme that utilizes mix-networks for anonymity. We present a case study considering 2007 Turkish Parliamentary Elections to demonstrate the effect of preferential voting on the election systems that have electoral barriers. After the mathematical formulation of the election procedure, we calculate the wasted votes in 2007 elections and present simulation results for 69 election regions (that have no independent parliament members) by using a combination of “modified STV and d’Hondt” methods, according to four different, politically unbiased scenarios on the distribution of secondary vote choices. Additionally, we modify the “Prêt à Voter: All-In-One” scheme by proposing three security enhancing modifications in its ballot construction phase: 1) ballot serial number, 2) digital signature of the first clerk in the mix-net, 3) different random numbers for each row of the ballot. Finally, we demonstrate the potential of multiplicative homomorphic algorithms like RSA for homomorphic tallying. The idea is based on the association of each candidate on the electronic ballot with a prime number, and unique prime factorization of the general vote product. We propose novel randomization methods for homomorphic RSA tallying, and discuss the performance and complexity of the scheme with such randomizations. Our suggestion for an auditable and verifiable e-voting scheme that employs homomorphic RSA tallying with proper randomization has advantages over El Gamal and Paillier tallying, such as having the least encryption complexity and strong anonymity resistant to unlimited computational power.