Coercion-resistant cast-as-intended verifiability in electronic voting systems

Abstract

(English) One of the most common fears regarding electronic voting is that a voting device will disregard the voter's intent and cast a different vote instead. An undetectable attack like that on a large scale will allow the adversary to control the election result completely. Therefore, the cast-as-intended verification, which ensures that the ballot contains the voter's choice and not something else, is crucial. Another common fear when introducing electronic voting is coercion, which captures a variety of ways the coercer can use to prevent voters from expressing their will. Hence, coercion resistance is a valuable property of electronic voting as well. One particularly challenging task is to find a trade-off between ensuring a voter cannot be coerced and, at the same time, preventing a malicious voting device from cheating. This thesis explores this trade-off to find how we can provide coercion-resistant cast-as-intended verification. The contributions can be roughly divided into three parts: (1) study in the standard settings, (2) exploration of post-quantum cryptography, and (3) practical constructions and search for the limitations of both properties. In the first part, we give an extensive overview of the current state of the art in electronic voting literature regarding those properties. Then, we put forward two formal definitions for achieving coercion-resistant cast-as-intended verification in settings without pre-exchanged data. After that, we present two practical constructions and prove their security under the proposed definitions. We also show the efficiency of our proposals by providing proof of the concept implementations. In the second part, we switch to post-quantum settings and identify the usability issues rooted in the lattice-based math affecting both proposed solutions. To address those issues, we present a generic transformation that departs from an interactive zero-knowledge system (that might require multiple re-runs to complete the protocol) and obtains a 3-move zero-knowledge system (without re-runs). The transformation combines the well-known Fiat-Shamir technique with several initially exchanged messages. The resulting 3-move system enjoys honest-verifier zero-knowledge and can be easily turned into a fully deniable proof using standard methods. In the final part, we focus on the practical aspects of the coercion-resistant cast-as-intended verification. First, we present the case of a computationally limited voter, which we consider the most realistic. We show that even a computationally limited voter can enjoy coercion-resistant cast-as-intended verification, but a help of a simple aid device for nonce generation is required. Also, we demonstrate that our generic definition easily adapts to the constraints of the limited voter. After that, we present ongoing work that focuses on the cases of extreme coercion based on new and unexplored mechanisms such as delay encryption and blockchain. We show an advanced coercive attack on our first construction and describe an improvement to the second solution that reduces the number of interactions to an optimal three rounds. To summarize, we start by studying coercion-resistant cast-as-intended verification in standard settings, which results in formal definitions and two practical solutions. Then we move into the post-quantum world, where we learn that an extra step is needed to preserve the usability of our previously proposed constructions, which results in the generic transformation to avoid protocol re-runs. After that, we concentrate on a computationally limited voter, which leads to another simple solution and shows the adaptability of our original definitions. Finally, we explore the extreme coercion threats, which result in a new coercion attack on the first construction and upgrade of the second solution.

(Català) Una de les preocupacions més comunes pel que fa al vot electrònic és que el dispositiu de votació no tingui en compte la intenció del votant i emeti un vot diferent. Un atac com aquest, si no fos detectable, a gran escala permetria a l'adversari controlar completament el resultat electoral. Per tant, és crucial permetre la propietat de verificació de la intenció del vot emès, la qual garanteix que la papereta contingui la intenció del votant i no una altra cosa. Una altra preocupació és la coacció, que engloba una varietat de maneres que el coaccionador pot utilitzar per obligar que els votants expressin la seva voluntat. La prevenció de la coacció també és una propietat valuosa del vot electrònic .Una tasca especialment difícil és trobar un compromís entre assegurar que un votant no pot ser coaccionat i, al mateix temps, evitar que un dispositiu de vot compromès faci trampes. Aquesta tesi analitza aquesta problemàtica; les contribucions de la tesi es poden dividir en tres parts: (1) estudi de les configuracions d’escenaris de vot estàndards, (2) exploració de la criptografia post-quàntica i (3) construccions pràctiques i cerca de les limitacions d'ambdues propietats. A la primera part, donem una visió general de l'estat actual de la literatura sobre el vot electrònic relacionada a aquestes propietats. A continuació, proposem dues definicions formals per assolir una verificació resistent a la coacció de la intenció del vot emès, en escenaris on no existeix un intercanvi de dades previ. Després, presentem dues propostes pràctiques i demostrem la seva seguretat sota les definicions proposades. També mostrem l'eficàcia de les nostres propostes implementant proves de concepte A la segona part, canviem a l’escenari post-quàntic amb matemàtiques basades en reticles i identifiquem els problemes d'usabilitat que afectarien ambdues solucions proposades en aquest nou escenari. Per solucionar-los, presentem una transformació genèrica que parteix d'un sistema interactiu de coneixement nul (que podria requerir múltiples re-execucions per completar el protocol) i que obté un sistema de coneixement nul de 3 moviments (sense re-execucions). La transformació combina la coneguda tècnica Fiat-Shamir amb diversos missatges intercanviats inicialment. A la part final, ens centrem en els aspectes pràctics de la verificació resistent a la coacció de la intenció del vot emès. En primer lloc, presentem el cas d'un votant limitat computacionalment, que considerem el més realista. Mostrem que fins i tot un votant amb limitacions computacionals pot gaudir d'una verificació resistent a la coacció de la intenció del vot emès, però requereix l'ajuda d'un dispositiu senzill per a la generació d’una prova. A més, demostrem que la nostra definició genèrica s'adapta fàcilment a les limitacions del votant. Després d'això, presentem un treball recent que se centra en els casos de coacció extrema basats en mecanismes nous i poc explorats com ara el xifrat amb retard i la cadena de blocs. Mostrem un atac coercitiu avançat a la nostra primera proposta genèrica i descrivim una millora de la segona que redueix el nombre d'interaccions a tres rondes òptimes. Com a resum, comencem estudiant la verificació resistent a la coacció de la intenció del vot emès en entorns criptogràfics estàndard, que dóna lloc a definicions formals i dues solucions pràctiques. Aleshores ens movem al món de la criptografia post-quàntica, on cal un pas addicional per preservar la usabilitat de les dues solucions proposades anteriorment: una transformació genèrica per evitar repeticions del protocol. Després d'això, ens concentrem en un votant computacionalment limitat, que condueix a una altra solució senzilla i mostra l'adaptabilitat de les nostres definicions originals. Finalment, explorem les amenaces de coacció extremes, que donen lloc a un nou atac de coerció a la primera solució i a una actualització de la segona solució.