Bingo Voting

Zur Vorbereitung der Wahl werden für jeden Kandidaten Zufallszahlen erzeugt. Diese Zufallszahlen dienen als Füllstimmen. Auf die Zufallszahlen werden Commitments veröffentlicht, zusammen mit einem Zero-Knowledge-Beweis, dass jeder Kandidat die gleiche Anzahl Füllstimmen erhalten hat. Ein Commitment-Verfahren bietet die Möglichkeit, einen Wert so zu veröffentlichen, dass man auf ihn festgelegt ist, ohne ihn zu verraten, das heißt man veröffentlicht nicht den Wert selbst, sondern eine „verschlüsselte Version“ davon. Die Entwickler schlagen dafür Pedersen-Commitments vor, da diese vorteilhafte Eigenschaften für die notwendigen Beweise besitzen.

Aus praktischen Gründen erhält jede Wahlmaschine einen eigenen Pool an Füllstimmen. Im Folgenden wird das Verfahren zur Veranschaulichung mit nur einer Wahlmaschine und einem Pool an Füllstimmen beschrieben.

Die für das Verfahren notwendige Wahlmaschine besteht aus einem Wahlcomputer mit einem Bildschirm, einem Eingabegerät (beispielsweise ein Touchscreen), einem Drucker und einem vertrauenswürdigen Zufallszahlengenerator.

Ein Wähler gibt seine Stimme an einer Wahlmaschine ab. Dabei sind durch das Verfahren selbst keine Einschränkungen gegeben, die Darstellung und Stimmabgabe sowie etwaige Hilfen können an die Wahl angepasst werden.

Nachdem der Wähler seine Stimme abgegeben hat, erzeugt der Zufallszahlengenerator für jede Stimme, die abgegeben wurde, eine Zufallszahl, und zeigt diese auf einem eigenen Display an. Der Wähler bekommt nun einen ausgedruckten Beleg und kann direkt in der Wahlkabine überprüfen, ob der Beleg korrekt ist. Dazu vergleicht er die Zufallszahlen, die seine Stimmen repräsentieren, also an den entsprechenden Stellen stehen, mit den Zufallszahlen, die vom Zufallszahlengenerator angezeigt werden. Stimmen diese überein, kann er sicher sein, dass die Wahlmaschine seine Stimme korrekt gespeichert hat.

Die Zufallszahlen auf dem Beleg, die nicht abgegebene Stimmen repräsentieren, stammen von den vorher festgelegten Listen. Der Wahlcomputer streicht diese Zufallszahlen von seiner Liste, sobald diese für einen Beleg verwendet wurden, so dass diese nicht ein zweites Mal benutzt werden.

Die Auszählung geschieht anhand der nicht benutzten Füllstimmen. Der Kandidat, der die meisten Füllstimmen in seiner Liste behalten hat, gewinnt die Wahl. Denn wenn ein Wähler seine Stimme für einen Kandidaten abgibt, verlieren alle anderen Kandidaten eine Füllstimme aus ihrer Liste. Die genaue Verteilung der Stimmen lässt sich aus der Anzahl der unbenutzten Füllstimmen und der Anzahl der Wähler berechnen.

Nach der Wahl werden neben dem Wahlergebnis noch weitere Informationen veröffentlicht:

• Alle unbenutzten Zufallszahlen (Füllstimmen) von den Listen der Kandidaten werden veröffentlicht.
• Alle Belege werden veröffentlicht.
• Für jeden Beleg wird ein Zero-Knowledge-Beweis veröffentlicht, der beweist, dass sich auf dem Beleg genau eine frische Zufallszahl befindet und die restlichen Zufallszahlen aus den Listen der Kandidaten stammen.

Mit der Hilfe dieser veröffentlichten Daten kann

• jeder Wähler überprüfen, ob sein Beleg veröffentlicht und damit seine Stimme bei der Zählung berücksichtigt wurde,
• jeder nachvollziehen, dass für jeden Beleg (und damit für jeden Wähler) von jeder Liste mit Füllstimmen außer einer (der des Kandidaten, für den die Stimme abgegeben wurde), eine Zufallszahl gestrichen wurde, und
• jeder nachvollziehen, dass die Anzahl der Belege mit der Anzahl der Wähler und dem Wahlergebnis korrespondiert.

Die letzten beiden Punkte können von jedem überprüft werden, unabhängig von der Teilnahme an der Wahl oder der Auszählung.

In der Wahlkabine: Der Wähler hat per Wahlcomputer (links) Kandidat B gewählt und bekommt einen Beleg (rechts), bei dem die zu Kandidat B gehörende Zufallszahl mit der Anzeige des Zufallszahlengenerators (Mitte) übereinstimmt.

Eine Wahl mit drei Kandidaten könnte etwa wie folgt ablaufen: Die Wahlkommission gibt zusammen mit den drei Kandidaten drei verschlüsselte Listen von Zufallszahlen (eigentlich Commitments auf die Zufallszahlen) bekannt. Dabei wird auch bewiesen, dass alle drei Listen gleich lang sind, also die gleiche Anzahl an Zufallszahlen enthalten.

In der Wahlkabine wählt der Wähler einen der drei Kandidaten aus, zum Beispiel mit einem Touchscreen. Nach der Bestätigung startet ein Zufallszahlengenerator, ein kleines Gerät mit Anzeige, das mit dem Computer verbunden ist. Der Wahlcomputer generiert nun einen Beleg, dazu nimmt er von den beiden Listen der Kandidaten, die nicht gewählt wurden, je eine Zufallszahl, sowie die Zufallszahl vom Zufallszahlengenerator. Die beiden Zufallszahlen von den Listen werden zu den jeweiligen Kandidaten geschrieben, der Kandidat, der gewählt wurde bekommt die Zufallszahl, die eben vom Zufallszahlengenerator erzeugt wurde.

Der Wähler bekommt nun einen Beleg, bei dem hinter jedem Kandidaten eine Zahl steht. Er kann nachprüfen, dass der Beleg seine Stimme korrekt wiedergibt, dazu muss die Zahl neben dem Kandidaten, den er gewählt hat, mit der Zahl, die vom Zufallszahlengenerator angezeigt wird, übereinstimmen. Ist dies der Fall, kann er die Wahlkabine verlassen und den Beleg mit nach Hause nehmen. Niemand, der nicht dabei war, als die Zufallszahl erzeugt und vom Zufallszahlengenerator angezeigt wurde, kann dem Beleg ansehen, für wen der Wähler gestimmt hat.

Nach der Wahl kann der Wähler nachschauen, ob sein Beleg veröffentlicht wurde. Damit kann er sicher sein, dass seine Stimme gezählt wurde. Zu jedem Beleg gibt es außerdem einen Beweis, dass zwei der drei Zufallszahlen aus den vorher festgelegten Listen stammen. Damit kann sich der Wähler sicher sein, dass bei den Kandidaten, die er nicht gewählt hat, je eine Zufallszahl gestrichen wurde, denn diese erscheinen ja auf seinem Beleg. Die Zufallszahl des Kandidaten, den der Wähler gewählt hat, kann nicht von der Liste stammen, denn sie wurde in der Wahlkabine vor seinen Augen erzeugt.

Es gibt mehrere Probleme, die während oder nach einer manipulierten Wahl auftreten können:

1. Ein Wähler stellt fest, dass der Beleg die frische Zufallszahl des Zufallszahlengenerators nicht oder an der falschen Stelle aufweist.
2. Ein Wähler stellt fest, dass sein Beleg nicht veröffentlicht wurde.
3. Einer der Zero-Knowledge-Beweise ist fehlerhaft.

Das Bingo Voting Verfahren macht keine Aussage darüber, bei welcher Beweislage eine Wahl angefochten werden kann. Es dient lediglich der Aufdeckung von Wahlmanipulationen.

Einer der Vorteile von Wahlverfahren, die Wahlcomputer einsetzen, ist die Unterstützung, die der Computer bei komplexen Wahlen mit vielen Stimmen sowie der Möglichkeit des Kumulierens und Panaschierens bieten kann. Ab einer gewissen Größe stößt Bingo Voting dabei an eine Grenze, da die Größe des Belegs und die Anzahl der Zufallszahlen mit der Stimmenanzahl zunehmen. Bei einer Wahl mit drei Kandidaten und einer Stimme muss der Wähler auf einem Beleg mit drei Zufallszahlen eine Zahl suchen und mit der Anzeige des Zufallszahlengenerators vergleichen. Bei einer Wahl mit 50 Kandidaten und neun Stimmen trägt der Beleg schon 450 Zufallszahlen, von denen der Wähler neun mit dem Zufallszahlengenerator vergleichen muss. Diese Aufgabe kann zwar durch Hilfestellung des Computers und eine entsprechende Formatierung des Belegs erleichtert werden, ist aber in jedem Fall zeitaufwändig.

Bingo Voting wurde erstmals bei der Studierendenparlamentswahl der Universität Karlsruhe im Jahre 2008 bei einer realen Wahl eingesetzt. Dort wurden ungefähr 2,5 % der abgegebenen Stimmzettel per Bingo-Voting abgegeben, die übrigen Stimmen waren herkömmliche Papierzettel.[2][3][4] Der Wahlausschuss berichtete nach der Wahl allerdings von Problemen mit dem Prototypsystem bis hin zur Möglichkeit, dass Mitarbeiter des EISS das Wahlgeheimnis hätten brechen können.[5]

Am 24. Oktober 2008 wurde das Projekt „Bingo Voting – Verifizierbare Wahlen mit Wahlmaschinen“ mit dem Deutschen IT-Sicherheitspreis der Horst Görtz Stiftung ausgezeichnet.[6]