Thwarting Last-Minute Voter Coercion

Thwarting Last-Minute Voter Coercion

Speakers: Rosario Giustolisi, Maryam Sheikhi, Carsten Schuermann

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=FbJ9HtOpkxc

Overview

This talk, presented by Rosario Giustolisi, Maryam Sheikhi, and Carsten Schuermann at IEEE S&P, introduces a novel technique designed to enhance the security and integrity of internet-based voting systems by providing robust last-minute voter coercion resistance. Internet voting, while offering unparalleled convenience by allowing ballots to be cast from personal devices, inherently introduces complex challenges related to vote privacy, verifiability, and crucially, resistance to coercion. The presentation meticulously details a new approach that addresses a significant gap in existing cryptographic voting schemes, specifically the vulnerability to coercion attempts that occur immediately before or during the act of voting.

The core of their work lies in a sophisticated blend of two established coercion-resistance paradigms: fake credentials and deniable revoting. By introducing dynamic credentials and strategically deploying noise ballots generated by the voting server, the proposed system empowers voters to cast their true votes even under duress, without the need for a trusted registration authority or an assumed "free" registration phase. This innovation not only strengthens the fundamental security properties of internet voting but also offers an efficient tallying mechanism, making it a significant contribution to the field of secure electronic elections. The research underscores the critical importance of ensuring that the convenience of remote voting does not come at the cost of a voter's autonomy and the integrity of the electoral process.

Background

▶ Watch: Introduction to internet voting challenges and coercion (0:00)

Internet-based voting systems are envisioned as a modern solution to increase voter participation and convenience, eliminating the logistical hurdles of physical polling stations. However, the digital nature of these systems introduces a unique set of security challenges that, if not adequately addressed, can undermine public trust and the democratic process itself. Central among these challenges are vote privacy, ensuring no one knows how an individual voted; verifiability, allowing for independent confirmation that votes are counted correctly; and coercion resistance, a stringent property demanding that a voter's true preference remains unknown, even if they are observed or pressured while casting their ballot. A related concept, receipt-freeness, prevents voters from being able to prove how they voted, thereby mitigating vote buying.

Existing cryptographic voting schemes primarily tackle coercion resistance through two main approaches:

1. Fake Credentials: This method typically relies on a trusted registration authority (RA) that issues voting credentials to legitimate voters. During registration, voters can generate and provide fake credentials to potential coercers, allowing them to appear to comply without revealing their true vote. While effective against certain forms of coercion, this approach carries several assumptions. It necessitates a trusted RA, assumes voters are not coerced during registration, and often requires a secure, trusted device to store and protect cryptographic keys associated with credentials. These assumptions can be difficult to guarantee in real-world scenarios, particularly when a coercer's influence extends to the registration phase.

1. Deniable Revoting: In this paradigm, voters are allowed to cast multiple ballots during the voting phase, with each subsequent ballot canceling or superseding any previously cast ones. The idea is that a voter, under coercion, can cast a "coerced" ballot and then, once free from observation, cast a new, true ballot that invalidates the coerced one. While this provides a form of coercion resistance, its primary limitation, as highlighted by the speakers, is its inability to guarantee last-minute coercion resistance. If a voter is coerced immediately before the voting period ends, or if they are observed continuously, they may not have the opportunity to cast a "deniable" revote, leaving their coerced vote as the final, counted ballot.

The fundamental problem addressed by Giustolisi, Sheikhi, and Schuermann is this specific vulnerability within deniable revoting schemes. The lack of robust protection against last-minute coercion attempts leaves a critical gap in the security of internet voting, potentially allowing malicious actors to influence election outcomes by targeting voters during the most critical period of the election. This research endeavors to bridge this gap, enhancing the utility and security of deniable revoting to encompass even the most time-sensitive coercion scenarios.

Key Findings

▶ Watch: Presenting new technique: dynamic credentials and noise ballots (2:00)

The central contribution of this research is a novel technique that integrates the strengths of fake credentials and deniable revoting to achieve last-minute coercion resistance in internet voting, a property previously elusive for deniable revoting schemes. The key findings and innovations presented are:

1. Dynamic Credentials for Last-Minute Coercion Resistance: The talk introduces the concept of dynamic credentials, where a voter's credentials are not static but change based on their behavior during the voting phase. This dynamic nature allows the system to provide deniable vote updating, even under last-minute coercion, by enabling the voter to effectively "signal" their true intent to the voting server, even if they appear to comply with a coercer.

1. Elimination of Trusted Authority Assumptions: A significant advantage of the proposed method is that it does not require a trusted registration authority and removes the assumption of a "free" or uncoerced registration phase. Unlike traditional fake credential schemes, the dynamic credential approach means the system's security doesn't hinge on a single, vulnerable point of trust or an ideal registration environment. Voters can even be coerced during registration and reveal the content of their registration ballot without compromising their final vote.

1. Introduction of Noise Ballots for Obfuscation: To further obscure a voter's true casting behavior and enhance deniability, the system incorporates noise ballots. These are periodically cast by the voting server and are cryptographically indistinguishable from legitimate voter ballots. This constant stream of server-generated ballots dilutes the signal of a voter's actual actions, making it exceedingly difficult for a coercer to discern whether a voter has complied or resisted.

1. Efficient Tallying: The proposed technique allows for a highly efficient tallying process. Instead of requiring a separate "filtering phase" to remove noise ballots, the system is designed such that only the last noise ballot in a voter's Cast Ballot Record (CBR) needs to be considered for tallying. This design choice results in a tallying complexity that is linear to the number of voters, not the total number of ballots (including noise ballots), making it scalable for large-scale elections. For instance, the prototype demonstrated tallying 1 million voters in less than a minute on a standard laptop.

1. Quantitative Measure of Coercion Resistance: The researchers provide a quantitative analysis of the system's coercion resistance against brute-force attacks. They demonstrate that the number of attempts a coercer would need to guess the correct sequence of voter-cast ballots (the "list of indexes") grows exponentially with the number of ballots in the CBR, specifically related to Fibonacci numbers. This exponential growth makes a brute-force attack computationally infeasible, especially as the voting phase progresses and more ballots (both real and noise) are added. The voting server can also detect and block suspicious patterns of incorrect attempts.

These findings represent a significant advancement in secure internet voting, offering a practical and robust solution to a long-standing challenge in the field.

Technical Deep Dive

▶ Watch: Example: How noise ballots thwart last-minute coercion (4:50)

The proposed technique fundamentally redefines how coercion resistance is achieved in deniable revoting schemes by introducing dynamic credentials and noise ballots. At its core, the system revolves around a Cast Ballot Record (CBR) for each voter, which is a publicly available, ordered list of all ballots associated with that voter on a bulletin board.

1. CBR Initialization and Population:

• Each voter's CBR is initialized during registration with a registration ballot containing their public credentials. Crucially, the voter can reveal the content of this registration ballot to a coercer without compromising their vote, as the system's dynamic nature accounts for this.
• Throughout the voting phase, the CBR is continuously populated. Ballots can be generated either by the voter themselves or by the voting server.

1. Noise Ballots and Indistinguishability:

• The voting server periodically casts noise ballots into the CBR. These noise ballots are cryptographically indistinguishable from actual voter ballots.
• Their purpose is twofold: to obfuscate the voter's casting behavior, making it harder for a coercer to pinpoint when a "real" vote was cast, and to provide deniable voter plots, allowing the voter to claim any ballot as their own.
• Each ballot, whether voter-generated or server-generated, is essentially an ElGamal encryption. A key concept is the O-Mallot, which is described as a randomization of this ElGamal encryption, ensuring that ballots can be updated or cancelled without revealing their content.

1. The List of Indexes and Voter-Server Signaling:

• The core innovation lies in a shared secret maintained by the voter and the voting server: a list of indexes. This list tracks which ballots within the voter's CBR were genuinely cast by the voter (i.e., not noise ballots or coerced ballots that were later "cancelled").
• When a voter casts a ballot, this ballot includes an encryption of their current understanding of this list of indexes.
• Uncoerced Voting: If a voter is not coerced, they submit a ballot with the correct list of indexes. The voting server verifies this and, in response, randomizes the last ballot in the CBR (effectively updating it to reflect the new vote).
• Coerced Voting: If a voter is coerced, they provide an incorrect list of indexes (e.g., an empty list, or a list that doesn't reflect their true voting history). Upon detecting this mismatch, the voting server adds a new noise ballot that specifically cancels the coerced ballot by randomizing the second-to-last ballot in the CBR (which would be the coerced vote). This mechanism allows the voter to appear to comply with the coercer while their true vote remains protected.
• Revoting and Null Ballots: The system supports traditional deniable revoting. A voter can cancel a previously cast ballot (coerced or uncoerced) by submitting a new ballot that encrypts the index of the ballot they wish to cancel. This prompts the server to randomize the last ballot. Furthermore, voters can cast a null ballot by providing a list of indexes referring to previous voter-cast ballots, effectively abstaining or invalidating prior choices.

1. Encoding the List of Indexes:

• To manage the dynamic list of indexes efficiently, a clever binary encoding scheme is employed. Each ballot in the CBR is assigned a binary value: 0 if it's a noise ballot (randomization by the server) and 1 if it's a ballot generated by the voter.
• This binary sequence is then stored as a decimal value.
• When a new ballot is added to the CBR:
• If it's a noise ballot (server randomization), the decimal value of the list of indexes is updated to 2 * previous_value. This effectively appends a 0 to the binary representation.
• If it's a voter-generated ballot, the decimal value is updated to 2 * previous_value + 1. This appends a 1 to the binary representation.
• This encoding allows the voter and server to consistently update and verify the sequence of voter-generated ballots. For example, if a voter wants to cancel ballots at indexes 2 and 4, the correct decimal value for the list of indexes would be 21 (assuming a specific sequence of previous ballots). The voting server checks if the value provided by the voter matches its own calculated value for the list of indexes.

1. Ballot Structure and Server Operations:

• Voter's Ballot: Consists of three ElGamal encryptions:

1. Encryption of the actual vote.
2. Re-encryption of the current list of indexes value.
3. Re-encryption of the 2 * previous_value + 1 (representing the addition of a voter-cast ballot).

• Voting Server's Ballot: Consists of three re-encryptions:

1. Re-encryption of the vote ballot: This depends on whether the voter's provided list of indexes was correct. If correct, the server re-encrypts the last ballot. If incorrect (coerced attempt), it re-encrypts the second-to-last ballot to cancel the coerced vote.
2. The other two re-encryptions set the values of the list of indexes to 2 * previous_value, effectively adding a noise ballot to the sequence.

1. Verifiability:

• To ensure the correct operation of the voting server without revealing the sensitive content of the list of indexes, a disjunctly non-interacted zero-knowledge proof of knowledge (DNIZKP) is employed. This proof takes as input the encrypted values of both the voter's and the server's list of indexes (which are publicly available on the bulletin board) and allows anyone to verify that the server correctly followed the protocol rules for updating the CBR and responding to voter inputs. This ensures that the voting server does not need to be trusted for verifiability.

1. Tallying:

• The tallying process is remarkably efficient. For each voter, only the last noise ballot in their CBR is considered. This design eliminates the need for a separate filtering phase and allows for tallying that is linear to the number of voters, not the total number of ballots, as coerced or invalid votes are effectively canceled during the voting phase itself.

1. Quantitative Coercion Resistance:

• The system offers strong resistance against brute-force attacks by a coercer attempting to guess the correct list of indexes. If the CBR contains M ballots, the coercer needs to guess K out of them. The number of required attempts exhibits exponential growth, specifically related to the M+1-th Fibonacci number. As M grows, it becomes astronomically difficult for a coercer to guess the precise sequence of voter-generated ballots. Furthermore, the voting server can detect and potentially block voters who submit an excessive number of incorrect index lists, further deterring brute-force attempts. The probability distribution of noise ballot timing, controlled by the server, also makes it difficult for a coercer to infer voter behavior based on timing.

This intricate interplay of dynamic credentials, noise ballots, cryptographic operations, and zero-knowledge proofs creates a robust framework for secure internet voting that can withstand sophisticated coercion attempts, particularly those occurring at the last minute.

Demo / Proof of Concept

▶ Watch: Example: Voter revotes to cancel a previously coerced ballot (6:00)

While the presentation did not feature a live, interactive demonstration of the system, the speakers confirmed the implementation of a prototype of their technique. This prototype was developed in Python, providing concrete evidence of the practical feasibility and efficiency of their proposed cryptographic scheme.

The performance metrics obtained from this Python prototype are highly encouraging and underscore the scalability of the approach:

• Ballot Generation and Encryption: For an election involving two candidates, the process of generating and encrypting a ballot required less than 10 milliseconds. This indicates that the cryptographic overhead for individual voters is minimal, ensuring a smooth user experience.
• Ballot Verification: The verification of a ballot (likely by the voting server using the DNIZKP) was even faster, requiring less than 1 millisecond. Such rapid verification is crucial for maintaining the responsiveness and integrity of the bulletin board and the overall voting system.
• Tallying Efficiency: Perhaps the most impressive performance figure relates to the tallying process. The prototype demonstrated that for an election with 1 million voters, the final tally could be completed in less than 1 minute on a standard laptop machine. This validates the claim that the system's design, which considers only the last noise ballot for each voter, results in a highly efficient tallying mechanism that scales linearly with the number of voters rather than the total number of ballots cast (including noise ballots).

These performance figures suggest that the proposed technique is not merely theoretically sound but also practically viable for real-world internet voting deployments, even at a large scale. The efficient processing times for ballot operations and, critically, for the final tally, address a common concern regarding the computational demands of advanced cryptographic voting schemes.

Defensive Implications

▶ Watch: How the list of indexes is encoded and updated (8:00)

The technique presented by Giustolisi, Sheikhi, and Schuermann offers profound defensive implications for the design and implementation of secure internet voting systems, particularly in mitigating the persistent threat of voter coercion.

1. Enhanced Coercion Resistance for System Designers: Election authorities and system architects should prioritize the integration of mechanisms that provide robust last-minute coercion resistance. This work demonstrates that by combining elements of fake credentials and deniable revoting through dynamic credentials and noise ballots, it is possible to build systems where voters can always cast their true vote, even under direct observation or duress. This raises the bar for security requirements in internet voting protocols.

1. Shift in Trust Assumptions: The elimination of the need for a trusted registration authority and the assumption of uncoerced registration significantly simplifies the trust model of internet voting systems. Defenders can design systems with fewer single points of failure related to trust, reducing the attack surface. This allows for more decentralized and resilient registration processes.

1. Proactive Coercion Mitigation: The system's ability to detect and effectively "cancel" coerced ballots during the voting phase itself, rather than relying solely on post-election audits or voter complaints, represents a proactive defense against coercion. The voting server's capacity to add noise ballots that invalidate coerced votes empowers the system to actively thwart coercion attempts in real-time.

1. Verifiable Server Operation: The use of disjunctly non-interacted zero-knowledge proofs of knowledge (DNIZKP) for verifying the voting server's correct operation is a critical defensive measure. It ensures that the server processes ballots and updates the CBR according to protocol rules without revealing sensitive voter information (like the list of indexes). This transparency without disclosure builds public trust and allows for independent auditing of the server's cryptographic processes.

1. Deterrence Against Brute-Force Attacks: The quantitative measure of coercion resistance, demonstrating exponential growth in the difficulty for a coercer to guess the correct list of indexes, acts as a strong deterrent. System designers can leverage this property by implementing server-side monitoring for excessive incorrect ballot submissions from a voter, potentially flagging or even temporarily blocking suspicious activity to prevent prolonged brute-force attempts.

1. Efficient and Auditable Tallying: The highly efficient tallying process (linear to the number of voters) means that election results can be compiled quickly without compromising security. Furthermore, because the system relies on publicly verifiable CBRs and cryptographic proofs, the final tally remains auditable, reinforcing the overall integrity of the election.

1. Empowering Voters: Ultimately, the defensive implications extend to the voters themselves. By providing a mechanism where they can resist coercion without having to lie or perform complex actions, the system empowers voters, enhancing their autonomy and confidence in the electoral process. They can trust that even if coerced, their true vote can still be counted.

In summary, this work provides a robust framework that can significantly strengthen the defensive posture of internet voting systems against one of their most challenging threats: voter coercion, particularly at the critical last minute.

Key Takeaways

• Last-Minute Coercion Resistance: The research introduces the first technique for deniable vote updating that effectively thwarts last-minute voter coercion, a significant vulnerability in previous deniable revoting schemes.
• Hybrid Approach with Dynamic Credentials: The system innovatively mixes fake credentials and deniable revoting through the concept of dynamic credentials, where voter credentials change based on voting behavior, providing robust deniability.
• Elimination of Trusted Authorities: The new technique removes the need for a trusted registration authority and the assumption of uncoerced registration, simplifying the trust model and enhancing overall system resilience.
• Strategic Use of Noise Ballots: Voting servers cast noise ballots that are indistinguishable from voter ballots, effectively obfuscating true voting behavior and providing a strong layer of deniability for voters under duress.
• Highly Efficient Tallying: The design allows for extremely efficient tallying, linear to the number of voters (e.g., 1 million voters in less than a minute), by canceling coerced ballots during the voting phase itself and only considering the last noise ballot for each voter.
• Quantitative Coercion Deterrence: The system offers exponential resistance against brute-force attacks by coercers attempting to guess a voter's true ballot sequence, making such attacks computationally infeasible.

About the Speaker(s)

The talk "Thwarting Last-Minute Voter Coercion" was a collaborative effort presented by Rosario Giustolisi, with joint work by Maryam Sheikhi and Carsten Schuermann. While specific affiliations were not detailed in the transcript, their presentation at a prestigious conference like IEEE S&P (Institute of Electrical and Electronics Engineers Symposium on Security and Privacy) indicates their background as researchers and experts in the fields of cryptography, election security, and secure computing. Their work focuses on addressing critical security challenges within internet-based voting systems, particularly concerning voter privacy and coercion resistance.