Scantegrity behandelt ein Prinzip, das bestimmte elektronische Wahlsysteme in Bezug auf Manipulation und Wahlgeheimnis sicherer machen soll. Dieses System wurde von David Chaum erarbeitet und stellt einen Aufsatz auf elektronische Systeme dar, die auf der Basis von optischen Scannern arbeiten.
Zweck
Da das Zählen von Stimmen sehr aufwendig ist, benötigt man elektronische Hilfe. Schon Hollerith hat dies seinerzeit erkannt. Diese elektronischen Wahlhelfer sind jedoch oft leicht manipulierbar, bzw. sie schützen oft nur schlecht das Wahlgeheimnis. Häufig gebrauchte Beispiele hierfür sind die Wahlmaschinen von Nedap und Diebold.
Die meisten elektronischen Wahlsysteme stellen Komplettlösungen mit Hardware zur Verfügung. Im Gegensatz zu diesen Systemen liegt der Schwerpunkt von Scantegrity eher in der Art der Verwaltung der Stimmzetteln und der Stimmen. Die Schwachstelle der Hardware wird also versucht zu beseitigen, indem das Verfahren selbst sicher gemacht werden soll. Dabei soll Sicherheit immer in Bezug auf das Wahlgeheimnis und die Manipulation interpretiert werden.
Prinzip
Scantegrity ist ein Prinzip bzw. System für die Verwaltung von Stimmen in einer Wahl, das sich zum Ziel setzt, abgegebene Stimmen anonym und verifizierbar zu speichern. Diese Verifikation (Audit) soll ebenfalls öffentlich und für jeden transparent sein. Es ergibt sich außerdem, dass dieses System beliebige, auf optische Scanner basierende, Systeme erweitern kann und daher nur geringe zusätzliche Kosten erfordert.
Scantegrity wird in die vier folgenden Phasen eingeteilt:
(1) pre-voting (2) voting (3) pre-audit (4) audit
Dabei wird zunächst nur der einfache Fall betrachtet, dass mit einem Wahlzettel genau eine Wahl vollzogen wird, in der genau eine Stimme für m (bzw. 2) Kandidaten abgegeben werden kann. Im Anschluss wird kurz erklärt, wie man das System erweitern kann, sodass mehr als eine Stimme abgegeben werden kann, bzw. mehrere Wahlen mit einem Wahlzettel vollzogen werden können.
(1) Pre-voting (Vorbereitung)
In der Pre-voting-Phase werden alle Notwendigkeiten für das Scantegrity-System vorbereitet. Dies sollte geschehen, noch bevor die Wahlzettel gedruckt werden, da sie dann Informationen tragen, die erst während dieser Phase berechnet werden. Zu den genannten Notwendigkeiten gehören u. a. eineindeutige Seriennummern für die Wahlzettel und das bulletin-board, das in diesem Kapitel im Detail erklärt wird. Das bulletin-board soll die Verbindung zwischen einem Wahlzettel, dem eine eineindeutige Seriennummer zugeordnet wird, und dem später mit diesem Wahlzettel gewählten Kandidaten verschleiern. Es stellt den Kern von Scantegrity dar.
Die Permutationen ist für das Verständnis von zentraler Bedeutung. Eine Permutation p ist eine Abbildungsvorschrift, die eine vorgegebene Anzahl von Buchstaben vertauscht. Man nennt sie daher auch manchmal Vertauschungsvorschrift. Es wird also jedem Buchstaben b ein Buchstabe p(b) zugeordnet. Die einfachste Permutation ist die Identität, die keinen Buchstaben vertauscht. Ein weiteres Beispiel ist die Permutation, die nur die ersten beiden Buchstaben vertauscht. Beispiel einer Permutation - p' Beispiel 2 einer Permutation - q'
Diese beiden Abbildungen zeigen zwei Permutationen. Sie seien hier mit p' und q' bezeichnet. p' würde in diesem Beispiel ein A durch ein B ersetzen und umgekehrt. p'(C) ergäbe wieder C selbst. Man interpretiert diese Schreibweise, indem ein Buchstabe immer durch den unter ihm stehenden Buchstaben ersetzt wird.
Hat man zwei Permutationen p und q, so kann man deren Verknüpfung bilden. Wird durch p ein Buchstabe b ersetzt, so nimmt man den neuen Buchstaben und verfährt analog mit der Permutation q. Der zuletzt erhaltene Buchstabe ist der Buchstabe, der durch die Verknüpfung von p und q aus b entsteht. Verfährt man so mit allen möglichen Buchstaben, so entsteht die komplette Vertauschungsvorschrift der Verknüpfung (Hintereinanderausführung) von p und q. Ein B würde im oben genannten Beispiel bei der Hintereinanderausführung ein C ergeben, da durch p' ein A entsteht und q' aus A ein C macht. Die Umkehrabbildung von p beschreibt die gleiche Abbildung in die andere Richtung. Wird b durch p in einen Buchstaben b2 ersetzt, so wird b2 durch die Umkehrabbildung von p in den Buchstaben b ersetzt. In obigen Beispiel würde die Umkehrabbildung q' aus einem B ein C machen.
Als Voraussetzung seien n Wahlzettel angenommen, die, von 1 beginnend, fortlaufend durchnummeriert sind. Diese eineindeutigen Nummern werden als Seriennummern {i} bezeichnet. Es sei angenommen, dass es m Kandidaten in der Wahl gibt. Auf jedem Wahlzettel werden dann die ersten m Buchstaben des Alphabets auf die Kandidaten verteilt, wobei die Zuordnung willkürlich für jeden Wahlzettel geschieht. Jedem Wahlzettel i wird dadurch eindeutig eine Permutation p[i] der Permutationsgruppe S(m) zugeordnet. Hierbei ist zu erwähnen, dass es genügt, sich auf die von (2 3 ... m 1) erzeugte zyklische Untergruppe zu beschränken, solange in der Wahl nur eine Stimme abgegeben werden kann. Auf diese Weise kann man von "shifts" reden und die Permutationen durch Zahlen 1 bis m ersetzen.
Das bulletin-board ist im Wesentlichen eine Tabelle mit drei Spalten und n Zeilen, wobei n die Anzahl der vorbereiteten Wahlzettel darstellt. Die Zellen der ersten beiden Spalten bestehen jeweils aus drei Komponenten. Die erste Komponente ist ein Platzhalter für einen der ersten m Buchstaben des Alphabets. Sie wird erst gefüllt, sobald der Wähler seine Stimme abgibt. Die zweite Komponente gibt eine Vertauschungsvorschrift (Permutation) der ersten m Buchstaben an. Die Permutationen der 1. Spalte und i-ten Zeile seien fortan mit q[i] und die Permutationen der 2. Spalte und i-ten Zeile mit r[i] bezeichnet. Die dritte Komponente ist eine Zahl zwischen 1 und n. Die Zahlen der 2. Spalte und i-ten Zeile seien dabei mit f(i) und die der 3. Spalte und i-ten Zeile mit g(i) bezeichnet. Die letzte Spalte besteht aus Platzhaltern für Buchstaben. Sie gleichen dem Aufbau der ersten Komponenten der Zellen der ersten beiden Spalten. Die folgende Abbildung illustriert dies noch einmal.
Illustration der Bestandteile des bulletin-boards
Die Zahlen f(i) und g(i) dürfen nicht komplett willkürlich bestimmt werden, stattdessen müssen sie genau eine Bedingung erfüllen. In der zweiten Spalte darf keine Zahl doppelt vorkommen. Ebenso darf in der dritten Spalte keine Zahl doppelt vorkommen. Die Zahlen f(i) sind also genau die Zahlen von 1 bis n. Ebenso umfassen die n Zahlen g(i) genau die Zahlen 1 bis n.
Bevor die Einschränkung der Permutationen genannt werden kann, muss die Bedeutung dieser Zahlen erklärt werden. Durch die Eindeutigkeit der Zahlen f(i) und g(i) werden eineindeutige Ketten von den Zellen der ersten Spalte zu den Zellen der dritten Spalte bestimmt. Eine Kette, die in der i-ten Zeile der ersten Spalte startet, besitzt ihr zweites Element in der zweiten Spalte in der Zeile mit der Nummer f(i). Der Einfachheit wegen sei dies Zahl f(i) kurz fixiert und mit j bezeichnet. Nun findet man das dritte Element der Kette in der dritten Spalte in der Zeile mit der Nummer g(j) = g(f(i)).
Die Permutationen der Buchstaben für die Kandidaten auf den Wahlzetteln und in der ersten Spalte dürfen beliebig, also zufällig, gewählt werden. Dagegen muss für jedes i zwischen 1 und n die Permutation r[i] der Umkehrabbildung der Hintereinanderausführung der Permutationen p[i] und q[i] entsprechen. Einfach ausgedrückt beläuft sich diese Einschränkung auf Folgendes. Wählt man einen der ersten m Buchstaben, tauscht diesen entsprechend der Permutation p[i] des Wahlzettels aus, so erhält man einen neuen Buchstaben. Fährt man mit dem neu gewonnenen Buchstaben entsprechend der Permutation q[i] der ersten Spalte fort und macht selbiges mit letzterem Buchstaben und der Permutation r[i] aus der zweiten Spalte, so muss der ursprünglich gewählte Buchstabe wieder entstehen.
An dieser Stelle soll noch erwähnt sein, dass der Inhalt der zweiten und dritten Komponenten der Zellen der ersten beiden Spalten nicht öffentlich sein sollen. Auf diese Weise soll sichergestellt werden, dass die Ketten nicht ersichtlich sind, wodurch die Verbindung von Wahlzetteln zu gewählten Kandidaten geheim bleibt.
(2) Voting
Die Wahl unter Benutzung von Scantegrity kann unter drei Gesichtspunkten betrachtet werden. Zunächst soll die Sicht des Wählers betrachtet werden. Anschließend werden Punkte genannt, die den Wahlveranstalter selbst betreffen. Zum Schluss wird diese Phase aus Sicht des Scantegrity-Systems betrachtet.
Aus der Sicht des Wählers sind bis zu drei Phasen zu durchlaufen. Die letzteren beiden Phasen sind dabei optional und dienen der Verifikation der abgegebenen Stimme. In der ersten Phase (A) füllt der Wähler den Wahlzettel aus. Genauer bedeutet das, dass der Wähler ein Kreuz in einen vorgegebenen Bereich neben einem beliebigen Kandidaten setzt. Zu diesem Bereich gehört ein Buchstabe, den er sich notieren kann. Ebenfalls kann er sich die Seriennummer des Wahlzettels notieren. Nur wenn er dies tut, kann er die folgenden optionalen Phasen durchlaufen. In der zweiten Phase (B) überprüft der Wähler online, ob seine Stimme korrekt abgegeben wurde. Dazu gibt er auf einer vorgegebenen Internetseite die Seriennummer seines Wahlzettels ein und erhält den Buchstaben des Kandidaten, der entsprechend angekreuzt wurde. Stimmt dieser Buchstabe nicht mit dem überein, den er sich während der Wahl notiert hat, so gibt es eine Unstimmigkeit, und erst dann sollte die dritte Phase eingeleitet werden. An dieser Stelle sollte nochmal bemerkt werden, dass man aus der Seriennummer und dem Buchstaben nicht herleiten kann, welcher Kandidat gewählt wurde, da die Zugehörigkeit der Buchstaben zu den Kandidaten für jeden Wahlzettel zufällig gewählt wurde. In der dritten Phase (C) wendet sich der Wähler an den Wahlveranstalter, um diese Unstimmigkeit zu klären. Eventuell liegt in diesem Fall ein Wahlbetrug vor, d. h. seine Stimme wurde manipuliert.
Aus der Sicht des Wahlveranstalters ist zu klären, welche technischen Voraussetzungen erfüllt werden müssen und wie die abgegebenen Stimmen verwaltet werden. Die Stimmzettel können, wie üblich, im Bezirk gescannt werden oder aber an zentraler Stelle. Ein zentraler Scanner würde den Zeitaufwand erhöhen, den technischen Aufwand jedoch verringern. Es gibt zwei unterschiedliche Typen von optischen Scan-Systemen. Dies sind einerseits die Pixel-Scanner und andererseits die Sense-Mark-Scanner.
Die Pixel-Scanner sind die üblichen Scanner, die auch häufig im privaten Gebrauch zu finden sind. Sie scannen mit einer gewissen Auflösung das gesamte Bild in ein zweidimensionales Raster. Die genutzten Wahlzettel werden gescannt, und das Bild kann der vorgefertigten Software direkt übergeben werden. Falls ein Wahlsystem mit dem Scantegrity-Verfahren erweitert wird, wird eine solche Software bereits existieren, und die Bilder gehen sowohl an diese als auch an die eigens für Scantegrity entwickelte Software. Auf der anderen Seite enthält die Software für Scantegrity bereits ein komplettes Wahlsystem, sodass das alte in dem Fall entfallen kann. Zahlen und Markierungen auf dem Wahlzettel, wie z. B. die Seriennummer des Wahlzettels, können mit vorgefertigten Algorithmen herausgerechnet werden.
Sensemark-Scanner scannen bestimmte vorgegebene Bereiche nach einer Markierung ab. Das Ergebnis für einen bestimmten Bereich kann dabei nur „markiert“ oder „nicht markiert“ sein. Seriennummern etc. können jedoch binär codiert werden, wodurch sie durch SensemarkScanner beim Scannen erfasst werden können. Dies kann analog zur Zahlendarstellung im Computer geschehen. Eine andere Möglichkeit wäre, pro Ziffer genau zehn Markierungen vorzugeben, von denen exakt eine ausgefüllt ist. Jede Markierung repräsentiert dabei eine Ziffer zwischen 0 und 9. Möchte man mit dieser Methode eine fünfstellige Zahl darstellen, so benötigt man hierfür schon 50 Markierungen.