Can we cast a ballot as intended and be receipt free?

Can we cast a ballot as intended and be receipt free?

Speakers: Henri Devillez, Olivier Pereira, Thomas Peters, Quentin Yang

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=amWdp4-76Os

Overview

In the realm of electronic voting, ensuring both the integrity of a voter's choice and the secrecy of that choice is paramount. This talk, presented by Henri Devillez and co-authored with Olivier Pereira, Thomas Peters, and Quentin Yang, delves into the intricate relationship between two critical security properties: cast-as-intended (CAI) and receipt-freeness (RF). CAI guarantees that the vote a voter intended to cast is precisely what is recorded, while RF prevents voters from proving how they voted, thereby combating vote selling and coercion. The research explores the fundamental limits of achieving both properties simultaneously, particularly in different interaction models of voting systems.

The speakers highlight that these two notions are notoriously difficult to achieve in conjunction, often employing mechanisms that conflict rather than synergize. Their work extends the definition of receipt-freeness to accommodate highly interactive voting scenarios, a more realistic model for modern e-voting systems. A significant contribution of this research is the demonstration of an impossibility result: it is fundamentally impossible to achieve both CAI and RF in a non-interactive voting process. This critical finding motivates the exploration of interactive protocols, where the researchers then present three distinct protocols that successfully achieve both properties, either through interactive ballot submission or pre-voting interactions with a trusted registration service. This work provides crucial insights for the design of future secure and private electronic voting systems, guiding architects toward viable interaction models.

Background

▶ Watch: Introduction and overview of the voting model (0:00)

Electronic voting systems aim to replace traditional paper-based methods with digital processes, promising increased efficiency, accessibility, and potentially enhanced verifiability. However, this transition introduces complex security and privacy challenges. A typical generalized voting model involves a voter interacting with a voting device, which then communicates with a casting server. The server publishes the computed vote onto a public bulletin board. After all ballots are cast, tellers compute the election result from the bulletin board and publish it along with a proof of correct computation, which auditors can then verify.

Several security properties are highly desired in such systems. Verifiability properties include:

• Cast-as-intended (CAI): The ballot obtained by the voter truly reflects their intended vote.
• Recorded-as-cast (RAC): The recorded ballot on the bulletin board accurately reflects the ballot initially cast, without alteration.
• Tallied-as-recorded (TAR): The final election result is correctly computed from all recorded ballots.

Beyond verifiability, voter privacy is crucial, aiming to ensure that no one learns anything about a voter's choices beyond what is discernible from the aggregate election results. A stronger privacy notion is receipt-freeness (RF), which dictates that a voter should be unable to produce any proof or "receipt" of how they voted to a third party. This property is vital for preventing vote buying, coercion, and undue influence, as it removes the incentive for an adversary to demand proof of a specific vote.

The core challenge addressed in this research lies in the inherent tension between CAI and RF. CAI often requires mechanisms that allow voters to verify their vote, potentially creating a receipt. Conversely, RF mechanisms typically obscure the link between a voter's actions and their recorded vote, making direct verification difficult. Prior work on receipt-freeness largely focused on non-interactive scenarios, where a voter sends a single message to a casting server. However, real-world e-voting protocols often involve multiple interactions between the voter, voting device, and server. This talk extends the theoretical understanding of RF to these more complex interactive settings, providing a foundation for evaluating and designing practical e-voting systems.

Key Findings

▶ Watch: Focus on 'cast as intended' and 'receipt-freeness' (2:30)

The research yielded several fundamental insights into the feasibility of simultaneously achieving cast-as-intended and receipt-freeness in electronic voting protocols.

First, the speakers introduced a significantly extended definition of receipt-freeness tailored for highly interactive voting scenarios. Unlike previous definitions that focused on single-message submissions, this new model accommodates multiple rounds of communication between the voter's device and the casting server. This extension is crucial for analyzing modern, complex e-voting protocols that rely on interactive cryptographic primitives.

Second, and perhaps the most impactful finding, is an impossibility result: it is impossible to achieve both cast-as-intended and receipt-freeness if the vote submission process is entirely non-interactive. This means that any protocol where a voter's device simply sends a single, unalterable message to the server without further communication cannot simultaneously guarantee that the voter's true intent is captured and that they cannot prove their vote. This result underscores the inherent trade-offs in e-voting design and highlights the necessity of interaction for robust security.

Finally, despite the impossibility in non-interactive settings, the research offers a positive outlook by demonstrating that CAI and RF can be achieved together if interaction is introduced somewhere in the process. The speakers presented three distinct protocol architectures that realize both properties. These protocols illustrate different approaches to interaction:

1. Multi-round interactive submission: The voting device and casting server engage in multiple rounds of communication during the ballot casting process.
2. Constant-round interactive submission: A specific, limited number of interactions (e.g., three rounds) during the voting process.
3. Single-pass submission with pre-voting interaction: The ballot submission itself is non-interactive, but voters must interact with a trusted registration service before the actual voting begins.

These possibility results provide concrete pathways for designing secure and private electronic voting systems, guiding developers away from models proven to be fundamentally insecure with respect to these crucial properties.

Technical Deep Dive

▶ Watch: Defining receipt-freeness in the non-interactive case (4:00)

The technical core of this work revolves around formalizing receipt-freeness in interactive settings and then rigorously proving the impossibility and possibility results.

To extend receipt-freeness (RF) to the interactive case, the authors model an adversary's instructions to a voter not as a single ballot message, but as a Turing machine. This Turing machine takes the current state and the last received message as input, and outputs the next message to be sent to the casting server. Crucially, this instruction machine also outputs a transcript of the interaction, which the adversary receives. This comprehensive model captures scenarios where an adversary might confiscate the voter's device or dictate a complex, adaptive strategy. The definition of RF then requires that two scenarios are indistinguishable from the adversary's perspective:

1. The voter follows the adversary's instructions (the Turing machine strategy).
2. The voter attempts to deviate using a deceive algorithm to cast their own intended vote, while still appearing to follow the adversary's instructions.

The deceiving correctness property ensures that this deceive algorithm actually produces a ballot reflecting the voter's true intent.

The impossibility result for non-interactive submission achieving both CAI and RF is a cornerstone of this research. The intuition relies on a clever reduction. Assume, for contradiction, that a non-interactive protocol is receipt-free. The proof then constructs a scenario involving a malicious voting device that attempts to alter the voter's choice. In a CAI game, a human voter interacts with either a true voting device or a malicious one. If the protocol is RF, the human voter (acting as a distinguisher) cannot differentiate between a legitimate device and a malicious device running the deceive algorithm. If the deceive algorithm is also correct (i.e., it successfully casts the intended vote despite the adversary's instructions), then a voter attempting to cast vote V via a malicious device running the deceive algorithm for V\ would still perceive their vote as V (due to CAI) while the system records V\ (due to RF's indistinguishability). This creates a contradiction.

Formally, the proof constructs three adversaries—one for the CAI game, one for the RF game, and one for the deceiving correctness game. By running these adversaries in parallel and showing that the resulting bulletin board distributions are identical across scenarios, and that the sum of their advantages is at least 1, the authors demonstrate that at least one adversary must win with non-negligible probability, thus proving the impossibility.

Following the impossibility result, the paper presents three constructive possibility protocols, each leveraging interaction differently.

1. Multi-round Human-Compatible Protocol: This protocol uses simple cryptographic primitives like CPA encryption schemes, commitment schemes, and zero-knowledge divertible proofs. It involves multiple interactions between the voting device and the casting server. Its "human-compatible" aspect means that the human voter only needs to perform simple tasks, such as flipping switches or comparing short strings displayed on the voting device with values on the bulletin board. This minimizes voter burden while maintaining security.
2. Constant-Round Protocol (3 rounds): This protocol, which the speaker detailed in the presentation, also uses simple crypto primitives (CPA encryption, commitment schemes, zero-knowledge divertible proofs) but requires slightly more active participation from the voter. The core idea is based on secret sharing and randomization:

• Round 1: To cast a vote V, the voter computes two shares, v0 and v1, such that V = v0 + v1. These shares are then encrypted into ciphertexts b0 and b1 and sent to the casting server. The casting server then randomizes these ciphertexts by multiplying them with an encryption of zero (e.g., b0' = b0 Enc(0), b1' = b1 Enc(0)) and publishes b0' and b1' on the bulletin board. This randomization is key for RF, as the voter does not know the randomness used, preventing them from producing a receipt for the published ciphertexts.
• Round 2: The human voter computes private random values, Alpha and Beta, and sends a commitment of these values to the casting server. The server then returns values that will be published later, essentially committing to the final state.
• Round 3: The voter reveals Alpha and Beta to the voting device. The device, in cooperation with the casting server, computes an opening of the values b0 raised to the power of Alpha multiplied by b1 raised to the power of Beta (i.e., b0^Alpha b1^Beta). This result is published. Simultaneously, divertible zero-knowledge proofs are used to demonstrate that b0 b1 (reconstructed from b0' and b1') is indeed a valid encryption of a valid vote.
• CAI in this protocol: A malicious voting device attempting to cheat must modify v0 or v1 before knowing Alpha and Beta. The voter, at the end, expects a specific output for v0^Alpha v1^Beta. If the device altered v0 or v1, the probability that the modified v0^Alpha v1^Beta matches the voter's expectation is negligible, thus detecting the cheat.
• RF in this protocol: Beyond the initial randomization of ciphertexts, the voting device can extract Alpha and Beta from an adversary's instructions (by simulating the instructions). It can then solve a linear system to find shares v0 and v1 that, when combined with Alpha and Beta, produce what the adversary expects, thus making the "deceive" scenario indistinguishable.

1. Single-Pass Submission with Pre-Voting Interaction: This protocol allows for a non-interactive ballot submission phase, but it necessitates interactions with a registration service before the actual voting protocol begins. This approach utilizes more advanced cryptographic primitives, specifically Trapdoor NIZK (Non-Interactive Zero-Knowledge) proof systems and malleable NIZK proofs. These complex primitives allow for the creation of proofs that can be manipulated in specific ways without revealing secrets, which is essential for achieving both CAI and RF in this model.

Demo / Proof of Concept

▶ Watch: Extending receipt-freeness to interactive protocols (5:30)

The conference talk focused on theoretical results, formal definitions, and protocol designs rather than a live demonstration. No specific demo or proof-of-concept implementation was described or shown during the presentation.

Defensive Implications

▶ Watch: Intuition behind the impossibility proof (7:50)

The findings presented in this research have profound implications for the design and implementation of secure electronic voting systems.

1. Interaction is Non-Negotiable for Robustness: The impossibility result for non-interactive protocols unequivocally demonstrates that for any e-voting system aiming to achieve both cast-as-intended (CAI) and receipt-freeness (RF), some form of interaction is fundamentally necessary. Designers must move away from simplistic, single-message submission models if these properties are critical.
2. Strategic Placement of Interaction: The possibility results highlight different ways interaction can be introduced. Systems can either integrate multi-round interactions directly into the ballot submission process or rely on pre-voting interactions with trusted authorities, allowing for a single-pass ballot submission. The choice depends on the desired trade-offs between protocol complexity, cryptographic overhead, and voter experience.
3. Voter Engagement as a Security Feature: The "human-compatible" multi-round protocol suggests that carefully designed voter interactions, even simple ones like comparing strings, can contribute significantly to the CAI property. This underscores the importance of user experience in security design, empowering voters to verify their actions without requiring deep cryptographic understanding.
4. Cryptographic Primitive Requirements: Achieving CAI and RF necessitates the use of specific, often advanced, cryptographic primitives. Designers should be prepared to integrate robust CPA encryption schemes, commitment schemes, and especially zero-knowledge divertible proofs. For protocols relying on pre-voting interactions, even more involved primitives like Trapdoor NIZK and malleable NIZK proof systems are required. The selection of these primitives must be done carefully, considering their security assumptions, performance characteristics, and implementation complexity.
5. Addressing the Trade-off Landscape: The research implicitly defines a landscape of trade-offs:

• Simpler crypto often implies more interaction rounds during voting (e.g., the multi-round protocol).
• Fewer interaction rounds during voting (e.g., the constant-round protocol) might require slightly more active voter participation.
• Non-interactive submission requires complex crypto and pre-voting interaction with trusted parties.

Defenders must evaluate their specific threat models, performance requirements, and usability goals to select the most appropriate protocol architecture.

1. Focus on Future Research: The speakers noted that this work opens avenues for designing more practical, usable, and efficient protocols that still achieve CAI and RF. Defenders should stay abreast of ongoing research in this area to leverage new advancements that might offer better balances of security, performance, and usability.

Key Takeaways

• Cast-as-intended (CAI) and receipt-freeness (RF) are two fundamental, yet often conflicting, security properties crucial for electronic voting systems.
• It is impossible to achieve both CAI and RF simultaneously in a purely non-interactive vote submission process. This is a critical impossibility result for e-voting designers.
• Achieving both CAI and RF is possible if interaction is introduced, either during the ballot submission process itself or through pre-voting interactions with a trusted registration service.
• Three distinct protocol architectures were presented, demonstrating different approaches to integrating interaction and cryptographic primitives (from simple CPA encryption and commitments to advanced Trapdoor NIZK proofs).
• The choice of protocol architecture involves trade-offs between cryptographic complexity, the number of interaction rounds, and the burden placed on the voter.

About the Speaker(s)

The talk was presented by Henri Devillez, who is credited as the primary speaker for this research. His co-authors include Olivier Pereira, Thomas Peters, and Quentin Yang. While specific affiliations were not detailed in the transcript, the collaborative nature of their work highlights expertise in the field of cryptographic security and electronic voting systems, presented at a prestigious conference like IEEE S&P.