Quantum-Safe Electronic Voting Schemes

Abstract

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.