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.
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.
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.
L'estudi de propietats de sistemes quantics formats per moltes particules es inherentment una tasca dificil. De fet, la solucio de problemes classics similars ja es un problema desafiant, encara mes complicat per la naturalesa quantica de les interaccions. Els recursos necessaris per l'estudi d'estats quantics en un espai de Hilbert creix exponencialment amb el nombre de particules. Resultats analitics son restringits a situacions particulars, i els resultats numerics son possibles nomes pera a poques particules. La teoria de la informacio quantica (QIT) proporciona una nova perspectiva per estudiar i explicar conceptes fonamentals de mecanica quantica, aprofitant aquest fenomens per dissenyar noves tecniques pel processat i manipulacio de la informacio. El desenvolupament de la QIT te una connexio directa amb els recents avencos experimental principalment en la interaccio de llum i la materia. Tot i tractar-se d'un camp relativament jove, aquest resultat teorics i experimental ja s'han traduit en aplicacions tecnologiques. La tesi s'ubica enmig de totes aquestes disciplines, actualment un camp de recerca molt fertil. Es centra en l'estudi de hamiltonians locals des de la perspectiva de la QIT, amb resultats en materia condensada. Es centra en metodes numerics per l'estudi de sistemes quantics formats per moltes particules, mostrant com resultats de QIT poden ser emprats en l'estudi de sistemes complexos. Es tracta d'un treball principalment numeric, amb resultats teorics pera a alguns casos particulars. Tot i aixo identifiquem propietats fonamentals dels sistemes quantics que apareixen indistintament en sistemes formats per especies completament diferents, fermions i bosons. Hem explorat les propietats fisiques dels estats termics de sistemes de moltes particules corresponents a situacions amb soroll termic. Estats termics son tipicament presents e escenaris experimentals, pero el seu estudi en llenguatge de la QIT es veu limitat per la dificultat de caracteritzar l' entanglement en estats mescla. Hem presentat un metode constructiu per mostrar la presencia de correlacions quantiques al sistema. A baixes temperatures, la fisica dels sistemes de moltes particules es dominada per les propietats de l'estat fonamental. Els hamiltonians locals poden ser simulats eficientment amb mitjans classics gracies a les propietats de l' entanglement de l'estat fonamental. Mostrem en aquesta tesi com la distancia d'interaccio juga un paper menor en aquest escenari, permetent una simulacio eficient en escenaris mes connectats que l'estandard regim d'interaccio al primers veins. La generalitat d'alguns dels resultats de la tesi permet una extensio directa. La nostra recerca actual es centra en la continuacio d'aquests resultats. Per una banda, la termodinamica quantica es un camp tan ampli que pot ser estes a multiples escenaris, en concret les geometries 2D permeten un millor estudi de la relacio entre lleis d'area i correlacions. Per altra banda, els metodes SDP desenvolupats en la tesi es poden adaptar a diferents problemes quantics, gracies a la seva generalitat basada en l' anticommutacio d'operadors.
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.
La darrera dècada ha estat testimoni d'una revolució tecnològica sense precedents, però els seus fruits encara trigaran a arribar al gran públic.Em refereixo al desenvolupament dels primers prototips d'ordinadors quàntics, la majoria dels quals han estat construïts per empreses privades nordamericanes, amb algunes poques excepcions a la Xina i Europa.Aquest nou tipus d'ordinador fa els càlculs utilitzant les lleis de la mecànica quàntica, és a dir, la teoria física que descriu el comportament de les partícules microscòpiques, com àtoms i molècules, que formen tota la matèria.Per aquest motiu es pensa que els ordinadors quàntics seran molt més potents que els clàssics i podran realitzar en una fracció de segon tasques que per a un ordinador normal requeririen milions d'anys.No obstant això, els ordinadors quàntics disponibles actualment són molt fràgils i de mida petita, per la qual cosa encara no han assolit tot el seu potencial.A Europa, hi ha poques empreses que hagin construït o que es trobin en condicions de construir ordinadors quàntics, i encara menys les universitats o institucions públiques que estan immerses en aquesta cursa.A Catalunya, s'ha anunciat recentment que el Centre de Supercomputació de Barcelona (BSC, segons les sigles en anglès) disposarà del primer ordinador quàntic del sud d'Europa.Això podria situar el nostre país a l'avantguarda de la recerca en aquest àmbit.En els darrers anys, la computació quàntica ha suscitat un gran interès tant per part del sector públic (universitats i institucions estatals de recerca) com del sector privat, i ha generat tot un ecosistema en què gegants tecnològics com Google o Amazon conviuen amb empreses de petit format o fins i tot start-ups que desenvolupen algoritmes i maquinari.Darrere d'aquest boom de la computació quàntica hi ha les grans expectatives que la societat ha posat en aquesta nova tecnologia.Per exemple, hi ha algoritmes que, si s'implementessin en un ordinador quàntic, permetrien descompondre nombres en nombres primers (vegeu la nota 1) en molt menys temps del que necessita un ordinador normal, inclosos els superordinadors més potents.Això pot semblar abstracte, però els sistemes de criptografia que utilitzen els bancs per protegir les transaccions entre comptes corrents es basen en la generació de nombres aleatoris molt grans per després descompondre'ls en factors primers.Un ordinador quàntic podria desxifrar ràpidament aquestes claus i finestra a l'actualitat
Electronic voting (e-voting) has emerged as a transformative technology in the modern digital era. Many countries across the world are using e-voting systems in different types of elections, from political to non-political. One of the primary goals of e-voting is ensuring both verifiability and privacy simultaneously, which we refer to as security. Verifiability is a security feature that guarantees voters can confirm their vote is reflected in the final election result, while privacy guarantees that no one is able to link a vote to the voter who cast it. Verifiability needs to hold only for the duration of the election, whereas privacy needs to extend beyond the election period, even decades after the election. This property, known as everlasting privacy in the literature, ensures that even computationally unbounded adversaries cannot compromise voter privacy, securing elections against future advances in computing, including quantum computing. Researchers have proposed a wide variety of protocols to achieve this ambitious goal in secure e-voting, however, these protocols differ significantly, making the analysis and state-of-the-art complicated. In this thesis, we first address this fragmentation by systematically analyzing all existing e-voting protocols designed to ensure everlasting privacy. We map out the relationships and dependencies among these protocols, evaluate their security and efficiency under realistic assumptions, and identify unresolved challenges in the field. Our work provides a foundational reference for researchers aiming to design secure e-voting systems with everlasting privacy, paving the way for privacypreserving elections in the post-quantum era. Building on these insights, we propose a novel e-voting system that integrates the best practices from prior research while addressing their limitations. Leveraging the Hyperion scheme as a foundation, we develop an enhanced protocol that not only guarantees everlasting privacy but also introduces everlasting receipt-freeness and coercion mitigation. Unlike existing systems like Selene and Hyperion, which rely on computational assumptions for privacy, our protocol offers privacy even against adversaries with unlimited computational power. In secure electronic voting systems with everlasting privacy, the focus is on futureproofing privacy, while sometimes election verifiability relies on the computational soundness of zero-knowledge proofs (ZKP), which are vulnerable to quantum adversaries. Therefore, a key technical challenge is designing e-voting systems with efficient post-quantum cryptographic primitives to secure both privacy and verifiability against quantum attacks. In this thesis, we advance the state of post-quantum ZKPs by focusing on the ZKPs proposed by Jain et al., which are based on the conservative Learning Parity with Noise (LPN) assumption. We optimize the efficiency of these ZKPs, achieve formal security verification using EasyCrypt, and uncover flaws in existing implementations, demonstrating their vulnerability to malicious provers. Additionally, we construct the first code-based ZKP of shuffle, enabling a verifiable and privacy-preserving e-voting protocol with mixing-based tallying. Our e-voting system ensures both verifiability and vote privacy through the computational difficulty of decoding random linear codes, marking it as the first verifiable code-based e-voting system.
El meu doctorat esta dedicat a analitzar transicions de fases quantiques de naturalesa exotica en sistemes fortament correlacionats descrits per Hamiltonians de spin. D'una banda, m'he centrat en l'estudi de transicions de fase quantiques localitzades a prop de punts multicr itics. Aquests punts son particularment patologics ja que diverses fases quantiques coexisteixen en una petita regio de parametres del Hamiltonia. Aquest fet, tal i com argumentare al llarg de la tesis, condiciona palesament les propietats mostrades pel sistema fortament correlacionat. De l'altre, tambe he investigat transicions de fase quantiques cap a liquids de spin quantics que son fases exotiques de la materia que apareixen en alguns sistemes frustrats. Aquestes fases es situen a l'avantguarda de la recerca en materia condensada ja que son, teorica i experimentalment, molt dificils de caracteritzar. La recerca presentada es pot dividir en tres parts. La primera part tracta sobre comportaments insolits que pateix l'entrellacament quantic, mes conegut com a entanglement, en algunes cadenes de spin. La rellevancia de les fluctuacions quantiques creix en baixes dimensions i per tant els sistemes unidimensionals ofereixen un bon ventall de possibilitats per analitzar el paper de les fluctuacions quantiques en transicions de fase quantiques. Alguns calculs han estat realitzats en models de spin-1/2 i d'altres en sistemes de spin-1. La segona part de la meva tesis tracta de sistemes quantics frustrats i, particularment, de la presencia de liquids de spin. La frustracio reflecteix la impossibilitat de satisfer simultaniament totes les restriccions imposades per alguns Hamiltonians. Es una propietat intrinseca d'alguns sistemes fortament correlacionats, com ara els gels classic de spins o models quantics antiferromagnetics en 2D. Aquesta incompatibilitat fa que sovint sigui molt dificil minimitzar-ne l'energia per a trobar l'estat fonamental. Molts sistemes frustrats s'ordenen a baixes, o inclus zero, temperatures pero tambe hi ha estats que no s'ordenen i que queden fora de la teoria de les transicions de fase de Landau, presentant aixi una estructura subjacent extraordinaria. Els liquids de spin pertanyen a aquest segon tipus. El meu enfocament per a estudiar-los ha consistit en desenvolupar un nou metode numeric fent servir unes condicions de contorn degudament dissenyades. Aixo m'ha permes detectar-ne inequivocament algunes de les empremtes caracteristiques de la seva naturalesa. L'ultima part de la meva recerca l'he dedicada a descriure i analitzar models frustrats de spin quantics mitjancant una tecnica anomenada modified spin wave theory. L'us d'aquesta tecnica analitica m'ha permes contrastar l'aplicacio i validesa de l'enfocament numeric que he desenvolupat i tambe m'ha permes aprofundir en l'estudi dels liquids de spin. Finalment, voldria mencionar que la primera i tercera part de la meva tesis va ser principalment duta a terme durant els mesos que vaig passar com a investigador predoctoral visitant a la Queen's University of Belfast (Regne Unit) en el grup del Dr. G. de Chiara al 2016 i a la Universitat Heidelberg (Alemanya) en el grup del Junior Prof. P. Hauke l'any 2018 respectivament.