Accountable secure multi-party computation for tally-hiding e-voting

Abstract

With multi-party computation becoming more and more efficient and thus more practical, we can start to investigate application scenarios. One application where multi-party computation can be used to great effect is e-voting. Unlike classical e-voting protocols, one can get tally-hiding e-voting systems. There, some part of the tally (especially the whole set of votes) is not made public. Notwithstanding this, most existing (verifiable) multi-party computation protocols are not suitable for e-voting. A property that is arguably more important than verifiability is missing: accountability -- as a matter of fact, we need external accountability in this setting, where anyone audit the protocol. This is especially of importance for e-voting systems and more researchers are paying attention to it lately. To this effect, we introduce a general multi-party computation protocol that meets all the requirements to be used in e-voting systems. Our protocol achieves accountability and fairness in the honest majority setting and is -- to our best knowledge -- the first one to do so.

Diese Masterarbeit beschäftigt sich mit Secure Multi-Party-Computation (MPC) und deren Nutzen für E-Voting. Wir betrachten MPC-Protokolle, die Accountability bieten. In solchen Protokollen ist es möglich, Manipulationsversuche zu erkennen. Dabei können Parteien, die dies versuchen, eindeutig identifiziert (und dafür belangt) werden. Damit bieten solche Protokolle stärkere Garantien als solche, die nur Verifiability bieten. Die Erwartung ist, dass dies abschreckend wirkt und in Systemen, die MPC-Protokolle mit Accountability benutzen, weniger Manipulationen stattfinden.

Außerdem bieten sich MPC-Protokolle (vor allem mit Accountability) für die Benutzung in E-Voting-Systemen, die tally-hiding sein sollen, an. Tally-hiding bezeichnet Systeme, bei denen die ausgezählten Stimmen nicht (oder nur teilweise) bekannt werden. In vielen anderen E-Voting-Systemen werden alle (anonymisierten) Stimmen oder die ausgezählten Stimmen veröffentlicht, wonach jeder das Wahlergebnis (z.B. die Zusammenstellung eines Parlaments) selbst berechnen kann. Mit einem tally-hiding System könnte stattdessen das Wahlergebnis direkt berechnet werden. Damit bleiben die Stimmen (zu einem größtmöglichen Teil) geheim. Ordinos bietet bereits ein E-Voting-System mit End-To-End-Verifiability an, wobei jedes MPC-Protokoll mit bestimmten Voraussetzungen (z.B. Accountability) zur Berechnung des Wahlergebnisses benutzt werden kann. In dieser Arbeit stellen wir ein Protokoll vor, das diese Voraussetzungen erfüllt und beliebige Funktionen berechnen kann.

Unser Protokoll baut auf einem verbreiteten MPC-Protokoll auf: dem SPDZ-Protokoll. Wie vorheriger Erweiterungen, die Auditability zu SPDZ hinzugefügt haben, erweitern wir dies um Accountability. Einige Versionen von SPDZ mit Accountability existieren zwar bereits, jedoch bieten diese entweder nicht alle Voraussetzungen für Ordinos oder sie sind nicht direkt auf E-Voting-Systeme ausgelegt. Eines dieser Protokolle weist deutliche Ähnlichkeiten zu unserem Protokoll auf, jedoch bietet es keine Fairness (wenn die Mehrheit der beteiligten Parteien nicht versucht die Berechnung zu manipulieren). Die Option, eine fehlgeschlagene MPC-Berechnung ohne die Parteien, die versucht haben, das Protokoll zu manipulieren, zu wiederholen, scheint für E-Voting-Systeme äußerst ungeeignet, da die Wahl dann wiederholt werden müsste. Deshalb bieten wir Fairness, wenn weniger als die Hälfte der Beteiligten versuchen zu manipulieren. Wir hoffen, dass die Abschreckungsfunktion von Accountability groß genug ist, um dies zu gewährleisten. Wie SPDZ setzen wir auf Secret-Sharing. Hierbei erhält jede beteiligte Partei (Compute-Party) einen Share für jeden Eingabewert des MPC-Protokolls. Die Compute-Parties können dann die gewünschte Funktion auf ihrem Share berechnen.* Am Ende kann das Ergebnis aus den Shares wiederhergestellt werden. Hierbei werden mindestens t von n Shares benötigt.** Weniger Shares enthalten keinerlei Informationen über den geshareten Wert. Damit alle Parties ihren Share preisgeben und keinen falschen Share, der das Ergebnis verfälschen würde, benutzen wir Commitments. Anders als für Auditability benötigen wir nicht nur ein Commitment für jeden Eingabewert, um festzustellen, ob das Ergebnis korrekt war -- wir benutzen ein Commitment für jeden Share (jedes Eingabewerts). Damit können wir die Berechnung für jede Party überprüfen und erhalten Accountability. Anders als die bisherigen Protokolle unterstützt unser MPC-Protokoll eine Vielzahl an Commitment-Schemes. In der Masterarbeit findet sich ein Beweis für die Security unseres Protokolls im UC-Framework. Außerdem werden Accountability und Verifiability im KTV-Framework analysiert (und bewiesen). Damit weist unser Protokoll alle Voraussetzungen auf, um in Kombination mit Ordinos (oder anderen E-Voting-Systemen) sichere und überprüfbare Wahlen durchzuführen.

* Ein Trick und Interaktionen zwischen den Parties sind erforderlich, um Multiplikationen von Werten zu unterstützen. ** n ist die Zahl der Compute-Parties. t = ⌈n / 2⌉ entspricht dem Fall, dass mindestens die Hälfte aller Shares benötigt wird.