Epoque: Practical End-to-End Verifiable Post-Quantum-Secure E-Voting

To date, the security of all practical end-to-end veri-

fiable e-voting protocols relies on “traditional” hardness

assumptions, such as factoring integers or computing discrete logarithms. With more and more powerful quantum

computers on the horizon (see, e.g., [5]), these voting

protocols may be rendered completely insecure. This

threat motivates the design of end-to-end verifiable evoting protocols that are secure against quantum attacks.

Unfortunately, it turned out to be very challenging to

pursue this objective, and, in fact, it had not been met

prior to our work.

The reason behind this state of affairs is that na¨ıvely

replacing the “classical” cryptographic primitives of an

arbitrary end-to-end verifiable e-voting protocol (e.g., Helios [2]) with known post-quantum primitives can destroy

practicality. Despite the fact that post-quantum-secure

cryptography has become more efficient and versatile

in the past decade or so, there exist only the following two practical post-quantum-secure e-voting protocols

in the literature. Boyen, Haines, and Muller [ ¨ 13] proposed and implemented a completely lattice-based veri-

fiable decryption mix net which can be used for verifi-

able post-quantum-secure e-voting but the class of elections it should be used for is limited (see Sec. 8). Del

Pino, Lyubashevsky, Neven, and Seiler [30] instantiated

the homomorphic e-voting protocol by Cramer, Franklin,

Schoenmakers, and Yung [25] with practical lattice-based

cryptographic primitives. However, unlike Boyen et al.’s

mix net [13], the homomorphic e-voting protocol by Del

Pino et al. [30] is not (end-to-end) verifiable: we will

elaborate in Sec. 2 that all tallying authorities and all

voters’ voting devices in [30] need to be honest in order

to (be able to) verify that the final election result is in fact

correct. As we will see, it has long been far from obvious

how to eliminate these undesirable trust assumptions in

the lattice-based setting without undermining practicality.

Altogether, there does not exist a homomorphic evoting protocol in the literature that can be used in a

real practical election to both protect the privacy of votes

and provide end-to-end verifiability in the presence of

quantum attackers.1