In an electronic election several cryptographic proofs are implemented to guarantee that all the process has been fair. Many cryptographic primitives are based on the hardness of the discrete logarithm, factorization and other related problems. However, these problems are efficiently computable with a quantum computer, and new proofs are needed based on different assumptions not broken by quantum computers. Lattice based cryptography seems one of the most promising post-quantum alternatives. In this thesis we present a coercion resistant cast as intended proof and a proof of a shuffle, both completely based on lattice problems as Inhomogeneous Short Integer Solution (ISIS) and Ring Learning With Errors (RLWE). With the first we prove to the voter that his vote correctly encodes his voting option, without allowing him to prove to a third party that he has chosen a specific option, to avoid the possibility of vote selling. Shuffles are permutations and re-encryptions of casted votes performed by mixing network nodes (mix- net nodes), so that the output can not be related with the input and nobody can link a decrypted vote with the voter who casted it. Given that the goal is to make the output not linkable to the input it is essential to provide a proof of it being a correct shuffle that has preserved the integrity of the votes, without deleting, adding of modifying any of them. To prove both things we have constructed non interactive zero-knowledge proofs, from which anyone can be convinced that a statement is true (with overwhelming probability over a security parameter) with- out revealing any information about the elements that witness it being true.
In an electronic election several cryptographic proofs are implemented to guarantee that all the process has been fair. Many cryptographic primitives are based on the hardness of the discrete logarithm, factorization and other related problems. However, these problems are efficiently computable with a quantum computer, and new proofs are needed based on different assumptions not broken by quantum computers. Lattice based cryptography seems one of the most promising post-quantum alternatives. In this thesis we present a coercion resistant cast as intended proof and a proof of a shuffle, both completely based on lattice problems as Inhomogeneous Short Integer Solution (ISIS) and Ring Learning With Errors (RLWE). With the first we prove to the voter that his vote correctly encodes his voting option, without allowing him to prove to a third party that he has chosen a specific option, to avoid the possibility of vote selling. Shuffles are permutations and re-encryptions of casted votes performed by mixing network nodes (mix- net nodes), so that the output can not be related with the input and nobody can link a decrypted vote with the voter who casted it. Given that the goal is to make the output not linkable to the input it is essential to provide a proof of it being a correct shuffle that has preserved the integrity of the votes, without deleting, adding of modifying any of them. To prove both things we have constructed non interactive zero-knowledge proofs, from which anyone can be convinced that a statement is true (with overwhelming probability over a security parameter) with- out revealing any information about the elements that witness it being true.
Electronic voting solutions are built on complex cryptographic tools to guarantee security and fairness. Currently, those tools are based on hardness assumptions of discrete logarithm, factorization and other classical problems. While they are hard to break in classical computers, there are efficient quantum algorithms to solve using quantum computers of the near future. Thus, there is a need to develop voting protocols that are resistant to quantum attacks. Verifiable shuffling based voting systems are a popular use-case of mix-networks first proposed by Chaum four decades ago [Cha81] as a general tool for building anonymous communication systems. A decade later the quantum threat was known and since then only a few studies searched for post-quantum secure mix-nets. Recently, Costa, Martinez and Morillo introduced new arguments of shuffle for RLWE ciphertexts and how to prove the correctness of the shuffling without leaking sensitive info [CMM17]. In this thesis, we provide exact, shorter proof of Costa et al.’s lattice-based shuffling arguments. As a result, we obtain a practical non-interactive zero-knowledge proof having a runtime of 1 second per voter.
This PhD thesis focuses on lattice-based cryptography and how to apply it to build post-quantum online voting systems. It is the result of the research done by the author at Scytl in close collaboration with Dr. Paz Morillo, from the Department of Applied Mathematics at UPC and Ramiro Martínez, PhD student. As part of her work at the electronic voting company Scytl, the author has participated in the design of several electronic voting systems as well as in their implementation, by providing support to the development team. Nevertheless, all these systems use standard and well-known cryptographic primitives, i.e., not lattice-based primitives, to ensure that the security requirements are fulfilled. Due to this, one of the main challenges of this PhD has been to start researching on a field which was not familiar to the author and contribute to its state of the art. This has allowed the company to enter the post-quantum world by participating in a project which aims to implement a lattice-based online voting system. The thesis has the following contents: an introduction to the lattice theory by describing some of its basic concepts and the computational problems in which the security of lattice-based cryptosystems relies. In this first part it is also described in detail those cryptosystems that are used as building blocks of three new protocols proposed in the thesis: a lattice-based coercion-resistant cast-as-intended protocol, a post-quantum mix-net and a fully post-quantum proof of a shuffle. The former is the lattice version of an existing protocol and allows the voter to check that the vote cast contains the selected voting options. The second and third protocols are the result of the research on lattice-based mix-nets. Two constructions are proposed: the first one allows to demonstrate that a mix-node has permuted and re-encrypted a list of RLWE ciphertexts without modifying them, but it cannot be considered fully post-quantum since the binding property of the commitment scheme relies on classical computational problems. The second one is fully post-quantum since all the cryptographic schemes used for building it, i.e., commitment scheme and zero-knowledge proofs, are based on lattices. Last but not least, for this second proposal a security definition and a proof of security are also provided. Finally, the last part of the thesis consists of building a post-quantum online voting system using as building blocks the protocols already presented and existing lattice-based constructions. This system is considered secure under quantum attacks and provides long-term privacy. It also guarantees vote anonymity, vote authenticity, vote integrity, individual verifiability and receipt-freeness. The algorithms involved in each phase are described in detail as well as the interaction among the participants. An implementation of this system is not given as part of this thesis although a lattice-based online voting system based on that is already being implemented at the company. Aquest tesi es centra en la criptografia basada en reticles i com aplicar-la a la construcció de sistemes de votació electrònica post-quàntics. És el fruit de la recerca feta per l'autora de la tesi a Scytl en estreta col·laboració amb la Dra. Paz Morillo, del Departament de Matemàtica Aplicada de la UPC i en Ramiro Martínez, estudiant de doctorat. Com a part de la seva feina a l'empresa de vot electrònic Scytl, l'autora ha participat tant en el disseny de sistemes de votació electrònica com en la seva implementació, donant suport a l'equip de desenvolupament. No obstant, tots aquests sistemes utilitzen primitives criptogràfiques estàndard (primitives no basades en reticles) per assegurar que els requisits de seguretat es compleixen, i és per aquest motiu que un dels principals reptes d'aquest doctorat ha estat fer en recerca en un camp que no era familiar per l'autora, i contribuir-hi. Per altra banda, això ha permès a l'empresa endinsar-se en el món post-quàntic i participar en un projecte que té per objectiu implementar un sistema de vot electrònic basat en reticles. Aquest tesi consta dels següents continguts: una introducció a la teoria dels reticles on es descriuen alguns dels seus conceptes bàsics i els problemes computacionals dels quals depèn la seguretat dels criptosistemes basats en reticles. En aquesta primera part també es descriuen en detall aquells criptosistemes utilitzats en la construcció dels tres nous protocols presentats en aquesta tesi: un protocol basat en reticles resistent a la coacció i que ofereix verificabilitat “cast-as-intended”; una “mix-net post-quàntica” i una prova de coneixement nul totalment post-quàntica que permet demostrar que la barreja de vots s'ha realitzat correctament. El primer protocol és la versió basada en reticles d'un protocol ja existent i permet que el votant comprovi que el vot emès conté les opcions que havia seleccionat. El segon i el tercer protocol són el resultat de la recerca feta en el camp de les mix-nets basades en reticles. Es proposen dues construccions: la primera d'elles permet demostrar que un node de la mix-net ha barrejat i rexifrat una llista de xifrats RLWE sense modificar-los, però no es pot considerar totalment post-quàntica ja que la propietat de lligar de l'esquema de compromís utilitzat per construir la prova es basa en problemes computacionals clàssics. La segona construcció és totalment post-quàntica ja que tots els esquemes criptogràfics utilitzats en el seu disseny, és a dir, esquema de compromís i proves de coneixement nul, estan basats en reticles. Finalment, però no per això menys important, per aquesta segona proposta també es dóna una definició de seguretat i una prova de seguretat. L'última part de la tesi consisteix en construir un sistema de vot online post-quàntic, utilitzant com a components els protocols prèviament presentats i construccions ja existents basades en reticles. El sistema es considera segur en front atacs quàntics i ofereix privadesa a llarg plaç. També garanteix l'anonimat del vot, la seva autenticitat i integritat, verificabilitat individual i resistència a la coacció. Es descriuen en detall tant els algoritmes executats a cada fase com la interacció entre els seus participants. Com a part de la tesi no s'inclou cap implementació del sistema tot i que l'empresa està implementant un sistema de vot online basat en el que es presenta en aquesta tesi.
We propose a lattice-based electronic voting scheme, EVOLVE (Electronic Voting from Lattices with Verification), which is conjectured to resist attacks by quantum computers. Our protocol involves a number of voting authorities so that vote privacy is maintained as long as at least one of the authorities is honest, while the integrity of the result is guaranteed even when all authorities collude. Furthermore, the result of the vote can be independently computed by any observer. At the core of the protocol is the utilization of a homomorphic commitment scheme with strategically orchestrated zero-knowledge proofs: voters use approximate but efficient "Fiat-Shamir with Aborts" proofs to show the validity of their vote, while the authorities use amortized exact proofs to show that the commitments are well-formed. We also present a novel efficient zero-knowledge proof that one of two lattice-based statements is true (so-called OR proof) and a new mechanism to control the size of the randomness when applying the homomorphism to commitments. We give concrete parameter choices to securely instantiate and evaluate the efficiency of our scheme. Our prototype implementation shows that the voters require 8 milliseconds to submit a vote of size about 20KB to each authority and it takes each authority 0.15 seconds per voter to create a proof that his vote was valid. The size of the vote share that each authority produces is approximately 15KB per voter, which we believe is well within the practical bounds for a large-scale election.
The ultimate goal in modern secure e-voting is to enable everyone to verify whether the final election result correctly reflects the votes chosen by the (human) voters, without exposing how each individual voted. These fundamental security properties are called end-to-end verifiability and voter privacy. Unfortunately, it turns out to be very challenging to pursue these properties simultaneously, especially when the latter must be future-proofed against the rise of quantum computers. In this work, we show, for the first time, a practical approach to do this. We present Epoque, the first end-to-end verifiable, voter-private, post-quantum-secure homomorphic e-voting protocol. It achieves its properties through the combination of practical lattice-based cryptographic primitives only, in a novel way. We formally prove all our security claims under common trust and hardness assumptions. At the core of Epoque lies an efficient identity-based encryption (IBE) scheme with blazingly fast master-key decryption. It is the component that makes the efficient tallying of thousands or millions of ballots a practical possibility. In order to demonstrate its practicality, we fully implemented it and provide detailed benchmarks; we believe this latter contribution is of independent interest beyond the specific e-voting application.
Ever since the appearance of quantum computers, prime factoring and discrete logarithm-based cryptography have been questioned, giving birth to the so-called post-quantum cryptography. The most prominent field in post-quantum cryptography is lattice-based cryptography, protocols that are proved to be as difficult to break as certain hard lattice problems like Learning with Errors (LWE) or Ring Learning with Errors (R-LWE). Furthermore, the application of cryptographic techniques to different areas, like electronic voting, has also nourished a great interest in distributed cryptography. In this work, we will give two original threshold protocols based in the lattice problem R-LWE: one for key generation and one for decryption. We will prove them both correct and secure under the assumption of hardness of some well-known lattice problems. Finally, we will give a rough implementation of the protocols in C to give some tentative results about their viability, in particular our model generates keys in the order of 103 ms and decrypts and encrypts in the order of 102 ms.
Cryptographic voting protocols have recently seen much interest from practitioners due to their (planned) use in countries such as Estonia, Switzerland, France, and Australia. Practical protocols usually rely on tested designs such as the mixing-and-decryption paradigm. There, multiple servers verifiably shuffle encrypted ballots, which are then decrypted in a distributed manner. While several efficient protocols implementing this paradigm exist from discrete log-type assumptions, the situation is less clear for post-quantum alternatives such as lattices. This is because the design ideas of the discrete log-based voting protocols do not carry over easily to the lattice setting, due to specific problems such as noise growth and approximate relations.