Quantum-Safe Electronic Voting Schemes

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.