Byzantine fault-tolerant vote collection for D-DEMOS, a distributed e-voting system

Abstract

E-voting systems are a powerful technology for improving democracy by reducing election cost, increasing voter participation, and even allowing voters to directly verify the entire election procedure. Unfortunately, prior internet voting systems have single points of failure, which may result in the compromise of availability, voter secrecy, or integrity of the election results. In this thesis, we consider increasing the fault-tolerance of voting systems by introducing distributed components. This is non-trivial as, besides integrity and availability, voting requires safeguarding confidentiality as well, against a malicious adversary. We focus on the vote collection phase of the voting system, which is a crucial part of the election process.We use the DEMOS state-of-the-art but centralized voting system as the basis for our study. This system uses vote codes to represent voters' choices, an Election Authority to setup the election and handle vote collection and result production, and a Bulletin Board for storing the election transcript for the long-term. We extract the vote collection mechanism from the centralized Election Authority component of the original DEMOS system, and replace it with a distributed system that handles vote collection in a Byzantine fault-tolerant manner. In this thesis, we present the design, security analysis, prototype implementation and experimental evaluation of this vote collection component. We present two versions of this component: one completely asynchronous and one with minimal timing assumptions but better performance. Both versions provide immediate assurance to the voter her vote was recorded as cast, without requiring cryptographic operations on behalf of the voter. This way, a voter may cast her vote using an untrusted computer or network, and still be assured her vote was recorded as cast. For example, she may vote via a public web terminal, or by sending an SMS from a mobile phone. Even in these cases, voter's privacy is still preserved.We provide a model and security analysis of the systems we present. We implement prototypes of the complete systems, we measure their performance experimentally, and we demonstrate their ability to handle large-scale elections. Finally, we demonstrate the performance trade-offs between the two versions of the system. We consider the vote collection components we introduce are applicable to any voting system that uses the code-voting technique.

Τα συστήματα διαχείρισης εκλογών είναι μια δυναμική τεχνολογία που επιτρέπει την βελτίωση της δημοκρατικής διαδικασίας μέσω της μείωσης του κόστους υλοποίησης εκλογών, της αύξησης της συμμετοχής των ψηφοφόρων και της αμεσότητας παραγωγής αποτελεσμάτων. Επίσης, δίνουν την δυνατότητα στους ψηφοφόρους να επιβεβαιώσουν άμεσα την ορθή λειτουργία ολόκληρης της εκλογικής διαδικασίας. Δυστυχώς, τα υπάρχοντα τέτοια συστήματα είναι σχεδιασμένα με κεντρικά συστατικά, τα οποία και αποτελούν μοναδικά σημεία αποτυχίας. Αυτό μπορεί να οδηγήσει στην απώλεια διαθεσιμότητας, εμπιστευτικότητας, καθώς και της ακεραιότητας του εκλογικού αποτελέσματος. Σε αυτή τη διατριβή εξετάζουμε την εισαγωγή ανοχής λαθών στα εκλογικά συστήματα, μέσω της εισαγωγής κατανεμημένων συστατικών. Αυτό είναι περίπλοκο γιατί, εκτός από την ακεραιότητα και διαθεσιμότητα, σε ένα εκλογικό σύστημα είναι σημαντικό να διαφυλαχθεί και η εμπιστευτικότητα, απέναντι σε έναν κακόβουλο αντίπαλο. Εστιάζουμε στην φάση συλλογής ψήφων του εκλογικού συστήματος, η οποία είναι ένα κρίσιμο τμήμα της εκλογικής διαδικασίας. Χρησιμοποιούμε το σύγχρονο αλλά κεντρικοποιημένο σύστημα διαχείρισης εκλογών DEMOS σαν βάση για την μελέτη μας. Αυτό το σύστημα χρησιμοποιεί κωδικούς που αντιστοιχούν στις δυνατές επιλογές των ψηφοφόρων, μια Αρχή Εκλογών η οποία αρχικοποιεί τις εκλογές, συλλέγει τις ψήφους και παράγει το αποτέλεσμα, και έναν Πίνακα Ανακοινώσεων για την διατήρηση των στοιχείων των εκλογών μακροπρόθεσμα. Εξάγουμε τον μηχανισμό συλλογής ψήφων από την κεντρικοποιημένη Αρχή Εκλογών του αρχικού συστήματος DEMOS, και τον αντικαθιστούμε με ένα κατανεμημένο σύστημα που χειρίζεται την συλλογή ψήφων με ανοχή σε λάθη Βυζαντινού τύπου. Σε αυτή τη διατριβή, παρουσιάζουμε τον σχεδιασμό, ανάλυση ασφάλειας, την ανάπτυξη και αξιολόγηση της πρωτότυπης υλοποίησης αυτού του κατανεμημένου συστατικού συλλογής ψήφων. Παρουσιάζουμε δύο εκδόσεις αυτού του συστατικού: μία πλήρως ασύγχρονη και μία με ελάχιστες υποθέσεις συγχρονισμού αλλά καλύτερη απόδοση. Και οι δύο εκδόσεις παρέχουν άμεση επιβεβαίωση στην ψηφοφόρο ότι η ψήφος της καταχωρήθηκε όπως υποβλήθηκε, χωρίς να απαιτούνται κρυπτογραφικές λειτουργίες από την πλευρά της ψηφοφόρου. Με αυτόν τον τρόπο, η ψηφοφόρος μπορεί να στείλει την ψήφο της χρησιμοποιώντας έναν μη ασφαλή υπολογιστή ή δίκτυο, και να συνεχίσει να είναι εξασφαλισμένη ότι η ψήφος της καταχωρήθηκε σωστά. Για παράδειγμα, μπορεί να ψηφίσει χρησιμοποιώντας έναν δημόσιο υπολογιστή, ή στέλνοντας ένα σύντομο μήνυμα μέσω κινητού τηλεφώνου. Ακόμη και σε αυτές τις περιπτώσεις, η εμπιστευτικότητα της ψήφου διατηρείται στο ακέραιο. Δίνουμε ένα μοντέλο και μια ανάλυση ασφάλειας για τα συστήματα που παρουσιάζουμε. Υλοποιούμε πρωτότυπα από τα πλήρη συστήματα, μετράμε την απόδοσή τους πειραματικά, και επιδεικνύουμε την ικανότητά τους να χειρίζονται εκλογές μεγάλου μεγέθους. Τέλος, παρουσιάζουμε τις διαφορές απόδοσης ανάμεσα στις δύο εκδόσεις του συστήματος.Θεωρούμε ότι τα συστατικά συλλογής ψήφων που παρουσιάζουμε σε αυτή τη διατριβή μπορούν να βρουν εφαρμογή σε οποιοδήποτε σύστημα διαχείρισης εκλογών που στηρίζεται στην τεχνική της εκπροσώπησης των επιλογών στα ψηφοδέλτια με κωδικούς.