Punchscan ist ein kryptographisches Verfahren zur elektronisch unterstützten Durchführung von Wahlvorgängen mittels papierbasierter Stimmzettel bei Wahrung des Wahlgeheimnisses. Das vorgestellte Verfahren hat Ähnlichkeiten zu der Durchführung von Wahlvorgängen mittels Bingo Voting.
Das Verfahren basiert auf einer Stimmenauszählung bzw. Datenerfassung von Stimmzetteln per optischem Scanner und wurde von David Chaum, einem US-Forscher der Kryptografie, erstmals realisiert.
Punchscan wurde entwickelt, um Integrität, Vertraulichkeit und Transparenz für die Abwicklung von Wahlen bereitzustellen. Eine Besonderheit des Verfahrens ist die Möglichkeit anhand eines Belegs – den jeder Wähler erhält – auch nachträglich überprüfen zu können, ob die eigene Wahlstimme korrekt gezählt wurde. Punchscan ermöglicht damit einen Sicherheitsaudit für alle Phasen dieses Verfahrens und insbesondere für die Phase der Auszählung von Stimmen.
Für die Realisierung von Punchscan wird quelloffene Software verwendet. Der Quellcode wurde am 2. November 2006 unter der überarbeiteten Open-Source-Lizenz BSD veröffentlicht. Das Punchscan-Verfahren ist jedoch prinzipiell softwareunabhängig und ist daher nicht wie z. B. Wahlcomputer auf Informationssicherheit angewiesen; es bezieht seine besonderen Eigenschaften für die Sicherheit des Wahlvorganges vielmehr aus kryptographischen Funktionen. Das bedeutet, dass Punchscan auch auf Betriebssystemen zum Einsatz gelangen kann, die nicht quelloffen sind (z. B. Windows und Mac OS) und dennoch seine volle Sicherheitsintegrität behält.
Punchscan selbst wird nicht mehr weiterentwickelt und gewartet, wird aber im Nachfolgeprojekt Scantegrity verwendet.
Stimmzettel und Wahlvorgang mini|Der zweiteilige Punchscan-Stimmzettel. Kompletter Zettel (oben), beide Teilzettel (unten).
Ein Punchscan-Stimmzettel besteht aus zwei Lagen Papier. Die obere Papierlage des Stimmzettels zeigt die Namen der möglichen Wahlkandidaten gekennzeichnet mit einem Symbol (hier mit den Buchstaben A und B). Unterhalb der Kandidatenliste befinden sich eine gleiche Anzahl von rund ausgestanzten offenen Sichtfenstern. Auf der unteren Papierlage des Stimmzettels sind alle verwendeten Symbole der oberen Papierlage so aufgedruckt, dass diese genau in den Sichtfenstern der oberen Papierlage erscheinen.
Ein Wahlberechtigter gibt seine Stimme wie folgt ab: Er sucht in der oberen Papierlage des Stimmzettels den Namen des Wahlkandidaten heraus, dem er seine Stimme geben möchte Nun wählt er dasjenige Sichtfenster aus, dessen Inhalt das gleiche Symbol enthält, das neben dem Namen des ausgewählten Wahlkandidaten aufzufinden ist Das gewählte Sichtfenster wird nun mit einem Farbstempel (ähnlich wie beim Bingo-Spiel) abgestempelt, der etwas mehr Fläche abdeckt, als das Sichtfenster selbst; somit verbleibt zusätzlich eine gestempelte Sichtfensterumrandung auf der oberen Papierlage Der Wahlberechtigte trennt nun die obere Papierlage des Stimmzettels von der unteren und wählt sich frei aus, welche Papierlage er als Beleg für seine Wahl behalten möchte. Die jeweils andere verbleibende Papierlage vernichtet der Wähler in einem Aktenvernichter Seinen aufbewahrten Beleg lässt der Wahlberechtigte im Wahllokal von einem Scanner elektronisch erfassen, damit seine Teilnahme und seine Stimme gezählt werden können
Das Wahlgeheimnis wird beim Punchscan-Verfahren durch ein besonderes Vorgehen sichergestellt: Den Pseudozufall. Die Zuordnung der Symbole zu den Namen der Wahlkandidaten erfolgt hier pseudozufällig und ist somit von Stimmzettel zu Stimmzettel unterschiedlich. Gleiches gilt für die Reihenfolge der Verteilung der Symbole auf die offenen Sichtfenster.
Der Wahlbeleg enthält somit keinerlei Information, für welchen Wahlkandidaten der Wahlberechtigte seine Stimme abgegeben hat. Behält der Wähler die obere Papierlage des Stimmzettels, ist nicht erkennbar, welche Reihenfolge die Symbole beim Wahlvorgang in den offenen Sichtfenstern hatten. Behält der Wähler die untere Papierlage ist nicht erkennbar, welche Zuordnung die Symbole zu den Namen der Wahlkandidaten beim Wahlvorgang hatten. Der Wahlberechtigte kann also nicht einmal einem Dritten beweisen, für wen er abgestimmt hat, egal welche Papierlage er für sich selbst als Beleg behält.
Stimmenauszählung Die Auszählung sei an einem Beispiel verdeutlicht: Es findet eine Wahl statt zwischen genau zwei Wahlkandidaten, nämlich Coke und Pepsi, wie in der Abbildung der Punchscan-Stimmzettel zu sehen. Die Reihenfolge der Buchstaben neben den Namen der Wahlkandidaten kann einerseits A und dann B, oder zuerst B und dann A sein.
Spezielle Form für 2 Wahlkandidaten Die Buchstabenreihenfolge neben den Kandidatennamen nennen wir ab jetzt .
Die Gleichung =0 entspricht dann der ersten möglichen Reihenfolge und =1 beschreibt die verbleibende Reihenfolge. Damit gilt Folgendes:
: Reihenfolge der Symbole neben den Namen der Wahlkandidaten, .
Daraus ergibt sich verallgemeinernd für andere Teile des Stimmzettels:
: Reihenfolge der Symbole in den offenen Sichtfenstern, .
: markiertes offenes Sichtfenster, .
: mögliche Ergebnisse des Stimmzettels, .
Wichtiger Hinweis: Die Reihenfolge der Namen der Wahlkandidaten ist auf allen Stimmzetteln exakt die gleiche. Das Wahlergebnis der Auszählung genau eines Stimmzettels kann man somit wie folgt berechnen,
Da jedoch entweder die obere oder die untere Papierlage des Stimmzettels in einem Aktenvernichter im Rahmen des Wahlvorgangs vernichtet wird, existiert entweder oder nach dem Wahlvorgang nicht mehr.
Um zu berechnen, fehlt also Information, der eingescannte Wahlbeleg allein reicht also nicht aus für eine Ergebnisbestimmung. Eine weitere Information ist notwendig, um die Stimmen auszählen zu können, diese wird in einer Datenbank hinterlegt.
Vor einer Wahl wird in einer Datenbank – die Daten in Spalten und Zeilen organisiert – eine spezifische Menge an Spalten erzeugt. Jede Datenzeile repräsentiert dann einen Stimmzettel. Die Reihenfolge, in der die Stimmzettelinformation in der Datenbank hinterlegt wird, wird zufällig festgelegt, unter Verwendung eines kryptographischen Schlüssels, den jeder Wahlkandidat durch die Mitwirkung an einem Schlüsselaustauschprotokoll selbst bestimmen kann. Die erste Spalte , enthält die per Zufall verteilten Seriennummern. enthält eine pseudozufällige Bitfolge, die mit Hilfe des kryptographischen Schlüssels erzeugt wurde und wird verwendet für eine Stromverschlüsselung. speichert lediglich das Zwischenergebnis. enthält ein Bit für das folgender Zusammenhang gilt:
Das Ergebnis jedes Stimmzettels wird wiederum in einer Spalte abgelegt, in der die Reihenfolge der Stimmzettelergebnisse nochmals per Zufall bestimmt wird. schließlich enthält die Zeilennummer, in der das Ergebnis in abgelegt wurde.
Nachdem die Wahlvorgänge beendet und die Werte für eingescannt wurden, lässt sich wie folgt bestimmen:
Das Ergebnis wird wie folgt berechnet:
Dies ist gleichbedeutend zu Gleichung 1:
Die Werte der Ergebnisspalte werden veröffentlicht. Wurden die Stimmzettel (repräsentiert durch die Datenzeilen) zweimal entsprechend zufällig in ihrer Reihenfolge vertauscht, gibt die Reihenfolge der Ergebnisse keinerlei Hinweis darauf, welches Ergebnis welchem Stimmzettel zuzuordnen ist. Somit könnte auch eine durchführende Institution mit Hoheit über die Datenbank die abgegebenen Stimmen nicht mit den Seriennummern der Stimmzettel in Verbindung bringen.
Verallgemeinerte Form für n Wahlkandidaten Für eine Wahl mit Kandidaten findet die obenstehende Berechnung mit Modulo-n Gleichungen statt.
Grundlegender Sicherheitsaudit Die vom Wahlteilnehmer gewählte Papierlage, die er als Beleg behalten hat, enthält keinerlei direkte Information darüber, was er gewählt hat, jedoch enthält dieser eine Seriennummer. Der Beleg enthält aber keine geheimen oder geheim zu haltenden Informationen über die gewählten Kandidaten. Nach der Beendigung der Stimmzettelabgabe kann der Wahlveranstalter den Inhalt der anderen Papierlage – die optisch gescannt wurde – online veröffentlichen. Jeder Wähler kann dann durch die Eingabe der Seriennummer seines Papierbelegs prüfen, ob der Inhalt der eingescannten Papierlage übereinstimmt mit der tatsächlichen Stimmabgabe, die anhand des vom Wähler einbehaltenen Papierbelegs dann z. B. zu Hause am Rechner überprüft werden kann. Auf diese Art und Weise lässt sich erstmals nachprüfen. Ob der optische Scanvorgang die Stimme tatsächlich richtig erfasst hat oder ob die erfasste Stimme auch gezählt wurde, ist damit nicht abgesichert.
Jeder Wahlteilnehmer und jeder weitere Interessent kann die Inhalte der Datenbank überprüfen (Sicherheitsaudit) und somit prüfen, ob die Ergebnisse korrekt berechnet wurden. Es kann jedoch nicht die gesamte Information der Datenbank überprüft werden, da sonst eine Verbindung zwischen der Seriennummer und dem registrierten Wahlteilnehmer hergestellt werden könnte. Das Wahlgeheimnis wäre dann nicht mehr sichergestellt.
Diesem Problem wird begegnet mit einem Zufallsmechanismus, der die Hälfte aller Datenbankinhalte zufällig auswählt und überprüft, dadurch wäre das Wahlgeheimnis dennoch sichergestellt und Manipulationen würden sofern sie in der Zufallsauswahl enthalten sind auffallen.
Konkret passiert Folgendes: Eine Zufallswahl der Inspektion von oder wird vorgenommen (Die Zufallswahl kann z. B. von einem geheimen Schlüssel abgeleitet werden, oder besser noch einem nicht-deterministischen Zufallszahlengenerator, etwa ein SpielwürfelArel Cordero, David Wagner, David Dill: The Role of Dice in Election Audits – Extended Abstract (PDF; 1,0 MB). oder dem AktienindexJeremy Clark, Aleks Essex, Carlisle Adams. Secure and Observable Auditing of Electronic Voting Systems using Stock Indices (PDF; 135 kB).). Diese Form des Auditing schließt aus, dass die Kandidatenwahl von einzelnen Stimmzetteln manipuliert wird.
Der gesamte Sicherheitsaudit zeigt die Korrektheit der Wahl an, wenn gilt: Alle abgegebenen Stimmzettel wurden in die Zählung einbezogen. Es wurde bei jedem Stimmzettel tatsächlich der gewählte Kandidat ausgewertet. Wenn alle Zettel gezählt wurden und der tatsächlich gewählte Kandidat gezählt wurde, dann wurde korrekt gezählt.
In diesem Fall ist eine unbeeinträchtigte Integrität der durchgeführten Wahl mit sehr hoher Wahrscheinlichkeit gegeben.
Zusätzliche Sicherheit Um die Sicherheit einer Wahl mit Punchscan Stimmzetteln herzustellen, können verschiedene weitere Maßnahmen ergriffen werden, um einen möglichen Manipulationsversuch durch die Organisatoren der Wahl zu verhindern.
Mehrere Datenbanken Da die Informationen , , und in der Stimmzetteldatenbank allesamt pseudozufällig generiert werden, können mehrere Datenbanken parallel existieren, mit wiederum verschiedenen pseudozufälligen Informationen in den genannten Datenspalten.
Jede Datenbank ist unabhängig von den anderen und erlaubt beispielsweise die offene Inspektion einiger willkürlich ausgewählter Datenbanken. Jede vollständig ausgewertete Datenbank muss letztlich jedoch das exakt gleiche Stimmenresultat ergeben. Es existiert also letztlich das gleiche Abstimmungsendergebnis nur liegt es in jeder Datenbank vollkommen unterschiedlich strukturiert vor, so dass man jede Datenbank auf andere Art und Weise manipulieren müsste, um auch nur einen abgegebenen Stimmzettel zu manipulieren. Die Wahrscheinlichkeit der Entdeckung einer Manipulation steigt also exponentiell mit der Anzahl der eingesetzten, unabhängigen Datenbanken. Bereits der Einsatz weniger unabhängiger Datenbanken erhöht somit die Manipulationssicherheit der gespeicherten Daten.
Commitments