Secure distributed paillier key generation with application to the Ordinos e-voting system

Abstract

Ordinos is a novel verifiable tally-hiding e-voting system. At its heart, a homomorphic encryption scheme and secure multi-party computation (MPC) are used to tally votes and securely determine the voting result, without necessarily revealing the full tally (e.g., the number of votes per candidate)The proof of concept implementation of Ordinos is based on a threshold variant of the Paillier encryption scheme and two MPC protocols for the comparison of encrypted numbers (greater-than and equality). Due to the threshold construction, the decryption key is shared among a set of trustees. The MPC protocols for comparison require precomputed encrypted randomness of certain shape. Formerly, a trusted party was employed to generate the key shares and randomness and distribute them to the trustees. In this thesis, the trusted party was replaced by MPC protocols that allow to generate the key shares and randomness among the trustees. The protocols provide security against malicious parties in the honest-majority setting. The key generation follows a proposal by Nishide and Sakurai (2010) that is based on verifiable secret sharings and zero-knowledge proofs for committed values. We introduce a few adaptations to reduce its runtime using mostly standard techniques. The generation of randomness is based on the Paillier encryption scheme as an arithmetic black box and standard zero-knowledge proofs for Paillier encrypted values. The protocols were implemented and their performance was evaluated in a local network. Most notablythe implemented key generation protocol for threshold Paillier showed an expected average runtime around 95 minutes for generating 2048-bit keys among 3 trustees with a threshold of 2. Since existing implementations provide security only in the semi-honest setting, this is the first time that an approach with security against malicious parties was implemented and evaluated. Overall, the distributed generation of both key shares and randomness takes considerably more time compared to the use of a trusted party, but avoids security risks and trust problems that occur with trusted parties.

Ordinos ist ein neuartiges verifizierbares E-Voting System mit der sogenannten Tally-Hiding-Eigenschaft. Im Kern werden ein homomorphes Verschlüsselungsschema und sichere Multi-Party Computations (MPC) verwendet, um Stimmen zu zählen und das Ergebnis einer Abstimmung zu bestimmen, ohne notwendigerweise das vollständige Auszählungsergebnis (z. B. die Anzahl der Stimmen je Kandidat) preiszugeben. Die Proof of Concept Implementierung von Ordinos basiert auf einer Threshold-Variante des Paillier-Verschlüsselungsschemas und zwei MPC-Protokollen für den Vergleich von verschlüsselten Zahlen (größer-als und Gleichheit). Aufgrund der Threshold-Variante wird der private Schlüssel unter mehreren Trustees verteilt aufbewahrt (engl.: sharing). Die MPC-Protokolle für die Vergleiche erfordern vorberechnete verschlüsselte Zufallszahlen bestimmter Form. Bisher wurde eine Trusted Third Party eingesetzt, um die Schlüssel-Shares und Zufallszahlen zu generieren und an die Trustees zu verteilen. In dieser Arbeit wurde die Trusted Third Party durch MPC-Protokolle ersetzt mit denen die Schlüssel-Shares und Zufallszahlen unter den Trustees generiert werden. Die Protokolle bieten Sicherheit gegen aktive Angreifer im Honest-Majority Szenario. Die Schlüsselgenerierung basiert auf einem Paper von Nishide and Sakurai (2010), wobei hierzu verifizierbare Secret-Sharings und Zero-Knowledge Beweise für Commitments eingesetzt werden. Um die Laufzeit zu reduzieren, werden einige Anpassungen vorgestellt, die sich überwiegend an Standardtechniken orientieren. Die Generierung der Zufallszahlen basiert auf dem Paillier-Verschlüsselungsschema als arithmetische Black Box und Zero-Knowledge Beweisen für Paillier-Chiffren. Die Protokolle wurden implementiert und ihre Performance in einem lokalen Netzwerk evaluiert. Hervorzuheben ist, dass die implementierte Schlüsselgenerierung eine zu erwartende durchschnittliche Laufzeit von etwa 95 Minuten zwischen 3 Trustees mit einen Threshold von 2 und der Schlüssellänge 2048 Bit benötigt. Bestehende Implementierungen bieten Sicherheit gegen passive Angreifer. Somit setzt diese Arbeit zum ersten Mal ein Ansatz mit Sicherheit gegen aktive Angreifer um und evaluiert diesen. Insgesamt benötigt die verteilte Generierung der Schlüssel-Shares und Zufallszahlen zwar erheblich mehr Zeit verglichen zum Einsatz einer Trusted Third Party, vermeidet aber Sicherheitsrisiken und Vertrauensprobleme, die mit solchen auftreten.