Not "trust us." "Verify it yourself."
Abstract.
RigKillis a clean-room, zero-dependency reference implementation of an end-to-end verifiable (E2E-V) in-person paper voting system, combined with risk-limiting audits (RLA) — the architecture that election-security experts (NAS 2018) actually recommend for trustworthy national elections. It pairs four in-depth research documents with a working, fully-tested CLI system: exponential-ElGamal homomorphic tallying, threshold decryption via Pedersen DKG (no trusted dealer), zero-knowledge validity proofs, a hash-chained public bulletin board, Scantegrity-style confirmation codes, an everlasting-privacy variant, an independent verifier, and a complete RLA suite (BRAVO, SHANGRLA, ballot-comparison, D'Hondt). It also contributes a novel result: the first assorter-based RLA analysis for Korea's semi-linked proportional system (준연동형), which quantifies why such audits are hard. The project is deliberately honest about being research-grade — and that honesty is the point.
Elections are the foundation of democracy, and trust in them rests on a single conviction: "my vote was counted the way I cast it." Yet most of today's voting and tabulation systems give the voter no way to verify this. We are simply asked to trust the election authority and the machines.
This project inverts that premise. Modern cryptography and statistics already make all of the following possible at the same time:
- Verify your own ballot — confirm directly that what you marked was recorded.
- Let anyone verify the entire national tally — confirm mathematically that the totals are correct, without learning how anyone else voted.
- Preserve the secret ballot — who voted for whom stays secret, forever.
That these three are not a "fundamental conflict" but a balance that can be achieved simultaneously is the heart of end-to-end verifiable voting (E2E-V) — and this repository demonstrates it in working code.
Closed, proprietary voting systems are an anti-pattern that the security research community has warned against consistently (for example, the blockchain mobile voting app Voatz was shown by MIT analysis to have severe flaws). The integrity of an election system can only come from public scrutiny of open code. That is why this project is open source from the start, written with zero external dependencies (Python standard library only) so that anyone can read it line by line.
This work began with one citizen's simple question — "Can't someone build a system where I can directly confirm that my vote was reflected exactly, and that everyone else's votes were counted exactly too?" That question turns out to be the doorway to a formal field of cryptography (E2E-V), and this repository is the technical answer to it — from concepts all the way to a working implementation.
The project has two halves: research documents explaining the why, what, and how, and a working system that implements them.
| Document | Contents |
|---|---|
| E2E-Voting-Research-Report.md | Conceptual encyclopedia. The three verifiability properties; cryptographic mechanisms (homomorphic encryption, zero-knowledge proofs, mixnets, threshold decryption); a comparison of real systems (Helios, Belenios, ElectionGuard, Scantegrity, etc.); a "do we really need blockchain?" analysis; the coercion and untrusted-device problems — a source-verified deep research report. |
| E2E-Voting-Frontier-HardProblems.md | Map of the frontier. Coercion resistance (JCJ → Civitas → BeleniosRF → Selene), the untrusted device, and identity/eligibility — dissecting the foundational papers one by one and marking exactly what is still open. |
| E2E-Voting-ProblemStatements.md | Problem statements. The two research tracks — Everlasting Privacy and RLA — turned into actionable form: foundational papers, success criteria, threat model, first experiment. |
| E2E-Voting-Design-Belenios-Fork.md | Initial design. A learning path based on forking Belenios (kept for historical reference, since the project later pivoted to the in-person paper route). |
Part 2 · Implementation rigkill/ (a working system)
A pure-Python CLI system — about 2,200 lines, zero external dependencies. See rigkill/README.md for details.
# The whole flow in one line (setup -> vote -> tally -> independent verify -> RLA -> everlasting privacy)
RIGKILL_FAST=1 python3 -m rigkill demo| Property | Meaning | Group |
|---|---|---|
| Cast-as-intended | Did the machine correctly encrypt the candidate I chose? | Individual verifiability |
| Recorded-as-cast | Was my ballot posted to the public board without omission? | Individual verifiability |
| Counted-as-recorded | Were all ballots on the board tallied correctly? | Universal verifiability |
The key trick: prove mathematically that the entire tally is correct without decrypting any individual ballot. This uses homomorphic encryption, where multiplying ciphertexts adds the underlying plaintexts. Individual ballots stay secret forever; only the final total is decrypted — and only when several trustees cooperate.
Pure remote (internet) voting runs into two unsolved hard problems — coercion and malware on the voter's device. This system takes the route that security experts recommend: polling-place paper ballots + E2E cryptographic verification + risk-limiting audits (RLA):
(1) Crypto layer : confirmation codes + homomorphic tally + threshold-decryption proofs + public bulletin board -> RigKill verify
(2) Physical layer: paper originals + risk-limiting audit (statistical hand count) -> RigKill audit
The two layers are independent. If the crypto has a bug, the paper catches it; if the paper handling is suspect, the crypto catches it — belt-and-suspenders. And the key insight:
The voter does not follow the paper — they follow a confirmation code. Even after the paper leaves their hands, the code-to-candidate mapping committed before the election lets them confirm directly on the board that "my ballot was recorded as I chose."
Requirement: Python 3.8+ only. Nothing to install, no pip install.
git clone <this-repo>
cd rigkill
# Full election-flow demo (fast 256-bit group)
RIGKILL_FAST=1 python3 -m rigkill demo
# Run the entire test/demo suite (crypto core, election, DKG, RLA, semi-linked PR, comparison audit, CLI)
RIGKILL_FAST=1 bash rigkill/demos/run_all.shIndividual commands:
python3 -m rigkill setup --dir D --candidates "Cand1,Cand2,Cand3" --voters 30 --trustees 5 --threshold 3 --dkg
python3 -m rigkill simulate --dir D --plan 0:14,1:9,2:7
python3 -m rigkill tally --dir D # homomorphic tally + threshold decryption
python3 -m rigkill verify --dir D # independent verifier — anyone can re-verify from the board alone
python3 -m rigkill audit --dir D --method comparison # risk-limiting audit
python3 -m rigkill everlasting --dir D # everlasting-privacy variant
RIGKILL_FAST=1selects a 256-bit toy group for demo speed. Without it, a 2048-bit RFC 3526 group is used.
Voter --(1)encrypt--(2)ZK validity proof--(3)credential signature--+
v
Trustees (DKG, no dealer) [Public bulletin board: append-only hash chain + signatures]
| secret-shared key | ^
| +------------+ +-- Observers: independent verification
v v
[Homomorphic tally: product of all ciphertexts] [Voter: check my confirmation code = recorded-as-cast]
|
[Threshold decryption: t trustees cooperate + decryption proofs] -- individual ballots never decrypted
|
[Publish result] --> [Independent verifier + paper RLA = counted-as-recorded]
rigkill/
crypto/ group(Schnorr group, Fiat-Shamir) . elgamal(homomorphic) . pedersen(everlasting privacy)
shamir . threshold(threshold decryption) . dkg(distributed key generation, no dealer)
zk(Chaum-Pedersen, OR proofs) . signature(Schnorr)
board/ bulletin(append-only hash chain + Schnorr-signed board)
election/ ballot(validity proofs) . codes(Scantegrity confirmation codes) . tally . verifier
everlasting(Pedersen variant) . run(orchestration)
rla/ bravo . shangrla(assorter) . comparison(overstatement, SOTA-efficient)
proportional(D'Hondt) . jundong(Korea semi-linked PR *) . montecarlo
cli.py CLI entry point . demos/ six demos + run_all.sh
This project goes beyond a bare implementation to deliver verified guarantees and a new research result.
Risk-limiting audits (RLA) are well-established for U.S.-style plurality and D'Hondt proportional contests, but designing RLA assorters for Korea's semi-linked MMP (준연동형) seat allocation was essentially an empty space. This project analyzes it for the first time, implements it in rla/jundong.py, and pins down why it is hard with numbers:
Auditing the 3% electoral threshold is cheap (minimum margin ~0.005). But auditing the "deserved seats" rounding boundary has a margin of only ~0.5/300 ≈ 0.0017, requiring roughly 1,000× more samples (essentially a full hand count) for the same risk limit. → The real difficulty of a semi-linked RLA is not the threshold but the seat-rounding boundary. This quantitative finding is the starting point for follow-up work (designing smarter assertions that avoid the rounding boundary).
| Component | What makes it SOTA |
|---|---|
Pedersen DKG (crypto/dkg.py) |
Feldman-VSS joint DKG — no one knows the secret key (the dealer is removed). The verifier re-checks it from the commitments. |
Ballot-comparison RLA (rla/comparison.py) |
Overstatement assorter comparing paper to CVRs — about 5× more efficient than polling (83 vs 421 ballots in a 10-point race). |
Everlasting privacy (election/everlasting.py) |
Perfectly-hiding Pedersen commitments — even if the cryptography is broken in the future, past ballots remain secret forever. |
| Guarantee | How it is demonstrated | Result |
|---|---|---|
| Homomorphic tally + threshold decryption correctness | End-to-end test | Pass |
| Tamper detection | Flip one bit of a ballot -> verification fails | Pass |
| False winner | The audit refuses to confirm -> escalate to full count | Pass |
| False-certification rate <= alpha | Hundreds of Monte Carlo trials | 0.000-0.005 <= 0.05 |
| Everlasting privacy | Only the total opens; individual ballots cannot | Pass |
| Dealer-free key generation | The verifier re-checks the DKG commitments | Pass |
The first virtue of trustworthy election technology is honesty about its own limits. A voting system that overhypes is itself a red flag. So, to be clear:
- Demo/research-grade cryptography: the
RIGKILL_FASTtoy group is 256-bit and not secure, and even the default 2048-bit parameters are for learning. Key management, side channels, and DoS resistance are simplified. - Simplified DKG: complaint/restart rounds and robust agreement are omitted.
- Code layer vs. tally: here the authoritative tally is the cryptographic homomorphic tally, and confirmation codes serve individual verification + print audit. A full Scantegrity back-end mix (verifying the tally from codes alone) is not implemented.
- Coercion / untrusted device: these are avoided by switching the threat model to in-person paper. Remote coercion, chain voting, booth photography, etc. are out of scope (see the research documents).
- Semi-linked rounding boundary: currently only the threshold is practically auditable. A full audit of the rounding boundary is an open research problem.
These limitations are not defects — they are precise coordinates. This repository is for education, research, and reference, and at the same time it can be a starting point for organizational, academic-society, and community voting where coercion and device risks are low.
Contributions are welcome on the following next steps:
- Rounding-boundary-avoiding assertions for semi-linked PR — re-express the allocation as a highest-averages-style rule so it can be audited via D'Hondt-style ordering margins (the key open problem).
- Production cryptography — elliptic-curve groups, robust DKG (complaint rounds), formally-verified ZK proofs.
- Verifiable mixnet — a Terelius-Wikström-style shuffle for ranked/preferential voting.
- Full everlasting privacy — Cuvelier-Pereira-Peters commitment-consistent encryption.
- Accountability — dispute resolution: deciding who is at fault when "my code is missing" (Küsters-style).
- Post-quantum — lattice-based perfectly-hiding commitments.
This implementation stands on the following foundational works (cited in detail in the research documents):
- Homomorphic voting: Cramer, Gennaro, Schoenmakers, "A Secure and Optimally Efficient Multi-Authority Election Scheme" (EUROCRYPT 1997)
- Zero-knowledge proofs: Chaum-Pedersen (CRYPTO 1992) . Cramer-Damgård-Schoenmakers OR-composition (CRYPTO 1994)
- Threshold / distributed key generation: Pedersen (CRYPTO 1991) . Feldman VSS (FOCS 1987) . Gennaro et al. DKG
- Paper E2E: Chaum Scantegrity II . Ryan Prêt à Voter . Bell et al. STAR-Vote
- Web E2E: Adida Helios . Cortier et al. Belenios (Helios-C)
- Risk-limiting audits: Stark RLA (2008) . Lindeman-Stark BRAVO (2012) . Stark SHANGRLA (2020) / ALPHA (2022) . Stark-Teague D'Hondt RLA (2014)
- Coercion resistance: Juels-Catalano-Jakobsson JCJ (2005) . Clarkson-Chong-Myers Civitas (2008)
- Everlasting privacy: Moran-Naor (CRYPTO 2006) . Cuvelier-Pereira-Peters (ESORICS 2013)
- Blockchain critique: Park-Specter-Narula-Rivest "Going from Bad to Worse" (2021) . NAS "Securing the Vote" (2018)
This project welcomes contributions from cryptographers, statisticians, election experts, and civic developers alike. See CONTRIBUTING.md.
- Report bugs and security issues (especially crypto/statistical correctness).
- Tackle the open problems on the roadmap — especially the semi-linked rounding-boundary assertion.
- Strengthen, challenge, or add sources to the research documents.
- Translate into additional languages.
Recommended: GNU AGPL-3.0. Election tooling should remain permanently public and auditable, so strong copyleft is recommended (the same license used by Belenios, a pioneer of verifiable voting). Derivative works and hosted services must also release their source.
The final license is the repository owner's decision. Adding the
LICENSEfile is a separate step.
This software is a reference implementation for education and research. Do not use it as-is for binding political elections. A real election system additionally requires formal verification, independent security audits, hardware security, and legal and operational procedures.
An unverifiable vote is not a question of trust but of evidence. This project aims to return that evidence to everyone.