Electronic Voting Systems

4.5 Anonyme Kanalsysteme

Das allgemeine Paradigma des anonymen Kanals kann durch eine Mix-Variante realisiert werden, in der wechselseitig unabhängige Administratoren jeweils eine Mix-Einheit kontrollieren. Wenn mindestens ein Administrator ehrlich arbeitet, dann realisieren Mix-Systeme Anonymität unter kryptographischen Annahmen.

4.5.1 Konventioneller Mix-Kanal

Chaum publizierte 1981 das erste anonyme E-Wahlschema (Chaum, 1981), das auf k Mix-Einheiten und einem Auswertungs-Server und BBS beruht. Das Protokoll erfordert jedoch einen vertrauenswürdigen Auswertungs-Server. Wir geben als Fallbeispiel eine Modifikation des Protokolls von Chaum an, wobei ein direktes Codierungsschema eingesetzt wird.

4.5.1.1 Reservierungsprotokoll

Jeder Client generiert ein zufälliges asymmetrisches Schlüsselpaar , verschlüsselt den öffentlichen Schlüssel (= Pseudonym) durch einen Transformations-Algorithmus und sendet

mit seiner Signatur zum BBS. Die Authentizität und Berechtigung der Teilnehmer wird vom BBS verifiziert.

Die erste Mix-Einheit entschlüsselt alle empfangenen Nachrichten mit seinem geheimen Schlüssel, mischt die entschlüsselten Daten und überträgt das Ergebnis zum BBS.
Die weiteren Mix-Einheiten führen dieselbe Aufgabe nacheinander aus.
Im BBS erscheinen die öffentlichen Schlüssel aller Wähler.
Jeder Wähler verifiziert, ob sein Schlüssel in dieser Liste vorkommt. Sobald ein Wähler feststellt, daß sein Schlüssel nicht erscheint, bricht das Protokoll ab und beginnt erneut.

4.5.1.2 Wahlprotokoll

Jeder Client signiert sein Votum mit dem Schlüssel überträgt zusammen mit seiner Signatur zum BBS.
Die Mix-Einheiten führen analoge Anonymisierungsoperationen aus.
Nach Ende der Operationen steht die Liste im BBS.
Jeder Wähler kann überprüfen, ob sein Votum und seine Signatur korrekt sind.

	Anforderungen (Beschreibung)
Authentifikation	Die Authentifikation erfolgt über eine digitale Signatur und erfordert einen Trust-Center, der die Zertifizierung der Teilnehmerschlüssel abwickelt. Versucht eine unautorisierte Person teilzunehmen, so muß diese eine Signatur eines anderen Teilnehmers fälschen, was jedoch praktisch unmöglich ist, wenn ein sicheres Signaturschema eingesetzt wird.
Übertragungsintegrität	Mix-Stationen und/oder Auswertungs-Server können die Übertragungsstrecke stören, doch decken die verifizierenden Wähler den Angriff auf.
Korrektheit	Wenn Wähler und/oder eine unabhängige Instanz die Auswertung prüfen, dann ist die Korrektheit der Ermittlung gegeben.
Verifizierbarkeit	Das System erreicht die individuelle Verifizierbarkeit.
Vertraulichkeit	Durch die Mix-Codierungen wird Vertraulichkeit der Kommunikation erreicht.
Nichtvermehrbarkeit	Sobald das Reservierungsprotokoll abgeschlossen ist, kann wegen der sicheren Signaturschemen kein böswilliger Administrator die Wahlscheine vermehren, vorausgesetzt, alle Teilnehmer verifizieren ihre Schlüsselabgabe (Reservierungsprotokoll).
Nichtbeeinflußbarkeit	Nichtbeeinflußbarkeit wird technisch nicht gewährleistet, es sei denn, die Mix-Server beginnen mit der Anonymisierung erst nach dem Ende der Wahlzeit.
Wahlgeheimnis	Das Schema benützt einen Mix-Kanal, der Nichtrückverfolgbarkeit im komplexitätstheoretischen Sinne gewährleistet.
Unmittelbarkeit	Unmittelbarkeit bleibt technisch unmöglich, weil die Verwendung bestimmter Pseudonyme vor der Wahl verlangt werden kann.
Effizienz	Die Durchgangskomplexität beträgt zwei Durchgänge, wobei der Wähler zweimal verifizieren muß. Die Nachrichtenlänge erhöht sich proportional zur Anzahl der Mix-Einheiten.
Skalierbarkeit	Bei großen Systemen bleibt ein einziger anonymer Kanal sehr aufwendig. Eine verteilte Struktur aus vielen Mix-Servern erreicht erhöhte Skalierbarkeit.
Ortsunabhängigkeit	Das System ermöglicht Netz-Szenario und Wahlzellen-Szenario
Flexibilität	Das Signaturschema erlaubt den Einsatz beliebiger Formate.
Änderbarkeit	Da der Wähler das Pseudonym im Reservierungsprotokoll festgelegt hat, besteht die Möglichkeit der Änderung. Diejenigen Wähler, die ihr Votum ändern möchten, führen das Wahlprotokoll erneut aus.

4.5.2 Erweiterungen und Modifikationen

Eine effiziente Weiterentwicklung des Mix-Kanals von Chaum wurde von Park, Itoh und Kurosawa vorgenommen (Park/Itoh/Kurosawa, 1993) und von Birgit Pfitzmann durch eine Reihe von Angriffen gebrochen (Pfitzmann, 1994). Eine modifizierte Variante wurde von Sako und Kilian präsentiert (Sako/Kilian, 1995), die das Kriterium der Unmittelbarkeit erreicht, wenn ein informationstheoretisch sicherer Kanal zwischen Client und Administrator existiert. Solche physikalischen Annahmen sind in einem Netz-Szenario unrealistisch. "Sako and Kilian proposed a receipt-free voting scheme, but the computational complexity is quite large when it is large scaled, and the voting is limited to yes/no" (Okamoto, 1996, S. 22). Außerdem kompromittierten die Wissenschaftler Horster und Michels das System durch neue Angriffe: "This results in the insecurity of the voting scheme under the commonly used assumption, that only one Mix-center must be honest" (Horster/Michels, 1996, S. 131).

Weitere anonyme Kanalsysteme wurden u.a. von Ogata, Kurosawa, Sako, Takatani (Ogata/Kurosawa/Sako/Takatani, 1997), Abe (Abe, 1998) und Jakobsson (Jakobsson, 1998) vorgeschlagen, die auf einem Schwellwertschema beruhen und die Integrität der Mix-Kommunikation verbessern. Die Mix-Server müssen kein wechselseitiges Vertrauen aufbringen, um die Korrektheit ihrer Outputdaten sicherzustellen. Diese Schemen zeichnen sich durch die folgenden Eigenschaften aus:

Die Eingabe besteht aus einer Menge von Nachrichten, die mit dem (E-Gamal-) Codierungschema verschlüsselt wurden. Die Ausgabe ist eine permutierte Liste korrespondierender decodierter Nachrichten.
Der Entschlüsselungsprozeß kann durch beliebige k von n Mix-Einheiten ausgeführt werden. Die Mix-Einheiten dechiffrieren nach einem Schwellenwertschema. Sie teilen untereinander den geheimen Dechiffrierungsschlüssel. Die Entschlüsselung ist für weniger als k Mix-Einheiten unmöglich.
Der Entschlüsselungsprozeß zeichnet sich durch Robustheit aus. Eine Untermenge betrügerischer Mix-Einheiten wird mit hoher Wahrscheinlichkeit durch ehrliche Mix-Stationen ausgeforscht. Solange mindestens eine von k Mix-Station ordungsgemäß arbeitet, ist die Korrektheit der Ausgabe praktisch garantiert.
Die Geheimhaltung bleibt sichergestellt, wenn mindestens eine von k Mix-Einheiten korrekt funktioniert.

Diese Protokolle brauchen mehrere Durchgänge und Aufzeichnungen einzelner Arbeitsschritte im BBS sowie z.T. Zero-Knowledge-Beweise. Außerdem verringert sich das Niveau der Geheimhaltung, da die Stimmen rückverfolgbar sind, wenn böswillige k von n Mix-Einheiten kooperieren.

Der Client hat beim Schema von Jakobsson minimalen Aufwand zu leisten (Jakobsson, 1998), da er die Nachricht mit nur einem öffentlichen Kollektivschlüssel codieren muß. Trotzdem ist der Datenaufwand für BBS-Aufzeichnungen hoch. Die Anonymität ist dann aufgehoben, wenn der geheime Dechiffrierungsschlüssel ausgeforscht wird. Die Effizienz konnte neuerdings stark durch den Flash-Mix gesteigert werden (Jakobsson, 1999).

"By introducing novel methods for robust protocol design, to substitute for costly zero-knowledge schemes, we are able to produce a mixing scheme with significantly lower costs of operation than all previously known such schemes. The scheme takes a list of ElGamal encrypted messages, and produces as output a permuted list of encryptions of the same plaintext messages, such that corresponding items of the input and output cannot be correlated. The scheme has the novel feature of not requiring the knowledge of a secret key corresponding to the public key used to encrypt the messages constituting the input to the mix-network... Here, the output items are either the plaintexts that correspond to the input ciphertexts, or (as in this paper) ciphertexts that correspond to the same plaintexts as the input ciphertexts. In this paper, we use standard ElGamal encryption, and participants contributing to the input list simply encrypt their messages using an ElGamal type public key associated with the mix-network" (Jakobsson, 1999, http://www.bell-labs.com/user/markusj/cv.html).