arXiv:2604.18163v1 [cs.CR] 20 Apr 2026
Audit-or-Cast: Enforcing Honest Elections with Privacy-Preserving Public Verification Aman Rojjha∗
Varul Srivastava∗
Gaurang Tandon∗
Kannan Srinathan
CSTAR, IIIT Hyderabad Hyderabad, India
MLL, IIIT Hyderabad Hyderabad, India
Independent Researcher India
CSTAR, IIIT Hyderabad Hyderabad, India
Abstract—Electronic voting systems must balance public verifiability with voter privacy and coercion resistance. Existing cryptographic protocols typically achieve end-to-end verifiability by revealing vote distributions, relying on trusted clients, or enabling transferable receipts — design choices that often compromise trust or privacy in real-world deployments. We present ACE, a voting protocol that reconciles public auditability with strong privacy guarantees. The protocol combines a publicly verifiable, tally-hiding aggregation mechanism with an Audit-or-Cast challenge that enforces cast-as-intended even under untrusted client assumptions. Tallier-side re-randomization eliminates persistent links between voters and public records, yielding information-theoretic receipt-freeness assuming at least one honest tallier. We formalize the security of ACE and show that it simultaneously achieves end-to-end verifiability, publicly tally-hiding results, and strong receipt-freeness without trusted clients.
I. I NTRODUCTION Voting is a fundamental primitive for collective decisionmaking in modern societies, underpinning democratic governance, corporate control, and decentralized systems. As elections scale in size and adversarial sophistication, voting protocols must simultaneously satisfy strong correctness guarantees, voter privacy, and public auditability. Achieving these properties in a single system remains a central challenge in secure distributed systems and applied cryptography [1], [2]. Voting as a Classical Security Problem. The core tension in voting systems is long-standing: ballots must remain secret, yet election outcomes must be publicly verifiable. Historically, procedural safeguards and paper-based audits were used to approximate this balance, but these mechanisms do not scale well and remain vulnerable to insider attacks and coercion. Early cryptographic work formalized these challenges, introducing notions such as receipt-freeness and coercion-resistance to prevent voters from proving how they voted, even if they are willing to do so [3], [4]. Cryptographic Voting Systems. Modern electronic voting protocols rely on cryptographic primitives such as publickey encryption, homomorphic tallying, commitment schemes, and zero-knowledge proofs to achieve end-to-end verifiability (E2E-V) [5]. Systems such as Helios [6], Prêt à Voter [7], and Ordinos [8] demonstrate that universal verifiability can be achieved in practice. However, these systems often leak full ∗ Equal first authors.
or partial tallies, rely on trusted clients, or permit transferable receipts, thereby weakening privacy guarantees such as receipt-freeness and public tally-hiding [1], [9]. National Elections — Persistent Trust and Auditability Gaps. Despite formal guarantees, deployed election systems continue to face disputes rooted in limited auditability and opaque tallying processes [10]–[17]. The inability for voters or third parties to independently verify election integrity without compromising ballot secrecy remains a key source of distrust. This gap highlights the need for voting protocols that provide strong public accountability while remaining secure against coercion, malicious authorities, and compromised voting devices [18]. Problem Statement — Efficient, Secure and Private elections. The most critical application of voting in a democratic world is choosing national leaders. Attacks are two-way: manipulation of election results to sway the results in a nondemocratic direction -OR- rejection of results and undermining public opinion based on claims of forgery. We aim to address the specific challenges of national-scale elections. The system should satisfy security and privacy properties along with providing audit at each step, eliminating the possibility of ‘claiming’ forgery without proof. Towards this, we introduce properties for privacy and security in Table I. Our Approach. In this work, we introduce a cryptographic voting protocol Audit-Cast Election (ACE) protocol that simultaneously achieves end-to-end verifiability, publicly tallyhiding results, and strong receipt-freeness. Our design enforces honest behavior among mutually adversarial participants via an Audit-or-Cast mechanism, ensuring cast-as-intended even under untrusted client assumptions. Unlike prior approaches, our protocol enables public auditability of election correctness without revealing individual votes or intermediate tallies, thereby reconciling transparency and privacy within a unified cryptographic framework.
II. R ELATED W ORKS We organize related work along four axes: game-theoretic analyses of voting, cryptographic voting protocols, differential privacy approaches, and complementary frameworks.
ID
Property
Description
P1
Public Privacy
P2
Double Voting Inhibition
P3
Publicly Tally-Hiding
P4
Receipt-Freeness
S1
Vote Immutability
S2
Cast-as-Intended
S3
Tally-as-Intended
S4
End-to-End Verifiability
Talliers cannot link voters to candidates. Each voter can cast at most one valid vote. Only Tdes learns T; no vote shares or margins are revealed. Voters cannot produce transferable proof of their vote. Recorded votes cannot be altered by any party. Voters can verify correct recording of their intent. Anyone can verify correct tally computation. Anyone can verify fres (T) without ballot disclosure.
TABLE I P RIVACY (P) AND S ECURITY (S) PROPERTIES REQUIRED OF THE VOTING PROTOCOL .
A. Game-Theoretic Analyses of Voting Game theory has been used to analyze strategic behavior in voting, particularly under coercion and manipulation. Benaloh’s randomized challenge mechanism [3] pioneered audits as a deterrent against ballot tampering. Jamroga [19] formalizes this mechanism as a Stackelberg game, showing that simple randomized audit strategies achieve near-optimal security. Our Audit-or-Cast mechanism naturally fits this framework. B. Cryptographic Voting Protocols Cryptographic voting protocols aim to achieve privacy, correctness, and verifiability under adversarial conditions [1], [2]. Systems such as Helios [6], Prêt à Voter [7], and Demos [5] provide end-to-end verifiability but rely on trusted clients or leak vote distributions. Ordinos [8] achieves publicly tallyhiding elections but permits transferable receipts. Blockchainbased systems such as DeVoS [20] provide immutability at the cost of receipt-freeness. Our protocol combines public auditability, tally-hiding, and receipt-freeness without trusted clients. C. Differential Privacy and Voting Differential privacy has been proposed to limit information leakage from election results [21], [22]. These approaches trade exact correctness for statistical privacy and generally preclude cryptographic verifiability. Moreover, DP does not address coercion or receipt-freeness. Our work avoids noisebased privacy and instead relies on protocol-level guarantees.
coercion risks through persistent identifiers. In contrast, our approach relies solely on ephemeral audits and public transcripts. While existing solutions like Helios and Kryvos achieve excellent verifiability (S4), they force a trade-off: Helios reveals the full tally (failing P3) and Kryvos lacks strong receiptfreeness (failing P4). ACE is the first to achieve the ‘Holy Trinity’ of Tally-Hiding, Receipt-Freeness, and Verifiability. A comparative study of the protocols v/s ours can be found in Table II TABLE II C OMPARISON OF VOTING P ROTOCOLS AGAINST P RIVACY (P) AND S ECURITY (S) P ROPERTIES
Protocol
P1
P2
P3
P4
S1
S2
S3
S4
Helios* [24] Fasten [25] DEMOS [5] Prêt à Voter [26] Kryvos [27] Ordinos [8] DeVoS [28] Selene [23]
✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓
✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓
✗ ✗ ✗ ✗ ✓ ✓ ✗ ✗
✗ ✗ ✗* ✗** ✗ ✗ ✗ ✗
✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓
✓ ✓ ✓ ✓ ✗ ✓ ✓ ✓
✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓
✗ ✗ ✓ ✗ ✓ ✓ ✗ ✓
ACE (Ours)
✓
✓
✓
✓
✓
✓
✓
✓
*
Demos doesn’t satisfy our definition of receipt-freeness Definition 4 given voter shares the code sheet and session transcript to the coercers. ** Prêt à Voter claims receipt-freeness, but is vulnerable to “pattern coercion” if the voter photographs the ballot before casting.
III. P RELIMINARIES We briefly recall the cryptographic primitives and system abstractions used throughout the protocol. We treat all constructions as black boxes, assuming security with a computational security parameter ℓ. A. Public Bulletin Boards A public bulletin board (PBB) is an append-only, publicly readable broadcast channel with the following properties [31]: • Persistence: Once a message is posted, it cannot be removed or altered. • Public Verifiability: Any party can independently read and verify all entries. • Global Consistency: All honest parties observe the same board contents. The PBB may be instantiated using a permissionless or permissioned blockchain, a replicated append-only log, or a consensus-backed ledger. We treat the PBB as an ideal abstraction.
D. Other Related Work
B. Pedersen Vector Commitment
Formal frameworks analyze relationships between privacy, verifiability, accountability, and coercion-resistance [9], [18]. Selene [23] improves usability via voter trackers but introduces
Let ppCommVec = (G, q, h, g) be the public parameters where g = (g1 , . . . , gn ) ∈ Gn and h ∈ G. We define the algorithms as follows:
D. Non-Interactive Zero Knowledge Proofs
TABLE III N OTATION AND T ERMINOLOGY Notation V C
Election Commission (EC) Talliers Tj Tdes (j) ⃗vi ⃗vi (k) ci (j)
ri
(k)
c̃i
(j)
r̃i
T fres PBB Auditors
Description Voter set, where n = |V| Choice set, where C ⊆ (Fq )nchoices where nchoices is the number of candidates and q is the maximum number of votes allowed for a single candidate Centralized entity for setting up election. Special meaning for publicly tally-hiding in elections. Tallier set T (size nt ) responsible for receiving voter (j) shares vi from the voters Designated tallier for accumulating the final tally Vote share submitted by ith voter to tallier Tj Vote finalized by voter i Pedersen Vector Commitment [29] over vote share (k) ⃗vi under the group generators g and h as specified on PBB Randomness used by voter i for computing commit(j) (j) ment ci for it’s jth vote-share ⃗vi (k) Pedersen Commitment [30] over vote share ⃗vi under the group generators g and h as specified on PBB Randomness used by tallier Tj for commiting to the (j) voter i’s vote-share commitment ci Final tally after voting period ends Efficient (polynomial) function that computes the final result from tally T Public Bulletin Board [31] providing robust storage for election transcript Any public entity (including voters themselves) which can verify the properties of the protocol from the transcripts available on PBB [31]
1) CommVec(⃗v ; r): Computes a commitment c to vector ⃗v ∈ Fnq with randomness r ∈ Fq : c = hr ·
n Y
v[k]
gk
(1)
k=1
2) ReRand(c; r′ ): Updates commitment c with fresh randomness r′ ∈ Fq to produce c′ : ′
c′ = c · hr = CommVec(⃗v ; r + r′ )
′
E. Sequential Audit-or-Cast Interactive Proof The Audit − or − Cast phase Section IV-D3 functions as a sequential Cut-and-Choose [33] interactive proof system between a Prover (Tallier Tj ) and a Verifier (Voter vi ), just like [34]. The goal is to prove the statement S that the published commitment c̃ is a valid re-randomization of the voter’s input c, i.e., S : ∃r̃ ∈ Fq s.t. c̃ = c · hr̃ . The protocol requires the voter to perform k sequential executions, auditing the first k − 1 attempts and casting the k-th, where k ∈ N is arbitrary (unknown to the adversary A). Definition 1 (PoIO). A Proof of Incorrect Opening is a tuple π⊥ = (i, j, c̃, r̃) where: • i, j are the voter and tallier indices. • c̃ is the re-randomized commitment published on PBB. • r̃ is the opening scalar sent by Tj to vi . (j)
The proof π⊥ is valid if and only if c̃ ̸= ci · hr̃ . IV. M ODEL
(2)
3) DeRand(c′ ; r′ ): Reverts c′ using factor r′ to retrieve original commitment c: c = c′ · h−r = CommVec(⃗v ; (r + r′ ) − r′ )
Let R be a relation generator for NP statements, defined as pairs (x, w) where x is the public instance and w is the private witness. A NIZKP scheme Π consists of three efficient algorithms: 1) Π.Setup(R) → (σpk , σvk ): A trusted setup that takes the relation R (represented as an arithmetic circuit) and outputs a proving key σpk and a verification key σvk . 2) Π.Prove(σpk , x, w) → π: Given the proving key, a public statement x, and a valid witness w such that (x, w) ∈ R, outputs a succinct proof π consisting of three group elements. 3) Π.Verify(σvk , x, π) → {0, 1}: Given the verification key, statement x, and proof π, outputs 1 (Accept) if the proof is valid, and 0 (Reject) otherwise. The protocol satisfies Completeness, Computational Knowledge Soundness, and Perfect Zero-Knowledge. We use [32] proof system.
(3)
Relationship: The functions satisfy the consistency relation DeRand(ReRand(c; r′ ); r′ ) = c. C. PKI We assume Public Key Infrastructure, i.e., all the involved entities (voter, Tj , auditors) have a consistent view of each other’s public keys. Digital Signatures Schemes are a 3-tuple (Gen, Sign, Vrfy) ((Gen(·), Signsk (m), Vrfypk (σ, m))) which can verify the integrity of a message w.r.t a public key pk, i.e., if the message m was sent by the entity holding the secret key sk corresponding to pk with which message was signed.
We describe the system/entities, threat assumptions, and formal properties required of the protocol. Our presentation follows standard e-voting modeling frameworks [35], [36]. A. Participants The protocol runs among the following entities: • Election Commission (EC): A trusted setup authority responsible for initializing public parameters, cryptographic primitives, and protocol timing. EC does not participate in voting or tallying. • Voters (vi ∈ V): Each voter selects a choice ⃗ vi ∈ C ⊆ (Fq )nchoices and participates in the Audit-or-Cast protocol to submit their vote. • Talliers (Tj ∈ T ): A set of mutually distrustful parties responsible for receiving blinded vote shares, validating openings, and contributing to tally reconstruction. • Public Bulletin Board (PBB): An append-only, publicly readable, and persistent broadcast channel that stores
commitments, proofs, and final results. This can be realized through public-blockchains [31]. • Designated Tallier (Tdes ): A publicly known entity responsible for reconstructing the final tally and producing a zero-knowledge proof of correctness. • Judge (J): A virtual verification entity that, given only public information, accepts or rejects a protocol execution. • Scheduler (S): A virtual process responsible for coordinating protocol phases and modeling the behavior of EC. All parties possess public-key identities established via a PKI, and all messages are digitally signed. B. Threat Model We model the adversary A as a static, active (malicious) entity capable of corrupting a subset of protocol participants. We assume mutually authenticated channels [37] between all parties. • Voter Independence: Let Vcorr ⊂ V be the set of voters corrupted by A. We assume that malicious voters are computationally independent; they do not share their pri(j) vate witnesses (randomness ri or shares ⃗vi ) to construct a joint proof. • Tallier Thresholds: – Privacy: Since the protocol uses (n, n)-threshold secret sharing, voter privacy is preserved as long as at least one tallier remains honest and refuses to reveal their received shares. – Integrity (Anti-Censorship): We assume that a tallier Tj does not collude with the entire remaining set of talliers T \ {Tj } to suppress valid votes. C. Protocol properties We discuss the intended privacy (P) and security (S) properties informally below: P1 Public Privacy: Any proper subset of Tj ⊂ T should not be able to verify if vi corresponds to a candidate ci . S1 Vote Immutability: Any party i should not be able to change vi (including the voter himself) once the vote has been casted/finalized. P2 Double Voting Inhibition: A voter should not be able to vote multiple times. S2 Cast-as-intended: A voter should be able to verify if his vote vi has been recorded correctly. S3 Tally-as-intended: Any voter should be able to verify the final tally T is correct. S4 End-to-end Verifiability: When voting is over and winner (or set of winners) is declared, then any person should be able to verify the results fres (T). P3 Publicly Tally-Hiding: Tdes knows final tally T but no one else does. Public disclosure of exact vote counts may deter candidates fearing reputational damage from wide margins of defeat. On the other hand, if a candidate widely perceived as popular wins by only a narrow
Algorithm 1: Vote Generation and Audit-or-Cast (Voter vi ) Input: Vote vi ∈ C, Talliers T = {T1 , . . . , Tnt }, Public Board PBB Output: Committed vote on PBB or ⊥ ▷ 1. Vote Generation & Sharding (j) t s.t. 1 Split vi into full-threshold shares {⃗ vi }nj=1 P (j) ⃗vi = vi mod q (j) 2 Sample randomness ri ← Zq for all j ∈ [nt ] (j) (j) (j) 3 Compute commitments ci ← CommVec(⃗ vi ; ri ) 4 Generate NIZKP πvotei proving well-formedness of vi (j) and {ci } ▷ 2. Blinded Submission 5 for j ∈ [nt ] do (j) 6 Send (i, ci ) to Tj via private channel 7 end 8 Verify presence of re-randomized commitments (j) {(i, c̃i )} on PBB ▷ 3. Audit-or-Cast Decision 9 Select b ← {0, 1} ▷ 0: Audit, 1: Cast 10 if b = 0 (AUDIT) then 11 Send AUDIT request to all Tj ∈ T (j) 12 Receive blinding factors {r̃i } from talliers 13 for j ∈ [nt ] do (j) (j) (j) 14 if ci ̸= DeRand(c̃i ; r̃i ) then 15 Construct and publish PoIO on PBB 16 return ⊥ (Restart protocol) 17 end 18 end 19 Wait for PBB to discard submission, then goto Step 1 20 end 21 else CAST 22 Send CAST request to all Tj ∈ T 23 Wait for CAST finalization on PBB ▷ 4. Opening 24 for j ∈ [nt ] do (j) (j) 25 Send opening (⃗vi , ri ) to Tj via private channel 26 end 27 end
margin (say, 51% to 49%), it undermines their perceived mandate and weakens their position. Therefore, public exposure can damage community trust and political stability in either case. P4 Receipt-Freeness: The voter should not be able to obtain information proving their vote [6]. This is to avoid voter coercion by third party or vote-selling by the voter himself. Also note that receipt-freeness inherently implies coercion-resistance.
D. Voting phase 1) Vote Generation: This phase represents the local computational steps performed by Voter i. Voter i selects their vote ⃗vi ∈ C and do the following: 1) Sharding: The voter splits the vote into fully-threshold Pnt (j) (j) ⃗vi mod q = ⃗vi . vote shares ⃗vi such that j=1 2) Commitment: The voter creates Pedersen Vector Commitments [29] for each share: (j)
ci
(j)
(j)
= CommVec(⃗vi ; ri )
∀ j ∈ [nt ]
3) Proof Generation: Voter i generates a NIZKP πvotei attesting to the well-formedness of ⃗vi ∈ C and that the (j) t reconstructs to this valid set of commitments {ci }nj=1 vote. 2) Blinded Submission: (j)
Voter i sends the commitment ci to each Tallier Tj over a private channel. (j) • Tallier Tj generates a random blinding factor r̃i and re-randomizes the commitment [30]:
•
(j)
c̃i •
(j)
(j)
(j)
(j)
= ReRand(ci ; r̃i ) = CommVec(⃗vi ; ri
(j)
+ r̃i ) (j)
Tj publishes the re-randomized commitment pair (i, c̃i ) on the PBB.
3) Audit-or-Cast Mechanism: Once the re-randomized commitments appear on the PBB, Voter i verifies their presence. The voter must then choose to strictly execute one of the following actions: Option A: AUDIT (Challenge). The voter challenges the talliers to prove they stored the commitments honestly. 1) Voter sends an AUDIT request to all Tj ∈ T . 2) Each Tj responds by privately sending the blinding factor (j) r̃i to Voter i. (j) (j) (j) (j) 3) Voter checks if ci = DeRand(c̃i ; r̃i ) where c̃i exists on PBB. 4) Outcome: The vote ⃗vi and its associated commitments on PBB become invalid. The talliers discard the submission. The Voter must return to Phase IV-D1 (Vote Generation) to generate fresh randomness and shares before resubmitting.1 Option B: CAST. If the voter is satisfied (or chooses not to audit), they finalize the vote. 1) Voter sends a CAST request to all Tj . 2) This signal commits the vote-shares for voter i as final on the PBB. No further auditing of this specific instance is permitted. 1 Security Note: If a voter detects a mismatch during Audit (meaning T j maliciously altered the commitment), the voter constructs a Proof of Incorrect Opening (PoIO) using the digitally signed messages from the submission step. This is published to PBB, triggering the removal of the malicious Tj .
4) Opening and Verification: This phase executes only after the CAST signal is finalized for voter i on the PBB. (j)
(j)
1) Opening: Voter i sends the openings (⃗vi , ri ) to the respective Tj ∈ T over a private channel. 2) Tallier Verification: Tj validates the opening against the (j) stored commitment ci . 3) Synchronization: All Tj ∈ T synchronize the commitments to reconstruct the aggregated commitment ci = Qnt (j) j=1 ci . 4) Proof Validation: Each Tj verifies the NIZKP πvotei . Upon success, the talliers generate a threshold signature σT attesting to the validity of the vote and publish it to PBB. 5) Validity Tests: 1) In the Audit − or − Cast phase, if the tallier Tj sends in(j) correct opening r̂i , voter vi creates a Proof of Incorrect Opening (PoIO) (discussed more in Definition 1) of jth vote-share commitment along with digitally-signed open(j) (j) ing r̂i and commitment c̃i it received and publishes on PBB. 2) If Tj finds πvotei invalid, vote-shares for voter i are considered invalid and discarded from the final tally after publishing a PoIO along with digitally-signed messages and aggregate commitment ci . Upon receiving a ballot, PBB checks the current state to verify that the associated voter has not previously committed a vote. If a prior entry exists, PBB aborts the operation and rejects the submission; otherwise, the vote is committed. 3) If taillier verification Section IV-D4 fails for a vote-share (j) (j) opening (⃗vi , ri ) at tallier Tj , Tj publishes a Proof of Incorrect Opening (PoIO) along with digitally-signed (j) (j) messages it received (⃗vi , ri ) on the PBB. This proof (j) consists of the digitally signed commitment ci (from the Voting Phase) and the conflicting opening received. Voting phase ends after CAST signal is finalized for all the voters vi ∈ V on the PBB. E. Tally Aggregation For simplicity, we assume that all vote-shares were valid. For each j ∈ [nt ], Tallier Tj performs the following: 1) Share Aggregation: Tj sums the valid vote-shares and corresponding randomness for all n voters: (j)
⃗v⊥ =
n X (j) ⃗vi , i=1
(j)
r⊥ =
n X (j) ri ,
(j)
r̃⊥ =
i=1
n X (j) r̃i i=1
(j)
(j)
(j)
2) Transmission: Tj sends the tuple (⃗v⊥ , r⊥ , r̃⊥ ) to the designated entity Tdes over an authenticated channel. F. Result Phase Tdes is responsible for reconstructing the final tally from the aggregates provided by the talliers.
Algorithm 2: Tallier Operations (Tallier Tj ) (j)
Input: Incoming commitments ci , signals from vi ∀vi ∈ V ▷ Phase: Blinded Submission (j) 1 Upon receiving ci from vi do (j) 2 Sample blinding factor r̃i ← Zq (j) (j) (j) 3 Compute c̃i ← ReRand(c̃i ; r̃i ) (j) 4 Publish (i, c̃i ) to PBB 5 end ▷ Phase: Audit-or-Cast 6 Upon receiving AUDIT from vi do (j) 7 Send r̃i to vi over private channel (j) 8 Discard stored vote-share commitment c̃i for vi from PBB; 9 end 10 Upon receiving CAST from vi do (j) 11 Mark vote-share commitment c̃i as finalized on PBB (j) (j) 12 Receive opening (⃗vi , ri ) from vi (j) (j) (j) 13 if CommVec(⃗vi ; ri ) ̸= ci then 14 Publish PoIO on PBB and discard vote 15 end (j) 16 Store verified share ⃗vi 17 end ▷ Synchronization & Proof Validation (j) 18 Exchange commitments ci with other talliers T \ {Tj } Qnt (k) 19 Reconstruct aggregated commitment ci ← k=1 ci 20 if ΠRvote .Verify(πvotei , ci ) = valid then (j) 21 Generate threshold signature share σT 22 Cooperatively aggregate σT and publish to PBB 23 end 24 else 25 Flag voter i as invalid on PBB (j) 26 Reset voter i’s vote-share ⃗vi = ⃗0 27 end ▷ Phase: Tally Aggregation (Post-Voting) Pn (j) (j) 28 Compute aggregate share ⃗ v⊥ = i=1 ⃗vi P (j) (j) n 29 Compute aggregate randomness r⊥ = and i=1 ri Pn (j) (j) r̃⊥ = i=1 r̃i (j) (j) (j) 30 Send tuple (⃗ v⊥ , r⊥ , r̃⊥ ) to Tdes
1) Tallier Consistency Check: Before reconstruction, Tdes must verify that the aggregate shares received from each Tj correspond to the sum of commitments published on PBB. For every tallier Tj ∈ T : 1) Tdes computes the expected aggregate commitment from the public board: (j) c̃⊥ =
n Y (j) c̃i i=1
2) Tdes verifies2 that the received shares are a valid opening for this aggregate commitment: (j) ?
(j)
(j)
(j)
c̃⊥ = CommVec(⃗v⊥ ; r⊥ + r̃⊥ ) 2) Global Reconstruction: Upon successful verification of all talliers, Tdes computes the final election tally T by summing the aggregate shares: T=
nt X (j) ⃗v⊥ j=1
3) Result Publication and Proof: To finalize the election, Tdes publishes the result and proves its correctness relative to the public commitments. 1) Derandomization: Tdes aggregates the blinding factors to isolate the global randomness: r̃⊥ =
nt X (j) r̃⊥ j=1
Note that the global commitment to the result c⊥ can be derived publicly as: nt Y (j) c⊥ = DeRand c̃ ; r̃⊥ ⊥
j=1
2) Proof Generation: Tdes generates a NIZKP πres for the relation Rres , proving that the final tally T used for calculating the plain-text result fres (T) corresponds to the committed value in c⊥ . 3) Publication: Tdes publishes the tuple (fres (T), r̃⊥ , πres ) on PBB. G. Verification Phase Auditors can verify the S and P properties by verifying the final accumulation of “valid” votes on the PBB, the final NIZKP was computed over witness with tally commitment Qnt (j) c⊥ = j=0 c⊥ and the correctness of computation of the final result fres (T). We discuss the relevant proof of security and integrity in section Section V-A2. V. P ROTOCOL A NALYSIS We consider the security model as discussed in Section IV-B. A. Computational model We formally model our protocol in a general computational framework that we can leverage to analyze security [35] as well as privacy [36] properties, used extensively in literature for verifiability [27], [28], [38], [39] and privacy properties [24], [27], [28], [39]. We denote π = (πP || πA ) for the process where honest protocol processes πP alongside the adversarial processes which can control both the network and a static set of protocol 2 If this verification fails for any T , the tallier is proven malicious. A PoIO j is published on PBB, the tallier Tj ’s shares are discarded, and voters must re-submit shares to a fallback tallier Tk .
Algorithm 3: Result Reconstruction (Tdes ) (j) (j) (j) t , Input: Aggregates from Talliers {(⃗v⊥ , r⊥ , r̃⊥ )}nj=1
PBB Output: Final Tally T and Proof πres 1 for j ∈ [nt ] do Qn (j) (j) 2 Fetch public aggregate c̃⊥ = i=1 c̃i from PBB ▷ Consistency Check (j) (j) (j) (j) 3 if c̃⊥ ̸= CommVec(⃗v⊥ ; r⊥ + r̃⊥ ) then 4 Identify malicious Tj via PoIO and abort 5 end 6 end ▷ Global Reconstruction Pnt (j) v⊥ 7 Compute Final Tally T = j=1 ⃗ P (j) nt 8 Compute Global Blinding r̃⊥ = j=1 r̃⊥ 9 Reconstruct global commitment Q (j) c⊥ ← DeRand( j c̃⊥ ; r̃⊥ ) ▷ Proof Generation 10 Generate NIZKP πres s.t. Rres (T, c⊥ ) holds 11 Publish (fres (T), r̃⊥ , πres ) on PBB
participants. Auditors (anyone) can act as judge J, i.e., run the program pJ of judge on public input, to verify the protocol run. The goal γ of protocol P is a set of protocol runs for which the election result corresponds to the actual voter choice, where the description of a run includes the description of the protocol, the adversary with which the protocol is run, and the random coins used by these entities. According to [35], a goal γ is verifiable by a judge J in a protocol P if and only if the probability of a judge J accepting a run r of protocol P in violation of the goal γ, i.e. r ∈ / γ is negligible in the security parameter . Lastly, a scheduler process S is responsible for playing the role of authority EC as well as scheduling all involved parties in a run according to defined protocol phases. 1) Assumptions for Verifiability: P1 The public key encryption scheme E is correct, Pedersen Vector Commitment scheme is correct and computationally binding and all NIZKPs are correct and computationally sound. P2 The scheduler S, judge J and PBB are honest: φ = hon(S) ∧ hon(J) ∧ hon(PBB). Theorem 1 (Verifiability). Under the assumptions (P1-P2), the ACE protocol is verifiable by judge J. Verifiability follows from the global relations implied by local relations between the message audit trails Definition 1, NIZKP and ‘mutual maliciousness’ detected by Section IV-D3. 2) Security Proofs: S1 Vote Immutability: After the Voting phase ends, all the (j) voters’ vote-share commitments ci ∀j ∈ [nt ] are fixed on the PBB, thus trivially satisfying vote immutability enforced by the protocol and the persistence property
of PBB [31] and computational binding property of pedersen commitments [29], [30]. S2 Cast-as-intended follows from the computational binding of pedersen vector commitments [29], soundness of Section III-E protocol and (1) Section IV-D5 (over all the talliers Tj ∈ T ). S3 Tally-as-intended follows directly from the computational binding and additive homomorphic properties of commitment scheme Section III-B. S4 End-to-end verifiability follows directly from defined in Theorem 1. B. Privacy Framework We refer to the privacy framework as defined in [36] for analyzing the privacy properties of our protocol. We also refer to [27] for formal definitions of publicly tally-hiding. While the privacy framework [36] formalizes and measures coercionresisitance as a part, we introduce our definitions of receiptfreeness motivated by [40]–[42]. The main idea of Definition 2 is showing the inability of the adversary to distinguish whether some voter Vobs who runs honest program voted for m0 or m1 . For a given voting method (C, fres ), voter Vobs and ⃗vobs ∈ C, we consider runs of the protocol P as (π̂Vobs (m)||π ∗ ||πA ) where π̂Vobs (m) is the honest process of voter Vobs considering m as their choice, π ∗ is the composition of the processes of rest of the parties P and πA is adversary’s process. Definition 2 (Privacy). Let P be the voting protocol, Vobs be the voter under observation and δ ∈ [0, 1]. Then, P achieves δ-privacy, if for all messages m0 , m1 ∈ C and all adversaries πA the difference Pr[(π̂Vobs (m0 )||π ∗ ||πA )(ℓ) 7→ 1]−Pr[(π̂Vobs (m1 )||π ∗ ||πA )(ℓ) 7→ 1] is δ-bounded as a function of the security parameter 1ℓ .3 Thus, we aim to keep δ as small as possible since it specifies the adversary’s advantage to “break” user privacy. 1) Ideal Privacy: Formal privacy results are formulated ideal w.r.t. the privacy level δ(n (C, fres ) of an ideal voting h v ,nv ,µ) h protocol Ivoting (nv , nv , C, fres , µ) for voting method (C, fres ) [27, Figure 11]. Here, nv refers to the overall voters, nhv refers to the honest voters in the run. Furthermore, we assume the honest voters to choose their votes from a distribution µ over choice-space C. Assumptions for Privacy: 1) The PKE scheme E is IND-CCA2-secure. 2) The election commission EC, public bulletin board PBB and Tdes are honest. 3) Communication channels between all parties (EC, voters v ∈ V, talliers Tj ∈ T and PBB) are all mutuallyauthenticated.4 3 A function f is δ-bounded if ∀c > 0, there exists ℓ such that f (ℓ) ≤ 0 δ + ℓ−c ∀ℓ > ℓ0 [43] 4 Note that mutual-authentication via mTLS [37] is necessary owing to mutually adversarial nature of parties, esp. voters and talliers.
4) The messages from voters vi to talliers Tj are private. (only required for strict receipt-freeness) 2) Publicly Tally-Hiding: Intuitively, for a voting protocol P to be publicly tally-hiding for some voting method (C, fres , µ) • Public Privacy: P provides same privacy as the ideal voting protocol Ivoting for voting method (C, fres ), assuming all talliers are honest. • Internal Privacy: P provides the same privacy as the ideal voting protocol Ivoting for voting method (C, fcomplete ), where fcomplete returns the full tally, assuming t-out-of-nt talliers are dishonest. In other words, talliers learn as much as they would’ve in non-tally-hiding voting protocols. Definition 3 (Publicly Tally-Hiding [27]). Let P be a voting protocol with a set of talliers T and t ≤ nt . We say that P is (δP , δi )-publicly tally-hiding w.r.t (T , t) iff: 1) Public Privacy δP : If all parties Tj ∈ T are honest, then P achieves δP -privacy. 2) Internal Privacy δi : If at most t − 1 parties Tj ∈ T are dishonest, then P achieves δi -privacy. The above theorem means that the public privacy level δP is the ideal one for (C, fres , µ) and its internal privacy δi is ideal one for (C, fcomplete ) as defined above. The formal game-based proofs for internal privacy and public privacy Theorem 4 are motivated from [27].
(1)
re-randomization of the received ciphertext ci Audit − or − Cast phase correctly on PBB.
after
Theorem 4 (Publicly Tally-Hiding [27]). Let T as defined in Table III and t = nt . Then, assuming Section V-B1 hold, the voting protocol PACE (nv , nt , C, fres , µ) ideal ideal is (δ(n (C, fres ), δ(n (C, fcomplete ))-publicly tallyh h v ,nv ,µ) v ,nv ,µ) hiding w.r.t (T , nt ). 3) Receipt-Freeness: Our motivation for receipt-freeness comes directly from [34], [44]. Definition 4 (Receipt-Freeness). We say that a protocol P is receipt-free if there exists a simulator S such that for any voter v and any adversary A (who corrupts v after the voting phase and demands all secrets): Simulated ′ ′ ViewReal (v , r , PBB) A (v, r, PBB) ≈ ViewA
where in Real view, A sees the PBB (containing c̃v and all voter’s secrets (v, r) while in Simulated view, A sees PBB but voter claims they voted for v ′ ̸= v with secrets (v ′ , r′ ) (amongst all other secrets). Theorem 5 (Receipt-Freeness for ACE). The ACE protocol is receipt-free (Definition 4) against an adversary A who controls the network (except secure channels to talliers) and can coerce the voter to reveal their private state (v, r), assuming at least one tallier is honest. (j)
Theorem 2 (Internal Privacy [27]). For all m0 , m1 ∈ C, for all programs π ∗ of the remaining parties such that at least nhv voters and at least one tallier are honest in π ∗ (excluding Vobs ), | Pr[(π̂Vobs (m0 )||πA ) 7→ 1] − Pr[(π̂Vobs (m1 )||πA ) 7→ 1] | ideal is δ(n (C, fcomplete )-bounded as a function of security h v ,nv ,µ) parameter ℓ, where fcomplete return the complete tally.
Theorem 3 (Public Privacy [27]). For all m0 , m1 ∈ C, for all programs π ∗ of the remaining parties such that at least nhv voters and all talliers are honest in π ∗ (excluding Vobs ), | Pr[(π̂Vobs (m0 )||πA ) 7→ 1] − Pr[(π̂Vobs (m1 )||πA ) 7→ 1] | ideal is δ(n (C, fres )-bounded as a function of security paramh v ,nv ,µ) eter ℓ, where fres is the actual (tally-hiding) result function.
Proof Sketches, Theorem 2 and Theorem 3. We replace [27, Appendix I.2, Game 1] and [27, Appendix I.3, Game 1] keeping the proof strategy similar for our protocol. (1)
Game 1 In π̂H (m), we modify the tallier T1 for Theorem 2/T for Theorem 3 (assumed honest) to abort if either message decryption over the authenticated channel between any arbitrary honest voter vi and tallier or the digital signature (1) of the voter-share commitment ci received fails. Due to the correctness of the encryption scheme E and the digital signature scheme, Games 0 and 1 are perfectly indistinguishable. Since tallier is honest, it opens the
Proof Sketch. 1) The coercer observes the PBB entry c̃i (j) and receives the voter’s receipt ci . (j) (j) 2) The coercer tries to verify that c̃i corresponds to ci . (j) (j) The coercer calculates ccalc = CommVec(ci ; r̃i ). The (j) coercer observes c̃i on the PBB. The validity condition (j) r̃ is c̃i = ccalc · h . 3) The value r̃ is generated by the Tallier. In the Voting phase, r̃ is never sent to the voter assuming at least one honest tallier. 4) Indistinguishability: Since r̃ is drawn uniformly from Zq , the term hr̃ is a uniform random element in G. (j) Therefore, c̃i is uniformly distributed in G, independent of ccalc . Thus, for any other fake vote v ′ and fake randomness r′ , there exists a theoretical r̃′ such that ′ (j) c̃i = CommVec(v ′ ; r′ ) · hr̃ . The coercer does not know r̃, therefore they cannot deter(j) mine if c̃i was derived from the voter’s real receipt (v, r) or a (j) fake receipt (v ′ , r′ ). The PBB entry c̃i effectively becomes a ‘perfectly hiding” commitment [30] of the vote relative to the coercer, even if the coercer knows the input randomness. 4) Privacy Proofs: P1 Public Privacy follows directly from Theorem 3. P2 Double Voting inhibition is handled by PBB over blockchains through the derived property of persistence (Section III-A). P3 Publicly Tally-Hiding follows directly from Theorem 4. P4 Receipt-Freeness follows directly from Theorem 5.
VI. C ONCLUSION AND F UTURE W ORK We introduce ACE, a voting protocol that achieves public auditability, tally-hiding, and receipt-freeness within a single cryptographic framework. By combining an Audit-or-Cast mechanism with tallier-side re-randomization, the protocol enforces cast-as-intended without relying on trusted voting devices and prevents the construction of transferable receipts. Our results demonstrate that explicit audit challenges provide a principled alternative to trusted-client assumptions in electronic elections. Future work includes reducing voter interaction costs, supporting richer voting rules, and evaluating usability at scale. R EFERENCES [1] V. Cortier, D. Galindo, R. Küsters, J. Müller, and T. Truderung, “Sok: Verifiability notions for e-voting protocols,” in IEEE Symposium on Security and Privacy, 2016. [2] R. Küsters, T. Truderung, and A. Vogt, “Verifiability, privacy, and coercion-resistance: New insights from a case study,” in IEEE Symposium on Security and Privacy, 2011. [3] J. Benaloh, “Simple verifiable elections,” in USENIX/Accurate Electronic Voting Technology Workshop, 2006. [4] T. Okamoto, “Receipt-free electronic voting schemes for large scale elections,” in Security Protocols Workshop, 1997. [5] A. Kiayias, T. Zacharias, and B. Zhang, “End-to-end verifiable elections in the standard model,” in EUROCRYPT, 2015. [6] D. Bernhard, V. Cortier, O. Pereira, B. Smyth, and B. Warinschi, “Adapting helios for provable ballot privacy,” in ESORICS, 2011. [7] P. Y. A. Ryan, D. Bismark, J. Heather, S. Schneider, and Z. Xia, “Prêt à voter: A voter-verifiable voting system,” IEEE Transactions on Information Forensics and Security, 2009. [8] R. Küsters, J. Liedtke, J. Müller, D. Rausch, and A. Vogt, “Ordinos: A verifiable tally-hiding e-voting system,” in IEEE European Symposium on Security and Privacy, 2020. [9] A. Pankova and J. Willemson, “Relations between privacy, verifiability, accountability and coercion-resistance in voting protocols,” in ACNS, 2023. [10] “Georgia election: opposition disputes and integrity concerns dominate post-vote climate,” Reuters, Oct. 2024, accessed: 2026-01-13. [Online]. Available: https://www.reuters.com/world/europe/georgia-oppositionsays-election-stolen-they-seek-revote-under-international-supervision2024-10-28/ [11] “Seven eu countries call on venezuela to publish electoral rolls quickly,” Reuters, Aug. 2024, accessed: 2026-01-13. [Online]. Available: https://www.reuters.com/world/americas/seven-eu-countriescall-venezuela-publish-electoral-rolls-quickly-2024-08-04/ [12] “Pakistan’s election day marred by violence and mobile phone service suspension,” Time, Feb. 2024, accessed: 2026-01-13. [Online]. Available: https://time.com/6692687/pakistan-election-dayvoting-violence-phone-service-disturbances/ [13] “Pakistan blocks x for the sixth day as activists criticize the social media platform’s shutdown,” Associated Press, Feb. 2024, accessed: 2026-01-13. [Online]. Available: https://apnews.com/article/1f782388be6445de8e592ba1c71d045a [14] “India top court rejects plea for 100% cross-verification of electronic votes,” Reuters, Apr. 2024, accessed: 2026-01-13. [Online]. Available: https://www.reuters.com/world/india/india-top-court-rejectsplea-100-cross-verification-electronic-votes-2024-04-26/ [15] “Bangladesh election: Sheikh hasina wins fourth consecutive term amid boycott and violence,” The Guardian, Jan. 2024, accessed: 2026-01-13. [Online]. Available: https://www.theguardian.com/world/2024/jan/07/bangladesh-electionsheikh-hasina-wins-fourth-consecutive-term-amid-boycott-and-violence [16] “Bangladesh’s prime minister wins reelection in vote boycotted by opposition,” Associated Press, Jan. 2024, accessed: 2026-0113. [Online]. Available: https://apnews.com/article/bangladesh-electionprime-minister-hasina-wins-65b60720a19679870be6b54d5c5eff3e
[17] “Nigeria election results: Delays in uploading polling station results raise concerns,” Associated Press, Feb. 2023, accessed: 2026-01-13. [Online]. Available: https://apnews.com/article/nigeria-election-results-delaysuploading-polling-station-results-4e7fe0bd3f1aab58099debb38f9d7e47 [18] R. Küsters, T. Truderung, and A. Vogt, “Accountability: Definition and relationship to verifiability,” in ACM CCS, 2010. [19] W. Jamroga, “Pretty good strategies for benaloh challenge,” in Electronic Voting, 2023. [20] J. Mueller, B. Pejo, and I. Pryvalov, “Devos: Deniable yet verifiable vote updating,” Cryptology ePrint Archive, 2023. [21] C. Dwork, “Differential privacy,” ICALP, 2006. [22] K. Nissim, S. Raskhodnikova, and A. Smith, “Smooth sensitivity and sampling in private data analysis,” STOC, 2007. [23] P. Y. A. Ryan, P. B. Rønne, and V. Iovino, “Selene: Voting with transparent verifiability and coercion-mitigation,” in Financial Cryptography, 2016. [24] B. Adida, “Helios: web-based open-audit voting,” in Proceedings of the 17th Conference on Security Symposium, ser. SS’08. USA: USENIX Association, 2008, p. 335–348. [25] S. Damle, S. Gujar, and M. H. Moti, “Fasten: Fair and secure distributed voting using smart contracts,” in 2021 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), 2021, pp. 1–3. [26] P. Y. A. Ryan, D. Bismark, J. Heather, S. Schneider, and Z. Xia, “PrÊt À voter: a voter-verifiable voting system,” IEEE Transactions on Information Forensics and Security, vol. 4, no. 4, pp. 662–673, 2009. [27] N. Huber, R. Kuesters, T. Krips, J. Liedtke, J. Mueller, D. Rausch, P. Reisert, and A. Vogt, “Kryvos: Publicly tally-hiding verifiable e-voting,” Cryptology ePrint Archive, Paper 2022/1132, 2022. [Online]. Available: https://eprint.iacr.org/2022/1132 [28] J. Mueller, B. Pejo, and I. Pryvalov, “DeVoS: Deniable yet verifiable vote updating,” Cryptology ePrint Archive, Paper 2023/1616, 2023. [Online]. Available: https://eprint.iacr.org/2023/1616 [29] J. Bootle and J. Groth, “Efficient batch zero-knowledge arguments for low degree polynomials,” Cryptology ePrint Archive, Paper 2018/045, 2018. [Online]. Available: https://eprint.iacr.org/2018/045 [30] T. P. Pedersen, “Non-interactive and information-theoretic secure verifiable secret sharing,” in Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, ser. CRYPTO ’91. Berlin, Heidelberg: Springer-Verlag, 1991, p. 129–140. [31] A. Kiayias, A. Kuldmaa, H. Lipmaa, J. Siim, and T. Zacharias, “On the security properties of e-voting bulletin boards,” in Security and Cryptography for Networks, D. Catalano and R. De Prisco, Eds. Cham: Springer International Publishing, 2018, pp. 505–523. [32] J. Groth, “On the size of pairing-based non-interactive arguments,” Cryptology ePrint Archive, Paper 2016/260, 2016. [Online]. Available: https://eprint.iacr.org/2016/260 [33] J.-J. Quisquater, M. Quisquater, M. Quisquater, M. Quisquater, L. C. Guillou, M. A. Guillou, G. Guillou, A. Guillou, G. Guillou, S. Guillou, and T. A. Berson, “How to explain zero-knowledge protocols to your children,” in Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, ser. CRYPTO ’89. Berlin, Heidelberg: Springer-Verlag, 1989, p. 628–631. [34] J. Benaloh, “Simple verifiable elections,” in Proceedings of the USENIX/Accurate Electronic Voting Technology Workshop 2006 on Electronic Voting Technology Workshop, ser. EVT’06. USA: USENIX Association, 2006, p. 5. [35] R. Küsters, T. Truderung, and A. Vogt, “Accountability: definition and relationship to verifiability,” in Proceedings of the 17th ACM Conference on Computer and Communications Security, ser. CCS ’10. New York, NY, USA: Association for Computing Machinery, 2010, p. 526–535. [Online]. Available: https://doi.org/10.1145/1866307.1866366 [36] R. Küsters, T. Truderung, and A. Vogt, “Verifiability, privacy, and coercion-resistance: New insights from a case study,” in 2011 IEEE Symposium on Security and Privacy, 2011, pp. 538–553. [37] E. Rescorla, “The Transport Layer Security (TLS) Protocol Version 1.3,” RFC 8446, Internet Engineering Task Force, Aug. 2018. [Online]. Available: https://datatracker.ietf.org/doc/html/rfc8446 [38] A. Pankova and J. Willemson, “Relations Between Privacy, Verifiability, Accountability and Coercion-Resistance in Voting Protocols,” in Applied Cryptography and Network Security, G. Ateniese and D. Venturi, Eds. Springer International Publishing, 2022, vol. 13269, pp. 313–333. [Online]. Available: https://link.springer.com/10.1007/978-3-031-092343 16
[39] R. Küsters, J. Liedtke, J. Müller, D. Rausch, and A. Vogt, “Ordinos: A Verifiable Tally-Hiding E-Voting System,” in 2020 IEEE European Symposium on Security and Privacy (EuroS&P), 2020, pp. 216–235. [Online]. Available: https://ieeexplore.ieee.org/document/9230368/ [40] P. Chaidos, V. Cortier, G. Fuchsbauer, and D. Galindo, “Beleniosrf: A non-interactive receipt-free electronic voting scheme,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’16. New York, NY, USA: Association for Computing Machinery, 2016, p. 1614–1625. [Online]. Available: https://doi.org/10.1145/2976749.2978337 [41] A. Kiayias, T. Zacharias, and B. Zhang, “End-to-End Verifiable Elections in the Standard Model,” in Advances in Cryptology EUROCRYPT 2015, E. Oswald and M. Fischlin, Eds. Springer Berlin Heidelberg, 2015, vol. 9057, pp. 468–498. [Online]. Available: http://link.springer.com/10.1007/978-3-662-46803-6 16 [42] A. Fraser, E. A. Quaglia, and B. Smyth, “A critique of game-based definitions of receipt-freeness for voting,” in Provable Security: 13th International Conference, ProvSec 2019, Cairns, QLD, Australia, October 1–4, 2019, Proceedings. Berlin, Heidelberg: Springer-Verlag, 2019, p. 189–205. [Online]. Available: https://doi.org/10.1007/978-3030-31919-9 11 [43] D. Mestel, J. Müller, and P. Reisert, “How efficient are replay attacks against vote privacy? a formal quantitative analysis,” in 2022 IEEE 35th Computer Security Foundations Symposium (CSF), 2022, pp. 179–194. [44] T. Okamoto, “Receipt-free electronic voting schemes for large scale elections,” in Security Protocols, B. Christianson, B. Crispo, M. Lomas, and M. Roe, Eds. Springer Berlin Heidelberg, 1998, vol. 1361, pp. 25–35, series Title: Lecture Notes in Computer Science. [Online]. Available: http://link.springer.com/10.1007/BFb0028157