TheOfficialACM OP t1_itqwe5v wrote on October 25, 2022 at 5:21 PM

Reply to comment by PaulSnow in I am the co-author behind ACM’s TechBrief on Election Security: Risk-limiting Audits. Ask me anything about election security! by TheOfficialACM

There's an entire academic discipline dedicated to the world of election integrity, and an important technique that's crossing the divide from academia to practice is called "end-to-end verifiable elections". Without getting lost in the technical details of how and why different encryption techniques are used, all of these voting systems generally include a concept called a "public bulletin board". If you squint at it, there isn't all that much difference between a public bulletin board and a blockchain. Both use cryptographic hash functions to build linear chains or tree-like structures.

The essential difference is that blockchains are "decentralized", which means that nobody is in charge. Instead, a series of unrelated parties reach a consensus as to what the blockchain means. In an election, however, all the parties are known in advance, and disputes are generally resolved through administrative processes or lawsuits. This means that public bulletin boards don't need consensus mechanisms. Instead, they're generally about publishing encrypted votes in such a way that a voter can verify that their vote was "counted as cast" (i.e., you get a strong proof that your vote was tabulated exactly as you cast it) as well as "cast as intended" (i.e., the machine didn't misinterpret your vote as you cast it). The exciting part of the cryptography is that we can achieve both of these properties without allowing you, the voter, to have enough evidence to be able to prove to anybody else how you voted (so, we don't enable bribery or coercion).

Bullboah t1_itqz0gc wrote on October 25, 2022 at 5:38 PM

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

TheOfficialACM OP t1_itr7m60 wrote on October 25, 2022 at 6:33 PM

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.

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

Bullboah t1_itrgiin wrote on October 25, 2022 at 7:30 PM

Very interesting, thanks for the thorough and informative response!

PaulSnow t1_itrjuks wrote on October 25, 2022 at 7:51 PM

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.

TheOfficialACM OP t1_itrmu5i wrote on October 25, 2022 at 8:10 PM

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.

PaulSnow t1_itrif3f wrote on October 25, 2022 at 7:42 PM

My point really isn't about counting or verifying votes, but the monitoring of processes. Of course, being in the blockchain myself, I've focused on creating cryptographic proofs of sequences of events, and gathering all those proofs into summaries (block hashes if you will).

Allowing the logging of all the processes behind voting (the set up, poll, venue, setup, voting machine configurations), observers, workers, video, etc.) all to the blockchain, you end up with time sequences and actions that create responsibilities. Failures in process can't be hidden.

I feel actual voting and ballots don't gain much from the blockchain, though there are ways to use the blockchain for voting. The real gain is to audit the execution of the election.

Public blockchains are much more complex than your description, and do allow for selecting authorities in distributed locations that all contribute to a unified (cryptographically speaking) log of events.

TheOfficialACM OP t1_itrn7r6 wrote on October 25, 2022 at 8:12 PM

A Reddit AMA is the wrong place to get into the finer points of blockchains, cryptocurrency, and/or public bulletin boards.

Suffice to say that one of the core features of most blockchains is consensus, while one of the core features of a public bulletin board is maintaining evidence. Those are emphatically not the same thing, even though many of the same cryptographic techniques (zero knowledge proofs, hash data structures, etc.) are used in both settings.