Demokratie ist keine Abstimmung, sondern eine Stimmenzählung.
Tom StoppardFür Kryptographieforscher ist die elektronische Abstimmung in erster Linie nicht mit der Abstimmungsmaschine und nicht mit der Online-Abstimmung verbunden - sie ist nur ein
Bereich für die mathematische Forschung . E-Voting-Forschung erstellt Protokolle, wichtige mathematische Komponenten, sichere und
überprüfbare Abstimmungssysteme oder Systeme, in denen unabhängige Prüfer und Wähler die Richtigkeit der Stimmenzahl sicher überprüfen können. Diese Systeme sind keine einfachen theoretischen Arbeiten, sondern bereits echte Technologien für echte Wahlen: In Tacoma Park, Maryland, vertrauten die Wähler dem
Scantegrity II- System, das auf unsichtbaren Stimmzetteln basiert, und die Kryptographen selbst verwendeten
Helios- Online-Abstimmungssysteme für die
Wahl der Führung.
Die elektronische Abstimmung ist ein äußerst kompliziertes Thema. In diesem Artikel beschränke ich mich daher auf Schlüsselkonzepte: Was bedeutet sichere Sprachüberprüfung, wie kann ich Stimmen zählen, ohne sie einzeln anzusprechen, und was verhindert, dass Wähler betrügen. Ich werde Ihnen keine vollständige Beschreibung des gesamten Protokolls der elektronischen Abstimmung mit all seinen Nuancen geben, aber diejenigen, die dies wünschen, können unabhängig nach Arbeiten zu diesem Thema suchen, von
denen es viele gibt .
Sichere Bestätigung
Was kann man von einem sicheren Abstimmungssystem erwarten?
Erstens und am offensichtlichsten: Sie müssen überprüfen, ob die Stimmzettel korrekt gezählt wurden, damit jeder bestätigen kann, dass die endgültige Zählung gemäß der Anzahl der von den Wählern ausgefüllten Stimmzettel erfolgt. Die Prüfung sollte keine zusätzlichen Informationen enthalten, außer Summen. Insbesondere sollte der Prüfer nicht erraten können, wer abgestimmt hat. Dies entspricht der klassischen manuellen Papierwahl.
Zweitens ist es notwendig, dass jeder Wähler sicherstellen kann, dass seine Stimme gezählt und korrekt gezählt wird. Dies muss ohne Offenlegung seiner Stimme geschehen, und in einem allgemeineren Fall sollte der Wähler nicht nachweisen können, wen er gewählt hat. Dies geschieht, um Zwang zu beseitigen und um es den Wählern zu ermöglichen, einen Kandidaten frei zu wählen, ohne die Konsequenzen ihrer Wahl zu fürchten.
Schließlich sollte das Abstimmungssystem vor Betrug geschützt werden: Der Wähler sollte nicht mehr als einmal abstimmen können und es sollte nicht die Möglichkeit geben, den Stimmzettel zu ändern oder zu kopieren. Außerdem dürfen nur registrierte Wähler wählen können.
Zusammenfassend lässt sich sagen: Wir brauchen öffentliche Kontrolle, Vertrauen der Wähler, Widerstand gegen Zwang und Integrität der Wahlen. Diese Prinzipien wurden in einer grundlegenden Studie von Chaum, Neff und anderen dargelegt, die Anfang der 2000er Jahre veröffentlicht wurde.
Grundprinzipien
Die meisten klassischen E-Voting-Protokolle funktionieren wie folgt:
- Der Wähler erhält einen Token in Form eines Bulletins, der sich je nach Wahl ändert. Unterschiedliche Wähler erhalten unterschiedliche Stimmzettel.
- Der Wähler verschlüsselt den Stimmzettel (mit einer speziellen Art der Verschlüsselung, mit der die Magie der elektronischen Abstimmung funktioniert, und sendet ihn, damit die Abstimmungsorganisatoren einen verschlüsselten Stimmzettel erhalten.
- Die Organisatoren veröffentlichen verschlüsselte Newsletter am Schwarzen Brett, dem „öffentlich-rechtlichen Rundfunkkanal mit Speicher“, im Fachjargon der Kryptographen - um es einfach auszudrücken, auf so etwas wie Pastebin.
- Die Organisatoren kombinieren verschlüsselte Stimmzettel, um ein zwischengespeichertes Ergebnis zu berechnen. Dann entschlüsseln sie es (aber nicht die Stimmzettel selbst!) Und veröffentlichen die Ergebnisse.
- Nach Erhalt des Ergebnisses und der verschlüsselten Stimmen kann jeder die Richtigkeit überprüfen.
Sichere Anzahl: Homomorphe Verschlüsselung
Im vierten Schritt kombinieren die Organisatoren Kryptogramme, um ein neues Kryptogramm zu erstellen, das die Summe der einzelnen Stimmen verschlüsselt. Zu diesem Zweck verwenden elektronische Abstimmungsschemata das Enc () - Verschlüsselungsschema, in dem Sie Enc (v1 + v2) berechnen können, wobei nur Enc (v1) und Enc (v2) zur Verfügung stehen und der Verschlüsselungsschlüssel nicht bekannt ist. Solche Verschlüsselungsschemata werden als
homomorph bezeichnet .
Wenn dies beispielsweise stark vereinfacht wird, tun die US-Wähler am 8. November Folgendes:
- Sie erhalten den Clinton-Newsletter und den Trump-Newsletter von den Organisatoren (der Einfachheit halber werden wir nur zwei Kandidaten berücksichtigen).
- Sie schreiben Enc (1) auf einen Stimmzettel und Enc (0) auf den anderen, wobei sie den von den Organisatoren ausgegebenen öffentlichen Schlüssel als Schlüssel verwenden.
Verschlüsselte Stimmzettel werden dann zusammen mit der Wähler-ID an der Pinnwand veröffentlicht. Ich kenne jeden, der abgestimmt hat, aber es ist unmöglich zu verstehen, wer genau ist, da jedes Enc (0) und Enc (1) einzigartig ist und wir eine starke und zufällige Verschlüsselung verwenden. Wenn die Verschlüsselung deterministisch war, könnte der Wähler gezwungen sein, seine Stimme preiszugeben, indem er erneut Enc (0) berechnet und mit dem Wert auf der Tafel vergleicht.
Schließlich kombinieren die Organisatoren alle Stimmzettel für Clinton und erhalten das Ergebnis von Enc (die Anzahl der Stimmen für Clinton). Dann machen sie dasselbe mit den Stimmzetteln für Trump und erhalten Enc (die Anzahl der Stimmen für Trump). Dann nehmen sie den Entschlüsselungsschlüssel, entschlüsseln diese beiden Werte und erklären den Gewinner.
Wie finde ich ein homomorphes Verschlüsselungsschema? Ziemlich einfach - Schaltungen wie RSA und ElGamal sind in ihrer Grundform homomorph, weil sie die Gleichung erfüllen
Enc (v1) × Enc (v2) = Enc (v1 × v2)
Aber das ist nicht genau das, was wir brauchen - es ist ein multiplikativer Homomorphismus, aber wir brauchen einen additiven. Es gibt Tricks, die RSA- und ElGamal-Schemata in additiv homomorphe Schemata verwandeln. Stattdessen werde ich ein weniger bekanntes Schema zeigen, das sofort additiv homomorph ist:
Das Paye-Kryptosystem verschlüsselt die Nachricht v1 bis
Enc (v1) = g
v1 r1
n mod n
2Wobei n = pq und g fest sind und r1 eine zufällige ganze Zahl von] 1 ist; n
2 [. Deshalb haben wir:
Enc (v1) × Enc (v2) = (gv1r1n) × (gv2r2n) modn2 = gv1
+ v2 (r1r2) nmodn2 = Enc (v1 + v2)
Das heißt, das Peye-Schema kann verwendet werden, um verschlüsselte Stimmen zu berechnen.
Um zu betrügen, möchte ein Wähler möglicherweise Enc (10000) anstelle von Enc (1) in den Stimmzettel schreiben, um dem Kandidaten Stimmen hinzuzufügen. Bei schlechten Absichten können Sie Enc (very_large_number) schreiben, so dass dies zu einem Überlauf des gesamten Systems und zu einem Ausfall des gesamten Systems führt. Wie kann die Sprachgültigkeit (0 oder 1) ohne Entschlüsselung garantiert werden?
Die Lösung ist
nicht interaktives Zero-Knowledge (NIZK). Der NINR-Beweis ist ein sehr komplexes und äußerst leistungsfähiges kryptografisches Objekt: In unserem Fall kann der Wähler nachweisen, dass sein Kryptogramm 0 oder 1 enthält, ohne jedoch die verschlüsselte Nachricht selbst anzuzeigen. Im allgemeinen Fall ermöglichen NINR-Beweise dem Prüfer, den Prüfer von der Wahrheit der Aussage zu überzeugen, indem er ihm nur einen Datensatz ohne andere Arten von Interaktion sendet.
Das vielleicht einfachste System ohne Offenlegung ist
das Schnorr-Schema : Nehmen wir an, Sie kennen die Lösung für das Problem des diskreten Logarithmus (die schwierige Aufgabe hinter
DSA und Verschlüsselung auf elliptischen Kurven) und möchten beweisen, dass Sie die Lösung kennen, ohne die Lösung selbst offenzulegen. Das heißt, Sie kennen x so, dass g
x = y mod p ist, und der Prüfer kennt nur g, y und p. Um den Rezensenten zu überzeugen, spielen Sie das folgende Spiel:
- Wählen Sie eine Zufallszahl r und senden Sie den Wert g r an den Tester (Verpflichtung).
- Sie erhalten eine Zufallszahl s vom Tester (Anruf).
- Senden Sie an den Prüfer s = r + cx.
- Der Prüfer berechnet g s = g r + cx und überprüft, ob es gleich g r × y c = g r × (g x ) c ist .
In diesem interaktiven Protokoll gibt der Prüfer den Wert von x nicht an, da er nur Zufallszahlen sendet. Allerdings kann nur der Prüfer, der x kennt, s senden und den letzten Test bestehen.
Um ein solches interaktives Protokoll in ein nicht interaktives Protokoll umzuwandeln (eines, das mit einem Datensatz gesendet werden kann), werden NINR-Beweise erstellt. Wir spielen dieses Spiel alleine und geben vor, ein Tester zu sein, damit der echte Tester sicherstellt, dass wir keinen NINR-Beweis entwickeln können, ohne die nachgewiesene Aussage zu kennen.
Fazit
Schlüsselideen in diesem Artikel diskutiert:
- Das Hauptproblem bei einem sicheren elektronischen Abstimmungssystem ist die öffentliche Hörbarkeit. Dies wird erreicht, indem verschlüsselte Newsletter in einem öffentlich zugänglichen Forum veröffentlicht werden. Die Wähler sollten auch den Mechanismus beschreiben, der die Bestätigung selbst durchführt.
- Die Richtigkeit der Abstimmung wird bestätigt, indem jeder Wähler mit einem eindeutigen Ausweis autorisiert wird und den Wählern Zugang gewährt wird, um zu überprüfen, ob ihr Stimmzettel 1) gezählt und 2) nicht geändert wurde.
- Wähler können nicht dafür bestraft werden, dass sie für „falsche“ Kandidaten gestimmt haben, weil sie sich gegen Zwang wehren, was insbesondere durch unvorhersehbare und probabilistische Verschlüsselung erreicht wird.
- Die Privatsphäre von Stimmzetteln wird durch die Tatsache gewährleistet, dass verschlüsselte Stimmen nicht entschlüsselt werden und nur das mit homomorpher Verschlüsselung erstellte Ergebnis entschlüsselt wird.
- Betrug funktioniert nicht, wenn wir die Wähler dazu zwingen, kryptografische Beweise für die Gültigkeit ihres Stimmzettels mithilfe von NINR zu veröffentlichen.
Die hier beschriebenen Konzepte und Technologien mögen tief und komplex erscheinen, aber in Wirklichkeit ist dies nur die Spitze des Eisbergs. Sie können kein sicher funktionierendes elektronisches Abstimmungssystem erstellen, indem Sie einfach der Beschreibung folgen. Zum Beispiel habe ich Details wie die Art und Weise, wie Wähler ihre Stimmzettel in der Praxis überprüfen, den Grund für die Verwendung des NINR-Servers usw. weggelassen. Das Fazit ist, dass jedes sichere elektronische Abstimmungsprotokoll eine sehr komplizierte Sache und voller Nuancen ist und die tatsächliche Implementierung aufgrund menschlicher und organisatorischer Faktoren zusätzliche Komplexität hinzufügt.
Um mehr über Kryptographie zum Thema elektronische Abstimmung zu erfahren, können Sie diese hochwertigen Materialien studieren: