How ElectionGuard counts encrypted votes

Contents

• Ignore the asymmetric encryption
• Homomorphic addition
• Multiple options per ballot
• Zero knowledge proofs
• Put it all together

How is it possible for ElectionGuard to add up votes, and guarantee the final tally is accurate, without being able to read any of the individual ballots?

Ignore the asymmetric encryption

This is also really cool, but I’ll gloss over it for today because it’s ubiquitous on the internet and there are lots of explanations available. You can think of it as standard public key encryption: the voting machine encrypts each ballot to the public key generated by the guardians during the key ceremony. Then they decrypt the final tally with with their (shared) private key.

Instead, today I want to go over what happens inbetween during step 2: How do all the encrypted ballots become one big final encrypted tally?

Voting machine encrypts ballots

???

Guardians decrypt final tally

Homomorphic addition

The trick is that the encrypted votes are encoded as exponents, and exponents have a cool property: multiplying the same base number with two different exponents is equivalent to adding the exponents.

You can get some intuition for it by playing around in any calculator app or programming language interpreter. Here I’m using R.

> 10^1 * 10^1 == 10^(1+1)
[1] TRUE

> 10^1 * 10^0 == 10^(1+0)
[1] TRUE

> 10^5 * 10^7 == 10^(5+7)
[1] TRUE

Of course the encrypted votes aren’t in base 10. They’re in base some-huge-number-you-can’t-guess, which is what keeps you from reading them! But the principle stays the same and, importantly, you can do the multiplication without knowing the base. This is the property we want:

encrypt(a) * encrypt(b) = encrypt(a + b)

For example, say the secret base number is 34. Here’s how we could encrypt and decrypt with it:

encrypt <- function(vote)
  # to encrypt, raise 34 to the `vote`th power
  34 ^ vote
  
decrypt <- function(vote)
  # to decrypt, take the base-34 logarithm
  log(vote, base=34)

> encrypt(5)
[1] 45435424

> encrypt(7)
[1] 52523350144

Now without knowing the base OR the encrypted values, someone else can still find their product, and can know that’s the encryption of the sum of the encrypted values.

> 45435424 * 52523350144
[1] 2.386421e+18

Since we know the secret base is 34, we can also get the sum back:

> decrypt(2.386421e+18)
[1] 12

Brilliant! Now, there are a couple more nuances that aren’t hard to add to our example…

Multiple options per ballot

Each ballot is really a data structure with an encrypted number per candidate/option. The main election config says which ones belong to which contests. Let’s say our ballot has two contests, one with two options and one with three. It could be represented in R using a vector:

c(n,n , n,n,n)
  ___   _____
   |      |
   |      contest 2
   |
   contest 1

(One reason to use R today is we don’t have to change our encrypt/decrypt functions. They’ll work on vectors automatically.)

Zero knowledge proofs

The other nuance is that each encrypted number should either be a 1 or a 0. Most of the data in real ballots is made of zero knowledge proofs (out of scope for today) to guarantee that each number is a 1 or a 0 without revealing which! Otherwise, it would be possible to cheat by creating one ballot with huge numbers like c(10000, -10000, ...).

Put it all together

Anyway, using our same functions from above, a little more realistic run-through might look like this.

# 6 ballots with two contests each
# (contest 1 has 2 options and contest 2 has 3)
b1 <- c(1,0 , 1,0,0)
b2 <- c(1,0 , 1,0,0)
b3 <- c(0,1 , 1,0,0)
b4 <- c(0,1 , 0,1,0)
b5 <- c(0,1 , 0,1,0)
b6 <- c(0,1 , 0,0,1)

# encryption done by voting machines
e1 <- encrypt(b1)
e2 <- encrypt(b2)
e3 <- encrypt(b3)
e4 <- encrypt(b4)
e5 <- encrypt(b5)
e6 <- encrypt(b6)

# guardian tally ceremony,
# including homomorphic addition
eSums <- e1 * e2 * e3 * e4 * e5 * e6
decrypt(eSums)
# [1] 2 4 3 2 1
#     ___ _____
#      |    |
#      |    contest 2 results
#      |
#      contest 1 results

Cool, right?? It’s as if we added up the unencrypted ballots column-wise.

This has been a simplified example, but I hope it provides some intuition—and reassurance—about one of the big questions you might have as a skeptical voter. I suspect that explaining stuff like this well will play an important role in getting election systems upgraded over the medium-to-long term.