Bingo Voting

Bingo Voting ist ein elektronisches Wahlverfahren, das am Europäischen Institut für Systemsicherheit (EISS) des Karlsruher Instituts für Technologie entwickelt wurde und die fehlende Nachvollziehbarkeit vieler elektronischer Wahlverfahren durch kryptographische Methoden beheben soll. Dabei wird die Korrektheit der Wahl unter der Annahme garantiert, dass vertrauenswürdige Zufallszahlengeneratoren eingesetzt werden. Der Name „Bingo Voting“ stammt von der Idee, als Zufallszahlengenerator ein mechanisches Gerät einzusetzen, ähnlich wie bei Bingo oder Lotto.

Bei dem Verfahren werden Wahlcomputer zur Stimmabgabe und -auszählung eingesetzt, allerdings bekommt der Wähler bei der Wahl einen Papierbeleg, mit dessen Hilfe er die korrekte Zählung seiner Stimme nachvollziehen kann. Der Beleg ist dabei nicht einfach eine Kopie des ausgefüllten Wahlzettels. Vielmehr ist die Stimmverteilung aus dem Beleg nur für den Wähler selbst ersichtlich. Der Beleg ist weder dazu gedacht noch dazu geeignet, eine Nachzählung des Wahlergebnisses durchzuführen und wird dem Wähler mit nach Hause gegeben.

Konzept

Das erklärte Ziel des Bingo Voting Verfahrens ist es, die Nachteile der herkömmlichen Wahlmaschinen, insbesondere die fehlende Nachprüfbarkeit, zu beheben und elektronische Verfahren für die Stimmabgabe nachprüfbar und damit verwendbar zu machen.

Die Grundidee des Verfahrens ist es, dem Wähler einen Beleg, aus dem er seine Stimme ersehen kann, in die Hand zu geben und nach der Wahl Kopien aller Belege zu veröffentlichen. Dies gewährleistet:

1. Jeder Wähler kann nachprüfen, dass sein Beleg veröffentlicht wurde, und damit, dass seine Stimme gezählt wurde.
2. Jeder kann das Ergebnis der Auszählung anhand der veröffentlichten Belege nachprüfen.

Ein triviales Verfahren wäre, dem Wähler einfach eine Kopie seines (mit einer Identifikationsnummer versehenen) Stimmzettels in die Hand zu geben. Nach der Wahl werden alle Stimmzettel veröffentlicht und jeder kann nachprüfen, dass sein Stimmzettel darunter ist, sowie die Auszählung und damit das Wahlergebnis nachvollziehen. Bei diesem naiven Verfahren wären durch den Beleg allerdings Erpressung und Stimmenkauf möglich, das Wahlgeheimnis wäre also nicht hinreichend geschützt.

Kryptographische Verfahren ermöglichen jedoch Belege, aus denen nur der Wähler selbst seine Stimme ersehen kann und niemand sonst. Dadurch kann der Wähler mit seinem Beleg keiner anderen Person beweisen, was er gewählt hat.

Der Beleg enthält neben der tatsächlichen Stimme des Wählers so genannte Füllstimmen (oder Dummy-Stimmen). Diese Stimmen wurden vor der Wahl festgelegt und gleichmäßig an die Kandidaten verteilt. Die echte Stimme wird in der Wahlkabine vor den Augen des Wählers erzeugt, so dass dieser sie kennt, ist aber für jeden anderen von einer Füllstimme nicht zu unterscheiden.

Wahlablauf

Wahlvorbereitung

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.

Wahl

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.

Auszählung

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.

Beispiel

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.

Sicherheit und Nachvollziehbarkeit

Die Sicherheit des Verfahrens basiert auf dem Grundgedanken, dass jeder Wähler die korrekte Auszählung seiner eigenen Stimme überprüfen kann. Dazu muss der Wähler in der Wahlkabine den Beleg mit der Anzeige des Zufallszahlengenerators vergleichen und nach der Wahl überprüfen, dass sein Beleg veröffentlicht wurde. Die Beweise, die für die Sicherheit ebenfalls nötig sind, können unabhängig davon nachvollzogen werden, auch von Personen oder Gruppen, die an der Wahl selbst nicht beteiligt waren.

Die beweisbare Korrektheit des Verfahrens basiert auf dem Zufallszahlengenerator. Ist dieser korrumpiert, kann die Korrektheit des Verfahrens nicht gewährleistet werden. Die Autoren argumentieren, dass es leichter ist, einen Zufallszahlengenerator nachvollziehbar zu bauen und zu zertifizieren als eine komplette Wahlmaschine.

Die Sicherheit des Wahlgeheimnisses basiert auf der Wahlmaschine und dem Vertrauen in die Wahlleitung, die vor der Wahl die Zufallszahlen erzeugt. Speichert die Wahlmaschine, wann welche Stimme abgegeben wurde oder wird die Liste der Zufallszahlen komplett bekannt, ist das Wahlgeheimnis nicht mehr gesichert.

Anfechten der Wahl

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.

Bingo Voting in der Praxis

Einsatz bei komplexen Wahlen

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.

Reale Wahlen, die mit Bingo Voting durchgeführt wurden

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. 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.

Auszeichnungen

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

Ähnliche Verfahren

Es existieren andere kryptographische Wahlverfahren mit einem ähnlichen Ziel wie Bingo Voting. Eines davon ist Punchscan, das von David Chaum entwickelt wurde.

Weblinks

• Website des Verfahrens
• Heise online über Bingo Voting