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

SOVEREIGN: Distributed End-to-End Verifiable Voting with Entity Contracts, Threshold Homomorphic Tallying, and Multi-Cell Consensus

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.
• 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.

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

Table 1: Limitations of existing E2E-V systems.

Limitation	ElectionGuard	Helios	Belenios	Blockchain	Pret a Voter
Centralized trust	Yes	Yes	Partial	Distributed but transparent	Yes
Single election type	Plurality only	Plurality only	Plurality + MJ	App-dependent	Plurality only
Procedural governance	Yes	Yes	Yes	Smart contract	Yes
Network required	Yes	Yes	Yes	Yes (consensus)	N/A (physical)
Coercion resistance	No	No	Partial (RF)	No	Yes (ballot destruction)

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. Multi-cell tallying with consensus verification. We present a distributed tallying protocol where cells accumulate homomorphic subtallies independently, synchronize via delay-tolerant networking, and produce a global tally verified through cross-cell consensus.

6. 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.

7. 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 in detail. Section 5 presents the election lifecycle as a state machine. Section 6 details election governance via entity contracts. Section 7 presents the multi-cell tallying protocol. Section 8 provides security analysis with reduction proofs for all five properties. Section 9 reports implementation, performance, and comparison. Section 10 discusses limitations. Section 11 addresses ethical considerations. Section 12 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 and secrecy 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 Multi-Authority Election Schemes

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, but their construction uses more complex cryptographic machinery and does not address distribution across independent jurisdictions.

2.6 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.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 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)	Example (Military)	Role
Node	State	Division	Theater command	Sovereign jurisdiction
Service Group	County	Department	Brigade area	Administrative district
Cell	Precinct	Office	Battalion position	Physical 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 Entity Model

SOVEREIGN models all participants as cryptographic entities:

Voters hold eligibility credentials. In anonymous elections, voters hold blind-signed tokens and (optionally) JCJ coercion-resistant credentials. Voter identity is decoupled from ballot identity through the blind signature protocol.

Election officials hold key share custodianship. Each official holds one share of the Paillier private key and participates in the threshold decryption ceremony. Officials are authenticated through the entity system and governed by the election contract.

Tallying agents perform homomorphic tally computation on encrypted data. Their behavior is governed by the election contract, which specifies the tallying algorithm, resource constraints, and success criteria.

Verifiers read the bulletin board and verify election correctness. Verifiers need no credentials -- the bulletin board is public.

3.3 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.4 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 Paillier Homomorphic Encryption

SOVEREIGN uses the Paillier cryptosystem [17] for ballot encryption. Paillier is additively homomorphic: the product of two ciphertexts decrypts to the sum of the plaintexts. We chose Paillier over the more common ElGamal for three reasons: (1) Paillier's additive homomorphism maps directly to vote counting -- the sum of 0/1 encryptions yields the count -- whereas ElGamal requires encoding votes as exponents and solving the discrete log after decryption; (2) Paillier decryption is deterministic, which simplifies threshold combination and eliminates the need for trial decryption; and (3) Paillier's security rests on the Decisional Composite Residuosity (DCR) assumption, which is well-studied and considered at least as hard as factoring.

Key generation. Generate two large primes p, q of equal bit-length (1024 bits each for 2048-bit security). Compute n = pq and g = n + 1. The private key is lambda = lcm(p-1, q-1) and mu = L(g^lambda mod n^2)^{-1} mod n, where L(x) = (x-1)/n. Primes are generated using Python's secrets module with 20-round Miller-Rabin primality testing, providing error probability at most 4^{-20} = 2^{-40} per candidate.

Encryption. To encrypt plaintext m in Z_n with randomness r in Z*_n:

c = (1 + n*m) * r^n mod n^2

The simplification g^m = 1 + nm mod n^2 (valid because g = n+1 and higher binomial terms vanish mod n^2) avoids an expensive modular exponentiation. The randomness r ensures semantic security: the same plaintext encrypted twice produces different ciphertexts.

Decryption. To decrypt ciphertext c:

m = L(c^lambda mod n^2) * mu mod n

Correctness. Starting from c = (1+nm)r^n mod n^2, raising to the power lambda gives c^lambda = (1+nm)^lambda * r^{nlambda} mod n^2. By Carmichael's theorem, r^{lambda} = 1 mod n, so r^{nlambda} = 1 mod n^2 (by a Hensel lifting argument). Then (1+nm)^lambda = 1 + nmlambda mod n^2 (binomial theorem, higher terms vanish mod n^2). Applying L gives m*lambda, and multiplying by mu = lambda^{-1} mod n recovers m.

Homomorphic property. For encrypted votes c_1 = E(v_1), ..., c_K = E(v_K):

product(c_i) mod n^2 = E(v_1 + v_2 + ... + v_K)

This is the key property enabling vote tallying without decryption. The tally engine initializes with E(0) as the identity element and iteratively applies modular multiplication in Z_{n^2}. Two verification steps are performed before including a ballot: ZK proof verification (the ciphertext encrypts 0 or 1) and anonymous token verification (the voter is authorized).

Security. Paillier is IND-CPA secure under the DCR assumption [17]. Informally, DCR states that given n, it is hard to determine whether a random element of Z*_{n^2} is an n-th residue. This directly implies that E(0) and E(1) are computationally indistinguishable, so individual encrypted ballots reveal no information about the underlying vote. We use 2048-bit keys for production (128-bit security per NIST) and 1024-bit keys for testing only.

Algorithm: Paillier Encrypt-Tally-Decrypt

Encrypt(pk, v):
  Input:  Public key pk = (n, n^2, g), vote v in {0, 1}
  Output: Ciphertext c in Z*_{n^2}, randomness r
   1.  r <- RandomCoprime(n)
   2.  c <- (1 + n*v) * r^n mod n^2
   3.  return (c, r)

HomomorphicTally(pk, {c_1, ..., c_K}):
  Input:  Public key pk, K encrypted votes
  Output: Encrypted tally T = E(sum(v_i))
   1.  T <- E(0) = (1 + n*0) * r_0^n mod n^2
   2.  for i = 1 to K:
   3.    T <- T * c_i mod n^2
   4.  return T

ThresholdDecrypt(T, {share_1, ..., share_M}, pk):
  Input:  Encrypted tally T, M key shares, public key pk
  Output: Plaintext count m
   1.  Delta <- N!
   2.  for each share i:
   3.    partial_i <- T^{2 * Delta * s_i} mod n^2
   4.  for each share i, compute Lagrange coefficient:
   5.    mu_i <- Delta * product_{j != i} (0 - x_j) / (x_i - x_j)
   6.  combined <- product_i (partial_i ^ mu_i) mod n^2
   7.  l_val <- (combined - 1) / n
   8.  scale <- 2 * Delta^2 mod n
   9.  m <- l_val * scale^{-1} * mu mod n
  10.  return m

4.2 RSA Blind Signatures for Anonymous Tokens

Blind signatures [8] enable the election authority to certify a voter's eligibility without learning their ballot identity.

Token generation. The voter generates a random 256-bit token.

Blinding. The voter computes:

h = SHA-256(token) mod n
blinded = h * r^e mod n

where r is a random blinding factor coprime to n and (n, e) is the authority's RSA public key.

Signing. The authority signs the blinded value:

blinded_sig = blinded^d mod n

The authority never sees the original token.

Unblinding. The voter computes:

sig = blinded_sig * r^{-1} mod n = h^d mod n

This is a standard RSA signature on h = SHA-256(token).

Verification. Anyone can verify: 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, this ensures each eligible voter casts at most one counted ballot.

4.3 Zero-Knowledge Ballot Proofs

Voters must prove their encrypted ballot contains 0 or 1 without revealing which, preventing ballot stuffing (encrypting a value > 1). We use a disjunctive Sigma protocol (OR-proof) made non-interactive via the Fiat-Shamir heuristic [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

Zero-knowledge. 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. The resulting transcripts are identically distributed to real proofs regardless of the witness value.

Soundness. By 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. Non-interactive soundness follows from the Fiat-Shamir transform in the random oracle model [14].

Domain separation. The hash input is prefixed with "SOVEREIGN-ZK-v1" to prevent 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.4 Threshold Key Management and Partial Decryption

The Paillier private key is split into N shares using Shamir's Secret Sharing [19] 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 because inverses are well-defined. 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 the group order phi(n^2) = n*phi(n), which is secret (knowing phi(n) is equivalent to factoring n). The Delta = N! trick ensures all Lagrange denominators divide N!, making all divisions exact over the integers without knowing phi(n^2).

Sharing polynomial. f(x) = lambda_val + a_1x + a_2x^2 + ... + a_{M-1}x^{M-1}, where each a_i is drawn uniformly from [0, n2^{128}). The large coefficient bound provides 128-bit statistical security: regardless of the value of lambda_val, the distribution of M-1 or fewer shares is statistically indistinguishable (within 2^{-128}) from uniform. Share i is f(i), evaluated without modular reduction.

Partial decryption. Each share holder computes locally:

partial_i = c^{2 * Delta * s_i} mod n^2

The factor of 2*Delta ensures that the Lagrange coefficients mu_i are always exact integers (since all denominators divide N!). The factor of 2 provides algebraic convenience in the recovery step. The share holder also computes a SHA-256 commitment hash over (share_id, partial_value, ciphertext) for audit logging. The raw share value s_i never leaves the holder's machine.

Correctness. 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 the standard Paillier decryption derivation). 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} of uniform, ensured by the large coefficient bound). 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.

4.5 Coercion-Resistant Credentials

SOVEREIGN implements a simplified variant of the JCJ protocol [15] using HMAC-SHA-256 rather than public-key encryption:

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):
  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. Our HMAC approach provides only computational security. However, it 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.

5. Election Lifecycle State Machine

The election lifecycle proceeds through a deterministic state machine with well-defined transitions. Each state has entry conditions, permitted operations, and exit conditions enforced by the election contract.

State Machine:
  DRAFT --[setup complete, contract published]--> OPEN
  OPEN --[temporal bound reached]--> CLOSED
  CLOSED --[tally initiated]--> TALLYING
  TALLYING --[decryption complete, attestation signed]--> CERTIFIED
  CERTIFIED --[archival period elapsed]--> ARCHIVED

5.1 DRAFT State (Setup Phase)

Entry: Election object created with type, privacy level, races, choices, eligible voters, temporal bounds, and threshold requirements.

Operations:

1. Generate Paillier keypair (pk, sk) at configured security level.
2. Split sk into N shares with threshold M. Distribute shares to holders on separate cells.
3. Generate RSA keypair for blind signatures.
4. Securely erase original sk -- it never exists on any machine after splitting.
5. Build AAMAS 2026 entity contract.
6. Publish election definition to bulletin board.

Exit: All cryptographic material distributed, contract published. Transition to OPEN.

5.2 OPEN State (Registration and Voting Phase)

Entry: Election definition and contract on bulletin board.

Registration operations (per voter):

1. Eligibility checker applies four filters: duplicate ballot guard, entity type restriction, explicit allow-list, live entity lookup.
2. Issue blind-signed anonymous token (authority never sees the token).
3. Optionally issue real JCJ credential; voter may generate fake credentials.

Voting operations (per ballot):

1. Voter encrypts each selection (0 or 1) using Paillier with fresh randomness.
2. Voter generates ZK proof per encrypted selection.
3. Ballot recorder writes to append-only journal with HMAC integrity signature.
4. Voter receives receipt: (ballot_id, SHA-256(encrypted_payload), timestamp).
5. Encrypted ballot published to bulletin board.

Exit: Temporal bound T.valid_until reached. Transition to CLOSED. Ballots outside the temporal window are rejected by the contract enforcement layer.

5.3 CLOSED State

Entry: Voting window ended.

Operations: No new ballots accepted. Final ballot count recorded. Late-arriving ballots from disconnected cells are accepted if their local timestamp (attested in the HMAC chain) falls within the temporal bounds.

Exit: Tally initiation. Transition to TALLYING.

5.4 TALLYING State

Entry: All cells synchronized (or sufficient subset).

Operations:

1. Credential filtering: authority validates JCJ credentials, silently discarding fakes.
2. Proof verification: verify each ballot's ZK proof and anonymous token.
3. Homomorphic summation: for each race/choice, multiply all valid ciphertexts mod n^2.
4. Publish encrypted tallies to bulletin board.

Exit: All encrypted tallies computed and published. Transition to threshold decryption.

5.5 CERTIFIED State (Decryption and Verification)

Entry: Encrypted tallies on bulletin board.

Operations:

1. Each of M share holders computes partial decryption on their machine.
2. Combiner recovers plaintext via Lagrange interpolation.
3. Voters verify receipts against bulletin board.
4. Observers verify all ZK proofs, recompute homomorphic sum, check decryption proofs.
5. Result attestation generator creates signed attestation binding result_hash, journal_hash, contract_id.

Exit: Attestation published. Transition to ARCHIVED after archival period.

5.6 ARCHIVED State

Entry: All verification complete, attestation published.

The bulletin board, encrypted ballots, proofs, tallies, and attestations are preserved for future audit. The cryptographic properties ensure the audit trail is self-verifying: any party with access to the bulletin board data can independently verify the entire election without trusting any participant.

6. Election Governance via Entity Contracts

6.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.

6.2 Election Contract Mapping

Tuple	Election Meaning	Example	Enforcement Point
I (Input)	Ballot format, field types, race/choice schema	{ballot_id: str, selections: list}	Ballot recorder
O (Output)	Tally format, minimum completeness = 1.0	{race_tallies: list, total_voted: int}	Attestation
S (Skills)	Tallying algorithm	"tally:ranked_choice"	Agent selection
R (Resources)	Max operations = eligible voters	max_api_calls = 100	Contract layer
T (Temporal)	Election open/close window	valid_from/valid_until	Contract layer
Phi (Success)	100% inclusion, quorum satisfaction	min_completeness = 1.0	Attestation
Psi (Termination)	Exception handling policy	timeout_action = "extend"	Exception handler

6.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. 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.

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 trigger investigation via Psi termination conditions.

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.

6.4 Concrete Contract Example

Contract = (I, O, S, R, T, Phi, Psi)

I = InputSpec(
  required_fields = (ballot_id, election_id, voter_entity_id, selections),
  field_types = {ballot_id: str, selections: list[BallotSelection]},
  schema_json = {race_ids: ["race-001"], choice_map: {"race-001": ["A", "B", "C"]}}
)

O = OutputSpec(
  guaranteed_fields = (election_id, race_tallies, total_voted, certified_at),
  min_completeness = 1.0
)

S = ("tally:simple_majority",)

R = ResourceConstraints(max_api_calls = 100)

T = TemporalConstraints(valid_from = "2026-01-01T00:00:00Z", valid_until = "2026-01-31T23:59:59Z")

Phi = SuccessCriteria(min_completeness = 1.0, quorum_pct = 0.5, evaluation_method = "exact_count")

Psi = TerminationConditions(timeout = "extend", violation = "escalate", budget_exhaustion = "terminate")

7. Multi-Cell Tallying Protocol

The multi-cell tallying protocol is SOVEREIGN's core architectural contribution, enabling trust distribution across independent cells while maintaining homomorphic tallying guarantees.

7.1 Per-Cell Accumulation

Each cell independently accumulates its local encrypted ballots:

CellTally(cell_k, pk):
  Input:  Cell identifier, public key
  Output: Encrypted subtally T_k, metadata
   1.  T_k <- E(0)                             // identity element
   2.  valid_count <- 0
   3.  for each ballot b_i in cell_k:
   4.    if not verify_zk_proof(b_i):
   5.      reject(b_i, "invalid_proof"); continue
   6.    if not verify_token(b_i):
   7.      reject(b_i, "invalid_token"); continue
   8.    T_k <- T_k * c_i mod n^2               // homomorphic add
   9.    valid_count <- valid_count + 1
  10.  commitment <- SHA-256(cell_id || T_k || valid_count)
  11.  publish (cell_id, T_k, valid_count, commitment) to bulletin board
  12.  return (T_k, valid_count)

This per-cell accumulation enables disconnected operation: each cell computes its subtally using only local data, requiring no inter-cell communication. The subtally T_k = E(sum of votes in cell k) reveals nothing about individual votes or the count itself.

7.2 Cross-Cell Aggregation

After all cells have published subtallies, the global tally is computed:

GlobalTally({T_1, ..., T_C}, pk):
  Input:  Per-cell encrypted subtallies, public key
  Output: Global encrypted tally T_global
   1.  T_global <- E(0)
   2.  total_count <- 0
   3.  for k = 1 to C:
   4.    verify commitment(cell_k) against bulletin board
   5.    T_global <- T_global * T_k mod n^2
   6.    total_count <- total_count + count_k
   7.  verify total_count matches bulletin board ballot count
   8.  global_commitment <- SHA-256(T_global || total_count || {cell_ids})
   9.  publish (T_global, total_count, global_commitment) to bulletin board
  10.  return T_global

Correctness. The homomorphic property guarantees: product(E(sum_k)) = E(sum(sum_k)) = E(total_count). Any observer independently verifies by reading cell subtallies, multiplying modulo n^2, and comparing with the published global tally.

7.3 Subtally Privacy

Individual per-cell subtallies are encrypted and never decrypted separately -- only the global tally undergoes threshold decryption. This prevents learning vote distributions within individual cells, which could enable demographic inference attacks. If per-cell results are desired (as in some jurisdictions), the threshold decryption ceremony can be applied to subtallies individually, but this is a policy decision governed by the election contract's output specification (O).

7.4 Delayed Synchronization

For disconnected cells, the protocol accommodates late-arriving subtallies:

1. Initial global tally computed from available cells.
2. When a disconnected cell synchronizes, its subtally is published to the bulletin board.
3. Global tally is recomputed by multiplying the previous global tally with the new subtally.
4. Threshold decryption is deferred until all expected cells have reported or a timeout (governed by Psi) expires.
5. The election contract's temporal bounds (T) determine whether late-arriving ballots are included based on their original recording timestamp.

8. Security Analysis

We analyze SOVEREIGN's security through reduction-based arguments, proving all five security properties under standard cryptographic assumptions.

8.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. The integer Shamir sharing scheme with coefficients drawn from [0, n*2^{128}) provides statistical security within 2^{-128} of uniform: for any two secrets s, s', the statistical distance between the distribution of M-1 shares derived from s and from s' is at most 2^{-128}. This is because the random coefficients dominate the polynomial evaluation at any M-1 points, making the shares statistically independent of the secret. Partial decryptions are deterministic functions of shares, adding no advantage.

Composition with ZK proofs. The ZK proofs do not leak information. The simulated branch of the OR-proof is identically distributed to the real branch by construction: both consist of (a, e, z) tuples where a is derived to satisfy z^n = a * c_b^e mod n^2. In the random oracle model, the Fiat-Shamir transform preserves this property because the hash output is indistinguishable from random, so the challenge partition (e_0 + e_1 = H(...)) does not reveal which branch was simulated.

Composition with blind signatures. The blinding factor r makes the signed message h * r^e uniformly distributed over Z_n during registration, breaking the voter-ballot linkage. The authority sees only a random element of Z_n and cannot correlate the signing session with the final (token, sig) pair used in the ballot.

The overall advantage is bounded by:

Adv^BS_A <= 2 * Adv^DCR + Adv^ZK_sim + Adv^RSA_blind + negl(lambda)

All terms are negligible, completing the proof.

8.2 Individual Verifiability

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

Proof. After casting, the voter receives receipt R = (ballot_id, SHA-256(encrypted_payload), timestamp). The encrypted ballot is published to the bulletin board.

Case 1: Ballot replacement. Suppose the adversary replaces the voter's encrypted ballot p with a different payload p' on the bulletin board. The voter checks SHA-256(p') against their receipt. For the verification to pass despite replacement, the adversary must produce p' such that SHA-256(p') = SHA-256(p). This requires finding a second preimage, which contradicts the collision resistance of SHA-256.

Case 2: Ballot deletion. Suppose the adversary deletes the voter's ballot from the bulletin board. The voter's verification fails because no entry with matching ballot_id exists. Moreover, the HMAC hash chain creates a gap: the next entry's HMAC references the deleted entry's HMAC, and any observer recomputing the chain detects the deletion.

Case 3: Ballot addition. The adversary adds a fraudulent ballot. This does not affect the voter's verification (their ballot still matches), but it is detected by the eligibility check: the fraudulent ballot must contain a valid blind-signed token, which requires the authority's signing key (RSA unforgeability).

Therefore, individual verifiability holds: the voter can confirm their ballot is recorded as cast, or detect any modification, deletion, or substitution.

8.3 Universal Verifiability

Theorem 3. SOVEREIGN provides universal verifiability under ZK soundness, homomorphic determinism, and threshold decryption correctness.

Proof. Any observer verifies by performing five checks:

1. Ballot validity. Verify each ballot's ZK proof. By soundness of the disjunctive Sigma protocol in the random oracle model, a ballot with a valid proof encrypts 0 or 1 with overwhelming probability (1 - 2^{-256}). Invalid ballots are detected.

2. Token validity. Verify each ballot's anonymous token against the authority's RSA public key. By RSA unforgeability, only tokens signed by the authority pass verification. Duplicate tokens are detected by the bulletin board.

3. Tally correctness. Recompute the homomorphic sum by multiplying all valid ciphertexts modulo n^2. By the determinism of modular arithmetic, any discrepancy between the recomputed sum and the published encrypted tally indicates tampering. For the multi-cell protocol, the observer additionally verifies that the global tally equals the product of per-cell subtallies.

4. Decryption correctness. Verify the decryption proof. The current implementation uses a SHA-256 binding hash; a Chaum-Pedersen proof (planned) would provide zero-knowledge verification of correct partial decryption.

5. Count consistency. Verify that the number of ballots on the bulletin board matches the tally metadata and the sum of per-cell counts.

If all five checks pass, the published result is correct with overwhelming probability. The only unverified step is the correctness of individual partial decryptions (addressed by future Chaum-Pedersen proofs).

8.4 Eligibility

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

Proof. Every counted ballot must contain a valid anonymous token -- an RSA blind signature from the election authority. We show that only eligible voters' ballots are counted.

Unforgeability. By the RSA assumption, no PPT adversary produces a valid (token, sig) pair without querying the signing oracle. Specifically, given the authority's public key (n, e), producing sig such that sig^e mod n = SHA-256(token) mod n for any token not signed by the authority is equivalent to computing RSA inversions, which is hard under the RSA assumption.

One-token policy. The authority maintains a set of voter identities that have received blind signatures. It refuses to sign for any voter already in the set. This ensures at most one token per eligible voter.

Duplicate detection. During tallying, the bulletin board rejects ballots with previously-seen tokens. Combined with the one-token policy, this ensures each eligible voter casts at most one counted ballot.

Four-layer eligibility. Before token issuance, the eligibility checker applies: (1) duplicate ballot guard -- rejects voters who already received a token; (2) entity type restriction -- only entities of the correct type (e.g., "voter") are eligible; (3) explicit allow-list -- the voter must be on the election's authorized voter list; (4) live entity lookup -- the voter entity must exist and be active in the system. All four filters must pass.

8.5 Coercion Resistance

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

Proof. We define coercion resistance as: the coercer cannot determine whether a voter used a real or fake credential, even after observing the voter's entire interaction and the election result.

Construction. A coerced voter uses a fake credential: (credential_id, token, mac) where mac = HMAC-SHA-256(fake_key, credential_id || ":" || token) for a random fake_key. A genuine credential has mac = HMAC-SHA-256(authority_key, credential_id || ":" || token).

Indistinguishability argument. We reduce distinguishing real from fake credentials to breaking the PRF security of HMAC-SHA-256. Construct a distinguisher D that receives oracle access to either F_k (HMAC with authority key) or a random function R.

1. D generates (credential_id, token) uniformly at random.
2. D queries its oracle on input (credential_id || ":" || token) and receives mac.
3. D presents (credential_id, token, mac) to the adversary A.
4. If A outputs "real," D outputs "F_k." If A outputs "fake," D outputs "R."

Analysis. When D's oracle is F_k (the real HMAC), the credential is a valid real credential. When D's oracle is R, the credential's mac is the output of a random function, which is statistically identical to HMAC with a random key (since the fake key is never reused). Therefore:

Adv^CR_A = |Pr[A("real") | real] - Pr[A("real") | fake]|
         = |Pr[D outputs F_k | F_k] - Pr[D outputs F_k | R]|
         = Adv^PRF_D

Since Adv^PRF_D is negligible (HMAC-SHA-256 is a secure PRF), Adv^CR_A is negligible.

Tally integrity. During tallying, the authority validates each credential by recomputing HMAC with the authority key. Real credentials match; fakes are silently discarded. The count of discarded credentials is not revealed, preventing the coercer from detecting compliance. The final tally reflects only genuine votes.

Limitation: receipt-freeness. SOVEREIGN provides coercion resistance through the JCJ mechanism but does not provide full receipt-freeness. A voter who reveals the Paillier encryption randomness 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 re-encryption mix-nets or designated verifier proofs.

9. Implementation and Evaluation

9.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. RSA key generation uses the cryptography library for constant-time operations and side-channel resistance. All cryptographic values use frozen dataclasses with __slots__ for immutability. Credential comparisons use hmac.compare_digest for constant-time equality.

Separation of concerns. The two-layer architecture separates cryptographic primitives from election management. A cryptographer can review the 1,313-LOC cryptographic layer independently, while an election specialist can review the governance and lifecycle logic independently.

9.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:

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).

Second, homomorphic tallying is near-instant: 20ms for 1,000 ballots. The O(K) tallying cost has a negligible constant factor -- modular multiplication in Z_{n^2} is a single arithmetic operation per ballot.

Third, threshold decryption is O(M) and independent of K: 21-33ms for 3-of-5 regardless of voter count. Decryption latency does not grow with election size.

Distributed scalability model. For K voters across C cells with M-of-N threshold:

• Voting: O(K/C) per cell, parallel
• Per-cell tally: O(K/C) per cell, parallel
• Global aggregation: O(C) multiplications
• Decryption: O(M), independent of K and C

At 2048-bit security, K = 10,000, C = 100: per-voter ~1s client-side; per-cell tally ~16ms; global aggregation ~0.2ms; decryption ~170ms.

9.3 Comparison

Table 2: Feature comparison with existing E2E-V systems.

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

SOVEREIGN's primary advantages are distributed multi-jurisdictional trust, multiple election types, and machine-enforced contract governance. Its primary disadvantages relative to Belenios are the lack of UC security proofs and Coq-verified implementations, and relative to ElectionGuard the lack of deployment experience with real election hardware.

9.4 Test Coverage

The implementation includes 122 passing tests across 17 test files:

Cryptographic tests (7 files): 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.

Election tests (8 files): Types, eligibility, contracts, full lifecycle for all 7 election types, ballot recording with HMAC integrity, bulletin board operations, and result attestation.

End-to-end integration tests (2 files): Complete cryptographic flow from key generation through threshold decryption with 5 simulated voters (3 for A, 2 for B), verifying final counts; and complete manager-level flow through the ElectionManager API.

9.5 Recommended Parameters

Parameter	Development	Production	High Security
Paillier key	1024 bits (~80-bit)	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	20 rounds	40 rounds	64 rounds
SHA-256 (Fiat-Shamir)	256 bits	256 bits	256 bits
HMAC-SHA-256 (JCJ)	256 bits	256 bits	256 bits

9.6 Deployment Scenarios

Federal election. 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; states coordinate threshold decryption.

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

Military field election. 1 node (theater command), 3 service groups (brigades), 9 cells (battalions). Key shares: 5, threshold 3. Cells operate disconnected for days; synchronize when tactical network available.

International organization. 27 nodes (member states), 27 service groups, 54 cells (primary + backup). Key shares: 9 (3 per region), threshold 5. Requires participation from at least 2 geographic regions.

10. Discussion

10.1 Limitations

No formal verification. SOVEREIGN's security arguments are game-based reductions, not UC-framework proofs. UC proofs would provide composability guarantees important for a system combining Paillier, RSA blind signatures, Sigma protocols, and Shamir sharing. 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.

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 DLOG equality 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. A threshold HMAC construction 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.

Integer Shamir leakage. Shamir sharing over integers can leak information about secret magnitude through share magnitudes. The large random coefficients (drawn from [0, n*2^{128})) provide 128-bit statistical security, which is weaker than information-theoretic security over a finite field.

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

10.2 Deployment Considerations

Key ceremony security. The threshold key ceremony is the most security-critical phase. Each share holder should operate from a separate, ideally air-gapped machine. The compute_single_partial method runs on the share holder's machine; only the partial decryption result (never the share value) is transmitted. The ceremony coordinator never sees key shares.

Split-path verification. SOVEREIGN supports a model where the voter encrypts on one device and verifies the ZK proof on a second independent device. Only the ciphertext and proof are needed for verification -- no secrets.

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. This trail is sufficient for independent audit years after the election.

Incremental deployment. SOVEREIGN is best suited initially for organizational voting where the threat model is manageable. These deployments provide validation before scaling to political elections, which require additional infrastructure: paper audit trails, HSMs for key shares, and formal certification.

11. Ethical Considerations

Responsible development. SOVEREIGN is presented as a research contribution, not 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 prioritizes privacy through multiple mechanisms, but metadata leakage (timing, network patterns, device fingerprinting) could compromise privacy in practice. Deployments 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.

Dual-use concerns. The same tools protecting democratic elections could theoretically be misused for sham elections. The open-source nature, universal verifiability, and public bulletin board mitigate this risk.

Incremental deployment. We advocate first for low-stakes organizational votes with parallel paper ballots, then advisory elections, and only after extensive validation in binding political elections.

12. 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.

We have provided complete security analysis with reduction proofs for all five properties (ballot secrecy, individual verifiability, universal verifiability, eligibility, and coercion resistance), a detailed multi-cell tallying protocol with per-cell accumulation and cross-cell consensus verification, and an election lifecycle state machine with formally specified state transitions.

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 distributed architecture provides near-linear scalability with the number of cells.

Future work includes UC-framework security proofs, Chaum-Pedersen proofs for partial decryption verification, threshold HMAC for the coercion-resistance authority key, range proofs for weighted voting, re-encryption mix-nets for ballot-order privacy, and pilot deployments with organizational voting conducted in parallel with traditional methods.

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

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 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] System9 Engineering. "Formal Entity Contracts for Autonomous Agent Governance." Submitted to AAMAS 2026.

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

[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] D. Pointcheval, J. Stern. "Security Arguments for Digital Signatures and Blind Signatures." Journal of Cryptology, 13(3):361-396, 2000.

[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] A. Shamir. "How to Share a Secret." Communications of the ACM, 22(11):612-613, 1979.

[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] 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.

[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 under a unified cryptographic framework. 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 %
Ranked Choice	Rank per choice	Multi-round: eliminate lowest, redistribute	Majority after elimination
Approval	Any number of choices (0/1 each)	Independent homomorphic sum	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 threshold
Referendum	Binary yes/no (0/1)	Homomorphic sum	Exceeds passage threshold

Appendix B: Recommended Parameters

Parameter	Development	Production	High Security
Paillier key	1024 bits	2048 bits	3072 bits
RSA blind sig	2048 bits	2048 bits	4096 bits
Threshold (M,N)	(2,3)	(3,5)	(5,9)
Miller-Rabin	20	40	64
SHA-256	256 bits	256 bits	256 bits
HMAC-SHA-256	256 bits	256 bits	256 bits

Appendix C: 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
• D(E(42)) = 42
• D(E(17) * E(25) mod n^2) = 42

ZK proof structure:

• 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
• Verify(pi, E(0), pk) = REJECT (proof for E(1) fails against different ciphertext)

Threshold (5,3):

• D_partial(E(77), {share_1, share_2, share_3}) = 77
• D_partial(E(77), {share_1, share_3, share_5}) = 77

Blind signature:

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

---

End of E-Vote-ID submission draft.