TU Darmstadt / ULB / TUbiblio

Universally Verifiable Poll-Site Voting Schemes Providing Everlasting Privacy

Demirel, Denise (2014)
Universally Verifiable Poll-Site Voting Schemes Providing Everlasting Privacy.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

Computer based voting brings up huge challenges for technology. On the one hand an electronic voting system has to be transparent enough to allow verification of its correct functioning; on the other hand, it must ensure that these verification procedures do not allow an attacker to violate voter privacy. Both requirements can be addressed by providing cryptographically secured voting receipts. Each voter cast his or her vote in encoded form and receives a copy of the recorded ballot as receipt. The voters can use these receipts to verify that their vote is contained in the input of the tally. Furthermore, the encoded votes are publicly processed, which allows voters and observers to check that the election outcome has been determined correctly. However, to provide a private and free election, no voter should be able to prove to someone else for whom he or she voted. This must not only be prevented during the election, but also afterwards for an indefinite period of time. Especially with respect to everlasting privacy this is not ensured by most verifiable voting systems. If the receipt contains, for instance, the voting decision encrypted using some public key cryptography, an attacker can determine the candidates selected as soon as the underlying computational problem has been solved for the key length chosen. In this work we provide a summary of privacy weaknesses that may arise in verifiable electronic poll-site voting systems, and we identify and solve open issues. More precisely, we concentrate on the following three questions: (1) How can we show correct anonymization of votes in an efficient and privacy preserving manner using a generic approach? (2) How can we introduce everlasting privacy to mixing and homomorphic tallying based voting schemes? (3) How can we reduce the amount of trust voters have to put in authorities regarding privacy? In electronic voting so-called reencryption mix-nets are used to anonymize votes. These mix-nets shuffles votes in a universally verifiable manner, i.e., they publish some audit information allowing voters and observers to verify that the votes came out as they went in. In practice, mostly generic verification procedures are used to show correctness of this process. However, many of them do not provide an adequate level of privacy. To address (1), we investigate several proposals and introduce a new protocol that combines existing approaches but improves them with respect to privacy and efficiency. Another drawback of mixing based voting schemes is that all implementations provide computational privacy only. We address (2) by presenting a mix-net that uses a homomorphic and unconditionally hiding commitment scheme to encode the votes and audit data, implying everlasting privacy. The correctness of the anonymization process is guaranteed with overwhelming probability, even if all authorities collaborate. An implication of our result is that many current voting systems that use mix-nets can be upgraded to everlasting privacy. Subsequently, we show that this protocol can be applied to Prêt à Voter and Split-Ballot imposing only minor changes to current implementations. The same approach is used to introduce everlasting privacy to homomorphic tallying based schemes. The votes are encoded with an unconditionally hiding commitment scheme, they are homomorphically tallied in public, and the result is decoded afterwards. To show that our solution can be applied to poll-site voting, we describe how the Scratch & Vote voting system can be improved using our tallying protocol. Again only minor changes to the classical scheme are necessary. To address (3), the approach of non-personalized receipts is analyzed. If the receipts handed out to the voters do not contain a link to their vote cast, they do not have to put their trust in authorities keeping this association secret. We introduce an electronic ballot box that generates non-personalized receipts using a process that is similar to the anonymization procedure carried out by mix-nets. The correctness of the receipt generation is universally verifiable. Furthermore, our approach improves on existing solutions with respect to correctness and privacy. Finally, we compare all voting systems that are improved in this work, highlight their advantages and disadvantages, and conclude with key issues for future work.

Typ des Eintrags: Dissertation
Erschienen: 2014
Autor(en): Demirel, Denise
Art des Eintrags: Erstveröffentlichung
Titel: Universally Verifiable Poll-Site Voting Schemes Providing Everlasting Privacy
Sprache: Englisch
Referenten: Buchmann, Prof. Dr. Johannes ; van de Graaf, Prof. Dr. Jeroen
Publikationsjahr: 2014
Datum der mündlichen Prüfung: 3 Dezember 2013
URL / URN: http://tuprints.ulb.tu-darmstadt.de/4019
Kurzbeschreibung (Abstract):

Computer based voting brings up huge challenges for technology. On the one hand an electronic voting system has to be transparent enough to allow verification of its correct functioning; on the other hand, it must ensure that these verification procedures do not allow an attacker to violate voter privacy. Both requirements can be addressed by providing cryptographically secured voting receipts. Each voter cast his or her vote in encoded form and receives a copy of the recorded ballot as receipt. The voters can use these receipts to verify that their vote is contained in the input of the tally. Furthermore, the encoded votes are publicly processed, which allows voters and observers to check that the election outcome has been determined correctly. However, to provide a private and free election, no voter should be able to prove to someone else for whom he or she voted. This must not only be prevented during the election, but also afterwards for an indefinite period of time. Especially with respect to everlasting privacy this is not ensured by most verifiable voting systems. If the receipt contains, for instance, the voting decision encrypted using some public key cryptography, an attacker can determine the candidates selected as soon as the underlying computational problem has been solved for the key length chosen. In this work we provide a summary of privacy weaknesses that may arise in verifiable electronic poll-site voting systems, and we identify and solve open issues. More precisely, we concentrate on the following three questions: (1) How can we show correct anonymization of votes in an efficient and privacy preserving manner using a generic approach? (2) How can we introduce everlasting privacy to mixing and homomorphic tallying based voting schemes? (3) How can we reduce the amount of trust voters have to put in authorities regarding privacy? In electronic voting so-called reencryption mix-nets are used to anonymize votes. These mix-nets shuffles votes in a universally verifiable manner, i.e., they publish some audit information allowing voters and observers to verify that the votes came out as they went in. In practice, mostly generic verification procedures are used to show correctness of this process. However, many of them do not provide an adequate level of privacy. To address (1), we investigate several proposals and introduce a new protocol that combines existing approaches but improves them with respect to privacy and efficiency. Another drawback of mixing based voting schemes is that all implementations provide computational privacy only. We address (2) by presenting a mix-net that uses a homomorphic and unconditionally hiding commitment scheme to encode the votes and audit data, implying everlasting privacy. The correctness of the anonymization process is guaranteed with overwhelming probability, even if all authorities collaborate. An implication of our result is that many current voting systems that use mix-nets can be upgraded to everlasting privacy. Subsequently, we show that this protocol can be applied to Prêt à Voter and Split-Ballot imposing only minor changes to current implementations. The same approach is used to introduce everlasting privacy to homomorphic tallying based schemes. The votes are encoded with an unconditionally hiding commitment scheme, they are homomorphically tallied in public, and the result is decoded afterwards. To show that our solution can be applied to poll-site voting, we describe how the Scratch & Vote voting system can be improved using our tallying protocol. Again only minor changes to the classical scheme are necessary. To address (3), the approach of non-personalized receipts is analyzed. If the receipts handed out to the voters do not contain a link to their vote cast, they do not have to put their trust in authorities keeping this association secret. We introduce an electronic ballot box that generates non-personalized receipts using a process that is similar to the anonymization procedure carried out by mix-nets. The correctness of the receipt generation is universally verifiable. Furthermore, our approach improves on existing solutions with respect to correctness and privacy. Finally, we compare all voting systems that are improved in this work, highlight their advantages and disadvantages, and conclude with key issues for future work.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Die Entwickelung elektronisch unterstützter Wahlsysteme stellt eine große Herausforderung für die Forschung dar. Einerseits müssen die Systeme transparent genug sein, um Wähler_innen und Beobachter_innen die Möglichkeit zu geben die Korrektheit der Ergebnisermittlung zu überprüfen. Andererseits darf das Verifizierungsverfahren Angreifern nicht erlauben das Wahlgeheimnis zu verletzen. Ein Ansatz für die Umsetzung beider Anforderungen ist die Generierung von kodierten Belegen während der Stimmabgabe. Ein Beleg erlaubt dem Wähler beziehungsweise der Wählerin nach Schließung der Wahlurne zu überprüfen, ob die eigene Stimme richtig von dem System erkannt und hierin gespeichert wurde. Anschließend werden alle kodierten Stimmen öffentlich ausgezählt, wodurch sich Wähler_innen und Beobachter_innen vergewissern können, dass das Wahlergebnis richtig ermittelt wurde. Um eine geheime und freie Wahl zu gewährleisten muss bei der Gestaltung des Belegs insbesondere darauf geachtet werden, dass kein_e Wähler_in in der Lage ist einem Dritten gegenüber zu beweisen wie er oder sie gewählt hat. Dies muss nicht nur während der Wahl verhindert werden, sondern auch im Anschluß an die Wahl. Insbesondere in Bezug auf die dauerhafte Geheimhaltung der abgegebenen Stimme wird das Wahlgeheimnis von vielen Systemen nicht ausreichend gewährleistet. Ein weit verbreiteter Ansatz ist die Stimme mit einem asymmetrischen Verschlüsselungsverfahren zu verschlüsseln. Dies erlaubt jedoch einem Angreifer beziehungsweise einer Angreiferin die getroffene Wahlentscheidung zu ermitteln, sobald das Verfahren für die verwendete Schlüssellänge gebrochen werden kann. Daher listen wir in dieser Arbeit zunächst alle Angriffe auf das Wahlgeheimnis auf, denen ein verifizierbares Wahlsystem ausgesetzt sein kann. Im Anschluss daran werden Lösungen für einzelne Schwachstellen präsentiert. In dieser Arbeit haben wir uns dabei auf drei Fragestellungen konzentriert: (1) Wie kann die korrekte Anonymisierung von Stimmen mit einem generischen Verfahren gezeigt werden ohne dabei das Wahlgeheimnis zu verletzen? (2) Wie können Wahlsysteme, die die abgegebenen Stimmen anonymisieren oder homomorph zählen so verbessern werden, dass sie eine dauerhafte Geheimhaltung der Stimme garantieren? (3) Wie kann das Vertrauen, welches ein_e Wähler_in in Wahlhelfer_innen und Wahlvorstände legen muss reduziert werden? Elektronische Wahlsysteme verwenden meist so genannte Mix-Netzwerke, um die kodierten Stimmen zu anonymisieren. Während der Anonymisierung veröffentlicht das Mix-Netzwerk Daten, mit denen Wähler_innen und Beobachter_innen kontrollieren können, dass keine Stimme verändert wurde. Die in der Praxis verwendeten generischen Ansätze bieten jedoch keinen ausreichenden Schutz vor Angriffen auf das Wahlgeheimnis. Um Frage (1) zu beantworten betrachten wir daher in dieser Arbeit verschiedene Ansätze und stellen ein neues Protokoll vor, welches auf bestehenden Verfahren beruht und diese hinsichtlich Effizienz und Geheimhaltung verbessert. Ein weiterer Nachteil von Wahlsystemen, die eine Anonymisierung der abgegebenen Stimmen vorsehen ist, dass alle Mix-Netzwerke asymmetrische Verschlüsselungsverfahren verwenden und somit das Wahlgeheimnis lediglich für eine begrenzte Zeit gewährleistet ist. Bezüglich Frage (2) stellen wir daher ein Verfahren vor, welches die abgegebenen Stimmen mit einem Commitment-Verfahren kodiert und somit eine informationstheoretische Sicherheit gewährleistet. Dies garantiert, dass ein_e Angreifer_in selbst bei beliebig großer Rechenleistung nicht in der Lage ist, die solcherart geschützten Daten zu decodieren. Wie Mix-Netzwerke erlaubt auch unser Verfahren die Korrektheit des Anonymisierungsprozesses zu verifizieren. Selbst unter der Annahme, dass alle Wahlhelfer_innen kooperieren, um das Ergebnis der Wahl zu verändern, kann die Integrität der abgegebenen Stimmen gewährleistet werden. Der von uns entwickelte Anonymisierungsprozess ist dem klassischen Mix-Netzwerk sehr ähnlich und kann dieses in vielen Wahlsystemen ersetzen. Dadurch können bestehende Systeme so angepasst werden, dass sie eine dauerhafte Geheimhaltung der abgegebenen Wahlentscheidung gewährleisten. Um dies zu verdeutlichen zeigen wir in dieser Arbeit wie unser Anonymisierungsprozess verwendet werden kann, um die Wahlsysteme Prêt à Voter und Split-Ballot zu verbessern. In beiden Fällen müssen lediglich kleine Änderungen an den aktuellen Verfahren vorgenommen werden. Ein ähnlicher Ansatz wird auch für Wahlsysteme erarbeitet, welche vorsehen die abgegebenen Stimmen homomorph zu zählen. Am Beispiel des Wahlsystems Scratch & Vote zeigen wir, wie unsere Lösung im Rahmen einer Präsenzwahl eingesetzt werden kann. Auch hier sind lediglich kleine Änderungen an dem aktuellen Verfahren notwendig. Bezüglich Frage (3) untersuchen wir den Ansatz so genannter nicht personifizierter Belege. In diesem Fall erhält ein_e Wähler_in einen Beleg, der die Stimme anderer Wähler_innen und nicht zwangsläufig die eigene Stimme enthält. Dadurch stellen die Belege keine Verbindung zwischen einem Wähler beziehungsweise einer Wählerin und seiner beziehungsweise ihrer getroffenen Wahlentscheidung her und Wähler_innen müssen Wahlhelfer_innen nicht vertrauen, dass sie diese Verbindung geheim halten. Wir stellen eine elektronische Wahlurne vor, die nicht personifizierte Belege erzeugt. Dabei wird ein Anonymisierungsprozess verwendet, der dem des Mix-Netzwerkes sehr ähnlich ist. Die Erzeugung der Belege ist universell verifizierbar und unser System verbessert die bestehenden Ansätze bezüglich Geheimhaltung der Stimmen und Korrektheit des Wahlergebnisses. Abschließend vergleichen wir die von uns verbesserten Wahlsysteme, arbeiten deren Vor- und Nachteile heraus, und stellen eine Liste mit möglichen künftigen Arbeiten vor.

Deutsch
URN: urn:nbn:de:tuda-tuprints-40193
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
20 Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra
Hinterlegungsdatum: 29 Jun 2014 19:55
Letzte Änderung: 29 Jun 2014 19:55
PPN:
Referenten: Buchmann, Prof. Dr. Johannes ; van de Graaf, Prof. Dr. Jeroen
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 3 Dezember 2013
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen