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

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.

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.

In manchen Nachrüstungen wird nicht die Software angepasst, sondern ein zweiter Scan mit einem Pixel-Scanner durchgeführt. Die Stimmen können dementsprechend ein zweites (redundantes) Mal gezählt werden, und die Resultate (Zählergebnisse) können verglichen werden.

Die Sicht des bulletin-boards soll zeigen, was genau geschieht, wenn ein Wahlzettel abgegeben wird. Angenommen, es liegt ein gültiger Wahlzettel mit einer abgegebenen Stimme vor, dann werden ihm nach dem Scannen die Seriennummer und der markierte Buchstabe entnommen. Der gescannte Buchstabe wird nun in den Platzhalter in die erste Spalte in der Zeile mit der Nummer der Seriennummer i geschrieben. Anschließend werden die Platzhalter der von dieser Zelle ausgehenden Kette gefüllt. Dazu wird der gescannte Buchstabe entsprechend der Permutation q[i] der ersten Spalte dieser Kette ersetzt und in den Platzhalter der zweiten Spalte dieser Kette geschrieben. Die zugehörige Zeilennummer lautet f(i). Ebenso wird der eben erhaltene Buchstabe durch die Permutation r[f(i)] der zweiten Spalte der Kette ersetzt und in die dritte Spalte der Kette geschrieben. Die zugehörige Zeilennummer dieser Zelle ist durch g(f(i)) gekennzeichnet. Der in der dritten Spalte in der zur Kette entsprechenden Zeile stehende Buchstabe entspricht eineindeutig einem zur Wahl stehenden Kandidaten.

(3) Pre-audit

In der Pre-audit-Phase wird das bulletin-board durch Stichproben auf Korrektheit geprüft. Korrektheit meint in diesem Sinne, dass die Einschränkungen, die in Kapitel "(1) pre-voting" beschrieben wurden, erfüllt sind.

Eine öffentliche Stichprobe für einen bestimmten Wahlzettel macht diesen ungültig. Die zugehörige Kette im bulletin-board wird dabei offenbart. Der Wähler kann nun prüfen, ob die Verknüpfung der Permutationen p[i], q[i] und r[f(i)] die identische Abbildung ergeben. Mit einfachen Worten ausgedrückt, heißt dies, dass er prüfen kann, ob am Ende der Kette der Buchstabe durch die Ersetzungen entsteht, den er am Anfang eingeben hat.

Bereits an dieser Stelle ist jedoch das Problem zu erkennen, dass die Kette auf Wunsch entschlüsselt bzw. offenbart werden kann. Es muss hier sichergestellt werden, dass dies nicht durch Unbefugte geschieht.

Wenn x % der Wahlzettel enthüllt werden, in der pre-audit-Phase, so ist die Wahrscheinlichkeit, einen Wahlbetrug aufzudecken, ebenfalls mindestens bei x %. Die Zahl x hängt dabei stark davon ab, welches Szenarium umgesetzt wird, um den Wählern die Möglichkeit zu geben, Stichproben durchzuführen. Dabei sind z. B. die folgenden Szenarien denkbar:

Eine Möglichkeit ist, jedem Wähler genau zwei Wahlzettel zu geben. Der Wähler kann dann entscheiden, welchen der beiden Wahlzettel er zur Verifikation enthüllt und welchen er zur Wahl benutzt. Die Wahrscheinlichkeit, einen Wahlbetrug aufzudecken, liegt dann bei mindestens 50 %. Eine weitere Möglichkeit ist, für jeden Wahlzettel zufällig zu entscheiden, ob er enthüllt wird. Der Zufallsalgorithmus kann dann so gestaltet werden, dass die Zahl x bis auf eine gewisse Ungenauigkeit selbst gewählt werden kann. Alle nicht enthüllten Wahlzettel werden dann an die Wähler verteilt. Natürlich muss hier sichergestellt werden, dass genügend Wahlzettel nicht enthüllt werden, sodass jeder Wähler seine Stimme geltend machen kann. Ebenso ist es denkbar, dass die Wähler das Recht haben, beliebige, noch nicht verteilte Wahlzettel zu enthüllen und damit zu prüfen. Hierbei ist das Problem jedoch am größten, die Anzahl der Wahlzettel richtig abzuschätzen, sodass am Ende jeder Wähler eine Stimme abgeben konnte.

(4) Audit

Die letzte Phase dient ebenfalls der Verifikation des bulletin-boards. Diese Verifikation findet jedoch im wesentlich größeren Maße in der Öffentlichkeit ab, als es in der vorhergehenden Phase der Fall war.

Für jeden Wahlzettel besteht die zugehörige Kette im bulletin-board aus genau drei Elementen. Die ersten beiden Elemente jeder Kette tragen dabei die Informationen, die nicht offenbart werden dürfen. Diese Einschränkung wird hier zum Teil wieder aufgehoben. In dieser Phase wird von jeder Kette entweder der geheimgehaltene Teil des ersten oder aber des zweiten Elements offenbart. Die Wahl, welcher Teil enthüllt wird erfolgt rein zufällig. Da hier niemals beide Teile gleichzeitig enthüllt werden, bleibt das Wahlgeheimnis weiterhin gewahrt. Von dem enthüllten Element wird der Buchstabe des Platzhalters mittels der zugehörigen Permutation ersetzt und mit dem Buchstaben des Platzhalters des folgenden Elements der Kette verglichen. Weichen diese beiden Buchstaben voneinander ab, so liegt hier eine Manipulation vor.

Die Chance eines Betruges wird nun verschwindend gering. Jede Manipulation einer Stimme wird mit einer Wahrscheinlichkeit von 50 % entdeckt. Die Wahrscheinlichkeit, für einen Betrüger nicht entdeckt zu werden, halbiert sich also mit jeder zusätzlich manipulierten Stimme. Da eine große Zahl von Stimmen notwendig ist, um eine Wahl zu beeinflussen, liegt die Chance, den Betrug aufzudecken, also bei fast 100 %. Die genaue Formel für die Wahrscheinlichkeit, dass der Betrüger nicht entdeckt wird, liegt für k manipulierte Stimmen bei ${\displaystyle {\frac {1}{2^{k}}}}$. Schon bei 10 Stimmen ist dieser Wert bereits kleiner als 0,001.

Erweiterungen auf übliche Wahlprinzipien

Bisher wurde für eine Wahl angenommen, dass unter m Kandidaten genau ein Kreuz gesetzt werden darf. Es sollte jedoch möglich sein, mehrere Stimmen in einer Wahl abzugeben. Weiterhin kommt es oft vor, dass mit einem Wahlzettel zwei verschiedene Wahlen ausgeführt werden. In diesem Kapitel wird gezeigt, wie dies gelöst werden kann.

Mehrere Stimmen auf einem Wahlzettel werden im bulletin-board untergebracht, indem aus den Platzhaltern ein y-Tupel wird, wobei y die Anzahl der Wahlen darstellt. Dies bedeutet, dass y verschiedene Buchstaben geschrieben werden. Der erste Buchstabe stellt dabei die Erststimme dar.

Werden z Wahlen mit einem Wahlzettel abgestimmt, so genügt es, z bulletin-boards vorzubereiten, die jeweils unabhängig voneinander sind. Zwar werden dann die Wahlen alle mit einem Wahlzettel getätigt, jedoch werden sie wie verschiedene Wahlen gehandhabt.