Punchscan

Punchscan
Basisdaten
Hauptentwickler	Richard Carback, David Chaum, Jeremy Clark, Aleks Essex, and Stefan Popoveniuc.
Betriebssystem	Cross-platform
Programmiersprache	Java
Kategorie	kryptographisches Wahlverfahren
Lizenz	Revised BSD-Lizenz
http://punchscan.org/

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

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:

1. Er sucht in der oberen Papierlage des Stimmzettels den Namen des Wahlkandidaten heraus dem er seine Stimme geben möchte
2. Nun wählt er dasjenige Sichtfenster aus, dessen Inhalt das gleiche Symbol enthält, das neben dem Namen des ausgewählten Wahlkandidaten aufzufinden ist
3. 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
4. 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
5. 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 $P_{1}$.

Die Gleichung $P_{1}$=0 entspricht dann der ersten möglichen Reihenfolge und $P_{1}$=1 beschreibt die verbleibende Reihenfolge. Damit gilt Folgendes:

$P_{1}$: Reihenfolge der Symbole neben den Namen der Wahlkandidaten,

$P_{1}=\{0,1\}=\{{\mbox{AB}},{\mbox{BA}}\}\,$.

Daraus ergibt sich verallgemeinernd für andere Teile des Stimmzettels:

$P_{2}$: Reihenfolge der Symbole in den offenen Sichtfenstern,

$P_{2}=\{0,1\}=\{{\mbox{AB}},{\mbox{BA}}\}\,$.

$P_{3}$: markiertes offenes Sichtfenster,

$P_{3}=\{0,1\}=\{{\mbox{1st}},{\mbox{2nd}}\}\,$.

$R$: mögliche Ergebnisse des Stimmzettels,

$R=\{0,1\}=\{{\mbox{Coke}},{\mbox{Pepsi}}\}\,$.

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,

$R=P_{1}+P_{2}+P_{3}{\bmod {2}}\,$		(Gleichung 1)

Da jedoch entweder die obere oder die untere Papierlage des Stimmzettels in einem Aktenvernichter im Rahmen des Wahlvorgangs vernichtet wird, existiert entweder $P_{1}$ oder $P_{2}$ nach dem Wahlvorgang nicht mehr.

Um $R$ 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 $D_{1}$, enthält die per Zufall verteilten Seriennummern. $D_{2}$ enthält eine pseudozufällige Bitfolge, die mit Hilfe des kryptographischen Schlüssels erzeugt wurde und wird verwendet für eine Stromverschlüsselung. $D_{3}$ speichert lediglich das Zwischenergebnis. $D_{4}$ enthält ein Bit für das folgender Zusammenhang gilt:

$D_{2}+D_{4}=P_{1}+P_{2}{\bmod {2}}\,$

Das Ergebnis jedes Stimmzettels wird wiederum in einer Spalte $R$ abgelegt, in der die Reihenfolge der Stimmzettelergebnisse nochmals per Zufall bestimmt wird. $D_{5}$ schließlich enthält die Zeilennummer, in der das Ergebnis in $R$ abgelegt wurde.

Nachdem die Wahlvorgänge beendet und die Werte für $P_{3}$ eingescannt wurden, lässt sich $D_{3}$ wie folgt bestimmen:

$D_{3}=P_{3}+D_{2}{\bmod {2}}\,$

Das Ergebnis wird wie folgt berechnet:

$R=D_{3}+D_{4}{\bmod {2}}\,$

Dies ist gleichbedeutend zu Gleichung 1:

${\begin{aligned}R&=(D_{3})+D_{4}{\bmod {2}}\\&=(P_{3}+D_{2})+D_{4}{\bmod {2}}\\&=P_{3}+(D_{2}+D_{4}){\bmod {2}}\\&=P_{3}+(P_{1}+P_{2}){\bmod {2}}\end{aligned}}$

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 $n$ 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 $\{D_{1},D_{2},D_{3}\}$ oder $\{D_{3},D_{4},D_{5}\}$ wird vorgenommen (Die Zufallswahl kann z. B. von einem geheimen Schlüssel abgeleitet werden, oder besser noch einem nicht-deterministischen Zufallszahlengenerator, etwa ein Spielwürfel oder dem Aktienindex). 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 $D_{1}$, $D_{2}$, und $D_{5}$ 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

Im Rahmen der Vorbereitungen einer Wahl, muss eine Institution die mit diesen Vorbereitungen vertraut ist, die Stimmzettel drucken und die Datenbank(en) anlegen. Ein wesentlicher Schritt bei der Erstellung der Stimmzettel besteht darin, dass sich die Institution durch ein kryptographisches Commitment auf die eindeutigen Informationen festlegt, die auf jedem Stimmzettel und in der/den Datenbank/en enthalten sind wird. Diese Festlegung findet statt, indem auf diese eindeutigen Information eine Einwegfunktion angewendet wird. Obwohl das Bild dieser Funktion (das Commitment) auf dem Stimmzettel veröffentlicht wird, ist die eigentliche Information die in die Einwegfunktion Eingang fand rechnerisch versiegelt. Wegen der Unumkehrbarkeit der Einwegfunktion, ist es rechentechnisch unmöglich die Eingangsinformation wieder zu ermitteln.

Prüfung des Stimmzettels

Im Vorfeld einer Wahl werden so viele papierbasierte Stimmzettel hergestellt, dass letztlich die doppelte Menge an Stimmzetteln verfügbar ist, als eigentlich zum Einsatz gelangen soll. Aus den hergestellten Stimmzetteln werden die tatsächlich benötigten Stimmzettel zufällig ausgewählt (es könnte z. B. jede der Wahlparteien einen Anteil an Stimmzetteln – die für die Wahl eingesetzt werden sollen – selbst auswählen). Während des Produktionsprozesses der Stimmzettel wurden diese bereits als Datenzeilen in der Datenbank angelegt. Die ausgewählten Stimmzettel könnten also vor dem eigentlichen Einsatz sogar nochmals geprüft werden, ob sie in der Datenbank korrekt registriert sind und auch noch keine Wahlergebnisse dafür eingetragen wurden.

Da die Wahlhelfer nicht vorab wissen, welche Hälfte der Stimmzettel tatsächlich zum Einsatz gelangt, bedeutet der erfolgreiche Sicherheitsaudit in Form eines Checks, ob der Stimmzettel in der Datenbank registriert ist, dass die Datenbank mit sehr hoher Wahrscheinlichkeit nicht manipuliert wurde. Sobald der Stimmzettelbeleg eingescannt und geschreddert wurde, kann dieser anhand seiner Festlegung nochmals gegen die Datenbank geprüft werden, um mit hoher Wahrscheinlichkeit eine unkorrekte Festlegung auszuschließen.

Kritik

Die Durchführung eines Wahlvorganges mittels Punchscan erscheint deutlich mehr Sicherheit zu bieten, als Verfahren, die auf so genannte Wahlcomputer setzen. Der Teufel steckt jedoch im Detail bzw. in den ordnungsgemäß einzuhaltenden kryptografischen Abläufen. Diese sind nicht ohne weiteres von Menschen zu verstehen, die keine ausgebildeten Kryptografie-Experten sind. Das bedeutet jedoch, dass diese Technologie zur Abwicklung eines Wahlvorgangs zumindest bei großen Teilen der Bevölkerung nicht nachvollziehbar, damit nicht überprüfbar und daher intransparent ist.

Transparenz darüber, was genau passiert, ist jedoch ein wichtiges Kriterium für die Akzeptanz von Verfahren zur Abwicklung von Wahlvorgängen. Punchscan kann als ein gelungener Versuch angesehen werden, eine erhöhte Sicherheit für papierbasiertes Wählen herzustellen, beispielsweise durch die Nachprüfbarkeit für den Wähler ob seine Stimme auch tatsächlich gezählt wurde. Jedoch scheitert das Punchscan-Verfahren darin, einfach nachvollziehbar für alle Wähler zu sein. Es braucht eine Menge kryptografischer Teilschritte, um das Verfahren anzuwenden. Die gewonnene Sicherheit und Nachprüfbarkeit sind jedoch genau von diesen de facto intransparenten Schritten abhängig und daher nur bedingt als Verbesserung von Wahlvorgängen anzusehen.

Weblinks

• Homepage des Punchscan-Projects
• Vocomp Submission – verständlich geschriebenes 80-seitiges Dokument, das alle Aspekte des Systems beschreibt (PDF; 2,26 MB) – englisch
• Electronic Democracy (MP3; 7,2 MB) – BBC World’s Digital Planet Audiointerview mit David Chaum.
• Making Every E-vote Count – IEEE Spectrum.
• Transparent and Open Voting with Punchscan: Teil 1 und Teil 2, 2006
• Future Tense (Memento vom 14. Oktober 2007 im Internet Archive) Audiointerview mit David Chaum.