The end-to-end verifiable e-voting system Ordinos [26] is primarily characterized by its tally-hiding property, which ensures that only the actual election result, e. g., the winner of the election, is revealed while the full tally consisting of the aggregated votes stays hidden. Ordinos is an abstract model that guarantees tally-hiding, verifiability and vote privacy if the underlying cryptographic primitives satisfy certain requirements. It uses a multi-party-computation protocol over an additively homomorphic encryption scheme and guarantees active security with zero-knowledge proofs. Ordinos has already been instantiated for several election systems using the Paillier [35] encryption scheme, which can be broken by Shor’s algorithm [41]. The aim of this thesis is to instantiate Ordinos post-quantum secure using a variant of Regev’s LWE-based cryptosystem [39], which is adapted to realize an actively secure threshold encryption scheme over an arbitrary plaintext space. Then a noise analysis of the arithmetic and logical components used in the MPC-protocol of the Paillier instantiation is conducted, and the components are slightly adapted to restrict the noise growth. Additionally, valid zero-knowledge proofs are provided and a concrete instantiation achieving a security level of 128 bits is shown.
The end-to-end verifiable e-voting system Ordinos [26] is primarily characterized by its tally-hiding property, which ensures that only the actual election result, e. g., the winner of the election, is revealed while the full tally consisting of the aggregated votes stays hidden. Ordinos is an abstract model that guarantees tally-hiding, verifiability and vote privacy if the underlying cryptographic primitives satisfy certain requirements. It uses a multi-party-computation protocol over an additively homomorphic encryption scheme and guarantees active security with zero-knowledge proofs. Ordinos has already been instantiated for several election systems using the Paillier [35] encryption scheme, which can be broken by Shor’s algorithm [41]. The aim of this thesis is to instantiate Ordinos post-quantum secure using a variant of Regev’s LWE-based cryptosystem [39], which is adapted to realize an actively secure threshold encryption scheme over an arbitrary plaintext space. Then a noise analysis of the arithmetic and logical components used in the MPC-protocol of the Paillier instantiation is conducted, and the components are slightly adapted to restrict the noise growth. Additionally, valid zero-knowledge proofs are provided and a concrete instantiation achieving a security level of 128 bits is shown.
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.
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.
The advent of quantum computing poses a significant threat to the cryptographic foundations of current electronic voting (e-voting) systems, which commonly rely on algorithms such as Rivest-Shamir-Adleman (RSA) and Elliptic Curve Cryptography (ECC). These algorithms are believed to be vulnerable to attacks imposed by quantum computers, jeopardizing core e-voting properties, including ballot secrecy, integrity, and auditability. To address these challenges, this work presents a quantum-resistant electronic-voting (e-voting) system, named post-quantum e-voting system (PQEVS) built entirely upon cryptographic primitives standardized by the National Institute of Standards and Technology (NIST) for post-quantum security. The proposed PQEVS utilizes Dilithium for secure voter authentication, Brakerski/Fan-Vercauteren (BFV)-based Fully Homomorphic Encryption (FHE) for privacy-preserving vote tallying, and Picnic-based Zero-Knowledge Proofs (ZKPs) to ensure vote validity without compromising voter anonymity. Designed for modularity and scalability, our PQEVS delivers enhanced security while achieving significant performance gains, reducing vote processing latency by 85% and supporting throughputs of up to 36,000 votes per second. These results highlight the practicality and robustness of post-quantum cryptography in securing large-scale electoral processes, setting a new benchmark for verifiable and future-proof e-voting systems.
There is no quantum election protocol that can fulfil the eight requirements of an electronic election protocol, i.e., completeness, robustness, privacy, legality, unreusability, fairness, verifiability, and receipt-freeness. To address this issue, we employ the general construction of quantum digital signature and quantum public key encryption, in conjunction with classic public key encryption, to develop and instantiate a general construction of quantum election protocol. The proposed protocol exhibits the following advantages: (i) no pre-shared key between any two participants is required, and no trusted third party or anonymous channels are required. The protocol is suitable for large-scale elections with numerous candidates and voters and accommodates the situation in which multiple voters vote simultaneously. (ii) It is the first protocol that dismantles the contradiction between verifiability and receipt-freeness in a quantum election protocol. It satisfies all eight requirements stated earlier under the physical assumptions that there exists a one-way untappable channel from the administrator to the voter and that there is no collusion between any of the three parties in the protocol. Compared with current election protocols with verifiability and receipt-freeness, this protocol relies upon fewer physical assumptions. (iii) This construction is flexible and can be instantiated into an election scheme having post-quantum security by applying cryptographic algorithms conveying post-quantum security. Moreover, utilizing quantum digital signature and public key encryption yields a good result: the transmitted ballots are in quantum states, so owing to the no-cloning theorem, ballot privacy is less likely to be compromised, even if private keys of the signature and public key encryption are leaked after the election. However, in existing election protocols employing classic digital signatures and public key encryption, ballot privacy can be easily violated if attackers obtain private keys. Thus, our construction enhances privacy.
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.
Voting is a primary democratic activity through which voters select representatives or approve policies. Conventional paper ballot elections have several drawbacks that might compromise the fairness, effectiveness, and accessibility of the voting process. Therefore, there is an increasing need to design safer, effective, and easily accessible alternatives. E-Voting is one such solution that uses digital tools to simplify voting. Existing state-of-the-art designs for secure E-Voting are based on number-theoretic hardness assumptions. These designs are no longer secure due to quantum algorithms such as Shor's algorithm. We present the design and analysis of \textit{first} post-quantum secure end-to-end verifiable E-Voting protocol based on multivariate polynomials to address this issue. The security of our proposed design depends on the hardness of the MQ problem, which is an NP-hard problem. We present a simple yet efficient design involving only standard cryptographic primitives as building blocks.