Auditable and verifiable electronic voting with homomorphic RSA tallying

Abstract

Bu çalısmada, çağdas elektronik oylama sistemlerinin genel yapısı ve arka planındakikavramlar, seçmen izlemeli ve tercihli oylamalarla, homomorfik sayımlar ve seçmengizliliğine özel vurguyla incelenmistir. Öncelikle, Tek Geçisli Oylama (TGO)yönteminin, seçim barajı içeren büyük ölçütlü seçimlerde kullanımına yarayan birdeğisiklik önerilmistir. Bu önerimiz, seçim barajı altında kalan partilerin oylarını,seçmenlerinin ikinci veya daha sonraki tercihlerine güvenli bir sekilde dağıtarak,oyların ziyan olmasını engelleme amaçlıdır. E-oylama için en uygunu, bu yöntemin,seçmen izlemeli ve anonimliği sağlamak için karıstırıcı ağlardan yararlanan ?Prêt àVoter: All-In-One? ile birlikte kullanımıdır.2007 Türk Parlamenter seçimleri için, tercihli oylamanın barajlı seçimlere etkisinigösteren bir örnek çalısma yapılmıstır. Seçim prosedürünün matematikselformülasyonundan sonra, 2007 seçimlerinde bağımsız aday çıkarmamıs olan 69seçim bölgesinde bosa giden oylar hesaplanmıs; ve seçmenlerin ikincil tercihleriüzerinde dört tarafsız senaryoya göre, ?değistirilmis TGO ve d'Hondt? yöntemlerinibirlikte kullanan simülasyon sonuçları sunulmustur.Çalısmamızda ayrıca, ?Prêt à Voter: All-In-One? yönteminin oy pusulası hazırlamafazı için üç güvenlik arttırıcı değisiklik önerilmistir: 1) pusula seri numarası 2)karıstırıcı ağdaki ilk görevlinin sayısal imzası, 3) oy pusulasının her satırı için ayrıbir rasgele sayı üretilmesi.Son olarak, RSA gibi çarpmaya göre homomorfik algoritmaların homomorfik sayımaçısından potansiyeli gösterilmistir. Anafikir, elektronik oy pusulasında her adayınbir asal sayıyla ifade edilmesine ve genel oy çarpımının yalnız tek bir sekilde asalçarpanlarına ayrılabilmesine dayanmaktadır. Homomorfik RSA sayımı için farklırassallastırma (rasgelelestirme) yöntemleri önerilmis; bu durumdaki basarım vekarmasıklık tartısılmıstır. Önerdiğimiz rassallastırılmıs homomorfik RSA sayımlı,izlenebilir ve denetlenebilir e-oylama yönteminin, homomorfik El Gamal ya daPaillier sayımıyla karsılastırıldığında, en az sifreleme karmasıklığı gerektirme vesınırsız hesaplama gücüne dayanıklı bir sekilde gizlilik (anonimlik) sağlama gibiavantajları vardır.

In this work, we investigate the general structure and the concepts behind thecontemporary electronic voting schemes, with special emphasis on voter verifiablepreferential voting, homomorphic tallying and voter privacy. We firstly propose amodification in the Single Transferable Voting (STV) method to be applied to largescale elections with electoral barriers. Our proposal prevents the loss of votes anddistributes them securely to the second or higher choices of their voters. This methodis 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 todemonstrate the effect of preferential voting on the election systems that haveelectoral barriers. After the mathematical formulation of the election procedure, wecalculate the wasted votes in 2007 elections and present simulation results for 69election regions (that have no independent parliament members) by using acombination 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 threesecurity enhancing modifications in its ballot construction phase: 1) ballot serialnumber, 2) digital signature of the first clerk in the mix-net, 3) different randomnumbers for each row of the ballot.Finally, we demonstrate the potential of multiplicative homomorphic algorithms likeRSA for homomorphic tallying. The idea is based on the association of eachcandidate on the electronic ballot with a prime number, and unique primefactorization of the general vote product. We propose novel randomization methodsfor homomorphic RSA tallying, and discuss the performance and complexity of thescheme with such randomizations. Our suggestion for an auditable and verifiable evotingscheme that employs homomorphic RSA tallying with proper randomizationhas advantages over El Gamal and Paillier tallying, such as having the leastencryption complexity and strong anonymity resistant to unlimited computationalpower.