TL;DR
This paper introduces "concurrent ballot authorization" for internet voting, allowing ballots to be authorized as they are submitted, not just after the election closes. Their proof-of-concept system, Cobra, achieves near-instantaneous tallying, significantly mitigating denial-of-service attacks that could delay results.
What Problem Does This Paper Address?
Internet voting faces significant challenges, particularly regarding coercion resistance and vote selling. In traditional voting, a private booth ensures voters can cast their ballot without external influence. Internet voting lacks this physical privacy, opening the door for coercion (someone forcing a voter to vote a certain way) and vote selling (a voter proving how they voted to a buyer).
Existing coercion-resistant internet voting schemes address this by allowing voters to generate "fake" credentials to show a coercer, while using their "real" credential to cast their actual vote. A crucial step in these systems is "ballot authorization," where the election authority verifies that submitted ballots are legitimate and not duplicates, without revealing which ballots were fake. However, this authorization process is computationally intensive and, in most prior work, must happen after all ballots are cast. This creates a vulnerability: an adversary could flood the system with fake ballots, delaying the election results and potentially undermining trust. The paper tackles the problem of making ballot authorization efficient and concurrent with ballot casting.
Methods
The core innovation is concurrent ballot authorization. Instead of waiting until the end of the election, Cobra authorizes ballots as they are submitted. This is achieved by using an encrypted Bloom filter as a central component.
Here's a breakdown of the key techniques:
- Encrypted Bloom Filter (EBF): This is a data structure that allows for efficient membership testing (checking if an element is in a set) even when the data is encrypted. Cobra uses an EBF to store encrypted voter credentials. When a ballot is submitted with a credential, the system queries the EBF. If the credential is found, the ballot is authorized; otherwise, it's "zeroed out" (effectively discarded).
- Concurrent Authorization: The EBF allows for individual ballot authorization. As soon as a ballot is submitted and its credential is checked against the EBF, the authorization decision can be made. This means authorization happens in parallel with ballot casting.
- Proof-of-Concept System (Cobra): The paper presents Cobra as a concrete implementation. It uses cryptographic primitives like homomorphic encryption and verifiable proofs.
- Registration Process: A key part of Cobra's design is its registration protocol. Voters create a credential (derived from a password) and this credential is used to populate the encrypted Bloom filter. The paper notes that their current registration process is computationally expensive (quadratic in the number of voters), which is a significant limitation.
- Ballot Casting and Authorization: Voters submit an encrypted ballot along with their credential and proofs. The authority then uses the EBF to authorize the ballot. If authorized, the vote is preserved; if not, it's nullified.
- Tallying: Because ballots are authorized concurrently, the tallying process can begin immediately after the polls close, leading to near-instantaneous results.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The Bottleneck is Authorization: The paper highlights that the computational cost of ballot authorization is a major bottleneck in existing coercion-resistant internet voting systems, especially concerning denial-of-service attacks.
- Concurrency is Key: Shifting ballot authorization to happen during the voting period, rather than after, is a fundamental shift that enables faster tallying and resilience against flooding attacks.
- Encrypted Bloom Filters as a Tool: The use of encrypted Bloom filters provides an efficient and verifiable way to perform set membership tests on encrypted data, which is crucial for authorization.
- Trade-offs in Registration: While Cobra excels at concurrent authorization and fast tallying, its current registration process is prohibitively slow for practical use. This points to a critical trade-off that needs to be addressed in future work.
Key Results
- Fastest Tallying: Cobra offers the fastest tallying time compared to related coercion-resistant internet voting schemes.
- Mitigation of Board Flooding: By authorizing ballots concurrently, Cobra significantly reduces the impact of denial-of-service attacks that aim to flood the system with fake ballots and delay results.
- Proof-of-Concept System: The paper provides a concrete system (Cobra) demonstrating the feasibility of concurrent ballot authorization.
- Impractical Registration: The authors acknowledge that their current registration process is quadratic in the number of eligible voters, making it "too slow to be viable" for real-world elections.
Limitations and Future Work
- Registration Complexity: The most significant limitation is the quadratic complexity of the registration process. Future work needs to find methods for concurrent ballot authorization with linear registration.
- Credential Reuse: Cobra, in its current form, does not maintain coercion resistance if a credential is used across multiple elections. This is a known issue in coercion-resistant systems and requires further investigation.
- Bare-handed Registration: The paper mentions that registration requires voters to use a computational device to generate proofs. Future work could explore "bare-handed" registration methods.
- False Positives: The use of Bloom filters inherently introduces a small probability of false positives (an invalid credential being accepted). The paper discusses parameterizing this probability to be acceptably low, but it remains a theoretical concern.
Summary updated