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

SOVEREIGN Security Specification

Version: 1.0.0 Date: 2026-03-30 Authors: System9 Engineering Status: Draft -- Prepared for Independent Review

---

Abstract

This document formally specifies the security properties of the SOVEREIGN distributed cryptographic voting system built on the System9 platform. We define the threat model, state the security properties, describe the cryptographic protocols in detail, and provide reduction-based arguments that each property holds under standard cryptographic assumptions.

SOVEREIGN implements end-to-end verifiable (E2E-V) elections using Paillier homomorphic encryption for vote confidentiality and tallying, RSA blind signatures for anonymous voter token issuance, disjunctive Sigma protocols with Fiat-Shamir heuristic for zero-knowledge ballot validity proofs, Shamir secret sharing with Damgard-Jurik partial decryption for threshold key management, and HMAC-based Juels-Catalano-Jakobsson (JCJ) credentials for coercion resistance. Elections are governed by formal entity contracts following the AAMAS 2026 seven-tuple model, and the system distributes trust across independent cryptographic cells -- each representing a sovereign jurisdiction.

This specification is intended for review by cryptographers, election security researchers, and certification bodies. All protocol descriptions correspond to implemented, tested code in the System9 repository.

---

Table of Contents

1. Introduction
2. Threat Model
3. Security Definitions
4. Cryptographic Protocols
5. Protocol Composition
6. Security Arguments
7. Assumptions and Limitations
8. Implementation Notes
9. Notation and Conventions
10. References

---

1. Introduction

1.1 Motivation

Electronic voting systems face a fundamental tension: voters must be confident that their votes are counted correctly (verifiability), while no one -- including election administrators -- should be able to determine how any individual voted (ballot secrecy). These two requirements are in direct opposition, and satisfying both simultaneously requires sophisticated cryptographic protocols.

Existing end-to-end verifiable (E2E-V) systems such as ElectionGuard [Ben+19], Helios [Adi08], and Belenios [Cor+15] have made significant progress toward resolving this tension. However, they share several limitations:

1. Centralized architecture. Existing systems operate on a single server or a small cluster under unified administrative control. There is no mechanism for distributing trust across independent jurisdictions that do not share infrastructure or administrative authority.

2. Single election type. Most systems support only simple plurality or approval voting. Ranked-choice, weighted, super-majority, consensus, and referendum voting require separate implementations or post-hoc extensions.

3. No formal governance model. Election rules are encoded as procedural compliance requirements (human-enforced checklists) rather than machine-enforced contracts with well-defined input/output specifications, temporal bounds, and termination conditions.

4. No disconnected operation. Military, humanitarian, and disaster- response deployments require voting systems that function without persistent network connectivity. No existing E2E-V system addresses this requirement.

SOVEREIGN addresses all four limitations. It distributes trust across independent System9 cells (physical deployment units), supports seven election types through a unified cryptographic framework, governs elections through formal entity contracts following the AAMAS 2026 seven-tuple model, and operates in disconnected environments via delay-tolerant networking with eventual consistency.

1.2 Scope

This document specifies:

• The threat model under which SOVEREIGN operates (Section 2)
• Formal definitions of the security properties SOVEREIGN claims (Section 3)
• Complete descriptions of each cryptographic protocol (Section 4)
• How the protocols compose into a complete election lifecycle (Section 5)
• Reduction-based security arguments for each claimed property (Section 6)
• Assumptions, limitations, and areas for future work (Section 7)
• Implementation details relevant to security analysis (Section 8)

1.3 Relationship to Implementation

Every protocol described in this specification corresponds to implemented code in the System9 repository:

Protocol	Implementation File
Paillier encryption	app/core/security/crypto/voting/paillier.py
RSA blind signatures	app/core/security/crypto/voting/blind_signature.py
ZK ballot proofs	app/core/security/crypto/voting/zk_ballot_proof.py
Threshold key management	app/core/security/crypto/voting/threshold_keys.py
Homomorphic tallying	app/core/security/crypto/voting/homomorphic_tally.py
Decryption ceremony	app/core/security/crypto/voting/decryption_ceremony.py
Coercion resistance	app/core/security/crypto/voting/coercion_resistance.py
Election management	app/services/compute/intelligence/workflow/voting/election_manager.py
Ballot recording	app/services/compute/intelligence/workflow/voting/ballot_recorder.py
Bulletin board	app/services/compute/intelligence/workflow/voting/bulletin_board.py
Election contracts	app/services/compute/intelligence/workflow/voting/election_contract.py
Result attestation	app/services/compute/intelligence/workflow/voting/result_attestation.py
Eligibility checking	app/services/compute/intelligence/workflow/voting/eligibility_checker.py

The implementation has 122 passing tests across 17 test files, including two comprehensive end-to-end integration tests that exercise the full election lifecycle from key generation through threshold decryption.

---

2. Threat Model

2.1 System Model

SOVEREIGN operates on the System9 platform, which organizes deployments into a three-level hierarchy:

• Nodes are logical constructs that represent a jurisdiction (e.g., a state). A node can span multiple physical locations.
• Service groups are groupings of cells within a node (e.g., counties within a state). Service groups can span clouds and regions.
• Cells are the physical deployment units. Each cell runs its own services, databases, and cryptographic operations. A cell is the fundamental unit of trust -- compromising one cell does not compromise others.

An election is created on a node, distributed across service groups, and executed on individual cells. Voters interact with their local cell. Encrypted ballots are published to a public bulletin board that aggregates data from all participating cells.

2.2 Participants

The system involves the following participants:

1. Election Authority (EA). Creates the election, defines rules, holds the RSA signing key for blind token issuance, and holds the HMAC key for coercion-resistant credential validation. The EA is implemented as a System9 entity governed by a contract.

2. Key Share Holders (KH_1, ..., KH_N). N officials who each hold one share of the Paillier private key. Any M of N can cooperate to decrypt the tally. In a multi-cell deployment, share holders are distributed across cells so that no single cell holds M shares.

3. Voters (V_1, ..., V_K). Eligible entities (humans, agents, or organizations) that cast encrypted ballots. Each voter interacts with the system through a voting client.

4. Bulletin Board (BB). An append-only public log that stores encrypted ballots, ZK proofs, tallies, and attestations. Anyone can read the bulletin board; only authorized services can write.

5. Verifiers. Any party (voter, observer, auditor) who checks the correctness of the election by reading the bulletin board.

2.3 Adversary Capabilities

We consider a computationally bounded adversary A (probabilistic polynomial-time) with the following capabilities:

Network control. A can observe all network traffic, including all data published to the bulletin board. The bulletin board is public by design -- this is not a vulnerability but a feature enabling universal verifiability. A can also delay, reorder, or drop network messages between cells, though the delay-tolerant networking layer ensures eventual delivery.

Threshold corruption. A can corrupt up to M-1 of N key share holders. A corrupted share holder reveals their key share to A and follows A's instructions. This is the standard threshold adversary model. A cannot corrupt M or more share holders simultaneously.

Cell compromise. A can compromise individual cells, gaining access to all data stored on that cell. However, A cannot compromise all cells in a service group simultaneously. In particular, A cannot compromise cells holding a total of M or more key shares.

Voter coercion. A can coerce voters, demanding that they vote in a particular way and provide evidence of compliance. A can observe the voter's interaction with the voting system (including the credential used). The JCJ protocol addresses this threat. A cannot physically prevent the voter from casting a ballot.

Registration authority observation. A can observe the voter registration process but cannot compromise the registration authority's private signing key or HMAC key. If A could compromise the EA's keys, all security properties except universal verifiability would fail.

2.4 Adversary Limitations

A CANNOT:

1. Break Paillier encryption. We assume the Decisional Composite Residuosity (DCR) assumption holds. Specifically, given n = pq where p and q are large primes, 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.

2. Forge RSA signatures. We assume the RSA assumption holds. Given (n, e) and a message m, no PPT algorithm can compute s such that s^e = H(m) mod n without knowledge of d.

3. Find SHA-256 collisions. We model SHA-256 as a random oracle. No PPT algorithm can find m1 != m2 such that SHA-256(m1) = SHA-256(m2).

4. Distinguish HMAC from random. We assume HMAC-SHA-256 is a pseudorandom function (PRF). Given key k, the function HMAC_k(.) is computationally indistinguishable from a random function.

5. Corrupt the registration authority. The EA honestly issues at most one real credential per eligible voter and does not reveal its private keys.

2.5 Trust Assumptions

The following trust assumptions are necessary for SOVEREIGN's security:

T1. Honest registration authority. The EA issues exactly one real credential per eligible voter. If the EA issues multiple credentials to one voter or credentials to ineligible voters, eligibility verifiability fails. This is an inherent limitation of any voting system -- someone must determine eligibility.

T2. Honest threshold. At least M of N key share holders are honest. If fewer than M are honest, the adversary can reconstruct the private key and decrypt individual votes, breaking ballot secrecy.

T3. Random oracle model. SHA-256 behaves as a random oracle for the purpose of the Fiat-Shamir heuristic. This is a standard assumption in the literature, though it is known to be an idealization.

T4. Append-only bulletin board. The bulletin board is append-only -- entries cannot be modified or deleted after publication. In SOVEREIGN, this is enforced by the ballot recorder's HMAC hash chain, where each entry's signature incorporates the previous entry, making tampering detectable.

T5. Voter device integrity. The voter's device correctly encrypts the voter's intended choice. If the voter's device is compromised, it could encrypt a different choice than intended. This is the "trusted device problem" common to all electronic voting systems.

---

3. Security Definitions

We now formally define the security properties that SOVEREIGN claims. Each definition follows the standard simulation/game-based approach from the cryptographic literature.

3.1 Ballot Secrecy (BS)

Informal statement. No PPT adversary can determine how any individual voter voted, given access to the bulletin board, all encrypted ballots, and all public parameters.

Formal definition (IND-CPA style).

Consider the following game between a challenger C and adversary A:

1. C runs the election setup, generating Paillier keypair (pk, sk) and splitting sk into N shares with threshold M. C gives pk to A.
2. A adaptively submits ballot queries, receiving encrypted ballots and ZK proofs.
3. A submits a challenge: two ballots b_0 and b_1 for the same race, both valid (i.e., b_0, b_1 in {0, 1}).
4. C flips a fair coin beta <- {0, 1}, encrypts b_beta as c* = E(b_beta, r*) for random r*, generates ZK proof pi*, and returns (c*, pi*) to A.
5. A outputs a guess beta'.

A's advantage is:

Adv^BS_A = |Pr[beta' = beta] - 1/2|

Definition (Ballot Secrecy). SOVEREIGN provides ballot secrecy if for all PPT adversaries A (corrupting at most M-1 key share holders):

Adv^BS_A <= negl(lambda)

where lambda is the security parameter.

3.2 Individual Verifiability (IV)

Informal statement. A voter can verify that their ballot appears on the bulletin board and was included in the tally, using only their receipt and the public bulletin board.

Formal definition.

After casting a ballot, voter V receives a receipt:

R = (receipt_id, ballot_id, election_id, commitment_hash)

where commitment_hash = SHA-256(encrypted_payload).

Definition (Individual Verifiability). SOVEREIGN provides individual verifiability if, for all voters V with valid receipt R and bulletin board B:

Verify(R, B) = 1

if and only if there exists an entry e in B such that:
(a) e.entry_type = "ballot"
(b) e.data.ballot_id = R.ballot_id
(c) SHA-256(e.data.encrypted_payload) = R.commitment_hash

and for any adversary A that modifies B to produce B':

Pr[Verify(R, B') = 1 and B' differs from B on entry e] <= negl(lambda)

The second condition follows from the collision resistance of SHA-256.

3.3 Universal Verifiability (UV)

Informal statement. Any observer can verify that the published tally correctly reflects the encrypted ballots on the bulletin board, without knowing any secret keys.

Formal definition.

Given bulletin board B containing:

• Election definition E
• Encrypted ballots {(c_i, pi_i, token_i, sig_i)} for i = 1..K
• Encrypted tally T_j for each choice j
• Decryption results {(R_j, proof_j)} for each choice j

Definition (Universal Verifiability). SOVEREIGN provides universal verifiability if the following verification algorithm accepts with overwhelming probability for honest executions and rejects with overwhelming probability for dishonest executions:

UniversalVerify(B):
  // Step 1: Verify all ballot proofs
  for each (c_i, pi_i) on B:
    if VerifyBallotProof(pk, c_i, pi_i) = 0:
      return REJECT("invalid ballot proof for ballot i")

  // Step 2: Verify all anonymous tokens
  for each (token_i, sig_i) on B:
    if VerifyToken(token_i, sig_i, auth_n, auth_e) = 0:
      return REJECT("invalid token for ballot i")

  // Step 3: Verify homomorphic tally
  for each choice j:
    T_computed = product of c_i for all ballots selecting choice j
    if T_computed != T_j:
      return REJECT("tally mismatch for choice j")

  // Step 4: Verify decryption proofs
  for each choice j:
    if VerifyDecryptionProof(T_j, R_j, proof_j, pk) = 0:
      return REJECT("invalid decryption proof for choice j")

  // Step 5: Verify ballot count consistency
  if count(ballot entries on B) != tally.ballot_count:
    return REJECT("ballot count mismatch")

  return ACCEPT

3.4 Eligibility Verifiability (EV)

Informal statement. Only eligible voters can cast ballots that are counted in the tally.

Formal definition.

Definition (Eligibility Verifiability). SOVEREIGN provides eligibility verifiability if:

(a) Every counted ballot contains a valid anonymous token: a blind RSA signature from the election authority on a unique token value.

(b) Each anonymous token is used at most once. Duplicate token detection ensures that even if a voter obtains a valid token, they cannot vote twice.

(c) The election authority issues at most one token per eligible voter (trust assumption T1).

Formally, for any PPT adversary A that does not control the EA:

Pr[A produces a valid token without EA cooperation] <= negl(lambda)

This follows from the unforgeability of RSA signatures.

3.5 Coercion Resistance (CR)

Informal statement. A coerced voter can comply with the coercer's demands (showing them a credential and a vote) without their real vote being affected.

Formal definition (adapted from JCJ [JCJ05]).

Consider the following game:

1. The EA issues a real credential CR to voter V: CR = (credential_id, token, HMAC_k(credential_id || token)) where k is the EA's secret key.

2. V generates a fake credential CF: CF = (credential_id', token', HMAC_k'(credential_id' || token')) where k' is a random key chosen by V.

3. A (the coercer) receives one of CR or CF (chosen uniformly at random) and must determine which.

Definition (Coercion Resistance). SOVEREIGN provides coercion resistance if for all PPT adversaries A that do not know the EA's key k:

|Pr[A(CR) = "real"] - Pr[A(CF) = "real"]| <= negl(lambda)

During tallying, the EA uses k to recompute the HMAC and filter: only ballots with real credentials (where the HMAC verifies under k) are counted. This filtering happens in aggregate -- the EA does not reveal which individual credentials are real or fake.

3.6 Receipt-Freeness (RF) -- Partial

Note. SOVEREIGN provides coercion resistance through the JCJ protocol but does NOT provide full receipt-freeness. A voter who reveals the randomness used in their Paillier encryption can prove to a third party how they voted. The JCJ mechanism mitigates this by allowing the voter to use a fake credential, so even if the voter proves a vote was cast with a specific credential, the coercer cannot verify whether the credential is real.

This is a known trade-off. Full receipt-freeness would require additional mechanisms such as re-encryption mix-nets or designated verifier proofs, which are left for future work.

---

4. Cryptographic Protocols

4.1 Paillier Homomorphic Encryption

The Paillier cryptosystem [Pai99] is an additive homomorphic public-key encryption scheme. It is the foundation of SOVEREIGN's ballot secrecy and verifiable tallying.

4.1.1 Key Generation

Algorithm: PaillierKeyGen(lambda)

1. Generate two random primes p, q each of bit-length lambda/2, where p != q.
2. Compute n = p * q and n^2 = n * n.
3. Set g = n + 1. (This is the standard simplification; when g = n + 1, the encryption formula simplifies significantly.)
4. Compute lambda_val = lcm(p - 1, q - 1).
5. Compute mu = L(g^{lambda_val} mod n^2)^{-1} mod n, where L(x) = (x - 1) / n.
6. Return public key pk = (n, n^2, g, lambda, mu) and private key sk = (lambda_val, mu, pk).

Implementation note. Primes are generated using Python's secrets.randbits with 20-round Miller-Rabin primality testing. The minimum key size is 1024 bits (for testing); production use requires 2048 bits (128-bit security level).

4.1.2 Encryption

Algorithm: Encrypt(pk, m)

Input: Public key pk = (n, n^2, g), plaintext m in Z_n. Output: Ciphertext c in Z_{n^2}.

1. Generate random r <- Z*_n (r coprime to n).
2. Compute g^m mod n^2:
   • Since g = n + 1, by the binomial theorem: (n + 1)^m mod n^2 = 1 + n*m mod n^2
   • This avoids expensive modular exponentiation.
3. Compute r^n mod n^2.
4. Return c = (1 + n*m) * r^n mod n^2.

Encrypt-with-randomness variant. For ZK proof generation, the prover needs to know the randomness r. The encrypt_with_randomness function returns (c, r).

4.1.3 Decryption

Algorithm: Decrypt(sk, c)

Input: Private key sk = (lambda_val, mu, pk), ciphertext c in Z_{n^2}. Output: Plaintext m in Z_n.

1. Compute x = c^{lambda_val} mod n^2.
2. Compute L(x) = (x - 1) / n.
3. Return m = L(x) * mu mod n.

Correctness proof.

We verify that Decrypt(sk, Encrypt(pk, m)) = m.

c = (1 + nm) * r^n mod n^2
c^{lambda} = ((1 + nm) * r^n)^{lambda} mod n^2
           = (1 + nm)^{lambda} * r^{n*lambda} mod n^2

By Carmichael's theorem, r^{lcm(p-1,q-1)} = 1 mod n (when gcd(r,n)=1), so r^{n*lambda} = (r^{lambda})^n = 1 mod n^2 (by a lifting argument).

c^{lambda} = (1 + nm)^{lambda} mod n^2
           = 1 + nm*lambda mod n^2    (binomial, higher terms vanish mod n^2)

L(c^{lambda}) = (1 + nm*lambda - 1) / n = m*lambda mod n

m*lambda * mu mod n = m * lambda * (L(g^{lambda}))^{-1} mod n

Since g = n+1, g^{lambda} = 1 + n*lambda mod n^2, so L(g^{lambda}) = lambda. Therefore mu = lambda^{-1} mod n, and m * lambda * lambda^{-1} = m mod n.

4.1.4 Homomorphic Addition

Property. For any plaintexts m1, m2 and corresponding ciphertexts c1 = E(m1, r1), c2 = E(m2, r2):

c1 * c2 mod n^2 = E(m1 + m2, r1 * r2 mod n)

Proof.

c1 * c2 = (1 + n*m1) * r1^n * (1 + n*m2) * r2^n mod n^2
        = (1 + n*m1)(1 + n*m2) * (r1*r2)^n mod n^2
        = (1 + n*(m1+m2) + n^2*m1*m2) * (r1*r2)^n mod n^2
        = (1 + n*(m1+m2)) * (r1*r2)^n mod n^2
        = E(m1 + m2, r1*r2)

(The n^2m1m2 term vanishes modulo n^2.)

This property is used to tally votes without decryption: multiply all encrypted votes for a choice to get an encryption of the vote count.

4.1.5 Security: Semantic Security under DCR

Theorem (Paillier [Pai99]). The Paillier cryptosystem is IND-CPA secure under the Decisional Composite Residuosity (DCR) assumption.

DCR Assumption. Given n = pq for primes p, q, the following distributions are computationally indistinguishable:

D_0 = {x^n mod n^2 : x <- Z*_{n^2}}
D_1 = {(1 + n)^m * x^n mod n^2 : m <- Z_n, x <- Z*_{n^2}}

Proof sketch. Suppose there exists a PPT adversary A that breaks IND-CPA security of Paillier with non-negligible advantage epsilon. We construct a distinguisher D for DCR:

1. D receives a challenge z from DCR.
2. D sets up a Paillier instance with the given n.
3. When A submits challenge plaintexts m0, m1:
   • D computes c* = z * (1 + n)^{m_beta} mod n^2 for random beta.
   • If z is from D_0 (n-th residue), then c* is a valid encryption of m_beta plus random offset -- A cannot determine beta.
   • If z is from D_1 (non-residue), then c* encodes information about beta that A can exploit.
4. D uses A's guess to distinguish D_0 from D_1.

A's advantage epsilon translates directly to D's advantage in distinguishing DCR, contradicting the assumption. Therefore epsilon must be negligible.

4.1.6 Protocol Pseudocode

Algorithm 1: Paillier.KeyGen(lambda)
---------------------------------------
Input:  Security parameter lambda (key size in bits)
Output: (pk, sk) keypair

 1.  p <- RandomPrime(lambda/2)
 2.  q <- RandomPrime(lambda/2) where q != p
 3.  n <- p * q
 4.  g <- n + 1
 5.  lambda_val <- lcm(p - 1, q - 1)
 6.  x <- g^lambda_val mod n^2
 7.  mu <- L(x)^{-1} mod n     where L(u) = (u - 1)/n
 8.  pk <- (n, n^2, g, mu)
 9.  sk <- (lambda_val, mu, pk)
10.  return (pk, sk)

Algorithm 2: Paillier.Encrypt(pk, m)
---------------------------------------
Input:  Public key pk = (n, n^2, g, mu), plaintext m in Z_n
Output: Ciphertext c in Z*_{n^2}

 1.  r <- RandomCoprime(n)
 2.  c <- (1 + n*m) * r^n mod n^2
 3.  return c

Algorithm 3: Paillier.Decrypt(sk, c)
---------------------------------------
Input:  Private key sk = (lambda_val, mu, pk), ciphertext c
Output: Plaintext m in Z_n

 1.  x <- c^lambda_val mod n^2
 2.  m <- L(x) * mu mod n
 3.  return m

Algorithm 4: Paillier.Add(pk, c_1, c_2)
---------------------------------------
Input:  Public key pk, ciphertexts c_1 = E(m_1), c_2 = E(m_2)
Output: c = E(m_1 + m_2)

 1.  c <- c_1 * c_2 mod n^2
 2.  return c

4.2 RSA Blind Signatures

RSA blind signatures [Cha83] enable the election authority to sign a voter's token without seeing it. After unblinding, the voter holds a valid signature that cannot be linked back to the signing session.

4.2.1 Key Generation

The election authority generates a standard RSA keypair:

1. Generate primes p, q (2048-bit minimum).
2. Compute n = p * q.
3. Choose e = 65537 (standard public exponent).
4. Compute d = e^{-1} mod phi(n), where phi(n) = (p-1)(q-1).
5. Public key: (n, e). Private key: d.

Implementation note. SOVEREIGN uses the cryptography library's RSA key generation for the authority keypair, ensuring constant-time operations and side-channel resistance.

4.2.2 Token Generation

The voter generates a random 256-bit token:

token = random_hex(32)  // 256 bits of entropy

4.2.3 Blinding

Algorithm: Blind(token, n, e)

1. Compute token_hash = SHA-256(token).
2. Convert to integer: token_int = int(token_hash, 16) mod n.
3. Generate random blinding factor r <- Z*_n (coprime to n).
4. Compute blinded = token_int * r^e mod n.
5. Return (blinded, r, token_hash).

Purpose. The blinding factor r^e "masks" the token. The authority sees blinded but cannot recover token_int because r is unknown.

4.2.4 Signing

Algorithm: Sign(blinded, n, d)

The authority computes:

blinded_sig = blinded^d mod n

The authority does not see the original token -- only the blinded value.

4.2.5 Unblinding

Algorithm: Unblind(blinded_sig, r, n)

The voter computes:

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

Correctness.

sig = blinded_sig * r^{-1} mod n
    = blinded^d * r^{-1} mod n
    = (token_int * r^e)^d * r^{-1} mod n
    = token_int^d * r^{ed} * r^{-1} mod n
    = token_int^d * r * r^{-1} mod n    (since r^{ed} = r mod n)
    = token_int^d mod n

This is a standard RSA signature on token_int.

4.2.6 Verification

Algorithm: Verify(token, sig, n, e)

1. Compute token_hash = SHA-256(token).
2. Compute token_int = int(token_hash, 16) mod n.
3. Compute computed = sig^e mod n.
4. Return computed == token_int.

Anyone can verify: the voter, the bulletin board, any auditor.

4.2.7 Security Properties

Unforgeability. Under the RSA assumption, no PPT adversary can produce a valid (token, sig) pair without interacting with the authority's signing oracle. This follows from the unforgeability of RSA signatures.

Unlinkability. The blinding factor r is chosen uniformly at random from Z_n. For any fixed token_int, the distribution of blinded = token_int * r^e mod n is uniform over Z_n (since multiplication by r^e is a bijection on Z*_n). Therefore, the authority gains no information about token_int from observing blinded.

Formal statement. For any two tokens t0, t1 and their corresponding blinded values b0, b1:

{Blind(t0, n, e).blinded : r <- Z*_n} ≡ {Blind(t1, n, e).blinded : r <- Z*_n}

where ≡ denotes statistical equivalence (in fact, identical distributions).

4.3 Zero-Knowledge Ballot Proof

The ZK ballot proof demonstrates that an encrypted ballot contains a valid vote (0 or 1) without revealing which. This prevents ballot stuffing (encrypting a value larger than 1) and negative voting (encrypting a negative value).

4.3.1 Protocol Overview

The protocol is a disjunctive Sigma protocol (OR-proof) made non-interactive via the Fiat-Shamir heuristic [FS86].

Given ciphertext c = E(b, r) where b in {0, 1}, define:

c_0 = c                     // "hypothesis: c encrypts 0"
c_1 = c * g^{-1} mod n^2   // "hypothesis: c encrypts 1"

If b = 0, then c_0 = r^n mod n^2 (the prover knows the n-th root r). If b = 1, then c_1 = r^n mod n^2 (the prover knows the n-th root r).

The prover demonstrates knowledge of the n-th root of EITHER c_0 OR c_1, without revealing which. By the special soundness property, this proves that c encrypts 0 or 1.

4.3.2 Proof Generation

Algorithm: ProveValidBallot(pk, b, c, r)

Input: Public key pk, plaintext b in {0,1}, ciphertext c, randomness r. Output: Proof pi = (a0, a1, e0, e1, z0, z1).

Case b = 0 (real proof for branch 0, simulated for branch 1):

1. Simulate branch 1:

   • Choose e1_sim <- Z_{2^256} uniformly at random.
   • Choose z1_sim <- Z*_n uniformly at random.
   • Compute a1 = z1_sim^n * c_1^{-e1_sim} mod n^2.

2. Real proof for branch 0:

   • Choose w <- Z*_n uniformly at random.
   • Compute a0 = w^n mod n^2.

3. Fiat-Shamir challenge:

   • e_total = H("SOVEREIGN-ZK-v1" || n || g || c || a0 || a1) mod 2^{256}.
   • e0 = (e_total - e1_sim) mod 2^{256}.

4. Response:

   • z0 = w * r^{e0} mod n.

5. Return (a0, a1, e0, e1_sim, z0, z1_sim).

Case b = 1: Symmetric -- simulate branch 0, real proof for branch 1.

4.3.3 Proof Verification

Algorithm: VerifyBallotProof(pk, c, pi)

Input: Public key pk, ciphertext c, proof pi = (a0, a1, e0, e1, z0, z1). Output: ACCEPT or REJECT.

1. Compute c_0 = c mod n^2 and c_1 = c * g^{-1} mod n^2.

2. Challenge check: e_total = H("SOVEREIGN-ZK-v1" || n || g || c || a0 || a1) mod 2^{256}. Verify (e0 + e1) mod 2^{256} = e_total. If not, REJECT.

3. Branch 0 check: Verify z0^n = a0 * c_0^{e0} mod n^2. If not, REJECT.

4. Branch 1 check: Verify z1^n = a1 * c_1^{e1} mod n^2. If not, REJECT.

5. ACCEPT.

4.3.4 Security Properties

Zero-knowledge. For the FALSE branch (the one where the prover does not know the witness), the proof is simulated: the prover freely chooses (e, z) and derives a to satisfy the verification equation. The distribution of simulated proofs is identical to the distribution of real proofs (both are uniformly random tuples satisfying the same algebraic relation). Therefore, a verifier cannot distinguish which branch is real and which is simulated.

Formal statement (simulator). There exists a PPT simulator S that, given only pk and c (without b or r), produces transcripts (a0, a1, e0, e1, z0, z1) that are identically distributed to real proof transcripts. S works by:

1. Choose e0, z0, e1, z1 uniformly at random.
2. Compute a0 = z0^n * c_0^{-e0} mod n^2.
3. Compute a1 = z1^n * c_1^{-e1} mod n^2.
4. Program the random oracle: H(..., a0, a1) = (e0 + e1) mod 2^{256}.

In the random oracle model, this simulation is perfect.

Soundness. By the special soundness property of Sigma protocols, if a prover can produce two accepting transcripts for the same commitment (a0, a1) but different challenges, then the prover can extract the n-th root of c_0 or c_1. This means c encrypts 0 or 1.

More precisely: if c encrypts some m not in {0, 1}, then neither c_0 nor c_1 is an n-th residue modulo n^2. The prover cannot produce a valid z for the real branch, and the Fiat-Shamir challenge binds the two branches together so that the prover cannot simulate both.

By the soundness of the Fiat-Shamir transform in the random oracle model [PS00], the non-interactive proof is sound.

Domain separation. The hash input is prefixed with "SOVEREIGN-ZK-v1" to prevent cross-protocol attacks where a proof generated for one purpose is replayed in another context.

4.3.5 Protocol Pseudocode

Algorithm 5: ZKBallot.Prove(pk, b, c, r)
---------------------------------------
Input:  pk = (n, n^2, g), plaintext b in {0,1},
        ciphertext c = E(b, r), randomness r
Output: Proof pi = (a_0, a_1, e_0, e_1, z_0, z_1)

 1.  g_inv <- g^{-1} mod n^2
 2.  c_0 <- c                          // hypothesis: c encrypts 0
 3.  c_1 <- c * g_inv mod n^2          // hypothesis: c encrypts 1
 4.  if b = 0:
 5.    // Simulate branch 1 (false branch)
 6.    e_1 <- Random(Z_n)
 7.    z_1 <- Random(Z_n)
 8.    a_1 <- z_1^n * c_1^{-e_1} mod n^2
 9.    // Real proof for branch 0 (true branch)
10.    w <- Random(Z_n)
11.    a_0 <- w^n mod n^2
12.    e_total <- H("SOVEREIGN-ZK-v1" || n || g || c || a_0 || a_1) mod n
13.    e_0 <- e_total - e_1 mod n
14.    z_0 <- w * r^{e_0} mod n
15.  else:
16.    // Simulate branch 0 (false branch)
17.    e_0 <- Random(Z_n)
18.    z_0 <- Random(Z_n)
19.    a_0 <- z_0^n * c_0^{-e_0} mod n^2
20.    // Real proof for branch 1 (true branch)
21.    w <- Random(Z_n)
22.    a_1 <- w^n mod n^2
23.    e_total <- H("SOVEREIGN-ZK-v1" || n || g || c || a_0 || a_1) mod n
24.    e_1 <- e_total - e_0 mod n
25.    z_1 <- w * r^{e_1} mod n
26.  return (a_0, a_1, e_0, e_1, z_0, z_1)

Algorithm 6: ZKBallot.Verify(pk, c, pi)
---------------------------------------
Input:  pk, ciphertext c, proof pi = (a_0, a_1, e_0, e_1, z_0, z_1)
Output: accept/reject

 1.  g_inv <- g^{-1} mod n^2
 2.  c_0 <- c; c_1 <- c * g_inv mod n^2
 3.  e_total <- H("SOVEREIGN-ZK-v1" || n || g || c || a_0 || a_1) mod n
 4.  if (e_0 + e_1) mod n != e_total: return reject
 5.  if z_0^n mod n^2 != a_0 * c_0^{e_0} mod n^2: return reject
 6.  if z_1^n mod n^2 != a_1 * c_1^{e_1} mod n^2: return reject
 7.  return accept

4.3.6 Blind Signature Protocol Pseudocode

Algorithm 7: BlindSig.Blind(token, n, e)
---------------------------------------
Input:  Token string, RSA public key (n, e)
Output: (blinded, r, token_hash)

 1.  token_hash <- SHA-256(token)
 2.  token_int <- int(token_hash) mod n
 3.  r <- RandomCoprime(n)
 4.  blinded <- token_int * r^e mod n
 5.  return (blinded, r, token_hash)

Algorithm 8: BlindSig.Sign(blinded, n, d)
---------------------------------------
Input:  Blinded value, RSA private key (n, d)
Output: Blinded signature

 1.  blinded_sig <- blinded^d mod n
 2.  return blinded_sig

Algorithm 9: BlindSig.Unblind(blinded_sig, r, n)
---------------------------------------
Input:  Blinded signature, blinding factor r, modulus n
Output: Unblinded signature sig

 1.  sig <- blinded_sig * r^{-1} mod n
 2.  return sig

Algorithm 10: BlindSig.Verify(token, sig, n, e)
---------------------------------------
Input:  Token, signature, RSA public key (n, e)
Output: accept/reject

 1.  token_hash <- SHA-256(token)
 2.  token_int <- int(token_hash) mod n
 3.  computed <- sig^e mod n
 4.  if computed = token_int: return accept
 5.  return reject

4.3.7 Threshold Protocol Pseudocode

Algorithm 11: Threshold.Split(sk, N, M)
---------------------------------------
Input:  Private key sk (secret = lambda_val), total shares N,
        threshold M
Output: N key shares

 1.  B <- n * 2^{128}                // coefficient bound
 2.  f(x) <- lambda_val + sum_{i=1}^{M-1} a_i * x^i
             where each a_i <- Random([0, B))
 3.  for i = 1 to N:
 4.    share_i <- (i, f(i), M, N, n)    // evaluated over integers
 5.  return {share_1, ..., share_N}

Algorithm 12: Threshold.PartialDecrypt(share_i, c, pk)
---------------------------------------
Input:  Key share (i, s_i, M, N, n), ciphertext c, public key pk
Output: Partial decryption partial_i, commitment hash

 1.  Delta <- N!
 2.  partial_i <- c^{2 * Delta * s_i} mod n^2
 3.  commitment <- SHA-256(i || partial_i || c)
 4.  return (partial_i, commitment)

Algorithm 13: Threshold.Combine(partials, metadata, pk)
---------------------------------------
Input:  At least M partial decryptions, share metadata, public key pk
Output: Decrypted plaintext m

 1.  Delta <- N!
 2.  for each share i in the M-subset:
 3.    mu_i <- Delta * product_{j != i} (0 - x_j) / (x_i - x_j)
       // exact integer division since all denominators divide N!
 4.  combined <- product_i (partial_i ^ mu_i) mod n^2
 5.  l_val <- (combined - 1) / n
 6.  scale <- 2 * Delta^2 mod n
 7.  m <- l_val * scale^{-1} * mu mod n
 8.  return m

Algorithm 14: JCJ.IssueReal(voter_id, authority_key)
---------------------------------------
Input:  Voter ID, authority's HMAC key k
Output: Real credential CR

 1.  credential_id <- UUID4()
 2.  token <- RandomHex(32)          // 256 bits
 3.  mac <- HMAC-SHA-256(k, credential_id || ":" || token)
 4.  return (credential_id, voter_id, token, mac, is_real=True)

Algorithm 15: JCJ.GenerateFake(voter_id)
---------------------------------------
Input:  Voter ID
Output: Fake credential CF (structurally identical to real)

 1.  credential_id <- UUID4()
 2.  token <- RandomHex(32)
 3.  fake_key <- RandomHex(32)
 4.  mac <- HMAC-SHA-256(fake_key, credential_id || ":" || token)
 5.  return (credential_id, voter_id, token, mac, is_real=False)

Algorithm 16: JCJ.Validate(credential, authority_key)
---------------------------------------
Input:  Credential (id, token, mac), authority's HMAC key k
Output: real/fake

 1.  expected <- HMAC-SHA-256(k, id || ":" || token)
 2.  if ConstantTimeEqual(expected, mac): return real
 3.  return fake

4.4 Threshold Key Management and Partial Decryption

SOVEREIGN uses Shamir's Secret Sharing [Sha79] to split the Paillier private key into N shares, where any M shares can reconstruct the key (or, preferably, cooperate to decrypt without reconstruction).

4.4.1 Secret Sharing over the Integers

Unlike standard Shamir sharing over a finite field F_p, SOVEREIGN evaluates the sharing polynomial over the integers. This is necessary because the partial decryption protocol requires exact arithmetic in the exponent -- modular reduction would introduce errors.

Algorithm: SplitKey(sk, N, M)

Input: Private key sk with secret = lambda_val, total shares N, threshold M. Output: N key shares.

1. Let n = pk.n and set coefficient bound B = n * 2^{128}. The factor 2^{128} provides statistical security: the random coefficients are so much larger than the secret that the secret is information-theoretically hidden.

2. Generate random polynomial: f(x) = secret + a_1x + a_2x^2 + ... + a_{M-1}*x^{M-1} where each a_i <- [0, B).

3. Evaluate: share_i = f(i) for i = 1, 2, ..., N.

4. Return shares {(i, share_i, M, N, n)}.

Information-theoretic security. For any set S of fewer than M shares, and any two possible secrets s, s', there exist polynomials consistent with S that yield s and s' respectively. This is the standard information-theoretic security of Shamir sharing, extended to the integer setting by the large coefficient bound.

4.4.2 Key Reconstruction (Direct)

Algorithm: ReconstructKey(shares, pk)

Input: At least M shares, public key pk. Output: Reconstructed private key sk.

Uses the Delta trick for exact integer Lagrange interpolation:

1. Let Delta = N! (factorial of total shares).
2. For each share i, compute the Lagrange basis coefficient: mu_i = Delta * product_{j != i} (0 - x_j) / (x_i - x_j) This is an exact integer because all denominators divide N!.
3. Compute Delta * f(0) = sum_i (share_i * mu_i).
4. Divide by Delta to recover f(0) = secret.

Security note. This method reconstructs the full private key in memory on the combiner's machine. It is provided for simplicity but is NOT recommended for production use. The partial decryption method (Section 4.4.3) is preferred because the full key is never assembled.

4.4.3 Partial Decryption (Damgard-Jurik Scheme)

Algorithm: ComputePartialDecryption(share_i, c, pk)

Each share holder computes their partial decryption locally:

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

where Delta = N!.

The factor of 2 * Delta ensures that the Lagrange coefficients in the combination step are exact integers, avoiding the need to compute modular inverses of unknown group order.

The share holder also computes a commitment hash for audit:

commitment = SHA-256(share_id || partial_i || c)

Security. The partial decryption partial_i = c^{2Deltas_i} reveals no information about s_i beyond what is already implied by the public key and ciphertext. This is because computing s_i from partial_i requires solving the discrete logarithm problem in Z*_{n^2}, which is at least as hard as factoring n.

Algorithm: CombinePartialDecryptions(partials, shares_metadata, pk)

Input: At least M partial decryptions, share metadata, public key. Output: Decrypted plaintext.

1. Let Delta = N!. Compute integer Lagrange coefficients: mu_i = Delta * product_{j != i} (0 - x_j) / (x_i - x_j)

2. Combine in the exponent: combined = product_i (partial_i ^ mu_i) mod n^2

   This equals c^{2 * Delta^2 * lambda_val} mod n^2.

3. Apply the L function: l_val = (combined - 1) / n

4. Recover plaintext: scale = 2 * Delta^2 mod n plaintext = l_val * scale^{-1} * mu mod n

Correctness.

combined = product(partial_i ^ mu_i) mod n^2
         = product(c^{2*Delta*s_i*mu_i}) mod n^2
         = c^{2*Delta * sum(s_i * mu_i)} mod n^2
         = c^{2*Delta * Delta * f(0)} mod n^2
         = c^{2 * Delta^2 * lambda_val} mod n^2

L(combined) = L(c^{2*Delta^2*lambda}) = 2*Delta^2 * m * lambda mod n
(using the same derivation as standard Paillier decryption)

plaintext = L(combined) * (2*Delta^2)^{-1} * mu mod n
          = 2*Delta^2 * m * lambda * (2*Delta^2)^{-1} * lambda^{-1} mod n
          = m mod n

Key never reconstructed. At no point does any party compute or hold lambda_val. Each share holder computes c^{2Deltas_i} on their own machine, and only the partial results are sent to the combiner. The combiner performs exponentiation and multiplication but never has access to any individual s_i.

4.4.4 Security of Threshold Scheme

Theorem. For any coalition of fewer than M share holders, the joint distribution of their shares and partial decryptions reveals no information about the secret lambda_val beyond what is implied by the public key.

Proof sketch. The shares are evaluations of a random polynomial of degree M-1 over the integers. By the information-theoretic security of Shamir sharing (extended to integers via the large coefficient bound), any M-1 shares are consistent with every possible value of f(0). The partial decryptions partial_i = c^{2Deltas_i} are deterministic functions of the shares, so they carry no additional information.

More precisely: given any M-1 shares {s_j : j in S} and a candidate secret s*, there exists a unique polynomial f* of degree M-1 that passes through all M-1 points and f*(0) = s*. The probability that a random polynomial with coefficients in [0, n2^{128}) yields the observed shares is the same for all s (up to statistical distance 2^{-128}). Therefore, the M-1 shares reveal no information about the secret.

4.5 Coercion-Resistant Credentials (JCJ Protocol)

The JCJ protocol [JCJ05] enables voters to resist coercion by generating fake credentials that are indistinguishable from real ones.

4.5.1 Credential Model

In SOVEREIGN's simplified JCJ implementation, credentials are HMAC-based rather than public-key-based:

• Real credential: HMAC computed with the election authority's secret key k.
• Fake credential: HMAC computed with a random key k' chosen by the voter.

A credential consists of:

(credential_id, token, mac)

where:

• credential_id is a random UUID
• token is a random 256-bit hex string
• mac = HMAC-SHA-256(k, credential_id || ":" || token)

For real credentials, k is the authority's key. For fake credentials, k is a random key chosen by the voter.

4.5.2 Real Credential Issuance

Algorithm: IssueRealCredential(voter_id)

Executed by the election authority:

1. Generate credential_id = UUID4().
2. Generate token = random_hex(32).
3. Compute mac = HMAC-SHA-256(authority_key, credential_id || ":" || token).
4. Return (credential_id, voter_id, token, mac, is_real=True).

The is_real flag is stored locally by the voter and NEVER transmitted.

4.5.3 Fake Credential Generation

Algorithm: GenerateFakeCredential(voter_id)

Executed by the voter (no authority involvement):

1. Generate credential_id = UUID4().
2. Generate token = random_hex(32).
3. Generate fake_key = random_hex(32).
4. Compute mac = HMAC-SHA-256(fake_key, credential_id || ":" || token).
5. Return (credential_id, voter_id, token, mac, is_real=False).

The credential looks structurally identical to a real one. Both credential_id and token are random. The mac is a 256-bit hex string in both cases.

4.5.4 Credential Validation During Tally

Algorithm: ValidateCredential(credential, authority_key)

Executed by the EA during the tallying phase:

1. Compute expected_mac = HMAC-SHA-256(authority_key, credential_id || ":" || token).
2. Compare expected_mac with credential.mac using constant-time comparison (hmac.compare_digest).
3. If match, credential is real. If not, credential is fake.

Batch filtering: The EA calls filter_valid_ballots which iterates over all credentials and returns only the credential_ids that pass validation. The COUNT of filtered credentials is not revealed to prevent the coercer from inferring information.

4.5.5 Security Properties

Indistinguishability. Without the authority's key k, the HMAC value is computationally indistinguishable from random by the PRF property of HMAC-SHA-256. A fake credential's HMAC (computed with random k') is also indistinguishable from random. Therefore:

{HMAC_k(m)} ≈_c {HMAC_{k'}(m')} ≈_c {uniform random}

where ≈_c denotes computational indistinguishability.

Formal statement. For any PPT adversary A that does not know k:

|Pr[A(cred_real) = 1] - Pr[A(cred_fake) = 1]| <= negl(lambda)

This follows directly from the PRF security of HMAC-SHA-256.

Comparison with original JCJ. The original JCJ protocol uses public-key encryption (ElGamal) for credentials, providing information-theoretic hiding rather than computational hiding. Our HMAC-based variant provides computational hiding, which is sufficient for practical security but is a weaker guarantee. The trade-off is simplicity: HMAC credentials require no additional public-key infrastructure beyond what is already used for blind signatures.

4.5.6 Limitations of HMAC-based JCJ

1. Authority key secrecy. If the authority's key k is compromised, the adversary can validate credentials and determine which are real. This is a stronger requirement than the original JCJ, where credential validation uses a distributed threshold decryption.

2. Single authority. The current implementation uses a single authority key. A distributed version would split k into shares using a threshold HMAC construction.

3. Revocation. There is no mechanism to revoke a real credential and issue a replacement. If a voter's real credential is compromised, it remains valid.

---

5. Protocol Composition

5.1 Election Lifecycle

The protocols compose into a complete election lifecycle with seven phases. Each phase is governed by the election contract (Section 5.3).

Phase 1: Setup

1. The election authority creates an Election object specifying:

   • Election type (simple majority, super majority, ranked choice, approval, weighted, consensus, referendum)
   • Privacy level (public, private, anonymous)
   • Races and choices
   • Eligible entity IDs, types, and organizations
   • Temporal bounds (opens_at, closes_at)
   • Quorum and threshold requirements

2. For anonymous elections, generate cryptographic keys: a. Generate Paillier keypair: (pk, sk) <- PaillierKeyGen(2048). b. Split sk into N shares with threshold M: {s_1, ..., s_N} <- SplitKey(sk, N, M). c. Distribute shares to key share holders on separate cells. d. Destroy sk (it must not be stored anywhere). e. Generate RSA keypair for blind signatures: (auth_n, auth_e, auth_d).

3. Build an entity contract governing the election (Section 5.3).

4. Publish the election definition to the bulletin board.

5. Transition election status: DRAFT -> OPEN.

Phase 2: Registration

For each eligible voter:

1. The eligibility checker verifies:

   • The voter has not already registered.
   • The voter's entity type matches the election's eligible types.
   • The voter's entity ID appears in the eligible list (if specified).
   • The voter's entity exists in the entity manager (if available).

2. For anonymous elections: a. The EA issues a real credential: CR <- IssueRealCredential(voter_id). b. The voter receives CR and stores it securely. c. Optionally, the voter generates fake credentials for coercion resistance: CF <- GenerateFakeCredential(voter_id).

3. For anonymous elections with blind tokens: a. The voter generates a random token: t <- GenerateToken(). b. The voter blinds the token: (blinded, r, hash) <- Blind(t, auth_n, auth_e). c. The voter sends blinded to the EA. d. The EA signs: blind_sig <- Sign(blinded, auth_n, auth_d). e. The voter unblinds: sig <- Unblind(blind_sig, r, auth_n). f. The voter verifies: VerifyToken(t, sig, auth_n, auth_e) = 1. g. The voter stores (t, sig) as their anonymous token.

Phase 3: Voting

For each vote:

1. Encrypt the ballot. For each race and each choice: a. Let v = 1 if the voter selects this choice, v = 0 otherwise. b. Encrypt: (c_v, r_v) <- EncryptWithRandomness(pk, v). c. Generate ZK proof: pi_v <- ProveValidBallot(pk, v, c_v, r_v).

2. Assemble the encrypted ballot. EncryptedBallotSelection = (race_id, choice_id, c_v, pi_v).

3. Attach the anonymous token. The ballot includes (token, signature) from the blind signature protocol.

4. Submit the ballot. The ballot recorder writes the encrypted ballot to the append-only journal with an HMAC integrity signature.

5. Issue a receipt. The voter receives VoterReceipt = (receipt_id, ballot_id, election_id, SHA-256(encrypted_payload), timestamp).

6. Publish to bulletin board. The encrypted ballot (with ZK proof, anonymous token, and commitment hash) is published. No voter identity is published.

Phase 4: Closing

1. The election authority transitions the election: OPEN -> CLOSED. No further ballots are accepted.

2. For coercion-resistant elections: The EA filters credentials: valid_ids <- FilterValidBallots(all_credentials). Only ballots with real credentials proceed to tallying.

Phase 5: Tallying

1. Verify all ballots. For each encrypted ballot: a. Verify the ZK proof: VerifyBallotProof(pk, c, pi) = 1. b. Verify the anonymous token: VerifyToken(t, sig, auth_n, auth_e) = 1. c. Reject invalid ballots.

2. Homomorphic summation. For each race and choice: T_j = product of all valid c_i for choice j. This equals E(sum of all votes for choice j).

3. Publish encrypted tallies. The EncryptedTally objects are published to the bulletin board.

4. Transition: CLOSED -> TALLYING.

Phase 6: Decryption Ceremony

1. Each of M key share holders computes their partial decryption: partial_i = ComputePartialDecryption(share_i, T_j, pk). This runs on the share holder's own machine; the share never leaves.

2. The combiner collects the M partial decryptions.

3. The combiner combines: plaintext_j = CombinePartialDecryptions(partials, metadata, pk).

4. The decrypted count for each choice is published with a decryption proof (SHA-256 hash of inputs and outputs for audit).

5. Transition: TALLYING -> CERTIFIED.

Phase 7: Verification and Attestation

1. Individual verification. Each voter checks their receipt against the bulletin board: VerifyReceipt(receipt, bulletin_board) = 1.

2. Universal verification. Any observer runs UniversalVerify(bulletin_board) (Section 3.3).

3. Attestation. The ResultAttestationGenerator creates a signed attestation:

   • result_hash = SHA-256(serialized_result)
   • journal_hash = hash_chain(all_ballot_entries)
   • signature = HMAC-SHA-256(signing_key, attestation_payload)

4. The attestation is published to the bulletin board.

5. Transition: CERTIFIED -> ARCHIVED (after retention period).

5.2 Multi-Cell Distribution

SOVEREIGN leverages the System9 cell architecture for distributed trust:

5.2.1 Key Share Distribution

In an N-cell deployment with threshold M:

• Each cell holds at most one key share.
• Shares are distributed across service groups so that no single cell group holds M shares.
• This ensures that compromising one service group is insufficient to decrypt individual votes.

Example: 5 cells across 3 service groups, threshold 3:

• Service group A: cells 1, 2 (shares 1, 2)
• Service group B: cells 3, 4 (shares 3, 4)
• Service group C: cell 5 (share 5) Compromising any one service group yields at most 2 shares < 3 = M.

5.2.2 Ballot Aggregation

Each cell collects encrypted ballots from local voters. Encrypted ballots are replicated to the bulletin board through the System9 replication layer. Because ballots are encrypted, replication does not leak vote content.

The homomorphic tally can be computed incrementally:

• Each cell computes a local subtally: T_local = product of local c_i.
• A coordinator computes the global tally: T = product of T_local values.
• This is correct because homomorphic multiplication is associative and commutative.

5.2.3 Disconnected Operation

For cells operating without network connectivity (military, disaster response):

1. Votes are encrypted and stored locally on the cell.
2. ZK proofs are generated and stored with the ballots.
3. When connectivity is restored, encrypted ballots are synchronized to the bulletin board.
4. The tally is computed after all cells have synchronized.
5. The threshold decryption ceremony proceeds as normal.

The delay-tolerant design is possible because all cryptographic operations (encryption, ZK proof generation) are local. Only the tally and decryption require multi-cell coordination.

5.3 Entity Contract Governance

Every SOVEREIGN election is governed by an entity contract following the AAMAS 2026 seven-tuple model:

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

I -- Input Specification: Defines the ballot format: required fields (ballot_id, election_id, voter_entity_id, selections), field types, and the race/choice schema.

O -- Output Specification: Defines the tally format: guaranteed fields (election_id, race_tallies, total_voted, certified_at), field types, and minimum completeness (1.0, meaning all ballots must be counted).

S -- Required Skills: Specifies the tallying algorithm required (e.g., "tally:simple_majority", "tally:ranked_choice"). The system verifies that the executing agent possesses the required skill.

R -- Resource Constraints: Sets the maximum number of ballots equal to the number of eligible voters (max_api_calls = len(eligible_entity_ids)). This prevents ballot stuffing at the contract level.

T -- Temporal Constraints: Defines when the election opens (valid_from = opens_at) and closes (valid_until = closes_at). Ballots submitted outside this window are rejected by the contract enforcement layer.

Phi -- Success Criteria: Requires 100% ballot inclusion rate (every valid ballot is counted) and quorum satisfaction (if a quorum percentage is specified).

Psi -- Termination Conditions:

• On timeout: extend (the election period is extended if ballots are still being submitted).
• On violation: escalate (contract violations are escalated to human administrators).
• On budget exhaustion: terminate (if the maximum ballot count is exceeded, the election is terminated and investigated).

The contract is created via the ContractManager and published to the bulletin board as part of the election definition. Contract compliance is verified during attestation.

---

6. Security Arguments

This section provides reduction-based arguments that SOVEREIGN satisfies the security properties defined in Section 3.

6.1 Ballot Secrecy

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

Proof. We proceed by reduction. Assume A breaks ballot secrecy with non-negligible advantage epsilon. We construct an algorithm B that breaks the DCR assumption.

Construction. B receives a DCR challenge (n, y) where y is either a random n-th residue (y = r^n mod n^2 for random r) or a random element of Z*_{n^2}.

B simulates the SOVEREIGN election for A:

1. B sets pk = (n, n^2, n+1, .) and gives pk to A. (B does not know the factorization of n, so it cannot create sk.)

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

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

4. B generates a ZK proof pi* for c* using the simulator (which exists by the zero-knowledge property of the Sigma protocol -- see Section 4.3.4).

5. B returns (c*, pi*) to A.

6. When A outputs beta', B outputs:

   • 1 if beta' = 0 (A thinks c* encrypts b_0, consistent with y being an n-th residue)
   • 0 if beta' = 1

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

Adv^DCR_B = |Pr[B(n-th residue) = 1] - Pr[B(random) = 1]|
          = |Pr[A wins | beta=0] - 1/2|
          = Adv^BS_A / 2

Since Adv^DCR_B is negligible (by assumption), Adv^BS_A is also negligible. This completes the core reduction.

Composing with the threshold scheme. The reduction above shows that no PPT adversary can break ballot secrecy given only the public key. We now argue that M-1 corrupted key share holders gain no additional advantage:

• The M-1 shares reveal no information about the secret lambda_val beyond what is implied by the public key (Section 4.4.4). This follows from the information-theoretic security of Shamir sharing over the integers with the large coefficient bound.

• The M-1 partial decryptions partial_i = c^{2Deltas_i} mod n^2 are deterministic functions of the shares and carry no additional information. Recovering s_i from partial_i requires solving the discrete logarithm in Z*_{n^2}, which is at least as hard as factoring n.

• Therefore, A with M-1 shares has negligibly more advantage than A with only pk, and the DCR reduction applies.

Composing with the ZK proofs. The ZK proofs published alongside each ciphertext do not leak information about the plaintext. By the zero-knowledge property (Section 4.3.4), a simulator can produce proofs indistinguishable from real proofs without knowing the plaintext. In the random oracle model, the Fiat-Shamir transform preserves this property for non-interactive proofs.

Composing with blind signatures. The blind signature protocol breaks the voter-ballot linkage. Even if A observes the registration phase and the bulletin board, the blinding factor makes the signed message uniformly distributed during registration, and the unblinded token bears no correlation to the blinding session (Section 4.2.7).

Conclusion. Combining all components, SOVEREIGN provides ballot secrecy with advantage bounded by:

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

where Adv^ZK_sim is the distinguishing advantage against the ZK simulator (zero in the random oracle model). All terms are negligible, so ballot secrecy holds. []

6.2 Individual Verifiability

Theorem 2. SOVEREIGN provides individual verifiability (Definition 3.2) under the collision resistance of SHA-256.

Proof.

Let V be a voter with receipt R = (receipt_id, ballot_id, election_id, commitment_hash) where commitment_hash = SHA-256(encrypted_payload).

Completeness. If the bulletin board correctly stores V's ballot, then there exists an entry e with e.ballot_id = ballot_id and SHA-256(e.encrypted_payload) = commitment_hash. Therefore Verify(R, B) = 1.

Soundness. Suppose an adversary A modifies the bulletin board to replace V's encrypted ballot with a different payload p' such that SHA-256(p') = SHA-256(encrypted_payload). This requires finding a SHA-256 collision, which occurs with probability at most negl(lambda) under the collision resistance assumption.

Alternatively, suppose A deletes V's ballot entirely. Then no entry with ballot_id exists, so Verify(R, B) = 0, and V detects the manipulation.

Implementation note. The ballot recorder computes the commitment hash immediately upon receipt and returns it in the VoterReceipt. The same hash is published to the bulletin board. The voter need only check that the published hash matches their receipt.

6.3 Universal Verifiability

Theorem 3. SOVEREIGN provides universal verifiability (Definition 3.3) under the soundness of the ZK ballot proof, the homomorphic property of Paillier, and the correctness of threshold decryption.

Proof.

We argue that the UniversalVerify algorithm (Section 3.3) accepts for honest executions and rejects for dishonest executions.

Step 1: Ballot proof verification. By the soundness of the disjunctive Sigma protocol (Section 4.3.4), if VerifyBallotProof(pk, c_i, pi_i) = 1, then c_i encrypts 0 or 1 (except with negligible probability). An adversary who submits a ballot encrypting a value outside {0, 1} cannot produce a valid proof.

Step 2: Token verification. By the unforgeability of RSA signatures (Section 4.2.7), only tokens signed by the authority pass verification. An adversary cannot forge a valid token.

Step 3: Homomorphic tally. By the homomorphic property of Paillier (Section 4.1.4), the product of all valid ciphertexts c_i for choice j equals E(sum(v_i)) for the votes v_i. This computation is deterministic -- any verifier who multiplies the same ciphertexts obtains the same result. If the published tally T_j differs, the verifier detects the discrepancy.

Step 4: Decryption proof. The decryption result R_j comes with a proof hash that binds the encrypted tally, plaintext, ballot count, and number of shares used. The verifier recomputes this hash and checks equality.

Note on decryption proof strength. The current implementation uses a SHA-256 hash as a decryption proof, which is an audit trail rather than a zero-knowledge proof of correct decryption. A Chaum-Pedersen DLOG equality proof would provide stronger guarantees (proving that each partial decryption was computed correctly). This is documented as a Phase 3 enhancement.

Step 5: Ballot count consistency. The verifier counts the ballot entries on the bulletin board and compares with the tally's ballot_count field. Any discrepancy indicates tampering.

6.4 Eligibility Verifiability

Theorem 4. SOVEREIGN provides eligibility verifiability (Definition 3.4) under the unforgeability of RSA blind signatures and the honest registration assumption (T1).

Proof.

Every counted ballot must contain a valid anonymous token (token, sig) such that VerifyToken(token, sig, auth_n, auth_e) = 1.

No forgery. By the unforgeability of RSA (Section 4.2.7), a PPT adversary cannot produce a valid (token, sig) pair without interacting with the authority's signing oracle. The authority only signs tokens for eligible voters (trust assumption T1).

No double-voting. The duplicate token detection in the ballot recorder rejects ballots with tokens that have already been used. Since each voter receives at most one valid token (from the blind signature protocol with one signing session per voter), each voter can cast at most one counted ballot.

Eligibility checking. Before the blind token issuance, the EligibilityChecker verifies:

1. The voter has not already registered.
2. The voter's entity type matches the election's requirements.
3. The voter appears in the eligible entity list (if specified).
4. The voter's entity exists in the entity manager (if available).

These checks are procedural (not cryptographic) and rely on the correctness of the eligibility data. The cryptographic guarantee is that a valid anonymous token can only be obtained through the authority's signing oracle.

6.5 Coercion Resistance

Theorem 5. SOVEREIGN provides coercion resistance (Definition 3.5) under the PRF security of HMAC-SHA-256 and the honest authority assumption.

Proof.

We prove that no PPT coercer A can distinguish real from fake credentials with non-negligible advantage.

Let k be the authority's secret key (unknown to A). Let CR = (id_r, token_r, HMAC_k(id_r || ":" || token_r)) be a real credential. Let CF = (id_f, token_f, HMAC_{k'}(id_f || ":" || token_f)) be a fake credential, where k' is random.

A sees one of CR or CF and must determine which.

Reduction to PRF security. Suppose A has advantage epsilon in distinguishing CR from CF. We construct a PRF distinguisher D:

1. D receives oracle access to either HMAC_k(.) or a random function f(.).
2. D generates (id, token) randomly.
3. D queries its oracle on input (id || ":" || token), receiving mac.
4. D gives A the credential (id, token, mac).
5. If A says "real," D says "PRF." If A says "fake," D says "random."

If D's oracle is HMAC_k, then the credential looks like a real one. If D's oracle is random, then the credential's MAC is independent of k, just like a fake credential's MAC (which uses random k'). Therefore:

Adv^PRF_D = |Pr[D says "PRF" | oracle = HMAC_k]
            - Pr[D says "PRF" | oracle = random]|
          = |Pr[A says "real" | real] - Pr[A says "real" | fake]|
          = Adv^CR_A = epsilon

By the PRF security of HMAC-SHA-256, epsilon is negligible.

Tally-phase filtering. During tallying, the EA validates each credential by recomputing HMAC_k(id || ":" || token). Real credentials match; fakes do not. The filtering is performed in batch -- only the set of valid credential IDs is returned. The size of the discarded set is not revealed, preventing the coercer from detecting that credentials were filtered.

Residual risk. If the coercer can observe the tally result and knows the total number of voters, the coercer may infer that some votes were cast with fake credentials (if the tally count is less than the number of observed voting sessions). SOVEREIGN mitigates this by not publishing the count of filtered credentials and by allowing the tally to include a "participation noise" padding (future enhancement).

---

7. Assumptions and Limitations

7.1 Cryptographic Assumptions

SOVEREIGN's security rests on the following standard assumptions:

Assumption	Used For	Strength
DCR (Decisional Composite Residuosity)	Paillier encryption (ballot secrecy)	Standard, well-studied
RSA	Blind signatures (eligibility)	Standard, well-studied
ROM (Random Oracle Model)	Fiat-Shamir heuristic (ZK proofs)	Idealization, standard in practice
PRF (Pseudorandom Function)	HMAC-SHA-256 (coercion resistance)	Standard, well-studied
Collision Resistance	SHA-256 (receipt verification)	Standard, well-studied

All assumptions are standard and well-studied in the cryptographic literature. The DCR assumption is the strongest specific assumption; it is implied by the hardness of factoring but is not known to be equivalent.

7.2 Trust Assumptions

Assumption	Impact if Violated
T1: Honest registration authority	Eligibility verifiability fails; authority could issue extra credentials
T2: At least M of N honest share holders	Ballot secrecy fails; adversary can decrypt individual votes
T3: Random oracle model for SHA-256	ZK proofs may not be sound in the standard model
T4: Append-only bulletin board	Ballots could be deleted without detection
T5: Voter device integrity	Votes could be silently changed at the device level

7.3 Known Limitations

L1: No full receipt-freeness. A voter who reveals the Paillier randomness r used in their encryption can prove how they voted. The JCJ protocol mitigates but does not eliminate this: the voter can use a fake credential, but the coercer could demand the randomness for a ballot cast with a specific (possibly fake) credential and verify the encrypted content. Full receipt-freeness would require re-encryption mix-nets or designated verifier proofs.

L2: Fiat-Shamir in the random oracle model. The ZK ballot proof uses the Fiat-Shamir heuristic, which is secure in the random oracle model but has known counterexamples in the standard model [GK03]. For SOVEREIGN's application, this is acceptable as all practical E2E-V systems use Fiat-Shamir.

L3: HMAC-based JCJ (not public-key JCJ). The original JCJ protocol uses ElGamal encryption for credentials, providing information-theoretic hiding and distributed validation. SOVEREIGN uses HMAC, which provides only computational hiding and requires a single authority key. Compromising this key breaks coercion resistance. A threshold HMAC variant is planned for future work.

L4: No Chaum-Pedersen proof for partial decryption. The current partial decryption protocol uses a SHA-256 commitment hash for audit logging, not a zero-knowledge proof of correct partial decryption. A malicious share holder could submit an incorrect partial decryption without detection. Adding Chaum-Pedersen DLOG equality proofs is planned for Phase 3.

L5: Integer-based Shamir sharing leakage. Shamir sharing over the integers (rather than a finite field) can leak information about the secret's magnitude through the share magnitudes. SOVEREIGN mitigates this by drawing random coefficients from [0, n * 2^{128}), making the shares statistically close to uniform regardless of the secret value. The statistical distance is at most 2^{-128}.

L6: Trusted device problem. Like all electronic voting systems, SOVEREIGN assumes the voter's device correctly implements the voting client. A compromised device could encrypt a different vote than the voter intended. This is a fundamental limitation that cannot be solved purely through cryptography and requires complementary measures (e.g., voter- verifiable paper audit trails for high-stakes elections).

L7: No mix-net. SOVEREIGN does not use a mix-net for re-encryption shuffling. The bulletin board publishes encrypted ballots in arrival order, which could leak timing information. A re-encryption mix-net would randomize the order, but this is not implemented.

7.4 Comparison with State of the Art

Property	SOVEREIGN	ElectionGuard	Helios	Belenios
Encryption	Paillier	ElGamal	ElGamal	ElGamal
ZK proofs	Disjunctive Sigma	Disjunctive Chaum-Pedersen	Disjunctive Sigma	Disjunctive Sigma
Tallying	Homomorphic	Homomorphic	Homomorphic	Mix-net + Homomorphic
Threshold	Shamir/Damgard-Jurik	Shamir/Lagrange	N/A (single key)	Threshold ElGamal
Blind signatures	RSA	N/A	N/A	N/A
Coercion resistance	HMAC-JCJ	No	No	Partial (Belenios-RF)
Formal contracts	AAMAS 2026	No	No	No
Multi-cell	System9 cells	No	No	No
Disconnected ops	Yes	No	No	No
Election types	7	1	1	1

---

8. Implementation Notes

8.1 Key Sizes and Security Levels

Parameter	Value	Security Level
Paillier key size (production)	2048-bit	128-bit
Paillier key size (testing)	1024-bit	80-bit
RSA blind signature key size	2048-bit	128-bit
RSA public exponent	65537	Standard
SHA-256 output	256-bit	128-bit (collision)
HMAC-SHA-256 key	256-bit	256-bit
ZK challenge space	256-bit	128-bit (birthday)
Shamir statistical security	128-bit	128-bit
Random token size	256-bit	128-bit
Miller-Rabin rounds	20	2^{-40} error bound

8.2 Test Vectors

The following test vectors were generated from the reference implementation and can be used to verify alternative implementations. All vectors use 1024-bit Paillier keys.

Paillier encryption/decryption:

• E(0): ciphertext is 2045 bits
• E(1): ciphertext is 2047 bits (approximately 2n bits, as expected for elements of Z*_{n^2})
• D(E(42)) = 42 (encryption/decryption round-trip)
• D(E(17) * E(25) mod n^2) = 42 (homomorphic addition: 17 + 25 = 42)

Zero-knowledge proof:

• Proof components: a_0, a_1 in Z*_{n^2} (2047 bits each), 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 generated for E(1) does not verify against a different ciphertext)

These bit lengths confirm the expected algebraic structure: commitments a_i live in Z_{n^2} (up to 21024 = 2048 bits), challenges e_i live in Z_n (up to 1024 bits), and responses z_i live in Z_n (up to 1024 bits).

Threshold decryption (5,3):

• 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 correctly recovers the plaintext)

Blind signature:

• Verify(Unblind(Sign_d(Blind_e(token, r)), r), token, e) = accept (full round-trip: blind, sign, unblind, verify)

Coercion-resistant credentials:

• Real credential: (UUID, 256-bit token, 256-bit HMAC)
• Fake credential: (UUID, 256-bit token, 256-bit HMAC)
• Structural comparison: both have identical field types and sizes
• ValidateCredential(real, authority_key) = real
• ValidateCredential(fake, authority_key) = fake

8.3 Performance Evaluation

Benchmarks were performed on a standard development machine (single core, CPython) using the reference Python implementation with 1024-bit Paillier keys.

Per-operation latency:

Operation	Time (ms)	Notes
KeyGen	583	One-time setup per election
Encrypt	26	Per-vote encryption
Decrypt	73	Used only in threshold ceremony
Homomorphic Add	0.02	Per-ballot accumulation
ZK Prove	102	Per-vote proof generation
ZK Verify	103	Per-ballot verification
Threshold Split (5,3)	0.9	One-time setup
Partial Decrypt	50	Per-share-holder
Combine Partials (3)	2.5	Per-race
Blind Token	0.6	Per-voter registration
Sign Blinded	85	Authority per-voter

Election simulation (1024-bit, single core):

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

Key observations:

1. Encryption dominates. Client-side encryption and proof generation account for >99% of total election time. These operations are embarrassingly parallel across voters and cells.

2. Homomorphic tallying is near-instant. Tallying 1,000 ballots takes 20ms (modular multiplication is cheap). This confirms the theoretical O(K) complexity with a negligible constant.

3. Threshold decryption is fast. 21-33ms regardless of voter count, confirming O(M) complexity independent of K.

4. 2048-bit keys are approximately 8x slower. Recommended for production use despite the performance cost. The dominant cost (encryption) is client-side and parallelizable.

5. Sign Blinded is expensive. At 85ms per voter, blind signing is a sequential bottleneck at the authority. For large elections, multiple signing authorities or batched signing should be considered.

8.4 Implementation Quality

• Pure Python cryptography. Paillier, ZK proofs, threshold sharing, and HMAC credentials are implemented in pure Python using built-in arbitrary-precision integers. No external cryptographic libraries are required for the core voting protocols.

• RSA from cryptography library. The RSA blind signature protocol uses the cryptography library for key generation only, ensuring constant-time key generation and protection against side-channel attacks. The blinding, signing, and verification operations use Python's built-in pow(base, exp, mod) which leverages GMP for modular exponentiation.

• Constant-time comparisons. All credential and signature comparisons use hmac.compare_digest to prevent timing attacks.

• Domain-separated hashing. The ZK proof hash is prefixed with "SOVEREIGN-ZK-v1" to prevent cross-protocol attacks.

• Deterministic serialization. All data structures are serialized with json.dumps(sort_keys=True) to ensure deterministic hashing.

• Immutable data structures. All cryptographic values (keys, shares, proofs, credentials) use frozen dataclasses with __slots__ for memory efficiency and immutability guarantees.

8.5 Test Coverage

The implementation includes 122 tests across 17 test files:

Test File	Tests	Coverage
test_paillier.py	Keygen, encrypt/decrypt, homomorphic ops	Core crypto
test_threshold_keys.py	Split, reconstruct, partial decrypt, combine	Threshold
test_blind_signature.py	Blind, sign, unblind, verify, unlinkability	Anonymity
test_zk_ballot_proof.py	Prove, verify, reject invalid, Fiat-Shamir	Soundness
test_homomorphic_tally.py	Tally engine, proof verification, token check	Tallying
test_decryption_ceremony.py	Ceremony, partial, combine, audit proof	Decryption
test_coercion_resistance.py	Real/fake creds, validation, batch filter	JCJ
test_voting_types.py	Type enums, dataclass construction	Types
test_eligibility_checker.py	All eligibility rules, edge cases	Eligibility
test_election_contract.py	Contract building, seven-tuple mapping	Contracts
test_election_manager.py	Full lifecycle, all 7 election types	Management
test_ballot_recorder.py	Journal writes, HMAC integrity, receipts	Recording
test_bulletin_board.py	Publish, query, verify, export	Board
test_result_attestation.py	Attestation generation, signing, chain	Attestation
test_voting_node_executor.py	Node execution, workflow integration	Execution
test_e2e_anonymous_election.py	Full crypto E2E: keygen -> decrypt	Integration
test_e2e_manager_anonymous.py	Full manager E2E: create -> certify	Integration

The two end-to-end tests are particularly significant: they exercise the complete election lifecycle including key generation, threshold splitting, blind token issuance, encrypted ballot casting with ZK proofs, homomorphic tallying across multiple ballots, and threshold decryption with partial shares.

---

9. Notation and Conventions

Symbol	Meaning
lambda	Security parameter (key size in bits)
n	Paillier modulus (n = pq)
n^2	Paillier ciphertext space modulus
g	Paillier generator (g = n + 1)
E(m, r)	Paillier encryption of m with randomness r
lambda_val	lcm(p-1, q-1) (Paillier private key)
mu	L(g^{lambda_val} mod n^2)^{-1} mod n
L(x)	(x - 1) / n
M	Threshold (minimum shares for decryption)
N	Total number of key shares
Delta	N! (factorial of total shares)
s_i	Share i (evaluation of sharing polynomial at point i)
H(.)	SHA-256 hash function (modeled as random oracle)
HMAC_k(.)	HMAC-SHA-256 with key k
Z_n	Integers modulo n: {0, 1, ..., n-1}
Z*_n	Integers coprime to n: {r in Z_n : gcd(r, n) = 1}
Z_{n^2}	Integers modulo n^2
negl(lambda)	A negligible function of lambda
PPT	Probabilistic polynomial-time
IND-CPA	Indistinguishability under chosen-plaintext attack
DCR	Decisional Composite Residuosity assumption
ROM	Random Oracle Model
PRF	Pseudorandom Function
pk	Public key
sk	Private (secret) key
(auth_n, auth_e)	Authority RSA public key for blind signatures
auth_d	Authority RSA private key for blind signatures
pi	Zero-knowledge proof
B	Bulletin board
R	Voter receipt
CR	Real credential
CF	Fake credential
k	Authority's secret HMAC key
A	Adversary

---

10. References

[Adi08] B. Adida. "Helios: Web-based Open-Audit Voting." In Proceedings of the 17th USENIX Security Symposium, 2008.

[Ben+19] J. Benaloh, M. Byrne, P. Kortum, N. McBurnett, O. Pereira, T. Stark, D. Wallach. "STAR-Vote: A Secure, Transparent, Auditable, and Reliable Voting System." usenix jet 2019.

[Cha83] D. Chaum. "Blind Signatures for Untraceable Payments." In Advances in Cryptology -- CRYPTO '82, pages 199--203, 1983.

[Cor+15] V. Cortier, P. Galindo, S. Glondu, M. Izabachene. "Election Verifiability for Helios under Weaker Trust Assumptions." In ESORICS 2014, pages 327--344, 2015.

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

[FS86] A. Fiat and A. Shamir. "How To Prove Yourself: Practical Solutions to Identification and Signature Problems." In Advances in Cryptology -- CRYPTO '86, pages 186--194, 1986.

[GK03] S. Goldwasser and Y. T. Kalai. "On the (In)security of the Fiat-Shamir Paradigm." In 44th FOCS, pages 102--113, 2003.

[JCJ05] A. Juels, D. Catalano, and M. Jakobsson. "Coercion-Resistant Electronic Elections." In Proceedings of the 2005 ACM Workshop on Privacy in the Electronic Society (WPES), pages 61--70, 2005.

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

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

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

[ElGrd] Microsoft. "ElectionGuard Specification." Version 2.0. https://www.electionguard.vote/spec/

[Bel] Belenios. "Belenios Specification." https://www.belenios.org/specification.pdf

[AAMAS26] System9 Engineering. "Formal Entity Contracts for Autonomous Agent Governance." Submitted to AAMAS 2026.

---

Appendix A: Election Type Security Considerations

SOVEREIGN supports seven election types. Each has specific security considerations:

A.1 Simple Majority

Standard plurality voting. Each voter selects one choice per race. The choice with the most votes wins. All security properties apply as described.

A.2 Super Majority

Requires a threshold percentage (default 66.7%) for a choice to win. The threshold is specified in the election definition and enforced by the contract. Security properties are identical to simple majority; the threshold is a tallying rule, not a cryptographic property.

A.3 Ranked Choice (Instant Runoff)

Voters rank choices in order of preference. Tallying proceeds in rounds, eliminating the lowest-ranked choice and redistributing its votes until a majority winner emerges.

Security consideration. Ranked-choice tallying requires individual ballot decryption to determine rankings, which is incompatible with pure homomorphic tallying. SOVEREIGN handles this by encrypting ranked-choice ballots differently: each ranking is encrypted separately, and the threshold decryption ceremony reveals the aggregate ranking distribution rather than individual rankings.

A.4 Approval Voting

Voters can approve (vote for) any number of choices. Each choice's approval count is tallied independently. Homomorphic tallying applies directly: one encrypted 0/1 per choice, summed independently.

A.5 Weighted Voting

Each voter's vote has a weight (e.g., proportional to shares in a corporate governance context). The Paillier encryption handles this naturally: encrypt the weight rather than 1, and the homomorphic sum produces the weighted total.

Security consideration. The ZK proof must be adapted to prove that the encrypted value is in [0, max_weight] rather than {0, 1}. Range proofs are more complex than disjunctive proofs and are planned for future work.

A.6 Consensus Voting

Requires unanimous or near-unanimous agreement. The tallying threshold is set close to 100%. No additional cryptographic considerations beyond standard tallying.

A.7 Referendum Voting

Binary yes/no vote with a required passage threshold. Identical to simple majority with exactly two choices and a configurable threshold.

---

Appendix B: Multi-Cell Threat Scenarios

B.1 Single Cell Compromise

An adversary compromises one cell, gaining access to all data on that cell including any key shares stored there.

Impact. The adversary obtains at most one key share (insufficient for decryption if M > 1). The adversary sees encrypted ballots from local voters but cannot decrypt them. The adversary cannot forge ballots (no access to the authority's signing key on other cells).

Mitigation. The cell's key share can be revoked and the election re-keyed if detected before tallying.

B.2 Service Group Compromise

An adversary compromises all cells in one service group.

Impact. The adversary obtains multiple key shares but (by the distribution policy) fewer than M. The adversary sees all encrypted ballots from the service group's voters but cannot decrypt them.

Mitigation. Same as single cell compromise, at larger scale.

B.3 Network Partition

A network partition isolates one or more cells from the rest.

Impact. Voters on isolated cells can still cast encrypted ballots (all crypto is local). Tallying and decryption are delayed until connectivity is restored. No security properties are violated.

Mitigation. Delay-tolerant networking with eventual consistency.

B.4 Bulletin Board Tampering

An adversary attempts to modify the bulletin board.

Impact. The HMAC hash chain makes tampering detectable. Each ballot entry's signature incorporates the previous entry. Modifying or deleting an entry breaks the chain. Individual verification by voters using their receipts also detects tampering.

Mitigation. Replicate the bulletin board across multiple cells. Any discrepancy triggers an alert.

---

Appendix C: Formal Definitions (Mathematical Notation)

C.1 Paillier Encryption Scheme

Pi_Pai = (KeyGen, Enc, Dec) where:

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

Enc(pk, m; r):
    c = (1 + n*m) * r^n mod n^2
    return c

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

C.2 Blind Signature Scheme

Pi_Blind = (KeyGen, Blind, Sign, Unblind, Verify) where:

KeyGen(1^lambda):
    (n, e, d) <- RSAKeyGen(lambda)
    return (pk = (n, e), sk = d)

Blind(pk, m):
    h = H(m) mod n
    r <- Z*_n
    b = h * r^e mod n
    return (b, r)

Sign(sk, b):
    s = b^d mod n
    return s

Unblind(s, r, n):
    sigma = s * r^{-1} mod n
    return sigma

Verify(pk, m, sigma):
    return (sigma^e mod n == H(m) mod n)

C.3 ZK Ballot Proof System

Pi_ZK = (Prove, Verify) for relation:
    R = {((pk, c), (b, r)) : c = Enc(pk, b; r) and b in {0, 1}}

Prove((pk, c), (b, r)):
    // OR-proof: real branch b, simulated branch 1-b
    // (See Section 4.3.2 for full algorithm)
    return (a0, a1, e0, e1, z0, z1)

Verify((pk, c), (a0, a1, e0, e1, z0, z1)):
    // (See Section 4.3.3 for full algorithm)
    return ACCEPT or REJECT

C.4 Threshold Decryption Scheme

Pi_Thresh = (Split, PartialDec, Combine) where:

Split(sk, N, M):
    f(x) = lambda_val + sum_{i=1}^{M-1} a_i * x^i
    where a_i <- [0, n * 2^{128})
    return {(i, f(i)) : i = 1..N}

PartialDec(s_i, c, pk):
    Delta = N!
    p_i = c^{2 * Delta * s_i} mod n^2
    return p_i

Combine({p_i : i in S}, pk):
    Delta = N!
    For each i in S: compute mu_i = Delta * L_i(0)
    combined = product(p_i^{mu_i}) mod n^2
    l = (combined - 1) / n
    m = l * (2 * Delta^2)^{-1} * mu mod n
    return m

---

Appendix D: Bulletin Board Protocol

The bulletin board is a critical component of SOVEREIGN's verifiability properties. This appendix specifies the bulletin board protocol in detail.

D.1 Bulletin Board Model

The bulletin board B is an append-only ordered log of entries. Each entry has the form:

e = (entry_id, entry_type, election_id, data, timestamp, signature)

where:

• entry_id is a UUID4 unique identifier
• entry_type in {"election", "ballot", "tally", "attestation"}
• election_id identifies the election
• data is a dictionary of type-specific fields
• timestamp is an ISO 8601 UTC timestamp
• signature is an optional HMAC-SHA-256 signature

D.2 Entry Types

Election entry. Published once per election during setup:

data = {
    name: string,
    election_type: string,
    privacy: string,
    race_count: int,
    opens_at: string,
    closes_at: string,
    contract_id: string
}

Ballot entry. Published once per encrypted ballot during voting:

data = {
    ballot_id: string,
    encrypted_payload: string,  // Paillier ciphertext (hex)
    zk_proof: string,           // JSON-serialized BallotProof
    anonymous_token: string,    // Blind-signed token (hex)
    commitment_hash: string     // SHA-256(encrypted_payload)
}

No voter identity appears in the ballot entry.

Tally entry. Published once per election during tallying:

data = {
    tally: string  // JSON with per-choice encrypted sums and counts
}

The tally entry may include an HMAC signature using the signing key.

Attestation entry. Published once per election during certification:

data = {
    attestation: string  // JSON-serialized ElectionAttestation
}

D.3 Integrity Properties

Append-only. Entries can only be appended, never modified or deleted. This is enforced by the ballot recorder's HMAC hash chain, where each entry's signature incorporates the content of all previous entries.

Tamper detection. The hash chain H_0 = "", H_i = SHA-256(H_{i-1} || payload_i) provides tamper evidence. Modifying any entry changes its hash, which cascades through all subsequent entries. Verification is O(n) in the number of entries.

Receipt binding. The commitment_hash in each ballot entry matches the commitment_hash in the voter's receipt. By collision resistance of SHA-256, the encrypted ballot cannot be replaced with a different payload without invalidating the receipt.

D.4 Verification Algorithms

Individual verification (voter):

VerifyReceipt(receipt, board):
  entries = board.get_entries(receipt.election_id)
  for entry in entries:
    if entry.type == "ballot" and entry.data.ballot_id == receipt.ballot_id:
      return entry.data.commitment_hash == receipt.commitment_hash
  return false  // ballot not found

Ballot count verification (auditor):

VerifyBallotCount(election_id, board):
  ballot_entries = board.get_ballots(election_id)
  tally_entry = board.get_tally(election_id)
  if tally_entry is None:
    return true  // no tally to verify against
  expected_count = parse(tally_entry.data.tally).ballot_count
  return len(ballot_entries) == expected_count

Full audit export:

ExportForAudit(election_id, board):
  return {
    election: board.get_election(election_id),
    ballots: board.get_ballots(election_id),
    ballot_count: count(ballots),
    tally: board.get_tally(election_id),
    attestation: board.get_attestation(election_id)
  }

D.5 Multi-Cell Bulletin Board

In a multi-cell deployment, each cell maintains a local bulletin board partition. The global bulletin board is the union of all local partitions. Consistency is ensured by the System9 replication layer:

1. Each cell writes ballot entries to its local partition.
2. The replication layer propagates entries to all other cells.
3. Before tallying, the coordinator verifies that all cells have synchronized by checking entry counts and hash chain consistency across partitions.
4. The tally is computed over the global bulletin board.

---

Appendix E: Result Attestation Protocol

The result attestation is the final cryptographic artifact of an election, binding together the election definition, all ballots, the tally, and the decryption result into a single signed proof.

E.1 Attestation Structure

ElectionAttestation = {
    attestation_id: UUID4,
    election_id: string,
    result_hash: SHA-256(JSON(ElectionResult)),
    ballot_count: int,
    journal_hash: H_n (hash chain terminal hash),
    contract_id: string,
    certified_by: string,
    certified_at: ISO 8601 timestamp,
    signature: HMAC-SHA-256(signing_key, attestation_payload)
}

E.2 Attestation Generation

1. Serialize the ElectionResult deterministically: result_json = JSON.dumps(result, sort_keys=True)

2. Compute result_hash = SHA-256(result_json).

3. Compute journal_hash by chaining all ballot journal entries: H_0 = "" H_i = SHA-256(H_{i-1} || payload_i) for i = 1..K

4. Assemble the signing payload: payload = attestation_id || ":" || election_id || ":" || result_hash || ":" || journal_hash || ":" || total_voted

5. Sign: signature = HMAC-SHA-256(signing_key, payload).

E.3 Attestation Verification

A verifier with the signing key can verify:

1. Recompute result_hash from the published ElectionResult.
2. Recompute journal_hash from the published ballot entries.
3. Recompute the HMAC and compare with the stored signature.

If any step fails, the attestation is invalid, indicating tampering between the tallying phase and the publication of results.

E.4 Attestation without Signing Key

Even without the signing key, a verifier can check:

1. The result_hash matches the published ElectionResult.
2. The journal_hash is consistent with the published ballot entries.
3. The ballot_count matches the number of ballot entries.

These checks do not require any secrets and provide a weaker but still useful form of verification.

---

Appendix F: Comparison of Cryptographic Assumptions

This appendix compares the cryptographic assumptions used by SOVEREIGN with those used by other E2E-V systems.

F.1 Assumption Comparison

Assumption	SOVEREIGN	ElectionGuard	Helios	Belenios
DCR	Yes (Paillier)	No	No	No
DDH	No	Yes (ElGamal)	Yes (ElGamal)	Yes (ElGamal)
RSA	Yes (blind sig)	No	No	No
ROM	Yes (Fiat-Shamir)	Yes (Fiat-Shamir)	Yes (Fiat-Shamir)	Yes (Fiat-Shamir)
PRF	Yes (HMAC-JCJ)	No	No	No

F.2 Assumption Strength Ordering

The standard ordering of assumption strength (from weakest to strongest):

1. Factoring >= DCR (DCR is implied by factoring hardness)
2. Factoring >= RSA (RSA is implied by factoring hardness)
3. DDH >= CDH >= DL (standard Diffie-Hellman hierarchy)
4. PRF (standard, implied by existence of one-way functions)
5. ROM (idealization, universally used in practice)

Both DCR and DDH are considered standard assumptions with decades of cryptanalytic study. The choice between Paillier (DCR) and ElGamal (DDH) does not significantly affect the overall security posture. The additional RSA assumption in SOVEREIGN (for blind signatures) is also standard and well-studied.

F.3 Post-Quantum Considerations

Neither Paillier nor ElGamal is post-quantum secure. Both DCR and DDH can be broken by Shor's algorithm on a sufficiently large quantum computer. The RSA and factoring assumptions are similarly vulnerable.

For SOVEREIGN, this means that encrypted ballots stored on the bulletin board could be decrypted by a future quantum computer (the "harvest now, decrypt later" threat). For elections where ballot secrecy must persist beyond the advent of large-scale quantum computing, lattice-based homomorphic encryption (e.g., BGV or CKKS) should be considered. This is an active area of research and is left for future work.

The ZK proofs and HMAC credentials are less affected: the Fiat-Shamir heuristic requires collision resistance of the hash function (SHA-256 provides 128-bit post-quantum collision resistance), and HMAC security degrades gracefully under quantum attacks (Grover's algorithm reduces 256-bit HMAC security to 128-bit, which remains adequate).

---

End of SOVEREIGN Security Specification v1.0.0