💻 computer science

Audit-or-Cast: Enforcing Honest Elections with Privacy-Preserving Public Verification

This paper introduces ACE, a novel voting protocol that achieves end-to-end verifiability, public tally-hiding, and strong receipt-freeness under untrusted client assumptions by combining a privacy-preserving aggregation mechanism with an "Audit-or-Cast" challenge and tallier-side re-randomization.

Original authors: Aman Rojjha, Gaurang Tandon, Varul Srivastava, Kannan Srinathan

Published 2026-04-22

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Aman Rojjha, Gaurang Tandon, Varul Srivastava, Kannan Srinathan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are part of a massive neighborhood vote to decide where to build a new park. You have three big worries:

Privacy: You don't want your neighbor to know you voted for the "Dog Park" instead of the "Swing Set."
Honesty: You don't want the person counting the votes to secretly change the numbers.
Coercion: You don't want a bully to force you to vote a certain way and then demand to see your "receipt" as proof.

For a long time, computer scientists thought you could only have two of these three. If you wanted to prove the count was honest, you usually had to reveal how people voted. If you wanted to hide the votes, you often had to trust the people counting them blindly.

This paper introduces ACE (Audit-or-Cast Election), a new digital voting system that solves this puzzle. Think of it as a "Magic Voting Booth" that guarantees all three things at once.

Here is how it works, using simple analogies:

1. The "Blind Envelope" (Privacy & The Talliers)

Imagine you write your vote on a piece of paper. Instead of putting it in a box, you put it in a magic envelope that is locked with a special code.

The Problem: If you give this envelope to the vote counters (called "Talliers"), they might peek inside or swap your paper for a different one.
The ACE Solution: Before the counters even see your envelope, they put it inside another magic envelope and shake it up. This is called Re-randomization.
- It's like taking your sealed envelope, putting it in a giant, opaque bag, and shaking the bag so hard that even if the counter opens the bag later, they can't tell which specific envelope was yours.
- Because of this shaking, even if all the counters collude (work together), they cannot link a specific vote back to you. It's mathematically impossible.

2. The "Audit-or-Cast" Game (Honesty)

This is the cleverest part. The system forces the counters to play a game of "Catch Me If You Can" with you, the voter.

The Setup: You submit your vote. The counters put it in that "shaken bag" (re-randomized) and post the result on a public bulletin board (like a town square notice board).
The Choice: Now, you have to make a choice. You can either Audit or Cast.
- Option A: Audit (The Check): You say, "I want to check if you are being honest." The counters must then show you the "un-shaking" key to prove they didn't swap your vote.
  - The Catch: If you choose to Audit, your vote is discarded. It doesn't count. You have to start over with a new vote.
  - Why this works: The counters don't know if you are going to Audit or Cast. If they try to cheat (swap your vote), and you happen to pick "Audit," they get caught immediately. If they cheat and you pick "Cast," they get away with it this time, but they can't cheat every single time because you might Audit next time.
- Option B: Cast (The Vote): You say, "I trust you, count my vote." You give them the final key to unlock the envelope.
  - Once you say "Cast," the vote is locked in forever. You can't change it, and you can't prove to anyone else what you voted for (more on that below).

The Analogy: Imagine a magician asks you to pick a card. He says, "I will put your card in a box. You can either ask me to open the box to prove I didn't swap it (but then I throw the card away), or you can say 'Keep it' and it counts."
Because the magician doesn't know which you will choose, he is terrified to swap the card. If he swaps it and you ask to check, he gets busted. So, he keeps your card safe.

3. The "Un-Receipt" (Stopping Coercion)

This is the "Holy Grail" of voting.

The Problem: In many systems, if a bully says, "Vote for Candidate X, or I'll hurt you," you can vote for X, take a photo of your digital receipt, and show the bully.
The ACE Solution: Because of the "shaking" (re-randomization) mentioned earlier, the receipt you hold is useless.
- Even if you show the bully your "receipt" (the original envelope), the public record shows a completely different, scrambled version.
- The bully cannot prove that your receipt matches the public record because the "shaking" key was held by the counters, not you.
- You can tell the bully, "I voted for Candidate Y," and show them a fake receipt that looks just as real as the real one. The bully has no way to verify you. This stops vote-selling and coercion.

4. The "Public Ledger" (Transparency)

Finally, imagine a giant, unchangeable digital chalkboard (the Public Bulletin Board) in the town square.

Every time a vote is cast, a math puzzle is posted there.
Anyone (a neighbor, a journalist, a computer) can look at the board and check the math to ensure the final winner was calculated correctly.
They can do this without ever seeing who voted for what. It's like checking the final score of a football game without needing to see the players' faces.

Summary: Why is this a big deal?

Previous systems were like a blind trust (we trust the counters) or a public leak (we show everyone how you voted to prove it's fair).

ACE is like a secure, self-policing game.

You get to check the counters constantly (Audit).
The Counters are forced to be honest because they don't know when you will check.
Your Privacy is protected by math that makes your vote untraceable.
The Result is verifiable by anyone, ensuring the winner is the true winner.

It's a system where you don't have to trust the people running the election; you just have to trust the math and the game rules.

1. Problem Statement

Electronic voting systems face a fundamental trilemma: they must simultaneously achieve End-to-End Verifiability (E2E-V), Voter Privacy (specifically Receipt-Freeness), and Public Tally-Hiding.

The Conflict: Existing protocols often sacrifice one property for another.
- Systems like Helios achieve verifiability but leak full vote tallies (failing Public Tally-Hiding).
- Systems like Ordinos hide tallies but often rely on trusted clients or allow transferable receipts (failing Receipt-Freeness).
- Many systems require voters to use trusted devices, which is unrealistic in real-world deployments where devices may be compromised.
The Goal: The authors aim to design a protocol for national-scale elections that prevents coercion (via receipt-freeness), hides intermediate and final vote distributions from the public (tally-hiding), and allows anyone to verify the election result without revealing individual votes, all without assuming trusted voting clients.

2. Methodology: The ACE Protocol

The proposed Audit-or-Cast Election (ACE) protocol resolves these conflicts through a novel combination of cryptographic primitives and an interactive challenge mechanism.

A. Core Cryptographic Primitives

Pedersen Vector Commitments: Used to commit to vote shares. These commitments are "perfectly hiding," meaning they reveal no information about the underlying value, even to an adversary with infinite computational power.
Tallier-Side Re-randomization: Instead of the voter committing and publishing directly, the voter sends a commitment to a Tallier. The Tallier then re-randomizes this commitment (multiplying by a random factor) before publishing it to the Public Bulletin Board (PBB). This breaks the link between the voter's original commitment and the public record.
Non-Interactive Zero-Knowledge Proofs (NIZK): Used to prove the well-formedness of votes and the correctness of the final tally without revealing the votes themselves.

B. The "Audit-or-Cast" Mechanism

This is the protocol's central innovation, replacing the need for trusted clients with a Cut-and-Choose style interactive proof between the Voter and the Talliers.

Vote Generation & Sharding: A voter splits their vote into shares and creates commitments.
Blinded Submission: The voter sends commitments to Talliers. Talliers re-randomize these commitments and publish them to the PBB.
The Challenge Phase: Upon seeing the re-randomized commitments on the PBB, the voter must choose one of two paths:
- Option A (Audit): The voter challenges the Talliers to reveal the re-randomization factors. The voter verifies that the published commitment is indeed a valid re-randomization of their original input.
  - Outcome: If the Tallier is honest, the verification passes, but the vote is discarded. The voter must restart the process with new randomness.
  - Security: If the Tallier is malicious (e.g., trying to alter the vote), the voter can detect the mismatch and publish a Proof of Incorrect Opening (PoIO), evicting the malicious Tallier.
- Option B (Cast): The voter accepts the commitment and signals "Cast."
  - Outcome: The vote is finalized. The voter opens the original shares to the Talliers for verification.
Security Guarantee: Since the adversary (Tallier) does not know whether the voter will Audit or Cast, they are forced to behave honestly in every instance. If they cheat, they risk being caught during an Audit round.

C. Tally Aggregation and Result

Tally-Hiding: The final tally is reconstructed by a Designated Tallier ( $T_{des}$ ) using the aggregated shares.
Public Verification: $T_{des}$ publishes the final result and a NIZK proof that the result corresponds to the committed votes on the PBB.
Receipt-Freeness: Because the Tallier adds a random blinding factor ( $\tilde{r}$ ) that is never revealed to the voter (unless an Audit is triggered, in which case the vote is voided), the voter cannot produce a valid receipt linking their specific vote to the public record. Even if coerced, the voter can claim they voted differently, and the coercer cannot verify the claim because the blinding factor is unknown.

3. Key Contributions

The "Holy Trinity" Achievement: ACE is the first protocol to simultaneously achieve:
- Public Tally-Hiding (P2): The public sees only the final result, not vote margins or distributions.
- Strong Receipt-Freeness (P3): Voters cannot prove how they voted, even if coerced.
- End-to-End Verifiability (S5): Anyone can verify the election outcome.
Untrusted Client Assumption: The protocol enforces "Cast-as-Intended" (S3) even if the voter's device is untrusted, relying instead on the Audit-or-Cast challenge to detect malicious Talliers.
Information-Theoretic Privacy: By using perfectly hiding Pedersen commitments and assuming at least one honest Tallier, the protocol achieves information-theoretic privacy (unbreakable even with infinite computing power) against collusion of all other Talliers.
Formal Security Proofs: The authors provide formal definitions and proofs for:
- Verifiability (S1–S5): Proving that the result matches the cast votes.
- Publicly Tally-Hiding: Proving that the public learns nothing about the tally distribution.
- Receipt-Freeness: Proving that a simulator can generate a view indistinguishable from a real execution, even if the adversary knows the voter's secrets.

4. Results and Performance

Comparative Analysis: Table II in the paper compares ACE against state-of-the-art protocols (Helios, Prêt à Voter, Ordinos, Kryvos, etc.). ACE is the only protocol marked with checkmarks for all Privacy (P1-P3) and Security (S1-S5) properties.
Communication Overhead:
- Voter: $O(k \cdot n_t)$ , where $k$ is the number of Audit-or-Cast rounds and $n_t$ is the number of Talliers.
- Tallier: $O(n_t)$ per voter.
- While slightly higher than some non-tally-hiding protocols, this overhead is considered acceptable for the enhanced security guarantees.
Robustness: The protocol handles malicious Talliers via the PoIO mechanism, allowing the system to detect and evict bad actors without halting the election.

5. Significance

The ACE protocol represents a significant leap forward in secure distributed systems and applied cryptography.

Real-World Applicability: By removing the "trusted client" assumption, ACE addresses a major barrier to deploying secure electronic voting in real-world scenarios where voter devices are often compromised or untrusted.
Balancing Transparency and Privacy: It solves the long-standing tension between the need for public auditability (to prevent fraud) and the need for strict privacy (to prevent coercion). It allows the public to verify the integrity of the count without compromising the secrecy of the ballot.
Theoretical Foundation: The formalization of "Publicly Tally-Hiding" combined with receipt-freeness sets a new standard for what constitutes a secure voting protocol, moving beyond the trade-offs that have defined the field for decades.

In summary, ACE provides a unified cryptographic framework that ensures elections are honest (via Audit-or-Cast), private (via re-randomization and hiding commitments), and verifiable (via NIZK proofs), making it a strong candidate for future national-scale digital elections.