Schwächen in “Bingo Voting”?

Am Freitag wurde Bingo Voting, ein kryptographisches Verfahren zur Durchführung von Wahlverfahren mit Computern, mit dem mit 100.000 Euro dotierten ersten Platz des Deutschen IT-Sicherheitspreises ausgezeichnet. Erste Zweifel kamen mir da gestern, die ich allerdings sehr spontan und ohne Kontrolllesen geäußert habe. Werfern wir noch mal einen genaueren Blick auf das Verfahren.

Die Autoren Bohle, Müller-Quade und Röhrich bzw. Röhrich beschreiben Bingo Voting als coercion-free, bzw. ein Verfahren, bei dem der Wähler nachweislich nicht erpressbar ist. Erpressbar im Zusammenhang mit Wahlen heißt, daß keinerlei Information darüber aussickert, wen der Wähler gewählt oder wen er nicht gewählt hat, und daß er es auch selbst nicht beweisen kann, man also auch keinen Beweis von ihm einfordern kann. Es soll so sein, daß der Wähler im Erpressungsfall gegenüber Dritten stets behaupten, etwas anderes gewählt zu haben, oder die Antwort zu verweigern, und man ihm dabei nicht auf die Schliche kommen kann. Der Wähler könnte also den Kandidaten A wählen und ohne weiteres behaupten, B gewählt zu haben, ohne daß ihm dies irgendwer widerlegen oder einen Beweis von ihm fordern könnte.

Schon bevor man das Verfahren betrachtet hat, kommen Zweifel, ob so eine Anforderung überhaupt allgemein erfüllbar ist:

• Man kann den ganz trivialen Fall betrachten, daß es nur einen Wähler gibt, also das Wahlergebnis direkt seine Stimme offenbart. Das ist zwar doof, stellt aber schon direkt in Frage, wenn jemand einen Beweis für diese Protokolleigenschaft erbracht haben will, ohne dazu eine Mindestzahl von Wählern zu fordern. Eine coercion-free-Behauptung, in der nicht wenigstens drin steht, daß man mindestens 2 Wähler braucht, kann von vornherein nicht stimmen.
• Bekommt ein Kandidat 0 Stimmen, was immer vorkommen kann und sogar zwangsläufig der Fall ist, wenn es mehr Kandidaten als Wähler gibt, dann weiß man und kann nachweisen, daß der Wähler diesen Kandidaten nicht gewählt haben kann und ggf. lügt. Jedenfalls ist dann die Anforderung nicht erfüllt.
• Und auch wenn ein Kandidat alle Stimmen bekommt, weiß man, wer wie gewählt hat. Auch hier ist die Anforderung nicht erfüllt.
• Und dann ist es auch so, daß die Anforderung ja nicht nur auf Nichtwähler bezogen ist, sondern auch auf andere Wähler. Hat ein Kandidat beispielsweise alle bis auf eine Stimme bekommen, dann weiß der, der ihn nicht gewählt hat, auch genau, was alle anderen gewählt haben. Auch da ist die Anforderung nicht erfüllt.

Es ist also offenbar so, daß es – unabhängig vom Verfahren – in der Natur einer Wahl liegt, daß sie nicht in allen Fällen coercion-free sein und der Wähler nicht immer vor Erpressung sicher sein kann. Das ist eben so. Umso fragwürdiger ist es aber, wenn da einer daherkommt und behauptet, sein Verfahren könne das erwiesenermaßen und allgemein, obwohl das unerfüllbar ist. Dann nämlich muß an dem Beweis etwas faul sein, und die Vermutung besteht, daß das Verfahren über die natürlichen Schwächen einer Wahl hinaus weitere Schwächen hat – angefangen mit dem fehlerhaften Beweis. Man muß also sehr vorsichtig sein, wenn einer einem erzählt, sein Verfahren wäre beweisbar sicher. Das ist die berühmte Lücke zwischen plausibel und bewiesen.

Über diese allgemeinen Zweifel hinaus glaube ich bisher auch, daß Bingo Voting noch weitere, individuelle Schwächen hat. Leider sind die Papers nicht so ganz sauber und präzise geschrieben, ich bin mir daher nicht so ganz sicher, ob ich das Verfahren richtig verstanden habe. Deshalb will ich das Verfahren mal anhand eines kleinen Beispiels mit zwei Wählern und zwei Kandidaten durchrechnen, um da eine Diskussionsgrundlage zu schaffen, und bitte um Hinweis, falls ich das Verfahren nicht richtig verstanden habe. Um überhaupt einen interessanten Fall und eine Chance auf Wahlgeheimnis zu bekommen, müssen die Wähler unterschiedlich wählen, denn wählen sie gleich, ist ja alles offensichtlich. Also:

• Wir haben zwei Wähler x und y.
• Wir haben zwei Kandidaten A und B.
• Wir haben insgesamt 6 Zufallszahlen, die ich der Lesbarkeit halber “symbolisch” mit 111, 222, 333,… bezeichne. Gemeint sind eben lange Zufallszahlen.
• Wir haben Commitments und maskierte Commitments() mit den im Paper beschriebenen Eigenschaften, und nennen diese C( ), Cleft( ), Cmiddle( ), Cright( )

Vorbereitungsphase

Es werden vier 2-Tupel aus Name und Zufallszahl (2 Wähler x 2 Kandidaten) erzeugt und deren Commitments veröffentlicht, also C(A:111), C(A:222), C(B:333), C(B:444).

Die Wahl

x betritt die Kabine und wählt A. Der Generator erzeugt 555 und die Wahlmaschine druckt auf die Quittung A:555 B:333. Die unbenutzte Stimme A:111 wird ausgesondert.

y betritt die Kabine und wählt B. Der Generator erzeugt 666 und die Wahlmaschine druckt auf die Quittung A:222 B:666. Die unbenutzte Stimme B:444 wird ausgesondert.

Das Wahlergebnis

Die Maschine verkündet:

• Ergebnis: A: 1 Stimme, B: 1 Stimme
• Kopien der beiden oben ausgedruckten Wahlquittungen, also A:555 B:333 und A:222 B:666
• Liste der nicht verbrauchten Stimmen, also A:111 und B:444 in Übereinstimmung mit dem Wahlergebnis.

Der Korrektheitsnachweis

An dieser Stelle bin ich mir nun trotz mehrmaligen Lesens der deutschen und der englischen Version nicht völlig sicher, ob das von den Autoren so beabsichtigt ist, wie ich es verstanden habe, u.a. weil sie da zwischen dem “Veröffentlichen” und dem beweisen einzelner Quittungen hin- und herspringen und die Bezeichungen etwas wechseln.

Erster Schritt: (Zitat: Die Commitments auf die für diesen Beleg vewrendeten Dummy-Stimmen werden ausgewählt und zusammen mit dem neuen Commit veröffentlicht. Also werden sie letztlich alle veröffentlicht? Wer ist denn überhaupt der, der die Zuordnung und die Zufallszahlen kennt?)

Folgende Commitments werden veröffentlicht:

Cleft(A:555) = C(A:555) [frisch, während der Wahl erzeugt, also ein “Ja”]
Cleft(B:333) = C(B:333) [alt, vor der Wahl erzeugt, also ein “Nein”]
Cleft(A:222) = C(A:222) [alt, vor der Wahl erzeugt, also ein “Nein”]
Cleft(B:666) = C(B:666) [frisch, während der Wahl erzeugt, also ein “Ja”]

Zweiter Schritt: Aus jedem dieser Cleft wird durch Maskierung ein Cmiddle erzeugt, also z. B.
Cmiddle(A:555) = Maskierung(Cleft(A:555)), dann die Reihenfolge der Cmiddle permutiert, und veröffentlicht. Aufgrund der Durchmischung weiß die Öffentlichkeit nicht, welches Cmiddle zu welchem Cleft gehört:

Cmiddle(A:555)
Cmiddle(B:333)
Cmiddle(A:222)
Cmiddle(B:666)

Dritter Schritt: Aus jedem dieser Cmiddle wird durch erneute Maskierung ein Cright erzeugt. Wieder die Reihenfolge durchmischt, damit man nicht sieht, welches Cmiddle zu welchem Cright gehört. Außerdem werden die Inhalte offengelegt. Also

Cright(A:555) , A:555
Cright(B:333) , B:333
Cright(A:222) , A:222
Cright(B:666) , B:666

Man überprüfe, daß die offengelegten Inhalte mit den veröffentlichten Quittungen übereinstimmen. OK.

Vierter Schritt: Es wird eine Zufallsbitfolge gezogen, z. B. 0110 und dementsprechend die Übereinstimmung zwischen Cleft und Cmiddle oder Cmiddle und Cright nachgewiesen, womit Manipulationen aufgedeckt werden sollen, es aber nie einen direkten Pfad von Cleft nach Cright gibt.

Angriff
Habe ich das so richtig verstanden? Wenn ja, dann versuche ich folgenden Angriff:

Aus dem ersten Schritt weiß ich durch Vergleich der Cleft mit der vor der Wahl veröffentlichten Liste der C(…), daß

Cleft(A:555) bedeutet “Ja” (weil frisch)
Cleft(B:333) bedeutet “Nein” (weil alt)
Cleft(A:222) bedeutet “Nein” (weil alt)
Cleft(B:666) bedeutet “Ja” (weil frisch).

Aus dem im vierten Schritt erfolgten öffentlichen Nachweis weiß ich, daß
Cmiddle(A:555) zu Cleft(A:555) gehört, also auch “Ja” bedeutet.
Cmiddle(B:666) zu Cleft(B:666) gehört, also auch “Ja” bedeutet.

Da es pro Zeile zwei “Ja” und zwei “Nein” geben muß, kann ich folgern, daß Cmiddle(B:333) und Cmiddle(A:222) beide “Nein” bedeuten müssen. Somit weiß ich von allen Cmiddle, ob sie “Ja” oder “Nein” bedeuten.

Ebenfalls aus dem vierten Schritt weiß ich, daß Cright(B:333) zu Cmiddle(B:333) gehört, und damit “Nein” heißt. Ich weiß außerdem, daß dazu das Tupel B:333 gehört, was also ein “Nein” in Bezug auf Kandidat B ist..

Ebenso weiß ich, daß Cright(A:222) zu Cmiddle(A:222) gehört, und damit auch “Nein” heißt. Ich weiß außerdem, daß dazu das Tupel A:222 gehört, und dieses ein “Nein” in Bezug auf Kandidat A ist.

Also weiß ich, daß wer auf seiner Wahlquittung B:333 stehen hat, also der Wähler x, bei B ein “Nein” und somit A gewählt hat.

Und ich weiß, daß wer auf seiner Quittung A:222 stehen hat, also der Wähler y, bei A ein “Nein”, also B gewählt hat.

Verallgemeinern wir den Angriff auf größere Wählerzahlen:

• Immer dann, wenn im Nachweisschritt mit der Zufallsbitfolge entweder alle “Ja” oder alle “Nein”-Stimmen in den Übereinstimmungsnachweis zwischen Cleft und Cmiddle kommen, gelingt es, für ganz Cmiddle die Zuordnung zu “Ja” und “Nein” aufzuklären. Danach ist für alle Stimmen, bei denen die Zuordnung zwischen Cmiddle und Cright nachgewiesen wurde, ersichtlich, ob sie “Ja” oder “Nein” bedeuten, was schon das Wahlgeheimnis bricht bzw. durch Abzählen zu weiteren Erkenntnissen führen kann.
• Zugegebenermaßen sinkt die Wahrscheinlichkeit dafür mit steigender Wählerzahl. Man muß aber bedenken, daß durch kooperativ-böswillige Wähler (etwa Angehörige einer radikalen oder kriminellen Partei), die zugunsten des Angriffs ihr eigenes Wahlgeheimnis offenbaren und die Quittung vorlegen, fehlende Informationen ergänzt werden können, und zwar durch Abzählüberlegungen und durch Aufklärung von Cright nach Cmiddle. Das hebt die Wahrscheinlichkeit einer Aufklärung ganz enorm.
• Und selbst wenn Cmiddle nicht vollständig aufgedeckt werden kann, könnte man immer noch erhebliche Wahrscheinlichkeitsüberlegungen anstellen.

So. Hab ich da jetzt einen Fehler gemacht oder ist Bingo Voting unsicher und nicht coercion-free?
Vielleicht hab ich das Protokoll ja auch irgendwo nicht richtig verstanden, z. B. bei der Beweisphase.

Ich bitte jedenfalls um Bestätigung oder Hinweis auf Fehler.

Mir ist übrigens auch überhaupt nicht klar, bei wem und wo eigentlich diese vielen Zufallszahlen und Commitments erzeugt und gespeichert werden sollen, wenn doch angeblich nur der primitive Zufallszahlengenerator vertrauenswürdig ist. Wenn die nämlich nicht vertrauenswürdig gespeichert sind, ist alles futsch. Aber wie sollte das gehen?

Oder wie man so schön sagt: Bingo!