INNOVATE

Coercion-Resistant Cast-as-Intended Verifiability in Electronic Voting Systems

Industrial PhD Thesis

When we hear about electronic voting, e-voting, we typically imagine a computer or another device somehow transmitting our vote directly to the election authorities and maybe helping them to speed up the result tabulation. A main benefit, of course, is convenience — voting from any place and at any time, faster result aggregation, and, perhaps, even the possibility to change one’s mind or vote far away from prying eyes. One can think of e-voting as a tool with its strengths and challenges.

There are many decisions that an e-voting scheme must make: whether to allow re-voting (the casting of multiple ballots with each subsequent ballot nullifying the previous ballot) or to keep similar restrictions as for a postal voting channel (one voter, one vote); if users should be able to verify ballot correctness or if the threat to privacy is too great; how to define what receipt-freeness means; etc. In many cases, choosing would imply consequences or tradeoffs. For example, a voting system that relies on anonymous vote-casting must prohibit multiple voting via different voting channels, as no vote can be traced to the voter’s identity and overridden later.

One particularly interesting tradeoff is ensuring a voter cannot sell the vote willingly or under duress while at the same time preventing a malicious voting device from cheating. At first glance, the task seems easy: We need coercion resistance to limit (in)voluntary vote-selling and cast-as-intended verification to stop the voting device from cheating. However, those properties are contradictory.

Informally, the coercion-resistance property ensures that a voter cannot prove to the coercer their vote’s content, which prevents vote selling and voting under duress. The cast-as-intended property states that a malicious voting device cannot cheat the voter and send different choices from what the voter intended. One property requires outputting no information about the selection, and the other demands proof — an extra piece of data.

A curious observation is that the voting device is malicious but not necessarily evil enough to collaborate with the coercer. Hence, we are in a situation where, for coercion-resistance, we need to rely on a voting device that might have another agenda and attempt to modify our choice. Such an unusual situation, naturally, raises questions:

• Can we simultaneously achieve cast-as-intended and coercion-resistance? And if so, how?
• Will the answer be different for the post-quantum world?
• Are there any limits or conditions under which we cannot have both?

A recently finalized Ph.D. thesis: “Coercion-resistant cast-as-intended verifiability in electronic voting systems.” — aims to look at all these questions to find out how we can provide coercion-resistant cast-as-intended verification. The thesis contributions can be roughly divided into three parts: (1) study in the standard settings, (2) exploration of post-quantum cryptography, and (3) practical constructions and search for the limitations of both properties.

In the first part, we give an extensive overview of the current state of the art in electronic voting literature regarding those properties. Then, we put forward two formal definitions for achieving coercion-resistant cast-as-intended verification in settings without pre-exchanged data. After that, we present two practical constructions and prove their security under the proposed definitions. We also show the efficiency of our proposal by providing proof of the concept implementation.

In the second part, we switch to post-quantum settings and identify the usability issues rooted in the lattice-based math affecting both proposed solutions. To address those issues, we present a generic transformation that departs from an interactive zero-knowledge system (that might require multiple re-runs to complete the protocol) and obtains a 3-move zero-knowledge system (without re-runs). The transformation combines the well-known Fiat-Shamir technique with several initially exchanged messages. The resulting 3-move system enjoys honest-verifier zero-knowledge and can be easily turned into a fully deniable proof using standard techniques.

In the final part, we focus on the practical aspects of the coercion-resistant cast-as-intended verification. First, we present the case of a computationally limited voter, which we consider the most realistic one. We show that even a computationally limited voter can enjoy coercion-resistant cast-as-intended verification, but a help of a simple aid device for nonce generation is required. Also, we demonstrate that our generic definition easily adapts to the constraints of the limited voter. After that, we present ongoing work that focuses on the cases of extreme coercion based on new and unexplored mechanisms such as delay encryption and blockchain. We show an advanced coercive attack on our first construction and describe an improvement to the second solution that reduces the number of interactions to an optimal three rounds.

To summarize, we start by studying coercion-resistant cast-as-intended verification in standard settings, which results in formal definitions and two practical solutions. Then we move into the post-quantum world, where we learn that an extra step is needed to preserve the usability of our previously proposed constructions, which results in the generic transformation to avoid protocol re-runs. After that, we concentrate on a computationally limited voter, which leads to another simple solution and shows the adaptability of our original definitions. Finally, we explore the extreme coercion threats to see the limits of coercion-resistant cast-as-intended verification, which resulted in a new coercion attack on the first construction and an upgrade of the second solution.

This articles was written by Tamara Finogina (PhD), Cryptography Researcher at Scytl.