fhe-vote, a guide

fhe-vote is a small end-to-end voting system: registration and identity proofing are treated as solved and out of scope; everything from ballot construction to public verification of the result is in scope. About nineteen hundred lines of Python across nine modules, with only numpy and cryptography as dependencies. It runs live at fhe-vote.theqissilent.app, and the whole board it produces — every ballot, every proof, every checkpoint — is downloadable as one JSON blob at /api/board.

The target it aims at is plurality voting: one selection from C candidates, aggregated to a per-candidate total. Not ranked-choice, not approval, not write-ins. That constraint keeps the encoding simple — one encrypted bit per candidate, exactly one of them set — and lets the proofs stay tractable. Everything else the protocol does (proof of well-formedness, threshold decryption, universal verification) is a consequence of taking that encoding seriously.

Concretely, the site lets you do three things: cast a ballot for one of the pre-registered voter slots and see it land on the public board; spoil a ballot instead of casting it and watch the client's honesty be verified; close the polls and run the threshold decryption to produce the totals. Then it lets you run the universal verifier — the same one that ships with the code, which knows nothing but what is on the board — and reproduce the result from first principles.

The elevator pitch for homomorphic voting is that the server can add up ballots it cannot read. That sounds like the whole problem solved. It is not, because the same property that stops the server reading a ballot stops it noticing that the ballot is garbage.

A voter who encrypts 1000 instead of 1 produces a ciphertext indistinguishable from an honest one, aggregates perfectly, and adds a thousand votes to their candidate. The server has no way to see it. Neither does anyone else — until the tally is decrypted and the numbers are absurd, at which point the election is void and the culprit is unidentifiable.

So the hard requirement isn't "encrypt the ballots" — that's the easy part. The hard requirement is every ballot must carry a public proof that its plaintext is a valid selection vector, verifiable without decrypting it. This is where the engineering effort in the system went (zkp.py), and it is the dominant cost: roughly 95% of a ballot's byte size, and nearly all of the CPU time on both sides.

The second thing homomorphic encryption doesn't give you is verifiable decryption. The trustees who jointly hold the key can, in principle, announce whatever total they like. The aggregation step is publicly recomputable — anyone with the board can sum the ciphertexts — but the final decryption isn't, unless each trustee proves that its published decryption share was actually derived from the key share it committed to before the election. That is the second proof system, in threshold.py.

Between them, these two proof systems are what turns "the server can't read the ballots" into "the result is correct and everyone can check it." Take either one out and you have a marketing slide, not a voting system.

The whole construction works in a polynomial ring R_q = Z_q[X]/(X^n + 1), with n a power of two and q held in residue-number-system form as a product of L NTT-friendly primes, each below 2³¹. Every modular product then fits in an int64, numpy handles the entire arithmetic layer without bignums, and negacyclic multiplication reduces to twelve stages of Cooley–Tukey NTT followed by pointwise multiplication (ring.py).

On top of the ring sits standard BFV / Fan–Vercauteren encryption. A key is a small ternary polynomial s; the public key is a pair (b, a) where a is derived from a fixed CRS seed (nobody knows a trapdoor for it) and b = −(a·s) + e for a small error e. A ciphertext of a plaintext m ∈ Z_t under randomness r = (u, e0, e1) is:

c0 = b·u + e0 + Δ·m        where Δ = ⌊q/t⌋
c1 = a·u + e1
Dec(c) = round_t( (c0 + c1·s) · t / q )

Ring-LWE security means an adversary who sees (c0, c1) but not s can't distinguish a real ciphertext from uniform noise. That's the confidentiality guarantee the server inherits when it stores ballots.

A vote for candidate j is a vector of C ciphertexts — one per candidate — c_j = Enc(b_j) with each b_j ∈ {0, 1} and Σ b_j = 1. The server never sees the b_j; it just receives the C ciphertexts and the proofs. That one-ciphertext-per-candidate choice is a deliberate one. A packed alternative — CRT-slot-batching all C bits into one ciphertext — would cut ballot size by a factor of C, but the sum-to-one check then requires Galois automorphisms and key-switching keys, which enlarge the trusted key material (§11.2 of the design document). Kept in the backlog, not shipped.

Only the additive half of BFV is exercised. Two ciphertexts add coordinate-wise; a ciphertext plus a plaintext constant is just addition on the c0 component. That's all a plurality tally needs. The multiplicative half — and with it relinearisation keys — is left intact in bfv.py but unused, because relinearisation keys enlarge the key material without buying any privacy for this use case.

From § 02, a ballot is only a ballot if you can check it's well-formed without decrypting it. Two properties have to be proven per ballot:

1. every c_j encrypts a bit, not a larger number that would inflate a candidate's tally; and
2. the bits sum to exactly one, not zero (a blank ballot, undetectable) and not more than one (an overvote).

Both proofs share the same skeleton: M parallel repetitions of a two-branch sigma protocol, compiled non-interactive by Fiat–Shamir, with uniform masking and rejection sampling. Soundness error is 2^−M. Zero-knowledge is statistical and exact, not computational — the accepted response is uniform on a fixed box, so the transcript really is independent of the vote.

The bit-proof, one repetition at a time

Recall c = Enc(b) for some b. Consider the companion ciphertext Δ·1 − c: this is an encryption of 1 − b. Notice that one of the pair encrypts a bit exactly when the other does. Per repetition the prover picks a secret flip bit γ_k and a mask ρ_k, and sends the commitment:

A_k = (γ_k ? Δ·1 − c : c) + Enc(0; ρ_k)
    = Enc(β_k ; ±r + ρ_k)          β_k = b XOR γ_k

The verifier answers with a challenge bit d_k:

• d_k = 0 → prover reveals (γ_k, seed_k). The verifier recomputes A_k from scratch, and checks it agrees. This proves A_k really is one of c or Δ−c.
• d_k = 1 → prover reveals (β_k, z_k). The verifier checks A_k = Enc(β_k ; z_k) with β_k ∈ {0, 1} and ‖z_k‖ inside a derived bound. This proves A_k encrypts a bit.

Neither branch alone proves anything useful; a cheater can trivially answer either. But being able to answer both branches simultaneously would force c to encrypt a bit — the only way A_k is both a bit and one of {c, Δ−c}. Under Fiat–Shamir the prover doesn't get to pick which branch will be opened; the challenge is derived from a hash of A_1…A_M. So each repetition halves a cheat's success probability, and M repetitions crush it to 2^−M.

A subtle piece of the zero-knowledge argument sits in that β_k is uniform. In the d_k = 0 case γ_k is never revealed on that branch, so β_k = b XOR γ_k hides b. In the d_k = 1 case z_k is uniform on a fixed box by rejection sampling. So neither the challenge bits nor the responses depend on b. The transcript — even its byte length — must be independent of the vote, and the test suite verifies this statistically.

The sum-proof

Once every c_j is known to encrypt a bit, all that's left is to prove Σ b_j = 1. Notice that if S = Σ c_j − Δ·1, then S is a ciphertext under randomness r_sum = Σ r_j, and its plaintext is (Σ b_j) − 1. So proving S is an encryption of zero — with the same skeleton as the bit-proof, minus the flip bit — nails the sum-to-one property.

The witness here is C times the size of a single ballot's randomness, so the masking bound must scale accordingly. In zkp.py this is the mult=C parameter passed to prove_zero, which is derived by the same function the verifier uses in verify_zero. Prover and verifier must call the same bound-derivation function; the design document calls this out as an invariant precisely because a hand-set bound on one side is exactly the kind of mistake that ships.

The four things every proof is bound to

Every Fiat–Shamir challenge inside a ballot is derived from SHA-256 over the tuple (election_id, voter_id, slot, H(all C ciphertexts)). The consequences:

• A bit-proof cannot be lifted from one candidate slot to another — the slot field changes.
• A ballot cannot be replayed by another voter — the voter_id is bound in.
• Proofs from an old election can't be reused in a new one — the election_id is bound in.
• Ciphertexts and proofs cannot be re-paired — the hash of the entire ciphertext vector is bound in, so swapping the ciphertext under a proof breaks the challenge.

All four of these have negative tests in tests.py. A validation routine that has never been shown a bad input is not evidence of anything.

The secret decryption key for the election is never held by anyone. Not on the server. Not on a trustee's machine. Not on a hardware security module. It doesn't exist as a coherent object at any point in the protocol. It exists only as an additive sharing.

Setup is one round. k trustees each generate their own small ternary secret s_i, produce b_i = −(a·s_i) + e_i, and publish b_i together with a Fiat–Shamir proof of knowledge of a small (s_i, e_i) behind it. The election public key is b = Σ b_i, which corresponds to the (nonexistent) secret s = Σ s_i. Every ballot is encrypted under (b, a). Nobody, individually or as a subset, can decrypt anything.

Rogue-key defence

The reason each trustee's KeyShareProof exists is concrete: without it, a trustee who publishes last can choose b_k to cancel the honest ones and effectively own the whole key. Requiring a proof of knowledge of a small pre-image blocks that. combine_public_key verifies every trustee's proof before summing and refuses otherwise.

Decryption — once, on the aggregate only

After polls close, the server publishes the aggregate ciphertext (C0, C1) = Σ c_j for each candidate. Each trustee then computes a partial decryption:

d_i = c1·s_i + E_i         E_i ← U[−S, S]

That extra term E_i — smudging noise, or noise flooding — is essential. Without it, the published d_i would leak s_i (an attacker who knows the aggregate ciphertext could subtract off the deterministic structure and read the small s_i directly out of the residual). The magnitude S must exceed the accumulated ballot noise by the desired statistical security margin, and that constraint is what pins down the parameter choices in § 09.

Each d_i ships with a DecShareProof: a Fiat–Shamir proof that the same s_i committed to in b_i was used to produce d_i, with a smudging term inside a bounded interval. This uses relaxed extraction (the "slack factor" you'll see in lattice-proof literature), so it proves (γ − γ')·s_i rather than s_i for a small pair of challenges — standard for this style of proof, and stated explicitly rather than glossed. The ballot proofs above are stronger (full extraction).

Anyone with the board can then combine:

phase = c0 + Σ d_i
      ≈ Δ·(vote count for this candidate)   (mod q)

and round to Z_t to recover the total. That Σ d_i is where the trustees' individual key shares finally combine into the aggregate key — but only inside the sum, applied only to the aggregate ciphertext, and producing only the tally. The individual votes never appear.

A voter cannot see inside their own ballot. It's a ciphertext. So how does the voter know their client encrypted the choice they actually made? A malicious client could quietly swap in a vote for whoever paid the developer.

The answer is the Benaloh challenge, sometimes called cast-or-audit. It works like this:

1. The client builds a signed ballot for the voter's choice.
2. The client sends only H(ballot) — the digest, not the ballot itself — to /prepare.
3. The server records the commitment on the public board and signs it. The server is now publicly bound to this particular ballot.
4. Only now does the voter decide. There are two paths:
   • Audit → the client reveals the randomness. The randomness is published on the board. Anyone can re-encrypt the stated choice under the revealed randomness and compare byte-for-byte with the ballot the server committed to. If the client cheated, this fails. If the client was honest, this succeeds — but the ballot is now spoiled and never counted.
   • Cast → the randomness is destroyed; the ballot is verified and appended; a receipt is returned.

Because the server commits before the voter chooses, a cheating client cannot know in advance whether it will be caught. Each audit catches a cheat with probability ½. A voter may audit as many times as they like before finally casting, so the undetected-cheat probability shrinks by half each time. Ten audits before casting means a cheating client survives with probability 2⁻¹⁰.

Two features protect this against re-use tricks. First, the session created by /prepare is single-use — you cannot spoil a ballot to reveal its randomness and then also cast it. The server marks the session spent the moment either action succeeds. Second, audited ballots reveal their randomness (which publicly leaks the vote) but are never counted — and cast ballots are counted but never reveal their randomness. So the voter still cannot prove to a coercer how they voted: any receipt they show either opens to a ballot that never counted, or opens to nothing at all.

Re-voting as the anti-coercion escape hatch

The system counts only each voter's last valid ballot. If a coercer stands behind you at the terminal and demands you vote for their candidate, you comply, then log back in later, alone, and overwrite it. The published counted_digests let anyone confirm the re-vote policy was applied correctly — each voter appears at most once in the counted set, and the retained digest is the latest one on the board.

Every write to the system — the election description, the trustee key proofs, every commitment, every audited ballot, every cast ballot, every rejected ballot, the close event, every decryption share, the final result — goes on a signed append-only Merkle log. The tree follows the RFC 6962 convention (Certificate Transparency's), with domain separators for leaf and interior nodes so no leaf can be forged as an internal node or vice versa.

Each append produces a signed checkpoint: the current tree size, the current Merkle root, and the board's public signing key, signed by the board. A voter's receipt is the triple (entry_hash, inclusion_path, signed_checkpoint): proof that a particular entry — identified only by its hash, not by any content the voter would rather not disclose — is in the tallied set. Anyone can verify a receipt against the current checkpoint without needing to see the ballot's contents.

The Voter.confirm_still_included helper re-checks a receipt against the current live board. That's what catches a server that accepts a ballot, issues a happy-looking receipt, and then quietly drops it later — the receipt still verifies against its old checkpoint (because it was genuinely valid at that moment), but the inclusion proof no longer holds against the current checkpoint.

The universal verifier lives in verifier.py. It takes a board snapshot and nothing else — no keys, no server cooperation, no witness testimony — and re-derives the entire election result from the public bytes. There are seventeen checks; the running site exposes them under /api/verify as a JSON structure, and the demo page renders them as a pass/fail ledger.

Concretely, the verifier:

1. Recomputes the Merkle root and checks that the checkpoint's signature verifies under the published board key.
2. Confirms exactly one election entry, at sequence 0, and parses the parameters from what the board itself says they are — never trusting anything handed to it privately.
3. Verifies every trustee's KeyShareProof, and checks that the published trustee shares sum to the published election public key. Both must hold, jointly.
4. For every cast ballot: valid voter signature, valid bit-proof for each of the C ciphertexts, valid sum-proof.
5. For every audited ballot: the opening re-encrypts to what the board claims, and no audited ballot was counted.
6. Confirms the counted set matches the re-vote policy — each voter appears at most once, and the retained digest is the last one for that voter that made it to the board.
7. Independently recomputes the coordinate-wise homomorphic sum of the counted ballots, and checks it equals the aggregate the server published.
8. For every decryption share: DecShareProof verifies against the trustee's committed key share.
9. Combines the shares from every trustee, decodes to the plaintext tallies, and checks they equal the announced result — and that the totals sum to the number of counted ballots.

Any failure marks the whole verification failed, and the report says exactly which check tripped. The test suite for the codebase runs the verifier against three deliberately forged boards — an inflated total, a silently deleted ballot, a swapped decryption share — each of which passes Merkle self-consistency because the forgery includes a fresh re-signing, and each of which still fails one of these checks.

Three parameter profiles are shipped. TOY is what runs on the demo site — small, fast, and cryptographically negligible. DEMO is what the design document defaults to — realistic ring size, sufficient security margin against an honest electorate. PRODUCTION is what you would actually deploy: wider ring, wider modulus, headroom for a large electorate and a strong smudging term.

The binding constraint is:

accumulated ballot noise × 2^(statistical security) ≤ smudge bound ≤ q/2t

With t greater than the maximum vote total any single candidate could receive. At DEMO parameters, the measured noise is 2⁹ after one honest ballot, 2¹¹ after ten, and 2¹⁴ after nine hundred, leaving 2⁶⁴ of headroom to the decryption ceiling — ample.

An adversarial ballot — one that just squeezes past the proof response bound — is much noisier: about 2³⁰ at DEMO for a single ballot, and 2⁴⁰ aggregated over 10³. At DEMO the statistical hiding of the decryption shares is 2²⁷ and the margin to the ceiling is 2¹⁰. These are deliberately tight, because DEMO is a "correctness at scale" profile, not a "deploy against a motivated adversary" profile. PRODUCTION widens both to 2⁵⁷ statistical hiding and 2⁴⁸ margin, and its reps=64 crushes the grinding attack (see §8.1 of the design document) that makes reps=32 feasible over months of compute for a well-resourced attacker.

Cost

Pure Python plus numpy, single core:

Read the ballot size row twice. Transcript size, not ciphertext size, is the cost — about 95% of a ballot is proof material. This is the fundamental tension in lattice-based verifiable voting, and the single strongest argument for eventually replacing the repeated sigma protocols with a succinct lattice proof system (LaBRADOR, Greyhound). That single change would take ballots from megabytes to kilobytes and is on the roadmap as the difference between a demonstration and a deployable system.

Stated as a table, because that's the useful shape.

Cryptographic assumptions

Decisional Ring-LWE at the stated parameters; SHA-256 and SHAKE-256 as random oracles (Fiat–Shamir); EUF-CMA of the signature scheme (currently Ed25519 — see the next section).

The trust distribution point is worth making twice: no single party — not the server, not any subset of trustees short of unanimity, not the network, not the board operator — can decrypt anything. The secret key is never assembled at any point in the protocol, on any machine, at any time. It exists only as an additive sharing.

Stated plainly, because a design document that only lists strengths is marketing.

• Signatures are not post-quantum. The board checkpoints, the voter ballot signatures, and the trustee key commitments are all signed with Ed25519. Every other part of the stack — encryption, KEM analogue, key generation, threshold decryption, ballot proofs — is Ring-LWE-based and therefore post-quantum. Ed25519 is the last classical component. It matters for long-term verifiability: a future quantum adversary could forge historical checkpoints and retroactively undermine an archived election. Swapping board.Signer for ML-DSA-87 is a two-method interface change and top of the roadmap.
• The threshold is k-of-k, not t-of-k. Every trustee must participate in decryption. A single unavailable or uncooperative trustee halts the tally permanently. The situation is detectable, not recoverable. A production deployment needs t-of-k — Shamir over the ring with clearing-denominator tricks, or replicated secret sharing for small k. Also on the roadmap.
• Coercion resistance is partial. Cast-or-audit plus re-voting handles vote-buying and after-the-fact coercion. Neither handles a coercer who is physically present for the voter's final ballot, nor one who demands the voter abstain. Full coercion resistance in the JCJ / Civitas sense (fake credentials indistinguishable from real ones) is a substantially different and more expensive protocol.
• The client sees the plaintext. Unavoidable for any system where a human expresses a choice to a device. Cast-or-audit reduces this from an unqualified trust assumption to a detection probability — but does not eliminate it.
• Results are per-candidate totals, not per-precinct. Fine for plurality. Small precincts are inherently disclosive (three voters, three–zero result reveals everyone). Ranked-choice or write-ins need a different encoding and probably a mixnet rather than homomorphic tallying.
• The CRS polynomial a is derived from a fixed seed. It should be per-election and ideally from a public randomness beacon — drand, the League of Entropy, an NIST-published beacon. Presently it's constant across every deployment, which is fine for the demo, not fine for real use.
• The code is not constant-time. The client's encryption path handles the plaintext choice; everything else in the pipeline is public by construction. Timing side channels on the client are the risk. Straightforward to fix, not yet done.
• The verifier loads the whole board as one JSON blob. At DEMO parameters, seven ballots produce a ~44 MB board; production would be worse. Streaming board transfer and incremental verification are on the roadmap.
• No formal or machine-checked proofs. Soundness and zero-knowledge arguments in zkp.py are prose backed by tests, not by machine-verified theorems.

Papers

• Brakerski, "Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP" (2012) — the BFV construction.
• Fan & Vercauteren, "Somewhat Practical Fully Homomorphic Encryption" (2012) — the other half of "BFV."
• Boneh et al., "Threshold Cryptosystems From Threshold Fully Homomorphic Encryption" — threshold decryption and noise flooding for lattice-based FHE.
• Benaloh, "Verifiable Secret-Ballot Elections" (1987) — the original cast-or-audit protocol.
• Beullens et al., "LaBRADOR: Compact Proofs for R1CS from Module-SIS" — the succinct-proof direction fhe-vote's ballot proofs would eventually move toward.

Standards

• Homomorphic Encryption Security Standard — the parameter tables that anchor DEMO and PRODUCTION.
• FIPS 204 — ML-DSA, the post-quantum signature that will replace Ed25519 in the board and voter signatures.
• RFC 6962 — Certificate Transparency's Merkle tree, whose construction the bulletin board copies.
• RFC 8032 — Ed25519, the current signature choice.

Adjacent

• theqissilent.app — parent site.
• pq-share — a guide — the sibling application; end-to-end encrypted file sharing with a per-send cipher picker.
• Live bulletin board — the current board of the demo election, as JSON.
• Live verifier output — the seventeen-check ledger for the current election.