How ElectionGuard counts encrypted votes

Contents

• Ignore the asymmetric encryption for now
• Homomorphic addition
• More realistic ballots
  • Vectors
  • Ones and zeros
  • 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 for now

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 they have a cool property: multiplying the same base number with two different exponents is equivalent to adding the exponents.

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

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. For example, say the base 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! I love when math actually turns out to be useful.

More realistic ballots

There are a couple more nuances that aren’t hard to add to our example…

Vectors

Each ballot is really a vector with an encrypted number per 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 like this:

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.)

Ones and zeros

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 more realistic run-through might look like this.

# 6 ballots with two contests each
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 original 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.