@misc{engineering2026sovereign,
  author = {System9 Engineering},
  title = {SOVEREIGN: USENIX Security Submission},
  year = {2026},
  url = {https://system9.ai/research/sovereign-usenix-submission},
  howpublished = {\\url\{https://system9.ai/research/sovereign-usenix-submission\}},
  note = {Draft, in preparation}
}

SOVEREIGN: Distributed End-to-End Verifiable Voting with Entity Contracts and Threshold Homomorphic Tallying

Abstract

End-to-end verifiable (E2E-V) voting systems must simultaneously provide ballot secrecy, individual and universal verifiability, eligibility enforcement, and coercion resistance. Existing systems -- ElectionGuard, Helios, and Belenios -- achieve subsets of these properties but share fundamental limitations: centralized trust within a single administrative domain, support for only one or two election types, procedural rather than machine-enforced governance, and dependence on persistent network connectivity. We present SOVEREIGN, a distributed E2E-V voting system that addresses all four limitations. SOVEREIGN distributes trust across independent cryptographic cells organized in a three-level hierarchy (nodes, service groups, cells), each representing a sovereign jurisdiction. Ballots are encrypted with Paillier homomorphic encryption, tallied without decryption via modular multiplication, and decrypted through threshold ceremonies using the Damgard-Jurik Delta scheme where the private key is never assembled. Voter anonymity is achieved through RSA blind signatures; ballot validity is proven via disjunctive Sigma protocols with Fiat-Shamir; coercion resistance is provided through HMAC-based JCJ credentials. Elections are governed by formal entity contracts following the AAMAS 2026 seven-tuple model, providing machine-enforced rules for ballot format, temporal bounds, and success criteria. SOVEREIGN supports seven election types under a unified cryptographic framework and operates in disconnected environments via delay-tolerant networking. We implement the system in Python with 122 passing tests across 17 files, demonstrate correct end-to-end operation, and provide performance benchmarks showing sub-second per-voter cryptographic cost with tallying latency independent of election size.

1. Introduction

1.1 The Problem

Democratic decision-making -- from national elections to corporate governance to military field votes -- requires systems that simultaneously guarantee ballot secrecy, verifiable integrity, and eligibility enforcement. These properties are mutually antagonistic: secrecy demands that individual votes remain hidden, while verifiability demands that anyone can audit the result. Satisfying both simultaneously is one of the hardest problems in applied cryptography.

The challenge is compounded in distributed settings. Federal elections span states that do not share infrastructure or administrative authority. International organizations span countries with different legal frameworks. Military operations span disconnected tactical networks where connectivity is intermittent or absent. Corporate governance spans divisions with competing interests. In all these contexts, no single entity should be trusted to operate the entire election system, yet the system must produce a single, universally verifiable result. Existing E2E-V systems assume a unified administrative domain and persistent network connectivity -- assumptions that exclude precisely the deployments where cryptographic voting is most needed.

1.2 Limitations of Existing Approaches

The past two decades have produced landmark E2E-V systems, each with structural constraints:

• ElectionGuard [6] integrates E2E-V with existing election hardware via ElGamal encryption and threshold key management. It supports only plurality voting, operates within a single administrative domain, does not address coercion, and requires persistent connectivity.
• Helios [1] pioneered web-based open-audit elections with browser-side encryption. It lacks threshold decryption (a single party holds the key), does not address coercion resistance, and trusts the server with encryption randomness if the browser is compromised.
• Belenios [11] extends Helios with threshold trustees and UC-framework proofs. It supports plurality and majority judgment but not ranked-choice, approval, weighted, or consensus voting. It operates on centralized infrastructure and requires persistent connectivity.
• Blockchain approaches [20] offer append-only ledgers but expose encrypted ballots permanently (enabling harvest-now-decrypt-later attacks), carry high computational overhead, and provide no mechanism for ballot secrecy beyond encryption strength over an indefinite horizon.

No existing system supports distributed multi-jurisdictional trust, multiple election types, machine-enforced governance, or disconnected operation. Table 1 summarizes these gaps.

Limitation	ElectionGuard	Helios	Belenios	Blockchain
Centralized trust	Yes	Yes	Partial (threshold)	Distributed but transparent
Single election type	Plurality only	Plurality only	Plurality + majority judgment	Application-dependent
Procedural governance	Yes	Yes	Yes	Smart contract (fragile)
Network required	Yes	Yes	Yes	Yes (consensus)

1.3 Our Contributions

We make the following contributions:

1. Distributed E2E-V architecture. We present the first E2E-V voting system where independent nodes (jurisdictions) operate sovereign elections with cross-node verification. Trust is distributed across cells via threshold cryptography such that no single cell, service group, or jurisdiction holds sufficient key material to decrypt.

2. Entity contract governance. We integrate formal entity contracts following the AAMAS 2026 seven-tuple model (I, O, S, R, T, Phi, Psi) as machine-enforced election governance. Contracts specify ballot format, tally algorithm, temporal bounds, and success criteria with cryptographic attestation of compliance -- replacing procedural checklists with verifiable computation.

3. Seven election types under unified cryptography. We implement simple majority, super majority, ranked choice, approval, weighted, consensus, and referendum voting using a shared Paillier encryption and homomorphic tallying framework. Only the tallying algorithm and threshold conditions vary per type.

4. Coercion resistance via HMAC-based JCJ. We implement a simplified JCJ protocol using HMAC-SHA-256 credentials that are computationally indistinguishable from fake credentials without the authority key, enabling voters to comply with coercers without affecting the real tally.

5. Tactical disconnected operation. All per-ballot cryptographic operations (encryption, ZK proof generation, token verification) are local. Only tallying and threshold decryption require multi-cell coordination. Cells operate disconnected during voting and synchronize via delay-tolerant networking.

6. Implementation and evaluation. We provide a complete implementation with 122 tests across 17 files, end-to-end integration verification, and performance benchmarks demonstrating feasibility for elections ranging from small boards to large-scale deployments.

1.4 Scope and Non-Goals

SOVEREIGN is a research prototype demonstrating the feasibility of distributed E2E-V voting with formal contract governance. It is not production-ready election infrastructure. We do not claim to solve the trusted device problem (common to all electronic voting systems), nor do we provide UC-framework security proofs (which would offer stronger composability guarantees). We do not address voter authentication (how a person proves they are who they claim to be) -- this is orthogonal to the cryptographic voting protocol and is handled by the platform's entity management system. We do not address accessibility, usability, or voter education, which are critical for real deployments but outside the scope of this cryptographic contribution.

1.5 Paper Organization

Section 2 reviews background and related work. Section 3 defines the system model and threat model. Section 4 describes the cryptographic protocols. Section 5 details election governance via entity contracts. Section 6 provides security analysis with reduction proofs. Section 7 reports implementation, performance, and comparison. Section 8 discusses limitations. Section 9 addresses ethical considerations. Section 10 concludes.

2. Background and Related Work

2.1 End-to-End Verifiable Voting

An E2E-V system provides three guarantees: (1) individual verifiability -- each voter can confirm their ballot was recorded as cast; (2) universal verifiability -- any observer can confirm the tally correctly reflects recorded ballots; and (3) ballot secrecy -- no observer can determine how any individual voted. The tension between verifiability (which requires transparency) and secrecy (which requires opacity) is resolved through homomorphic encryption: ballots are encrypted so individual votes are hidden, but the homomorphic property allows computing the tally over ciphertexts. The result is decrypted via threshold ceremonies, ensuring no single party can decrypt individual ballots.

2.2 ElectionGuard

ElectionGuard [6] is Microsoft's open-source E2E-V toolkit designed for integration with existing election hardware. It uses ElGamal encryption over an elliptic curve group with additive homomorphic tallying and threshold key management via Shamir secret sharing with Lagrange interpolation. Ballot proofs use the Chaum-Pedersen protocol. ElectionGuard's primary contribution is its deployment model: an add-on verification layer for existing voting machines. Its limitations are its restriction to plurality voting, operation within a single administrative domain, lack of coercion resistance, and no support for disconnected environments.

2.3 Helios

Helios [1] pioneered web-based open-audit elections. Voters encrypt ballots in the browser using JavaScript and verify them on a public bulletin board. Helios uses ElGamal with homomorphic tallying and provides individual and universal verifiability. However, it does not support threshold decryption (a single party holds the key), does not address coercion resistance, and the server knows the encryption randomness if the browser is compromised, meaning ballot secrecy depends on server honesty.

2.4 Belenios

Belenios [11] extends Helios with a distributed trust model using threshold ElGamal encryption with multiple trustees. It provides formal security in the Universal Composability (UC) framework and supports a "Belenios-RF" variant with partial receipt-freeness through re-encryption. Belenios is the closest system to SOVEREIGN in security ambition. Its advantages include UC proofs (stronger than SOVEREIGN's game-based arguments) and Coq-verified implementations. Its limitations include support for only plurality and majority judgment, centralized infrastructure, and no disconnected operation.

2.5 Blockchain Approaches

Blockchain-based voting systems [20, 25] exploit append-only ledgers as natural bulletin boards. However, public blockchains expose encrypted ballots to all participants indefinitely, making ballot secrecy dependent on encryption security for the lifetime of the chain -- a critical vulnerability as quantum computing advances. The computational cost of consensus is high and poorly suited to bursty election access patterns. Smart contract bugs, which have caused catastrophic failures in financial applications, carry unacceptable risk in elections. SOVEREIGN uses an HMAC hash chain on a replicated bulletin board, providing tamper-evidence without blockchain overhead.

2.6 Other E2E-V Systems

Pret a Voter [24] achieves E2E-V through physical ballot forms with randomized candidate orderings and onion-layer decryption. It provides strong receipt-freeness through physical ballot destruction but requires specialized printing infrastructure and cannot operate in disconnected environments. Cramer, Gennaro, and Schoenmakers [10] present a multi-authority election scheme with optimal efficiency and information-theoretic privacy against authority coalitions. Their distributed trust model is closer to SOVEREIGN's than single-authority systems, but they do not address disconnected operation, multiple election types, or machine-enforced governance. Kiayias, Zacharias, and Zhang [16] achieve E2E-V in the standard model (without random oracles), a stronger theoretical result than SOVEREIGN's ROM-based proofs. Their construction uses more complex cryptographic machinery; SOVEREIGN prioritizes implementation simplicity and deployment flexibility.

2.7 Entity Contracts for Autonomous Systems

The AAMAS 2026 seven-tuple contract model [5] specifies agreements between autonomous agents: C = (I, O, S, R, T, Phi, Psi), where I is input specification, O is output specification, S is required skills, R is resource constraints, T is temporal constraints, Phi is success criteria, and Psi is termination conditions. SOVEREIGN applies this model to elections: the election authority proposes a contract, the tallying agent accepts it, and compliance is verified cryptographically. This replaces the procedural compliance model (human-enforced checklists) used by all existing E2E-V systems with formally verifiable governance.

3. System Model

3.1 Architecture

SOVEREIGN maps jurisdictional hierarchy to a three-level topology:

Level	Example (Federal)	Example (Corporate)	Role
Node	State	Division	Sovereign jurisdiction; logical, spans physical infrastructure
Service Group	County	Department	Administrative district; replication boundary
Cell	Precinct	Office	Physical deployment unit; fundamental trust boundary

Each cell runs its own SOVEREIGN services, databases, and cryptographic operations. Compromising one cell does not compromise others. Key shares are distributed across cells so that no single cell or service group holds enough shares to decrypt. Encrypted ballots are collected locally and synchronized to a shared bulletin board.

The mapping is flexible: a board vote may use a single cell; a national election may use thousands of cells across hundreds of service groups and dozens of nodes.

Sovereignty invariant. Each cell operates autonomously during the voting phase: it collects encrypted ballots, verifies ZK proofs, and records entries to its local bulletin board segment without contacting other cells. This is critical for disconnected operation: a cell in a forward-deployed military unit or a disaster-response camp continues accepting votes even when network connectivity to other cells is lost. Synchronization occurs asynchronously -- when connectivity is restored, encrypted ballots are replicated to the shared bulletin board via the platform's delay-tolerant networking layer. Only the tallying and threshold decryption phases require multi-cell coordination, and even then, only M of N share holders must be reachable, not all N.

Bulletin board. The bulletin board is an append-only public log replicated across cells. Each entry is protected by an HMAC hash chain: entry_i.hmac incorporates entry_{i-1}.hmac, creating a tamper-evident chain where modifying or deleting any entry is detectable by recomputing the chain from the genesis entry. The board stores election definitions, encrypted ballots with ZK proofs and anonymous tokens, encrypted tallies, decryption results, and signed attestations. Any party -- voter, observer, or auditor -- can read the board and independently verify the election.

3.2 Threat Model

Adversary capabilities. We consider a computationally bounded (PPT) adversary A with:

• Network observation: A observes all traffic and the public bulletin board.
• Threshold corruption: A corrupts up to M-1 of N key share holders, learning their shares and controlling their behavior.
• Cell compromise: A compromises individual cells but cannot compromise cells holding M or more total key shares.
• Voter coercion: A coerces voters, demanding specific votes and evidence of compliance. A observes the voter's interaction but cannot prevent ballot casting.
• Registration observation: A observes voter registration but cannot compromise the election authority's signing or HMAC keys.

Adversary limitations. A cannot break the Decisional Composite Residuosity (DCR) assumption, forge RSA signatures, find SHA-256 collisions, or distinguish HMAC-SHA-256 from a random function.

Trust assumptions.

ID	Assumption	Consequence if Violated
T1	Honest registration authority (one credential per eligible voter)	Eligibility fails
T2	Honest threshold (at least M of N key holders honest)	Ballot secrecy fails
T3	Random oracle model (SHA-256 for Fiat-Shamir)	ZK soundness weakens
T4	Append-only bulletin board (HMAC hash chain)	Universal verifiability fails
T5	Voter device integrity (correct encryption)	Cast-as-intended fails

3.3 Security Properties

Property	Informal Statement	Formal Basis
Ballot secrecy	No PPT adversary determines any individual vote	IND-CPA under DCR (Theorem 1)
Individual verifiability	Voter confirms ballot recorded as cast	Collision resistance of SHA-256
Universal verifiability	Anyone verifies tally correctness from bulletin board	ZK soundness + homomorphic determinism
Eligibility	Only authorized voters' ballots are counted	RSA unforgeability + one-token policy
Coercion resistance	Coerced voter complies without affecting real tally	PRF security of HMAC-SHA-256

4. Cryptographic Protocol

4.1 Overview

The SOVEREIGN protocol proceeds in five phases:

1. Setup. The election authority generates a Paillier keypair (pk, sk) at the configured security level (2048-bit for production). The private key sk is immediately split into N shares with threshold M via Shamir sharing over the integers. Each share is distributed to a designated key share holder on a separate cell. The original sk is securely erased -- it never exists on any machine after splitting. The authority generates an RSA keypair for blind signatures and creates the election contract. The election definition (type, races, choices, temporal bounds, contract_id) is published to the bulletin board.

2. Registration. For each eligible voter, the eligibility checker applies four filters in sequence: duplicate ballot guard, entity type restriction, explicit allow-list, and live entity lookup. All four must pass. For anonymous elections, the voter generates a random 256-bit token, blinds it with a random factor, sends the blinded value to the authority, receives a blind RSA signature, and unblinds to obtain a valid signed token. The authority never sees the original token. For coercion-resistant elections, the authority additionally issues a real JCJ credential; the voter may generate fake credentials for use under duress.

3. Voting. For each race and choice, the voter encrypts their selection (0 or 1) using Paillier with fresh randomness. For each encrypted selection, the voter generates a ZK proof demonstrating the ciphertext encrypts 0 or 1. The encrypted selections, ZK proofs, anonymous token, and token signature are assembled into a ballot and submitted to the ballot recorder, which writes it to the append-only journal with an HMAC integrity signature. The voter receives a receipt containing (ballot_id, SHA-256(encrypted_payload), timestamp) -- the receipt reveals nothing about the voter's choice.

4. Tallying. After the election closes, the homomorphic tally engine verifies each ballot's ZK proof and anonymous token, rejecting invalid ballots. For each race and choice, the engine multiplies all valid ciphertexts: T_j = product(c_i) mod n^2, producing E(count_j) without decryption. Encrypted tallies are published to the bulletin board.

5. Decryption and verification. Each of M share holders computes a partial decryption on their own machine -- the share value never leaves the holder's machine. The combiner collects M partial decryptions and recovers the plaintext count via Lagrange interpolation in the exponent. Voters verify their receipts against the bulletin board. Observers verify all ZK proofs, recompute the homomorphic sum, and check decryption proofs. The result attestation generator creates a signed attestation binding the result hash, journal hash chain, and contract_id.

4.2 Paillier Homomorphic Encryption

We use the Paillier cryptosystem [17] rather than the more common ElGamal for three reasons: (1) Paillier's additive homomorphism maps directly to vote counting -- the product of encrypted 0/1 values decrypts to the count, whereas ElGamal requires encoding votes as exponents; (2) Paillier decryption is deterministic, simplifying threshold combination; (3) Paillier's security rests on the DCR assumption, which is well-studied and at least as hard as factoring.

KeyGen(lambda):
  p, q <- RandomPrime(lambda/2)
  n = pq,  g = n + 1
  lambda_val = lcm(p-1, q-1)
  mu = L(g^{lambda_val} mod n^2)^{-1} mod n   where L(x) = (x-1)/n
  return pk = (n, n^2, g), sk = (lambda_val, mu)

Encrypt(pk, m):
  r <- Z*_n
  c = (1 + n*m) * r^n mod n^2
  return (c, r)

Decrypt(sk, c):
  m = L(c^{lambda_val} mod n^2) * mu mod n
  return m

HomAdd(pk, c1, c2):
  return c1 * c2 mod n^2       // Decrypt(HomAdd(E(m1), E(m2))) = m1 + m2

Correctness. The simplification g^m = 1 + nm mod n^2 holds because g = n+1 and higher binomial terms vanish modulo n^2. The homomorphic property follows from (1+nm1)(1+nm2) = 1+n*(m1+m2) mod n^2 (the n^2m1m2 term vanishes). Decryption correctness follows from Carmichael's theorem and Hensel lifting.

Security. Paillier is IND-CPA secure under DCR [17]: given n, the distributions {x^n mod n^2 : x <- Z_{n^2}} and {(1+n)^m * x^n mod n^2 : m <- Z_n, x <- Z_{n^2}} are computationally indistinguishable. This directly implies E(0) and E(1) are indistinguishable, so individual encrypted ballots reveal no information about the underlying vote. We chose 2048-bit keys for production (128-bit security per NIST), with 1024-bit keys for development and testing only.

4.3 Anonymous Voter Tokens

RSA blind signatures [8] decouple voter identity from ballot identity:

Blind(token, pk_auth):
  h = SHA-256(token) mod n
  r <- Z*_n                           // random blinding factor
  blinded = h * r^e mod n
  return (blinded, r)

Sign(blinded, sk_auth):
  return blinded^d mod n

Unblind(blinded_sig, r, n):
  sig = blinded_sig * r^{-1} mod n    // standard RSA signature on h
  return sig

Verify(token, sig, pk_auth):
  return sig^e mod n == SHA-256(token) mod n

Unlinkability. For any fixed token, blinded = h * r^e mod n is uniformly distributed over Z*_n (multiplication by r^e is a bijection), so the authority gains zero information about the token during signing. The signed token cannot be correlated with the signing session.

Unforgeability. Under the RSA assumption, no PPT adversary produces a valid (token, sig) pair without querying the signing oracle. This prevents ballot stuffing: an adversary who has not interacted with the authority cannot create valid tokens, and the authority issues at most one token per eligible voter.

One-token-per-voter policy. The authority maintains a record of which voters have received blind signatures (indexed by voter identity, not by token value -- the token remains hidden). The authority refuses to sign more than once per voter. Combined with duplicate token detection during tallying (the bulletin board rejects ballots with previously-seen tokens), this ensures each eligible voter casts at most one counted ballot.

4.4 Zero-Knowledge Ballot Proofs

Voters must prove their encrypted ballot contains 0 or 1 without revealing which, preventing ballot stuffing. We use a disjunctive Sigma protocol (OR-proof) made non-interactive via Fiat-Shamir [13].

Protocol. Given c = E(b, r) for b in {0, 1}, define c_0 = c (encrypts 0 hypothesis) and c_1 = c * g^{-1} mod n^2 (encrypts 1 hypothesis). If b = beta, then c_beta = r^n mod n^2 and the prover knows the n-th root. The prover generates a real proof for the true branch and simulates the false branch:

Prove(pk, b, c, r):
  // For the FALSE branch: choose e_sim, z_sim; compute a_sim = z_sim^n * c_b^{-e_sim}
  // For the TRUE branch: choose w; compute a = w^n mod n^2
  // Fiat-Shamir: e_total = H("SOVEREIGN-ZK-v1" || n || g || c || a_0 || a_1)
  // Split: e_true = e_total - e_sim;  z_true = w * r^{e_true} mod n
  return (a_0, a_1, e_0, e_1, z_0, z_1)

Verify(pk, c, pi):
  Check: (e_0 + e_1) mod 2^256 = H("SOVEREIGN-ZK-v1" || n || g || c || a_0 || a_1)
  Check: z_0^n = a_0 * c_0^{e_0} mod n^2
  Check: z_1^n = a_1 * c_1^{e_1} mod n^2

Security. Zero-knowledge holds because a simulator can produce indistinguishable transcripts by programming the random oracle: for both branches, the simulator freely chooses (e, z) and derives a to satisfy the verification equation, producing transcripts identically distributed to real proofs. Soundness follows from special soundness of Sigma protocols: two accepting transcripts for the same commitment (a_0, a_1) with different challenges yield the n-th root of c_0 or c_1. If c encrypts some m not in {0, 1}, then neither c_0 nor c_1 is an n-th residue, and the prover cannot produce valid responses for either branch. By the soundness of the Fiat-Shamir transform in the random oracle model [18], the non-interactive proof is sound. Domain separation ("SOVEREIGN-ZK-v1") prevents cross-protocol attacks where a proof generated in one context is replayed in another.

Efficiency. The proof consists of 6 elements: (a_0, a_1, e_0, e_1, z_0, z_1). At 1024-bit Paillier, the proof is approximately 768 bytes. Verification requires 4 modular exponentiations in Z_{n^2} and one hash evaluation, taking 103ms at 1024-bit keys. Proof verification is independent across ballots, enabling parallel verification across cells during tallying.

4.5 Threshold Decryption

The Paillier private key is split into N shares via Shamir secret sharing over the integers. Any M shares enable decryption without ever assembling the full key, using the Damgard-Jurik Delta scheme [12]:

Split(sk, N, M):
  f(x) = lambda_val + sum_{i=1}^{M-1} a_i * x^i    // a_i <- [0, n*2^128)
  share_i = (i, f(i))     // evaluated over integers, no modular reduction

PartialDecrypt(share_i, c):
  Delta = N!
  partial_i = c^{2 * Delta * s_i} mod n^2
  return partial_i

Combine({partial_1, ..., partial_M}):
  Delta = N!
  mu_i = Delta * prod_{j != i} (0 - x_j) / (x_i - x_j)   // exact integer division
  combined = prod_i (partial_i ^ mu_i) mod n^2
  l_val = (combined - 1) / n
  m = l_val * (2 * Delta^2)^{-1} * mu mod n
  return m

Why sharing over integers? Standard Shamir sharing uses a finite field F_p where Lagrange interpolation is exact. However, threshold Paillier decryption applies Lagrange combination in the exponent of c^{s_i} mod n^2. Computing modular inverses in the exponent requires knowing phi(n^2), which is secret (equivalent to factoring n). The Delta = N! trick ensures all Lagrange denominators divide N!, making all divisions exact over the integers.

Correctness sketch. The combination yields c^{2Delta^2lambda_val} because the exponent sum is 2Delta * sum(s_i * mu_i) = 2Delta * Delta * f(0) = 2Delta^2lambda_val (by Lagrange interpolation). Applying L gives 2Delta^2mlambda (by standard Paillier decryption). Dividing by scale = 2Delta^2 and multiplying by mu = lambda^{-1} recovers m. The modular inverse of scale is computable because Delta = N! is public and mu is part of the public key.

Security. M-1 or fewer shares reveal no information about lambda_val (statistical security within 2^{-128} from uniform, ensured by the large coefficient bound n2^{128}). Partial decryptions are deterministic functions of shares; extracting s_i from partial_i requires solving the discrete logarithm in Z_{n^2}, at least as hard as factoring n.

Multi-cell distribution. In a deployment with N = 5 share holders across 5 cells, each cell stores exactly one share. An adversary must compromise M cells to reconstruct the key. By distributing share holders across service groups (e.g., different counties or geographic regions), SOVEREIGN ensures that localized attacks (compromising all machines in one data center) are insufficient for decryption. This is the core of SOVEREIGN's distributed trust model and the primary architectural difference from ElectionGuard and Helios, where key material is concentrated in a single administrative domain.

4.6 Coercion-Resistant Credentials

SOVEREIGN implements a simplified JCJ protocol [15] using HMAC-SHA-256:

IssueReal(voter_id, authority_key):
  credential_id = random_hex(32)
  token = random_hex(32)
  mac = HMAC-SHA-256(authority_key, credential_id || ":" || token)
  return (credential_id, token, mac)

GenerateFake(voter_id):
  credential_id = random_hex(32)
  token = random_hex(32)
  fake_key = random_hex(32)
  mac = HMAC-SHA-256(fake_key, credential_id || ":" || token)
  return (credential_id, token, mac)

Filter(credentials, authority_key):
  // During tallying: only count ballots where HMAC verifies under authority_key
  return [c for c in credentials if HMAC-SHA-256(authority_key, c.id || ":" || c.token) == c.mac]

Indistinguishability. Both real and fake credentials are tuples (random_id, random_token, 256-bit_mac). Without the authority key, HMAC output is computationally indistinguishable from random (PRF security). A fake credential's HMAC (computed with a random key) is also indistinguishable from random. No PPT adversary can distinguish real from fake.

Tally-phase filtering. The authority validates credentials by recomputing the HMAC; only real credentials pass. The count of discarded fakes is not revealed, preventing the coercer from inferring whether the voter complied.

Trade-offs versus public-key JCJ. The original JCJ protocol [15] uses public-key encryption for credential hiding, providing information-theoretic security against the coercer (even with unlimited computation, the coercer cannot distinguish credentials). Our HMAC approach provides only computational security (the coercer cannot distinguish without breaking HMAC-SHA-256). However, the HMAC approach is significantly simpler to implement, requires no additional public-key infrastructure, and is sufficient for the threat models SOVEREIGN targets. A threshold HMAC construction would distribute the authority key across multiple parties, addressing the single-point-of-compromise limitation.

5. Election Governance via Entity Contracts

5.1 The AAMAS 2026 Model

The seven-tuple contract C = (I, O, S, R, T, Phi, Psi) formally specifies an agreement between autonomous agents [5]. In SOVEREIGN, the election authority proposes a contract and the tallying agent is bound by its terms, with compliance verified automatically and attested cryptographically.

5.2 Election Contract Mapping

Tuple	Election Meaning	Example
I (Input)	Ballot format: required fields, field types, race/choice schema	{ballot_id: str, selections: list[BallotSelection]}
O (Output)	Tally format: guaranteed fields, minimum completeness = 1.0	{race_tallies: list[RaceTally], total_voted: int}
S (Skills)	Tallying algorithm the executing agent must implement	"tally:ranked_choice"
R (Resources)	Max ballot operations = number of eligible voters	max_api_calls = 100
T (Temporal)	Election open/close window	valid_from: 2026-01-01, valid_until: 2026-01-31
Phi (Success)	100% ballot inclusion, quorum satisfaction	min_completeness = 1.0, quorum_pct = 0.5
Psi (Termination)	Actions on exception: timeout extends, violation escalates	timeout_action = "extend"

5.3 Machine-Enforced Governance

Existing E2E-V systems enforce election rules through procedural compliance: human-readable policy documents and manual checklists. This model has two weaknesses. First, procedural compliance is unverifiable after the fact -- an auditor cannot cryptographically prove that a procedure was followed. Second, procedural compliance does not compose: when multiple jurisdictions cooperate, each may follow different procedures with no formal mechanism for verifying cross-jurisdictional consistency.

SOVEREIGN's entity contracts address both weaknesses. The contract is published to the bulletin board during setup, creating a public commitment to the election rules. During tallying, the contract enforcement layer automatically verifies compliance: ballots outside the temporal window are rejected by the contract, not just by application logic. After certification, the result attestation includes a cryptographic binding to the contract, enabling any auditor to verify that the declared rules were applied to the declared inputs to produce the declared output. This shifts election governance from "trust that procedures were followed" to "verify that the contract was satisfied."

Multi-jurisdictional contracts. In a distributed election spanning multiple nodes, each node operates under the same contract (published on the shared bulletin board). Contract consistency is verifiable: any observer can compare the contract used by each node against the published version. Discrepancies indicate either a bug or an attack and trigger investigation via the Psi termination conditions. This is particularly important for federal elections where states must apply uniform ballot formats and tallying algorithms despite operating independently.

Contract composition. For elections with multiple races (e.g., a general election with federal, state, and local contests), SOVEREIGN supports multiple contracts -- one per race -- within a single election. Each contract specifies the tallying algorithm, success criteria, and temporal bounds for its race. The election manager enforces all contracts independently, and the result attestation covers all races, creating a unified cryptographic binding across the entire election.

6. Security Analysis

We analyze SOVEREIGN's security through reduction-based arguments. Each property is reduced to a standard cryptographic assumption. The full formal treatment, including game definitions with challenger/adversary interactions, appears in the companion security specification [anonymous, available for review].

6.1 Ballot Secrecy

Theorem 1. If the DCR assumption holds for Paillier with security parameter lambda, then SOVEREIGN provides ballot secrecy (IND-CPA) against any PPT adversary A corrupting at most M-1 key share holders.

Proof. We reduce ballot secrecy to DCR. Assume A breaks ballot secrecy with non-negligible advantage epsilon. We construct B that breaks DCR.

Construction. B receives DCR challenge (n, y) where y is either a random n-th residue (y = r^n mod n^2) or a random element of Z*_{n^2}. B sets pk = (n, n^2, n+1) and simulates the election for A:

1. When A requests ballot encryptions, B returns E(m) = (1+nm) * r^n mod n^2 using fresh random r. These are valid Paillier ciphertexts.

2. When A submits challenge (b_0, b_1), B computes c* = (1 + nb_0) * y mod n^2. If y is an n-th residue (y = r^n), then c = E(b_0, r) -- a valid encryption of b_0. If y is random, c* is computationally indistinguishable from a random element of Z*_{n^2}.

3. B generates ZK proof pi* using the simulator (which exists by the zero-knowledge property).

4. When A outputs beta', B outputs 1 if beta' = 0, else 0.

Analysis. If y is an n-th residue, B perfectly simulates beta = 0. If y is random, A's advantage is 0. Therefore:

Adv^DCR_B = |Pr[B(residue) = 1] - Pr[B(random) = 1]| = Adv^BS_A / 2

Since Adv^DCR_B is negligible by assumption, Adv^BS_A is negligible.

Composition with threshold. M-1 corrupted shares reveal no information about lambda_val (statistical security of integer Shamir sharing within 2^{-128} of uniform). Partial decryptions are deterministic functions of shares, adding no advantage. The reduction holds even with M-1 known shares.

Composition with ZK proofs. The simulated OR-proof branch is identically distributed to the real branch; the Fiat-Shamir transform preserves this in the random oracle model.

Composition with blind signatures. The blinding factor makes the signed message uniformly distributed, breaking voter-ballot linkage.

The overall advantage is bounded by: Adv^BS_A <= 2 * Adv^DCR + Adv^ZK_sim + negl(lambda). All terms are negligible.

6.2 Individual Verifiability

Claim. SOVEREIGN provides individual verifiability under the collision resistance of SHA-256.

Proof sketch. After casting, the voter receives receipt R = (ballot_id, SHA-256(encrypted_payload)). The encrypted ballot is published to the bulletin board. The voter verifies that the published ballot's hash matches their receipt. Replacing the ballot requires finding p' such that SHA-256(p') = SHA-256(encrypted_payload), which requires a collision. Deleting the ballot causes receipt verification to fail (no matching ballot_id).

6.3 Universal Verifiability

Claim. SOVEREIGN provides universal verifiability under ZK soundness, homomorphic determinism, and decryption correctness.

Proof sketch. Any observer verifies by: (1) checking each ballot's ZK proof (soundness ensures encryption of 0 or 1); (2) verifying each anonymous token against the authority's RSA public key (unforgeability ensures only authorized tokens); (3) recomputing the homomorphic sum and comparing with the published encrypted tally (deterministic modular arithmetic detects any discrepancy); (4) verifying the decryption proof; (5) checking ballot count consistency. If all checks pass, the tally is correct with overwhelming probability.

6.4 Eligibility

Claim. SOVEREIGN provides eligibility verifiability under RSA unforgeability and the honest registration assumption (T1).

Proof sketch. Every counted ballot must contain a valid blind RSA signature on its anonymous token. By RSA unforgeability, tokens cannot be forged without the authority's signing key. The authority issues at most one token per eligible voter (T1). Duplicate token detection prevents double-voting. The four-layer eligibility checker (duplicate guard, type restriction, allow-list, live lookup) ensures only eligible entities receive tokens.

6.5 Coercion Resistance

Claim. SOVEREIGN provides coercion resistance under PRF security of HMAC-SHA-256.

Proof sketch. A coerced voter uses a fake credential (HMAC computed with a random key). Without the authority key, both real and fake HMAC outputs are computationally indistinguishable from random (PRF property). An adversary distinguishing real from fake can be directly transformed into a PRF distinguisher: the reduction queries its oracle (either HMAC with authority key or a random function) and uses the response as the credential MAC. The adversary's advantage equals the distinguisher's advantage, which is negligible.

Note on receipt-freeness. SOVEREIGN provides coercion resistance through the JCJ mechanism but does not provide full receipt-freeness. A voter who reveals the randomness used in Paillier encryption can prove to a third party how they voted. The JCJ mechanism mitigates this: even if the voter proves a vote was cast with a specific credential, the coercer cannot verify whether the credential is real. Full receipt-freeness would require additional mechanisms such as re-encryption mix-nets or designated verifier proofs.

7. Implementation and Evaluation

7.1 Implementation

SOVEREIGN is implemented in Python as two layers:

Cryptographic layer (7 modules, ~1,313 LOC):

Module	LOC	Function
paillier.py	224	Key generation, encrypt/decrypt, homomorphic ops
blind_signature.py	127	Token generation, blind/sign/unblind/verify
zk_ballot_proof.py	182	Disjunctive Sigma, Fiat-Shamir transform
threshold_keys.py	334	Shamir over integers, partial decrypt, Lagrange combine
homomorphic_tally.py	123	Tally engine with proof/token verification
decryption_ceremony.py	133	Ceremony orchestration, audit proofs
coercion_resistance.py	190	JCJ credential management, batch filtering

Election layer (7 modules, ~1,675 LOC):

Module	LOC	Function
voting_types.py	205	Election, Race, Choice, Ballot, Tally types
election_manager.py	~500	Full lifecycle: create, open, cast, tally, certify
election_contract.py	164	AAMAS 2026 contract construction
eligibility_checker.py	129	Four-layer eligibility verification
ballot_recorder.py	227	Journal recording, HMAC integrity, receipts
bulletin_board.py	321	Publish, query, verify, audit export
result_attestation.py	129	Signed attestation with hash chain binding

Design decisions. Core voting cryptography uses pure Python with built-in arbitrary-precision integers, eliminating external cryptographic dependencies and simplifying auditing. This is a deliberate trade-off: pure-Python modular exponentiation is 10-100x slower than C implementations (e.g., GMP via gmpy2), but the code is more auditable, more portable, and has a smaller attack surface. The one exception is RSA key generation for blind signatures, which uses the cryptography library for constant-time operations and side-channel resistance -- properties that are difficult to achieve in pure Python. All cryptographic values use frozen dataclasses with __slots__ for immutability and memory efficiency. Credential comparisons use hmac.compare_digest for constant-time equality, preventing timing side-channel attacks on credential validation.

Separation of concerns. The two-layer architecture cleanly separates cryptographic primitives from election management. The cryptographic layer has no knowledge of elections, voters, or contracts -- it operates on keys, plaintexts, and ciphertexts. The election layer orchestrates the protocol lifecycle using the cryptographic layer as a black box. This separation simplifies auditing: a cryptographer can review the 1,313-LOC cryptographic layer independently, while an election specialist can review the governance and lifecycle logic independently.

7.2 Performance

Benchmarks use 1024-bit Paillier keys on a single-core CPython runtime. Production deployments use 2048-bit keys (estimated 8x overhead).

Per-operation latency (1024-bit, single core):

Operation	Time	Notes
KeyGen	583 ms	One-time per election
Encrypt	26 ms	Per-vote, client-side
ZK Prove	102 ms	Per-vote, client-side
ZK Verify	103 ms	Per-ballot, server-side
Homomorphic Add	0.02 ms	Per-ballot accumulation
Partial Decrypt	50 ms	Per-share-holder
Combine (3-of-5)	2.5 ms	Per-race
Blind Token	0.6 ms	Per-voter registration
Sign Blinded	85 ms	Authority, per-voter

Election-scale benchmarks (1024-bit, single core):

Voters	Encrypt+Prove	Tally	Decrypt	Total
100	4.5 s	3 ms	33 ms	~4.5 s
1,000	30 s	20 ms	21 ms	~30 s
10,000	~5 min	~200 ms	~21 ms	~5 min

Analysis. Three observations emerge from the benchmarks:

First, encryption and proof generation dominate total election time (>99%), but these are client-side operations that are embarrassingly parallel across voters and cells. In a deployment with 100 cells, a 10,000-voter election completes the encryption phase in approximately 3 seconds per cell (100 voters per cell, each encrypting and proving in ~128ms). This parallel scalability is a direct consequence of SOVEREIGN's distributed architecture: each cell processes its voters independently.

Second, homomorphic tallying is near-instant: 20ms for 1,000 ballots. This confirms that the O(K) tallying cost has a negligible constant factor -- modular multiplication in Z_{n^2} is a single arithmetic operation per ballot. Even at 2048-bit security (estimated 8x overhead), tallying 10,000 ballots takes approximately 1.6 seconds sequential or 16ms with 100x parallelism across cells.

Third, threshold decryption is O(M) and independent of K: 21-33ms for 3-of-5 regardless of whether the election has 100 or 10,000 voters. This means decryption latency does not grow with election size -- a critical property for large-scale deployments. The decryption cost is dominated by M modular exponentiations in Z_{n^2} (one per share holder) plus one Lagrange combination.

Scalability model. For an election with K voters distributed across C cells with M-of-N threshold:

• Voting phase: O(K/C) encryptions and proofs per cell, each independent
• Tallying phase: O(K) proof verifications and homomorphic additions, parallelizable across cells
• Decryption phase: O(M) partial decryptions and one combination, independent of K

At 2048-bit security (128-bit per NIST), estimated performance for K = 10,000: per-voter encrypt+prove ~1s client-side; tallying ~1.6s sequential; decryption ~170ms for 3-of-5.

7.3 Comparison

Feature	SOVEREIGN	ElectionGuard	Helios	Belenios
Encryption	Paillier	ElGamal (EC)	ElGamal	ElGamal
Homomorphic tallying	Yes	Yes	Yes	Partial
Threshold decryption	Damgard-Jurik	Lagrange	No (single key)	Threshold ElGamal
Key never assembled	Yes	No	N/A	Yes
Blind signatures	RSA	No	No	No
Coercion resistance	HMAC-JCJ	No	No	Partial (RF)
Formal contracts	AAMAS 2026	No	No	No
Multi-cell distribution	Yes	No	No	No
Disconnected operation	Yes	No	No	No
Election types	7	1	1	2
Formal proofs	Game-based	Game-based	Game-based	UC
Open source	Yes	Yes	Yes	Yes

SOVEREIGN's primary advantages are distributed multi-jurisdictional trust, multiple election types, and machine-enforced contract governance -- features that no existing system provides individually, let alone in combination. Its primary disadvantages relative to Belenios are the lack of UC security proofs and Coq-verified implementations. UC proofs provide composability guarantees that game-based proofs do not: they ensure security is preserved when the protocol is composed with other protocols in a larger system. For SOVEREIGN, which composes Paillier, RSA blind signatures, Sigma protocols, and Shamir sharing, UC proofs would provide stronger assurance. Relative to ElectionGuard, SOVEREIGN lacks deployment experience with real election hardware and voter populations, which is critical for understanding usability, accessibility, and operational failure modes.

Baseline comparison methodology. We compare against published specifications and academic papers for each system. ElectionGuard benchmarks are from the specification v2.0 [6] using elliptic curve ElGamal, which is faster per-operation than Paillier but requires encoding votes as exponents. Helios benchmarks are from Adida [1] using JavaScript client-side encryption. Belenios properties are from Cortier et al. [11]. Direct performance comparison is complicated by different encryption schemes, key sizes, and implementation languages; we focus on feature comparison and asymptotic behavior rather than raw operation latency.

7.4 Test Coverage

The implementation includes 122 passing tests across 17 test files: 7 cryptographic test files covering all primitives (Paillier round-trips, threshold reconstruction with arbitrary M-of-N subsets, blind signature unlinkability, ZK proof acceptance and rejection, tally engine with invalid ballot rejection, decryption ceremony, and credential indistinguishability); 8 election test files covering types, eligibility, contracts, full lifecycle for all 7 election types, ballot recording with HMAC integrity, bulletin board operations, and result attestation; and 2 end-to-end integration tests that exercise the complete cryptographic flow from key generation through threshold decryption with 5 simulated voters (3 for candidate A, 2 for candidate B), verifying final counts match expected results.

8. Discussion

8.1 Limitations

No formal verification. SOVEREIGN's security arguments are reduction-based game-hops, not UC-framework proofs or Coq-verified implementations. Composition security across Paillier, RSA blind signatures, Sigma protocols, and Shamir sharing is argued informally. Achieving UC security is important future work.

Trusted device problem. Like all electronic voting systems, SOVEREIGN assumes the voter's device correctly implements the protocol. A compromised device could encrypt a different vote than intended. Mitigations include voter-verifiable paper audit trails and split-path verification (encrypting on one device, verifying the ZK proof on another).

Decryption proof strength. The current decryption proof is a SHA-256 binding hash, not a zero-knowledge proof of correct partial decryption. A malicious share holder could submit an incorrect partial decryption. Adding Chaum-Pedersen proofs would detect this.

Single authority key for JCJ. The HMAC-based coercion resistance relies on a single authority key. Compromising this key breaks coercion resistance entirely. A threshold HMAC construction or reverting to public-key JCJ would distribute this trust.

No mix-net. Encrypted ballots appear on the bulletin board in arrival order, potentially leaking timing information. A re-encryption mix-net would randomize ballot order at the cost of additional complexity.

Python performance. The pure-Python implementation is suitable for evaluation but not production. A C or Rust implementation would provide 10-100x speedup for modular exponentiation.

8.2 Deployment Considerations

SOVEREIGN is best suited initially for organizational voting (corporate boards, professional associations, committee decisions) where the threat model is less severe and the operational complexity is manageable. These deployments provide real-world validation before scaling to political elections.

For political elections, additional infrastructure is required: voter-verifiable paper audit trails, independent client auditing, hardware security modules for key share storage, and formal certification processes. The multi-cell architecture maps naturally to existing election administration boundaries (states, counties, precincts), and the disconnected operation capability addresses disaster-response and military deployment scenarios.

Key ceremony security. The threshold key ceremony is the most security-critical phase. Each share holder should operate from a separate machine, ideally air-gapped. The compute_single_partial method is designed for this: it runs on the share holder's machine, and only the partial decryption result (never the share value) is transmitted. The ceremony coordinator never sees key shares and cannot reconstruct the private key. Share distribution uses authenticated, encrypted channels. Each holder verifies their share by computing a test partial decryption on a known ciphertext before the election begins.

Split-path verification. SOVEREIGN's architecture supports a split-verification model where the voter encrypts on one device and verifies the ZK proof on a second independent device (or a public verification terminal). Only the ciphertext and proof are needed for verification -- no secrets. This addresses the trusted device problem for voters who distrust their primary device.

Audit trail completeness. The bulletin board records all encrypted ballots, ZK proofs, tallies, decryption proofs, and attestations. The result attestation includes a hash chain over all ballot journal entries, creating a tamper-evident binding between raw ballot data and the certified result. This trail is sufficient for independent audit years after the election without trusting any participant's claims.

9. Ethical Considerations

Responsible development. Electronic voting systems carry significant societal risk if deployed prematurely or incorrectly. SOVEREIGN is presented as a research contribution with a working prototype, not as production-ready election infrastructure. We recommend extensive independent security review, formal verification, and pilot deployment with parallel paper-based elections before any use in binding political elections.

Voter privacy. SOVEREIGN's design prioritizes voter privacy through multiple mechanisms (homomorphic encryption, blind signatures, ZK proofs). However, metadata leakage (timing, network patterns, device fingerprinting) could compromise privacy in practice. Deployment must address these side channels.

Coercion resistance limitations. While the JCJ protocol provides formal coercion resistance, real-world coercion involves social dynamics that cryptographic protocols cannot fully address. The system should not be presented as eliminating coercion in contexts where physical threats or social pressure dominate.

Dual-use concerns. The same cryptographic tools that protect democratic elections could theoretically be misused to conduct sham elections with a veneer of cryptographic legitimacy. The open-source nature of SOVEREIGN, combined with universal verifiability and the public bulletin board, mitigates this: any observer can audit the election, and the code is available for independent review.

No deceptive use. The formal contract governance model is specifically designed to make election rules transparent and verifiable. We oppose any use of this technology to obscure or manipulate election processes.

Incremental deployment. We advocate for incremental deployment: first in low-stakes organizational votes with parallel paper ballots, then in advisory elections, and only after extensive validation in binding political elections. Each stage provides real-world feedback on security, usability, and operational robustness while minimizing the consequences of undiscovered flaws.

10. Conclusion

We have presented SOVEREIGN, a distributed E2E-V voting system addressing four key limitations of existing systems: centralized trust, single election types, procedural governance, and network dependency. SOVEREIGN distributes trust across independent cells via threshold cryptography, supports seven election types under a unified Paillier-based framework, governs elections through formal AAMAS 2026 entity contracts with cryptographic attestation, and enables disconnected operation through local cryptographic processing with eventual synchronization.

Our implementation demonstrates feasibility with 122 passing tests, end-to-end integration verification, and benchmarks showing sub-second per-voter cryptographic cost with tallying latency independent of election size. The comparison analysis shows SOVEREIGN is the first E2E-V system to combine distributed multi-jurisdictional trust, multiple election types, formal governance, and disconnected operation.

Future work includes UC-framework security proofs for formal composability guarantees, Chaum-Pedersen proofs for partial decryption verification, threshold HMAC for distributing the coercion-resistance authority key, range proofs for encrypted weighted voting, re-encryption mix-nets for ballot-order privacy, and a C/Rust reimplementation for production performance. Pilot deployments with organizational voting -- conducted in parallel with traditional methods to provide a safety net -- will validate usability, operational robustness, and real-world performance characteristics before any use in binding elections.

SOVEREIGN demonstrates that the four key limitations of existing E2E-V systems -- centralized trust, single election types, procedural governance, and network dependency -- can be addressed within a unified cryptographic framework without sacrificing the core security properties that make E2E-V systems valuable. The combination of distributed cells, formal contracts, and disconnected operation opens new deployment contexts -- federal elections across sovereign jurisdictions, military operations in austere environments, and international organizations spanning legal frameworks -- that are currently beyond the reach of any existing E2E-V system.

Availability

The SOVEREIGN implementation is part of the System9 platform. The complete source code, including all cryptographic modules, election management layer, and 122 tests across 17 test files, is available for review. Test vectors for all cryptographic primitives are provided to enable independent verification and alternative implementations.

References

[1] B. Adida. "Helios: Web-based Open-Audit Voting." In Proc. 17th USENIX Security Symposium, pp. 335-348, 2008.

[2] J. Benaloh. "Simple Verifiable Elections." In Proc. USENIX/ACCURATE Electronic Voting Technology Workshop (EVT), 2006.

[3] D. Bernhard, V. Cortier, D. Galindo, O. Pereira, B. Warinschi. "SoK: A Comprehensive Analysis of Game-Based Ballot Privacy Definitions." In Proc. IEEE S&P, pp. 499-516, 2015.

[4] R. Canetti. "Universally Composable Security: A New Paradigm for Cryptographic Protocols." In 42nd FOCS, pp. 136-145, IEEE, 2001.

[5] [Anonymous]. "Formal Entity Contracts for Autonomous Agent Governance." Submitted to AAMAS 2026. [Reference anonymized for double-blind review.]

[6] [ElectionGuard]. ElectionGuard Specification v2.0. https://www.electionguard.vote/spec/. See also: J. Benaloh et al. "STAR-Vote: A Secure, Transparent, Auditable, and Reliable Voting System." USENIX JETS, 2019.

[7] D. Chaum. "Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms." Communications of the ACM, 24(2):84-88, 1981.

[8] D. Chaum. "Blind Signatures for Untraceable Payments." In CRYPTO '82, pp. 199-203, 1983.

[9] V. Cortier, J. Lallemand. "Voting: You Can't Have Privacy without Individual Verifiability." In Proc. ACM CCS, pp. 53-66, 2018.

[10] R. Cramer, R. Gennaro, B. Schoenmakers. "A Secure and Optimally Efficient Multi-Authority Election Scheme." In EUROCRYPT '97, LNCS 1233, pp. 103-118, 1997.

[11] V. Cortier, P. Galindo, S. Glondu, M. Izabachene. "Election Verifiability for Helios under Weaker Trust Assumptions." In ESORICS 2014, LNCS 8713, pp. 327-344, 2015. See also: https://www.belenios.org/

[12] I. Damgard, M. Jurik. "A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System." In PKC 2001, LNCS 1992, pp. 119-136, 2001.

[13] A. Fiat, A. Shamir. "How To Prove Yourself: Practical Solutions to Identification and Signature Problems." In CRYPTO '86, LNCS 263, pp. 186-194, 1986.

[14] A. Juels, M. Jakobsson. "Coercion-Resistant Electronic Elections." In Proc. WPES, pp. 61-70, ACM, 2005.

[15] A. Juels, D. Catalano, M. Jakobsson. "Coercion-Resistant Electronic Elections." In Proc. WPES, pp. 61-70, ACM, 2005.

[16] A. Kiayias, T. Zacharias, B. Zhang. "End-to-End Verifiable Elections in the Standard Model." In EUROCRYPT 2015, LNCS 9057, pp. 468-498, 2015.

[17] P. Paillier. "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes." In EUROCRYPT '99, LNCS 1592, pp. 223-238, 1999.

[18] D. Pointcheval, J. Stern. "Security Arguments for Digital Signatures and Blind Signatures." Journal of Cryptology, 13(3):361-396, 2000.

[19] A. Shamir. "How to Share a Secret." Communications of the ACM, 22(11):612-613, 1979.

[20] F. Shaikhli, R. Zulkurnain, M. Chuprat. "Blockchain-Based E-Voting Systems: A Technology Review." Electronics, 10(19), 2021.

[21] B. Smyth, S. Frink, M. Clarkson. "Election Verifiability: Cryptographic Definitions and an Analysis of Helios and JCJ." Cryptology ePrint Archive, Report 2015/233, 2015.

[22] N. Smart, F. Vercauteren. "Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes." In PKC 2010, LNCS 6056, pp. 420-443, 2010.

[23] S. Delaune, S. Kremer, M. Ryan. "Verifying Privacy-Type Properties of Electronic Voting Protocols." Journal of Computer Security, 17(4):435-487, 2009.

[24] P. Ryan, D. Bismark, J. Heather, S. Schneider, Z. Xia. "Pret a Voter: A Voter-Verifiable Voting System." IEEE Trans. Information Forensics and Security, 4(4):662-673, 2009.

[25] R. Hanifatunnisa, B. Rahardjo. "Blockchain Based E-Voting Recording System Design." In Proc. TSSA, pp. 1-6, IEEE, 2017.

---

Appendix A: Election Types

SOVEREIGN supports seven election types. The cryptographic layer (Paillier encryption, ZK proofs, threshold decryption) is shared; only the tallying algorithm and threshold conditions vary.

Type	Ballot	Tallying Algorithm	Winner Condition
Simple Majority	One choice per race (0/1)	Homomorphic sum per choice	Highest count
Super Majority	One choice per race (0/1)	Homomorphic sum per choice	Exceeds threshold % (default 66.7%)
Ranked Choice	Rank per choice	Multi-round: eliminate lowest, redistribute	Majority after elimination rounds
Approval	Any number of choices (0/1 each)	Independent homomorphic sum per choice	Highest approval count
Weighted	Weight per choice (0..max)	Homomorphic sum of weights	Highest weighted total
Consensus	One choice per race (0/1)	Homomorphic sum per choice	Meets unanimity/near-unanimity threshold
Referendum	Binary yes/no (0/1)	Homomorphic sum	Exceeds passage threshold

Ranked choice detail. Pure homomorphic tallying reveals only per-choice sums, not individual rankings. SOVEREIGN encrypts each rank position separately (choice X ranked 1st, 2nd, etc.) and performs multiple rounds of threshold decryption. Each round reveals the aggregate rank distribution, not individual rankings.

Weighted voting detail. Voters encrypt their weight rather than 1 for selected choices. The homomorphic sum produces the weighted total. ZK proofs must demonstrate the encrypted value is in [0, max_weight] rather than {0, 1}; range proofs are planned for future work.

Appendix B: Recommended Parameters

Parameter	Development	Production	High Security
Paillier key	1024 bits (~80-bit security)	2048 bits (~128-bit)	3072 bits (~128-bit+)
RSA blind sig	2048 bits	2048 bits	4096 bits
Threshold (M, N)	(2, 3)	(3, 5)	(5, 9)
Miller-Rabin rounds	20	40	64
SHA-256 (Fiat-Shamir)	256 bits	256 bits	256 bits
HMAC-SHA-256 (JCJ)	256 bits	256 bits	256 bits

The 2048-bit Paillier key provides 128-bit security aligned with NIST recommendations through ~2030. The 3072-bit key provides additional margin for elections whose secrecy must be preserved beyond 2030. The (3,5) threshold balances availability (any 3 of 5 decrypt) against security (compromising 2 is insufficient). The (5,9) configuration suits elections with mutually distrustful jurisdictions.

Appendix C: Extended Test Vectors

Generated from the reference implementation with 1024-bit Paillier keys.

Paillier round-trips:

• E(0): ciphertext is 2045 bits
• E(1): ciphertext is 2047 bits (~2n bits, as expected for n^2 domain)
• D(E(42)) = 42
• D(E(17) * E(25) mod n^2) = 42 (homomorphic addition: 17 + 25)

ZK proof structure:

• Proof components: a_0, a_1 in Z*_{n^2} (2047 bits), e_0 in Z_n (255 bits), z_0 in Z_n (1022 bits)
• Verify(pi, E(1), pk) = ACCEPT (correct proof for correct ciphertext)
• Verify(pi, E(0), pk) = REJECT (proof for E(1) fails against different ciphertext)

Threshold (5,3) round-trips:

• D_partial(E(77), {share_1, share_2, share_3}) = 77
• D_partial(E(77), {share_1, share_3, share_5}) = 77 (any 3-of-5 subset)

Blind signature round-trip:

• Verify(Unblind(Sign_d(Blind_e(token, r)), r), token, e) = ACCEPT

Appendix D: Multi-Cell Deployment Scenarios

Federal election (large scale). 50 nodes (states), 3,000+ service groups (counties), 100,000+ cells (precincts). Key shares: 7 (one per judicial circuit), threshold 4. Precincts collect encrypted ballots locally; counties aggregate subtallies homomorphically; states coordinate threshold decryption; national bulletin board aggregates all state boards.

Corporate board vote (small scale). 1 node, 1 service group, 1 cell. Key shares: 3 (board chair, corporate secretary, external auditor), threshold 2. All operations are local.

Military field election (disconnected). 1 node (theater command), 3 service groups (brigade areas), 9 cells (battalion positions). Key shares: 5 (1 per battalion commander + 2 at brigade), threshold 3. Cells operate disconnected for days or weeks; encrypted ballots synchronize when the tactical network is available; threshold decryption occurs at theater command.

International organization (cross-border). 27 nodes (member states), 27 service groups (national delegations), 54 cells (primary + backup per delegation). Key shares: 9 (3 per geographic region), threshold 5. Threshold decryption requires participation from at least 5 key holders spanning at least 2 geographic regions.