Viewing a single comment thread. View all comments

Bullboah t1_itqz0gc wrote

That’s interesting. How is verification that your vote correctly tabulated your choice achieved without giving you proof another person would recognize?

2

TheOfficialACM OP t1_itr7m60 wrote

There are a lot of variations on this, so I'm going to assume we're talking about how Microsoft's ElectionGuard project would work in the context of a ballot marking device. (I've written some of the code being used in ElectionGuard.)

Once the voter finishes specifying their vote, the machine computes an encrypted version of their vote. It's public key encryption, where the voting machine only knows the public key, so only the election official (or a group of election trustees working together, using a technique called threshold cryptography) can do the decryption.

The voting machine can also compute the hash of that encrypted ballot, and then hand it back to the voter, perhaps on a small receipt printer. Now here's the fun part: all the encrypted ballots for the entire election will be posted on some public web server somewhere. And you'll be able to use your receipt and figure out that a ballot matching your hash is right there where it's supposed to be. And now here's the crazy fun part: you can add all the encrypted ballots without first decrypting them. This is called an additive homomorphism. Every election observer can compute this same value, and compare it to the value that's ultimately decrypted by the election official, who provides a cryptographic proof that they did the decryption correctly. So, anybody can validate that their encrypted ballot is part of the big total and that the big total was decrypted correctly. But your receipt doesn't let you sell your vote, since it's the hash of an encrypted ballot, and that ballot is never individually decrypted. (This paragraph summarizes the "counted as cast" property.)

But wait, you ask, why should I believe that my ballot was correctly encrypted in the first place? Turns out, there are a number of independent ways to prove this.

  1. Your paper ballot, which is human readable, includes the hash of your ciphertext below it. A risk-limiting audit would, for each ballot being audited, recompute the encryption of the ballot, based on the human-readable text, and make sure that the hash matches.
  2. Ballots that are spoiled aren't tabulated. That means it's safe for the election official to decrypt those spoiled ballots. So we could create a process where regular voters and/or trained auditors are allowed to keep copies of spoiled ballots, and we'll check later on whether the human-readable text matches up with the ciphertext.

The cool trick here is that the machine doesn't know which ballots will be cast and which will be audited, so if it's going to cheat, it needs to cheat before it knows whether it might be caught. This is called a Benaloh challenge. Josh Benaloh is also, not coincidentally, one of the designers behind Microsoft's ElectionGuard.

14

Bullboah t1_itrgiin wrote

Very interesting, thanks for the thorough and informative response!

2

PaulSnow t1_itrjuks wrote

If the hash doesn't give feedback to the voter that the ballot is counted correctly, I think you need open source to ensure that is actually done correctly.

0

TheOfficialACM OP t1_itrmu5i wrote

The trick with these fancy e2e-verifiable schemes is that they're very good at providing the voter with evidence that everything worked perfectly, but if something goes wrong, and there are a lot of ways for things to go wrong, it's not necessarily easy to pinpoint the problem.

ElectionGuard happens to be open source, but that's not a requirement for security. In fact, the magic of e2e-verifiable schemes is that they create a much more interesting property called software independence, which means that we can verify a correct election outcome without being required to trust any of the software used by the election officials.

Risk limiting audits, by the way, are also a method of achieving software independence, without any cryptography at all.

7