Building a Cryptographically Verifiable Multi-Candidate Election System

In our previous post, we built a privacy-preserving, verifiable Yes/No referendum using partially homomorphic encryption, zero-knowledge proofs and threshold decryption. But real-world elections are rarely binary: they have multiple candidates, parties, or choices. That raises a new question: how do we tally votes for many options under encryption, without one candidate’s count bleeding into another’s, while still proving that every ballot is valid?

Red, white and blue political buttons reading Vote and I Voted, illustrating a multi-candidate election
Red, white, and blue political buttons with ‘Vote’ and ‘I Voted’ text for election and civic engagement themes by pexels

LightPHE offers two strategies, and the cryptosystem you choose decides which ones are available:


🙋‍♂️ You may consider to enroll my top-rated cryptography course on Udemy

Public Key Cryptography From Scratch

  • Base encoding packs every candidate’s tally into a single ciphertext by encrypting a vote for candidate k as base^k. The decrypted tally is a large number, so this needs a cryptosystem with a large plaintext space and direct decryption. So, Paillier or Damgard-Jurik are strong candidates for this approach.
  • One-hot encodes each ballot as an array of 0/1 ciphertexts, one per candidate, with a proof that exactly one slot is 1. Each candidate’s count stays small, so it works with Exponential ElGamal and Elliptic Curve ElGamal as well as Paillier and Damgard-Jurik.

Both approaches rely on the same building blocks: homomorphic addition to tally ballots without decrypting them, zero-knowledge proofs that every ballot is valid and bound to its voter, and threshold decryption in which trustees prove their partial results are correct, so no single party can read individual votes or fake the outcome.

In this post, we’ll dive into both approaches, compare their trade-offs, and walk through complete implementations in Python, Go, Java, and TypeScript.

Designing a Multi-Candidate E-Voting System

Our system will use four building blocks, all of which apply to both approaches:

1. Homomorphic addition. Ballots are summed while still encrypted, so individual votes are never decrypted.

2. Zero-knowledge proofs of ballot validity. These are OR-proofs, meaning they show a ballot encrypts one of the allowed values without revealing which:

  • Base encoding: a proof that the ciphertext encrypts one of base^0, base^1, …, base^(k−1).
  • One-hot: a proof that each slot is 0 or 1, plus a proof that the slots add up to 1. Voting for two parties, voting twice for one party, or leaving every slot empty all fail verification.

3. Binding each proof to its voter. Each proof is tied to the voter’s identity (context = voter). That’s why, in the code below, Mallory’s copy of Alice’s ballot fails to verify, and so do Oscar’s tampered ballots: doubling a base-encoded ballot to vote twice, or reordering the slots of a one-hot ballot to move his vote to another party. The context is just a public string, so the bulletin board that collects ballots must also authenticate voters, accept a ballot only for the ID of the authenticated voter, and accept at most one ballot per ID.

4. Verifiable threshold decryption. A dealer splits the private key among trustees (any 2 out of 3 in our examples) and forgets it. Any 2 trustees decrypt the tally partially, and each partial decryption carries a proof that it was computed with the trustee’s own share. This matters: without these proofs, a trustee nominated by one party can tamper with its partial decryption and quietly add 50 votes to its own party, because the Lagrange coefficients of the other trustees are public. With the proofs, the forged partial decryption is discarded and the honest trustees still decrypt the correct tally.

Approach 1: Base Encoding (Single Ciphertext)

In this approach, we utilize cryptosystems with a large plaintext space like Paillier or Damgard-Jurik. Instead of creating multiple ciphertexts for each candidate, we pack all party votes into a single ciphertext using a chosen base (B).

For instance, if our base is 100, a vote for a party k is encrypted as 100k.

Red (Index 0): 1000 = 1

Green (Index 1): 1001 = 100

Blue (Index 2): 1002 = 10000

During tallying, all individual ballots are homomorphically added together into one single ciphertext. When the trustees decrypt the final tally, the result is a packed integer (e.g., 10002), which can be easily split by reading digits from right to left: 2 votes for red, 0 for green and 1 for blue. The base must be greater than the number of votes a party can get—with base 100, a party can get at most 99 votes, since 100 votes for red would carry into green’s digit. Use a larger base for real elections, e.g. 1000001 for a million votes per party.





While Exponential-ElGamal or EC-ElGamal are additively homomorphic as well, their decryption requires solving a discrete logarithm, which is only feasible for small numbers. A packed tally like 10002—let alone one with a base of a million—is far beyond that. Therefore, this approach is reserved for schemes that decrypt directly, like Paillier and Damgard-Jurik. Their keys must be generated with safe_primes = True so that trustees can prove their partial decryptions.

Approach 2: One-Hot Encoding (One Ciphertext per Party)

In this approach, rather than packing all party votes into a single integer, each voter casts a vote as a one-hot vector (e.g., [1, 0, 0, 0] for a vote to the first party).

Supported by cryptosystems like Exponential-ElGamal, EC-ElGamal, Paillier, and Damgard-Jurik, individual ballots consist of an array of ciphertexts along with zero-knowledge proofs. During tallying, votes are summed slot by slot, meaning each party’s votes are counted independently in its own dedicated ciphertext slot. The trustees then decrypt each party’s count separately. Exponential-ElGamal keys must be generated with prime_order = True for the proofs and threshold decryption.

In both approaches, the dealer’s cryptosystem is never used to decrypt anything: it drops the private key right after splitting it, and a single trustee cannot decrypt a tally alone. Java snippets use assert for brevity, so run them with -ea to enable assertions.

Architectural Comparison

When choosing between Base Encoding and One-Hot Encoding for a multi-candidate election system, developers must weigh key trade-offs regarding algorithm compatibility, bandwidth, decryptions, and capacity limits:

One-hotBase Encoding
AlgorithmsEC ElGamal, Exponential ElGamal, Paillier, Damgard-JurikPaillier, Damgard-Jurik
Max votes per partyNo hard limit. With Paillier and Damgard-Jurik, decryption cost doesn’t depend on the count. With ElGamal variants, decryption time grows with the count (a discrete logarithm search)base – 1
Max partiesNo limitbase ^ parties < n (e.g. 51 parties at base 10^6 with 1024 bit key)
Ballot sizeGrows with the number of parties (k ciphertexts and k+1 proofs)One ciphertext, with a proof that grows with the number of parties
Tally decryptionsOne per partyOne in total

To put the ElGamal caveat into numbers: in Python on my laptop, decrypting a party’s count of 100,000 votes takes about 2 seconds with Exponential ElGamal (threshold decryption included), and about a minute with EC ElGamal, because the search grows linearly with the count. That is fine for a city council election, but for a nationwide election with millions of votes per party, Paillier or Damgard-Jurik with one-hot ballots is the safer choice.

When to Choose Base Encoding:

  • Ideal for elections with a small, fixed number of candidates and a known voter cap (e.g., board elections or local council voting).
  • Minimizes network payload during ballot submission since the entire ballot fits into a single ciphertext.
  • Drastically speeds up final tallying, requiring only one threshold decryption regardless of the candidate count.

When to Choose One-Hot Encoding:

  • Essential for large-scale, nationwide, or open-ended elections where candidate counts or total voters could exceed packed integer capacity.
  • Removes the overflow risk (base – 1) and the modulus capacity constraint (base^parties < n). With the ElGamal variants, keep the decryption time of large counts in mind.
  • Allows full leverage of Exponential-ElGamal and EC-ElGamal cryptosystems alongside Paillier and Damgard-Jurik.

What This Design Does Not Cover

As in the referendum, cryptography covers the tally, not the whole election. Voter authentication is up to the bulletin board. The dealer knows the private key during setup, so it must be trusted, or replaced with a distributed key generation protocol. A voter can still reveal the randomness of their ballot to prove how they voted, so coercion and vote selling need additional techniques. And the proofs show that a ballot is valid, not that it is the choice the voter intended, so a compromised voter device remains a risk.

Conclusion

Moving from a Yes/No referendum to a multi-candidate election doesn’t need new cryptography. It needs a smarter way to encode the ballot. Base encoding packs every candidate’s count into one ciphertext, so each ballot is compact and the whole tally is decrypted once. In exchange, you’re tied to Paillier or Damgard-Jurik and to two ceilings: votes per candidate must stay below the base, and base^candidates must fit within the key’s plaintext space. One-hot puts each candidate in its own slot. That removes both ceilings and opens the door to Exponential ElGamal and EC ElGamal, at the cost of ballots and proofs that grow with every candidate, one decryption per candidate, and—with the ElGamal variants—decryption time that grows with each candidate’s count.

Whichever you choose, the guarantees stay the same: ballots are tallied without being decrypted, zero-knowledge proofs reject malformed, copied or tampered ballots, and threshold decryption with proofs keeps any single trustee from reading votes or forging the result. As a rule of thumb, base encoding suits elections with a few candidates and a modest number of voters per candidate, while one-hot scales to long ballots and gives you the widest choice of cryptosystems. With LightPHE, either one is only a few lines of code.


Support this blog financially if you do like!

Buy me a coffee      Buy me a coffee


Leave a Reply